煞氣の阿弟即將迎接他的第一次高一新生活，甫進入小熊班の阿弟全班立刻被老師叫到教室後面排排站。

老師想對班級成員的身高進行深入研究，但因為阿弟班的同學太多了，老師無法立刻算出數據。

請你幫阿弟寫個程式給老師，讓他能在開學第一天就能讓老師有好的印象，幫他交到新朋友！

這個程式要支援兩種詢問：

詢問一：找到排列中的一個人 \(i\)，找出所有 \(j\) ( \(i\neq j\) ) 中 \(|a_j-a_i|\) 第 \(k\) 小的值

詢問二：找到排列中任兩個人 \(x, y\) 滿足 \(x<y\) 的所有差值 \(a_y-a_x\) 中第 \(m\) 小的差值

Input

第一行包含兩個整數 \(n, q\) ， \(n\) 代表阿弟班的學生人數， \(q\) 代表詢問次數。

\(1\le n\le 20000, 1\le q\le 10\)

第二行包含 \(n\) 個數 \(a_i\) ，代表阿弟班學生的身高，由於阿弟特別電，所以他同學的身高可能為負。

\(-10^8\le a_i\le 10^8\)

接下來 \(q\) 行詢問中：

• \(1\) \(i\) \(k\) ： 代表第一種詢問

\(1\le i\le n\)

\(1\le k<n\)

• \(2\) \(m\) ： 代表第二種詢問

\(1\le m\le\frac {n\cdot (n-1)} {2}\)

Output

輸出 \(q\) 行，包含一個整數，代表詢問的結果。

Constraints

第 \(1\) 組測資, 沒有第二種詢問。\((12\text{%})\)

第 \(2\) 組測資, \(n\le 1000\)。\((17\text{%})\)

第 \(3\) 組測資, \(1\le a_i\le 2\cdot 10^5\)。\((36\text{%})\)

第 \(4\) 組測資, 沒有其他限制。\((35\text{%})\)

Sample Input 1

4 6
1 2 4 7
1 2 1
1 2 3
2 1
2 3
2 4
2 6

Sample Output 1

1
5
1
3
3
6

Sample Input 2

5 7
-10 2 0 6 1
1 3 4
2 1
2 3
1 3 1
2 10
2 7
2 5

Sample Output 2

10
-5
-1
1
16
10
4