AT_1_stpc2025_1_m.Many Approaches

有一个公园，里面有 $N$ 个广场排成一排，每个广场从左到右依次编号为 $0,1,\dots, N-1$。

公园里有 $N$ 个人，每个人的编号为 $0,1,\dots, N-1$。当你声明一个由 $0$ 到 $N-1$ 的非负整数构成的序列 $X=(X_1,X_2,\dots, X_{|X|})$ 时，这些人会按照如下方式进行行进：

1. 对于每个 $i = 0,1,\dots, N-1$，第 $i$ 号人会移动到编号为 $i$ 的广场。
2. 对于每个 $j = 1, 2, \dots, |X|$，依次执行以下操作：
   • 所有不在广场 $X_j$ 的人，会沿着广场向 $X_j$ 的方向移动一个广场的距离。

给定一个长度为 $M$，每个元素都是 $0$ 到 $N-1$ 之间的非负整数的序列 $A=(A_0,A_1,\dots, A_{M-1})$。

请在线回答 $Q$ 个查询。对于第 $i$ 个查询（$i=1,2,\dots, Q$），给出整数 $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-1$。

对于恢复得到的 $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$ 的广场上的人数。

输入格式如下：

$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$ 行输出第 $i$ 条查询的答案 $\mathrm{ans}_i$。

样例解释 1

对于第 $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$ 号到 $3$ 号依次为 $0,4,0,0$。因此答案为 $0$。

对于第 $3$ 条查询，有 $(t_i,L_i,R_i,P_i)=(1,4,4,1)$。声明 $X=(A_4)=(1)$ 并按照行进规则执行，最终每个广场上的人数从 $0$ 号到 $3$ 号依次为 $0,3,1,0$。因此答案为 $3$。

数据范围

• 所有输入均为整数
• $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)$

由 ChatGPT 5 翻译