Problem Description

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

Due to the popularity of the food stalls, customers need to queue up, and initially, all queues are empty.

Today, all food stalls are open, and $Q$ events occur:

• Join Event: In all food stalls numbered within the interval $[L, R]$, the family numbered $C$ joins the end of the queue, adding $K$ people to the end of each queue that meets the criteria.
• Leave Event: In all food stalls numbered within the interval $[L, R]$, if the queue has more than $K$ people, the first $K$ people leave the queue; otherwise, everyone in the queue leaves.
• Freebie Event: If the queue at the food stall numbered $A$ has at least $B$ people, the food stall will give a special bookworm to the $B$-th person from the start of the queue; otherwise, the staff will eat the bookworm.

Determine for each Freebie Event whether a customer was given a special bookworm, and if so, identify the family the customer belongs to.

Input Format

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

The next $Q$ lines, each starting with an integer $T$:

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

Output Format

For each Freebie Event, output one integer:

• If a customer was given a special bookworm, output the family they belong to.
• If the staff ate the bookworm, output $0$.

Sample Input and Output

Input Sample #1

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

Output Sample #1

2
0
4

Input Sample #2

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

Output Sample #2

4
0

Input Sample #3

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

Output Sample #3

0
22166
32334
0
82845
8750
60918

Notes/Hints

Sample 1 Explanation

We use $Q_i(a_1, a_2, \cdots, a_k)$ to represent the queue at the $i$-th food stall, with $a_1$ being the front and $a_k$ being the end of the queue, where $a_i = p$ means the $i$-th position is occupied by someone from the $p$-th family. Specifically, $Q_i()$ represents an empty queue.

Based on the events in Sample 1:

• The first Join Event:

$$Q_1(), Q_2(5, 5), Q_3(5, 5)$$

• The second Join Event:

$$Q_1(2, 2, 2, 2), Q_2(5, 5, 2, 2, 2, 2), Q_3(5, 5)$$

• The third Freebie Event, the third person in the second food stall (from the second family) is given a special bookworm.
• The fourth Leave Event:

$$Q_1(2), Q_2(2, 2, 2), Q_3()$$

• The fifth Freebie Event, the first food stall does not have enough people, so the staff eats the bookworm.
• The sixth Join Event:

$$Q_1(2), Q_2(2, 2, 2, 4, 4), Q_3(4, 4)$$

• The seventh Freebie Event, the second person in the third food stall (from the fourth family) is given a special bookworm.

Data Constraints and Specifications

This problem is bundled with 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.

The following properties exist:

• 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: Only Join Events and Freebie Events occur.

见题面 Input 部分

见题面 Output 部分