Problem Description

On a number line, there are $ N+Q $ points $A_1,\dots,A_N,B_1,\dots,B_Q$. The coordinates of point $ A_i $ are $ a_i $, and the coordinates of point $ B_j $ are $ b_j $.

For each $j=1,2,\dots,Q$, solve the following problem:

• Among the points $A_1,A_2,\dots,A_N$, let $ X $ be the point that is the $ k_j $-th closest to point $ B_j $. Determine the distance between point $ X $ and point $ B_j $. More formally, let $ d_i $ be the distance between point $ A_i $ and point $ B_j $. Sort the distances $(d_1,d_2,\dots,d_N)$ in ascending order to get the sequence $(d_1',d_2',\dots,d_N')$. Find $ d_{k_j}' $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ a_1 $ $ a_2 $ $\dots$ $ a_N $ $ b_1 $ $ k_1 $ $ b_2 $ $ k_2 $ $\vdots$ $ b_Q $ $ k_Q $

Output Format

Output $ Q $ lines. The $ l $-th line (where $1\leq\ l\ \leq\ Q$) should contain the answer to the problem for $ j=l $ as an integer.

Sample Input and Output

Sample Input #1

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

Sample Output #1

7
3
13

Sample Input #2

2 2
0 0
0 1
0 2

Sample Output #2

0
0

Sample Input #3

10 5
-84 -60 -41 -100 8 -8 -52 -62 -61 -76
-52 5
14 4
-2 6
46 2
26 7

Sample Output #3

11
66
59
54
88

Notes/Hints

Constraints

• $1\leq\ N,Q\ \leq\ 10^5$
• $-10^8\leq\ a_i,b_j\ \leq\ 10^8$
• $1\leq\ k_j\leq\ N$
• All inputs are integers

Sample Explanation 1

For the first query, the distances between points $ A_1,A_2,A_3,A_4 $ and point $ B_1 $ are $ 1,1,7,8 $ respectively. The third closest point to $ B_1 $ is $ A_3 $. Therefore, output the distance $ 7 $ between $ A_3 $ and $ B_1 $.

Sample Explanation 2

There could be multiple points at the same coordinate.

见题面 Input 部分

见题面 Output 部分