KNN算法
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

K最邻近（KNN，K-NearestNeighbor）分类算法是数据挖掘分类技术中最简单的方法之一
期末考试在即，紧张预习数据挖掘的 Capps 对如下问题十分感兴趣：

在一维空间中有点集 S 包含 n 个点，用什么算法能快速回答如下 q 次查询：

  • 第 i 次查询给出点 p_i 和整数 k_i，要求输出 S 中与点 p_i 距离第 k_i 近的点和 p_i的距离。

距离：若点 u_i 坐标为 x_i，v_i 坐标为 y_i，则定义点 u_i 与点 v_i 的距离为 |x_i-y_i| 。

输入描述:

第一行两个整数 n,q (1\le n, q \le 2 \times 10^5) 表示点集 S 的大小和查询次数。

第二行 n 个整数，第 i 个整数 a_i (-10^9 \le a_i \le 10^9) 描述点集 S 里第 i 个点的坐标。

保证对于 \forall i, j (1\le i \lt j \le n) 有 a_i \neq a_j 。

接下来 q 行， 第 i 行两个整数 x_i,k_i (-10^9 \le x_i \le 10^9, \ 1\le k_i \le n)，表示 p_i 的坐标和需要查询距离 p_i 第 k_i 近的结果。

输出描述:

输出 q 行，第 i 行一个整数，表示第 i 次查询的答案。
示例1

输入

复制 
5 3
10 -2 1 3 4
12 4
3 1
2 2

输出

复制 
11
0
1