Tin Golubić，也被称为“魔术先生”（Mr. Magic Man），是瓦拉日丁（Varaždin）最有天赋的年轻魔术师之一。他的专长是纸牌魔术，本题旨在向我们多年来见证过的一些真正令人印象深刻的魔术表演致敬。

本题中 Tin 的戏法涉及一副 $N$ 张牌的牌组，每张牌上都写有一个从 $1$ 到 $N$ 的唯一整数，且牌的总数是偶数。Tin 将表演一系列看似是“洗牌”（riffle shuffles）的动作，观众随时可能会大声提问：“在你执行了 $t$ 次洗牌后，从底部数第 $i$ 张牌上的数字是多少？”当然，Tin 会立即给出正确的答案。

这个戏法背后的秘密在于 Tin 不可思议的心理能力和洗牌技巧的结合。首先，他会完美地记住牌组的初始状态，这意味着他清楚地知道初始时哪张牌在哪个位置。

然后，他会使用一种观众难以察觉的、经过微调的标准洗牌法。与典型的洗牌类似，Tin 会将牌组的下半部分拿在左手中，上半部分拿在右手中，并始终保持牌面朝下，然后逐张放下它们以在桌面上形成新的牌组。与随意从一只手中放下底牌不同，他总是会放下两只手中底牌数字较小的那一张。此外，一旦他放完了其中一只手上的所有牌，他也会放下另一只手中剩余的所有牌。放下后的牌被收集起来，洗牌即告完成。

从初始牌组开始，Tin 会在当前的牌组上重复执行他的洗牌动作，从而获得一个新的牌序，并在此基础上执行下一次洗牌。

你的任务是编写一个程序来模拟 Tin 的戏法，即给定牌组的初始状态，你需要回答观众提出的 $Q$ 个询问。

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $Q$。保证 $N$ 是偶数。

第二行包含 $N$ 个空格分隔的正整数，是集合 $\{1, 2, \dots, N\}$ 的一个排列，表示从底部到顶部牌组的初始状态。

接下来的 $Q$ 行中，第 $j$ 行包含两个空格分隔的整数 $t$ 和 $i$ ($1 \le i \le N$)，描述观众的第 $j$ 个询问。更准确地说，该询问是关于完成 $t$ 次洗牌后，从牌组底部数第 $i$ 张牌上的数字。

输出格式

输出 $Q$ 行，第 $j$ 行包含一个 $1$ 到 $N$ 之间的正整数，即第 $j$ 个询问的答案。

数据范围

在所有子任务中，满足 $2 \le N \le 200\,000$，$1 \le Q \le 1\,000\,000$ 且 $0 \le t \le 10^9$。

样例

样例输入 1

6 3
1 5 6 2 3 4
1 2
0 4
1 5

样例输出 1

2
2
5

样例输入 2

6 6
2 1 5 4 6 3
0 1
1 1
0 3
1 3
0 6
10 6

样例输出 2

2
2
5
4
3
3

样例输入 3

10 10
7 5 2 9 10 8 4 3 6 1
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10

样例输出 3

2
3
6
1
7
5
8
4
9
10

说明

第三个样例的说明： 下表显示了每次洗牌后牌组的状态。所有询问的 $t=3$，因此输出即为洗牌 3 次后的牌组状态。