X 教授最近向世界展示了他的最新发明：终极珠子交换机（Ultimate Bead Swapper，简称 UBS）。顾名思义，它可以通过交换珠子序列中的某些珠子，使序列变得更加有趣！

UBS 拥有 $N$ 条平行放置的南北向传送带。传送带从左到右编号为 $1$ 到 $N$。每条传送带都以相同的速度由北向南移动。在相邻的传送带之间放置了 $M$ 个交换机。没有两个交换机距离 UBS 北端的距离相等。（换句话说，它们可以根据距离北端的远近进行完全排序。）交换机从北到南编号为 $1$ 到 $M$。图 1 展示了从上方俯视时的 UBS。

图 1：拥有 5 条传送带和 5 个交换机的终极珠子交换机。

使用 UBS 时，$N$ 颗珠子同时放置在传送带的北端，这样它们在沿传送带移动时形成水平的一行。当两颗珠子到达一个交换机下方时，右侧传送带上的珠子被移动到左侧传送带，左侧传送带上的珠子被移动到右侧传送带。交换后，这两颗珠子不会破坏水平排列的顺序。图 2 展示了交换机的工作方式。

任务

编写一个程序，给定传送带数量 $N$、交换机数量 $M$ 以及每个交换机的位置，回答以下形式的问题：

给定 $K$ 和 $J$，对于放置在 UBS 北端第 $K$ 条传送带上的珠子，在所有珠子刚刚经过第 $J$ 号交换机后，该珠子位于哪条传送带上？

图 2：(a) 四颗珠子沿传送带移动。(b) 珠子 2 和 3 在经过交换机后交换了位置。

输入格式

你的程序应从标准输入读取数据。第一行包含传送带数量 $N(1 \le N \le 300,000)$ 和交换机数量 $M(1 \le M \le 300,000)$。

接下来的 $M$ 行按从北到南的顺序列出交换机。每行包含一个整数 $P(1 \le P \le M - 1)$，表示在传送带 $P$ 和 $P + 1$ 上方有一个交换机。

交互

读取上述输入后，你的程序应调用表 1 中指定的库函数。函数必须按以下顺序调用：

1. 调用函数 getNumQuestions 以获取 $Q(1 \le Q \le 300,000)$，即将被询问的问题数量。
2. 执行 $Q$ 次以下操作： (a) 调用函数 getQuestion 以接收一个问题。 (b) 调用函数 answer 以回答刚刚收到的问题。

我们强调 getNumQuestions 必须首先调用且仅调用一次。getQuestion 和 answer 必须交替调用：在调用一次 getQuestion 后，你的程序在调用 answer 之前不得再次调用 getQuestion，反之亦然。如果你的程序在运行测试场景时违反此约定，该测试场景将获得 0 分。

实现细节

如果你提交 Pascal 源代码，代码必须包含： uses beadslib;

如果你提交 C 或 C++ 源代码，代码必须包含： #include "beadslib.h"

表 1：交互库。

样例

样例输入 1

5 5
2
4
1
3
3

样例输出 1

(无)

说明

样例输入对应图 1。questions.txt 的内容如下：

2
3 4
5 5

样例交互

子任务

如果你的程序遵循上述函数调用约定并正确回答了所有问题，则每个输入场景的得分为 100%，否则为 0%。

在分值为 20 分的测试场景中，$M$ 和 $Q$ 最多为 $10,000$。