Universal Cup Judging System

Universal Cup

حد الوقت: 3.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

There is a park with $N$ squares arranged in a row from left to right, numbered $0, 1, \dots, N - 1$ in this order.

Inside the park, there are $N$ people, also numbered $0, 1, \dots, N - 1$. When you announce a sequence $X = (X_1, X_2, \dots, X_{|X|})$ of non-negative integers between $0$ and $N - 1$, the people perform a march according to the following rules:

  1. For each $i = 0, 1, \dots, N - 1$, person $i$ moves to square $i$.
  2. For each $j = 1, 2, \dots, |X|$, in this order, do the following:
    • Every person not currently on square $X_j$ moves exactly one square toward $X_j$.

You are given a sequence $A = (A_0, A_1, \dots, A_{M-1})$ of length $M$, consisting of integers between $0$ and $N - 1$.

You must answer $Q$ online queries. For each $i = 1, 2, \dots, Q$, integers $t'_i, L'_i, R'_i, P'_i$ are given. First, reconstruct $t_i, L_i, R_i, P_i$ using the following procedure:

Let $\text{ans}_0 = 0$, and let $\text{ans}_i$ denote the answer to the $i$-th query. Reconstruct $t_i, L_i, R_i, P_i$ as follows:

  • $t_i = ((t'_i + \text{ans}_{i-1}) \bmod 2)$
  • $a = ((L'_i + \text{ans}_{i-1}) \bmod M)$
  • $b = ((R'_i + \text{ans}_{i-1}) \bmod M)$
  • $L_i = \min(a, b)$
  • $R_i = \max(a, b)$
  • $P_i = ((P'_i + \text{ans}_{i-1}) \bmod N)$

Here, for a non-negative integer $a$ and a positive integer $b$, $(a \bmod b)$ denotes the remainder when $a$ is divided by $b$, which is in the range $0$ through $b - 1$.

For each reconstructed $(t_i, L_i, R_i, P_i)$, answer the following query:

  • If $t_i = 0$: Let $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simulate the march and output the final square where person $P_i$ ends up.
  • If $t_i = 1$: Let $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simulate the march and output how many people end up on square $P_i$.

Input

The input is given in the following format:

N M Q
A_0 A_1 ... A_{M-1}
t'_1 L'_1 R'_1 P'_1
t'_2 L'_2 R'_2 P'_2
:
t'_Q L'_Q R'_Q P'_Q
  • All input values are integers.
  • $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$)

Output

Output $Q$ lines. For each $i = 1, 2, \dots, Q$, output $\text{ans}_i$, the answer to the $i$-th query.

Examples

Sample Input 1

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

Sample Output 1

2
0
3

Sample Input 2

7 4 1
3 3 3 3
1 3 0 3

Sample Output 2

7

Note

In the first query of Sample 1, for $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ with $X = (2, 3, 2)$, person $2$ moves as $2 \to 2 \to 3 \to 2$, so the answer is $2$.

In the second query of Sample 1, for $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ with $X = (3, 2, 1)$, the number of people on square $3$ at the end is $0$.

In the third query of Sample 1, for $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ with $X = (1)$, the number of people on square $1$ at the end is $3$.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.