MloVtry的idea

题目背景

点击~

题目描述

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]=a[i]-zz(i<=j);a[i]=i+a[i]-j(i>j)。 如果仅仅如此MloVtry也不会感到迷茫,但关键的是这个坑还会不定时的跳跃,这就让MloVtry手足无措了---它不知道这个时候要问哪个问题了。 现在MloVtry会给出你---它最好的朋友一些询问---一些二元组(at,k),表示脑洞位于at,且它想询问第k简单的idea,请你告诉MloVtry这个idea难度是多少。

输入输出格式

输入格式


第一行三个整数n,q,zz,含义见题面 第二行n个整数a[1],a[2].....a[n] 随后q行,每行两个整数表示at与k 特别的,MloVtry是一个三维生物,所以它无法想象有人可以在时间轴上翻滚,所以at与k与上一个询问的答案的绝对值的异或值并对n取膜后再+1的值为本次的at和k。 (也就是设lastans为上次询问答案,每一次at=(at^abs(lastans))%n+1,k=(k^abs(lastans))%n+1,并将lastans更新,初始lastans=0)

输出格式


q行q个整数,表示对每个询问的回答

输入输出样例

输入样例 #1

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

输出样例 #1

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

说明

各个值保证在int范围内。 对于100%的数据,n,q<=6w。 对于40%的数据,n,q<=1000。 PS.可能有重复,例如 1 1 1 1 1 0 此时第1大、第2大....第5大的值都是1,第6大的值是0