题目描述

在一个数轴上给你 $n$ 个点，每个点的坐标分别是 $a_1,a_2,\cdots,a_n$。

现在有 $q$ 组询问，每次询问给你一个点 $x$，你要找到距离点 $x$ 第 $k$ 近的点的距离是多少。

例如有 $4$ 个点，它们的坐标分别是 -3 -1 5 6。

• 距离点 $-2$ 第 $1$ 近的点是 -1，它们之间的距离是 $1$。
• 距离点 $-2$ 第 $2$ 近的点是 -3，它们之间的距离是 $1$。注意这里 $-1,-3$ 这两个点距离 $-2$ 的距离都相同。
• 距离点 $-2$ 第 $3$ 近的点是 5，它们之间的距离是 $7$。

输入格式

第一行输入两个整数 $n,q$

第二行输入 $n$ 个空格隔开的整数 $a_1,a_2,\cdots,a_n$

接下来 $q$ 行，每行两个整数 $x,k$

输出格式

一共输出 $q$ 行，每行输入一个整数代表第 $k$ 近的点和 $x$ 的距离。

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

7
3
13

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

数据范围

• 对于 $30\%$ 的数据，$1\leq n,q\leq 10^3$，$-10^8\leq a_i\leq 10^8$，$-10^8\leq x\leq 10^8$，$1\leq k\leq n$。
• 对于 $100\%$ 的数据，$1\leq n,q\leq 10^5$，$-10^8\leq a_i\leq 10^8$，$-10^8\leq x\leq 10^8$，$1\leq k\leq n$。