IOI 中心是一个配备了生活设施的培训中心。中心内有一个供大型团体使用的大型美食广场。美食广场内有 $N$ 个排成一行的店铺，编号从 $1$ 到 $N$。每家店铺前都有一个供顾客排队的队列。顾客会在每个队列中排队。
今天，共有 $M$ 个团体入住 IOI 中心，编号从 $1$ 到 $M$。为了方便聊天，各团体的成员会以一种相当奇怪的方式排队。
在这个美食广场中，店铺有时会向队列中的顾客免费赠送甜点。在美食广场工作的 JOI 君的任务是记录下领取免费甜点的顾客所属的团体。
店铺关闭时，队列中没有顾客。今天，当店铺营业时，队列中发生了 $Q$ 次事件。第 $i$ 次事件是以下三种之一：
- Join：对于编号在 $L_i$ 到 $R_i$（含）之间的每一家店铺，来自团体 $C_i$ 的 $K_i$ 名顾客加入到队列的末尾。
- Leave：对于编号在 $L_i$ 到 $R_i$（含）之间的每一家店铺，如果队列中已有 $K_i$ 名或更多的顾客，则队列最前面的 $K_i$ 名顾客离开。否则，队列中的所有顾客都离开。
- Service：如果店铺 $A_i$ 的队列中有 $B_i$ 名或更多的顾客，则该店铺向队列中从前往后数的第 $B_i$ 名顾客免费赠送一份甜点。否则，店铺工作人员吃掉这份免费甜点。
不幸的是，JOI 君丢失了领取甜点的顾客所属团体的记录。他计划利用上述 $Q$ 次事件的信息来恢复记录。
请编写一个程序，给定店铺数量、团体数量、事件数量以及事件的详细信息，确定对于每一次“Service”事件，是否有顾客领取了免费甜点。如果顾客领取了免费甜点，程序应找出该顾客所属的团体编号。
输入格式
从标准输入读取以下数据。所有给定的值均为整数。
$N \ M \ Q$ (Query 1) . . . (Query Q)
在第 $i$ 次查询（$1 \le i \le Q$）中，输入一行空格分隔的整数。设第一个整数为 $T_i$。则第 $i$ 次查询的含义如下：
- 如果 $T_i = 1$，后面跟着四个整数 $L_i, R_i, C_i, K_i$。这意味着第 $i$ 次事件是“Join”，对于编号在 $L_i$ 到 $R_i$（含）之间的每一家店铺，来自团体 $C_i$ 的 $K_i$ 名顾客加入到队列的末尾。
- 如果 $T_i = 2$，后面跟着三个整数 $L_i, R_i, K_i$。这意味着第 $i$ 次事件是“Leave”，对于编号在 $L_i$ 到 $R_i$（含）之间的每一家店铺，如果队列中已有 $K_i$ 名或更多的顾客，则队列最前面的 $K_i$ 名顾客离开。否则，队列中的所有顾客都离开。
- 如果 $T_i = 3$，后面跟着两个整数 $A_i, B_i$。这意味着第 $i$ 次事件是“Service”，如果店铺 $A_i$ 的队列中有 $B_i$ 名或更多的顾客，则该店铺向队列中从前往后数的第 $B_i$ 名顾客免费赠送一份甜点。否则，店铺工作人员吃掉这份免费甜点。
输出格式
对于每一次“Service”事件，即对于每个 $T_i = 3$ 的事件 $i$（$1 \le i \le Q$），输出一行。如果顾客在第 $i$ 次事件中领取了免费甜点，输出该顾客所属的团体编号。如果店铺工作人员在第 $i$ 次事件中吃掉了免费甜点，输出 $0$。
数据范围
- $1 \le N \le 250\,000$
- $1 \le M \le 250\,000$
- $1 \le Q \le 250\,000$
- $T_i$ 为 $1, 2$ 或 $3$（$1 \le i \le Q$）
- 若 $T_i = 1$，则 $1 \le L_i \le R_i \le N, 1 \le C_i \le M, 1 \le K_i \le 1\,000\,000\,000$（$1 \le i \le Q$）
- 若 $T_i = 2$，则 $1 \le L_i \le R_i \le N, 1 \le K_i \le 1\,000\,000\,000$（$1 \le i \le Q$）
- 若 $T_i = 3$，则 $1 \le A_i \le N, 1 \le B_i \le 1\,000\,000\,000\,000\,000 \ (= 10^{15})$（$1 \le i \le Q$）
- 至少存在一个 $i$ 使得 $T_i = 3$（$1 \le i \le Q$）
子任务
- (2 分) $N \le 2\,000, Q \le 2\,000$。对于每个 $T_i = 1$ 或 $T_i = 2$ 的事件 $i$，满足 $K_i = 1$。
- (5 分) $N \le 2\,000, Q \le 2\,000$。
- (7 分) $N \le 65\,000, Q \le 65\,000$。对于每个 $T_i = 1$ 的事件 $i$，满足 $R_i - L_i \le 10$ 且 $K_i = 1$。
- (21 分) $M = 1$。
- (15 分) $N \le 65\,000, Q \le 65\,000$。对于每个 $T_i = 1$ 或 $T_i = 2$ 的事件 $i$，满足 $K_i = 1$。
- (13 分) $N \le 65\,000, Q \le 65\,000$。对于每个事件 $i$，满足 $T_i = 1$ 或 $T_i = 3$。
- (26 分) $N \le 65\,000, Q \le 65\,000$。
- (11 分) 无附加限制。
样例
样例输入 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
样例输出 1
2 0 4
样例输入 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
样例输出 2
4 0
样例输入 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
样例输出 3
0 22166 32334 0 82845 8750 60918