— Willem...

— What's the matter?

— It seems that there's something wrong with Seniorious...

— I'll have a look...

<img class="tex-graphics" src="https://espresso.codeforces.com/43c1b40837a8d0f9245554bac363fe1a7a21a74b.png" style="max-width: 100.0%;max-height: 100.0%;"/>

Seniorious is made by linking special talismans in particular order.

After over 500 years, the carillon is now in bad condition, so Willem decides to examine it thoroughly.

Seniorious has *n* pieces of talisman. Willem puts them in a line, the *i*-th of which is an integer *a*<sub class="lower-index">*i*</sub>.

In order to maintain it, Willem needs to perform *m* operations.

There are four types of operations:
-  1 *l* *r* *x*: For each *i* such that *l* ≤ *i* ≤ *r*, assign *a*<sub class="lower-index">*i*</sub> + *x* to *a*<sub class="lower-index">*i*</sub>.-  2 *l* *r* *x*: For each *i* such that *l* ≤ *i* ≤ *r*, assign *x* to *a*<sub class="lower-index">*i*</sub>.-  3 *l* *r* *x*: Print the *x*-th smallest number in the index range [*l*, *r*], i.e. the element at the *x*-th position if all the elements *a*<sub class="lower-index">*i*</sub> such that *l* ≤ *i* ≤ *r* are taken and sorted into an array of non-decreasing integers. It's guaranteed that 1 ≤ *x* ≤ *r* - *l* + 1.-  4 *l* *r* *x* *y*: Print the sum of the *x*-th power of *a*<sub class="lower-index">*i*</sub> such that *l* ≤ *i* ≤ *r*, modulo *y*, i.e. <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/bb452ebe2c68ca0f9c697357e053ba4e4b93c89e.png" style="max-width: 100.0%;max-height: 100.0%;"/>.
The only line contains four integers *n*, *m*, *seed*, *v*<sub class="lower-index">*max*</sub> (1 ≤ *n*, *m* ≤ 10<sup class="upper-index">5</sup>, 0 ≤ *seed* &lt; 10<sup class="upper-index">9</sup> + 7, 1 ≤ *vmax* ≤ 10<sup class="upper-index">9</sup>).

The initial values and operations are generated using following pseudo code:

Here *op* is the type of the operation mentioned in the legend.
In the first example, the initial array is {8, 9, 7, 2, 3, 1, 5, 6, 4, 8}.

The operations are:
 -  2 6 7 9 -  1 3 10 8 -  4 4 6 2 4 -  1 4 5 8 -  2 1 7 1 -  4 7 9 4 4 -  1 2 7 9 -  4 5 8 1 1 -  2 5 7 5 -  4 3 10 8 5
10 10 7 9
2
1
0
3
10 10 9 9
1
1
3
3
1000 1000 658073485 946088556
375432604
52885108
732131239
335583873
375432604
582199284
235058938
682619432
62026709
631048460
51394660
25596188
244696891
1009575922
9787768
9787768
618642640
278237785
251668359
321813234
563194827
101752810
208858224
262327445
11344020
907542692
275574805
1182618779
20489113
1215012508
838060601
15849943
168527462
537661946
301301341
838060601
46928748
656331376
1656165287
181551648
31803656
1136481
836554656
836554656
836554656
487461834
653789051
24729...
1000 1000 663001819 921338426
549050815
1494447218
123274718
949106303
363391514
1550246060
107855794
206930179
462058384
167101179
858273570
356404756
156657135
591408459
315837577
277556562
423807049
57871554
207585345
207585345
711053606
62414948
736991621
141019877
15668980
1659611655
39231619
202790129
3196038
236864151
56524932
313582670
72493924
535770507
88995537
194484599
539736025
273631024
149972180
416123619
323570345
695471102
71796515
66127408
1269337883
296472622
72864255
42...
1000 1000 811605498 961464625
230231691
50907792
772872116
28726758
20957398
48216401
564116048
70658978
9545021
789851575
993564693
754556313
1407453357
281963589
624055178
50804159
50804159
894467226
24436906
209344702
583604216
545435223
399103514
286455036
672601056
112440928
28906651
285384887
437165549
672601056
672601056
672601056
418317887
1156656565
123389163
939398850
323019445
1040606872
181812742
631705944
1252601229
1270982340
2020261282
209344702
661730192
61860166
140819245
...
100000 100000 585767874 969488314
488773319
425485657
31451411
125354121
198709192
1297027050
915846188
865847922
865847922
495955788
430259012
38112058
655555207
269554140
655555207
655555207
865847922
655555207
330862299
257742484
881124869
278870276
623597474
530082948
1127525850
1204398738
1730577047
37072555
694048
31371749
9135760
33463298
1057194805
770383482
565637501
520029864
991846906
1371315075
97454049
300044161
1305967176
519456769
74989894
519456769
14719300
880742495
196109958
...
100000 100000 456616815 974410294
29694410
114810283
27479618
509651935
1377955711
1853568141
48591174
550185772
1377733875
3188073431
552494826
162623392
119629080
961540301
13098980
961540301
73386869
81666310
556381646
556381646
16557046
585391759
513708058
835481600
835481600
196542142
155864374
390537976
556381646
272417853
2018159187
36749272
123046338
556381646
292126506
292126506
292126506
438730662
15137105
292126506
138122700
231556955
119940584
118400300
851007817
551381231
41556221
...
35293 65394 377702722 965499399
239665146
662971035
63311606
197632809
411726834
310795966
240415864
2536670
5613
202237164
104440580
72640017
570409322
114470532
15706744
576574650
495809922
2202598461
230071751
131974040
921695668
2206028955
142512706
154685285
921695668
439798074
3278435837
206871252
611644713
150614106
24485187
3485714729
2523738028
3485714729
247403172
215325649
590457343
3485714729
1729280554
25140341
351532943
1729280554
252624780
1083769695
188669787
332592766
4313876...
96334 53956 282409557 989731155
264424564
831132059
72908436
368090942
227423644
311506102
194783295
206318770
56695549
211863709
56695549
214634804
297831496
365649379
247715382
293899239
635203088
137366134
24683564
1445257517
98960586
325902360
114187617
292648787
431543187
46443921
716759516
1430137540
1430137540
431543187
574046806
248546906
1126047236
2649836
759894053
706270467
223031249
759894053
316507989
119726966
1213065175
68123952
68123952
13792714
331483558
446844394
446844394
...
34281 4646 305421312 941787985
29743039
480172415
140640480
856939452
98074616
3035375
644241474
644241474
279358712
279358712
17376223
182274578
333883463
509541754
310952850
685788527
223266725
253520950
26530950
501280346
24526068
117438324
5300076
117438324
117438324
313193846
9007832
305109765
1728525074
28677313
28506441
363836046
28677313
810490379
630323845
303089169
211750693
20586044
1727991144
13537401
789731968
789731968
71774445
430486019
456241150
430486019
99829885
106821794
...
65410 84158 299309076 977599182
685446942
701897521
809216029
455806624
249004690
273488789
92895066
971005418
127013721
1249277917
147217558
139154621
821049631
1375797794
157402634
1198902618
1620738977
24571589
1481406668
1459610003
98342934
98342934
2238344471
190638960
971005418
347261832
804800693
561476144
804800693
804800693
1238964356
220043336
1238964356
350972540
54846606
444625629
186497410
435072732
105203033
609625024
435072732
609625024
67644091
609625024
367494
609625024
53480...
75424 85046 913047528 985636135
452443538
919821162
214758190
538602859
599290738
1380479354
91
30402955
313667506
46450616
430822033
1064551056
1589735072
885640637
53728070
4773196
1622583932
195603732
72827616
61957289
2299040254
75818259
642736943
507230783
241032135
373689191
1460529968
1253584727
65126128
24852939
137801751
318674322
60000306
318674322
1253584727
1253584727
318674322
579230242
982770772
398108613
694874412
6896765
30216757
10782747
694874412
450833972
654671372
6546713...
96011 69484 952656656 949837239
32539942
221637648
6685807
221637648
130499111
749816296
749816296
465720281
169837107
434579635
434579635
434579635
140347135
80756745
917825533
176391976
388876628
24154597
52986937
749816296
143381298
115970301
8487472
578697326
129033564
129033564
342075018
129033564
129033564
215260680
62781742
377703498
215260680
215260680
823964653
229054709
215260680
543738340
377703498
215260680
288700027
839891288
823964653
148164475
215260680
868684479
868684479
308...
69971 85577 806771998 978710230
129329933
68385719
540565769
56655160
1686967476
1541942367
503262086
1262717021
1917927442
89532045
331110012
285803527
214266325
622411716
501726093
418940034
501726093
119341174
514438082
288349614
574659327
312054790
2954052
1519871905
1519871905
148270297
285803527
2141292212
2644011758
952023412
211365450
101906015
952023412
81336979
1142528136
1124663438
623313617
328980988
73743051
734701813
8348685
792032598
167646751
1079261493
546235003
500693783
792...
53834 13558 705236852 914473856
227634968
75533466
692001026
372458402
4199748
372458402
1011605540
148163245
1082313030
1876361538
252764794
1082313030
213855976
20679522
213855976
39289356
227865875
2316098912
767062628
485927680
767062628
266488539
745842201
22734895
609911878
111182647
100331484
1753687996
167171744
485927680
3238342
65048581
675400107
102847960
79627523
99751245
75065723
446974685
69768843
234926533
1346413189
268814655
99751245
113231745
123381304
52895998
162960402
13...
92855 38088 901131679 905998083
55981088
160365879
198841463
16748732
1486157
940679842
90710681
324660985
166529288
535567417
151558952
218974486
331522181
760674601
760674601
332166026
246407870
79818860
5979574
536221952
50773637
79818860
519436559
331522181
127744454
98592365
83358985
275931666
732449614
405457829
1353659460
11058078
729708778
342000739
1162214
1162214
1162214
310867040
148135539
574118370
928983682
524479467
41969224
511281496
649137291
285473957
285473957
300759177
10...
48858 21838 231460178 954692031
370847937
463563365
367380589
341817660
106844349
631218936
1903253855
152677346
2122059099
527292097
3519900
13012943
84734828
1520810540
226192657
1978951417
1386685276
1682768810
9119707
1521671071
2776435178
33398758
1528015541
226489528
571104910
243497460
400780750
420100208
1043989628
1451057360
434594375
327308470
16499992
901126852
1453786073
268548975
901126852
327308470
118609516
447919118
555690825
1092279693
3750710219
3709774734
5866129199
53198154...
32475 84541 799815170 924502267
1476622863
620575616
620575616
78358606
438229787
864343294
12338748
1533951174
22149457
225899435
116727262
2363454966
23802028
126121524
47524507
360201478
58493311
58493311
363006653
1659243219
1898547080
111467637
151197193
17047098
481900146
523981654
667787844
193996944
906407106
5613772
561747384
355019510
755462348
45612357
552152736
467700213
133377364
667678683
523981654
1041743225
25175667
689741016
689741016
27813939
118945345
577631414
928133446
2...
56021 2857 942001819 920619100
220073701
727295171
403209389
57913378
533442531
590064935
219334821
934651827
1276456256
367157678
123336941
385398504
957948763
205735222
1299753192
456943243
366180607
435417349
607104570
56298134
193843556
300856292
173076391
636606525
313268237
677092026
172995482
412475584
20029368
32735150
467452356
210066452
210066452
210066452
136919226
1382145697
914945606
194540184
624906162
624906162
588138580
624906162
115762671
122995130
602863059
473714412
187136...
83662 39961 277703709 950449724
126252222
849892280
167866056
127364128
127364128
450004640
458130870
127364128
585334262
14475851
127364128
38910263
224539282
825993384
127364128
96652010
18604923
47266399
906040086
46391759
318595826
127364128
318595826
104497172
318595826
841837314
119474015
202909906
186683697
161340425
890054689
207667046
186683697
186683697
982483372
982483372
970578805
1509014350
169911047
399527384
148321924
260202217
1079582546
341511245
1704702615
206165042
30995511...
34134 37276 316383536 923096494
870247680
35828540
10693546
198698070
8284050
7996330
184167090
211946972
581355602
413509769
238825775
288191626
120306907
784563961
695255246
173030372
322425686
987458693
1047783977
7655871
695255246
1273433928
1574983481
151640495
227480251
224928429
227480251
42411840
232624919
224928429
189372927
224928429
194449043
906749416
258234237
3253928010
43269307
218951276
474442785
421639939
18679100
51715037
421639939
474442785
389762766
3176639
39619784
16759...
34736 88419 280789856 941687084
183818278
205903405
163799308
114262258
473958519
374203788
7412532
789150889
339153118
133450986
339153118
355870030
213438639
72371912
897178997
567245519
9226262
61273072
482571152
61273072
25069173
26289124
157227437
9064234
91919653
769517395
392022677
138881826
482961641
276680584
513335054
16319149
513335054
513335054
513335054
484706460
90429697
265064608
274690262
264818705
117287263
1131988503
329064115
1074580206
596447015
9064234
596447015
1233496
...
65839 45757 768591103 998790277
678126807
1032303763
443892850
2900162
359867860
909321721
282237191
32476392
909321721
909321721
909321721
395833688
909321721
111393833
1862877827
9657375
1841936689
200749704
112435038
736555479
1206250982
9356050
736555479
297818932
290875157
322725717
206227944
932542054
630169903
1206250982
1206250982
311006658
966119600
966119600
381477
326255604
85400943
3891748251
98327387
120588804
480537833
16411381
924545423
618680484
442365821
186723124
1570384675
...
92582 97744 474444887 902071104
615962324
871938501
46758368
771582484
23362941
483737060
645934514
360312782
143955012
37888632
87503654
24280201
380445709
558574575
29583810
56351351
20177884
3763903
20652
225045569
139842734
34921510
76167018
62940058
202172786
675330569
856736574
17852626
1348761106
1348761106
151879079
59349419
1479504273
675524105
30936840
246296399
1647188865
151010160
448224904
1647188865
44525093
2262297944
625076927
244983906
60408560
534966611
534966611
42959560
...
46031 42537 451207636 982647444
20264423
153434450
164995661
577060066
564247456
260347857
720604311
329587356
351913053
1412130719
962683528
7311281
1488665438
1419729339
46949459
1488665438
124051366
1488665438
8135269
1159282
239565871
229564151
18448464
1426435681
46900807
644262799
268629120
56343862
163559110
73270721
59427856
644262799
644262799
644262799
1426435681
644262799
644262799
1538104637
1427165695
416453692
579373083
40662989
149471664
873195434
11027753
606249189
1302016003
...
64909 20063 18579507 927481501
269516549
642864303
25032469
115372744
46740774
422004558
308450120
292670932
1225114614
308450120
586984082
308450120
831925309
782629281
195873104
1338669052
831925309
846888619
3593834
979073
4143263
71565650
339206737
869962395
272554744
394452983
80076701
219349564
236647603
95367812
189131938
15570719
5499337
813294149
96253960
178177637
339136655
64762330
2444408353
3311130099
181458657
2208828278
252557929
223375980
3447406493
163783624
181458657
32068...
90798 73851 189131066 992703032
82268803
823120145
22437793
79305058
141058630
454513528
50278331
286975891
71675090
1280701409
199601434
1224942235
145318910
145318910
175299998
413619613
33333661
356101636
15085552
88093049
660604153
69342898
9661704
41141377
825929676
1661301459
62218513
1993966592
281100568
532143708
514062254
81371299
73984632
849331146
42454875
812612262
236025988
376131279
981695252
129041988
2959698729
1655673084
81054581
1655673084
206317887
1529748115
828696819
587...
72580 68306 62781726 916636983
955231872
1345938897
37809236
1023745536
193327830
436196190
1390545560
981804553
1045391793
851876301
687402477
687402477
42268493
328559844
24034514
252182937
279807511
106057230
1039492777
7502068
511880431
2318324125
45502261
563695247
462332546
672588582
624384702
672588582
31449928
72203770
684180552
709466604
709466604
684180552
759166137
67435990
405911259
277606868
1076032126
759166137
21671606
1980595676
843191728
61650249
612025245
472605762
61202524...
1924 16436 604734001 960651460
224407039
21629501
51671061
618123933
66618374
349548646
1707651063
21984485
745056175
66017917
294185410
519710292
513436148
24316769
158658898
612865248
225546641
368908923
1127927911
209356404
583748672
607372677
718946905
722922265
8318377
299512174
918433001
50651876
324485498
415234261
17609483
82606475
184620922
5720471
1287572969
1080877827
86077625
1660997030
479967009
389354602
159084510
639166732
766227609
1940884570
521559131
1304554719
2296012179
...
41309 15973 780671431 932433911
75563798
403789976
6393139
254976448
805601247
6393139
254976448
175939840
1389369508
922395878
61632625
1686490793
23750495
625527070
434310777
113496156
460480347
261196051
2583744434
505830077
280326977
77318221
430992600
410525376
902799147
132626784
851717663
476352311
545543140
9677235
849072777
1496482050
150578755
55426222
815693999
1369752719
2326528906
7493896
50909437
808378541
313315600
808378541
91608487
2649723
683362929
42620542
818196368
648192...
100000 100000 1000000006 1
1
0
1
1
1
1
0
2
0
2
0
2
3
0
1
2
1
0
1
0
0
0
1
0
1
0
0
0
0
1
2
0
0
0
0
1
0
0
2
2
0
0
0
3
0
0
1
3
1
0
1
1
1
1
0
1
0
2
1
0
2
2
0
1
0
0
1
1
1
0
0
0
2
1
1
1
1
0
2
1
2
2
1
0
0
0
0
1
1
0
2
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
1
2
2
0
0
2
2
0
2
2
0
2
2
0
0
1
0
3
0
0
3
5
1
4
0
0
0
0
1
0
1
2
0
0
3
1
1
2
0
0
0
1
1
2
0
0
0
5
0
0
0
0
0
0
3
1
0
0
4
0
0
1
1
0
0...
100000 100000 1000000006 1000000000
882118768
227532426
982370702
89007427
485790874
634312928
49251089
627764763
80706419
1397244924
272967282
1397244924
1350824337
670835165
760200096
767082446
172014978
293563707
338455390
326300712
148951496
883219864
966553744
159024974
174268768
150366372
11996640
444249353
142162688
467511457
696083115
204657135
284818568
44568313
262909776
594416395
202008512
519417095
337769547
337769547
28098864
35755678
326275262
2694086723
569314771
221615842
16755104...
100000 100000 0 1000000000
10169893
16014934
817242366
909155662
909155662
64934185
63188268
294217675
78389509
71850126
71850126
100243750
898699956
133848650
1054178187
133848650
22516864
62515496
537279455
124507892
440708118
124507892
217708272
133848650
125674761
458997492
253085860
377119511
1595531354
377119511
455176528
621245765
1268020473
1268020473
1471497703
2437200935
612553989
244788470
1503454951
313339152
565198602
585007836
861854621
98979356
570051021
681628204
48341592...
#include <cstdio>
#include <cstring>
#include <numeric>
#include <cmath>
#include <algorithm>
#include <iostream>
#define R(a,b,c) for(register int a = (b); a <= (c); ++a)
#define nR(a,b,c) for(register int a = (b); a >= (c); --a)
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define MP make_pair
#ifdef QWQ
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#define D_e_Line cerr << "\n--------\n"
#define D_e(x) cerr << (#x) << " : " << x << endl
#define C_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define TIME() fprint(stderr, "TIME : %.3lfms\n", (double)clock() / (double)CLOCKS_PER_SEC)
#else
#endif
struct FastIO {
	template<typename ATP> inline FastIO & operator >> (ATP & x)  {
		x = 0; int f = 1; char c;
		for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
		while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();
		if(f == -1) x = -x;
		return *this;
	}
} io;
using namespace std;
template<typename ATP> inline ATP Max(ATP x, ATP y) {
	return x > y ? x : y;
}
template<typename ATP> inline ATP Min(ATP x, ATP y) {
	return x < y ? x : y;
}
template<typename ATP> inline ATP Abs(ATP x) {
	return x > 0 ? x : -x;
}
#include<set>
#include<vector>
const int MOD = 1e9 + 7;
const int N = 1e5 + 7;

struct nod {
	int l, r;
	mutable long long val;
	nod() {}
	nod(int _l, int _r = -1, long long _val = 0) : l(_l), r(_r), val(_val) {}
	bool operator < (const nod &rhs) const {
		return l < rhs.l;
	}
};

set<nod> S;

set<nod>::iterator Split(int pos) {
	set<nod>::iterator it = S.lower_bound(nod(pos));
	if(it != S.end() && it->l == pos) return it;
	--it;
	int r = it->r, l = it->l;
	long long val = it->val;
	S.erase(it);
	S.insert(nod(l, pos - 1, val));
	return S.insert(nod(pos, r, val)).first;
}
inline void Assign(int l, int r, long long val = 0) {
	set<nod>::iterator R = Split(r + 1), L = Split(l);
	S.erase(L, R);
	S.insert(nod(l, r, val));
}

inline void Add(int l, int r, long long val = 1) {
	set<nod>::iterator R = Split(r + 1), L = Split(l);
	for(; L != R; ++L) L->val += val;
}

inline long long Rank(int l, int r, int K) {
	vector<pair<long long, int> > V;
	set<nod>::iterator R = Split(r + 1), L = Split(l);
	V.clear();
	for(; L != R; ++L) V.push_back(MP(L->val, L->r - L->l + 1));
	sort(V.begin(), V.end());
	for(vector<pair<long long, int> >::iterator it = V.begin(); it != V.end(); ++it){
		K -= it->second;
		if(K <= 0) return it->first;
	}
	return -1ll;
}

inline long long Pow(long long a, int b, int &mod) {
	long long s = 1;
	a %= mod;
	while(b){
		if(b & 1) s = s * a % mod;
		a = a * a % mod, b >>= 1;
	}
	return s;
}
inline long long Sum(int l, int r, int ex, int mod) {
	set<nod>::iterator R = Split(r + 1), L = Split(l);
	long long sum = 0;
	for(; L != R; ++L){
		sum = (sum + 1ll * (L->r - L->l + 1) * Pow(L->val, ex, mod)) % mod;
	}
	return sum;
}

int n, m;
long long seed, vmax;

inline long long rnd() {
	long long ret = seed;
	seed = (seed * 7 + 13) % MOD;
	return ret;
}

long long a[N];

int main(){
	io >> n >> m >> seed >> vmax;
    R(i,1,n){
    	a[i] = (rnd() % vmax) + 1;
    	S.insert(nod(i, i, a[i]));
	}
	S.insert(nod(n + 1, n + 1, 0));
	
    R(i,1,m){
    	int opt = rnd() % 4 + 1, l = rnd() % n + 1, r = rnd() % n + 1;
        if(l > r) Swap(l, r);
        int x, y;
        if(opt == 3){
        	x = rnd() % (r - l + 1)  + 1;
		}
		else{
			x = rnd() % vmax + 1;
		}
		if(opt == 4){
			y = rnd() % vmax + 1;
		}
        if(opt == 1)
            Add(l, r, x);
        else if (opt == 2)
            Assign(l, r, x);
        else if (opt == 3)
            printf("%lld\n", Rank(l, r, x));
        else
            printf("%lld\n", Sum(l, r, x, y));
    }
    return 0;
}