2858: [JOISC 2021 Day1]饮食区
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：7
解决：3
题目描述
IOI 中心是一个配备了生活设施的训练中心。这里有着为大型团体设置的饮食区。在饮食区内，依次排列着 N 家商店，从 1 到 N 标号。在每家商店前，都有一个为顾客准备的队列。顾客们会在每个队列中排队。
今天有 M 个团体呆在 IOI 中心，从 1 到 M 标号。团体中的成员们会以一种相对奇怪的方式排队，以享受他们之间的闲谈。
在这个饮食区中，有时商店会给予在他们的队列中的顾客免费的甜点。在饮食区中工作的 JOI 君的工作内容是记录被给予免费甜点的顾客所在的团体编号。
没有顾客会在关门的商店前排队。今天，当所有商店都营业时，在队列中发生了 Q 次事件。第 i 次事件是下列几种之一：
1. 加入：对于编号在 Li 到 Ri 之间（包括边界）的所有商店，来自 Ci 团体的 Ki 位顾客加入于队列的末尾。
2. 离开：对于编号在 Li 到 Ri 之间（包括边界）的所有商店，如果队列中有 Ki 或更多位顾客，于队列开头的前 Ki 位顾客离开队列。否则，所有顾客离开队列。
3. 服务：如果在商店 Ai 前的队列中有 Bi 或更多位顾客，商店会给予队列中从开头数起第 Bi 位顾客一个免费甜点。否则商店的工作人员会吃掉免费甜点。
不幸的是，JOI 君丢失了被给予免费甜点的顾客所在的团体编号的记录。他决定利用上述 Q 次事件的信息恢复记录。
给出商店、团体、事件的数量，以及事件的详细信息，请编写一个程序确定每次“服务”时是否有顾客被给予了免费甜点。如果有顾客被给予了免费甜点，程序还应该确定这位顾客所在的团体的编号。
今天有 M 个团体呆在 IOI 中心，从 1 到 M 标号。团体中的成员们会以一种相对奇怪的方式排队，以享受他们之间的闲谈。
在这个饮食区中，有时商店会给予在他们的队列中的顾客免费的甜点。在饮食区中工作的 JOI 君的工作内容是记录被给予免费甜点的顾客所在的团体编号。
没有顾客会在关门的商店前排队。今天，当所有商店都营业时，在队列中发生了 Q 次事件。第 i 次事件是下列几种之一：
1. 加入：对于编号在 Li 到 Ri 之间（包括边界）的所有商店，来自 Ci 团体的 Ki 位顾客加入于队列的末尾。
2. 离开：对于编号在 Li 到 Ri 之间（包括边界）的所有商店，如果队列中有 Ki 或更多位顾客，于队列开头的前 Ki 位顾客离开队列。否则，所有顾客离开队列。
3. 服务：如果在商店 Ai 前的队列中有 Bi 或更多位顾客，商店会给予队列中从开头数起第 Bi 位顾客一个免费甜点。否则商店的工作人员会吃掉免费甜点。
不幸的是，JOI 君丢失了被给予免费甜点的顾客所在的团体编号的记录。他决定利用上述 Q 次事件的信息恢复记录。
给出商店、团体、事件的数量，以及事件的详细信息，请编写一个程序确定每次“服务”时是否有顾客被给予了免费甜点。如果有顾客被给予了免费甜点，程序还应该确定这位顾客所在的团体的编号。
输入
第一行，三个正整数 N, M, Q。
接下来 Q 行，第 i 行描述一个事件：
令 Ti 为第一个数，则第 i 个询问：
1. 如果 Ti = 1，同一行接下来四个正整数 Li, Ri, Ci, Ki。表示第 i 次事件为“加入”，并且对于编号在 Li 到 Ri 之间（包括边界）的所有商店，来自 Ci 团体的 Ki 位顾客加入于队列的末尾。
2. 如果 Ti = 2，同一行接下来三个正整数 Li, Ri, Ki。表示第 i 次事件为“离开”，并且对于编号在 Li 到 Ri 之间（包括边界）的所有商店，如果队列中有 Ki 或更多位顾客，于队列开头的前 Ki 位顾客离开队列。否则，所有顾客离开队列。
3. 如果 Ti = 3，同一行接下来两个正整数 Ai, Bi。表示第 i 次事件为“服务”，并且如果在商店 Ai 前的队列中有 Bi 或更多位顾客，商店会给予队列中从开头数起第 Bi 位顾客一个免费甜点。否则商店的工作人员会吃掉免费甜点。
接下来 Q 行，第 i 行描述一个事件：
令 Ti 为第一个数，则第 i 个询问：
1. 如果 Ti = 1，同一行接下来四个正整数 Li, Ri, Ci, Ki。表示第 i 次事件为“加入”，并且对于编号在 Li 到 Ri 之间（包括边界）的所有商店，来自 Ci 团体的 Ki 位顾客加入于队列的末尾。
2. 如果 Ti = 2，同一行接下来三个正整数 Li, Ri, Ki。表示第 i 次事件为“离开”，并且对于编号在 Li 到 Ri 之间（包括边界）的所有商店，如果队列中有 Ki 或更多位顾客，于队列开头的前 Ki 位顾客离开队列。否则，所有顾客离开队列。
3. 如果 Ti = 3，同一行接下来两个正整数 Ai, Bi。表示第 i 次事件为“服务”，并且如果在商店 Ai 前的队列中有 Bi 或更多位顾客，商店会给予队列中从开头数起第 Bi 位顾客一个免费甜点。否则商店的工作人员会吃掉免费甜点。
输出
对于每次“服务”事件，也就是所有满足 Ti = 3 的事件 i（1 ≤ i ≤ Q）输出一行。如果在第 i 次事件中有顾客被给予了免费甜点，输出这位顾客所在的团体的编号。如果在第 i 次事件中商店的工作人员吃掉了免费甜点，输出 "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
提示
1 ≤ N, M, Q ≤ 2.5 × 10 ^ 5，Ti ∈ {1, 2, 3}，1 ≤ Li, Ri, Ai ≤ N，1 ≤ Ci ≤ M，1 ≤ Ki ≤ 10 ^ 9，1 ≤ Bi ≤ 10 ^ 15，至少存在一次满足 Ti = 3 的事件。