//~ author : Sumit Prajapati #pragma GCC optimize("O3") #pragma GCC target ("avx2") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> using namespace std; // using namespace __gnu_pbds; //---------------------Macros---------------------------------------------------------------------------------- #define ull unsigned long long #define ll long long #define ld long double // #define int long long #define pii pair<int, int> #define pll pair<ll, ll> #define vi vector<int> #define pb push_back #define mk make_pair #define ff first #define ss second #define SZ(x) ((int)x.size()) #define set_bits __builtin_popcountll #define all(a) a.begin(),a.end() #define trav(x,v) for(auto &x:v) #define rep(i,n) for(int i=0;i<n;i++) #define repe(i,n) for(int i=1;i<=n;i++) #define FOR(i,a,b) for(int i=a;i<=b;i++) #define curtime chrono::high_resolution_clock::now() #define timedif(start,end) chrono::duration_cast<chrono::nanoseconds>(end - start).count() #define myshuffle(a,n) FOR(i,1,n-1) swap(a[i], a[rand() % (i + 1)]) #define shuffle(a) shuffle(a.begin(), a.end(), rng) #define mtrand(a,b) uniform_int_distribution<int>(a, b)(rng) #define myunique(v) sort( vec.begin(), vec.end() );vec.erase( unique( vec.begin(), vec.end() ), vec.end() ) template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } int gcd(int a, int b) {return a * b == 0 ? a ^ b : __gcd(a, b);} // template <typename T> // using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // ------------------------------------------------------------------------------------------------------------ // -----------------------------Debugging---------------------------------------------------------------------- template<class Fun> class y_combinator_result { Fun fun_; public: template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {} template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); } }; template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); } template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; } 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 << '}'; } void dbg_out() { cerr << endl; } template<typename TT, typename... UU> void dbg_out(TT H, UU... T) { cerr << ' ' << H; dbg_out(T...); } #ifndef ONLINE_JUDGE #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #else #define dbg(...) #endif // ----------------------------------------------------------------------------------------------------------- // ------------------------------Global Variables------------------------------------------------------------- mt19937 randGen(chrono::steady_clock::now().time_since_epoch().count()); const int MD = 1e9 + 7; const int MDL = 998244353; const ll INF = 1e17; const int MX = 1e5 + 5; // ----------------------------------------------------------------------------------------------------------- // --------------------------------Let's Go!------------------------------------------------------------------ vector<int>G[MX]; multiset<ll>st; map<ll, int>mp; const int B = 320; int timer = 0; int n, q; ll a[MX], ans[MX], flatten[MX]; // mt19937_64 randGen(system_clock().now().time_since_epoch().count()); inline void raiseError(string errorCode) { cerr << "Error : " << errorCode << endl; exit(42); } inline int64_t gilbertOrder(int x, int y, int pow, int rotate) { if (pow == 0) { return 0; } int hpow = 1 << (pow - 1); int seg = (x < hpow) ? ( (y < hpow) ? 0 : 3 ) : ( (y < hpow) ? 1 : 2 ); seg = (seg + rotate) & 3; const int rotateDelta[4] = {3, 0, 0, 1}; int nx = x & (x ^ hpow), ny = y & (y ^ hpow); int nrot = (rotate + rotateDelta[seg]) & 3; int64_t subSquareSize = int64_t(1) << (2 * pow - 2); int64_t ans = seg * subSquareSize; int64_t add = gilbertOrder(nx, ny, pow - 1, nrot); ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1); return ans; } struct query { int idx, l, r; int64_t ord; inline void calcOrder() { ord = gilbertOrder(l, r, 21, 0); } bool operator <(const query& other)const { return ord < other.ord; } } Q[MX]; void dfs(int u, int par) { Q[u].l = ++timer; Q[u].idx = u; flatten[timer] = a[u]; for (auto &c : G[u]) if (c != par) dfs(c, u); Q[u].r = timer; Q[u].calcOrder(); } void add_element(ll x) { x = flatten[x]; auto itr = st.upper_bound(x); auto itl = itr; if (itl != st.begin() && itr != st.end()) { itl--; ll val = (*itl) ^ (*itr); auto it = mp.find(val); assert(it != mp.end()); it->ss--; if (it->ss == 0) mp.erase(it); mp[(*itl)^x]++; mp[x ^ (*itr)]++; } else if (itl != st.begin()) { itl--; mp[(*itl)^x]++; } else if (itr != st.end()) { mp[x ^ (*itr)]++; } st.insert(x); } void remove_element(ll x) { x = flatten[x]; auto it = st.lower_bound(x); assert(it != st.end()); auto itl = it; auto itr = it; itr++; if (itl != st.begin() && itr != st.end()) { itl--; ll val = (*itl) ^ (*itr); mp[val]++; ll v1 = (*itl)^x; ll v2 = x ^ (*itr); auto it1 = mp.find(v1); auto it2 = mp.find(v2); assert(it1 != mp.end()); assert(it2 != mp.end()); it1->ss--; it2->ss--; if (it1->ss == 0) mp.erase(it1); if (it2->ss == 0) mp.erase(it2); } else if (itl != st.begin()) { itl--; ll v1 = (*itl)^x; auto it1 = mp.find(v1); assert(it1 != mp.end()); it1->ss--; if (it1->ss == 0) mp.erase(it1); } else if (itr != st.end()) { ll v2 = x ^ (*itr); auto it2 = mp.find(v2); assert(it2 != mp.end()); it2->ss--; if (it2->ss == 0) mp.erase(it2); } st.erase(it); } void MO_S() { for (int L = 1, R = 0, i = 1; i <= q; i++) { while (R < Q[i].r) add_element(++R); while (L > Q[i].l) add_element(--L); while (R > Q[i].r) remove_element(R--); while (L < Q[i].l) remove_element(L++); if (SZ(mp)) { ans[Q[i].idx] = mp.begin()->first; } } } struct Testcase { void solve() { cin >> n; q = n; timer = 0; repe(i, n) G[i].clear(), ans[i] = -1; st.clear(); mp.clear(); repe(i, n - 1) { int x, y; cin >> x >> y; G[x].pb(y); G[y].pb(x); } repe(i, n) { cin >> a[i]; } dfs(1, -1); sort(Q + 1, Q + q + 1); MO_S(); repe(i, q) cout << ans[i] << " "; cout << "\n"; } }; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); auto time0 = curtime; int t = 1; cin >> t; repe(tt, t) { // cout<<"Case #"<<tt<<": "; Testcase T; T.solve(); } cerr << "Execution Time: " << timedif(time0, curtime) * 1e-9 << " sec\n"; return 0; }
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
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
Execution Time: 0.00408967 sec