背景

点击～

题目描述

MloVtry 是一个脑洞很大的人，它总会想出一些奇奇怪怪的 idea。

可问题是，MloVtry 作为一个蒟蒻，很多时候都没办法解决自己提出的问题，所以 MloVtry 想出一套题的梦想一直被搁置。

不过好在 MloVtry 有一些神犇朋友，他们强的没边，所以 MloVtry 一有机会就会向这些 dalao 们请教。

现在 MloVtry 有 $n$ 个 idea，这 $n$ 个 idea 在 MloVtry 二维的大脑里排成一列，每一个 idea 都有一个难度值，用 $a_i$ 表示，当然难度值越大越困难。

MloVtry 准备与 $q$ 个神犇进行交♂易，但是 MloVtry 不想问一些过于简单的 idea 来降自己的 B 格，又不好意思用太难的、无法解决的idea来伤害自己与神犇之间的感情，所以它每次都会挑idea序列中的第 $k$ 简单的 idea 来向神犇询问（也就是难度值第 $k$ 小的那个 idea）。

MloVtry 的脑子有坑，但是没关系，这个坑会反而会帮助 MloVtry 思考，不过这样数列的 $a_i$ 就会更新，具体的，设坑在第 $j$ 个 idea 上，那么有：

• $a_i\leftarrow a_i-zz(i\le j)$；
• $a_i\leftarrow a_i+i-j(i>j)$。

如果仅仅如此MloVtry也不会感到迷茫，但关键的是这个坑还会不定时的跳跃，这就让MloVtry手足无措了——它不知道这个时候要问哪个问题了。

现在 MloVtry 会给出你——它最好的朋友一些询问——一些二元组 $(at,k)$，表示脑洞位于 $at$，且它想询问第 $k$ 简单的 idea，请你告诉 MloVtry 这个 idea 难度是多少。

输入格式

第一行三个整数 $n,q,zz$，含义见题面。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

随后 $q$ 行，每行两个整数表示 $at$ 与 $k$。

特别的，MloVtry 是一个三维生物，所以它无法想象有人可以在时间轴上翻滚，所以 $at$ 与 $k$ 与上一个询问的答案的绝对值的异或值并对 $n$ 取模后再 $+1$ 的值为本次的 $at$ 和 $k$。

（也就是设 $lastans$ 为上次询问答案，每一次 $at=(at\oplus |lastans|)\bmod n+1$，$k=(k\oplus |lastans|)\bmod n+1$，并将 $lastans$ 更新，初始 $lastans=0$）

输出格式

$q$ 行 $q$ 个整数，表示对每个询问的回答。

13 12 56
10100 12208 11766 11872 11336 10815 10710 11872 11536 11988 10100 10908 10815 
11 13
1 3
3 10
1 7
8 4
7 11
11 4
5 2
13 11
13 6
3 11
11 10

10044
11932
10918
11280
10044
10759
10827
11874
12152
10759
10044
10713

提示

各个值保证在 int 范围内。

对于 $100\%$ 的数据，$n,q<=6\times10^4$。

对于 $40\%$ 的数据，$n,q<=1000$。

提示：可能有重复，例如

1 1 1 1 1 0

此时第 $1$ 大、第 $2$ 大....第 $5$ 大的值都是 $1$，第 $6$ 大的值是 $0$。