第 K 近的点

题目描述

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

输入格式

输入按以下格式从标准输入给出。

$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 \le l \le Q)$ 应包含 $j=l$ 时该问题的答案,以整数形式输出。

样例

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

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
0 0
0 1
0 2

0
0

可能存在坐标相同的多个点。

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

11
66
59
54
88

数据范围

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