logo AlgoBeat OnlineJudge
登录 注册

#216047. [CSPro 23] 箱根山岳险天下

内存限制:512 MiB 时间限制:1999 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

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

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

“是‘快’吗?”

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

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

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

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

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

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


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

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

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

输入格式

从标准输入读入数据。

第一行为三个用空格隔开的整数

如果 ,事件 1 中 ,事件 2 中 ;如果 ,表示事件日志被加密了,事件 1 中 ,事件 2 中 ,其中 为按位异或运算, 为此前最后一次事件 3 所统计出的结果。如果此前没有事件 3 发生,则

接下来 行,第 行表示在第 天结束时发生的事件:

  • :表示事件 1 发生。若 ,表示有一个强度为 的学生作为最后一名纳入正式队员的名单;若 ,表示排名在最后的正式队员被从名单中淘汰。保证有
  • :表示事件 2 发生。保证有 , , ,其中 为在第 天结束时正式队员的人数。
  • :表示事件 3 发生。保证有 , ,其中 为在第 天结束时正式队员的人数。

输出格式

输出到标准输出。

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

样例

样例输入 1

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

样例输出 1

7
0

样例输入 2

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

样例输出 2

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 中 ^
没有事件 2
事件 1 中 中随机选取
^
^
^

每个测试点占 分。