Background

The testdata on Luogu is only for community exchange and is not official testdata. Official judging link: https://www.cspro.org/.

“Do you know what the best compliment is for a long-distance runner?”

“Is it ‘fast’?”

“No, it’s ‘strong’,” Kiyose said. “Just being fast is not enough to stand out in long-distance running. Weather, the course, how the race develops, physical condition, and your own mental state—long-distance runners must calmly analyze all these factors. Even when facing huge difficulties, they must endure and push through. What long-distance runners need is real ‘strength’. So we must treat ‘strength’ as the highest honor and keep running every day.”

Whether it was Aoi or the other housemates, everyone listened to Kiyose with full attention.

“Seeing how you’ve done these past three months, I believe more and more that I didn’t choose the wrong person,” Kiyose continued. “You’re talented, and you have great potential. So, Aoi, you must believe in yourself more, and don’t rush to become amazing overnight. Getting stronger takes time, and you could also say it never has an endpoint. Long-distance running is a competition worth dedicating a lifetime to. Some people, even when they’re old, still don’t give up jogging or marathons.”

— Shion Miura, The Wind Rises Strongly (pinyin: Qiang Feng Chui Fu).

The Hakone Ekiden (official name: Tokyo-Hakone Round-Trip Intercollegiate Ekiden Race) is a Japanese relay road race held every year on January 2-3, hosted by the Kanto Intercollegiate Athletic Association. Every university in the Kanto region has a chance to participate. In Japan, the Hakone Ekiden is a must-watch during the New Year holiday, and many families watch the intense race while eating ozoni.

This year, Kyoto University also wants to send a long-distance team to the Hakone Ekiden. The long-distance coach of the track and field club organized a group of reserve athletes and started strict training.

Problem Description

Kyoto University’s training lasts for a total of $m$ days. During training, the roster of official team members may change. For simplicity, we agree that at and only at the end of day $t \ (1 \leq t \leq m)$, exactly one of the following three events happens:

1. Either a student’s $10\text{km}$ speed reaches the official-member requirement, and the coach adds them as the last member of the official roster, with strength $x$; or the official member ranked last in speed is eliminated from the official roster due to being too slow.
   • During training, we assume the relative speed ranking of athletes never changes, and it is unrelated to strength.
   • The strict coach sets a harsh rule: an eliminated student will still train with everyone, but cannot rejoin this year’s official roster for the Hakone Ekiden.
2. Due to recent training, at the end of day $s$, the strengths of athletes whose speed ranks are from $l$ to $r$ change to $y$ times their previous values.
3. Late at night, the coach wants to know the effect of recent training, so he computes the sum of the current (i.e., at the end of day $t$) strengths of athletes whose speed ranks are from $l$ to $r$ in the roster at the end of day $s$. Since the result may be large, we only consider its value modulo $p$.

To protect students’ privacy, the event log may be encrypted.

Input Format

Read input from standard input.

The first line contains three integers $m, p$ and $T$, separated by spaces.

If $T = 0$, then in event 1, $x = x'$, and in event 2, $y = y'$. If $T = 1$, the event log is encrypted: in event 1, $x = x' \oplus A$, and in event 2, $y = y' \oplus A$, where $\oplus$ is the bitwise XOR operation, and $A$ is the result computed by the most recent event 3. If no event 3 has occurred before, then $A = 0$.

The next $m$ lines describe the events. Line $t$ describes the event that happens at the end of day $t$:

• 1; x': event 1 happens. If $x > 0$, a student with strength $x$ is added as the last member of the official roster; if $x = 0$, the last-ranked official member is eliminated from the roster. It is guaranteed that $0 \leq x' < 2^{30}$.
• 2; s; l; r; y': event 2 happens. It is guaranteed that $1 \leq s \leq t$, $1 \leq l \leq r \leq n$, $0 \leq y' < 2^{30}$, where $n$ is the number of official members at the end of day $s$.
• 3; s; l; r: event 3 happens. It is guaranteed that $1 \leq s \leq t$, $1 \leq l \leq r \leq n$, where $n$ is the number of official members at the end of day $s$.

Output Format

Write output to standard output.

For each event 3, output one line containing one integer: the computed result.

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

Hint

Sample 1 Explanation

At the end of day $1$, a student with strength $7$ is listed as an official member; let us call him Oz. The official roster is: Oz.

At the end of day $2$, a student with strength $3$ is listed as an official member; let us call him Jonosaki. The official roster is: Oz, Jonosaki.

At the end of day $3$, Jonosaki is eliminated. The official roster is: Oz.

At the end of day $4$, a student with strength $4$ is listed as an official member; let us call him Higuchi Seitaro. The official roster is: Oz, Higuchi Seitaro.

At the end of day $5$, due to recent training, in the roster at the end of day $4$, the strengths of the $1$st to $2$nd members—namely Oz and Higuchi Seitaro—are multiplied by $2$. Therefore, Oz’s strength becomes $14$, and Higuchi Seitaro’s strength becomes $8$.

At the end of day $6$, the coach computes the current strengths of the $1$st to $2$nd members in the roster at the end of day $2$—namely Oz and Jonosaki. Oz’s strength is $14$, Jonosaki’s strength is $3$, so the sum is $17$, and its value modulo $p$ is $7$.

At the end of day $7$, due to recent training, in the roster at the end of day $1$, the strength of the $1$st member—namely Oz—is multiplied by $3$. Therefore, Oz’s strength becomes $42$.

At the end of day $8$, the coach computes the current strengths of the $1$st to $2$nd members in the roster at the end of day $6$—namely Oz and Higuchi Seitaro. Oz’s strength is $42$, Higuchi Seitaro’s strength is $8$, so the sum is $50$, and its value modulo $p$ is $0$.

Subtasks

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

Each test point is worth $10$ points.

Translated by ChatGPT 5