QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#381836#7436. Optimal Ordered Problem SolverQingyu100 ✓1992ms109868kbC++239.3kb2024-04-07 20:53:582024-04-07 21:44:37

Judging History

你现在查看的是最新测评结果

  • [2024-04-07 21:44:37]
  • 评测
  • 测评结果:100
  • 用时:1992ms
  • 内存:109868kb
  • [2024-04-07 20:53:58]
  • 提交

answer

#include<bits/stdc++.h>
#define F(i,l,r) for(int i=l;i<r;++i)
#define Fe(i,l,r) for(int i=l;i<=r;++i)
#define Fer(i,l,r) for(int i=l;i>=r;--i)
#if 0
#define pr(...) fprintf(stderr,__VA_ARGS__)
#else
#define pr(...) void(0)
#endif

typedef long long i64;
const int maxn=1e6,maxm=1e6,N=maxn+10;

namespace IO{
const int BUF_SZ=1<<16;
char ib[BUF_SZ+1],*ip=ib+BUF_SZ;
void ipre(int n){
 int c=ib+BUF_SZ-ip;
 if(c<n){
  memcpy(ib,ip,c);
  ip=ib;
  fread(ib+c,1,BUF_SZ-c,stdin)[ib+c]=0;
 }
}
template<class T>
T read(T L,T R){
 ipre(100);
 T x=0,f=1;
 while(*ip<'0'||*ip>'9')if(*ip++=='-')f=-f;
 while(*ip>='0'&&*ip<='9')x=x*10+*ip++-'0';
 x*=f;
 if(!(L<=x&&x<=R)){
  std::cerr<<x<<" not in ["<<L<<","<<R<<"]\n";
  exit(1);
 }
 return x;
}
char ob[BUF_SZ+1],*op=ob;
void opre(int n){
 int c=ob+BUF_SZ-op;
 if(c<n){
  fwrite(ob,1,BUF_SZ-c,stdout);
  op=ob;
 }
}
template<class T>
void write(T x){
 opre(100);
 char ss[100],*sp=ss;
 if(x<T(0))x=-x,*op++='-';
 do *sp++=x%10+'0';while(x/=10);
 while(sp!=ss)*op++=*--sp;
}
template<class T>
void write(T x,char c){
 write(x);
 *op++=c;
}
struct __{
 __(){}
 ~__(){
  fwrite(ob,1,op-ob,stdout);
 }
}_;
};
using IO::read;
using IO::write;
const int MEM=1<<26;
char pool[MEM],*pool_p=pool;

template<class T>
void alloc(T *&p,int sz,bool init=1){
 //p=new T[sz]();
 //return;
 p=reinterpret_cast<T*>(pool_p);
 pool_p+=(sz*sizeof(T)+7)&~7;
 assert(pool_p<pool+MEM);
 if(init)F(i,0,sz)new(p+i)T();
}

template<class T>
struct Undo{
 T &x;
 T x0;
 Undo(T &x):x(x),x0(x){}
 ~Undo(){x=x0;}
};

#define alloc_scope Undo<char*> _##__LINE__(pool_p)
struct Void{
 char _[0];
 template<class T>
 friend void operator*=(T &,Void){}
 friend Void operator+(Void,Void){return Void();}
};

template<class D=Void,class M=Void>
struct MSegTree{
 struct Node{
  D d;
  M m;
  void app(const M &t){
   d*=t;
   m*=t;
  }
  void up(const Node &a,const Node &b){
   d=a.d+b.d;
   d*=m;
  }
 }*tr;
 int mx;
 int n;
 void in(int x){assert(1<=x&&x<=n);}
 void in(int l,int r){assert(1<=l&&l<=r&&r<=n);}
 void alloc(int n){
  for(mx=1;mx<n+2;mx<<=1);
  ::alloc(tr,mx+n+3);
  this->n=n;
 }
 void init(int n,D d0){
  alloc(n);
  Fe(i,1,n)tr[mx+i].d=d0;
  range_update(1,n);
 }
 template<class T>
 void init(int n,T *d0){
  alloc(n);
  Fe(i,1,n)tr[mx+i].d=d0[i];
  range_update(1,n);
 }
 Node &at(int x){
  in(x);
  return tr[mx+x];
 }
 D &operator[](int x){
  in(x);
  return tr[mx+x].d;
 }
 void range_update(int l,int r){
  in(l),in(r);
  l+=mx,r+=mx;
  for(l>>=1,r>>=1;l<r;l>>=1,r>>=1){
   Fe(x,l,r)up(x);
  }
  for(;l;l>>=1)up(l);
 }
 void up(int x){
  tr[x].up(tr[x*2],tr[x*2+1]);
 }
 void add(int x,const D &y){//M=Void
  in(x);
  for(x+=mx;x;x>>=1)tr[x].d=tr[x].d+y;;
 }
 void update(const M &t){
  tr[1].app(t);
 }
 template<class T>
 void update(int x,T y){
  in(x);
  for(tr[x+=mx].d=y;x>1;up(x>>=1));
 }
 void update(int l,int r,const M &t){
  in(l),in(r);
  for(l+=mx-1,r+=mx+1;l^r^1;up(l>>=1),up(r>>=1)){
   if(~l&1)tr[l+1].app(t);
   if(r&1)tr[r-1].app(t);
  }
  for(;l>1;up(l>>=1));
 }
 void update_prefix(int x,const M &t){
  in(x);
  for(x+=mx+1;x>1;up(x>>=1)){
   if(x&1)tr[x-1].app(t);
  }
 }
 void update_suffix(int x,const M &t){
  in(x);
  for(x+=mx-1;x>1;up(x>>=1)){
   if(~x&1)tr[x+1].app(t);
  }
 }
 D query(){
  return tr[1].d;
 }
 D query(int l,int r){
  in(l),in(r);
  assert(l<=r);
  D a1,a2;
  for(l+=mx-1,r+=mx+1;l^r^1;a1*=tr[l>>=1].m,a2*=tr[r>>=1].m){
   if(~l&1)a1=a1+tr[l+1].d;
   if(r&1)a2=tr[r-1].d+a2;
  }
  a1=a1+a2;
  for(;l>1;a1*=tr[l>>=1].m);
  return a1;
 }
 D query_prefix(int r){
  in(r);
  D a1;
  for(r+=mx+1;r>1;r>>=1,a1*=tr[r].m){
   if(r&1)a1=tr[r-1].d+a1;
  }
  return a1;
 }
 D query_suffix(int l){
  in(l);
  D a1;
  for(l+=mx-1;l>1;l>>=1,a1*=tr[l].m){
   if(~l&1)a1=a1+tr[l+1].d;
  }
  return a1;
 }
 void dn(int x){
  tr[x*2].app(tr[x].m);
  tr[x*2+1].app(tr[x].m);
  tr[x].m=M();
 }
 void dna(int x){
  in(x);
  x+=mx;
  for(int c=__builtin_ctz(mx);c>0;--c)dn(x>>c);
 }
 void dna(int l,int r){
  in(l,r);
  l+=mx,r+=mx;
  for(int c=__builtin_ctz(mx);c>0;--c){
   int L=l>>c,R=r>>c;
   Fe(i,L,R)dn(i);
  }
 }
 void dna(){
  F(i,1,mx){
   tr[i*2].app(tr[i].m);
   tr[i*2+1].app(tr[i].m);
   tr[i].m=M();
  }
 }
 template<class T>
 int bsearch_l(int x,T f){//M=Void
  in(x);
  for(x+=mx+1;;x>>=1){
   if(x&1){
    if(f(tr[x-1].d))break;
   }
  }
  for(--x;x<mx;){
   x<<=1;
   if(f(tr[x+1].d))++x;
  }
  x-=mx;
  return x+1;
 }
 template<class T>
 int bsearch_r(int x,T f){//M=Void
  in(x);
  for(x+=mx-1;;x>>=1){
   if(~x&1){
    if(f(tr[x+1].d))break;
   }
  }
  for(++x;x<mx;){
   x<<=1;
   if(!f(tr[x].d))++x;
  }
  x-=mx;
  return x-1;
 }
 template<class T>
 int find_lm(T f){
  int x=1;
  while(x<mx){
   dn(x);
   x<<=1;
   if(!f(tr[x].d))++x;
  }
  x-=mx;
  return x;
 }
};

template<class T>
struct BIT{
 T *a;
 int n;
 void alloc(int n0){
  n=n0;
  ::alloc(a,n+1);
 }
 void add(int x,T y){
  assert(1<=x&&x<=n);
  int _n=n;
  for(;x<=_n;x+=x&-x)a[x]+=y;
 }
 T sum(int x){
  assert(0<=x&&x<=n);
  T s=0;
  for(;x;x-=x&-x)s+=a[x];
  return s;
 }
 void dna(){
  Fe(i,1,n)a[i]+=a[i-(i&-i)];
 }
 T at(int x){
  assert(0<=x&&x<=n);
  return a[x];
 }
 void build(){
  Fe(i,1,n){
   int j=i+(i&-i);
   if(j<=n)a[j]+=a[i];
  }
 }
};
#define CMP(T,x) bool operator<(const T &w)const{return x<w.x;}
#define CMPL(T,x) [](const T &a,const T &b)->bool{return a.x<b.x;}
#define KEYL(T,x) [](const T &a){return a.x;}
template<class T,class F>
void rsort(T *d0,T *d1,int n,int v,F key){
 static int t[1<<20];
 F(i,0,v)t[i]=0;
 F(i,0,n)++t[key(d0[i])];
 int s=0;
 F(i,0,v){
  int a=t[i];
  t[i]=s;
  s+=a;
 }
 F(i,0,n)d1[t[key(d0[i])]++]=d0[i];
}

template<class T,class F>
void rsort2(T *d0,int n,F key){
 alloc_scope;
 T *d1;
 alloc(d1,n,0);
 rsort(d0,d1,n,2048,[key](const T &x){return key(x)&2047;});
 rsort(d1,d0,n,2048,[key](const T &x){return key(x)>>11;});
}
using std::max;
using std::min;

const int inf=1e9;

struct Pos{
 int x,y;
}ps[N],ds[N],ps0[N];
bool in(int x,int l,int r){return l<=x&&x<=r;}

struct XY{
 int x,y;
 XY(int x0=0,int y0=inf):x(x0),y(y0){}
};
XY operator+(XY a,XY b){
 return a.y<b.y?a:b;
}
MSegTree<XY> xyt;
BIT<int> xs0,ys0;
int cur[N];
int f1(int x1,int x2,int y1,int y2){
 if(x1>x2)return 0;
 XY xy=xyt.query(x1,x2);
 if(xy.y>y2)return 0;
 int id=cur[xy.x]++;
 xy.y=(ps0[id].x==ps0[id+1].x?ps0[id+1].y:inf);
 xyt.update(xy.x,xy);
 return id;
}
template<class T>
struct Sum{
 T x;
 Sum(T x0=0):x(x0){}
 operator T(){return x;}
 friend Sum operator+(Sum a,Sum b){return Sum(a.x+b.x);}
};
MSegTree<Sum<int>> xs,ys;
int sumclr(MSegTree<Sum<int>> &ws,int l,int r){
 if(l>r)return 0;
 int s0=ws.query(l,r);
 int s=s0;
 while(s0){
  int x=ws.bsearch_r(l,[](Sum<int> d){return d.x;})+1;
  s0-=ws[x];
  ws.add(x,-ws[x]);
  l=x+1;
 }
 return s;
}
struct Q{
 int x,y,id;
}qs[N];
int qp=0;
int ans[N];

struct MinI{
 int x;
 MinI(int x0=inf):x(x0){}
};
MinI operator+(MinI a,MinI b){return MinI(min(a.x,b.x));}
MSegTree<MinI> domt;
int main(){
 int n=read(1,maxn);
 int m=read(1,maxm);
 bool REV=0;
 Fe(i,1,n){
  ps[i].x=read(1,n);
  ps[i].y=read(1,n);
  if(REV)std::swap(ps[i].x,ps[i].y);
 }
 int n0=n;
 xs0.alloc(n);
 ys0.alloc(n);
 Fe(i,1,n){
  ++xs0.a[ps[i].x];
  ++ys0.a[ps[i].y];
  ps0[i]=ps[i];
 }
 xs0.build();
 ys0.build();
 rsort2(ps0+1,n,KEYL(Pos,y));
 rsort2(ps0+1,n,KEYL(Pos,x));
 xyt.alloc(n);
 Fe(i,1,n){
  Pos &p=ps0[i];
  if(p.x!=ps0[i-1].x){
   xyt[p.x]=XY(p.x,p.y);
   cur[p.x]=i;
  }
 }
 xyt.range_update(1,n);
 xs.alloc(n);
 ys.alloc(n);
 domt.alloc(n+2);
 domt[1]=1;
 domt[n+2]=1;
 domt.range_update(1,n+2);
 Fe(qi,1,m){
  int o=read(1,2);
  int x=read(1,n),y=read(1,n);
  int qx=read(1,n),qy=read(1,n);
  if(REV){
   o=3-o;
   std::swap(x,y);
   std::swap(qx,qy);
  }
  int mx=x+(o==1),my=y+(o==2);
  int dp=0;
  for(;;){
   int i=domt.find_lm([my](MinI d){return d.x<=my;});
   if(i>mx)break;
   ds[++dp]={i,domt[i].x};
   domt.update(i,inf);
  }
  if(dp){
   int x0=ds[1].x,y0=ds[dp].y;
   ds[0].y=my;
   ds[dp+1].x=mx;
   Fe(i,1,dp){
    int x1=ds[i].x,x2=ds[i+1].x-1;
    int y1=ds[i].y,y2=my-1,y3=ds[i-1].y-1;
    if(o==1&&x1<=x2){
     int s=sumclr(ys,y1,y3);
     if(s)xs.add(x1,s);
    }
    if(o==2&&y1<=y3){
     int s=sumclr(xs,x1,x2);
     if(s)ys.add(y1,s);
    }
    for(;;){
     int id=f1(x1,x2,y1,y2);
     if(!id)break;
     Pos &p=ps0[id]; 
     if(o==1)xs.add(p.x,1);
     else ys.add(p.y,1);
     --n0;
     xs0.add(p.x,-1);
     ys0.add(p.y,-1);
    }
   }
   if(x0<mx||x0==mx&&y0==my){
    domt.update(x0,my);
   }
   if(y0<my){
    domt.update(mx,y0);
   }
  }
  int y0=domt.query_prefix(qx).x;
  int ans0=0;
  if(y0<=qy){
   int x0=domt.find_lm([qy](MinI d){return d.x<=qy;});
   qs[qp++]={qx+1,qy+1,qi};
   ans0+=n;
   ans0-=n0-xs0.sum(qx);
   ans0-=n0-ys0.sum(qy);
   ans0-=xs.query().x-xs.query(x0,qx).x;
   ans0-=ys.query().x-ys.query(y0,qy).x;
   ans[qi]=ans0;
  }
 }
 rsort2(qs,qp,KEYL(Q,x));
 BIT<int> bit;
 bit.alloc(n+1);
 int pp=n;
 Fer(i,qp-1,0){
  Q &q=qs[i];
  for(;pp&&ps0[pp].x>=q.x;--pp)bit.add(n+1-ps0[pp].y,1);
  ans[q.id]+=bit.sum(n+1-q.y);
 }
 Fe(i,1,m)write(ans[i],'\n');
 return 0;
}

详细

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 0ms
memory: 26164kb

input:

995 996
950 481
376 18
141 776
711 966
130 727
468 529
47 39
857 563
832 821
776 472
154 914
825 279
332 415
470 361
968 440
45 560
299 755
703 785
744 387
547 382
3 549
344 573
778 424
784 765
280 115
251 434
695 98
463 506
379 38
610 486
305 623
703 244
856 365
117 360
772 847
331 723
663 991
900 ...

output:

423
473
758
313
694
232
333
784
821
154
247
244
504
54
200
370
872
782
734
174
660
467
76
754
77
3
144
974
526
415
439
694
507
577
258
120
243
3
2
319
313
498
218
828
433
623
981
700
120
55
70
499
375
283
387
128
317
139
220
410
22
547
3
385
430
168
32
0
178
625
677
561
488
672
577
64
144
537
235
54...

result:

ok 996 numbers

Test #2:

score: 0
Accepted
time: 4ms
memory: 28196kb

input:

1000 998
483 753
603 464
306 515
71 717
536 195
335 816
275 223
236 392
764 856
434 203
910 542
595 408
185 212
559 836
27 238
959 252
830 212
946 431
794 63
164 800
566 307
861 840
555 580
37 225
976 897
946 891
459 163
101 679
511 141
628 271
115 202
6 911
131 99
991 975
578 60
193 889
683 437
408...

output:

411
275
9
632
553
5
873
494
172
893
41
194
638
599
747
37
653
919
560
334
536
26
244
448
800
189
64
383
829
662
4
196
785
548
215
430
258
463
132
488
581
217
229
513
765
817
750
3
213
1
624
545
499
79
59
873
211
334
709
371
597
290
0
957
689
192
119
6
322
390
129
464
24
278
876
824
243
663
443
84
61...

result:

ok 998 numbers

Test #3:

score: 0
Accepted
time: 5ms
memory: 30260kb

input:

1000 995
301 895
261 325
211 404
100 381
849 291
851 65
272 465
786 647
26 15
779 368
356 74
26 196
308 809
532 229
643 707
426 380
152 371
622 652
905 793
847 322
574 197
117 960
339 751
246 87
322 948
511 800
967 25
36 906
278 611
586 991
392 314
933 644
42 569
948 769
982 134
518 314
741 491
800 ...

output:

423
240
474
705
507
222
71
715
306
761
254
570
660
638
797
511
581
691
577
876
695
607
230
812
266
89
79
690
456
514
337
549
916
430
79
563
524
372
690
388
853
54
923
388
850
142
307
460
416
605
263
68
928
644
607
911
471
599
455
620
151
2
748
305
88
282
993
59
574
381
568
238
340
644
566
747
0
119
...

result:

ok 995 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 26160kb

input:

995 997
185 576
420 830
106 145
449 735
293 805
945 57
638 163
316 69
389 66
859 807
632 451
99 437
512 805
645 345
477 93
380 167
502 493
645 333
395 337
729 294
195 209
78 130
592 217
296 864
274 766
791 84
426 303
800 473
198 693
194 756
383 178
404 496
147 487
944 650
316 250
466 523
433 591
794...

output:

67
19
382
84
402
398
880
170
289
60
32
151
17
153
273
203
35
953
2
218
820
458
8
131
80
176
133
487
374
136
756
724
422
128
731
0
685
108
153
24
115
104
646
47
940
854
38
373
831
622
140
49
302
503
460
93
341
105
97
185
228
756
114
466
212
671
967
290
492
859
176
515
249
519
170
0
758
334
899
516
87...

result:

ok 997 numbers

Test #5:

score: 0
Accepted
time: 4ms
memory: 26144kb

input:

996 995
359 306
463 864
932 861
257 565
951 362
874 446
709 578
155 792
887 792
955 630
323 951
273 186
274 877
23 243
643 465
990 822
435 852
403 515
248 410
523 106
512 405
890 889
617 782
539 889
322 419
443 573
805 375
702 60
749 808
147 302
614 933
968 565
681 344
687 665
762 603
17 646
188 34
...

output:

136
742
755
119
569
60
718
478
674
77
676
593
64
132
6
43
797
750
603
229
693
791
874
899
149
61
417
609
132
243
752
409
504
165
901
647
105
175
743
569
468
877
526
0
52
217
792
190
421
343
457
0
696
29
408
40
0
725
467
11
357
402
545
129
761
512
369
573
428
57
5
912
103
876
64
85
257
386
742
760
67...

result:

ok 995 numbers

Test #6:

score: 0
Accepted
time: 4ms
memory: 26168kb

input:

1000 1000
863 244
541 217
420 994
514 373
675 10
137 518
258 267
691 946
517 233
522 726
468 850
698 633
677 591
651 270
739 673
119 385
213 71
2 177
480 66
398 68
233 965
808 316
883 346
486 966
116 926
850 663
129 22
665 370
6 911
38 919
124 555
236 350
12 98
261 510
124 565
294 447
703 338
408 37...

output:

876
833
394
566
775
762
88
202
176
781
306
2
948
563
855
224
953
842
506
326
857
786
428
443
707
975
120
165
67
93
750
775
412
446
850
777
563
399
922
305
169
556
60
12
122
349
935
363
826
415
94
94
221
668
997
779
0
15
355
824
978
12
772
916
365
21
462
487
87
641
9
871
488
586
813
861
791
30
270
12...

result:

ok 1000 numbers

Test #7:

score: 0
Accepted
time: 0ms
memory: 26184kb

input:

998 995
968 598
292 481
163 318
24 536
222 338
486 556
600 574
730 474
653 981
669 378
513 79
766 774
100 543
895 535
752 93
883 427
338 874
253 536
235 384
761 822
790 235
823 909
598 348
319 746
650 219
710 485
862 816
847 978
397 497
108 894
61 939
860 633
545 743
130 362
782 855
72 965
906 146
5...

output:

885
513
845
589
139
453
34
725
407
679
629
662
345
547
303
609
463
207
585
227
290
350
105
382
270
19
380
707
413
366
491
284
784
887
642
672
547
651
126
16
26
771
752
723
315
244
66
626
169
923
720
449
889
812
406
53
745
218
151
583
551
520
286
668
626
316
892
937
339
804
7
149
470
32
723
753
341
2...

result:

ok 995 numbers

Test #8:

score: 0
Accepted
time: 0ms
memory: 26164kb

input:

1000 1000
118 698
770 781
232 191
699 983
873 604
753 289
556 223
577 705
614 711
50 822
59 41
169 346
535 785
956 299
570 831
933 382
193 64
943 608
973 38
283 425
679 272
769 954
369 484
202 454
916 768
474 703
502 751
453 156
202 791
864 285
834 371
631 580
131 132
724 408
789 344
735 982
835 826...

output:

35
241
333
424
60
661
739
244
78
185
303
353
72
756
112
94
0
756
518
941
931
1
217
908
332
211
432
64
930
747
716
474
313
510
827
362
773
257
632
490
417
710
273
179
453
466
473
718
230
714
491
703
74
108
484
40
220
214
0
170
843
121
182
538
606
662
824
0
666
425
620
75
182
16
389
422
0
343
365
299
...

result:

ok 1000 numbers

Subtask #2:

score: 20
Accepted

Test #9:

score: 20
Accepted
time: 534ms
memory: 93924kb

input:

999996 999996
921339 140126
955508 363759
958698 342406
280137 955674
907511 75721
189876 946586
152058 168837
541857 557702
84498 865987
185574 809224
704828 701026
815379 548000
989515 518951
335439 336866
745570 790616
766723 212893
926629 859003
51261 40866
592510 556235
324926 700261
320946 798...

output:

0
0
953730
0
0
512663
0
0
0
0
407467
0
0
0
0
420
0
0
0
0
0
0
513245
0
0
0
0
0
0
0
0
0
0
0
11756
0
0
7822
0
0
0
0
22726
0
0
0
8233
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
13818
349438
0
0
0
0
0
0
6803
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8602
0
0
0
0
0
0
0
15717
0
0
0
0
0
0
0
0
0
0...

result:

ok 999996 numbers

Test #10:

score: 0
Accepted
time: 528ms
memory: 91932kb

input:

999999 999998
593840 81071
226822 360556
984658 495723
774168 212723
961202 460976
425364 312068
135686 76747
312878 654073
77701 260718
263549 822714
513429 976716
926207 374094
338002 624578
897648 332005
630931 241967
134312 551284
743455 355739
997122 435568
642662 63663
795243 94444
696789 3776...

output:

491984
0
125735
422908
0
226183
0
0
0
2158
0
0
280064
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
19502
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
747
0
0
0
0
0
0
0
0
0
0
0
0
59265
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 999998 numbers

Test #11:

score: 0
Accepted
time: 509ms
memory: 91972kb

input:

1000000 1000000
883777 318082
13863 878428
601471 340063
593065 648191
228224 432858
585884 205059
770071 963599
897140 940808
68907 32537
396365 642545
822913 211348
629556 82339
190410 157689
907562 173596
271125 337580
145399 606492
749603 897091
193876 205903
678121 530830
947890 589055
721497 7...

output:

261157
0
0
52244
0
0
0
0
4610
0
20801
505827
0
0
0
655799
0
0
0
0
0
163473
0
0
113182
0
0
556199
0
0
0
282902
197726
0
0
0
521870
0
0
0
0
0
0
0
0
0
0
146288
0
136329
0
0
0
0
0
91372
0
0
0
0
0
522077
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
181410
0
0
0
0
0
0
...

result:

ok 1000000 numbers

Test #12:

score: 0
Accepted
time: 512ms
memory: 93888kb

input:

999999 999998
510701 119376
730813 348187
969509 347009
150616 323014
602592 62582
356110 705851
244692 610953
398605 700401
220533 880308
10280 261179
57162 967936
642021 39765
410482 274103
869979 489138
673553 368275
889697 840948
383673 63696
607963 107808
875626 9630
793170 959823
798227 760130...

output:

65013
21415
692431
0
388141
0
0
0
0
0
0
0
0
0
0
42859
0
0
0
0
0
0
0
0
0
0
8862
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
172112
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1215
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6288
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 999998 numbers

Test #13:

score: 0
Accepted
time: 504ms
memory: 95980kb

input:

999995 999997
148480 214663
902145 539206
771718 173309
708903 967479
984809 352800
21198 668703
879442 719279
593199 82759
286519 788269
873747 641026
246815 368469
585243 532758
177189 437376
566499 996874
663718 794807
847945 784546
68802 611025
636042 793005
656312 200282
90301 316758
516692 913...

output:

408393
0
0
210017
0
0
0
0
0
0
0
0
0
0
0
0
0
0
34271
0
0
0
0
0
0
0
0
0
0
31774
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
624290
27190
0
0
0
0
0
0
0
0
2486
0
0
0
0
0
0
0
0
0
844
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10393
0
0
0
0
0
0
0
0
0
0
0
0
49019
0
0
0
19256
0
0
0
0
0
0
62458
0
0
0
0
0
0
...

result:

ok 999997 numbers

Test #14:

score: 0
Accepted
time: 525ms
memory: 95976kb

input:

999997 999999
21022 22383
798350 250307
186761 593014
213847 210545
769838 227750
113146 776982
163493 384752
89954 142451
392976 865128
131868 401967
725617 848954
553332 555884
864058 712711
390463 443782
552326 132864
92265 612350
758766 28175
452611 460112
344799 865045
46279 695425
971996 40084...

output:

418555
110151
3026
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
33746
0
0
0
0
63321
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
60309
0
0
0
0
0
0
6997
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3366
0
0
0
0
0
0
0
0
0
2...

result:

ok 999999 numbers

Test #15:

score: 0
Accepted
time: 531ms
memory: 95812kb

input:

1000000 1000000
151138 713282
47031 196016
951306 826897
695178 570874
853734 782231
254275 640338
166145 420223
154398 814676
670384 826624
992734 757955
486563 187117
169107 198294
973559 847637
993679 950871
217983 940481
10443 754197
627178 253860
607235 514653
806520 269962
714084 706285
32303 ...

output:

493206
119482
243747
3831
0
30734
45299
0
84535
0
0
32866
0
0
0
0
0
0
663462
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
89699
0
76885
0
0
0
0
0
0
0
1347
0
0
0
114007
0
0
822812
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8470
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
518
0
0
946947
0
0
0
0
...

result:

ok 1000000 numbers

Test #16:

score: 0
Accepted
time: 502ms
memory: 91880kb

input:

1000000 1000000
527391 935776
928283 415193
584695 629231
364709 289656
296798 845590
807666 903716
100319 286344
880595 598376
232292 301072
465491 18715
537421 144321
773917 271368
633706 520802
140917 281422
550382 123883
348051 422164
732339 760403
883443 660056
240883 539950
301009 698713
73859...

output:

956868
480655
0
0
3595
0
0
234921
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4511
0
0
0
975
446781
0
0
0
1210
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
897203
8983
0
0
0
0
0
0
0
0
0
0
0
0
953761
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 1000000 numbers

Subtask #3:

score: 20
Accepted

Test #17:

score: 20
Accepted
time: 1343ms
memory: 105436kb

input:

999995 999997
261379 334440
985281 986034
549380 718157
670003 253925
533027 437989
326806 983213
965935 756259
229069 686789
331338 684961
957559 390618
937820 959719
338153 779814
582581 965418
634156 421264
308778 938878
913059 390904
481477 431492
739774 793015
901442 934600
256704 991485
366691...

output:

160635
633543
123519
313576
450015
383636
574186
2373
203701
326075
117994
567275
652824
199778
380317
380374
105875
373857
788346
703176
609801
648161
367059
497975
57979
478851
745054
75935
543062
251837
769828
436489
480966
235835
509625
757188
763486
396842
262680
2240
267171
165787
558963
16523...

result:

ok 999997 numbers

Test #18:

score: 0
Accepted
time: 1063ms
memory: 109868kb

input:

999995 1000000
503105 994319
301845 645636
538613 176453
944222 13642
220616 61270
445661 771824
758217 940994
11782 103262
159910 298805
317312 333018
741333 381578
579921 219986
605953 400913
625208 245340
729891 669648
186684 920562
118589 936228
281749 70955
103542 8281
854584 972667
663720 1425...

output:

8906
95485
8020
794529
288722
194571
738405
141163
47184
574675
21317
361918
336935
752285
747548
767325
485498
549919
836009
224230
243311
43089
166877
861403
1740
800031
757202
757248
571568
258896
110506
308599
111448
82706
495681
126271
557664
498332
507141
161535
251016
116433
490396
350530
854...

result:

ok 1000000 numbers

Test #19:

score: 0
Accepted
time: 1673ms
memory: 108144kb

input:

999997 1000000
44415 540937
815519 772048
580901 820033
176932 136598
26200 658165
495640 298186
350660 672003
66843 751311
886121 454924
75107 454946
855867 668594
952401 723257
914495 648341
931555 500560
451289 811080
275183 969584
28984 255298
971792 603789
290513 485349
63131 4066
4993 123137
6...

output:

629719
695599
351561
83909
248197
337451
198910
119007
163901
59655
227999
446205
417989
21251
943060
809056
530827
874242
191820
190031
801897
103766
56477
114351
865146
677995
221128
278416
622213
580214
223576
311442
602474
22418
10224
852728
546723
793775
936547
18769
695901
400642
163668
131209...

result:

ok 1000000 numbers

Test #20:

score: 0
Accepted
time: 1621ms
memory: 108436kb

input:

999995 999995
583944 643022
937405 396314
664613 53634
851937 959727
682251 262542
332058 495766
657697 254050
368945 648181
175500 409923
987447 663924
254362 212955
27186 48916
280933 263728
376404 531873
991175 304206
637107 818051
718055 603621
219979 376988
818262 602594
182634 716446
199549 42...

output:

632589
674038
421313
484901
850231
228438
726812
388070
754679
535180
282906
25258
23979
984419
946557
113528
158768
603008
400873
344667
550891
469199
301296
257606
310724
113289
667078
869781
273972
414507
36966
141760
266471
765423
406244
590218
968606
19385
46201
1519
39710
219752
427711
92415
6...

result:

ok 999995 numbers

Test #21:

score: 0
Accepted
time: 1351ms
memory: 107744kb

input:

1000000 1000000
447619 721571
584229 399494
614240 965088
204795 826646
448424 16919
866545 997174
657300 767860
490299 320401
773237 573187
494243 285955
630714 533001
811444 822428
571608 72868
490258 309897
415722 410945
967983 117451
928078 616204
939548 894410
622192 510197
568931 946541
594774...

output:

126935
145263
465828
476012
65533
42535
698958
492977
890460
175334
194482
579490
712753
695360
739259
853109
150308
228326
104307
750668
105724
512722
81223
925835
382011
92740
184439
918760
104781
443444
190528
204480
31387
835933
934756
66557
530040
18748
381135
735303
30969
306423
125340
33784
7...

result:

ok 1000000 numbers

Test #22:

score: 0
Accepted
time: 1619ms
memory: 106968kb

input:

1000000 1000000
563011 69168
799795 322619
625047 265910
302908 329651
912744 87238
944646 651913
883129 540212
154443 308737
809426 72823
394629 784304
722788 621382
600870 838097
351383 148859
863544 219752
279356 573627
168233 338737
748815 773018
779663 11919
819024 722313
784467 172146
429478 8...

output:

931763
507651
2891
279771
232600
358080
668537
179794
209284
323888
8579
28498
724380
790693
913562
742416
237268
811986
666427
110749
337341
45733
893515
541297
415398
387692
840824
806569
300977
7251
210484
844863
141462
768680
694505
368468
120097
826126
58764
335812
638189
244154
574681
705704
4...

result:

ok 1000000 numbers

Test #23:

score: 0
Accepted
time: 1675ms
memory: 107764kb

input:

999999 999998
549904 780695
952102 832337
321082 698470
315767 459429
88631 296205
224845 246509
898700 395777
277973 403130
437048 186188
393884 45421
993904 511710
94564 534733
606016 40744
294330 813572
957779 147335
315712 805921
835751 978801
764915 214826
33564 855982
174621 309776
202372 4386...

output:

174929
683585
23870
145186
591016
146066
527528
825193
571238
633087
677612
57791
250466
20273
94886
182538
544573
426519
148353
8778
283430
226442
23493
85639
27407
955906
174708
192446
139541
672132
487223
351873
370386
161299
345077
163475
831109
778917
16063
732
359442
2254
570035
292433
527730
...

result:

ok 999998 numbers

Test #24:

score: 0
Accepted
time: 1587ms
memory: 108540kb

input:

1000000 1000000
875926 620802
927410 582189
453297 27134
625927 194770
285863 198107
758448 934846
628394 508725
472741 244210
63544 906210
694594 426018
95086 100899
791006 237438
459186 660344
422538 932319
786905 189449
38062 851236
615341 58794
935296 669950
41835 430485
638425 532888
887360 956...

output:

314353
240231
222662
88736
363994
50619
459541
704120
315257
144316
755815
369269
315280
552329
382758
939953
104281
715086
891561
724596
298843
885639
44610
110591
551022
693346
436359
15173
17290
155448
18605
889862
815068
470390
238390
874503
68546
21916
704446
344934
357808
355718
103549
888118
...

result:

ok 1000000 numbers

Subtask #4:

score: 20
Accepted

Dependency #1:

100%
Accepted

Test #25:

score: 20
Accepted
time: 385ms
memory: 57260kb

input:

300000 300000
189563 143721
113019 232012
283009 152341
235960 146797
105782 100287
206719 212533
238247 192897
161513 101004
277069 129851
143907 67623
222005 158357
160618 31368
104158 90114
148304 15002
40521 169190
123876 140598
98925 113096
140488 204997
261142 106636
248565 219481
169567 27352...

output:

133975
58943
108003
271435
240472
18520
37226
64824
110443
24926
100107
57084
94462
77185
184644
44920
9569
36924
35679
185190
185985
59207
158326
295411
139708
12926
12708
66759
205320
8991
58151
18350
77099
21936
68243
193824
3369
33845
198412
152705
74697
80791
17996
195006
131057
125867
119782
4...

result:

ok 300000 numbers

Test #26:

score: 0
Accepted
time: 288ms
memory: 56360kb

input:

299996 299995
79019 129698
234860 13102
158780 130519
261477 120960
60568 211885
256377 296230
147012 276380
185086 180605
204971 176492
88129 293796
227141 23984
220343 191736
58992 215794
109290 47137
212346 145295
153762 283639
47157 61831
123097 99924
192275 67142
245853 133217
66762 222393
1151...

output:

131818
260140
3505
105184
9284
13024
251956
148517
174364
116271
35508
244852
118953
118474
103947
120727
281820
252822
180298
79580
281785
12209
210581
252212
1720
26573
27339
9033
43182
93870
263052
28232
20251
213930
3831
16733
47322
1601
11575
1448
196631
18062
199534
253177
147386
27733
84098
1...

result:

ok 299995 numbers

Test #27:

score: 0
Accepted
time: 457ms
memory: 57948kb

input:

299995 299996
188804 55811
167434 153058
154932 74503
173622 52433
26915 214178
234016 135998
15896 265764
8622 97137
227795 200595
48807 86677
33673 153470
152556 137563
266890 148077
94382 46942
282125 163817
268632 4779
234991 130657
187910 159651
79388 104610
233085 133115
150223 76879
54979 261...

output:

19418
250508
142313
50795
202976
270503
29304
38129
149746
192581
190066
194819
196136
137213
96812
14034
229385
45437
163195
236623
128107
160769
243153
98499
277308
250726
46463
246021
26467
77438
244641
158038
98826
2702
13513
127549
178416
26046
33066
57526
49752
126683
237234
111752
200579
2880...

result:

ok 299996 numbers

Test #28:

score: 0
Accepted
time: 480ms
memory: 57804kb

input:

300000 300000
287600 159144
154753 83801
270907 47305
204449 62527
191095 292913
144320 60580
93307 49515
3998 158033
282445 245654
145947 29326
92088 215104
277974 232931
26354 28648
70712 212065
10723 229150
150470 127263
9535 37547
23636 86990
236638 251737
80546 258533
262007 100054
12817 102109...

output:

247971
230684
161145
23290
227117
78047
82712
45112
32137
62021
38426
157008
60980
192430
120614
32520
155874
263799
127259
224499
38665
221398
7452
166265
51356
271847
31072
159795
233035
67072
107748
83341
22705
974
17753
83155
145154
160389
151396
210838
189311
57161
230585
21207
35195
219190
710...

result:

ok 300000 numbers

Test #29:

score: 0
Accepted
time: 393ms
memory: 56956kb

input:

299996 299998
184207 84911
287984 212458
244826 86388
197096 179170
44973 252282
172396 89784
102544 201463
22457 247915
95428 192248
85330 147275
156957 163186
54903 157709
28992 129096
163944 169142
292808 198914
1336 127387
119305 47621
148571 183483
209901 108145
251623 284161
183206 100059
1405...

output:

26149
69871
215541
1914
9018
90038
175590
120535
18222
162774
164013
118400
158442
97990
63361
175299
260728
55139
6618
3969
84166
196689
54864
39135
99707
227834
218578
214866
52660
241197
146719
21361
221940
27645
111387
19507
32703
133617
78042
283204
199994
75334
225998
287307
157383
20181
25588...

result:

ok 299998 numbers

Test #30:

score: 0
Accepted
time: 487ms
memory: 57132kb

input:

299996 299999
77650 14898
64549 295007
73990 219923
119584 280074
11286 11441
272839 28325
123199 3684
61093 88515
289951 214024
173865 243628
4479 136903
57898 46525
255260 212810
55907 23912
22768 241324
278290 242498
198303 64731
244399 7499
25694 122349
168625 247625
299288 255534
216462 140161
...

output:

143226
74062
207551
47856
141644
32608
33152
204761
52682
16602
171109
205983
189016
151648
5046
238148
1748
96002
76006
55690
224514
136312
148838
94901
103801
78863
33410
81183
115448
50915
3242
207678
176913
64793
83278
94525
82130
116737
206916
114406
84673
246977
173449
129299
80085
214230
5954...

result:

ok 299999 numbers

Test #31:

score: 0
Accepted
time: 505ms
memory: 62296kb

input:

299997 299997
190993 215622
243261 26985
127770 251331
111155 41690
101159 31069
29199 285927
140484 139072
135109 18256
146623 239470
158906 119232
241906 281104
263930 235599
80043 130803
265878 266345
77202 175920
289086 99035
140600 133644
169588 266548
230444 163562
94229 242491
56720 190479
18...

output:

290866
14937
13346
240114
4793
217485
129252
11210
189154
44538
249342
87105
250322
101710
188454
24352
131134
86431
82991
12889
232740
38
3237
150432
227843
33074
10172
147166
128156
7611
26151
27472
41580
3212
189958
186596
105636
3452
45187
183054
61073
41651
10288
45726
93600
140880
229014
27814...

result:

ok 299997 numbers

Test #32:

score: 0
Accepted
time: 471ms
memory: 59616kb

input:

300000 300000
148349 245555
245354 71011
149343 269464
242383 282469
148527 292294
42415 86272
13679 134550
212614 282776
233124 41381
146910 183006
137371 184324
224049 137290
234770 86628
228569 46338
218151 69152
24578 220200
106904 39810
264055 196329
13754 17665
288981 124549
259685 40701
28486...

output:

49781
296960
75532
229085
23875
75341
209
195487
138057
129109
154280
11922
15783
83877
223219
209219
113978
167906
175343
11182
71695
137117
241246
136477
110931
67885
4617
194285
128747
128736
260623
257512
62455
40155
14234
128411
137319
239092
46829
270200
39346
145983
59972
237948
2435
94043
17...

result:

ok 300000 numbers

Subtask #5:

score: 20
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #33:

score: 20
Accepted
time: 1615ms
memory: 104360kb

input:

1000000 1000000
527057 870207
62318 386643
246170 135479
15332 814242
853607 819602
661978 135735
727369 794653
239840 417449
193844 180967
670319 953449
121632 133189
285718 675312
847342 857660
911443 348634
406484 665426
619413 738374
973660 487875
897975 628981
95320 336373
986146 440494
3686 94...

output:

502709
4378
804347
507197
656721
683800
211837
352494
334034
28662
284894
44128
243285
625969
740241
116139
511373
481852
748418
625156
761625
259293
240159
800284
689841
759271
13511
562433
702391
862275
797302
227007
851791
39559
701291
648410
647927
14723
523006
307469
47111
238828
556956
36718
7...

result:

ok 1000000 numbers

Test #34:

score: 0
Accepted
time: 1168ms
memory: 109248kb

input:

999995 999995
651426 945699
52015 238214
238275 707060
262561 650406
404029 633378
565481 439014
620894 277882
247543 395877
162004 888838
725881 416730
806616 166296
762831 393381
841471 499284
25217 101250
938073 783236
329564 25932
449295 875959
8096 827567
643696 983358
522425 984422
56637 86636...

output:

9092
207936
425852
757131
799946
376518
81987
754069
760927
81515
222428
575155
609094
310274
149960
341223
28833
239919
138056
741463
537762
156371
295339
226286
722268
820236
109150
641793
441461
727458
128425
7281
328093
229566
464965
489736
790448
341977
683694
507573
82312
67400
766412
307058
4...

result:

ok 999995 numbers

Test #35:

score: 0
Accepted
time: 1992ms
memory: 107844kb

input:

1000000 1000000
915997 131080
726227 905570
841366 651450
538411 316570
604986 331082
952930 434524
143432 872327
381396 912926
720075 172654
955541 78683
13121 624658
220933 747962
674038 56596
816103 280152
270936 857687
796820 942714
568780 58054
570516 983834
985449 315859
376149 566354
232356 1...

output:

205002
585811
69514
283743
81143
241116
491527
167262
550457
814491
120554
3084
263099
175998
606126
778266
560021
305114
357121
981740
68073
70717
841862
299422
398614
300305
848999
695136
842425
164137
488744
711655
422105
583719
508084
243725
782787
339452
285660
512423
946491
137361
328938
22332...

result:

ok 1000000 numbers

Test #36:

score: 0
Accepted
time: 1876ms
memory: 107056kb

input:

1000000 1000000
150739 751391
506983 63096
884932 547035
2190 689660
562566 369233
873150 572658
924949 271881
770661 120112
790737 467963
434143 854238
624749 804346
569889 20896
117601 570456
837159 278806
669038 311912
525719 759763
182541 391445
646745 450607
243052 500140
642649 946911
797653 3...

output:

86310
749420
712668
358213
262607
610624
727300
492258
488830
347620
542739
370304
503994
169728
87698
52948
594469
323656
647722
485956
821313
194329
218795
414885
720267
246810
99153
40160
519238
434421
846392
349741
660148
583392
169704
341771
486638
390630
73339
475144
371420
97007
79077
291446
...

result:

ok 1000000 numbers

Test #37:

score: 0
Accepted
time: 1568ms
memory: 105536kb

input:

999997 1000000
326813 836438
660095 500957
156840 970405
558934 116262
415858 656797
61423 860041
886954 894983
844315 296372
489459 75158
696873 728051
321072 858285
574682 648919
841402 813600
292157 318327
433981 808970
765509 140622
364840 899777
979697 716247
301865 908019
818981 844271
2829 46...

output:

401172
24036
860078
491660
158642
8316
577291
449545
634397
959599
207750
639137
582792
943488
83395
239020
264293
928111
559684
149714
565564
964707
12763
791158
545697
223052
753693
205382
616198
56582
549540
298422
75005
92838
142070
309100
803704
189959
440612
604506
433574
931608
201374
233945
...

result:

ok 1000000 numbers

Test #38:

score: 0
Accepted
time: 1887ms
memory: 106736kb

input:

1000000 1000000
601296 665854
297900 102700
693456 741225
493337 109330
292282 982172
347605 277869
439714 759989
285654 111360
140329 379832
154002 938339
464120 219412
436854 420216
242985 143983
980131 297922
852749 134681
338641 20120
793629 794583
891009 325638
183018 716606
847366 717225
28292...

output:

622364
281133
202654
381537
115338
744279
167290
596110
288290
83184
28083
19375
940656
428337
35841
615491
414275
871953
613438
978472
441143
44139
120116
89196
156943
596378
590732
560308
528208
252261
543122
5183
563154
742836
881228
245309
654268
838699
127361
564683
300262
265851
91295
979479
1...

result:

ok 1000000 numbers

Test #39:

score: 0
Accepted
time: 1938ms
memory: 107300kb

input:

999996 999996
664451 986455
234620 98119
901931 987296
481981 347041
434366 439392
634265 146098
374502 770738
660671 539576
289585 639612
394235 416438
694812 976442
218665 927539
423928 379357
995837 23433
311224 428187
827472 356389
220432 451241
987093 174507
904143 3613
653913 307223
275290 223...

output:

724429
56311
461374
712706
911035
119990
274914
429101
139383
118092
48853
429723
145943
770596
274687
828245
476420
452885
903907
335838
47028
729722
661
431679
484553
288376
502744
564718
666632
783048
273878
903608
158530
168182
250804
788371
529557
592531
13671
26483
718098
755560
562307
788883
...

result:

ok 999996 numbers

Test #40:

score: 0
Accepted
time: 1912ms
memory: 107600kb

input:

1000000 1000000
423538 12107
844589 986915
204379 601010
259635 728575
693823 306312
869741 616130
33447 238212
826190 129937
378701 326026
653161 810500
789874 30196
60365 436695
900410 911414
399765 74105
9128 469233
684448 50577
34763 681794
704502 397391
601963 509690
971052 394111
452656 216032...

output:

153867
391294
280811
717687
897510
107194
924308
910198
144743
642641
356450
590073
296495
512804
719906
127642
551174
275769
280771
148931
197239
652727
5633
35306
969569
389879
447970
840639
459667
228206
207029
960669
31049
377246
665922
548519
236350
284122
781097
412781
756292
397488
186894
528...

result:

ok 1000000 numbers