BZOJ3196 Tyvj1730 二逼平衡树

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <cstring>
  5 #define rep(i,l,r) for(int i=l; i<=r; i++)
  6 #define clr(x,y) memset(x,y,sizeof(x))
  7 #define travel(x) for(Edge *p=last[x]; p; p=p->pre)
  8 using namespace std;
  9 const int INF = 0x7fffffff;
 10 const int maxn = 50010;
 11 int n,m,a[maxn],mn=INF,mx=-INF,l,r,k,pos,opt;
 12 struct Node{
 13     Node* ch[2];
 14     int s,w,v,rnd;
 15     inline void maintain(){
 16         s = ch[0]->s + ch[1]->s + w;
 17     }
 18 };
 19 Node TREAP[1200000], *pt = TREAP, *null = pt++;
 20 inline Node* newnode(int x){
 21     pt->s = pt->w = 1; pt->v = x; pt->rnd = rand();
 22     pt->ch[0] = pt->ch[1] = null;
 23     return pt++;
 24 }
 25 inline void rotate(Node *&o,int d){
 26     Node *k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o;
 27     o->maintain(); k->maintain(); o = k;
 28 }
 29 struct Treap{
 30     Node *root;
 31     Treap(){
 32         root = null;
 33     }
 34     void ins(int x,Node *&p){
 35         if (p == null){
 36             p = newnode(x); return;
 37         }
 38         p->s++; if (x == p->v) p->w++;
 39         else{
 40             int d = x > p->v;
 41             ins(x,p->ch[d]);
 42             if (p->ch[d]->rnd < p->rnd) rotate(p,d^1);
 43         }
 44     }
 45     void del(int x,Node *&p){
 46         if (p == null) return;
 47         if (p->v == x){
 48             if (p->w > 1){
 49                 p->s--; p->w--; return;
 50             }
 51             if (p->ch[0] != null && p->ch[1] != null){
 52                 int d = p->ch[0]->rnd > p->ch[1]->rnd;
 53                 rotate(p,d); del(x,p->ch[d]);
 54             }
 55             else p = p->ch[0] == null ? p->ch[1] : p->ch[0];
 56         }
 57         else{
 58             int d = x > p->v; p->s--;
 59             del(x,p->ch[d]);
 60         }
 61         if (p != null) p->maintain();
 62     }
 63     int getrank(int x,Node *p){
 64         int ans = 0;
 65         for(Node *p = root; p != null;){
 66             int d = p->v == x ? -1 : x > p->v;
 67             if (d == -1){
 68                 ans += p->ch[0]->s; break;
 69             }
 70             else if (!d) p = p->ch[0];
 71             else ans += p->ch[0]->s + p->w, p = p->ch[1];
 72         }
 73         return ans;
 74     }
 75     int getpre(int x){
 76         int ans = -INF;
 77         for(Node *p = root; p != null;){
 78             if (x > p->v) ans = max(ans,p->v), p = p->ch[1];
 79             else p = p->ch[0];
 80         }
 81         return ans;
 82     }
 83     int getnxt(int x){
 84         int ans = INF;
 85         for(Node *p = root; p != null;){
 86             if (x < p->v) ans = min(ans,p->v), p = p->ch[0];
 87             else p = p->ch[1];
 88         }
 89         return ans;
 90     }
 91 }treap[maxn<<2];
 92 struct Node2{
 93     int l,r;
 94 }t[maxn<<2];
 95 void build(int u,int v,int w){
 96     t[w].l = u; t[w].r = v;
 97     rep(i,u,v) treap[w].ins(a[i],treap[w].root);
 98     if (u == v) return;
 99     int mid = (u + v) >> 1;
100     build(u,mid,w<<1); build(mid+1,v,w<<1|1);
101 }
102 int getrank(int u,int v,int w){
103     if (t[w].l == u && t[w].r == v) return treap[w].getrank(k,treap[w].root);
104     int mid = (t[w].l + t[w].r) >> 1;
105     if (v <= mid) return getrank(u,v,w<<1);
106     else if (u > mid) return getrank(u,v,w<<1|1);
107     else return getrank(u,mid,w<<1) + getrank(mid+1,v,w<<1|1);
108 }
109 int getnum(int u,int v){
110     int ans, l = mn, r = mx; int k2 = k;
111     while (l <= r){
112         int mid = (l + r) >> 1; k = mid;
113         if (getrank(u,v,1) < k2) ans = mid, l = mid + 1;
114         else r = mid - 1;
115     }
116     return ans;
117 }
118 void modify(int u,int w){
119     treap[w].del(a[u],treap[w].root);
120     treap[w].ins(k,treap[w].root);
121     if (t[w].l == t[w].r) return;
122     int mid = (t[w].l + t[w].r) >> 1;
123     if (u <= mid) modify(u,w<<1);
124     else modify(u,w<<1|1);
125 }
126 int getpre(int u,int v,int w){
127     if (t[w].l == u && t[w].r == v) return treap[w].getpre(k);
128     int mid = (t[w].l + t[w].r) >> 1;
129     if (v <= mid) return getpre(u,v,w<<1);
130     else if (u > mid) return getpre(u,v,w<<1|1);
131     else return max(getpre(u,mid,w<<1), getpre(mid+1,v,w<<1|1));
132 }
133 int getnxt(int u,int v,int w){
134     if (t[w].l == u && t[w].r == v) return treap[w].getnxt(k);
135     int mid = (t[w].l + t[w].r) >> 1;
136     if (v <= mid) return getnxt(u,v,w<<1);
137     else if (u > mid) return getnxt(u,v,w<<1|1);
138     else return min(getnxt(u,mid,w<<1), getnxt(mid+1,v,w<<1|1));
139 }
140 inline int read(){
141     int ans = 0, f = 1;
142     char c = getchar();
143     while (!isdigit(c)){
144         if (c == ‘-‘) f = -1;
145         c = getchar();
146     }
147     while (isdigit(c)){
148         ans = ans * 10 + c - ‘0‘;
149         c = getchar();
150     }
151     return ans * f;
152 }
153 int main(){
154     n = read(); m = read();
155     rep(i,1,n) a[i] = read(), mn = min(mn,a[i]), mx = max(mx,a[i]);
156     build(1,n,1);
157     rep(i,1,m){
158         opt = read();
159         switch(opt){
160             case 1:
161                 l = read(); r = read(); k = read();
162                 printf("%d\n",getrank(l,r,1) + 1);
163             break;
164             case 2:
165                 l = read(); r = read(); k = read();
166                 printf("%d\n",getnum(l,r));
167             break;
168             case 3:
169                 pos = read(); k = read();
170                 mn = min(mn,k); mx = max(mx,k);
171                 modify(pos,1); a[pos] = k;
172             break;
173             case 4:
174                 l = read(); r = read(); k = read();
175                 printf("%d\n",getpre(l,r,1));
176             break;
177             case 5:
178                 l = read(); r = read(); k = read();
179                 printf("%d\n",getnxt(l,r,1));
180             break;
181         }
182     }
183     return 0;
184 }

  1 1000 500 
  2 1687147 9918457 2675072 6198365 6458901 3336818 3252441 7895169 7512927 5207317 8463545 2874717 4419017 9196785 3031681 400019 3401729 7093743 8250872 6484669 5684929 5634489 1023417 2154881 1640119 3685505 6491081 3605473 5397443 1006817 6283109 3538627 1718385 44240 5291054 2418337 6915285 1248177 7427205 8336251 4227025 2495281 4730577 4139521 1997963 4601237 2552285 7271417 5970037 5865217 3377977 9728449 7220099 6357973 6375857 8515593 8341910 9001533 8097069 4609855 735025 3680876 4218241 747948 1595401 4085761 1712421 1774209 9109033 5191383 9525085 1882381 9568689 4989184 954761 1289937 9773125 8624129 3591209 3115457 5822679 1112597 7519809 494617 5598757 8825601 6279013 7717281 4595513 5533503 7305647 55185 3514371 2302593 4303905 2050361 396579 5094973 5127288 4610043 1331139 5005063 6608109 6418983 2076701 2868477 709697 8446181 9936081 7527425 2545056 1179509 7735335 6464453 3624001 8802681 5776817 552865 4689281 7079937 4451905 1975294 6941697 1991209 7851617 2911071 3639287 976747 2351617 4554241 2888273 6831125 5975303 9282845 1608681 5832857 3871233 4513923 1374620 3657473 2630481 9184363 9520329 2103425 8199105 5753681 6493933 9642809 1692002 9571137 9207501 4402769 6095183 3049985 2944718 3982623 683201 548605 8250193 1627571 441057 347607 7372229 3277585 1920817 8369099 3375015 6556961 6248485 3849177 460063 8501683 1353765 9145087 8261193 5542857 1443249 1218405 5668737 2883670 8838437 8255561 1674115 5377487 1443629 6297225 7909033 3045311 1097789 7361081 3776289 5956225 4964353 1268377 5166813 8015241 5746369 1826596 2805952 7458955 2892501 7194625 2486305 9568323 1385557 4437465 1933049 1822173 2637897 2573473 2437083 5197251 3570757 3813536 2442358 9056385 2107069 5218120 6447925 6109673 8253651 1640271 7130961 7210961 1731741 459777 8528269 2272207 6314641 7156993 4761601 3229233 1218762 2904249 3104017 7991857 8124043 855569 908137 5529849 9597232 7515378 7452966 1359677 6824513 2930101 3757345 8329089 7013189 8488705 516339 7337470 713245 8877905 3076481 7241330 6152817 6789769 5341285 5456173 9640113 83049 5208149 4495233 5961657 2761797 3929651 5521089 1849281 3265241 1964993 330195 4558041 1053685 3698369 1093417 7873025 1076311 2795569 8247265 8241726 5856387 1841645 848449 815393 7627393 1208705 9425647 9754445 4485641 846297 6741817 8622948 5852929 8771827 8438713 8228212 3811017 9690027 9030019 6851841 3857813 7496869 3004475 6681625 9766545 9557709 9465759 5407369 6299265 4329113 2343236 4899937 4257517 841237 2016187 8010937 5532575 6633821 3180129 3178785 1126531 3547435 6206020 7064601 2606337 2625153 3024299 6349673 5473537 905453 5051259 3067934 2857917 3243421 271853 2215995 9134692 702653 5606545 411713 4369613 6890873 5899169 5919041 7237273 5969275 7351161 7866589 3945873 7813249 9980519 5343485 7697707 545977 9943609 4783545 3095825 4955761 5605263 1567857 5981831 2097403 1159397 6064862 3296669 13490 2984093 7567489 4388265 8326169 628413 2333779 4359745 8794605 9166737 802549 2686394 3657249 6351745 37121 1892193 7906175 1973637 4989643 5576409 5234529 7433157 1856925 7959253 4075033 8594719 4529465 11413 6996401 4843297 176163 7621748 6178001 6223059 4042085 5418785 1752857 8055537 1545850 9556225 7511892 2715509 7430449 393173 5583917 8921553 2501041 8445581 6807841 4683067 3364356 2387729 467641 6781657 5682545 8114779 2962023 6601541 8271249 9900033 9065971 7756958 4459923 523537 1329041 2108033 7325387 3478115 6214155 1244873 2964689 3046355 8182561 3153557 9645951 3599185 425347 3572291 6246401 5778945 1612509 9687087 4343881 1350145 6496349 4935125 5199114 6678857 9083506 3023873 6123001 2563637 3329857 7243681 9533100 5423089 6045323 2619137 1753745 9938282 4567141 5834197 7854913 7189553 5862819 6248449 91633 6188333 6766637 2869221 5164528 7140137 2156865 2191297 1480545 8480951 4710685 5164039 8933528 6198469 395953 8346763 716313 8203649 2352001 1812161 7824961 2159673 6772665 3043145 8740860 9406105 7397136 7079699 1143914 7664257 5083521 968020 8264137 9431421 1195071 9428882 3608595 5405697 3080529 6988061 6037941 5126321 4412988 4899853 5367537 7654621 3345121 5669993 5450223 1512897 46733 9936553 4620673 6642753 8481845 6314297 3636075 336079 1332097 7666721 5260803 8521661 9585293 5646289 6270001 8432049 6804617 6289473 6693425 9616033 1799079 3150645 2805199 9896209 9901957 6368497 290397 7929649 3607185 8533977 2613204 1083341 8661825 7438001 1400671 707391 8311553 8821341 7165208 5646465 1525001 8352925 5496689 5101036 3607575 610240 2749281 5471089 6915089 8878066 8563817 5251061 5902055 4550785 112801 2036641 7364049 8192517 6993874 3559561 8819643 246505 5185679 1805855 5347329 8595395 3235719 2190266 2345289 5856789 9950779 6665729 968773 1816849 7644135 5882293 9321793 6995462 7505457 2801753 8264761 9115249 8633667 9458263 4071167 8654029 5627277 5879233 4277121 1914504 5304193 3710317 4909645 9390583 5601217 7569129 6334001 1125393 6655585 1286761 4106577 71617 8292497 8924937 9827980 3720061 3394741 5610461 5407934 1315297 1312304 5853957 1643009 3355545 3854453 7919657 7891661 3931945 7188331 1704097 9567767 4713871 2921443 1036033 6217361 8796045 6310618 6782801 376965 1980225 5825601 9226673 4488143 4847099 8994677 3108857 7235953 1965055 9623301 7774188 5948681 4941845 4238411 1226324 9363081 7578993 6451881 261769 9270081 8675823 2936745 4393953 3725145 2506865 5921449 4365871 8209657 9756015 9367769 7193825 5020799 3541401 7694482 5628917 8722714 2199575 3599889 6335613 2444069 4981233 9613845 9844635 9189709 4907017 9865441 9122998 979161 1795726 5494795 3227665 7402595 7520017 8749457 9244249 324089 4720001 9594989 9289033 1570467 1728673 2446233 4289725 5991205 1420703 5959521 1133761 1740653 1454601 7873089 4399409 5340257 5015715 5630935 6532953 8415436 7014689 4883523 9471889 4283233 2399757 4860168 930607 1694945 3525049 9577791 3591761 9786209 7890225 7551057 5275877 3303485 7513883 8396573 8557937 3088767 6957421 6741884 1472509 1279393 1802285 5903929 9959861 9367489 946049 6987577 4427361 276658 2709827 7881893 4243745 3428615 8784441 541089 9646433 7923609 3738689 5323721 3559899 9608414 1516969 4561687 4242129 7322817 4344641 9410807 227153 8694337 815201 2971905 9430721 4476897 6705649 9784201 5295267 6318305 7915003 6243408 5345467 5979781 1814961 6815498 7078433 9827361 471569 5899223 6194283 5339809 451969 6984239 7936041 7120933 8033793 3878317 3136641 9256697 2408229 9334283 1172888 4122885 334785 6917377 4998800 6369431 9909389 9153745 9165239 7624342 7294721 3246113 6474980 8065417 7536833 6762281 8854529 1206547 2822817 4602835 9467889 8368481 9684209 613441 1280497 710861 3237783 9411095 7795982 257848 1228324 5682051 6763225 1267001 8531685 2595465 9565441 8981271 1032161 2964669 4780186 5629773 7373929 1109347 9660573 5755465 96129 3779337 1620048 9482721 688498 7918707 5374860 4048801 7796897 2657605 6523477 3279307 1235244 9732061 2104985 2281987 2812175 9818989 7592449 1415305 2387609 1239202 9220177 6444913 5216666 503569 3551889 4985881 2408037 6232213 6129969 4487905 2300784 2931491 6286883 3942945 257825 4102511 4383057 3684174 5882305 1611509 7406137 8746753 344080 1401405 2490243 8116501 8374479 6559447 7871701 6756865 3495817 9255633 843799 3933743 910329 1099209 379897 7052417 419469 3598673 2012285 1019677 827003 1956673 4768977 307529 8154709 8421993 4400897 4881947 3140611 6189743 8511329 9413769 127217 318689 1501127 6940761 3990824 3203213 4071449 7847047 1434449 5668205 6193461 5937833 2615001 1742553 6938379 1697291 6097289 7476449 5533829 4340333 4236890 7807527 509705 4846953 2897953 58523 4207437 6128737 6261361 6721237 5882445 2132097 5858724 398959 875403 2628433 3870186 962217 5401375 1122799 7162119 140865 1006209 4584769 696961 1123665 773857 5695329 5213661 1243757 4858885 7151169 7752144 9276061 4869129 8492061 1567179 2800729 9805505 8081149 1255121 6498425 5681057 3977345 4599133 12295 3939139 6034525 4439777 
  3 5 97 287 7451845 
  4 2 264 689 293 
  5 1 108 772 8114779 
  6 2 15 697 370 
  7 4 150 513 913774 
  8 2 697 781 20 
  9 3 113 5307515 
 10 3 749 2979458 
 11 2 11 529 249 
 12 4 633 801 4288634 
 13 2 92 128 1 
 14 3 961 4252907 
 15 2 447 961 393 
 16 1 28 444 2904249 
 17 4 477 981 122562 
 18 5 314 857 9553024 
 19 2 545 853 78 
 20 2 142 739 457 
 21 3 993 9190707 
 22 3 89 7664635 
 23 2 405 602 157 
 24 2 161 409 90 
 25 4 147 517 5964842 
 26 2 63 537 126 
 27 2 66 548 168 
 28 4 285 894 3935514 
 29 2 73 190 79 
 30 5 166 628 6772755 
 31 3 234 3754561 
 32 4 233 840 7087425 
 33 5 254 645 1142777 
 34 1 93 849 1512897 
 35 1 196 734 8933528 
 36 4 318 345 6893431 
 37 1 313 852 6766637 
 38 5 88 721 5851536 
 39 5 653 693 8204128 
 40 3 681 5157061 
 41 2 137 686 537 
 42 2 115 524 39 
 43 4 17 519 756973 
 44 2 661 920 145 
 45 2 317 726 13 
 46 5 165 171 8367394 
 47 2 251 589 83 
 48 1 130 671 7515378 
 49 3 901 9130549 
 50 5 271 613 4778010 
 51 3 600 7773809 
 52 2 90 369 3 
 53 1 75 409 5832857 
 54 4 128 470 5749762 
 55 2 657 747 17 
 56 2 563 913 16 
 57 3 334 7251305 
 58 3 327 3781745 
 59 5 365 841 6236548 
 60 3 41 2138172 
 61 2 196 591 81 
 62 4 489 809 4990822 
 63 5 433 797 7185055 
 64 2 266 899 187 
 65 4 53 961 910294 
 66 1 147 670 7929649 
 67 4 345 523 1162014 
 68 2 306 730 194 
 69 5 115 769 3596408 
 70 4 489 913 1712364 
 71 1 169 583 3607185 
 72 5 226 805 5230062 
 73 4 251 898 1968754 
 74 4 521 745 3548534 
 75 5 177 696 1751000 
 76 5 357 965 3712428 
 77 5 525 829 333146 
 78 3 361 3256159 
 79 2 27 551 269 
 80 1 544 589 8821341 
 81 4 137 692 4567041 
 82 3 121 4554906 
 83 1 13 437 6807841 
 84 1 320 799 6782801 
 85 4 545 601 2752066 
 86 3 487 7250591 
 87 5 25 689 8262304 
 88 2 193 857 30 
 89 3 617 1407497 
 90 3 833 6348417 
 91 1 81 553 1208705 
 92 3 33 1325065 
 93 5 97 569 1626907 
 94 2 229 839 107 
 95 4 29 646 3364159 
 96 1 127 755 37121 
 97 3 397 3541281 
 98 1 272 317 4257517 
 99 5 215 834 3604560 
100 3 924 9883041 
101 5 275 816 5893776 
102 1 259 637 3720061 
103 2 689 985 222 
104 2 313 861 64 
105 1 641 795 4720001 
106 2 720 825 23 
107 5 4 390 9135802 
108 1 273 690 6633821 
109 1 24 614 1975294 
110 4 132 571 2501042 
111 2 134 564 335 
112 1 312 912 4243745 
113 3 373 8123403 
114 2 659 881 118 
115 1 55 568 3639287 
116 5 143 977 2107530 
117 5 113 740 367516 
118 5 241 870 3566242 
119 2 46 987 373 
120 4 193 853 5412684 
121 1 33 225 6418983 
122 3 765 1826353 
123 2 485 809 106 
124 2 379 945 405 
125 3 361 8742817 
126 1 281 689 6681625 
127 4 123 713 9653112 
128 5 277 775 7922221 
129 1 188 676 1195071 
130 3 247 5825603 
131 2 65 698 301 
132 3 153 8781955 
133 2 156 711 193 
134 4 437 801 6808082 
135 2 473 770 91 
136 4 146 567 6778216 
137 2 73 493 2 
138 2 476 761 25 
139 5 56 621 1805524 
140 4 307 739 4467503 
141 3 801 6046933 
142 4 705 905 6771324 
143 3 105 7040705 
144 1 685 734 1570467 
145 4 681 769 5342410 
146 3 660 7472801 
147 2 264 762 334 
148 5 109 447 5895736 
149 4 73 905 8254306 
150 4 400 435 2115306 
151 5 233 793 7921520 
152 3 473 9896025 
153 1 658 895 261769 
154 2 65 903 416 
155 1 29 661 8501683 
156 3 669 9319861 
157 3 221 218857 
158 4 705 921 6919557 
159 2 281 849 214 
160 2 401 937 13 
161 2 187 626 337 
162 4 301 408 5986044 
163 3 480 7217212 
164 1 145 307 6447925 
165 4 609 685 75866 
166 5 4 668 9614034 
167 3 753 4149889 
168 4 232 872 9167224 
169 4 244 730 398246 
170 1 212 835 1329041 
171 5 405 673 9451361 
172 1 206 722 6335613 
173 1 639 783 4427361 
174 5 457 793 6181576 
175 1 295 757 3541281 
176 3 611 9897517 
177 4 89 681 9324662 
178 5 14 569 1284976 
179 2 319 714 269 
180 2 4 501 197 
181 4 645 905 6202659 
182 1 319 721 6781657 
183 3 289 7740067 
184 5 97 393 75913 
185 4 306 939 5925218 
186 4 527 761 5825762 
187 4 239 850 1043498 
188 4 193 707 7924247 
189 3 425 7758339 
190 5 473 703 3541384 
191 4 292 669 8447458 
192 5 643 697 7189430 
193 3 1 6364929 
194 3 453 2158337 
195 5 3 658 8202018 
196 3 623 8290081 
197 5 367 489 9079161 
198 3 367 5273956 
199 3 751 8918006 
200 5 421 841 8205980 
201 1 140 614 7243681 
202 3 649 9851073 
203 5 235 830 9893392 
204 3 225 800105 
205 3 695 2484031 
206 4 181 403 5239750 
207 3 225 7767337 
208 4 165 377 5748789 
209 1 257 391 1159397 
210 1 401 497 9900033 
211 3 22 4808585 
212 2 793 977 21 
213 5 143 833 1723536 
214 1 237 857 8346763 
215 4 280 896 4718984 
216 4 501 625 5891678 
217 3 225 2702111 
218 1 91 714 848449 
219 3 769 7055773 
220 5 125 653 7620207 
221 5 257 433 3003978 
222 1 145 229 4437465 
223 3 561 2052993 
224 2 45 745 245 
225 1 179 816 3136641 
226 1 717 913 8854529 
227 1 47 477 1774209 
228 4 305 533 274434 
229 5 361 557 8116262 
230 4 667 937 7586162 
231 5 286 533 9937280 
232 4 185 577 52050 
233 4 307 762 8603000 
234 4 81 832 852023 
235 2 86 434 168 
236 1 71 705 112801 
237 2 312 965 501 
238 2 266 874 315 
239 3 685 5389169 
240 3 585 3652621 
241 4 232 778 5992486 
242 5 11 407 4434419 
243 3 743 116929 
244 5 86 622 5892622 
245 4 801 817 6372720 
246 5 61 721 8050711 
247 1 193 741 610240 
248 3 245 5295735 
249 3 529 6509008 
250 3 288 6800545 
251 2 89 269 45 
252 1 173 793 848449 
253 2 57 443 50 
254 4 665 881 2604746 
255 4 405 673 8272191 
256 3 881 2908849 
257 5 66 445 5158028 
258 3 781 6734493 
259 4 225 869 1971250 
260 3 703 115813 
261 1 121 205 3982623 
262 3 581 7933811 
263 1 265 301 6800545 
264 1 42 785 4683067 
265 2 89 281 34 
266 4 313 745 4902610 
267 4 175 667 7670790 
268 1 26 523 7251305 
269 3 237 1704569 
270 1 108 496 7458955 
271 3 356 5789733 
272 2 262 852 514 
273 4 201 813 1168104 
274 5 809 881 2272502 
275 2 905 968 61 
276 1 625 983 2300784 
277 2 291 815 412 
278 2 113 517 77 
279 5 385 749 2341812 
280 1 49 501 8838437 
281 3 153 9626153 
282 4 93 121 4612409 
283 4 273 794 3791714 
284 4 65 793 3548561 
285 5 605 693 6211712 
286 5 82 567 4951356 
287 2 174 635 217 
288 5 125 737 7430568 
289 5 217 823 8388280 
290 3 873 8942433 
291 2 193 749 404 
292 1 604 801 9363081 
293 1 927 965 58523 
294 4 199 551 7467338 
295 2 157 939 577 
296 4 205 227 1822679 
297 1 126 486 7351161 
298 2 65 85 14 
299 4 413 945 5029564 
300 5 21 534 4603634 
301 4 45 483 3763570 
302 2 161 585 400 
303 1 497 649 3235719 
304 2 189 252 34 
305 2 121 337 8 
306 2 625 807 41 
307 3 642 2270569 
308 4 417 561 1337858 
309 4 143 617 525142 
310 3 649 8465125 
311 5 489 497 3041632 
312 3 877 3799405 
313 3 305 9893473 
314 5 214 755 619648 
315 1 289 710 9766545 
316 1 897 934 8511329 
317 1 121 283 9640113 
318 3 447 6244061 
319 1 68 285 5456173 
320 5 795 953 7367102 
321 2 555 781 190 
322 3 517 1410927 
323 2 3 435 105 
324 1 187 593 8771827 
325 1 296 779 8742817 
326 3 465 4215147 
327 4 52 414 1783134 
328 1 145 701 4558041 
329 2 209 913 303 
330 4 117 696 5092970 
331 4 218 557 6210827 
332 1 55 652 2606337 
333 3 327 8661453 
334 3 325 9458669 
335 2 237 795 181 
336 1 232 894 9244249 
337 5 309 725 2603839 
338 1 212 859 6815498 
339 4 25 798 3084850 
340 1 101 518 1812161 
341 3 94 4923811 
342 3 497 8493269 
343 1 94 465 5576409 
344 4 142 793 7573332 
345 5 141 593 8248892 
346 5 433 960 5625012 
347 5 234 738 1321132 
348 4 181 695 4078164 
349 3 385 7929735 
350 4 331 417 5973526 
351 1 113 927 6756865 
352 2 245 851 137 
353 3 799 563233 
354 1 351 783 3559899 
355 2 51 193 106 
356 4 135 762 8595496 
357 5 169 809 1139751 
358 5 385 839 7753513 
359 3 667 6545153 
360 4 855 953 5943824 
361 4 317 833 2753326 
362 4 249 521 8922702 
363 1 253 377 8228212 
364 4 193 587 2568322 
365 4 141 723 2750037 
366 5 523 589 9578780 
367 1 273 769 1752857 
368 1 225 481 1053685 
369 2 226 756 421 
370 5 129 502 3367086 
371 3 857 5644593 
372 5 210 564 3600990 
373 4 169 981 9691200 
374 2 25 248 29 
375 5 6 65 4132350 
376 3 373 2851785 
377 4 102 593 5782678 
378 5 33 93 4725408 
379 4 176 718 331936 
380 3 341 9821717 
381 1 123 457 8438713 
382 5 368 957 820074 
383 1 179 775 5825603 
384 5 329 941 3094352 
385 3 573 8534193 
386 3 33 2984321 
387 5 118 540 4248596 
388 2 228 778 368 
389 2 33 627 521 
390 3 441 7651039 
391 1 14 371 3680876 
392 4 163 690 1228591 
393 5 95 748 9314500 
394 3 391 6605317 
395 1 50 637 8838437 
396 5 65 974 9873388 
397 3 789 6435845 
398 5 465 577 5468916 
399 2 771 929 48 
400 5 161 899 2927358 
401 2 301 863 546 
402 3 619 1144309 
403 2 116 532 246 
404 1 279 662 6741817 
405 4 817 949 2291826 
406 2 479 841 224 
407 2 332 926 308 
408 4 545 969 7369914 
409 3 281 3944193 
410 5 643 997 4853408 
411 3 865 6391807 
412 2 257 737 62 
413 1 239 561 2158337 
414 3 593 2966368 
415 2 598 791 2 
416 1 12 482 5668737 
417 2 130 773 115 
418 2 497 924 9 
419 1 229 671 1126531 
420 2 277 892 399 
421 5 303 823 7926342 
422 4 1 745 7461666 
423 3 561 1743273 
424 2 171 755 43 
425 5 187 703 9460612 
426 3 881 8158165 
427 5 70 467 3919716 
428 4 61 901 5211380 
429 3 93 1102279 
430 1 108 480 7929735 
431 2 633 825 131 
432 5 183 762 2185466 
433 4 189 378 8666288 
434 1 195 649 1093417 
435 5 171 921 6307598 
436 3 979 3397089 
437 1 229 891 4558041 
438 3 910 3267953 
439 3 137 3581625 
440 5 55 550 1840497 
441 2 40 588 459 
442 4 47 519 7671796 
443 4 124 555 7960694 
444 2 247 601 164 
445 5 56 462 1341200 
446 4 103 213 5759266 
447 3 801 2925058 
448 2 181 553 155 
449 1 93 137 7527425 
450 5 212 791 5786884 
451 2 245 917 588 
452 4 233 661 5970972 
453 5 324 804 5574954 
454 4 33 567 3054144 
455 3 392 8033759 
456 4 245 893 9412695 
457 3 235 3519197 
458 4 193 233 8018330 
459 1 553 697 9613845 
460 5 277 543 5050 
461 3 777 7090625 
462 3 778 2472185 
463 2 61 651 202 
464 4 563 569 1533094 
465 1 585 801 968773 
466 3 849 8300175 
467 5 249 879 836646 
468 1 96 458 5473537 
469 5 106 609 621934 
470 1 275 758 4550785 
471 5 457 669 43528 
472 2 169 520 21 
473 1 127 805 7873025 
474 3 875 6038481 
475 3 565 774625 
476 4 745 948 4570368 
477 4 174 734 940400 
478 2 119 586 329 
479 1 494 993 5853957 
480 4 7 500 7629241 
481 4 551 897 4049638 
482 4 329 385 5608924 
483 1 283 959 8819643 
484 4 697 791 1137466 
485 1 156 754 8819643 
486 1 133 844 5407369 
487 2 757 883 12 
488 3 188 2775174 
489 4 561 633 5883110 
490 3 809 62139 
491 5 20 430 6305500 
492 1 73 915 2016187 
493 4 199 865 3556600 
494 1 189 833 2702111 
495 1 82 233 548605 
496 1 43 665 7959253 
497 4 156 563 5855218 
498 2 8 510 50 
499 1 21 273 6447925 
500 3 793 2260369 
501 1 137 735 5630935 
502 5 248 830 5598612

  1 7452966 
  2 6890873 
  3 536 
  4 5532575 
  5 908137 
  6 1802285 
  7 4683067 
  8 4283233 
  9 55185 
 10 7796897 
 11 130 
 12 112801 
 13 9556225 
 14 2964669 
 15 7654621 
 16 8114779 
 17 3180129 
 18 5961657 
 19 2573473 
 20 3243421 
 21 3931945 
 22 6279013 
 23 6781657 
 24 7079699 
 25 1143914 
 26 109 
 27 485 
 28 6890873 
 29 353 
 30 5852929 
 31 8209657 
 32 9687087 
 33 1053685 
 34 747948 
 35 5882305 
 36 324089 
 37 8369099 
 38 2625153 
 39 413 
 40 4783545 
 41 83049 
 42 205 
 43 5746369 
 44 2444069 
 45 503569 
 46 6243408 
 47 2108033 
 48 4981233 
 49 7188331 
 50 3178785 
 51 908137 
 52 422 
 53 1159397 
 54 5083521 
 55 3599185 
 56 1704097 
 57 149 
 58 5234529 
 59 1965055 
 60 3541401 
 61 1752857 
 62 3720061 
 63 334785 
 64 5197251 
 65 43 
 66 4558041 
 67 303 
 68 321 
 69 2749281 
 70 8264137 
 71 516339 
 72 54 
 73 1627571 
 74 1856925 
 75 3355545 
 76 3 
 77 18 
 78 3607185 
 79 5899169 
 80 136 
 81 7406137 
 82 1312304 
 83 65 
 84 3088767 
 85 9145087 
 86 269 
 87 116 
 88 2501041 
 89 7654621 
 90 231 
 91 5755465 
 92 193 
 93 2108033 
 94 376965 
 95 3572291 
 96 4071167 
 97 5407934 
 98 135 
 99 3738689 
100 7364049 
101 265 
102 9645951 
103 7923609 
104 50 
105 5083521 
106 3607575 
107 6804617 
108 3559561 
109 6772665 
110 13490 
111 1226324 
112 1805855 
113 4459923 
114 6763225 
115 7 
116 5340257 
117 6851841 
118 5899169 
119 8253651 
120 2108033 
121 7923609 
122 5 
123 5260803 
124 549 
125 6917377 
126 4369613 
127 307529 
128 7621748 
129 5981831 
130 105 
131 71617 
132 9616033 
133 9166737 
134 393173 
135 73 
136 9458263 
137 324 
138 60 
139 6188333 
140 139 
141 9321793 
142 1289937 
143 7165208 
144 3781745 
145 6194283 
146 263 
147 83049 
148 5921449 
149 5825601 
150 1036033 
151 7919657 
152 3541401 
153 8445581 
154 7193825 
155 8203649 
156 9083506 
157 8209657 
158 340 
159 9896025 
160 5234529 
161 5746369 
162 19 
163 96 
164 827003 
165 1728673 
166 507 
167 4713871 
168 5882293 
169 43 
170 7621748 
171 3004475 
172 45 
173 3608595 
174 183 
175 168 
176 74 
177 271853 
178 8123403 
179 7578993 
180 9938282 
181 46733 
182 8595395 
183 848449 
184 4761601 
185 7 
186 7773809 
187 5628917 
188 5991205 
189 4437465 
190 5899169 
191 6369431 
192 8055537 
193 24 
194 2272207 
195 38 
196 1218762 
197 2595465 
198 8264761 
199 5166813 
200 1964993 
201 42 
202 25 
203 329 
204 1608681 
205 4899937 
206 7666721 
207 375 
208 302 
209 8796045 
210 1159397 
211 2281987 
212 8511329 
213 85 
214 7959253 
215 1973637 
216 2345289 
217 414 
218 4610043 
219 3781745 
220 3547435 
221 6217361 
222 4955761 
223 5208149 
224 7433157 
225 8396573 
226 7364049 
227 175 
228 1 
229 7458955 
230 7472801 
231 1822173 
232 277 
233 5598757 
234 5020799 
235 4609855 
236 3754561 
237 9134692 
238 41 
239 4761601 
240 460063 
241 2921443 
242 1332097 
243 523537 
244 3043145 
245 628413 
246 409 
247 33 
248 162 
249 129 
250 7373929 
251 8749457 
252 2387729 
253 369 
254 417 
255 1774209 
256 235 
257 4713871 
258 5083521 
259 6206020 
260 149 
261 3607575 
262 601 
263 2606337 
264 425 
265 3080529 
266 69 
267 213 
268 7569129 
269 8250193 
270 5627277 
271 1329041 
272 4075033 
273 5969275 
274 537 
275 2709827 
276 134 
277 7305647 
278 8595395 
279 1143914 
280 7756958 
281 5937833 
282 2749281 
283 8921553 
284 104 
285 2563637 
286 2749281 
287 9585293 
288 73 
289 25 
290 8055537 
291 3375015 
292 3607185 
293 9690027 
294 1325065 
295 4139521 
296 5778945 
297 4730577 
298 330195 
299 293 
300 827003 
301 331 
302 3095825 
303 4257517 
304 6987577 
305 8594719 
306 141 
307 1226324 
308 9319861 
309 530 
310 9883041 
311 5471089 
312 2931491 
313 2930101 
314 9786209 
315 5956225 
316 243 
317 2281987 
318 6772665 
319 5629773 
320 7364049 
321 4858885 
322 1480545 
323 61 
324 115813 
325 270 
326 1856925 
327 257825 
328 42 
329 6772665 
330 7929649 
331 7458955 
332 979161 
333 9465759 
334 3929651 
335 5208149 
336 309 
337 7235953 
338 2190266 
339 8661453 
340 40 
341 6314297 
342 271 
343 1841645 
344 8247265 
345 7664635 
346 7959253 
347 5273956 
348 1350145 
349 5753681 
350 4495233 
351 40 
352 5789733 
353 8796045 
354 5969275 
355 5576409 
356 3049985 
357 9411095 
358 8015241 
359 139 
360 11413 
361 3375015 
362 1525001 
363 14 
364 841237 
365 201 
366 628413 
367 195 
368 46733 
369 841237 
370 529 
371 4561687 
372 930607 
373 6996401 
374 277 
375 7627393 
376 4048801 
377 5606545 
378 594 
379 1133761 
380 535 
381 357 
382 1109347 
383 5882293 
384 6314641 
385 165 
386 3547435 
387 154 
388 9 
389 504 
390 5852929 
391 1112597 
392 180 
393 327 
394 5605263