题目背景

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：https://www.cspro.org/。

“你知道对长跑选手来说，最棒的赞美是什么吗？”

“是‘快’吗？”

“不，是‘强’，”清濑说，“光跑得快，是没办法在长跑中脱颖而出的。天候、场地、比赛的发展、体能，还有自己的精神状态——长跑选手必须冷静分析这许多要素，即使面对再大的困难，也要坚忍不拔地突破难关。长跑选手需要的，是真正的‘强’。所以我们必须把‘强’当作最高的荣誉，每天不断跑下去。”

不论阿走或其他房客，全都全神贯注地聆听清濑的话。

“看了你这三个月来的表现，我越来越相信自己没看错人，”清濑接着说，“你很有天分，也很有潜力。所以呢，阿走，你一定要更相信自己，不要急着想一飞冲天。变强需要时间，也可以说它永远没有终点。长跑是值得一生投入的竞赛，有些人即使老了，仍然没有放弃慢跑或马拉松运动。”

——三浦紫苑《强风吹拂》

箱根驿传（正式名称为东京箱根间往复大学驿传竞走）是日本一项在每年 1 月 2-3 日举行的驿站接力赛，由关东学生田径联盟主办，关东的每所高校都有机会参加。在日本，箱根驿传是新年假期必看的比赛，许多家庭会一边吃年糕汤一边欣赏激烈的比赛。

今年，京都大学也想派出长跑队参加箱根驿传，田径部的长跑教练组织起一批预备役运动员，并开展了严苛的训练。

题目描述

京都大学的训练一共会持续 $m$ 天，在训练过程中正式队员的名单可能发生变化。简单起见，我们约定在且仅在第 $t (1 \leq t \leq m)$ 天结束时，会有以下三种事件之一发生：

1. 有一个学生跑 $10\text{km}$ 的速度达到了正式队员要求，教练将其作为最后一名纳入正式队员的名单中，这个学生的强度为 $x$；或者速度排名在最后一位的正式队员，由于速度过慢，而被从正式队员的名单中淘汰。
   • 在训练过程中，我们假定队员的速度的相对排名不会发生变化，与强度无关。
   • 严苛的教练制订了残酷的规则：被淘汰的学生虽然依然会跟大家一起训练，但将不能再次加入本年度参加箱根驿传的正式队员的名单中。
2. 由于近日的训练，第 $s$ 天结束时速度排名为 $l$ 至 $r$ 的选手的强度有了变化，变为此前的 $y$ 倍。
3. 教练在深夜想知道近日训练的效果，于是他统计了第 $s$ 天结束时速度排名为 $l$ 至 $r$ 的选手目前（即第 $t$ 天结束时）强度的和。由于这个结果可能很大，方便起见我们只考虑其模 $p$ 的值。

出于学生们的隐私考虑，事件日志有可能会被加密。

输入格式

从标准输入读入数据。

第一行为三个用空格隔开的整数 $m, p$ 和 $T$。

如果 $T = 0$，事件 1 中 $x = x'$，事件 2 中 $y = y'$；如果 $T = 1$，表示事件日志被加密了，事件 1 中 $x = x' \oplus A$，事件 2 中 $y = y' \oplus A$，其中 $\oplus$ 为按位异或运算，$A$ 为此前最后一次事件 3 所统计出的结果。如果此前没有事件 3 发生，则 $A = 0$。

接下来 $m$ 行，第 $t$ 行表示在第 $t$ 天结束时发生的事件：

• $1; x'$：表示事件 1 发生。若 $x > 0$，表示有一个强度为 $x$ 的学生作为最后一名纳入正式队员的名单；若 $x = 0$，表示排名在最后的正式队员被从名单中淘汰。保证有 $0 \leq x' < 2^{30}$。
• $2; s; l; r; y'$：表示事件 2 发生。保证有 $1 \leq s \leq t$, $1 \leq l \leq r \leq n$, $0 \leq y' < 2^{30}$，其中 $n$ 为在第 $s$ 天结束时正式队员的人数。
• $3; s; l; r$：表示事件 3 发生。保证有 $1 \leq s \leq t$, $1 \leq l \leq r \leq n$，其中 $n$ 为在第 $s$ 天结束时正式队员的人数。

输出格式

输出到标准输出。

对于每一个事件 3，输出一行一个数字，为其所统计出的结果。

8 10 0
1 7
1 3
1 0
1 4
2 4 1 2 2
3 2 1 2
2 1 1 1 3
3 6 1 2

7
0

200 307854322 1
1 304192542
1 261749745
1 227234660
1 258761107
1 71490397
1 72584186
1 172113773
1 170623186
1 109308637
1 108383253
1 221430535
1 184520171
1 12820964
1 64943840
1 271383631
1 103269159
1 12002213
1 141551258
1 200255671
1 303679342
1 177153246
1 242934504
1 192722694
1 81041418
1 129449540
1 208869479
1 193883084
1 47265951
1 14844237
1 204331401
1 120715260
1 183356222
1 151061115
1 97645108
1 95770509
1 10891614
1 136365751
1 277592250
1 244161106
1 74405936
1 140365146
1 22587603
1 172441554
1 300179553
1 235367849
1 75467014
1 291045594
1 220071302
1 26967280
1 279868778
1 109902396
1 286509675
1 275417760
1 74253569
1 57318310
1 147462465
1 89999340
1 17784677
1 245244350
1 138709004
1 214478013
1 134244031
1 298548097
1 17276277
1 183802269
1 22366514
1 275904549
1 142230969
1 116156399
1 63581175
1 136336228
1 214860504
1 72329372
1 204231581
1 78276583
1 277642488
1 81760292
1 7831561
1 134535873
1 42237141
1 165620849
1 286362129
1 87388726
1 288617590
1 97675237
1 113222505
1 292912
1 98092392
1 257549905
1 180583994
1 244157382
1 117371320
1 304810612
1 148813285
1 150599985
1 229632823
1 246806551
1 297736161
1 66536628
1 70165839
1 31086027
1 0
1 46984478
1 0
3 13 2 11
1 134407869
1 134407869
2 73 7 31 130418473
1 134407869
1 62804642
1 134407869
1 134407869
3 28 12 21
1 173819539
3 93 34 83
3 68 5 38
1 95422722
2 85 54 85 89788932
2 28 2 25 251954506
1 185543612
1 34466375
1 185543612
2 28 2 13 51844756
3 43 22 33
3 97 5 87
1 53569742
1 83590412
1 53569742
2 1 1 1 131620724
2 128 5 72 41971821
1 53569742
1 197197823
1 333156690
3 59 48 50
1 224641252
1 24037560
3 54 26 40
2 91 7 37 58105019
2 59 4 50 254285874
3 112 17 63
3 103 53 54
3 3 1 3
3 4 4 4
2 121 68 76 258392700
2 88 55 59 10180251
2 110 45 76 125533148
1 160394017
1 170735200
3 51 18 34
3 136 43 64
1 49346652
1 114223193
3 62 17 26
3 57 8 40
1 278848254
1 278848254
1 411603847
1 278848254
1 278848254
1 278848254
2 112 70 79 437553006
2 120 4 89 428224488
3 53 50 51
2 109 36 81 205513848
3 81 31 46
3 78 45 64
2 107 19 28 8661353
3 36 21 33
2 28 4 28 227981470
2 42 18 29 7067955
1 1536382
1 214941299
1 176373062
2 172 26 74 241772251
1 21368911
2 61 50 61 37266210
3 84 30 48
3 31 8 24
1 297156062
1 328205831
2 175 57 77 408989526
1 528105214
2 30 4 24 416690156
3 9 4 8
1 31664726
3 144 40 67
1 276474902
2 115 56 72 15951722
2 187 6 50 38653155
1 17582098
1 276474902
1 415944350
3 34 1 24
1 204461450
2 136 1 59 92444637
3 79 7 79
3 22 2 17
1 284506459
2 166 78 86 22058413
1 30931926

134407869
184056088
13293385
185543612
34566045
53569742
224641252
2971977
10689074
196073568
220349662
170735200
273278086
25664733
155812556
278848254
238098134
256392602
172981220
1536382
57033232
297156062
31664726
276474902
204461450
168966052
30931926

提示

样例 1 解释

第 $1$ 天结束时，有一个强度为 $7$ 的学生被列为正式队员，我们不妨称他为小津。此时正式队员名单依次为：小津。

第 $2$ 天结束时，有一个强度为 $3$ 的学生被列为正式队员，我们不妨称他为城崎。此时正式队员名单依次为：小津、城崎。

第 $3$ 天结束时，城崎被淘汰了。此时正式队员名单为：小津。

第 $4$ 天结束时，有一个强度为 $4$ 的学生被列为正式队员，我们不妨称他为樋口清太郎。此时正式队员名单依次为：小津、樋口清太郎。

第 $5$ 天结束时，由于近日的训练，第 $4$ 天正式队员名单中第 $1$ 至 $2$ 个人——即小津和樋口清太郎——的强度乘了 $2$，所以，小津的强度达到了 $14$，樋口清太郎的强度达到了 $8$。

第 $6$ 天结束时，教练统计了第 $2$ 天正式队员名单中第 $1$ 至 $2$ 个人——即小津和城崎——当前的强度，小津的强度为 $14$，城崎的强度为 $3$，故统计结果为 $17$，模 $p$ 的值为 $7$。

第 $7$ 天结束时，由于近日的训练，第 $1$ 天正式队员名单中的第 $1$ 个人——即小津——的强度乘了 $3$，所以，小津的强度达到了 $42$。

第 $8$ 天结束时，教练统计了第 $6$ 天正式队员名单中第 $1$ 至 $2$ 个人——即小津和樋口清太郎——当前的强度，小津的强度为 $42$，樋口清太郎的强度为 $8$，故统计结果为 $50$，模 $p$ 的值为 $0$。

子任务

$1 \leq m \leq 3 \times 10^5$, $2 \leq p < 2^{30}$, $T \in {0, 1}$

测试点	特殊性质	$T$
$1$	$m \leq 5000$	$1$
$2$	事件 1 中 $x > 0$	^
$3$	没有事件 2
$4$	事件 1 中 $x$ 在 ${0, 1}$ 中随机选取	$0$
$5$	$r - l \leq 10$	^
$6$	^	$1$
$7, 8$	无	$0$
$9, 10$	^	$1$

每个测试点占 $10$ 分。