题目描述

卢瑞恩守望着泪水之城。

泪水之城可以被抽象为一个长为 $n$ 的整数序列，初始为序列 $\{a_i\}$。在接下来的时间里，会依次发生 $m$ 个事件。每个事件会是以下三种事件之一：

1. 区间 $[l,r]$ 内的元素增加了 $v$（$v$ 可能是负数）。
2. 卢瑞恩派出了一个守望者，监视区间 $[l,r]$。
3. 卢瑞恩询问了第 $i$ 个派遣出的守望者，守望者会回答它的监视结果。一个守望者的监视结果为，自它被派遣出至被询问的这一段时间里，它所观察的区间内的元素的最大值。

三类事件分别用 1 l r v、2 l r、3 i 来表示。

其实不需要其他守望者的报告，卢瑞恩也能根据发生的事件和初始序列计算出每个 3 类事件的监视结果。可是它算得太慢了，你能帮帮它吗？

形式化题意：给定一个长为 $n$ 的、初始为 $\{a_i\}$ 的整数序列，接下来按时间发生上述 $m$ 个事件，你要对每个 3 类事件，输出它的“监视结果”。部分测试点强制在线。

输入格式

第一行三个正整数 $n,m,op$。

第二行 $n$ 个正整数 $a_1,a_2,\dots,a_n$。

接下来 $m$ 行，每行表示一个事件，格式如题目描述中所述。

若 $op=0$，则输入中的数就是真实的事件参数；否则，设上一个 3 类事件的输出为 $last$（若不存在上一个 3 类事件则 $last=0$），你需要对输入进行如下处理才能得到真实的事件参数（其中 $\oplus$ 为异或运算）：

• 1 l r v $\rightarrow$ 1 (l ⊕ last) (r ⊕ last) (v ⊕ last)
• 2 l r $\rightarrow$ 2 (l ⊕ last) (r ⊕ last)
• 3 i $\rightarrow$ 3 (i ⊕ last)

输出格式

对于每个 3 类事件，输出一行一个整数，表示这次事件的结果。

99 100 0
821549273 343134352 184511456 742695763 194318793 357160643 -753603723 -250960302 361601523 210968755 569945004 -634248405 397079195 -886244646 523203210 -640831795 -939566336 -751628361 -648925605 -975434957 -983318230 -831135500 -250879424 -551448306 87428605 -58877766 173830639 816730936 -898492497 -726676271 -556070430 775573129 616458081 628441026 370785244 -336706774 -161881979 617181521 412332924 -947764104 -319333372 -165205719 -582012508 -922254177 -198934012 941190702 -710569619 -138500347 -957921307 -359495224 -261418951 -941239537 -190630723 487701626 -640171490 896797882 -718659788 533659149 566045170 -764635932 806982878 -990025261 -989062803 275957312 490932118 234238794 939250538 -818433508 -296063332 204099815 -766197612 384603296 -961105905 -348210120 314865472 -307523564 -554503066 604295854 553976089 -512424373 -902683018 -854926509 -601147556 -93313741 632775117 -241319046 -343999507 914115329 -855143544 -925437985 -998004251 951839334 -915463246 -987067054 80312998 427985226 99688094 -127920111 609551718 
1 17 45 40744410
1 21 60 -487417060
2 64 83
2 42 54
1 31 50 463555671
3 2
3 2
1 19 26 922481054
3 1
3 1
2 24 31
2 59 67
3 3
3 3
3 3
1 16 56 -587438809
3 2
2 19 43
2 15 85
3 3
2 54 64
2 42 90
3 4
3 1
1 3 25 -299455731
2 9 88
3 4
1 1 85 639315075
1 56 73 852133911
3 7
3 6
1 32 73 -903997535
1 75 81 604809492
3 9
1 39 53 -19612499
3 1
2 8 72
2 19 53
3 9
1 22 28 -9817781
2 58 93
1 29 85 766144705
2 61 77
1 4 79 335715093
3 13
2 35 91
2 42 65
1 21 23 -352790248
2 37 98
1 86 88 92349171
2 37 59
2 23 72
2 34 40
1 10 23 -948230397
1 45 72 74643248
2 56 63
1 9 90 -883489509
2 85 95
3 14
1 28 76 -348141381
1 23 44 342154912
2 71 96
2 19 26
1 28 38 643132570
1 22 44 -256072493
3 17
1 11 15 -573881433
2 5 62
1 33 35 350071668
3 21
1 32 97 176419358
1 2 29 418353439
2 3 7
1 5 29 -942279080
2 24 98
3 20
2 61 90
1 30 31 692609211
1 10 73 633147022
3 6
2 17 66
2 31 70
1 96 97 664974050
1 5 85 -1267462
1 69 87 176004560
3 20
2 14 45
2 5 57
3 29
1 10 18 -473501134
2 40 73
2 4 32
2 26 63
3 3
3 20
1 29 80 394017086
3 14
3 31
1 46 56 -68262794
1 9 20 -955035391

917329313
917329313
939250538
939250538
563237009
563237009
563237009
917329313
563237009
939250538
939250538
939250538
2298431864
2430699524
2430699524
2430699524
2430699524
2660849837
2950280219
1842582607
1154745388
2570937375
2950280219
2570937375
2281140525
1437888987
2570937375
2950280219
1945034347

数据范围

下述数据范围均指代真实数据范围（即经过强制在线解密后的数据），并不保证原始输入数据符合此范围。

• 对于 10% 的数据：保证 $n,m\le 100$。
• 对于 30% 的数据：保证 $n,m\le 5000$。
• 对于 60% 的数据：保证 $n,m\le 2\times 10^4$。
• 对于 100% 的数据：$n,m\le 2\times 10^5$；$1\le l\le r\le n$；$|v|,|a_i|\le 10^9$。
• 对于每一档部分分，其中 50% 的数据满足 $op=0$，另 50% 的数据满足 $op=1$。