103643: [Atcoder]ABC364 D - K-th Nearest

Problem Statement

There are $N+Q$ points $A_1,\dots,A_N,B_1,\dots,B_Q$ on a number line, where point $A_i$ has a coordinate $a_i$ and point $B_j$ has a coordinate $b_j$.

For each $j=1,2,\dots,Q$, answer the following question:

• Let $X$ be the point among $A_1,A_2,\dots,A_N$ that is the $k_j$-th closest to point $B_j$. Find the distance between points $X$ and $B_j$. More formally, let $d_i$ be the distance between points $A_i$ and $B_j$. Sort $(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}'$.

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 input values are integers.

Input

The input is given from 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

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

Sample Input 1

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

Sample Output 1

7
3
13

Let us explain the first query.

The distances from points $A_1, A_2, A_3, A_4$ to point $B_1$ are $1, 1, 7, 8$, respectively, so the 3rd closest to point $B_1$ is point $A_3$. Therefore, print the distance between point $A_3$ and point $B_1$, which is $7$.

Sample Input 2

2 2
0 0
0 1
0 2

Sample Output 2

0
0

There may be multiple points with the same coordinates.

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

问题陈述

在数轴上有$N+Q$个点$A_1,\dots,A_N,B_1,\dots,B_Q$，其中点$A_i$的坐标为$a_i$，点$B_j$的坐标为$b_j$。

对于每个$j=1,2,\dots,Q$，回答以下问题：

• 设$X$为$A_1,A_2,\dots,A_N$中到点$B_j$第$k_j$近的点。求点$X$和点$B_j$之间的距离。 更正式地说，设$d_i$为点$A_i$和点$B_j$之间的距离。将$(d_1,d_2,\dots,d_N)$按升序排序得到序列$(d_1',d_2',\dots,d_N')$。找到$d_{k_j}'$。

约束条件

• $1 \leq N, Q \leq 10^5$
• $-10^8 \leq a_i, b_j \leq 10^8$
• $1 \leq k_j \leq N$
• 所有输入值都是整数。

输入

输入从标准输入以以下格式给出：

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

输出

打印$Q$行。 第$l$行$(1 \leq l \leq Q)$应包含对$j=l$问题的答案，作为一个整数。

示例输入1

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

示例输出1

7
3
13

让我们解释第一个查询。

点$A_1, A_2, A_3, A_4$到点$B_1$的距离分别为$1, 1, 7, 8$，所以到点$B_1$第3近的是点$A_3$。 因此，打印点$A_3$和点$B_1$之间的距离，即$7$。

示例输入2

2 2
0 0
0 1
0 2

示例输出2

0
0

可能有多个点的坐标相同。

示例输入3

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

示例输出3

11
66
59
54
88