{"raw_statement":[{"iden":"statement","content":"Tin 是一位著名的魔术师，他的一个经典魔术与洗牌有关。\n\nTin 会准备一套牌，总共 $n$ 张（保证 $n$ 为偶数），各编号为 $1\\sim n$，一开始的时候牌是乱的且倒扣在桌子上。紧接着他开始表演洗牌，在洗牌的任意时刻，观众都可以向 Tin 询问从底往上数第 $t$ 张牌是什么牌，很显然 Tin 一定会立即回答出正确答案。\n\n事实上，Tin 采用如下方式来完成这个魔术，首先他记下了一开始的 $n$ 张牌的顺序，接着采用如下技巧洗牌：\n\n1. 拿起自顶向下 $\\frac{n}{2}$ 张牌放在右手，自底向上 $\\frac{n}{2}$ 张牌放在左手，牌的正面对着桌子。\n1. 借助他的记忆，将左右手最底下的牌进行比较，将编号较小的那张牌放下，重复这个操作直到左右手一边为空。\n1. 将还有牌的那只手上的所有牌放下。\n\n请你写一个程序模拟 Tin 的魔术。"},{"iden":"input","content":"第一行两个整数 $N,Q$。\n\n接下来一行 $N$ 个整数 $p_i$，从底向上描述了整个牌堆。\n\n接下来 $Q$ 行，一行一个询问 $t,i$，表示询问 $t$ 次洗牌后自底向上第 $i$ 张牌编号是多少。"},{"iden":"output","content":"对于每一个询问，输出你的答案。"},{"iden":"note","content":"### 样例 3 解释\n\n| 洗牌次数 |          自底向上的牌堆           |\n| :------: | :-----------------------------: |\n|   $0$    | $7\\ 5\\ 2\\ 9\\ 10\\ 8\\ 4\\ 3\\ 6\\ 1$ |\n|   $1$    | $7\\ 5\\ 2\\ 8\\ 4\\ 3\\ 6\\ 1\\ 9\\ 10$ |\n|   $2$    | $3\\ 6\\ 1\\ 7\\ 5\\ 2\\ 8\\ 4\\ 9\\ 10$ |\n|   $3$    | $2\\ 3\\ 6\\ 1\\ 7\\ 5\\ 8\\ 4\\ 9\\ 10$ |\n\n### 数据规模与约定\n\n对于全部数据，满足 $1\\le N\\le 2\\times 10^5$，$N$ 为偶数，$1\\le Q\\le 10^6$，$0\\le t\\le 10^9$，$p$ 为 $1\\sim n$ 的排列，$1\\le i\\le N$。\n\n| Subtask 编号 |       特殊限制        |   分数   |\n| :----------: | :------------------: | :------: |\n|   $1$\t    |   $N\\le 10^3$\t    |   $10$   |\n|   $2$\t    | 每一个询问的 $t$ 相同 | \t$40$ |\n|   $3$\t    |   $N,Q\\le 10^5$\t   |   $25$   |\n|   $4$\t    |      无特殊限制\t      |   $25$   |"}],"translated_statement":null,"sample_group":[["6 3\n1 5 6 2 3 4\n1 2\n0 4\n1 5","2\n2\n5"],["6 6\n2 1 5 4 6 3\n0 1\n1 1\n0 3\n1 3\n0 6\n10 6","2\n2\n5\n4\n3\n3"],["10 10\n7 5 2 9 10 8 4 3 6 1\n3 1\n3 2\n3 3\n3 4\n3 5\n3 6\n3 7\n3 8\n3 9\n3 10","2\n3\n6\n1\n7\n5\n8\n4\n9\n10"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}