21786번 - Food Court 서브태스크다국어

IOI Center is a training center equipped with living facilities. There is a food court for large groups. In the food court, there are N shops in a row, numbered from 1 to N. In front of each shop, there is a queue for customers. Customers will make a line in each queue.

Today, there are M groups staying in IOI Center, numbered from 1 to M. Members of groups will make lines in a rather strange way to enjoy chatting.

In this food court, shops sometimes give free desserts to customers in their queue. JOI-kun, working in this food court, has a job to record the groups the customers who receive free desserts belong to.

No customers were making lines in the queues when the shops were closed. Today, when the shops were open, Q events happened in the queues. The i-th event is one of the following.

• Join For every shop whose number is between L_i and R_i, inclusive, K_i customers from the group C_i joined the queue at its end.
• Leave For every shop whose number is between L_i and R_i, inclusive, if there were K_i or more customers in the queue, K_i customers from the beginning of the queue left. Otherwise, all the customers in the queue left.
• Service If there were B_i or more customers in the queue of the shop A_i, the shop gave a free dessert to the B_i-th customer from the beginning of the queue. Otherwise, the staff of the shop ate the free dessert.

Unfortunately, JOI-kun lost the record of the groups the customers who received the desserts belong to. He plans to recover the record using information of the above Q events.

Write a program which, given the number of shops, groups, events, and the details of the events, determines for each “Service” whether a customer received a free dessert or not. If a customer received a free dessert, the program should find the index of the group the customer belongs to.

Read the following data from the standard input. Given values are all integers.

N M Q
(Query 1)
.
.
.
(Query Q)

In (Query i) (1 ≤ i ≤ Q), space-separated integers are written. Let T_i be the first integer. Then (Query i) means as follows.

• If T_i = 1, four more integers L_i, R_i, C_i, K_i are written in this order. This means the i-th event is “Join”, and, for every shop whose number is between L_i and R_i, inclusive, K_i customers from the group C_i joined the queue at its end.
• If T_i = 2, three more integers L_i, R_i, K_i are written in this order. This means the i-th event is “Leave”, and, for every shop whose number is between L_i and R_i, inclusive, if there were K_i or more customers in the queue, K_i customers from the beginning of the queue left. Otherwise, all the customers in the queue left.
• If T_i = 3, two more integers A_i, B_i are written in this order. This means the i-th event is “Service”, and, if there were B_i or more customers in the queue of the shop A_i, the shop gave a free dessert to the B_i-th customer from the beginning of the queue. Otherwise, the staff of the shop ate the free dessert.

Output one line to the standard output for each “Service”, i.e., for each event i (1 ≤ i ≤ Q) with T_i = 3. If a customer received a free dessert in the i-th event, the output should contain the number which represents the group the customer belongs to. If the staff of the shop ate the free dessert in the event i, the output should contain 0.

• 1 ≤ N ≤ 250 000.
• 1 ≤ M ≤ 250 000.
• 1 ≤ Q ≤ 250 000.
• T_i is either 1, 2, or 3 (1 ≤ i ≤ Q).
• If T_i = 1, we have 1 ≤ L_i ≤ R_i ≤ N, 1 ≤ C_i ≤ M, 1 ≤ K_i ≤ 1 000 000 000 (1 ≤ i ≤ Q).
• If T_i = 2, we have 1 ≤ L_i ≤ R_i ≤ N, 1 ≤ K_i ≤ 1 000 000 000 (1 ≤ i ≤ Q).
• If T_i = 3, we have 1 ≤ A_i ≤ N, 1 ≤ B_i ≤ 1 000 000 000 000 000 (= 10¹⁵) (1 ≤ i ≤ Q).
• T_i = 3 holds for at least one i (1 ≤ i ≤ Q).