We define that
g(x) = x^(x/2)
h1(x) = x / m1 * m1 + ( x + s1) % m1
h2(x) = x / m2 * m2 + ( x + s2) % m2
f(x) = g( h2( g( h1( g( x ) ) ) ) )
All above are integer arithmetic, and '^' is binary xor, for example, 8/3 = 2 , 5 ^ 12 = 9. m1, m2, s1, s2 are 4 positive integers less than 345678, and fixed in all cases. But they are not explicitly given, you should guess them from the sample. (0.3m1 < s1< m1, 0.3m2 < s2<m2)
What's more, your submission limit is 1KB!
Input
Each line is a case. Every case is an integer x,( 0≤ x< 232).
Output
Each case a line, please output f(x).
Sample Input
352395959
155843937
2777593999
1427455912
2158569277
3669327611
3395255191
3926365759
3767161069
422697681
469505916
2928120507
3616285626
181146713
2900895146
1463815256
895140294
130
1026379508
2410694193
1535643610
3991087302
3795179980
31325050
597546721
41206937
1955011783
1701383187
2899688875
1954290683
2269919034
713992939
490
4187068796
3354974155
2215039863
2102195735
2120167499
3158993997
4240059015
496762898
2944323975
2036300583
3125575704
3383312009
677527674
855397779
1779985933
3411822505
2560960233
382675114
2941620659
3208332403
2145593438
3311174596
892138963
1803227927
975272146
3869222993
4280044577
867742260
2594210001
1156172069
1327802527
3349237447
222943242
2356715146
3881315752
3215833551
374798522
2504478610
1541885536
1390934799
1936320380
3010932397
1019305655
2069986187
1333258051
3299226255
17757938
229716856
1565894054
3785372440
3883126158
3344329744
1919213181
800188002
1132833108
1573150614
908853823
302074986
1573619110
1275784841
2616233642
626079324
148534191
1415363253
958375734
1974424582
1753909769
1394084790
1511340019
1975653348
4236493566
2447776870
602730296
379323717
2541205948
111470844
1438184223
2959578397
3825458391
1923770929
3697464907
152704510
2899556130
1545148365
1792865941
1410379267
1651324869
2686728373
3549853265
1020193499
2727078786
3043379904
95282854
2186483497
2957080780
1771798176
982698968
268202141
471765631
4233652405
612391534
1241404135
3897370520
1976063202
218223921
1313886409
2962890492
756435503
532023863
3963586582
2305597552
4137892206
2850125756
4042945763
2373326964
1316282731
2337176810
4166872405
1712552066
2103570015
209428179
3434213308
2827924242
2149771936
2482041117
3555437872
3994502993
4056281258
276779980
2680610099
4047583248
2812776119
2921266659
1516345254
1526696341
998255241
2096301753
271010770
400674247
1290363806
1502366062
1510785438
4196155009
579
2911833428
1427561271
3084328693
670154131
2499950903
1542936759
2494585803
3229156524
2349223356
3524810600
1795156633
2509316000
2964893890
196862985
1061297141
666267144
1969377987
1170858538
1970863009
462166221
2225053391
3400098787
716
1525363795
2146765356
797114974
1827374704
1396960693
1623971635
4060951157
2186094207
3665194420
378603777
560464555
3808314174
2562179903
3191402843
1057201684
1095515513
2874473400
364970324
38104447
2597328630
3394262696
1811503311
2626534505
217848796
2321772812
2425753166
4026443045
371423843
4058819386
734824520
986990562
716238764
722
1868339834
571679220
625953277
2511211615
3027470401
3853627878
128350300
2311479706
2148171582
415517227
2130683661
204054801
2228645576
238
1086287284
1249501330
2818386337
1228188722
143558635
2334785475
1392120976
2591819799
1022571744
4139974148
1059969896
1511086691
1269220143
4196123820
2546513325
1006434973
1588672453
728839420
573367915
3405128454
4285055064
3125312574
1607758583
3527156149
3898608196
2652021696
1438284554
3863356393
1369598332
3925961051
514565364
1094352747
1091404024
3083731330
4130128305
1425506902
89240982
1146911584
1105403084
2491459186
1016077643
3132984590
1599520748
1251721485
1691960293
928322624
4063948922
906101373
2779332523
1932438201
1207119652
287308819
1602187925
1806614424
2234517228
3214808211
684391864
2971019841
3491814434
3519400875
3133984002
2813856353
2243265809
56
2479971907
452998219
2977867060
1682006767
1765434767
1573856099
1739374806
4134373895
1940727040
1542022595
338
1340301401
3632306802
113235442
905072635
82812595
1320136091
1537520773
1018884311
3685515706
3837965002
1300684701
675192015
438165515
536768253
1510150621
2231725622
2903870707
4017053470
3168379081
2414609654
3552794689
1160310582
3461479008
1199643816
3395672532
2103879657
2936491903
3764845071
506269130
4048364186
2805954765
3612036029
1398767491
958554122
3387570160
1705776367
3683177642
1481926757
3275685654
2336508304
3132637572
3326659116
3062669732
2146849985
1609409484
2891537971
2674471460
527316647
2098761943
88536508
2862982450
1172548842
3462031693
2359202569
2943310272
3149938118
1143934326
3004752417
3207400734
759437273
1353779847
3401987109
2906747496
2234536841
2741440383
465083359
2567672510
4176371345
3813649356
2417929123
1143923889
3623960998
613666856
1525424374
101664256
2229685852
1641364405
2550469874
4293811973
1665971239
3472357384
1876851327
1831964923
1728279270
1896441103
2207070819
2493950116
1908605521
4270327113
2141095314
328148881
1017627745
1716306295
353405392
1627926860
1683850232
2361427666
3784460985
3200733761
1577103802
818825068
3749890974
1212445431
4127325916
3793259632
965267112
3269088359
1341282117
579936391
1299191640
3233470407
1624427846
1548068947
3171227767
568350874
3886409174
3808924432
2910257970
3542676327
3284908925
2149365308
813251524
2638268269
3147995418
1845145138
936240752
736659263
3027736238
226086434
1008752446
1803234238
1375325750
580000482
1858958209
3694465986
4071316497
2757625107
2702389645
2419831131
4089406585
3804743110
116864377
3537255619
951210724
2245190444
3797438421
4107933007
3338313829
2938727542
3279576703
4149340704
576748506
4074780576
1678020562
1814381261
1498608975
2360964460
1009448619
2794311263
1006566500
1946360702
709699818
4040810832
3051119410
2611781893
238117854
711560547
1956457723
2148452786
2703184066
3488677695
3302546279
1450257103
3533801458
1046527842
4093113348
2100345952
1084316699
861580389
577999848
4063309876
3507508844
639779469
1424943496
157837673
4245306687
3820333524
2404495816
2336165936
2355718407
3198068515
1071476594
3272678769
1835203181
1481149968
1787333254
3942157917
886636058
1736686171
2493621352
2800816249
1660838920
27989031
2578672630
3162809268
2390351192
543771179
597203771
206978011
3261879617
1029723664
154173425
117322546
3303103298
2351941890
405643828
1836612871
3897580429
2759824726
314674128
2897241760
1457926562
4046932218
3534510903
4072559796
928239206
3822615599
2142275735
1235694564
2204421020
2493077389
1216975709
1160353706
2305177647
3081896938
3845876880
1977785511
318502134
1854144566
1037563520
2125303837
1801576016
2758827815
782388037
1789941403
4121374030
812364502
2480714676
272718977
431523279
2422840894
1008614997
2508955370
2183204523
2752187443
812358596
4177514432
1390050170
1568012560
3454651640
2411608404
2269957458
490081803
3211864751
67974621
2359622733
676331593
4075200501
2093585037
3305566547
1484965471
1217470893
1221408462
3878811345
405990665
4083651655
853588614
296077505
3051237647
2361433863
1596613077
3798902292
3838813196
152458132
850060549
960315688
