题目描述

题目译自 JOISC 2021 Day1 T3「フードコート / Food Court」

IOI 中心是一个配备了生活设施的训练中心。这里有着为大型团体设置的饮食区。在饮食区内，依次排列着 $N$ 家商店，从 $1$ 到 $N$ 标号。在每家商店前，都有一个为顾客准备的队列。顾客们会在每个队列中排队。

今天有 $M$ 个团体呆在 IOI 中心，从 $1$ 到 $M$ 标号。团体中的成员们会以一种相对奇怪的方式排队，以享受他们之间的闲谈。

在这个饮食区中，有时商店会给予在他们的队列中的顾客免费的甜点。在饮食区中工作的 JOI 君的工作内容是记录被给予免费甜点的顾客所在的团体编号。

没有顾客会在关门的商店前排队。今天，当所有商店都营业时，在队列中发生了 $Q$ 次事件。第 $i$ 次事件是下列几种之一：

1. 加入：对于编号在 $L_i$ 到 $R_i$ 之间（包括边界）的所有商店，来自 $C_i$ 团体的 $K_i$ 位顾客加入于队列的末尾。
2. 离开：对于编号在 $L_i$ 到 $R_i$ 之间（包括边界）的所有商店，如果队列中有 $K_i$ 或更多位顾客，于队列开头的前 $K_i$ 位顾客离开队列。否则，所有顾客离开队列。
3. 服务：如果在商店 $A_i$ 前的队列中有 $B_i$ 或更多位顾客，商店会给予队列中从开头数起第 $B_i$ 位顾客一个免费甜点。否则商店的工作人员会吃掉免费甜点。

不幸的是，JOI 君丢失了被给予免费甜点的顾客所在的团体编号的记录。他决定利用上述 $Q$ 次事件的信息恢复记录。

给出商店、团体、事件的数量，以及事件的详细信息，请编写一个程序确定每次“服务”时是否有顾客被给予了免费甜点。如果有顾客被给予了免费甜点，程序还应该确定这位顾客所在的团体的编号。

输入格式

第一行，三个正整数 $N, M, Q$。
接下来 $Q$ 行，第 $i$ 行描述一个事件：
令 $T_i$ 为第一个数，则第 $i$ 个询问：

1. 如果 $T_i = 1$，同一行接下来四个正整数 $L_i, R_i, C_i, K_i$。表示第 $i$ 次事件为“加入”，并且对于编号在 $L_i$ 到 $R_i$ 之间（包括边界）的所有商店，来自 $C_i$ 团体的 $K_i$ 位顾客加入于队列的末尾。
2. 如果 $T_i = 2$，同一行接下来三个正整数 $L_i, R_i, K_i$。表示第 $i$ 次事件为“离开”，并且对于编号在 $L_i$ 到 $R_i$ 之间（包括边界）的所有商店，如果队列中有 $K_i$ 或更多位顾客，于队列开头的前 $K_i$ 位顾客离开队列。否则，所有顾客离开队列。
3. 如果 $T_i = 3$，同一行接下来两个正整数 $A_i, B_i$。表示第 $i$ 次事件为“服务”，并且如果在商店 $A_i$ 前的队列中有 $B_i$ 或更多位顾客，商店会给予队列中从开头数起第 $B_i$ 位顾客一个免费甜点。否则商店的工作人员会吃掉免费甜点。

输出格式

对于每次“服务”事件，也就是所有满足 $T_i = 3$ 的事件 $i$（$1 \le i \le Q$）输出一行。如果在第 $i$ 次事件中有顾客被给予了免费甜点，输出这位顾客所在的团体的编号。如果在第 $i$ 次事件中商店的工作人员吃掉了免费甜点，输出 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

数据范围与提示

本题采用捆绑测试。

对于 $100 \%$ 的数据，$1 \le N, M, Q \le 2.5 \times {10}^5$，$T_i \in \{ 1, 2, 3 \}$，$1 \le L_i, R_i, A_i \le N$，$1 \le C_i \le M$，$1 \le K_i \le {10}^9$，$1 \le B_i \le {10}^{15}$，至少存在一次满足 $T_i = 3$ 的事件。

每个子任务的具体限制见下表：