#P17936. Many Approaches

Many Approaches

Many Approaches

有 NN 个广场从左到右编号为 0,1,…,N−10,1,\ldots,N-1,以及同样编号的 NN 个人。

给定一个元素均在 [0,N−1][0,N-1] 内的整数序列 XX,一次行进定义如下:

  1. 先让每个人 ii 回到广场 ii。
  2. 按顺序处理 XX 中的每个元素 xx:所有不在广场 xx 的人同时向 xx 的方向移动一个广场;已经在 xx 的人不动。

给定长度为 MM 的序列 A=(A0,…,AM−1)A=(A_0,\ldots,A_{M-1})。你需要在线回答 QQ 个询问。每个询问输入四个加密整数 ti′,Li′,Ri′,Pi′t'_i,L'_i,R'_i,P'_i。

令 ans0=0\mathrm{ans}_0=0,ansi−1\mathrm{ans}_{i-1} 为上一个询问的答案。先解码:

ti=(ti′+ansi−1) mod 2,t_i=(t'_i+\mathrm{ans}_{i-1})\bmod2, $$a=(L'_i+\mathrm{ans}_{i-1})\bmod M,\quad b=(R'_i+\mathrm{ans}_{i-1})\bmod M,$$$$L_i=\min(a,b),\quad R_i=\max(a,b),\quad P_i=(P'_i+\mathrm{ans}_{i-1})\bmod N.$$

然后以 X=(ALi,ALi+1,…,ARi)X=(A_{L_i},A_{L_i+1},\ldots,A_{R_i}) 进行一次独立的行进:

  • 若 ti=0t_i=0,回答人 PiP_i 最终所在的广场编号;
  • 若 ti=1t_i=1,回答最终位于广场 PiP_i 的人数。

每次询问都从人 ii 位于广场 ii 的初始状态开始,前一次行进不会改变下一次行进的初始状态。

输入格式

N M Q
A_0 A_1 ... A_{M-1}
t'_1 L'_1 R'_1 P'_1
...
t'_Q L'_Q R'_Q P'_Q

输出格式

输出 QQ 行,按顺序回答询问。

数据范围

1≤N,M,Q≤2×1051\le N,M,Q\le2\times10^5,0≤Ai<N0\le A_i<N。

0≤ti′≤10\le t'_i\le1,0≤Li′,Ri′<M0\le L'_i,R'_i<M,0≤Pi′<N0\le P'_i<N。所有输入均为整数。

样例 1

输入:

4 5 3
0 2 3 2 1
0 1 3 2
1 0 2 1
1 4 4 1

输出:

2
0
3

样例 2

输入:

7 4 1
3 3 3 3
1 3 0 3

输出:

7