给定长度为 $N$ 的序列 $A_1, A_2, \ldots, A_N$ 和整数 $M$。处理 $Q$ 个查询。每个查询由两个整数 $d$ 和 $k$ 组成，按顺序执行以下操作：

• 构造新序列 $B_i = (A_i + d) \bmod M$（$1 \le i \le N$）。
• 对于所有 $i$（$1 \le i \le N$），将第 $i$ 个后缀定义为 $B_i, B_{i+1}, \ldots, B_N$。
• 输出按字典序第 $K$ 小的序列 $B$ 的后缀编号。

输入格式

第一行包含序列长度 $N$ 和整数 $M$。

第二行包含 $A_1, A_2, \ldots, A_N$。

第三行包含查询个数 $Q$。

接下来 $Q$ 行，每行包含一个查询 $d$ 和 $k$。

输出格式

对于每个查询，输出按字典序第 $K$ 小的序列 $B$ 的后缀编号，每个查询输出一行。

说明

第一个查询中，序列 $B = [5, 2, 0, 5, 5]$。将所有后缀按字典序排序后得到 $[0, 5, 5]$, $[2, 0, 5, 5]$, $[5]$, $[5, 2, 0, 5, 5]$, $[5, 5]$。字典序第 $4$ 小的后缀编号为 $1$。

样例

输入 1

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

输出 1

1
1
5