Score : $425$ points

问题陈述

在数轴上有 $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}'$。

以上为大语言模型 kimi 翻译，仅供参考。

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