fork download
  1. //~ author : Sumit Prajapati
  2. #pragma GCC optimize("O3")
  3. #pragma GCC target ("avx2")
  4. #pragma GCC optimize("Ofast")
  5. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  6. #pragma GCC optimize("unroll-loops")
  7. #include <bits/stdc++.h>
  8. // #include <ext/pb_ds/assoc_container.hpp>
  9. // #include <ext/pb_ds/tree_policy.hpp>
  10.  
  11.  
  12. using namespace std;
  13. // using namespace __gnu_pbds;
  14.  
  15.  
  16. //---------------------Macros----------------------------------------------------------------------------------
  17. #define ull unsigned long long
  18. #define ll long long
  19. #define ld long double
  20. // #define int long long
  21. #define pii pair<int, int>
  22. #define pll pair<ll, ll>
  23. #define vi vector<int>
  24. #define pb push_back
  25. #define mk make_pair
  26. #define ff first
  27. #define ss second
  28. #define SZ(x) ((int)x.size())
  29. #define set_bits __builtin_popcountll
  30. #define all(a) a.begin(),a.end()
  31. #define trav(x,v) for(auto &x:v)
  32. #define rep(i,n) for(int i=0;i<n;i++)
  33. #define repe(i,n) for(int i=1;i<=n;i++)
  34. #define FOR(i,a,b) for(int i=a;i<=b;i++)
  35. #define curtime chrono::high_resolution_clock::now()
  36. #define timedif(start,end) chrono::duration_cast<chrono::nanoseconds>(end - start).count()
  37. #define myshuffle(a,n) FOR(i,1,n-1) swap(a[i], a[rand() % (i + 1)])
  38. #define shuffle(a) shuffle(a.begin(), a.end(), rng)
  39. #define mtrand(a,b) uniform_int_distribution<int>(a, b)(rng)
  40. #define myunique(v) sort( vec.begin(), vec.end() );vec.erase( unique( vec.begin(), vec.end() ), vec.end() )
  41. template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
  42. template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
  43. int gcd(int a, int b) {return a * b == 0 ? a ^ b : __gcd(a, b);}
  44. // template <typename T>
  45. // using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  46.  
  47. // ------------------------------------------------------------------------------------------------------------
  48.  
  49.  
  50. // -----------------------------Debugging----------------------------------------------------------------------
  51. template<class Fun> class y_combinator_result {
  52. Fun fun_;
  53. public:
  54. template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
  55. template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
  56. };
  57. template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
  58. template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
  59. template < typename T_container, typename T = typename enable_if < !is_same<T_container, string>::value, typename T_container::value_type >::type > ostream & operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
  60. void dbg_out() { cerr << endl; }
  61. template<typename TT, typename... UU> void dbg_out(TT H, UU... T) { cerr << ' ' << H; dbg_out(T...); }
  62. #ifndef ONLINE_JUDGE
  63. #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
  64. #else
  65. #define dbg(...)
  66. #endif
  67. // -----------------------------------------------------------------------------------------------------------
  68.  
  69.  
  70.  
  71. // ------------------------------Global Variables-------------------------------------------------------------
  72. mt19937 randGen(chrono::steady_clock::now().time_since_epoch().count());
  73. const int MD = 1e9 + 7;
  74. const int MDL = 998244353;
  75. const ll INF = 1e17;
  76. const int MX = 1e5 + 5;
  77. // -----------------------------------------------------------------------------------------------------------
  78.  
  79. // --------------------------------Let's Go!------------------------------------------------------------------
  80.  
  81.  
  82.  
  83. vector<int>G[MX];
  84. multiset<ll>st;
  85. map<ll, int>mp;
  86. const int B = 320;
  87. int timer = 0;
  88. int n, q;
  89. ll a[MX], ans[MX], flatten[MX];
  90. // mt19937_64 randGen(system_clock().now().time_since_epoch().count());
  91.  
  92. inline void raiseError(string errorCode) {
  93. cerr << "Error : " << errorCode << endl;
  94. exit(42);
  95. }
  96.  
  97. inline int64_t gilbertOrder(int x, int y, int pow, int rotate) {
  98. if (pow == 0) {
  99. return 0;
  100. }
  101. int hpow = 1 << (pow - 1);
  102. int seg = (x < hpow) ? (
  103. (y < hpow) ? 0 : 3
  104. ) : (
  105. (y < hpow) ? 1 : 2
  106. );
  107. seg = (seg + rotate) & 3;
  108. const int rotateDelta[4] = {3, 0, 0, 1};
  109. int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
  110. int nrot = (rotate + rotateDelta[seg]) & 3;
  111. int64_t subSquareSize = int64_t(1) << (2 * pow - 2);
  112. int64_t ans = seg * subSquareSize;
  113. int64_t add = gilbertOrder(nx, ny, pow - 1, nrot);
  114. ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
  115. return ans;
  116. }
  117. struct query {
  118. int idx, l, r;
  119. int64_t ord;
  120.  
  121. inline void calcOrder() {
  122. ord = gilbertOrder(l, r, 21, 0);
  123. }
  124. bool operator <(const query& other)const {
  125. return ord < other.ord;
  126. }
  127. } Q[MX];
  128. void dfs(int u, int par) {
  129.  
  130. Q[u].l = ++timer;
  131. Q[u].idx = u;
  132. flatten[timer] = a[u];
  133.  
  134. for (auto &c : G[u])
  135. if (c != par)
  136. dfs(c, u);
  137.  
  138. Q[u].r = timer;
  139. Q[u].calcOrder();
  140. }
  141.  
  142.  
  143.  
  144. void add_element(ll x) {
  145.  
  146. x = flatten[x];
  147. auto itr = st.upper_bound(x);
  148. auto itl = itr;
  149. if (itl != st.begin() && itr != st.end()) {
  150. itl--;
  151. ll val = (*itl) ^ (*itr);
  152. auto it = mp.find(val);
  153. assert(it != mp.end());
  154. it->ss--;
  155. if (it->ss == 0)
  156. mp.erase(it);
  157.  
  158. mp[(*itl)^x]++;
  159. mp[x ^ (*itr)]++;
  160. }
  161. else if (itl != st.begin()) {
  162. itl--;
  163. mp[(*itl)^x]++;
  164. }
  165. else if (itr != st.end()) {
  166. mp[x ^ (*itr)]++;
  167.  
  168. }
  169. st.insert(x);
  170. }
  171. void remove_element(ll x) {
  172. x = flatten[x];
  173.  
  174. auto it = st.lower_bound(x);
  175. assert(it != st.end());
  176. auto itl = it;
  177. auto itr = it;
  178. itr++;
  179. if (itl != st.begin() && itr != st.end()) {
  180. itl--;
  181. ll val = (*itl) ^ (*itr);
  182. mp[val]++;
  183. ll v1 = (*itl)^x;
  184. ll v2 = x ^ (*itr);
  185.  
  186. auto it1 = mp.find(v1);
  187. auto it2 = mp.find(v2);
  188. assert(it1 != mp.end());
  189. assert(it2 != mp.end());
  190. it1->ss--;
  191. it2->ss--;
  192. if (it1->ss == 0)
  193. mp.erase(it1);
  194. if (it2->ss == 0)
  195. mp.erase(it2);
  196. }
  197. else if (itl != st.begin()) {
  198. itl--;
  199. ll v1 = (*itl)^x;
  200. auto it1 = mp.find(v1);
  201. assert(it1 != mp.end());
  202. it1->ss--;
  203. if (it1->ss == 0)
  204. mp.erase(it1);
  205. }
  206. else if (itr != st.end()) {
  207. ll v2 = x ^ (*itr);
  208.  
  209. auto it2 = mp.find(v2);
  210. assert(it2 != mp.end());
  211. it2->ss--;
  212.  
  213. if (it2->ss == 0)
  214. mp.erase(it2);
  215.  
  216. }
  217. st.erase(it);
  218.  
  219. }
  220. void MO_S() {
  221.  
  222. for (int L = 1, R = 0, i = 1; i <= q; i++) {
  223. while (R < Q[i].r)
  224. add_element(++R);
  225. while (L > Q[i].l)
  226. add_element(--L);
  227. while (R > Q[i].r)
  228. remove_element(R--);
  229. while (L < Q[i].l)
  230. remove_element(L++);
  231. if (SZ(mp)) {
  232. ans[Q[i].idx] = mp.begin()->first;
  233. }
  234. }
  235. }
  236.  
  237.  
  238. struct Testcase {
  239.  
  240.  
  241. void solve() {
  242.  
  243. cin >> n;
  244. q = n;
  245. timer = 0;
  246. repe(i, n)
  247. G[i].clear(), ans[i] = -1;
  248.  
  249. st.clear();
  250. mp.clear();
  251. repe(i, n - 1) {
  252. int x, y;
  253. cin >> x >> y;
  254. G[x].pb(y);
  255. G[y].pb(x);
  256. }
  257. repe(i, n) {
  258. cin >> a[i];
  259. }
  260. dfs(1, -1);
  261.  
  262.  
  263. sort(Q + 1, Q + q + 1);
  264.  
  265. MO_S();
  266. repe(i, q)
  267. cout << ans[i] << " ";
  268. cout << "\n";
  269.  
  270. }
  271.  
  272. };
  273.  
  274. int32_t main() {
  275. ios_base::sync_with_stdio(false);
  276. cin.tie(NULL);
  277.  
  278. auto time0 = curtime;
  279. int t = 1;
  280. cin >> t;
  281. repe(tt, t) {
  282. // cout<<"Case #"<<tt<<": ";
  283. Testcase T;
  284. T.solve();
  285. }
  286.  
  287. cerr << "Execution Time: " << timedif(time0, curtime) * 1e-9 << " sec\n";
  288. return 0;
  289.  
  290. }
Success #stdin #stdout #stderr 0.01s 8988KB
stdin
1
1000
44 137
305 467
19 515
278 836
71 581
216 34
527 667
623 283
21 595
796 368
720 838
253 631
912 956
924 531
145 441
382 205
950 834
498 63
783 734
820 426
877 435
944 958
749 361
131 210
889 272
538 726
593 404
189 802
688 700
248 759
995 29
122 575
445 358
702 49
456 241
561 945
802 66
824 389
489 967
438 573
881 990
315 815
79 606
57 577
472 868
349 329
111 34
169 635
566 716
868 133
979 176
927 546
528 672
137 914
625 662
90 622
687 738
699 46
238 356
563 159
735 590
211 158
890 170
390 994
257 416
181 109
602 413
366 376
196 660
228 99
337 324
65 934
847 432
647 576
993 31
210 555
625 394
454 840
798 311
884 885
349 818
413 611
29 11
97 246
872 490
953 509
701 705
768 451
666 549
34 849
319 68
838 557
862 33
677 550
464 306
228 192
24 109
827 773
375 655
622 404
715 846
701 277
132 184
100 853
287 514
201 432
606 132
353 579
216 677
840 394
447 932
66 754
838 563
411 318
95 598
742 601
646 35
97 915
532 179
693 606
978 403
74 30
582 26
206 850
247 256
969 324
474 695
803 76
838 926
304 79
880 579
251 102
422 602
570 30
323 232
259 996
519 268
352 320
745 206
497 145
845 645
531 838
481 40
570 801
434 951
634 602
217 979
31 659
290 266
546 711
329 392
142 721
737 894
7 276
370 465
686 115
559 802
682 827
25 19
849 240
633 130
632 228
15 676
89 917
517 101
111 207
145 671
8 890
825 849
587 820
581 435
394 864
318 678
266 986
576 882
690 348
645 569
347 549
292 653
24 819
921 461
880 142
617 824
554 496
254 139
670 601
718 306
359 532
833 526
752 228
154 868
652 6
542 99
478 924
341 390
854 684
122 531
129 152
570 38
558 668
780 880
203 182
597 146
674 983
5 332
644 403
383 784
250 387
956 602
25 890
194 529
775 53
58 120
625 985
291 958
684 911
782 762
478 658
572 991
989 330
137 880
512 406
365 751
720 908
814 999
645 542
188 454
408 206
35 344
536 965
853 282
147 780
889 597
53 456
27 66
962 6
910 120
623 25
70 43
710 140
106 397
287 68
466 182
63 795
274 684
429 769
605 483
60 1
254 665
481 726
273 460
896 695
520 354
605 22
939 763
425 685
300 295
778 724
818 760
828 430
773 324
79 25
486 940
340 88
512 579
480 570
280 436
119 992
206 567
719 298
435 146
931 734
917 540
145 118
512 10
479 395
542 196
311 458
1 200
313 664
786 422
265 161
423 922
268 793
372 133
460 896
140 25
704 268
64 687
777 190
506 961
383 489
121 709
781 118
330 241
771 588
605 289
225 41
587 773
231 666
797 969
297 516
569 844
921 369
821 16
442 644
866 930
976 679
628 562
956 6
730 243
780 801
728 692
865 798
869 736
197 531
377 841
218 551
39 324
932 517
218 208
548 108
45 530
671 663
624 619
4 229
118 334
824 766
500 895
398 740
444 271
145 408
435 527
384 737
872 652
899 427
329 3
186 577
839 759
83 291
213 255
503 586
648 210
564 456
600 739
194 294
720 301
700 649
582 415
397 482
250 42
473 961
250 673
782 33
812 977
712 73
672 103
696 989
47 68
803 302
52 141
873 202
438 496
550 381
615 79
126 250
259 332
807 31
110 568
788 725
702 386
965 158
981 410
609 459
120 111
450 67
613 813
876 100
739 736
416 701
46 111
312 692
449 584
851 666
790 21
940 144
1000 511
553 638
342 568
244 412
469 481
626 645
238 994
693 131
262 493
603 527
488 796
255 340
693 463
872 252
481 295
348 887
105 198
265 160
596 586
384 801
222 376
604 648
531 530
98 495
234 103
718 87
896 134
586 764
858 733
689 788
396 948
477 493
949 100
999 471
54 397
270 720
171 837
131 251
980 331
704 73
193 209
77 979
355 977
420 6
542 594
918 584
792 986
668 511
202 533
694 296
494 835
513 313
795 960
497 114
241 896
813 433
6 138
612 844
884 98
105 765
536 974
29 693
780 950
681 104
615 560
25 625
359 851
34 175
481 845
554 163
55 513
985 86
775 405
354 120
3 817
966 742
314 146
322 743
770 358
858 147
707 591
40 566
224 563
220 442
605 907
935 645
378 474
833 931
321 651
62 408
333 262
852 459
443 432
731 344
515 886
21 322
690 626
930 984
287 219
489 892
577 763
806 300
643 677
860 707
492 344
764 368
146 120
472 218
646 265
456 722
856 363
946 893
936 367
725 959
897 385
474 881
930 416
440 646
741 602
568 558
156 941
207 645
25 729
607 580
453 134
688 266
218 800
756 654
275 979
401 415
838 880
645 801
167 131
176 393
423 879
266 977
867 272
62 110
734 382
725 157
93 574
405 942
842 740
78 695
11 608
148 515
444 963
843 671
740 423
657 700
987 236
456 599
434 801
355 409
748 628
110 642
278 355
660 338
287 736
438 524
251 928
908 943
962 669
100 801
214 858
324 227
23 552
849 310
701 470
796 296
988 789
645 577
567 450
781 155
4 924
849 371
646 400
118 94
585 20
750 234
227 653
972 204
487 135
909 187
173 221
250 791
471 547
878 277
357 528
16 693
365 172
810 698
933 693
183 943
452 925
903 875
383 99
816 631
204 683
973 518
671 445
631 756
506 947
869 685
360 519
165 87
196 627
41 854
32 574
705 461
129 110
76 124
423 965
7 677
59 178
940 373
366 291
592 979
524 713
704 822
969 774
614 177
829 710
267 367
75 412
499 718
305 166
577 322
126 631
513 525
895 430
997 570
773 736
920 129
92 450
910 368
38 438
521 774
536 535
472 346
41 895
360 501
562 145
290 82
716 65
61 352
28 41
845 848
929 812
19 937
975 689
777 804
534 322
150 27
948 513
742 264
645 609
480 388
327 320
271 142
666 6
323 838
967 343
731 693
779 595
164 578
77 997
156 986
68 545
245 571
602 855
29 328
517 344
961 958
855 468
805 583
380 921
946 144
629 883
53 909
368 964
104 353
768 456
598 885
353 331
435 128
349 141
776 284
619 437
956 17
826 840
365 46
946 25
258 304
109 364
504 973
765 890
475 19
459 723
902 170
901 692
300 379
216 418
457 627
325 18
292 93
96 949
605 446
884 912
281 618
987 98
689 113
352 487
730 36
686 441
809 132
1 622
412 344
293 632
269 958
651 811
185 573
53 362
100 411
77 261
983 178
339 456
706 757
693 472
100 773
421 747
411 735
753 644
383 620
994 51
661 399
285 66
976 704
117 17
749 648
744 647
906 6
147 767
207 423
235 481
697 809
626 919
239 114
802 923
250 84
958 945
225 375
212 345
717 672
630 628
910 174
481 802
562 317
940 50
991 225
870 346
639 186
762 553
456 557
552 647
912 215
112 254
168 267
761 170
896 399
20 6
927 985
625 543
610 716
17 199
577 234
645 442
859 157
985 493
448 99
656 563
259 351
242 87
742 544
374 794
116 874
707 51
162 438
763 455
180 557
686 491
596 757
256 912
371 428
898 837
690 529
916 801
680 320
968 885
970 123
448 2
74 195
648 871
727 700
629 962
656 336
797 13
952 665
392 260
469 785
675 493
72 331
41 16
79 992
228 485
957 998
541 577
465 994
636 44
863 851
805 310
307 471
255 267
114 164
780 9
864 479
303 460
594 857
838 931
973 80
402 376
502 659
729 471
907 832
651 750
170 116
26 549
904 570
432 136
137 742
641 51
432 931
43 66
808 383
505 9
193 214
838 306
25 367
619 718
739 537
142 897
504 884
18 837
628 502
535 607
645 408
89 764
560 665
652 190
141 778
606 386
719 922
553 470
384 279
614 314
376 233
472 466
383 316
449 565
888 354
153 168
524 556
323 772
345 940
245 813
971 534
37 976
729 970
118 622
616 802
407 738
776 866
349 315
683 484
626 417
529 795
280 267
326 996
166 216
208 732
149 193
226 132
118 738
69 582
29 391
704 747
708 196
703 317
137 688
713 830
846 190
637 489
323 299
91 902
178 442
55 469
775 831
263 389
302 652
462 382
633 796
523 419
671 789
27 246
602 645
597 861
746 771
508 48
981 271
914 539
523 310
16 588
487 913
729 509
367 320
584 630
823 405
957 519
789 259
647 997
384 221
728 153
53 85
466 494
107 435
507 422
746 202
413 237
788 631
755 885
185 309
965 841
891 957
522 277
191 499
982 788
961 875
497 414
788 470
240 799
726 108
546 650
690 813
955 197
249 608
605 99
424 11
286 668
303 14
949 143
794 427
403 350
475 476
481 787
121 509
367 845
750 798
628 281
297 509
617 56
127 563
316 769
397 508
89 12
919 230
79 51
308 506
232 691
223 437
837 652
787 439
589 726
824 6
243 579
303 905
676 6
925 884
510 647
335 781
849 169
100 268
431 909
114 151
566 698
743 621
944 788
771 427
624 938
81 157
882 363
854 288
640 569
24 234
566 683
985 397
349 487
758 383
470 888
900 809
954 469
125 221
759 153
714 713
448705428988861 419387191197160 205853548581561 815646997215561 370924437713490 37684839204181 492714440404168 24325505702649 573973716344705 284903016112905 201911046883236 252715505656052 828857765116284 162219000617040 965242798091080 480426589890506 113412371571568 951246693685356 550740162846573 125953041054245 743818146145955 513991520861869 548717203756578 853270576763015 266351629364897 124221591086551 551005573982012 48350147342987 146648717810698 21492999794810 506644521567128 439489435169837 782553794872799 491919871503512 527851213229073 979983072730600 966535449466789 46729037657378 390343698987859 526238123605848 502841570331456 234451184424229 901124386701696 206893934162535 270946063461248 111119723679167 730112909833168 363726162796967 360689086558521 738286581687046 696932806104338 897713123442935 704033583882202 789482157459173 377580899214533 676194343421006 545609458397326 649201960534768 885095098579122 686337060594450 555099013075761 191166603219928 153232716219277 134024227442052 243105882957792 573092692618085 403236221825425 487753011973674 196846138196011 909415943106404 457622436705659 253793464466368 193954593630610 408343225626163 710910121843848 393638960257262 20600682201863 883963403922531 683591165090897 86117237011008 341086202328538 66361208729228 14879040849388 923592510437560 932457498436921 747854782839229 202887815630081 823551331311772 13440670265955 321793531857588 324815575325516 656691862942625 433101575031185 480204297999656 418613607043535 982898239645514 486962626694486 277233670002271 732216835755743 331862765087994 537170163845171 501469804697993 619244328529255 692543802811186 265036597326286 726496891084691 859719159744317 493210678779297 892612457579757 625367099661330 758240173728212 93702760929835 238233502751941 799801108595842 447279053533859 68440141818755 35226743470050 364786544566873 92666701981258 348630642713303 730344943125617 748284761747043 367295435092334 872365474115895 385460489940404 975762938107458 936352465924101 741777976328756 436404583965942 577894822625634 955409170803456 47325880398810 787376908288793 626313980974667 49964968745761 951001321648587 549746413909288 956406291795101 310120382058063 637945195527209 593747470562360 483199420874342 659133671171015 767229825928288 287937185146989 708349778746531 398965182623951 459249181456792 886413198296367 942231217575 514600520538614 975904036465630 535648870243667 776911492055820 58321032030326 637046516361323 23090242417039 341051594051039 453882049529085 841711513586464 816704576385190 610252060678251 399026561732820 122961555015737 911106003741769 361201345563566 814970051506327 938835554344542 754781355200255 318585743052952 828064659046755 237277949899608 351496265442812 568449694294994 329663585514750 266090632400520 322683932611470 672331803591330 251822090972909 369626248825560 46263961128802 411860523247795 879955598409892 600830289194410 843929773634694 379788674281392 799968042072093 656979176340793 647833828567402 134845729376021 685991448810455 403938773113994 615355834419393 909562290511459 469790622252473 746228607264867 252920218828704 764341637956699 946439771822631 49523829482750 643123659184687 535702873071542 121828713037837 749094344371036 258707064643252 629051884019361 418198937314296 333291369626468 59689877801637 481265692905883 167063988938994 236767640399275 421731971674705 725052784338781 720862344708846 598186252376605 354521601617723 607986973780372 131044080453999 99787366638764 683723912266532 467706003619421 80756655502781 732270040835988 274551206193326 481947184649178 922335861040051 215635150637899 565957383555363 7052129894733 554225951638743 993555326590635 800133720934205 311622397919962 921107808624683 573575193237415 582832459123094 34566720350994 504238365950233 895215245531539 233675162267411 24103672276839 926731779327512 915003871514148 926433085607143 414657476795356 638457087212651 932849830189243 639848665628605 980759035403768 432256473745757 393761374956258 753847788267861 237463496138521 661229641413485 633174658771738 35200333792313 567065999048012 348663807697390 521379500706728 131950983106493 687158784619940 516309032652818 794997867611721 436572047704302 918988863798502 899162516665788 313125740067302 582144508110975 100661059820722 331607949657023 274646320919271 625516680430345 348696982489655 658914699748697 798060509410478 207910547646192 4876296087320 31404125964209 159495852938989 738327170896877 882548524648061 702519426833183 966799347788332 923288229907097 928870192847263 405872339289423 113779306282670 958256580201737 610122887333110 3030281271330 582087378926715 124303984870166 965863723051868 732980250606296 274059475739942 139786608494628 307187656555236 508485900058342 272034645175256 825140506620223 338563988638428 901216211401978 369192419522966 602503782960763 806722218007426 60199239933093 6605008436684 703239148140478 902793131532862 243827543075488 327974169683467 977565269337455 912449810022401 672715146047126 62833774041020 9522083028058 362512247083332 431122264231031 649265686258221 857282304767034 713094510813245 417788948050740 578531778913002 848675512446908 587752313444928 392171575488453 216127696656250 901768230423370 615080080702790 91578653019598 605645002580698 176705264042450 59176111829418 722051715380350 378960069622660 460437425822036 413337751913824 812644149261432 664593225340969 456237855572514 446156166879658 279493939768060 547284352040896 70281112964264 728888911580726 919869169451350 916265405909484 404597000967948 105013321620883 150660785013756 531314954818305 840191992897605 525155676371071 37870682675730 98308800395159 573772352648444 245834033639377 757420653250403 463905348995004 541668214534935 487704998825876 763113451817161 669101112046848 642827504650019 474213420276750 665133514013846 976802768477383 274095875556189 920281229889311 126962206035259 315162995585031 239133307634212 335489719413728 840957658606820 687828482138227 858146925086806 148557667176040 858207258459541 14783211206461 553166925280854 277505092577679 217554972707435 480574542189456 236232195752218 469438747647312 652234654716003 99593909949619 326916909056062 683410390676510 39363533992141 533929320240213 509223286129187 264887701838364 692083953851510 876465451873768 172088567663234 627231622886152 879757061841766 227340182664935 739565920297915 314502148460702 880528543859146 337892015805175 107134981528749 447645774933983 26534707616917 390041109693080 534879538771620 373237469035300 911380306285018 343518088596250 375811703523730 203599817093728 427492885507998 750527386665291 868465362100720 23655167015019 762417278039421 855048525826852 335927362962379 111226483334126 973881855441529 170975378094384 304467651404430 843571291116313 353618445144379 219429186574627 900621652336125 483146545204110 73939916648123 367104822140162 795860155952233 394740088109799 942050686690795 112752106667026 390402764230181 138184045365110 217108708957919 172771642089252 163632137139878 843972815861984 347848304823837 784690705939664 444333570553404 76377334237096 540236720415759 469345167643208 756213132865377 107917136761312 126626649989662 854071440228583 648780371154542 331639021984509 752368631765708 358427224035353 887396641897442 202709420669549 834878862645521 458464019077581 645980894929065 84325911879538 525200556008099 803885557451642 653099434511561 992260702512664 7018052151796 669334701279691 516506502395004 295678463731944 327739908851344 334796815895881 992987663701079 90017147607668 52639129842957 689926328802612 825426639114513 155728033440755 513961817203523 256950213196177 287271659516869 801307837314453 907206535699050 231197701913128 129244756139058 349919678320078 60206022798694 155905633392488 969869113934334 111107991232809 746311026548594 490397518321862 719973662350834 653271177689708 316226967735659 172360275567996 309212477306364 48896768083058 391198110385535 591889841273887 121102946626102 563294328501031 513916163180022 482502031690544 305863712228729 431350188017886 511202264028439 622469731883954 159983637568049 347530570075128 463334322341706 59083066360928 118934994186722 665993489479450 946298656961508 40843698608237 193743997158370 961522866680929 707716070367091 95220237739305 481263766046669 295041110158229 880943647376647 187420460649167 240915780360978 509360369801486 832833839541984 808462480708713 181387089588605 809127983221169 193384581012991 748830049619570 247748789813932 648801381082392 23267269880426 769522714781379 841048296476323 744391347132452 309547838642027 841566353232268 360189930664158 74145260263031 714481194781937 657121360482276 812475036639528 885367570220233 383586602422356 412443906908336 628130891664272 556014395325989 228730649044418 66255795785984 349512251783282 968658784157300 737759821706838 127079576338057 952798119617901 500724677377719 758732940149570 355280721821956 55424399432425 194234282511558 465865215183123 120715674543389 588589898266276 634534681987041 142102871562833 951413011987385 830127824127571 371050007354593 600184136216094 692447513169821 427059081088308 475522287091867 856342815948162 739882129574862 357085642808931 90893266441923 435695698342466 747813620223079 921330422094551 89563457008847 373491812953368 590539229074101 716182192283580 689002904266157 376396287661062 378776444723066 196657410614180 810763440286266 192852206093852 586813459508501 756145769302530 835840296073223 650812918945114 886566329758276 255798313278061 245703602769920 141158872753470 8332921895990 65378521296385 886479659668495 497588579653268 963850813337471 920194429168251 296455690154873 524024880016929 257941653029837 354576294210868 551253320039079 632006856099251 631747103872851 983321508588734 591533569568590 586599443146595 646270544843765 155773374433344 319419819551377 660793812148482 252062452225976 362957558012755 351076202216140 600259595071805 180618514363645 93387881503223 459552418456722 201244379894594 301201260754915 151879533092942 943673098536215 107595402134910 569836840699169 640971326520507 76024455907599 649752448303321 548436841867268 870934200706363 426062273922601 275846182419533 428277564912494 893618550607197 213294265230953 135536666033615 794015328374353 147067976208720 384478178278751 215194947299398 746294099358755 29496071312820 145438632826500 498110535233784 289290184547276 9056283435021 398439543530708 822499284066481 13680151479624 208658167851013 334524741637816 384629497645588 474725874436694 692027945017412 824090218399016 43422296579319 190354900734900 623540569468081 100985487883506 962724958054720 991463613626800 835921517084827 290967011184478 842390883699563 409732342291583 370649577190365 855014745193558 675792108939832 542911726667437 820314360562781 735398578128196 723055706446136 639583317646952 999721956323499 85042343860451 870981090010523 922188019422254 374560998019562 601426110910309 976076114000340 178653786507465 115324016946594 743585634444082 802738457989284 84390372618877 876632600218115 220361353084463 124305163016631 159101125860339 416721843271755 728747967637220 623436052872382 69074177300829 937186818087575 684122488853699 235044956314568 466555485664353 672904371167451 200522463323850 742449428165458 22209572607925 121388479638916 911704244610353 409322902838911 413726314634588 423677523052995 881252907181193 465325815566238 428192801036348 284338263689531 90373152463516 79596524401960 144198934860458 743746972443752 492531639926499 742018580033097 187771419752926 813287064103095 578704959565686 833798366504053 910711190813892 724542741443523 296316932703098 388824350372522 468492969318716 955200530269750 460827715599106 912566196416641 442396814516984 689006956986378 936830243346695 446834096451413 92887943625881 777083818224236 173903676886731 755473257717071 184538124854244 411697138608374 464871917870953 348656311284343 885683974389936 819458507219035 439444574427705 317290769547547 365140048328797 458118482150050 426280311329603 680476632211190 121177317773325 942575807610574 729287571004111 152178190468745 921112124359982 381519022356713 224310135577135 886808785328323 458734578865325 826786867856155 839871645247460 418873027974860 781596931425363 57007066152248 539181432898133 422597554724923 145765136094416 226063949400297 344283283408777 780695816593205 783561307876002 549822322757534 512685265817459 646693304408831 318420013816824 67835618896840 477093833552283 998028247551098 570339183280174 368609525218820 35978344467520 221111390127245 532259926080817 975332143657887 820360622733248 655463291392138 736117081663690 767229430268118 165348632155946 515015260914451 179971175800070 844551486787480 481520782144101 11886719364166 297203179159245 381251928606892 658558204782999 689259568782685 591798549259772 590219210024130 604078291491 38165448163245 778923940426188 395795763997025 438570574263030 868436111754075 854929106276286 556753631379122 194977994069788 53476339095697 77063659063556 461681881546479 169896849895898 166760750907452 883815683834845 897407373627606 901014371647983 259644680730345 830258966883844 577022767693144 608813509600172 954613937605558 665777948969449 325555738431723 210580801696514 917613288501930 523705164915097 4900820205879 441855500668410 173853556017802 168731333047911 738336198921101 541577954991547 766142450468195 687574711139746 638926199864654 711722856508158 825988690118583 597343055071795 148799579133075 805931761168183 846330187671544 524810332835010 570241820686850 335626243507196 441309631711047 697441633766344 371362203292511 534570517800248 928483624585840 168905541011188 289756950610432 654465627024003 817220324569153 421015051577954 568317442301680 137965708426505 836691788830300 560094968773807 860380585542338 285458007551141 442067659419928 742751675190371 135863536341797 604771150019104 828343576579677 226648980253954 459335376773680 295400901736588 37899438368732 522093839507996 831683190984153 789903972981088 292907970949506 472850354183215 659806577255598 744938035573280 759885418941729 430341274381045 905086384333889 538333771423189 95907321771465 383086941422303 958701660094761 500496073102360 377877271635052 50634385014126 543946394319825 5313318896588 737843300138546 964030641724817 715038647767296 470965309158814 273381356728900 748494044938362 368523184245824 204662259808500 938943385975161 233186106810210 782045047068843 479620033176050 785540619857442 842433153946783 319192017694595 582445174099316 95118606407344 324344453237643 426559626417832 92329798009965 289830927811781 169600284829156 287766256120351 914148022866508 904651012566084 552393207664430 851207872575058 694064711431642 769647695809610 54326904580776 160341220385162 636159950264353 694988123400475 983149903844543 703911701700498 13526496316012 475391095246562 817012718130225 178547152903796 293827694696055 11841403832046 80820337458393 862809989129419 874440726454905 5845922024280 680578231705194 988998100691943 410487512516561 344432140518652 102131848798596 998701538028024 610991975468563 619946001572895 700549569044429 402017222032998 335821713932620 277368293557501 605281768091660 100409457098909 286317043009700 748156341568213 832532562776342 112645915922098 476765041807765 668019752746359 75647188291475 350946326595872 24486008584007 151030417295501 189333504979582 203078715150222 94061711298582 337570801842971 558502326614894 350034000927528 815447531073075 84876614211057 99531642603808 199840749978374 806061486708034 22913392850707 860315464804287 792158239316544 75166608716474 10759189814868 699809566522361 211890851549959 221936831380777 301045983642171 403074652921824 63391428862682 597755473776581 666975705730341 501416573330625 234812509555705 334274165124082 702520528154963 914087239117888 665463655847597 296474339636402 559506385804926 292077144713002 818699392950742 826621236781230 478533733100091 755608721946548 
stdout
412830902 -1 308811154844758 254466700472426 -1 122415231500 868390648289382 -1 875386721524472 -1 48530355191444 -1 -1 -1 -1 1135727770254 78255337575570 108829290772432 32408597578424 837624175486361 4136932822949 -1 -1 39410650633322 1113942604 36900375449880 87691050068586 -1 33947926291770 237664024433546 543692582992949 -1 768284387227862 4351890330726 29969777179526 -1 -1 5761372603639 -1 12716534442698 12332168871630 -1 9391898767076 368232650742371 -1 140355058645917 -1 -1 -1 -1 22358287278348 -1 19348729751336 -1 110170834538631 -1 -1 -1 -1 -1 -1 25126765629543 183781380081663 -1 516935428469143 9391898767076 -1 56631835378269 -1 -1 -1 -1 501577968481486 237664024433546 -1 703044745931225 30191102958931 -1 232347887695 -1 -1 -1 -1 -1 -1 -1 190673244187238 -1 257210820186775 -1 -1 -1 6948353375676 -1 -1 -1 208333145196947 95887353617026 1078205842703 1220250034523 -1 -1 64754273606043 555118136071065 640081189483925 -1 -1 201825273871633 364319366640109 25126765629543 36960134779 -1 -1 33659148376303 -1 337088755471119 -1 412830902 -1 36960134779 833809311558133 459979290285025 -1 -1 -1 5599668601065 -1 -1 134751593688024 -1 9270844572799 31855715455274 1076142216426270 131593064005669 -1 -1 1310645787948 -1 -1 414540032383256 330358227006671 24656181252637 -1 15579134209935 412830902 1221515780921 24383266825731 -1 -1 -1 -1 -1 111467598457419 -1 -1 492713869411212 320195388179541 459453567214893 -1 -1 -1 -1 -1 67618003558138 -1 368202066715226 -1 6260610680549 246885412556326 7333706435540 -1 -1 -1 -1 -1 348685922438315 -1 49876932707556 -1 -1 -1 308244249929918 -1 -1 140854153085752 461292384162813 -1 -1 -1 91506019778560 -1 -1 292030230351342 93799219410239 -1 179447129523447 649219391454581 -1 -1 -1 -1 78045235084678 -1 830999306904188 -1 27290397350247 36960134779 146475375223384 -1 26477560688134 -1 -1 -1 207563694845852 -1 4351890330726 -1 36758215067049 -1 -1 106910755407944 -1 -1 -1 12332168871630 -1 6948353375676 4955941084964 -1 -1 -1 384503674342927 -1 4097912562877 -1 -1 -1 77075272064133 -1 885098758698453 1138991736042 -1 54501397355504 -1 399445930074873 139334961651481 -1 -1 -1 5599668601065 71704546300116 -1 -1 143761557554482 5579950648132 135730252666737 -1 -1 53163254544538 -1 -1 791931726378102 -1 -1 29969777179526 32206546581336 5579950648132 9170054063236 -1 -1 81270120881034 399968589038591 -1 -1 -1 -1 476369566223717 172737323487615 -1 272144712575743 1052247800625532 -1 -1 -1 -1 -1 56631835378269 -1 -1 587953671629434 6782294614611 6948353375676 -1 -1 272569995055611 54063196461833 98986933440585 -1 -1 272569995055611 -1 94485591855666 550729917916241 928507914552538 604299003750287 941981748058 -1 -1 -1 22141810665273 111731176476877 -1 1077759004833499 321200782061391 654717791417863 12083305736836 243458665138066 1079053200282624 -1 4743134841789 -1 2190013902914 199617340034514 6360222713686 -1 -1 -1 -1 69999454134269 76124305461258 199667465762318 975877309730952 -1 -1 -1 -1 -1 -1 -1 195104653670581 -1 -1 -1 2028348515479 255899987632387 194488688899094 -1 869080254020645 4743134841789 -1 -1 4743134841789 10601988675787 513559781390 41911053450506 -1 -1 340798272482692 28381846522129 505565358075274 -1 -1 615255423962685 -1 553460499395139 6782294614611 1113942604 17164472823672 -1 -1 198914557400088 -1 -1 -1 18518810856533 182674260862798 -1 -1 -1 -1 -1 25466451212091 12083305736836 26778277610621 -1 249558020713577 -1 -1 277905158443052 1112142166292028 -1 69999454134269 -1 4579178619348 -1 -1 25076828402544 -1 375239095517986 -1 -1 -1 30645778231081 1017024539613429 155398131821124 -1 -1 412830902 -1 -1 1220250034523 499871278518956 49322625846309 -1 884475137494053 48717099322965 -1 -1 -1 -1 -1 76485641000878 21722153527972 -1 -1 -1 121778242069870 -1 -1 1102736344367719 -1 107020481451571 -1 452175233220122 1221515780921 -1 328080301718424 5761372603639 -1 -1 145386758082583 4583902624120 -1 634351781327965 139086298182761 -1 -1 237167548002208 202947218987461 295338415562865 -1 -1 -1 976483773802436 -1 903547968358 -1 -1 94067499792216 281077670435746 268521745511520 -1 -1 -1 304565324940246 264789470808711 -1 -1 26765977230017 513559781390 130624248944324 15967437307925 -1 236128827364380 664774989670457 -1 -1 489960716744011 1026945298186037 196973134179618 376959164292 -1 -1 -1 -1 -1 4743134841789 -1 116597283103941 -1 -1 -1 24560835141532 787507538030822 -1 552141073184168 33659148376303 -1 857813362939560 -1 -1 102720493839754 -1 276611861066054 -1 437942037607698 -1 981780668234261 18985602098592 -1 855826739228926 163000458955990 110170834538631 -1 79387393631309 -1 4234923502652 -1 9170054063236 -1 -1 -1 444600890978426 24122954004941 -1 -1 456172269045664 235970330419349 52386732503792 608619445428785 1091585698998 646553427353759 -1 566408335978729 503234230256715 21722153527972 -1 -1 -1 -1 -1 1078205842703 -1 -1 -1 545359783987451 -1 -1 36900375449880 16127712348275 -1 509401629656866 55432089728946 591627161382560 -1 -1 903547968358 107813899893245 -1 19359546465469 -1 15695474877457 65412704177646 -1 -1 12716534442698 249707481025457 50042467394086 37202221178208 1306790359933 -1 -1 140854153085752 70139813508278 -1 5975868127726 2190013902914 -1 10601988675787 -1 815586141564844 248982713316580 -1 15695474877457 -1 139737952685194 524374180860100 7761885723993 -1 -1 -1 -1 -1 1125596976609799 4136932822949 139737952685194 19171592988810 461576925479375 -1 -1 338460986466655 122415231500 -1 -1 16726319619892 980272284780 972762342662726 755814804929648 94067499792216 -1 -1 -1 -1 910969297763520 19359546465469 -1 821687692397582 -1 260820908949824 -1 -1 412830902 104586195872290 1054470817699460 1855042816006 12922096174347 1002836114253984 15695474877457 625891254807919 15695474877457 5599668601065 694130009474615 82885816401369 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 30645778231081 412830902 29969777179526 5975868127726 26477560688134 -1 -1 33428247213921 122415231500 6948353375676 -1 -1 374764564954828 -1 -1 159548743584140 237696559386422 -1 -1 -1 -1 19359546465469 10647474367945 -1 221510482288687 -1 -1 18816571804892 130002612065604 -1 -1 -1 703843780718053 16127712348275 -1 -1 -1 -1 -1 150375073493768 399817725025415 70644176712548 145386758082583 860198675395664 2785177827281 136562909403825 12922096174347 -1 111467598457419 1135727770254 -1 36081165566915 -1 -1 870995492885522 -1 39586765425897 1359861480785 886480529434106 -1 13881077854652 52247870619762 -1 511877753154686 -1 -1 586211320608218 -1 -1 350541098220225 -1 -1 123337730646683 -1 941981748058 385955184381900 17891729221024 -1 -1 -1 -1 5427926948086 188364957071186 -1 111467598457419 11860256257970 692923170315922 2028348515479 -1 -1 25466451212091 524036696332987 4669223800237 693177465373638 39267406635219 441937157870435 208049727379958 -1 122021856558615 1096225834763804 -1 -1 7761885723993 13881077854652 -1 850953158284108 5718213342968 -1 -1 -1 -1 -1 286238725633241 1107325483849732 -1 537255149723096 -1 -1 195132728665894 434076165816847 91844382000702 97716784924480 -1 -1 762997300094541 845269634080965 -1 7761885723993 -1 2186824254950 154667159830596 155398131821124 466096676913294 1106330600499810 414026926618285 -1 113116227119 9590017229758 506396868316306 -1 -1 -1 -1 13658241686098 2022612289180 53163254544538 -1 -1 -1 -1 465378831957194 115123674368993 51012767664750 547325063067364 111731176476877 -1 -1 49160487358 7645167139487 399714720918634 -1 927426390264282 -1 -1 -1 31855715455274 -1 -1 432904909803564 58022386851929 -1 -1 -1 -1 1089865426564340 -1 524374180860100 -1 -1 -1 9648138127840 -1 -1 889982018671445 -1 -1 -1 -1 -1 504915218815033 -1 -1 -1 108829290772432 252744203594 -1 40529794941083 362166667228440 -1 -1 37202221178208 1113942604 980539014602921 -1 -1 11464613037914 -1 28381846522129 -1 689861262234914 54948899137566 330621507634107 -1 -1 73185496449817 -1 -1 -1 -1 -1 50668973694956 -1 466096676913294 -1 15967437307925 70644176712548 -1 -1 188220695219243 -1 -1 975880666193573 -1 -1 -1 -1 113116227119 958853402775388 21476258708201 -1 38840154523231 148770814700193 -1 -1 513559781390 399968589038591 7333706435540 -1 -1 -1 -1 78991253435894 1401867687234 664693173981210 -1 -1 -1 -1 454410253067192 -1 -1 -1 -1 868886677819323 525982637216827 388620798329144 9445128479408 -1 28794498888014 -1 363324372325126 -1 -1 1118060030419859 -1 897955415289097 -1 268521745511520 385955184381900 -1 207578818939227 1012729023635821 -1 383910948318674 -1 -1 119878956757829 21179777086944 857920539979838 -1 -1 -1 -1 -1 -1 -1 15579134209935 -1 -1 590519277061208 5224089044462 1053573425853201 15579134209935 -1 387034197748261 328248516461709 176678141643958 -1 -1 -1 -1 -1 122415231500 336304584174302 5224089044462 -1 -1 40106398439952 82844439367098 -1 -1 21722153527972 -1 507107111981543 -1 7993312124065 1033165347200861 -1 -1 276611861066054 -1 -1 107188954361882 41911053450506 -1 73614385743948 -1 443943660693539 -1 589806799208045 -1 9762854214847 101997856253870 95887353617026 -1 76124305461258 -1 12332168871630 962193486301706 -1 66466470590679 -1 878691214097770 5975868127726 -1 284144487628071 -1 
stderr
Execution Time: 0.00408967 sec