Description

There are $N$ Bookworm food shops, and $M$ families come to enjoy delicious food made from bookworms.

Because the food shops are very popular, customers need to line up. At the beginning, all queues are empty.

Today, all food shops open again, and $Q$ events occur:

• Join event: In every food shop with an index in the interval $[L, R]$, family $C$ joins the back of the queue. For each food shop that meets the condition, $K$ people are added to the back of the queue.
• Leave event: In every food shop with an index in the interval $[L, R]$, if the queue has more than $K$ people, then the first $K$ people leave the queue; otherwise, everyone in the queue leaves.
• Freebie event: If the queue of food shop $A$ has at least $B$ people, then the food shop gives the $B$-th person counting from the front of the queue one special bookworm; otherwise, the staff member eats the bookworm.

For each Freebie event, determine whether a customer receives a special bookworm. If yes, output which family the customer belongs to.

Input Format

The first line contains three integers $N, M, Q$, representing the number of food shops, the number of families, and the number of events.

In the next $Q$ lines, each line starts with an integer $T$:

• If $T = 1$, then four integers $L, R, C, K$ follow, describing a Join event.
• If $T = 2$, then three integers $L, R, K$ follow, describing a Leave event.
• If $T = 3$, then two integers $A, B$ follow, describing a Freebie event.

Output Format

For every Freebie event, output one integer per line:

• If a customer is given a special bookworm, output the family the customer belongs to.
• If the staff member eats the bookworm, output $0$.

3 5 7
1 2 3 5 2
1 1 2 2 4
3 2 3
2 1 3 3
3 1 2
1 2 3 4 2
3 3 2

2
0
4

3 4 7
1 1 2 1 1
1 1 3 4 1
2 2 3 1
2 1 3 1
1 1 2 2 1
3 1 1
3 3 2

4
0

183326 218318 22
1 106761 160918 151683 574906362
3 68709 1
1 29240 156379 22166 957318472
1 14054 181502 82845 97183925
2 112033 122908 587808357
2 57819 160939 215041262
3 36674 524274467
1 35854 69866 32334 322730299
1 1384 7230 115069 454256926
1 44192 158235 8750 84192710
3 54457 1077490708
2 10592 110384 979714505
2 44594 79244 311724477
3 160965 97183926
1 88748 101697 39148 373927458
3 41166 58039001
1 91501 137591 205480 958877326
2 77775 169655 135756956
1 12497 57047 60918 15666764
1 47839 51716 144688 732270998
3 114514 774994894
3 48645 169986425

0
22166
32334
0
82845
8750
60918

Hint

Sample 1 Explanation

We use $Q_i(a_1, a_2, \cdots, a_k)$ to denote the queue of the $i$-th food shop, where $a_1$ is the front and $a_k$ is the back. Here, $a_i = p$ means that the person at position $i$ comes from family $p$. In particular, $Q_i()$ means that the queue is currently empty.

According to the events in Sample 1:

• The $1$-st Join event:

• The $2$-nd Join event:

• The $3$-rd Freebie event: the $3$-rd person in the $2$-nd food shop (from family $2$) is given a special bookworm.
• The $4$-th Leave event:

• The $5$-th Freebie event: the $1$-st food shop has fewer than $2$ people, so the staff member eats the bookworm.
• The $6$-th Join event:

• The $7$-th Freebie event: the $2$-nd person in the $3$-rd food shop (from family $4$) is given a special bookworm.

Constraints and Notes

This problem uses bundled subtasks.

• Subtask 1 (2 pts): $N, Q \le 2000$, satisfies Property A.
• Subtask 2 (5 pts): $N, Q \le 2000$.
• Subtask 3 (7 pts): $N, Q \le 65000$, satisfies Property B.
• Subtask 4 (21 pts): $M = 1$.
• Subtask 5 (15 pts): $N, Q \le 65000$, satisfies Property A.
• Subtask 6 (13 pts): $N, Q \le 65000$, satisfies Property C.
• Subtask 7 (26 pts): $N, Q \le 65000$.
• Subtask 8 (11 pts): no special restrictions.

For $100\%$ of the data:

• $1 \le N, M, Q \le 25 \times 10^4$.
• $T \in \{1, 2, 3\}$.
• For all Join events, $1 \le L \le R \le N$, $1 \le C \le M$, $1 \le K \le 10^9$.
• For all Leave events, $1 \le L \le R \le N$, $1 \le K \le 10^9$.
• For all Freebie events, $1 \le A \le N$, $1 \le B \le 10^{15}$.
• There is at least one Freebie event.

There are the following properties:

• Property A: For all Join events and Leave events, $K = 1$.
• Property B: For all Join events, $R - L \le 10$ and $K = 1$.
• Property C: There are only Join events and Freebie events.

Note

Translated from The 20th Japanese Olympiad in Informatics Spring Training Camp Day1 C フードコート (Food Court) English version.

Translated by ChatGPT 5