QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#515272#9172. Alternating CycleCrysflyAC ✓45ms49680kbC++177.0kb2024-08-11 16:40:462024-08-11 16:40:47

Judging History

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

  • [2024-08-11 16:40:47]
  • 评测
  • 测评结果:AC
  • 用时:45ms
  • 内存:49680kb
  • [2024-08-11 16:40:46]
  • 提交

answer

// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define int long long
#define ull unsigned long long

using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define mod 998244353
struct modint{
  int x;
  modint(int o=0){x=o;}
  modint &operator = (int o){return x=o,*this;}
  modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
  modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
  modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
  modint &operator ^=(int b){
    modint a=*this,c=1;
    for(;b;b>>=1,a*=a)if(b&1)c*=a;
    return x=c.x,*this;
  }
  modint &operator /=(modint o){return *this *=o^=mod-2;}
  friend modint operator +(modint a,modint b){return a+=b;}
  friend modint operator -(modint a,modint b){return a-=b;}
  friend modint operator *(modint a,modint b){return a*=b;}
  friend modint operator /(modint a,modint b){return a/=b;}
  friend modint operator ^(modint a,int b){return a^=b;}
  friend bool operator ==(modint a,modint b){return a.x==b.x;}
  friend bool operator !=(modint a,modint b){return a.x!=b.x;}
  bool operator ! () {return !x;}
  modint operator - () {return x?mod-x:0;}
  bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}

vector<modint> fac,ifac,iv;
inline void initC(int n)
{
  if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
  int m=iv.size(); ++n;
  if(m>=n)return;
  iv.resize(n),fac.resize(n),ifac.resize(n);
  For(i,m,n-1){
    iv[i]=iv[mod%i]*(mod-mod/i);
    fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
  }
}
inline modint C(int n,int m){
  if(m<0||n<m)return 0;
  return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 800005
#define inf 0x3f3f3f3f

struct P{
  int x,y,id;
  P(int x=0,int y=0):x(x),y(y){}
  P&operator +=(P o){return x+=o.x,y+=o.y,*this;}
  P&operator -=(P o){return x-=o.x,y-=o.y,*this;}
  P&operator *=(int o){return x*=o,y*=o,*this;}
  P&operator /=(int o){return x/=o,y/=o,*this;}
  friend P operator +(P a,P b){return a+=b;}
  friend P operator -(P a,P b){return a-=b;}
  friend P operator *(P a,int b){return a*=b;}
  friend P operator /(P a,int b){return a/=b;}
  friend bool operator <(P a,P b){return a.x==b.x?a.y<b.y:a.x<b.x;}
  friend int operator %(P a,P b){return a.x*b.x+a.y*b.y;} // dot
  friend int operator *(P a,P b){return a.x*b.y-a.y*b.x;} // cross
  
  inline double ang(){return atan2(y,x);}
  inline double l(){return sqrt((*this)*(*this));}
  
  void read(){cin>>x>>y;}
  void out(){cout<<"("<<x<<","<<y<<")"<<endl;}
};

int sgn(int x){
  return x<0?-1:(x>0);
}
int cross(P a,P b,P c){
  //(a->b) ---> (a->c)
  return (b-a)*(c-a);
}
int cmp3(P a,P b,P c){
  return sgn(cross(a,b,c));
}

int n,m;
vector<P>a,b,t;
bool vis[maxn];

vector<P>convex(vector<P>o){
  sort(o.begin(),o.end());
  int n=o.size();
  vector<P>p;
  For(i,0,n-1){
    while(p.size()>1&&(p.back()-p[p.size()-2])*(o[i]-p[p.size()-2])<=0) p.pop_back();
    p.pb(o[i]);
  }
  int m=p.size();
  Rep(i,n-2,0){
    while(p.size()>m&&(p.back()-p[p.size()-2])*(o[i]-p[p.size()-2])<=0) p.pop_back();
    if(i)p.pb(o[i]);
  }
  return p;
}

void check(vector<P>o){
//  cout<<"check\n";
  int n=o.size();
  vector<int>d(n);
  For(i,0,n-1) d[i]=cmp3(o[i],o[(i+1)%n],o[(i+2)%n]);
//  For(i,0,n-1) cout<<d[i]<<" "; cout<<"\n";
  For(i,0,n-1) if(d[i]!=-d[(i+1)%n]) return;
  cout<<o.size()<<"\n";
  for(auto it:o)cout<<it.x<<" "<<it.y<<"\n";
  exit(0);
}

bool in(P p,P a,P b,P c){
  return cmp3(a,b,p)>0 && cmp3(b,c,p)>0 && cmp3(c,a,p)>0;
}

bool vis1[13],vis2[13];
vector<P>ans;
void dfs(int u){
  if(u==6){
    check(ans);
    return;
  }
  if(u%2==0){
    For(i,0,n-1) if(!vis1[i]) {
      vis1[i]=1;
      ans[u]=b[i];
      dfs(u+1);
      vis1[i]=0;
    }
  }else{
    For(i,0,m-1) if(!vis2[i]){
      vis2[i]=1;
      ans[u]=t[i];
      dfs(u+1);
      vis2[i]=0;
    }
  }
}

void solve3(){
//  for(auto it:b)it.out();puts("---b---");
//  for(auto it:t)it.out();puts("---t---");
  while(b.size()>6){
    n=b.size();
    bool fd=0;
    Rep(i,n-1,0){
      P A=b[(i+n-1)%n],B=b[i],C=b[(i+1)%n];
      bool ok=1;
      for(auto p:t)
        if(in(p,A,B,C)) ok=0;
      if(ok){
        For(j,i,n-2) b[j]=b[j+1];
        b.pop_back();
        fd=1;
        break;
      }
    }
    assert(fd);
  }
//  for(auto it:b)it.out();puts("---b---");
//  for(auto it:t)it.out();puts("---t---");
  n=b.size();
  m=t.size();
  ans.resize(6);
  dfs(0);
  puts("-1"),exit(0);
  assert(0);
}

namespace S2{

  int op[maxn],n;
  P A,B;
  vector<P>p,q;
  bool solve2(vector<P>b,vector<P>t){
    n=b.size();
    A=t[0],B=t[1];
    int c1=0,c2=0;
    For(i,0,n-1) op[i]=cmp3(A,B,b[i]),c1+=(op[i]>0),c2+=(op[i]<0);
    if(c1<=1 || c2<=1) return 0;
    For(i,0,n-1) if(op[(i+n-1)%n]==-1 && op[i]==1){
      for(int j=i;op[j]==1;j=(j+1)%n) p.pb(b[j]);
      break;
    }
    For(i,0,n-1) if(op[(i+n-1)%n]==1 && op[i]==-1){
      for(int j=i;op[j]==-1;j=(j+1)%n) q.pb(b[j]);
      break;
    }
  //  assert(p.size()>=2 && q.size()>=2);
    P p1,p2,q1,q2;
    int np=p.size(),nq=q.size();
    int j=nq-1;
    bool ok=0;
    Rep(i,np-1,0){
      while(j>=0 && cmp3(p[i],B,q[j])>0) --j;
      if(j>=0 && cmp3(p[i],A,q[j])>0){
        p1=p[i],q1=q[j];
        ok=1;
        break;
      }
    }
    if(!ok) return 0;
    j=0;
    ok=0;
    For(i,0,nq-1){
      while(j<=np-1 && cmp3(q[i],B,p[j])<0) ++j;
      if(j<=np-1 && cmp3(q[i],A,p[j])<0){
        q2=q[i],p2=p[j];
        ok=1;
        break;
      }
    }
    if(!ok) return 0;
    vector<P>tmp={p1,A,q2,p2,B,q1};
    For(i,0,5)For(j,i+1,5)if(tmp[i].id==tmp[j].id) return 0;
    check(tmp);
    return 0;
  }
  
}

signed main()
{
//  freopen("data.in","r",stdin);
//  freopen("my.out","w",stdout);
  n=read();
  a.resize(n);
  For(i,0,n-1)a[i].x=read(),a[i].y=read(),a[i].id=i;
  b=convex(a);
  for(auto t:b) vis[t.id]=1;
  int cnt=0;
  For(i,0,n-1)cnt+=(!vis[i]);
  if(cnt<=1){
    puts("-1");
    exit(0);
  }
  vector<P>aa;
  for(auto t:a) if(!vis[t.id] && aa.size()<3) aa.pb(t);
  ::t=aa;
  if(cnt==2){
    S2::solve2(b,t);
    puts("-1");
    exit(0);
  }
  For(i,0,2) For(j,i+1,2) S2::solve2(b,vector<P>{t[i],t[j]});
  solve3();
  return 0;
}
/*
6
0 0 
2 0
1 10
-10 -1
10 -1
1 1

10
5 7
6 6
8 3
2 2
4 2
3 5
7 6
10 4
1 5
9 3
1
3 7 4 8
*/

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3832kb

input:

6
10 15
20 15
15 23
0 31
15 0
30 30

output:

6
0 31
10 15
15 0
20 15
30 30
15 23

result:

ok Everything ok

Test #2:

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

input:

4
0 0
0 1
1 0
1 1

output:

-1

result:

ok Everything ok

Test #3:

score: 0
Accepted
time: 1ms
memory: 5668kb

input:

9
693150551 810053304
26684055 999173154
767007508 725151476
697948407 601311897
593914132 156628727
294286621 249587903
361249906 42266067
110658137 698550461
923704821 886066345

output:

6
26684055 999173154
693150551 810053304
923704821 886066345
767007508 725151476
593914132 156628727
697948407 601311897

result:

ok Everything ok

Test #4:

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

input:

9
870407732 947373192
362190573 311657719
792350850 916217578
908809410 529664178
147184624 105531482
800863654 27569449
290489622 819212758
64484618 355712627
474856219 425123887

output:

6
147184624 105531482
362190573 311657719
800863654 27569449
290489622 819212758
792350850 916217578
870407732 947373192

result:

ok Everything ok

Test #5:

score: 0
Accepted
time: 1ms
memory: 5680kb

input:

9
47664912 379660370
66293309 34207701
186290410 443720168
456106901 458016459
995422410 349401528
602407977 731922069
588325559 932595937
608245683 644278574
657411398 627744942

output:

6
47664912 379660370
186290410 443720168
588325559 932595937
602407977 731922069
995422410 349401528
456106901 458016459

result:

ok Everything ok

Test #6:

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

input:

9
224922093 516980257
696767119 51724974
580229972 266190050
593338977 91401448
843660194 888238866
108985009 509903616
591194203 709542627
225635675 932844521
618628214 461769776

output:

6
108985009 509903616
224922093 516980257
593338977 91401448
580229972 266190050
843660194 888238866
591194203 709542627

result:

ok Everything ok

Test #7:

score: 0
Accepted
time: 1ms
memory: 5588kb

input:

9
107211982 359332853
695837148 142871176
605573313 162288860
509232688 314721021
396930687 132108911
205496625 287885162
183997430 822925807
474429448 221410467
801183393 664390830

output:

6
396930687 132108911
605573313 162288860
695837148 142871176
107211982 359332853
509232688 314721021
801183393 664390830

result:

ok Everything ok

Test #8:

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

input:

9
284469163 791620032
31343664 160388450
294480166 689791450
351497471 948106011
245168471 81011666
7040948 65866709
481833366 304905205
91819440 215009122
983738573 203448372

output:

6
7040948 65866709
294480166 689791450
351497471 948106011
481833366 304905205
983738573 203448372
91819440 215009122

result:

ok Everything ok

Test #9:

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

input:

9
461726344 560343699
661817474 882938432
319823507 217294040
562358475 876458292
93406256 619849004
513617981 138815548
484702011 418288384
340613213 503575069
534889971 406069427

output:

6
93406256 619849004
461726344 560343699
661817474 882938432
484702011 418288384
513617981 138815548
340613213 503575069

result:

ok Everything ok

Test #10:

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

input:

9
638983525 992630879
660887503 900455706
713763069 113392850
404623258 99777864
646676749 863719050
315162304 548200875
782537947 195235074
958003206 160737235
422477859 945126970

output:

6
638983525 992630879
646676749 863719050
422477859 945126970
958003206 160737235
782537947 195235074
713763069 113392850

result:

ok Everything ok

Test #11:

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

input:

9
521273414 129950765
291361311 623005687
107702630 935862733
320516969 733162854
494914533 812621805
453143117 621149714
711777663 308618254
206796978 449303183
678661966 147748023

output:

6
107702630 935862733
291361311 623005687
521273414 129950765
453143117 621149714
494914533 812621805
320516969 733162854

result:

ok Everything ok

Test #12:

score: 0
Accepted
time: 1ms
memory: 5680kb

input:

8
563402439 725563321
430451262 152240853
780848346 860389268
888894820 499849356
415818421 408692535
840472921 429397462
326582722 561795426
53848834 517062841

output:

6
53848834 517062841
563402439 725563321
780848346 860389268
415818421 408692535
430451262 152240853
326582722 561795426

result:

ok Everything ok

Test #13:

score: 0
Accepted
time: 1ms
memory: 5652kb

input:

8
740659620 157850500
839586707 169758127
469755198 387891858
436192311 428201637
264056205 652562581
936984536 838782790
624418658 970145897
966206119 805628788

output:

-1

result:

ok Everything ok

Test #14:

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

input:

8
917916801 295170387
470060516 892308109
495098540 283990668
647053314 356553918
817326699 191399918
443561568 911731629
922254594 157158003
920032600 94194734

output:

-1

result:

ok Everything ok

Test #15:

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

input:

8
800206690 432490275
469130545 909825383
889038101 106460550
489318097 284906199
665564483 140302673
245105891 689713175
925123238 565508474
832389884 456389610

output:

-1

result:

ok Everything ok

Test #16:

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

input:

8
272431162 201213942
99604353 632375365
914381443 338995849
700179101 213258480
218834975 384172719
751682924 762662014
222959174 47487873
786216365 744955557

output:

-1

result:

ok Everything ok

Test #17:

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

input:

8
154721052 338533829
803707091 18488857
308321004 530061950
542443884 141610761
772105469 628042765
553227248 540643561
447166182 455838344
698573649 33521503

output:

6
154721052 338533829
542443884 141610761
698573649 33521503
308321004 530061950
553227248 540643561
772105469 628042765

result:

ok Everything ok

Test #18:

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

input:

8
331978233 475853717
434180900 741038840
997227857 57564540
384708667 774995751
620343253 871912811
354771571 950028888
450034826 937817743
947367422 322087450

output:

-1

result:

ok Everything ok

Test #19:

score: 0
Accepted
time: 1ms
memory: 5544kb

input:

8
214268122 908140896
64654708 758556113
727603907 585067131
595569671 998315324
468581038 115782857
861348604 728010435
747870762 346168213
196161194 610653397

output:

-1

result:

ok Everything ok

Test #20:

score: 0
Accepted
time: 1ms
memory: 5844kb

input:

8
686492595 45460782
63724737 776073387
121543467 776133233
142867162 926667605
21851530 359652903
589263999 800959274
45706698 828147612
108518478 267815563

output:

6
45706698 828147612
63724737 776073387
21851530 359652903
142867162 926667605
121543467 776133233
686492595 45460782

result:

ok Everything ok

Test #21:

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

input:

7
728621620 936040631
202814687 10341261
89656474 700659768
79841231 324757887
942755419 324319853
681626511 240610802
660511757 417761272

output:

-1

result:

ok Everything ok

Test #22:

score: 0
Accepted
time: 1ms
memory: 5808kb

input:

7
610911509 704764298
243353913 27858534
778563328 228162358
627138724 958142877
790993203 273222607
483170835 313559641
589751473 194707963

output:

6
243353913 27858534
483170835 313559641
627138724 958142877
610911509 704764298
778563328 228162358
589751473 194707963

result:

ok Everything ok

Test #23:

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

input:

7
493201398 842084186
242423942 750408517
172502889 755664949
132967018 550058669
639230987 812059946
284715158 91541188
887587409 308091142

output:

-1

result:

ok Everything ok

Test #24:

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

input:

7
965425871 274371364
872897751 767925791
197846230 651763759
680264510 183443658
192501480 55929991
791292191 164490026
890456054 85037832

output:

-1

result:

ok Everything ok

Test #25:

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

input:

7
847715760 116723959
871967780 490475772
591785792 179266348
522529294 111795939
40739264 4832745
592836514 647504282
188291989 198421011

output:

-1

result:

ok Everything ok

Test #26:

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

input:

7
24972940 254043847
207474297 171556557
617129133 1736230
733390297 40148220
888977050 543670083
689348130 351856901
486127925 975367703

output:

-1

result:

ok Everything ok

Test #27:

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

input:

7
907262830 686331026
206544325 894106539
11068694 897835041
575655080 968500502
442247542 787540130
195925162 129838447
783963861 88750881

output:

-1

result:

ok Everything ok

Test #28:

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

input:

7
379487302 455054693
837018135 911623813
405008255 720304923
786516083 896852783
290485327 31410175
997469486 202787286
81799797 570730280

output:

-1

result:

ok Everything ok

Test #29:

score: 0
Accepted
time: 1ms
memory: 5672kb

input:

7
261777191 887341873
467491944 634173795
430351597 247807513
628780867 825205064
475159600 275280221
135450298 685801541
11039513 684113459

output:

-1

result:

ok Everything ok

Test #30:

score: 0
Accepted
time: 1ms
memory: 5596kb

input:

6
303906216 482954428
975178114 499845449
767060824 877366757
270787644 223295346
59626998 576383660
522780101 715387654

output:

-1

result:

ok Everything ok

Test #31:

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

input:

6
776130689 620274315
15717339 885958943
792404166 773465567
818085136 151647627
612897492 115220998
324324425 493369201

output:

6
818085136 151647627
776130689 620274315
792404166 773465567
612897492 115220998
324324425 493369201
15717339 885958943

result:

ok Everything ok

Test #32:

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

input:

6
658420578 52561494
646191148 608508925
481311018 595935449
955317212 79999908
166167984 359091044
125868749 271350747

output:

-1

result:

ok Everything ok

Test #33:

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

input:

6
835677759 189881381
645261177 920993490
506654360 123438039
871210923 8352189
14405769 307993798
927413073 344299586

output:

-1

result:

ok Everything ok

Test #34:

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

input:

6
717967648 958605050
275734986 643543472
605626629 314504140
713475706 641737179
567676262 846831136
433990105 753684914

output:

-1

result:

ok Everything ok

Test #35:

score: 0
Accepted
time: 1ms
memory: 5672kb

input:

6
895224829 95924936
979837723 661060745
999566191 842006731
924336710 865056752
415914047 90701182
235534428 826633752

output:

-1

result:

ok Everything ok

Test #36:

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

input:

6
72482009 233244823
610311532 752206947
24909532 369509321
766601493 793409033
895555612 39603936
37078752 309648007

output:

-1

result:

ok Everything ok

Test #37:

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

input:

6
954771899 665532003
609381561 769724221
713816385 560575423
682495204 426794022
448826105 283473982
543655785 382596846

output:

-1

result:

ok Everything ok

Test #38:

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

input:

6
132029079 802851890
944888078 492274202
107755946 88078013
819727279 650113595
297063889 822311321
976603889 160578392

output:

-1

result:

ok Everything ok

Test #39:

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

input:

10
602781308 562877333
701561416 487042206
756931309 419120530
629114356 254957006
933207470 191192457
126399253 963963922
316265473 910569415
210683287 694898529
119806165 843088872
321184644 778828605

output:

6
756931309 419120530
602781308 562877333
316265473 910569415
629114356 254957006
321184644 778828605
126399253 963963922

result:

ok Everything ok

Test #40:

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

input:

10
27154761 353121833
449891032 344596801
998944503 631082724
371058755 936719308
98301539 223568116
531220160 248722590
887035755 435845791
264731295 872145780
142137838 447122456
209712437 121304407

output:

6
209712437 121304407
449891032 344596801
887035755 435845791
27154761 353121833
142137838 447122456
264731295 872145780

result:

ok Everything ok

Test #41:

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

input:

10
529183565 78209258
358863118 858884649
844734074 986681857
857355975 728742922
141144673 609254683
78200115 187763286
73637073 317952747
549559639 585052321
437344279 5708063
313403075 884126789

output:

-1

result:

ok Everything ok

Test #42:

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

input:

10
887959662 141207075
774214557 959048437
786535844 756120012
363734072 135827656
932278605 352075571
843543683 740796014
124326738 522077665
816593901 565359276
181703134 337284593
802372423 873446279

output:

-1

result:

ok Everything ok

Test #43:

score: 0
Accepted
time: 1ms
memory: 5660kb

input:

10
440367787 858937197
158953788 912343006
19553619 911587943
928100779 54779866
805524346 494044991
104084880 490852722
621835991 358439801
393776860 7774133
203612476 104093498
241999208 325197996

output:

6
928100779 54779866
621835991 358439801
805524346 494044991
203612476 104093498
241999208 325197996
104084880 490852722

result:

ok Everything ok

Test #44:

score: 0
Accepted
time: 1ms
memory: 5596kb

input:

10
251575389 869045585
486782434 895974003
219350983 78324415
165044239 731503960
875263719 26674969
578779162 488351425
823852191 396151213
914697742 227826853
370785241 884945445
672707889 504704582

output:

6
165044239 731503960
578779162 488351425
875263719 26674969
486782434 895974003
672707889 504704582
823852191 396151213

result:

ok Everything ok

Test #45:

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

input:

10
593765715 861374708
835541281 12864274
442025201 608543558
342340079 884735732
449667397 909608065
861230311 540048849
562748828 376522543
420019648 4009749
219227108 596777959
349343250 896136832

output:

6
593765715 861374708
442025201 608543558
219227108 596777959
861230311 540048849
562748828 376522543
420019648 4009749

result:

ok Everything ok

Test #46:

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

input:

1
1000000000 1000000000

output:

-1

result:

ok Everything ok

Test #47:

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

input:

10
202715730 138362228
141832589 276165235
43710268 797955176
338588352 338387532
845926694 663210263
987686850 91988087
461984513 60629532
720590693 430740718
759880069 943032503
590954318 56498502

output:

6
43710268 797955176
338588352 338387532
202715730 138362228
845926694 663210263
720590693 430740718
987686850 91988087

result:

ok Everything ok

Test #48:

score: 0
Accepted
time: 1ms
memory: 5812kb

input:

10
939045219 480594277
466784451 766395023
294335368 223248163
632617311 774141522
685742957 323548253
260501185 624426930
108081675 236878293
83141263 128443320
706460859 860255950
842144004 773384893

output:

6
83141263 128443320
294335368 223248163
685742957 323548253
466784451 766395023
632617311 774141522
706460859 860255950

result:

ok Everything ok

Test #49:

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

input:

8
491935955 442706242
803883719 186022944
855243629 521202777
226856400 22975550
918860057 981935058
94633866 144810804
354635903 234690664
386163606 959673403

output:

-1

result:

ok Everything ok

Test #50:

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

input:

8
486919275 983194644
51411504 6716103
754742381 955323120
325486310 361608870
170189796 485729094
967464666 615781785
800541630 441442488
457885102 461050681

output:

-1

result:

ok Everything ok

Test #51:

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

input:

8
922254594 157158003
495098540 283990668
443561568 911731629
647053314 356553918
920032600 94194734
470060516 892308109
817326699 191399918
917916801 295170387

output:

-1

result:

ok Everything ok

Test #52:

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

input:

8
832389884 456389610
489318097 284906199
889038101 106460550
665564483 140302673
800206690 432490275
925123238 565508474
469130545 909825383
245105891 689713175

output:

-1

result:

ok Everything ok

Test #53:

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

input:

8
272431162 201213942
222959174 47487873
218834975 384172719
914381443 338995849
700179101 213258480
99604353 632375365
786216365 744955557
751682924 762662014

output:

-1

result:

ok Everything ok

Test #54:

score: 0
Accepted
time: 1ms
memory: 5648kb

input:

8
685593338 833404883
633106413 167278815
505948044 107383032
823328710 283348779
945583955 814018317
264339793 985975869
195443882 71644426
847277664 544821998

output:

-1

result:

ok Everything ok

Test #55:

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

input:

100
171 43
312 271
144 606
891 209
203 193
165 386
135 662
159 323
442 766
513 339
571 302
23 759
688 770
610 730
253 669
474 480
331 807
836 877
364 55
724 716
153 70
523 359
322 468
835 482
161 524
726 378
47 304
590 240
822 611
281 869
817 815
115 783
603 350
58 529
402 579
242 167
140 902
615 35...

output:

6
268 38
312 271
989 826
16 189
144 606
152 993

result:

ok Everything ok

Test #56:

score: 0
Accepted
time: 1ms
memory: 3612kb

input:

100
272 376
278 426
780 221
863 686
980 614
135 737
533 564
760 985
240 20
900 476
704 465
893 256
752 322
468 997
306 523
733 462
543 653
887 508
154 780
284 429
197 187
263 14
456 875
345 484
404 213
980 115
162 697
651 735
746 267
253 666
897 647
249 674
700 775
899 471
946 251
434 751
455 980
96...

output:

6
6 906
272 376
263 14
278 426
980 115
780 221

result:

ok Everything ok

Test #57:

score: 0
Accepted
time: 1ms
memory: 5588kb

input:

100
754 461
236 192
795 828
223 924
755 33
716 80
312 92
607 654
47 44
907 241
838 255
388 134
435 487
327 271
605 758
379 54
128 117
550 512
707 893
465 374
868 295
757 671
597 902
857 725
27 912
845 845
38 82
951 228
50 304
233 90
604 471
780 214
53 775
202 591
833 354
848 924
676 404
166 557
157 ...

output:

6
38 82
754 461
755 33
795 828
893 989
236 192

result:

ok Everything ok

Test #58:

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

input:

100
855 786
201 346
819 62
966 400
150 834
678 424
329 994
827 323
226 681
293 379
963 36
876 624
118 651
805 538
276 994
25 417
332 964
602 524
498 5
264 80
531 31
250 707
350 300
367 727
270 221
328 963
161 475
250 102
975 960
214 508
304 303
690 754
26 776
745 712
712 68
889 715
889 837
993 266
8...

output:

6
993 266
855 786
975 960
85 194
201 346
25 417

result:

ok Everything ok

Test #59:

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

input:

100
336 490
548 120
834 678
938 638
934 874
259 386
727 522
54 993
33 705
299 136
477 819
364 502
182 815
663 193
957 228
664 390
917 428
273 528
50 118
826 413
202 139
983 362
103 327
879 729
894 300
574 700
38 860
931 597
278 616
806 305
11 747
219 294
1000 768
48 833
599 171
302 267
482 649
820 9...

output:

6
820 975
336 490
11 747
809 1
548 120
377 53

result:

ok Everything ok

Test #60:

score: 0
Accepted
time: 1ms
memory: 5592kb

input:

100
56 194
887 275
850 905
679 496
329 293
459 730
513 805
274 42
220 348
686 281
610 228
479 381
246 367
521 468
628 90
310 984
509 273
945 159
221 231
5 119
866 868
484 10
864 354
389 970
144 609
439 428
534 253
611 479
583 272
786 730
91 960
137 223
346 387
964 954
478 894
335 66
695 81
26 922
79...

output:

6
26 922
56 194
5 119
989 457
887 275
993 151

result:

ok Everything ok

Test #61:

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

input:

100
538 519
852 660
493 520
31 973
724 713
421 81
912 333
502 704
19 364
72 38
744 390
967 879
930 913
999 354
307 945
576 965
713 739
988 545
393 964
186 445
918 984
977 46
617 380
901 972
768 688
304 546
657 638
291 974
507 301
146 146
799 411
286 383
319 388
887 73
365 997
757 239
908 125
846 630...

output:

6
31 973
538 519
14 58
967 879
852 660
995 560

result:

ok Everything ok

Test #62:

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

input:

997
122 926
287 615
720 957
18 324
449 207
668 565
250 686
320 706
896 231
416 575
402 90
454 734
745 693
836 996
840 721
248 687
580 411
625 798
467 743
17 289
927 912
436 666
186 698
121 683
512 930
984 169
191 589
142 224
120 442
693 692
93 673
31 961
642 403
360 987
915 742
257 247
429 593
826 3...

output:

6
161 996
122 926
63 978
996 1
287 615
0 0

result:

ok Everything ok

Test #63:

score: 0
Accepted
time: 2ms
memory: 3648kb

input:

9973
3904 2472
5536 267
2137 9108
6192 4652
1367 3738
6236 2969
7640 7604
2322 6264
6716 6750
4238 9244
6528 155
5473 4810
1309 8098
4412 8421
9582 3286
8852 43
3200 7702
5732 4762
1078 5216
3743 7957
1649 6545
5326 3064
8283 3822
2726 1191
6043 6696
8309 6375
57 3249
2128 642
6981 6283
5674 1432
53...

output:

6
0 0
3904 2472
9972 1
1143 9959
2137 9108
2798 9972

result:

ok Everything ok

Test #64:

score: 0
Accepted
time: 17ms
memory: 12688kb

input:

199999
70899 93334
189145 9905
39055 100651
135529 1682
191966 129411
133788 118440
108557 81172
81992 121677
132080 13626
113825 195405
54455 161851
127760 99213
27835 191098
64896 111873
87158 154946
105190 191424
109445 67916
81229 183431
75524 103095
90395 96881
75755 48719
50199 152200
43090 15...

output:

6
0 0
70899 93334
199998 1
189145 9905
21076 199996
39055 100651

result:

ok Everything ok

Test #65:

score: 0
Accepted
time: 21ms
memory: 28756kb

input:

177634
3287274 920571
1570748 9546456
403117 7797169
3921241 11461796
7865782 11568047
9958706 10045270
299508 4453299
3709554 11346142
308116 4431211
11998493 5822115
9519022 1546532
38601 5445780
947950 3247212
11259561 8439484
45887 6606987
7415090 249842
6643309 51553
3506107 778108
11911653 514...

output:

6
210955 4702170
1753711 6088063
211104 4701711
7857214 11572031
7248572 11025042
7857436 11571928

result:

ok Everything ok

Test #66:

score: 0
Accepted
time: 37ms
memory: 26156kb

input:

177634
2212510 1794011
7383567 11763726
3489460 788524
5177607 84817
371291 4277749
5002844 11877935
6059545 468
10600901 2652352
4785289 184832
10554826 2597750
9436884 1475148
7793328 11601158
4751028 195391
684113 3661692
7541378 296468
3177533 11006029
10173607 2175797
8734876 11068639
11963719 ...

output:

6
9125947 1220217
4361844 4782087
9126609 1220734
384445 7755071
3517251 5413503
384673 7755591

result:

ok Everything ok

Test #67:

score: 0
Accepted
time: 33ms
memory: 24952kb

input:

177634
3748890 11368480
8080706 540442
110130 5062688
7875090 438855
11968080 5476363
3154506 10989711
10919878 3057994
6280642 9802
11268927 3578488
11766776 4627843
5194396 81397
11611008 4231357
2586127 1457632
3412951 11165266
11732172 7472060
1062910 8917565
7621902 328282
152607 7106156
930860...

output:

6
12834 5681391
3979906 5657198
12874 5680890
11983285 5609075
7665889 5634972
11983256 5608779

result:

ok Everything ok

Test #68:

score: 0
Accepted
time: 24ms
memory: 27116kb

input:

177634
3132762 1028373
6715567 63802
1964914 9966414
11516349 4028962
437792 4129734
10535737 2575385
4374215 330895
11701818 7552422
11945548 5326122
10011878 2010215
10450631 9525146
3244095 11052456
2680563 10624416
11331236 8318875
3422846 11171655
10448347 9527738
5677620 11989416
10028003 9976...

output:

6
612580 3787392
3937752 3686202
612668 3787233
11198936 3465532
7496621 3578031
11198775 3465278

result:

ok Everything ok

Test #69:

score: 0
Accepted
time: 21ms
memory: 29484kb

input:

177634
11950899 5358615
11591073 7815705
3456026 809653
1614125 9595076
3149830 10986381
1942026 2059302
8000637 499619
9455 6275631
11072988 3274049
11743546 7440789
2607316 10562952
8791261 972838
6171908 11998866
11860737 4936179
1786440 9782041
11825881 7190108
10959877 3112882
6908800 102961
13...

output:

6
11323207 3669859
8999329 4661323
11323348 3670101
623292 8234432
2235331 7546919
623450 8234715

result:

ok Everything ok

Test #70:

score: 0
Accepted
time: 33ms
memory: 25428kb

input:

177634
9818664 1821217
8172576 11413312
500552 8002504
10248580 2255027
9120205 1215737
661162 3701275
11537781 4072926
8890232 1043081
648226 3723888
4519413 274470
10378203 9606441
6527805 34685
2903735 10803430
7668116 347272
4873969 11843689
289839 7524063
8510307 786776
962251 3226515
2758563 1...

output:

6
5627562 11985054
6163931 7079014
5627273 11985027
6926499 107016
6676644 2390685
6926218 106951

result:

ok Everything ok

Test #71:

score: 0
Accepted
time: 27ms
memory: 19208kb

input:

177633
11680781 4396798
7197327 178823
1517297 2516934
5738680 8666
11346142 8292999
1566153 9541266
1506901 2528890
10770895 2861989
11804990 7258458
5500010 11971110
1189 6096976
2535538 10501417
7074707 144044
128156 4988776
1930663 2070852
8843059 10993257
5028882 11884348
3314650 11100460
14159...

output:

-1

result:

ok Everything ok

Test #72:

score: 0
Accepted
time: 28ms
memory: 20024kb

input:

177633
11536674 4070631
9441897 1479456
9730249 1737833
2811156 1271870
2216000 10211846
9656314 10332950
8934 6267928
986272 3192095
2057521 1943781
6567878 40158
5104820 100465
3342653 11119168
10873932 2996182
11350530 8285326
9178633 10740841
9738907 1745912
1485950 9449440
11987983 6342186
1198...

output:

-1

result:

ok Everything ok

Test #73:

score: 0
Accepted
time: 22ms
memory: 20200kb

input:

177633
11862557 4943035
39173 5441675
8443524 11257097
11934907 6736787
4692856 213990
7265136 11802886
2589839 1454465
4526660 11730761
5368188 11952426
2681850 10625484
8575974 828494
10999657 3168519
11409404 8179765
11779251 4664675
4471780 11710154
11457313 3912636
10734729 9186319
7713586 3664...

output:

-1

result:

ok Everything ok

Test #74:

score: 0
Accepted
time: 24ms
memory: 17968kb

input:

177633
7385242 11763147
179527 4802873
11687562 4413793
991450 8817822
2152172 1851603
8775839 11040440
34832 6528922
4827529 11830334
7700881 361057
2302827 10293053
3332170 890363
150046 4905709
294335 7535828
5346307 11948903
4915951 11855299
2486754 1543699
1717071 9707906
552515 3898746
8852998...

output:

-1

result:

ok Everything ok

Test #75:

score: 0
Accepted
time: 32ms
memory: 20880kb

input:

177633
11061069 3256620
7080256 11857016
7234429 190086
244 6041435
8930502 10930193
11471871 3940713
13752 6332450
2869702 1225614
4123 6181839
6937159 109496
11690621 4421519
6380677 11984519
4591592 11754168
1412043 9362592
10835163 9057553
2674293 1383346
11992824 6279596
11930096 5240036
262421...

output:

-1

result:

ok Everything ok

Test #76:

score: 0
Accepted
time: 26ms
memory: 29920kb

input:

177635
4881090 156864
10409464 2430973
11998360 5819169
882386 8658396
8636723 11134503
7707903 364046
11928751 6769557
3375894 11141120
442091 4120567
4178914 11587467
9383482 1429647
6299339 11151
4959230 11866809
2226246 10221528
11975195 5533788
6517366 11969227
5179943 11918216
8266887 641539
3...

output:

6
9883147 1883261
9096303 2802339
9883315 1883424
2516934 10485256
5742340 6718987
2517190 10485479

result:

ok Everything ok

Test #77:

score: 0
Accepted
time: 33ms
memory: 24660kb

input:

177635
972974 8791456
3494111 11216946
920474 3287417
4632705 11768442
127439 7010941
2778701 1297883
3672165 678003
11481145 3958799
8390389 713378
11938264 6718290
9924751 10078710
12000157 6138382
10912170 3047534
1184119 9079376
6134479 12000289
4660176 224809
2953751 1160715
5384885 47519
44807...

output:

6
1043603 8890955
1795851 7765274
1043416 8890696
6916874 104801
2512954 6692417
6915733 104540

result:

ok Everything ok

Test #78:

score: 0
Accepted
time: 30ms
memory: 29200kb

input:

177635
1586887 9564623
509052 8019407
118993 6976908
7571156 11694510
3558952 11257050
8416217 728882
5081243 105819
496054 4009077
767989 3522387
1196538 2907076
11016644 8809941
3029559 10898860
8563766 820657
4898082 152142
868247 8637022
11986285 5640983
7783040 396801
1562053 2465924
53023 6652...

output:

6
600909 8193970
738304 8186984
600812 8193793
11670214 7631884
6515439 7893475
11670353 7631543

result:

ok Everything ok

Test #79:

score: 0
Accepted
time: 33ms
memory: 27148kb

input:

177635
10980191 3141158
7147530 11838306
8936204 1076538
953366 3239356
10262294 2269702
1266677 9184878
2106446 10106697
1547028 2482967
10988637 3152997
8359072 694803
1116202 8989789
1651635 2365959
9837112 10163692
10715871 2792636
3720093 11352165
11838122 4854381
463032 7926014
762200 8470804
...

output:

6
11985154 5628634
9021306 5351998
11985196 5629085
269054 4534107
4160775 4897983
268856 4534647

result:

ok Everything ok

Test #80:

score: 0
Accepted
time: 32ms
memory: 27852kb

input:

177635
2054857 1946408
3121783 1036260
1697588 9686819
2964184 10849771
12001193 5898715
5842430 11999353
3287790 920221
11998723 6175230
7657756 342969
127726 7012077
4149093 428782
657462 3707720
700551 8368807
160183 4869297
11419757 3841886
10140015 9861730
626444 3762482
1776880 2230641
981135 ...

output:

6
1174986 2935072
2291406 4223158
1175068 2934965
8406448 11279555
6935941 9582618
8406621 11279451

result:

ok Everything ok

Test #81:

score: 0
Accepted
time: 42ms
memory: 49680kb

input:

199268
147318361 115596514
122247258 142411838
153795466 104190282
140188872 124939703
146344214 117011412
158006155 92022524
159380885 82027212
112383734 149390443
120084678 144098578
147238335 115714841
155101318 101168169
129354177 136248888
158208039 91117454
109966758 150821235
102928190 154361...

output:

6
17005250 37201681
80716504 82760501
140004160 125156239
82725298 74714795
100971701 4250982
75558005 77445213

result:

ok Everything ok

Test #82:

score: 0
Accepted
time: 36ms
memory: 45340kb

input:

199268
157749314 93085622
153214733 105420397
159316418 83207896
115299291 147518209
106078125 152892532
114481228 148059679
158985619 86597262
159428437 80252224
130082881 135563244
126071844 139213377
108271849 151759018
112958350 149034107
150785826 110028900
119063757 144864266
110961918 1502454...

output:

6
17005250 37201681
79912739 82968831
139191730 126096654
85959764 87313426
100971701 4250982
87310534 79526799

result:

ok Everything ok

Test #83:

score: 0
Accepted
time: 28ms
memory: 32812kb

input:

198699
163976049 183111313
164159670 182953639
190196298 155043364
164478439 182678765
173518370 174275539
170114645 177577425
173416784 174376496
206473768 121845540
169797914 177876207
188352517 157512685
192309380 152056578
161439933 185239502
204055411 129694468
156916340 188805818
170235040 177...

output:

6
150709537 15456616
110819573 95798518
208677030 104336419
1 104339217
98649994 112245834
57966109 193219493

result:

ok Everything ok

Test #84:

score: 0
Accepted
time: 26ms
memory: 32348kb

input:

198699
206469231 121863555
160739159 185811249
187462722 158664217
208537388 108744076
196982984 144672333
206806808 120468265
188695880 157061588
208576622 108073774
189950882 155378932
191349742 153435510
175241542 172540150
192495131 151785031
205623414 124948946
164259223 182867952
202472636 133...

output:

6
150711622 193219028
98230621 112875923
1 104339217
208677030 104336419
104393703 96857790
57964708 15458474

result:

ok Everything ok

Test #85:

score: 0
Accepted
time: 45ms
memory: 43548kb

input:

190501
246693083 128590682
204076691 207332236
214806547 196051480
234285741 168908780
242470728 150289011
220822012 188881830
245107139 140387869
239015385 159346662
233258026 170731568
238327755 160888822
222368113 186908453
208283472 203100248
243686867 146261707
241685032 152596663
245528846 138...

output:

6
13433748 76408727
121787514 117937757
99916582 3358938
125788845 114019675
224381596 184242609
112751276 127178372

result:

ok Everything ok

Test #86:

score: 0
Accepted
time: 39ms
memory: 45664kb

input:

190501
199996992 211229691
225795412 182298610
200397112 210856387
200058509 211172423
224404097 184212157
229789397 176422879
215244057 195554065
210031913 201273547
238486991 160537405
246582653 130123355
246430171 131789721
223952145 184820913
218236812 192054881
228886982 177806023
229691769 176...

output:

6
13433748 76408727
112719809 120978793
99916582 3358938
114672354 130316921
216287279 194353921
114584708 135220706

result:

ok Everything ok

Test #87:

score: 0
Accepted
time: 31ms
memory: 33080kb

input:

199267
126975607 138417358
151885321 108035832
159398466 81579544
154018234 103701678
119998282 144164135
134290263 131408579
159041961 86147474
121448401 143045174
147109293 115904832
157390684 94442217
115753833 147211907
134453752 131240224
159427885 80304101
158823861 87749989
105014095 15340969...

output:

-1

result:

ok Everything ok

Test #88:

score: 0
Accepted
time: 27ms
memory: 32960kb

input:

199267
109180963 151262728
113231024 148862842
155932009 99000789
147114867 115896646
133823466 131886268
159429211 80168596
157264958 94889158
134901187 130776655
136826463 128731914
142414280 122244207
158507448 89624046
151048074 109565592
147423494 115440465
136251817 129351041
123086329 1417336...

output:

-1

result:

ok Everything ok

Test #89:

score: 0
Accepted
time: 21ms
memory: 33428kb

input:

198698
176597541 171142853
206164404 123034251
191541533 153163032
174626022 173165060
208428643 110215295
191816370 152769904
208393853 110613508
203481289 131223322
182628994 164535976
174462110 173330519
204955500 127091727
208320341 111381328
195243591 147568208
186593017 159766617
201108198 136...

output:

-1

result:

ok Everything ok

Test #90:

score: 0
Accepted
time: 36ms
memory: 29800kb

input:

198698
184404393 162448297
174324097 173469528
192032793 152458070
191287890 153523061
180031798 167465757
161326832 185332257
175905360 171859727
196208748 145986232
172399208 175379597
176552993 171189222
175949898 171813831
192842510 151272983
195516846 147126257
197520215 143734950
208076376 113...

output:

6
150709537 15456616
109334567 107019523
208489043 109450675
1 104339217
101478808 109132850
57966109 193219493

result:

ok Everything ok

Test #91:

score: 0
Accepted
time: 25ms
memory: 29860kb

input:

190500
234790751 167985745
244154514 144509188
225405473 182841129
228954476 177703796
222380826 186891972
230633536 175095533
246022026 135136174
235684654 166303209
241254037 153788076
244583350 142762960
200808170 210470860
239127856 159088071
242362618 150618163
244553851 142888105
224757018 183...

output:

-1

result:

ok Everything ok

Test #92:

score: 0
Accepted
time: 24ms
memory: 32536kb

input:

190500
244820467 141726015
207184781 204226992
242751843 149413628
230376835 175502749
244505524 143091389
221474050 188056949
220783295 188930484
246815690 125973170
221962788 187431683
214276499 196649577
243997000 145115306
227724273 179537867
236354992 164996817
231640822 173465641
233051595 171...

output:

-1

result:

ok Everything ok

Extra Test:

score: 0
Extra Test Passed