[JOISC 2021 Day1] フードコート

本题数据保留一部分，请在 [此处](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day1/foodcourt-data.zip) 获取完整数据。

有 $N$ 家书虫食品店，有 $M$ 个家庭来享受用书虫制作的美味食物。 因为食品店十分火爆，所以顾客需要排队，刚开始所有队列都是空的。 今天食品店又全部开张了，发生了 $Q$ 个事件： - **加入事件**：编号位于区间 $[L,R]$ 内的所有食品店中，都有编号为 $C$ 的家庭加入队尾，每个满足要求的食品店队尾都加入了 $K$ 个人。 - **离开事件**：编号位于区间 $[L,R]$ 内的所有食品店中，如果队列有超过 $K$ 个人，那么队列的前 $K$ 个人离开队列，否则队列里的所有人离开队列。 - **白嫖事件**：如果编号为 $A$ 的食品店的队列中有大于等于 $B$ 个人，那么食品店就会赠送从队列开头开始数第 $B$ 个人一份秘制书虫，否则店员会吃掉书虫。 求每次 **白嫖事件** 是否有顾客被赠送了秘制书虫，如果有的话，求顾客所在的家庭。

第一行三个整数 $N,M,Q$ 代表食品店个数，家庭个数和事件个数。 接下来 $Q$ 行，每行首先一个整数 $T$： - $T=1$，接下来四个整数 $L,R,C,K$ 描述 **加入事件**。 - $T=2$，接下来三个整数 $L,R,K$ 描述 **离开事件**。 - $T=3$，接下来两个整数 $A,B$ 描述 **白嫖事件**。

对于所有 **白嫖事件**，一行一个整数： - 如果有顾客被送了秘制书虫，输出他所在的家庭。 - 如果店员吃掉了书虫，输出 $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

#### 样例 1 解释 我们用 $Q_i(a_1,a_2,\cdots,a_k)$ 代表第 $i$ 个食品店的队列，$a_1$ 为队首，$a_k$ 为队尾，其中 $a_i=p$ 就代表第 $i$ 个位置的人来自第 $p$ 个家庭。特殊地，$Q_i()$ 就代表当前队列为空。 根据样例 1 的这几个事件： - 第 $1$ 个 **加入事件**： $$Q_1(),Q_2(5,5),Q_3(5,5)$$ - 第 $2$ 个 **加入事件**： $$Q_1(2,2,2,2),Q_2(5,5,2,2,2,2),Q_3(5,5)$$ - 第 $3$ 个 **白嫖事件**，第 $2$ 个食品店的第 $3$ 个人（第 $2$ 个家庭）被送上秘制书虫。 - 第 $4$ 个 **离开事件**： $$Q_1(2),Q_2(2,2,2),Q_3()$$ - 第 $5$ 个 **白嫖事件**，第 $1$ 个食品店不够 $2$ 个人，店员会吃掉书虫。 - 第 $6$ 个 **加入事件**： $$Q_1(2),Q_2(2,2,2,4,4),Q_3(4,4)$$ - 第 $7$ 个 **白嫖事件**，第 $3$ 个食品店的第 $2$ 个人（第 $4$ 个家庭）被送上秘制书虫。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（2 pts）：$N,Q \le 2000$，满足性质 A。 - Subtask 2（5 pts）：$N,Q \le 2000$。 - Subtask 3（7 pts）：$N,Q \le 65000$，满足性质 B。 - Subtask 4（21 pts）：$M=1$。 - Subtask 5（15 pts）：$N,Q \le 65000$，满足性质 A。 - Subtask 6（13 pts）：$N,Q \le 65000$，满足性质 C。 - Subtask 7（26 pts）：$N,Q \le 65000$。 - Subtask 8（11 pts）：无特殊限制。 对于 $100\%$ 的数据： - $1 \le N,M,Q \le 25 \times 10^4$。 - $T \in \{1,2,3\}$。 - 对于所有 **加入事件**，$1 \le L \le R \le N$，$1 \le C \le M$，$1 \le K \le 10^9$。 - 对于所有 **离开事件**，$1 \le L \le R \le N$，$1 \le K \le 10^9$。 - 对于所有 **白嫖事件**，$1 \le A \le N$，$1 \le B \le 10^{15}$。 - 至少有一个 **白嫖事件**。 有以下若干个性质： - 性质 A：对于所有 **加入事件** 和 **离开事件**，有 $K=1$。 - 性质 B：对于所有 **加入事件**，有 $R-L \le 10$ 和 $K=1$。 - 性质 C：只有 **加入事件** 和 **白嫖事件**。 #### 说明 翻译自 [第２０回日本情報オリンピック　春季トレーニング合宿](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/index.html) [Day1 C フードコート (Food Court) 的英文版本](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day1/foodcourt-en.pdf)。