题目描述

大笨龙最近又在捣鼓自己的“神奇洗牌术”了。

他准备了一叠牌，一共有 $n$ 张（保证 $n$ 为偶数），每张牌上分别写着 $1 tilde n$ 中的一个编号。起初，这叠牌是乱序的，倒扣在桌上。

聪明兔对大笨龙的本事半信半疑，于是决定随时提问：在洗牌过程中的任意时刻，她都可以问大笨龙“现在从底往上数第 $i$ 张牌是什么”。而大笨龙总能立刻回答正确。

其实，大笨龙的做法并不是真的会魔法，而是他先记住了最开始整叠牌的顺序，然后严格按照下面的方法反复“洗牌”：

1. 把整叠牌分成两半：

   • 上半部分（自顶向下的 $n/2$ 张）拿到右手；
   • 下半部分（自底向上的 $n/2$ 张）拿到左手。

   两只手中的牌都保持正面对着桌子。

2. 接下来开始放牌：

   • 比较左右手最底下两张牌的编号；
   • 把编号较小的那张放到桌上；
   • 重复这个过程，直到某一只手里的牌被放空。

3. 最后，把另一只手中剩下的所有牌按顺序全部放到桌上。

聪明兔会提出很多问题，每次给出两个数 $t,i$，表示想知道：经过 $t$ 次洗牌后，从底往上数第 $i$ 张牌的编号是多少。

请你帮助大笨龙回答聪明兔的所有问题。

输入格式

第一行两个整数 $n,q$。

第二行 $n$ 个整数 $p_i$，表示初始牌堆中从底向上第 $i$ 张牌的编号。

接下来 $q$ 行，每行两个整数 $t,i$，表示询问经过 $t$ 次洗牌后，从底向上第 $i$ 张牌的编号是多少

输出格式

对于每个询问，输出一行一个整数，表示答案。

样例1输入

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

样例1输出

2
2
5

样例2输入

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

样例2输出

2
3
6
1
7
5
8
4
9
10

样例2解释

第0次洗牌：7，5，2，9，10，8，4，3，6，1；

第1次洗牌：7，5，2，8，4，3，6，1，9，10；

第2次洗牌：3，6，1，7，5，2，8，4，9，10；

第3次洗牌：2，3，6，1，7，5，8，4，9，10。

数据范围

对于所有测试数据，保证： $1<= n<= 2 times 10^5$，$n$ 为偶数，$1<= Q<= 10^6$，$0<= t<= 10^9$，$p$ 为 $1 tilde n$ 的排列，$1<= i<= n$。