配点 : 100 点
問題文
N 有一个由若干广场左右排列的公园,广场从左到右顺序为 0,1,\dots, N-1 编号已附上。
公园中,0, 1, \dots, N-1 它是一个具有 N 有很多人。你 0 以上 N-1 声明以下的非负整数序列时, X=(X_1,X_2,\dots, X_{|X|}) 这些人有如下的 行進 。 对于
- 各 i = 0,1,\dots, N-1 关于人 求 i 是正方形 i 。
- 各 j = 1, 2, \dots, |X| ,按此顺序执行以下操作: 方格内除
- 広場 X_j 以外的所有人都可以从自己的方格移动到本方格。 X_j 走向广场 移动 1 。 在线回答
0 以上 N-1 由小于或等于的非负整数组成的长度 在 M 栏 A=(A_0,A_1,\dots, A_{M-1}) 。 对于
Q 疑问。 给出 i=1,2,\dots, Q , 当我输入 i 个查询是一个整数 查找 t_i',L_i',R_i',P_i' 。首先,请按照以下步骤操作 请恢复 t_i,L_i,R_i,P_i 。
- \mathrm{ans}_0=0 、\mathrm{ans}_i= ( i 答案)。
- 本例如下
恢复 t_i,L_i,R_i,P_i 。
- t_i=((t_i' + \mathrm{ans}_{i-1})\bmod 2)
- a=((L_i' + \mathrm{ans}_{i-1})\bmod M)
- b=((R_i' + \mathrm{ans}_{i-1})\bmod M)
- L_i=\min(a,b)
- R_i=\max(a,b)
- P_i=((P_i' + \mathrm{ans}_{i-1})\bmod N)
其中非负整数 表示除以 a 和一个正整数 从范围 b 反对 (a\bmod b) 是 您也可以写 a 该值应乘以 b 所得的余数。这个值是 小于 0 以上 b 。
这样获取 请回答以下 t_i,L_i,R_i,P_i 的查询。 当人们游行并宣布
- t_i=0 : X = (A_{L_i},A_{L_i+1}\dots, A_{R_i}) 请回答 P_i 所在方格的编号。
- t_i=1 : X = (A_{L_i},A_{L_i+1}\dots, A_{R_i}) 行军并宣布时 请告诉我们 P_i 中有多少人。 第
制約
- 所有输入均为整数
- 1\le N,M,Q\le 2\times 10^5
- 0\le A_i\le N-1\ (0\le i\le M-1)
- 0\le t_i',t_i\le 1\ (1\le i\le Q)
- 0\le L_i',R_i'\le M-1\ (1\le i\le Q)
- 0\le L_i\le R_i\le M-1\ (1\le i\le Q)
- 0\le P_i',P_i\le N-1\ (1\le i\le Q)
入力
输入按以下格式给出。
N M Q
A_0 A_1 \dots A_{M-1}
t_1' L_1' R_1' P_1'
t_2' L_2' R_2' P_2'
\vdots
t_Q' L_Q' R_Q' P_Q'
出力
Q 行。i=1,2,\dots, Q 关于 i 在线 i 个查询的答案 当我们游行并宣布 \mathrm{ans}_i 。
入力例 1
4 5 3 0 2 3 2 1 0 1 3 2 1 0 2 1 1 4 4 1
出力例 1
2 0 3
1 个查询中 给出了 (t_i,L_i,R_i,P_i)=(0,1,3,2) 。 X = (A_1,A_2,A_3)=(2,3,2) 时,人们 2 是正方形 导航至 2\to 2\to 3\to 2 。因此答案是 当你宣布 2 。
2 个查询中 给出了 (t_i,L_i,R_i,P_i)=(1,2,4,3) 。 X = (A_2,A_3,A_4)=(3,2,1) 并游行时,每个方格的人数将为 0 开始 0,4,0,0 。因此答案是 0 。
3 个查询中 给出了 (t_i,L_i,R_i,P_i)=(1,4,4,1) 。 X = (A_4)=(1) 并游行时,每个方格的人数将为 0 开始 0,3,1,0 。因此答案是 3 。
入力例 2
7 4 1 3 3 3 3 1 3 0 3
出力例 2
7