AT_joisc2021_c.フードコート (Foodcourt)

translate from P7560，copied by @Network_Error

有 $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$。

样例 #1

样例输入 #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

样例输入 #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

样例输入 #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

样例 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$ 个家庭）被送上秘制书虫。

数据规模与约定

对于 $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：只有 加入事件 和 白嫖事件。

翻译自 第２０回日本情報オリンピック　春季トレーニング合宿 Day1 C フードコート (Food Court) 的英文版本。