Universal Cup Judging System

Universal Cup

Süre Sınırı: 3.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Есть парк с $N$ площадями, расположенными в ряд слева направо и пронумерованными в этом порядке числами $0, 1, \dots, N - 1$.

В парке находятся $N$ человек, также пронумерованных числами $0, 1, \dots, N - 1$. Когда вы объявляете последовательность $X = (X_1, X_2, \dots, X_{|X|})$ из неотрицательных целых чисел от $0$ до $N - 1$, люди совершают шествие по следующим правилам:

  1. Для каждого $i = 0, 1, \dots, N - 1$ человек $i$ переходит на площадь $i$.
  2. Для каждого $j = 1, 2, \dots, |X|$ в этом порядке выполняется следующее:
    • Каждый человек, не находящийся в данный момент на площади $X_j$, перемещается ровно на одну площадь в сторону площади $X_j$.

Вам дана последовательность $A = (A_0, A_1, \dots, A_{M-1})$ длины $M$, состоящая из целых чисел от $0$ до $N - 1$.

Вам нужно ответить на $Q$ онлайн-запросов. Для каждого $i = 1, 2, \dots, Q$ даны целые числа $t'_i, L'_i, R'_i, P'_i$. Сначала восстановите $t_i, L_i, R_i, P_i$ с помощью следующей процедуры:

Пусть $\text{ans}_0 = 0$, а $\text{ans}_i$ обозначает ответ на $i$-й запрос. Восстановите $t_i, L_i, R_i, P_i$ следующим образом:

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

Здесь для неотрицательного целого числа $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 ... 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
  • Все входные значения являются целыми числами.
  • $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$)

Выходные данные

Выведите $Q$ строк. Для каждого $i = 1, 2, \dots, Q$ выведите $\text{ans}_i$ — ответ на $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

Пример ввода 2

7 4 1
3 3 3 3
1 3 0 3

Пример вывода 2

7

Примечание

В первом запросе первого примера для $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ и $X = (2, 3, 2)$ человек $2$ перемещается как $2 \to 2 \to 3 \to 2$, поэтому ответ равен $2$.

Во втором запросе первого примера для $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ и $X = (3, 2, 1)$ количество людей на площади $3$ в конце равно $0$.

В третьем запросе первого примера для $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ и $X = (1)$ количество людей на площади $1$ в конце равно $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.