Universal Cup Judging System

Universal Cup

実行時間制限: 3.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

C'è un parco con $N$ piazze disposte in fila da sinistra a destra, numerate $0, 1, \dots, N - 1$ in quest'ordine.

All'interno del parco ci sono $N$ persone, anch'esse numerate $0, 1, \dots, N - 1$. Quando annunci una sequenza $X = (X_1, X_2, \dots, X_{|X|})$ di interi non negativi compresi tra $0$ e $N - 1$, le persone eseguono una marcia secondo le seguenti regole:

  1. Per ogni $i = 0, 1, \dots, N - 1$, la persona $i$ si sposta nella piazza $i$.
  2. Per ogni $j = 1, 2, \dots, |X|$, in quest'ordine, esegui quanto segue:
    • Ogni persona che non si trova attualmente nella piazza $X_j$ si sposta di esattamente una piazza verso $X_j$.

Ti viene data una sequenza $A = (A_0, A_1, \dots, A_{M-1})$ di lunghezza $M$, composta da interi compresi tra $0$ e $N - 1$.

Devi rispondere a $Q$ query online. Per ogni $i = 1, 2, \dots, Q$, vengono dati gli interi $t'_i, L'_i, R'_i, P'_i$. Per prima cosa, ricostruisci $t_i, L_i, R_i, P_i$ utilizzando la seguente procedura:

Sia $\text{ans}_0 = 0$, e sia $\text{ans}_i$ la risposta alla $i$-esima query. Ricostruisci $t_i, L_i, R_i, P_i$ come segue:

  • $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)$

Qui, per un intero non negativo $a$ e un intero positivo $b$, $(a \bmod b)$ indica il resto della divisione di $a$ per $b$, che è compreso nell'intervallo da $0$ a $b - 1$.

Per ciascuna quaterna ricostruita $(t_i, L_i, R_i, P_i)$, rispondi alla seguente query:

  • Se $t_i = 0$: Sia $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simula la marcia e stampa la piazza finale in cui termina la persona $P_i$.
  • Se $t_i = 1$: Sia $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simula la marcia e stampa quante persone terminano nella piazza $P_i$.

Input

L'input è fornito nel seguente formato:

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
  • Tutti i valori di input sono interi.
  • $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

Stampa $Q$ righe. Per ogni $i = 1, 2, \dots, Q$, stampa $\text{ans}_i$, la risposta alla $i$-esima query.

Esempi

Input di esempio 1

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

Output di esempio 1

2
0
3

Input di esempio 2

7 4 1
3 3 3 3
1 3 0 3

Output di esempio 2

7

Note

Nella prima query dell'esempio 1, per $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ con $X = (2, 3, 2)$, la persona $2$ si muove come $2 \to 2 \to 3 \to 2$, quindi la risposta è $2$.

Nella seconda query dell'esempio 1, per $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ con $X = (3, 2, 1)$, il numero di persone nella piazza $3$ alla fine è $0$.

Nella terza query dell'esempio 1, per $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ con $X = (1)$, il numero di persone nella piazza $1$ alla fine è $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.