题目背景

期末考试快要到了，机器学习老师明确说了期末答题要考 KNN（K-Nearest Neighbors） 算法。还好 『 Aswert 』 最近正在学习这个算法，这是一种常用的机器学习算法，用于分类和回归任务。该算法的核心思想是“物以类聚”，即通过查找最近的 $K$ 个邻居来预测新样本的类别或值。为了深入理解 KNN 的工作原理，『 Aswert 』 决定从一维数据入手，研究如何高效地解决大规模查询问题。

题目描述

给定一个包含 $n$ 个不同点的一维点集 $S$，你需要帮助『 Aswert 』快速回答 $q$ 次查询。每次查询给出一个点 $p_i$ 和一个整数 $k_i$，要求输出点集 $S$ 中与 $p_i$ 距离第 $k_i$ 近的点到 $p_i$ 的距离。

注意：

• 距离定义为两点坐标之差的绝对值
• 输入保证所有点的坐标互不相同，且每个查询的答案唯一存在

输入格式

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

第二行， $n$ 个整数 $x_i$ $(-2,147,483,647 \leq x_i \leq 2,147,483,647)$，表示点集 $S$ 中每个点的坐标

输入保证所有 $x_i$ 互不相同。

接下来 $q$ 行，每行两个整数 $p_i$ 和 $k_i$ $(-2,147,483,647 \leq p_i \leq 2,147,483,647, 1 \leq k_i \leq n)$，表示查询点的坐标和要求的第 $k_i$ 近的距离。输入保证答案存在

输出格式

一共 $q$ 行，每行一个整数，表示对应查询的结果

样例输入输出

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

11
0
1

样例解释

对于第一个查询 $p=12$，$k=4$，点集 $S$ 按与 $12$ 的距离排序后的顺序是：$10$（距离 $2$），$4$（距离 $8$），$3$（距离 $9$），$1$（距离 $11$），$-2$（距离 $14$）。第 $4$ 近的是坐标 $1$ 的点，距离为 $11$，因此输出 $11$