QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#519000#6403. Master of PolygonpanzyAC ✓1036ms60660kbC++2015.9kb2024-08-14 15:14:472024-08-14 15:14:48

Judging History

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

  • [2024-08-14 15:14:48]
  • 评测
  • 测评结果:AC
  • 用时:1036ms
  • 内存:60660kb
  • [2024-08-14 15:14:47]
  • 提交

answer

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=200005,M=200005,K=17,inf=~0U>>1;
int n,m,cq,i,xl,xr;
bool ans[M];
int idseg[K][N],idque[K][M];
struct P{
  int x,y;
  P(){}
  P(int _x,int _y){x=_x,y=_y;}
  P operator-(const P&b)const{return P(x-b.x,y-b.y);}
  P operator+(const P&b)const{return P(x+b.x,y+b.y);}
  ll operator*(const P&b)const{return 1LL*x*b.x+1LL*y*b.y;}
  bool operator==(const P&b)const{return x==b.x&&y==b.y;}
  void read(){scanf("%d%d",&x,&y);}
}a[N];
struct Line{
  P a,b;
  int xl,xr;
  int sx,sy,dx,dy;
  ll base;
  void fix(){
    if(a.x>b.x)swap(a,b);
    xl=a.x,xr=b.x;
    sx=a.x,sy=a.y,dx=b.x-a.x,dy=b.y-a.y;
    base=1LL*sy*dx-1LL*sx*dy;
  }
}seg[N],que[M];
struct Frac{
  ll u,d;
  Frac(){}
  Frac(ll _u,ll _d){
    u=_u,d=_d;
    if(d<0)u*=-1,d*=-1;
  }
  bool operator<(const Frac&b)const{return u*b.d<b.u*d;}
  bool operator>(const Frac&b)const{return u*b.d>b.u*d;}
  bool operator<=(const Frac&b)const{return u*b.d<=b.u*d;}
  bool operator>=(const Frac&b)const{return u*b.d>=b.u*d;}
}slo[M];
inline int sgn(ll x){
  if(x>0)return 1;
  return x?-1:0;
}
inline ll cross(const P&a,const P&b){return 1LL*a.x*b.y-1LL*a.y*b.x;}
inline void umin(int&a,int b){a>b?(a=b):0;}
inline void umax(int&a,int b){a<b?(a=b):0;}
inline Frac gety(const Line&a,int x){
  if(a.dx==0)return Frac(a.sy,1);
  return Frac(a.base+1LL*x*a.dy,a.dx);
}
inline bool point_on_segment(const P&p,const P&a,const P&b){
  return cross(b-a,p-a)==0&&(p-a)*(p-b)<=0;
}
inline bool has_intersection(const Line&A,const Line&B){
  if(!A.dx&&!A.dy)return point_on_segment(A.a,B.a,B.b);
  const P&a=A.a;
  const P&b=A.b;
  const P&p=B.a;
  const P&q=B.b;
  int d1=sgn(cross(b-a,p-a)),d2=sgn(cross(b-a,q-a));
  int d3=sgn(cross(q-p,a-p)),d4=sgn(cross(q-p,b-p));
  if(d1*d2<0&&d3*d4<0)return 1;
  if((d1==0&&point_on_segment(p,a,b))||
     (d2==0&&point_on_segment(q,a,b))||
     (d3==0&&point_on_segment(a,p,q))||
     (d4==0&&point_on_segment(b,p,q)))return 1;
  return 0;
}
namespace CaseWholeSeg{
int cnt,q[N];
inline void init(){cnt=0;}
inline void add(int x){q[++cnt]=x;}
inline bool cmpseg(int A,int B){
  const Line&p=seg[A];
  const Line&q=seg[B];
  int x=p.a==q.a?min(p.xr,q.xr):max(p.xl,q.xl);
  return gety(p,x)<gety(q,x);
}
inline void work(){sort(q+1,q+cnt+1,cmpseg);}
inline bool ask(const Line&p){
  int l=1,r=cnt,mid;
  while(l<=r){
    mid=(l+r)>>1;
    const Line&o=seg[q[mid]];
    if(has_intersection(p,o))return 1;
    int x=max(p.xl,o.xl);
    if(gety(p,x)<gety(o,x))r=mid-1;else l=mid+1;
  }
  return 0;
}
}
namespace CaseWholeQue{
int xl,xr;
int cs,idseg[N];
int cq,idque[M];
Frac yl[M],yr[M];
int cnt,cp,cl,cr,idl[N],idr[N];
P pool[N*2];
int ccur,chull;
struct Component{
  int st,en;
  bool isl,isr;
  Frac lmi,lma,rmi,rma;
  void upl(const Frac&b){
    if(!isl){
      isl=1;
      lmi=lma=b;
      return;
    }
    if(lmi>b)lmi=b;
    if(lma<b)lma=b;
  }
  void upr(const Frac&b){
    if(!isr){
      isr=1;
      rmi=rma=b;
      return;
    }
    if(rmi>b)rmi=b;
    if(rma<b)rma=b;
  }
}com[N];
struct Point{
  int x;Frac y;
  Point(){}
  Point(const P&b){x=b.x,y=Frac(b.y,1);}
  Point(int _x,const Frac&_y){x=_x,y=_y;}
}cur[N*2],hull[N*2];
inline bool cmpx(const P&a,const P&b){return a.x<b.x;}
inline void init(int _xl,int _xr){xl=_xl,xr=_xr;cs=cq=0;}
inline void addseg(int x){idseg[++cs]=x;}
inline void addque(int x){
  idque[++cq]=x;
  yl[x]=gety(que[x],xl);
  yr[x]=gety(que[x],xr);
}
inline Frac slope(const Point&a,const Point&b){//a.x<b.x
  return Frac(b.y.u*a.y.d-a.y.u*b.y.d,(b.x-a.x)*a.y.d*b.y.d);
}
namespace CaseLeft{
  inline bool cmpyl(int x,int y){return yl[x]<yl[y];}
  inline bool cmplma(int x,int y){return com[x].lma<com[y].lma;}
  inline bool cmplmi(int x,int y){return com[x].lmi>com[y].lmi;}
  inline void ext_down(int&n,Point*q,const Point&p){
    if(n&&q[n].x==p.x){
      if(q[n].y>=p.y)return;
      n--;
    }
    while(n>1&&slope(p,q[n])<=slope(q[n],q[n-1]))n--;
    q[++n]=p;
  }
  inline bool notin_down(const Point&p){
    if(chull<=1)return 1;
    if(p.x>hull[1].x)return 1;
    int l=2,r=chull-1,t=1;
    while(l<=r){
      int mid=(l+r)>>1;
      if(p.x==hull[mid].x)return p.y>=hull[mid].y;
      if(p.x>hull[mid].x)r=mid-1;else l=(t=mid)+1;
    }
    return slope(hull[t+1],p)>=slope(p,hull[t]);
  }
  inline void ext_up(int&n,Point*q,const Point&p){
    if(n&&q[n].x==p.x){
      if(q[n].y<=p.y)return;
      n--;
    }
    while(n>1&&slope(p,q[n])>=slope(q[n],q[n-1]))n--;
    q[++n]=p;
  }
  inline bool notin_up(const Point&p){
    if(chull<=1)return 1;
    if(p.x>hull[1].x)return 1;
    int l=2,r=chull-1,t=1;
    while(l<=r){
      int mid=(l+r)>>1;
      if(p.x==hull[mid].x)return p.y<=hull[mid].y;
      if(p.x>hull[mid].x)r=mid-1;else l=(t=mid)+1;
    }
    return slope(hull[t+1],p)<=slope(p,hull[t]);
  }
  inline void solve(){
    if(!cl)return;
    int i,j,k,A,B;
    sort(idque+1,idque+cq+1,cmpyl);
    sort(idl+1,idl+cl+1,cmplma);
    //left
    Frac minl;
    for(i=cq,j=cl;i;i--){
      A=idque[i];
      if(ans[A])continue;
      while(j){
        B=idl[j];
        if(com[B].lma<yl[A])break;
        if(j==cl)minl=com[B].lmi;
        else if(minl>com[B].lmi)minl=com[B].lmi;
        j--;
      }
      if(j<cl&&minl<=yl[A])ans[A]=1;
    }
    //down
    chull=0;
    for(i=j=1;i<=cq;i++){
      A=idque[i];
      if(ans[A])continue;
      while(j<=cl){
        B=idl[j];
        if(com[B].lma>=yl[A])break;
        ccur=0;
        if(com[B].isr)ext_down(ccur,cur,Point(xr,com[B].rma));
        for(k=com[B].en;k>=com[B].st;k--)ext_down(ccur,cur,pool[k]);
        ext_down(ccur,cur,Point(xl,com[B].lma));
        if(com[B].isr){
          chull=ccur;
          for(k=1;k<=ccur;k++)hull[k]=cur[k];
        }else{
          k=ccur;
          while(k>1&&notin_down(cur[k-1]))k--;
          while(chull&&hull[chull].x<=cur[k].x)chull--;
          for(;k<=ccur;k++)ext_down(chull,hull,cur[k]);
        }
        j++;
      }
      if(chull<=1)continue;
      int l=1,r=chull-1;
      if(hull[1].x==xr){
        if(hull[1].y>=yr[A]){
          ans[A]=1;
          continue;
        }
        if(chull==2)continue;
        l++;
      }
      int t=r--;
      const Frac&v=slo[A];
      //min slope(hull[t+1],hull[t]) >= v
      while(l<=r){
        int mid=(l+r)>>1;
        if(slope(hull[mid+1],hull[mid])>=v)r=(t=mid)-1;else l=mid+1;
      }
      if(slope(que[A].a,hull[t])>=slope(hull[t],que[A].b))ans[A]=1;
    }
    //up
    sort(idl+1,idl+cl+1,cmplmi);
    chull=0;
    for(i=cq,j=1;i;i--){
      A=idque[i];
      if(ans[A])continue;
      while(j<=cl){
        B=idl[j];
        if(com[B].lmi<=yl[A])break;
        ccur=0;
        if(com[B].isr)ext_up(ccur,cur,Point(xr,com[B].rmi));
        for(k=com[B].en;k>=com[B].st;k--)ext_up(ccur,cur,pool[k]);
        ext_up(ccur,cur,Point(xl,com[B].lmi));
        if(com[B].isr){
          chull=ccur;
          for(k=1;k<=ccur;k++)hull[k]=cur[k];
        }else{
          k=ccur;
          while(k>1&&notin_up(cur[k-1]))k--;
          while(chull&&hull[chull].x<=cur[k].x)chull--;
          for(;k<=ccur;k++)ext_up(chull,hull,cur[k]);
        }
        j++;
      }
      if(chull<=1)continue;
      int l=1,r=chull-1;
      if(hull[1].x==xr){
        if(hull[1].y<=yr[A]){
          ans[A]=1;
          continue;
        }
        if(chull==2)continue;
        l++;
      }
      int t=r--;
      const Frac&v=slo[A];
      while(l<=r){
        int mid=(l+r)>>1;
        if(slope(hull[mid+1],hull[mid])<=v)r=(t=mid)-1;else l=mid+1;
      }
      if(slope(que[A].a,hull[t])<=slope(hull[t],que[A].b))ans[A]=1;
    }
  }
}
namespace CaseRight{
  inline bool cmpyr(int x,int y){return yr[x]<yr[y];}
  inline bool cmprma(int x,int y){return com[x].rma<com[y].rma;}
  inline bool cmprmi(int x,int y){return com[x].rmi>com[y].rmi;}
  inline void ext_down(int&n,Point*q,const Point&p){
    if(n&&q[n].x==p.x){
      if(q[n].y>=p.y)return;
      n--;
    }
    while(n>1&&slope(q[n],p)>=slope(q[n-1],q[n]))n--;
    q[++n]=p;
  }
  inline bool notin_down(const Point&p){
    if(chull<=1)return 1;
    if(p.x<hull[1].x)return 1;
    int l=2,r=chull-1,t=1;
    while(l<=r){
      int mid=(l+r)>>1;
      if(p.x==hull[mid].x)return p.y>=hull[mid].y;
      if(p.x<hull[mid].x)r=mid-1;else l=(t=mid)+1;
    }
    return slope(hull[t],p)>=slope(p,hull[t+1]);
  }
  inline void ext_up(int&n,Point*q,const Point&p){
    if(n&&q[n].x==p.x){
      if(q[n].y<=p.y)return;
      n--;
    }
    while(n>1&&slope(q[n],p)<=slope(q[n-1],q[n]))n--;
    q[++n]=p;
  }
  inline bool notin_up(const Point&p){
    if(chull<=1)return 1;
    if(p.x<hull[1].x)return 1;
    int l=2,r=chull-1,t=1;
    while(l<=r){
      int mid=(l+r)>>1;
      if(p.x==hull[mid].x)return p.y<=hull[mid].y;
      if(p.x<hull[mid].x)r=mid-1;else l=(t=mid)+1;
    }
    return slope(hull[t],p)<=slope(p,hull[t+1]);
  }
  inline void solve(){
    if(!cr)return;
    int i,j,k,A,B;
    sort(idque+1,idque+cq+1,cmpyr);
    sort(idr+1,idr+cr+1,cmprma);
    //right
    Frac minl;
    for(i=cq,j=cr;i;i--){
      A=idque[i];
      if(ans[A])continue;
      while(j){
        B=idr[j];
        if(com[B].rma<yr[A])break;
        if(j==cr)minl=com[B].rmi;
        else if(minl>com[B].rmi)minl=com[B].rmi;
        j--;
      }
      if(j<cr&&minl<=yr[A])ans[A]=1;
    }
    //down
    chull=0;
    for(i=j=1;i<=cq;i++){
      A=idque[i];
      if(ans[A])continue;
      while(j<=cr){
        B=idr[j];
        if(com[B].rma>=yr[A])break;
        ccur=0;
        if(com[B].isl)ext_down(ccur,cur,Point(xl,com[B].lma));
        for(k=com[B].st;k<=com[B].en;k++)ext_down(ccur,cur,pool[k]);
        ext_down(ccur,cur,Point(xr,com[B].rma));
        if(com[B].isl){
          chull=ccur;
          for(k=1;k<=ccur;k++)hull[k]=cur[k];
        }else{
          k=ccur;
          while(k>1&&notin_down(cur[k-1]))k--;
          while(chull&&hull[chull].x>=cur[k].x)chull--;
          for(;k<=ccur;k++)ext_down(chull,hull,cur[k]);
        }
        j++;
      }
      if(chull<=1)continue;
      int l=1,r=chull-1;
      if(hull[1].x==xl){
        if(hull[1].y>=yl[A]){
          ans[A]=1;
          continue;
        }
        if(chull==2)continue;
        l++;
      }
      int t=r--;
      const Frac&v=slo[A];
      //min slope(hull[t],hull[t+1]) <= v
      while(l<=r){
        int mid=(l+r)>>1;
        if(slope(hull[mid],hull[mid+1])<=v)r=(t=mid)-1;else l=mid+1;
      }
      if(slope(que[A].a,hull[t])>=slope(hull[t],que[A].b))ans[A]=1;
    }
    //up
    sort(idr+1,idr+cr+1,cmprmi);
    chull=0;
    for(i=cq,j=1;i;i--){
      A=idque[i];
      if(ans[A])continue;
      while(j<=cr){
        B=idr[j];
        if(com[B].rmi<=yr[A])break;
        ccur=0;
        if(com[B].isl)ext_up(ccur,cur,Point(xl,com[B].lmi));
        for(k=com[B].st;k<=com[B].en;k++)ext_up(ccur,cur,pool[k]);
        ext_up(ccur,cur,Point(xr,com[B].rmi));
        if(com[B].isl){
          chull=ccur;
          for(k=1;k<=ccur;k++)hull[k]=cur[k];
        }else{
          k=ccur;
          while(k>1&&notin_up(cur[k-1]))k--;
          while(chull&&hull[chull].x>=cur[k].x)chull--;
          for(;k<=ccur;k++)ext_up(chull,hull,cur[k]);
        }
        j++;
      }
      if(chull<=1)continue;
      int l=1,r=chull-1;
      if(hull[1].x==xl){
        if(hull[1].y<=yl[A]){
          ans[A]=1;
          continue;
        }
        if(chull==2)continue;
        l++;
      }
      int t=r--;
      const Frac&v=slo[A];
      //min slope(hull[t],hull[t+1]) >= v
      while(l<=r){
        int mid=(l+r)>>1;
        if(slope(hull[mid],hull[mid+1])>=v)r=(t=mid)-1;else l=mid+1;
      }
      if(slope(que[A].a,hull[t])<=slope(hull[t],que[A].b))ans[A]=1;
    }
  }
}
inline void work(){
  if(!cs||!cq)return;
  int i,j,k,x;
  static int q[N];
  static bool vis[N],is[N];
  for(i=1;i<=cs;i++){
    x=idseg[i];
    is[x]=1;
    vis[x]=0;
  }
  cnt=cp=cl=cr=0;
  for(i=1;i<=cs;i++){
    x=idseg[i];
    if(vis[x])continue;
    cnt++;
    com[cnt].st=cp+1;
    com[cnt].isl=com[cnt].isr=0;
    vis[x]=1;
    int head=1,tail=1;
    q[1]=x;
    while(head<=tail){
      x=q[head++];
      const Line&p=seg[x];
      if(p.xl>xl&&p.xr<xr){
        pool[++cp]=p.a;
        pool[++cp]=p.b;
      }else if(p.xr<xr){
        if(p.xl==p.xr){
          com[cnt].upl(Frac(p.a.y,1));
          com[cnt].upl(Frac(p.b.y,1));
        }else{
          pool[++cp]=p.b;
          com[cnt].upl(gety(p,xl));
        }
      }else{
        if(p.xl==p.xr){
          com[cnt].upr(Frac(p.a.y,1));
          com[cnt].upr(Frac(p.b.y,1));
        }else{
          pool[++cp]=p.a;
          com[cnt].upr(gety(p,xr));
        }
      }
      for(j=x-1;j<=x+1;j+=2){
        k=j;
        if(k<0)k+=n;
        if(k>=n)k-=n;
        if(!is[k]||vis[k])continue;
        const P&v=j<x?a[x]:a[x+1];
        if(v.x<xl||v.x>xr)continue;
        vis[k]=1;
        q[++tail]=k;
      }
    }
    com[cnt].en=cp;
    if(com[cnt].isl)idl[++cl]=cnt;
    if(com[cnt].isr)idr[++cr]=cnt;
    sort(pool+com[cnt].st,pool+cp+1,cmpx);
  }
  for(i=1;i<=cs;i++)is[idseg[i]]=0;
  CaseLeft::solve();
  CaseRight::solve();
}
}
void solve(int o,int l,int r,int cs,int cq){
  if(l>=r||!cs||!cq)return;
  //Case 1: whole seg
  CaseWholeSeg::init();
  CaseWholeQue::init(l,r);
  for(int i=0;i<cs;i++){
    int id=idseg[o][i];
    int a=seg[id].xl,b=seg[id].xr;
    if(a<=l&&b>=r)CaseWholeSeg::add(id);
    else CaseWholeQue::addseg(id);
  }
  CaseWholeSeg::work();
  for(int i=0;i<cq;i++){
    int id=idque[o][i];
    int a=que[id].xl,b=que[id].xr;
    if(CaseWholeSeg::ask(que[id]))ans[id]=1;
    else if(a<=l&&b>=r)CaseWholeQue::addque(id);
  }
  //Case 2: whole query, partial seg
  CaseWholeQue::work();
  if(l+1==r)return;
  int mid=(l+r)>>1;
  for(int _=0;_<2;_++){
    int _l,_r,_cs=0,_cq=0;
    if(_==0)_l=l,_r=mid;else _l=mid,_r=r;
    for(int i=0;i<cs;i++){
      int id=idseg[o][i];
      int a=seg[id].xl,b=seg[id].xr;
      if(a<=l&&b>=r)continue;
      if(a>_r||b<_l)continue;
      idseg[o+1][_cs++]=id;
    }
    for(int i=0;i<cq;i++){
      int id=idque[o][i];
      if(ans[id])continue;
      int a=que[id].xl,b=que[id].xr;
      if(a<=l&&b>=r)continue;
      if(a>_r||b<_l)continue;
      idque[o+1][_cq++]=id;
    }
    solve(o+1,_l,_r,_cs,_cq);
  }
}
namespace CaseBothSameX{
int i,l,r,x,ce;
struct E{
  int x,y,v,p;
  E(){}
  E(int _x,int _y,int _v,int _p){x=_x,y=_y,v=_v,p=_p;}
}e[N+M];
inline bool cmpe(const E&a,const E&b){
  if(a.x!=b.x)return a.x<b.x;
  if(a.y!=b.y)return a.y<b.y;
  return a.p<b.p;
}
void solve(){
  for(i=0;i<cq;i++){
    x=idque[0][i];
    if(ans[x])continue;
    if(que[x].xl!=que[x].xr)continue;
    l=que[x].a.y,r=que[x].b.y;
    if(l>r)swap(l,r);
    e[ce++]=E(que[x].xl,r,l,x);
  }
  for(i=0;i<n;i++)if(a[i].x==a[i+1].x){
    l=a[i].y,r=a[i+1].y;
    if(l>r)swap(l,r);
    e[ce++]=E(a[i].x,l,r,-1);
  }
  sort(e,e+ce,cmpe);
  for(i=0;i<ce;i++){
    if(i==0||e[i].x!=e[i-1].x)r=-inf;
    if(e[i].p<0)umax(r,e[i].v);
    else if(r>=e[i].v)ans[e[i].p]=1;
  }
}
}
int main(){
  scanf("%d%d",&n,&m);
  xl=inf,xr=-inf;
  for(i=0;i<n;i++){
    a[i].read();
    umin(xl,a[i].x);
    umax(xr,a[i].x);
  }
  a[n]=a[0];
  for(i=0;i<n;i++){
    seg[i].a=a[i];
    seg[i].b=a[i+1];
    seg[i].fix();
    idseg[0][i]=i;
  }
  for(i=0;i<m;i++){
    que[i].a.read();
    que[i].b.read();
    que[i].fix();
    umax(que[i].xl,xl);
    umin(que[i].xr,xr);
    if(que[i].xl>que[i].xr)continue;
    if(que[i].xl==que[i].xr&&que[i].a.x!=que[i].b.x){
      if(que[i].xl==xl)que[i].a=que[i].b;
      else que[i].b=que[i].a;
      que[i].fix();
    }
    idque[0][cq++]=i;
    if(que[i].xl<que[i].xr)slo[i]=Frac(que[i].b.y-que[i].a.y,que[i].b.x-que[i].a.x);
  }
  solve(0,xl,xr,n,cq);
  CaseBothSameX::solve();
  for(i=0;i<m;i++)puts(ans[i]?"YES":"NO");
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 6
1 1
4 1
4 4
1 4
0 2 2 0
0 1 1 1
0 0 5 5
2 2 4 2
2 2 3 2
5 1 0 2

output:

YES
YES
YES
YES
NO
YES

result:

ok 6 token(s): yes count is 5, no count is 1

Test #2:

score: 0
Accepted
time: 128ms
memory: 39028kb

input:

20 200000
8838 9219
12190 11292
15953 7581
16690 6159
21104 5484
8978 1076
4354 1065
1261 676
12684 14159
15469 22416
13493 28027
15531 26837
18253 26053
26444 24253
22160 19958
24879 12856
28793 22156
25300 10245
14749 15078
12946 13942
26544 28338 18806 21279
5592 29200 20935 25253
28189 17513 215...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES...

result:

ok 200000 token(s): yes count is 156067, no count is 43933

Test #3:

score: 0
Accepted
time: 177ms
memory: 33672kb

input:

500 200000
17729 7936
17684 8099
17925 10195
17441 9150
17314 9604
17008 8764
17003 7525
16501 4085
16247 5851
16768 625
16492 706
15995 4316
16287 976
16032 629
15217 133
15692 4260
16153 6940
15550 5717
15493 4823
15085 4477
14465 4830
13595 4960
13721 3490
13309 2776
11167 3053
14319 2156
14626 2...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
Y...

result:

ok 200000 token(s): yes count is 197031, no count is 2969

Test #4:

score: 0
Accepted
time: 142ms
memory: 31364kb

input:

2000 200000
15746 1958
15965 1785
16322 2203
16779 3060
15774 2055
15869 2486
16141 3025
14987 1567
16314 3508
14816 1823
13841 1058
15595 3183
15716 4094
15939 4023
16426 4179
16507 5225
17035 6211
17233 5343
18059 5915
17140 5103
17154 4324
17471 4562
18065 5767
20733 10646
21651 12444
18707 6969
...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 199151, no count is 849

Test #5:

score: 0
Accepted
time: 180ms
memory: 50980kb

input:

2000 200000
11439 4221
11601 4531
11351 4595
10165 4725
11049 4209
9643 4623
8884 4596
8598 4376
10987 3767
10577 3606
10678 3417
10159 3481
10288 3302
11157 2781
10513 2652
10601 2489
10785 2201
9881 2932
10877 1775
9578 3034
9083 3337
8118 4188
8911 3253
10649 1785
6624 3607
6002 3749
10788 1539
8...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 200000 token(s): yes count is 1564, no count is 198436

Test #6:

score: 0
Accepted
time: 185ms
memory: 48756kb

input:

2000 200000
25931 29637
25732 29388
25090 29397
24676 29660
24268 29454
24712 28969
24252 27672
23976 28067
24211 27138
24428 27732
24389 27010
24062 26426
24278 25689
24727 26596
25281 28154
25062 26750
24927 26324
24625 25457
25456 26307
25444 25561
26008 27471
26065 27717
26065 27194
25255 24568
...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 200000 token(s): yes count is 5859, no count is 194141

Test #7:

score: 0
Accepted
time: 264ms
memory: 51596kb

input:

2000 200000
14066 4014
14235 4742
15201 5329
15389 5460
11381 3722
12856 4511
8264 2372
13039 4278
11684 3711
12888 4180
11849 3607
11431 3373
9979 2823
9099 2534
9055 2434
9393 2382
9867 2512
10315 2558
8175 1662
6480 184
5437 92
4413 100
5548 790
4362 471
4463 552
4817 748
6715 1673
5807 1562
7942...

output:

NO
YES
YES
NO
YES
NO
NO
YES
NO
YES
NO
NO
NO
YES
NO
NO
NO
YES
NO
YES
YES
YES
YES
NO
YES
YES
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
YES
NO
YES
YES
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
...

result:

ok 200000 token(s): yes count is 55692, no count is 144308

Test #8:

score: 0
Accepted
time: 199ms
memory: 51560kb

input:

2000 200000
14977 2004
14689 1703
15835 1810
16896 1690
16802 1617
16193 869
15027 1025
14890 398
15977 29
17024 621
16998 991
17114 745
18865 277
18293 764
18306 941
19319 12
17810 1554
19311 271
17748 1881
15553 3843
17271 2971
18157 1924
19839 300
19482 727
19186 1301
19603 836
19522 1061
19765 1...

output:

YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 171136, no count is 28864

Test #9:

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

input:

99966 1000
25033 23639
25334 23745
25777 23856
25534 23761
24893 23589
24648 23517
24596 23501
24535 23479
24356 23416
24269 23406
24131 23319
24905 23572
24978 23588
24418 23387
23595 23085
24070 23293
23843 23200
23484 23078
23596 23125
23438 23066
23142 22915
24265 23317
23323 22980
23624 23088
2...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 1000 token(s): yes count is 1000, no count is 0

Test #10:

score: 0
Accepted
time: 55ms
memory: 22716kb

input:

99969 1000
19235 2200
19307 2137
19620 1920
19590 1908
19486 1919
19280 2087
19260 2029
19226 2197
19147 2281
19135 2254
19095 2304
19207 2101
18981 2354
18936 2288
18943 2166
18851 2224
18697 2428
19149 2332
18976 2371
18948 2403
19134 2347
19220 2323
19196 2374
19128 2467
19084 2485
19018 2464
190...

output:

NO
NO
NO
YES
NO
NO
YES
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
N...

result:

ok 1000 token(s): yes count is 173, no count is 827

Test #11:

score: 0
Accepted
time: 50ms
memory: 42664kb

input:

99976 1000
23538 24587
23600 24898
23569 24997
23628 25053
23693 25259
23691 25126
23674 25068
23623 24923
23664 25002
23713 25142
23659 24925
23558 24571
23523 24358
23569 24559
23578 24562
23637 24783
23621 24703
23685 24932
23735 25098
23768 25199
23802 25254
23768 25186
23774 25165
23645 24685
2...

output:

YES
YES
YES
NO
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
NO
NO
YES
NO
YES
NO
YES
YES
YES
YES
NO
NO
NO
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
NO
NO
YES
YES
YES
NO
YES
NO
YES
YES
NO
NO
YES
NO
NO
NO
YES
YES
YES
NO
YES...

result:

ok 1000 token(s): yes count is 666, no count is 334

Test #12:

score: 0
Accepted
time: 70ms
memory: 23816kb

input:

199886 1000
14938 9857
14804 10006
14968 9807
14708 10115
14761 10098
14678 10167
14648 10192
14715 10150
14497 10337
14635 10227
14596 10269
14648 10256
14774 10175
14682 10266
14490 10424
14602 10339
14754 10214
14490 10489
14360 10622
14157 10755
14299 10632
14431 10511
14245 10670
14429 10473
14...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 1000 token(s): yes count is 1000, no count is 0

Test #13:

score: 0
Accepted
time: 99ms
memory: 44888kb

input:

199901 1000
1983 26999
2038 26992
2067 26988
2231 26970
2022 26966
2763 26923
2133 26996
2353 26976
2258 26995
2211 27022
2129 27045
2138 27046
2532 27004
2630 26988
3195 26898
3060 26912
3210 26895
3069 26904
2936 26918
2839 26924
2998 26888
2696 26891
2461 26909
2257 26930
1640 26991
1708 26971
18...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
N...

result:

ok 1000 token(s): yes count is 88, no count is 912

Test #14:

score: 0
Accepted
time: 85ms
memory: 30676kb

input:

199898 1000
18799 13687
18845 13550
18777 13722
18754 13747
18726 13809
18674 13927
18698 13858
18740 13747
18818 13555
18664 13906
18651 13907
18649 13898
18605 13894
18656 13746
18693 13650
18784 13527
18811 13447
18775 13570
18818 13471
18851 13382
18907 13296
18924 13316
18943 13240
18829 13393
...

output:

NO
YES
NO
NO
NO
YES
NO
YES
YES
NO
YES
NO
NO
YES
YES
YES
NO
YES
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
YES
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
...

result:

ok 1000 token(s): yes count is 235, no count is 765

Test #15:

score: 0
Accepted
time: 101ms
memory: 42528kb

input:

199886 1000
10118 8021
10120 8003
10112 8046
10126 8048
10157 8041
10255 8007
10140 8106
10114 8118
10137 8118
10284 8037
10259 8097
10381 8066
10302 8091
10209 8127
10185 8149
10199 8146
10314 8117
10340 8108
10261 8229
10328 8182
10333 8267
10377 8257
10465 8176
10416 8235
10421 8256
10400 8332
10...

output:

NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES...

result:

ok 1000 token(s): yes count is 762, no count is 238

Test #16:

score: 0
Accepted
time: 83ms
memory: 30596kb

input:

199879 1000
18589 2979
18584 2916
18708 2953
18498 2855
18498 2848
18472 2840
18436 2819
18649 2859
18521 2809
18573 2808
18386 2799
18442 2784
18486 2785
18648 2774
18360 2745
18649 2770
18730 2789
18716 2804
18731 2927
18751 2963
18855 2956
18826 2904
18833 2895
18848 2902
18851 2916
18922 2944
18...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 1000 token(s): yes count is 987, no count is 13

Test #17:

score: 0
Accepted
time: 564ms
memory: 41876kb

input:

199874 200000
8778 8537
8541 8516
8372 8496
7893 8430
7794 8429
7968 8456
7837 8443
7844 8452
8024 8493
8016 8501
8137 8518
7682 8492
7633 8489
7684 8508
7633 8520
8523 8538
8449 8539
7714 8536
7660 8547
8781 8557
7918 8557
8942 8561
9037 8578
9079 8577
9031 8586
9310 8621
9280 8625
9224 8619
8927 8...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 199974, no count is 26

Test #18:

score: 0
Accepted
time: 560ms
memory: 47440kb

input:

199886 200000
24070 3955
24089 3887
24151 3955
24147 3956
24180 3982
24256 3985
24157 3861
24147 3828
24222 3748
24287 3767
24285 3745
24363 3729
24318 3770
24341 3779
24255 3837
24336 3900
24279 3909
24359 3922
24317 3926
24267 3939
24378 3995
24420 3943
24407 4034
24419 4067
24444 4045
24442 3995
...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 199974, no count is 26

Test #19:

score: 0
Accepted
time: 529ms
memory: 53688kb

input:

199881 200000
17149 10727
17186 10704
17136 10668
17184 10671
17147 10615
17284 10700
17129 10577
17126 10568
17179 10571
17199 10594
17371 10773
17323 10689
17327 10679
17413 10826
17421 10778
17439 10828
17492 10807
17303 10623
17092 10415
17251 10535
17191 10487
17152 10442
17109 10389
17242 1051...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 199974, no count is 26

Test #20:

score: 0
Accepted
time: 638ms
memory: 59688kb

input:

199893 200000
28788 23708
28788 23330
28801 22621
28804 22517
28804 22387
28786 22396
28784 22569
28781 23598
28781 23119
28783 22714
28778 21429
28777 20858
28771 16718
28767 17297
28764 16540
28766 18109
28772 19388
28771 19492
28770 19502
28769 19226
28766 18324
28762 16664
28763 17813
28764 1860...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
N...

result:

ok 200000 token(s): yes count is 8963, no count is 191037

Test #21:

score: 0
Accepted
time: 627ms
memory: 57428kb

input:

199904 200000
13557 23580
13524 23609
13716 23354
13735 23326
13740 23301
13921 23069
13752 23250
13850 23122
14052 22875
14077 22866
14086 22868
14394 22544
14344 22584
14392 22531
14446 22470
14552 22350
14629 22258
14644 22245
14629 22234
14601 22257
14447 22436
14349 22539
14336 22552
14405 2237...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 200000 token(s): yes count is 10793, no count is 189207

Test #22:

score: 0
Accepted
time: 704ms
memory: 45880kb

input:

199870 200000
22975 15511
23102 15451
22820 15583
23109 15429
23101 15430
22892 15506
23324 15307
23281 15314
23121 15374
23050 15388
22799 15539
22979 15482
22876 15521
22872 15523
22832 15554
22817 15556
22742 15579
22602 15652
22715 15599
22609 15672
22530 15881
22528 15950
22583 15950
22675 1574...

output:

NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 200000 token(s): yes count is 15176, no count is 184824

Test #23:

score: 0
Accepted
time: 734ms
memory: 40048kb

input:

199872 200000
6841 2680
6777 3012
6771 2964
6771 2802
6730 3187
6711 3197
6665 3496
6225 5261
6648 3570
6789 3010
6795 3011
6905 2634
6902 2671
6860 2868
6680 3550
6661 3589
6628 3672
6574 3916
6434 4480
6711 3434
6900 2736
6719 3429
6894 2781
6545 4083
6542 4098
6736 3384
6846 2983
6814 3149
6689 3...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES...

result:

ok 200000 token(s): yes count is 26619, no count is 173381

Test #24:

score: 0
Accepted
time: 805ms
memory: 41432kb

input:

199886 200000
17334 6856
18139 6745
18939 6631
19422 6563
18967 6611
18584 6679
18356 6711
18268 6722
18288 6707
17584 6811
16986 6901
17560 6799
17911 6737
17903 6743
17906 6748
17569 6812
18383 6684
18655 6652
19729 6489
20434 6385
20928 6310
21502 6225
20369 6387
19566 6506
19448 6524
18628 6642
...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
YES
YES
NO
YES
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO...

result:

ok 200000 token(s): yes count is 44418, no count is 155582

Test #25:

score: 0
Accepted
time: 772ms
memory: 57564kb

input:

199864 200000
20471 23764
20465 23713
20468 23853
20478 24195
20458 23888
20467 24117
20441 23679
20441 23769
20427 23718
20422 23515
20432 23508
20416 23390
20414 23272
20404 23240
20389 23260
20440 23950
20354 23433
20374 23587
20378 23678
20432 23966
20462 24135
20402 23861
20367 23695
20336 2357...

output:

NO
NO
YES
YES
NO
NO
YES
NO
NO
YES
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
YES
YES
NO
NO
YES
NO
NO
NO
NO
YES
NO
YES
YES
YES
YES
NO
NO
NO
YES
NO
YES
NO
YES
YES
YES
NO
YES
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
YES
NO
YES
YES
NO
YES
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
YES
YE...

result:

ok 200000 token(s): yes count is 63070, no count is 136930

Test #26:

score: 0
Accepted
time: 812ms
memory: 44868kb

input:

199878 200000
10321 24028
10372 24050
10596 24130
10790 24185
10800 24171
10839 24173
10707 24135
10168 23980
10298 24015
10300 24013
10459 24057
10356 24020
10309 24000
10151 23944
10036 23902
10232 23941
10724 24123
10547 24051
10131 23901
10779 24118
10863 24147
10578 24020
10557 24013
10229 2387...

output:

YES
YES
YES
NO
NO
YES
NO
YES
NO
YES
NO
YES
YES
YES
NO
NO
NO
YES
YES
NO
NO
YES
NO
YES
YES
NO
YES
YES
NO
NO
NO
NO
YES
NO
NO
NO
YES
YES
NO
YES
NO
YES
YES
NO
NO
YES
NO
YES
NO
YES
NO
NO
YES
NO
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
YES
YES
NO
YES
YES
YES...

result:

ok 200000 token(s): yes count is 95620, no count is 104380

Test #27:

score: 0
Accepted
time: 778ms
memory: 60660kb

input:

199872 200000
12605 17615
12645 17453
12632 17499
12701 17194
12744 17002
12727 17069
12692 17096
12626 17417
12662 17044
12684 16951
12673 17024
12711 17006
12719 16970
12748 16911
12739 16878
12791 16827
12783 16797
12791 16768
12746 16830
12809 16679
12751 16774
12736 16748
12751 16700
12830 1660...

output:

NO
YES
YES
YES
NO
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
NO
NO
NO
YES
YES
YES
NO
YES
YES
YES
YES
NO
NO
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
NO
NO
YES
YES
YES
YES
NO
YES
YES
YES
NO
NO
NO
YES
NO
YES
NO
NO
YE...

result:

ok 200000 token(s): yes count is 132363, no count is 67637

Test #28:

score: 0
Accepted
time: 750ms
memory: 56804kb

input:

199883 200000
23919 20346
23562 19885
23557 19868
22944 19070
22448 18443
22350 18318
22455 18453
22964 19109
23268 19503
23335 19590
22979 19138
23326 19582
22782 18888
23046 19234
23044 19242
23414 19729
23268 19541
23069 19278
23056 19262
23108 19334
23095 19321
22905 19067
23037 19246
23197 1946...

output:

YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 166937, no count is 33063

Test #29:

score: 0
Accepted
time: 728ms
memory: 44636kb

input:

199892 200000
24403 11365
24445 11216
24472 11099
24539 10829
24577 10696
24645 10467
24649 10490
24562 10843
24535 10941
24614 10697
24534 10947
24512 11193
24474 11264
24468 11259
24466 11329
24442 11438
24424 11453
24349 11664
24388 11714
24401 11728
24409 11758
24319 11883
24254 11954
24298 1184...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
...

result:

ok 200000 token(s): yes count is 184337, no count is 15663

Test #30:

score: 0
Accepted
time: 640ms
memory: 46656kb

input:

199885 200000
25573 17804
24620 18469
25782 17666
26226 17361
25214 18061
25678 17744
25496 17879
26125 17435
26797 16972
26652 17074
26230 17382
25818 17663
26360 17298
26522 17191
26215 17400
24663 18446
26961 16901
26923 16929
25331 17998
25483 17896
26185 17429
25560 17852
24542 18545
25251 1805...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 194548, no count is 5452

Test #31:

score: 0
Accepted
time: 624ms
memory: 38620kb

input:

199864 200000
22203 12936
22118 12953
22192 12911
22456 12703
22323 12794
22151 12905
22475 12684
22332 12765
22430 12595
22332 12725
22345 12681
22233 12820
22299 12718
22525 12420
22645 12256
22565 12407
22463 12597
22402 12717
22528 12583
22549 12556
22591 12449
22649 12255
22698 12229
22652 1235...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YE...

result:

ok 200000 token(s): yes count is 198307, no count is 1693

Test #32:

score: 0
Accepted
time: 573ms
memory: 40528kb

input:

199863 200000
22050 20130
22065 20114
22174 19985
22343 19793
22265 19890
22371 19765
22430 19728
22337 19773
22456 19614
22510 19560
22586 19527
22929 19205
22847 19297
22641 19519
22930 19219
22902 19251
22905 19266
22710 19457
22580 19599
22699 19487
22585 19607
22700 19491
22399 19825
22391 1983...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 199573, no count is 427

Test #33:

score: 0
Accepted
time: 535ms
memory: 40736kb

input:

199902 200000
29212 15830
29209 15836
29376 15814
29327 15827
29390 15826
29314 15845
29426 15840
29357 15860
29408 15856
29383 15865
29304 15887
29257 15874
29272 15965
29282 15976
29164 15952
29116 15893
29145 15859
29067 15861
29022 15874
29042 15908
28955 15913
28706 15938
28646 15943
28643 1594...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 199890, no count is 110

Test #34:

score: 0
Accepted
time: 461ms
memory: 40860kb

input:

199874 200000
29188 5004
29564 5050
29973 5101
29561 5053
29859 5092
29937 5111
29680 5089
29537 5076
29988 5206
29737 5184
29696 5180
29722 5189
29841 5277
29858 5295
29958 5274
29899 5325
29956 5391
29987 5436
29971 5440
29864 5348
29898 5397
29809 5360
29525 5253
29664 5298
29799 5346
29654 5286
...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 199980, no count is 20

Test #35:

score: 0
Accepted
time: 108ms
memory: 45224kb

input:

62509 200000
1505 1
1549 2
514 2
1592 3
460 3
1634 4
487 4
1675 5
518 5
1715 6
534 6
1754 7
463 7
1792 8
472 8
1829 9
474 9
1865 10
548 10
1900 11
470 11
1934 12
519 12
1967 13
488 13
1999 14
504 14
2030 15
522 15
2060 16
458 16
2089 17
467 17
2117 18
540 18
2144 19
481 19
2170 20
472 20
2195 21
452...

output:

YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
...

result:

ok 200000 token(s): yes count is 190774, no count is 9226

Test #36:

score: 0
Accepted
time: 317ms
memory: 35220kb

input:

62509 200000
1 1505
2 1549
2 536
3 1592
3 514
4 1634
4 482
5 1675
5 508
6 1715
6 519
7 1754
7 537
8 1792
8 543
9 1829
9 550
10 1865
10 490
11 1900
11 515
12 1934
12 511
13 1967
13 500
14 1999
14 460
15 2030
15 453
16 2060
16 488
17 2089
17 481
18 2117
18 466
19 2144
19 486
20 2170
20 486
21 2195
21 ...

output:

YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YE...

result:

ok 200000 token(s): yes count is 183285, no count is 16715

Test #37:

score: 0
Accepted
time: 187ms
memory: 40612kb

input:

62509 200000
1505 1
1549 2
480 2
1592 3
454 3
1634 4
458 4
1675 5
457 5
1715 6
531 6
1754 7
473 7
1792 8
458 8
1829 9
487 9
1865 10
489 10
1900 11
487 11
1934 12
536 12
1967 13
513 13
1999 14
496 14
2030 15
510 15
2060 16
513 16
2089 17
546 17
2117 18
521 18
2144 19
456 19
2170 20
459 20
2195 21
477...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
Y...

result:

ok 200000 token(s): yes count is 177621, no count is 22379

Test #38:

score: 0
Accepted
time: 259ms
memory: 40076kb

input:

62509 200000
1 1505
2 1549
2 511
3 1592
3 494
4 1634
4 501
5 1675
5 525
6 1715
6 503
7 1754
7 462
8 1792
8 507
9 1829
9 497
10 1865
10 462
11 1900
11 473
12 1934
12 459
13 1967
13 529
14 1999
14 451
15 2030
15 505
16 2060
16 459
17 2089
17 534
18 2117
18 517
19 2144
19 451
20 2170
20 521
21 2195
21 ...

output:

YES
YES
NO
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES...

result:

ok 200000 token(s): yes count is 169835, no count is 30165

Test #39:

score: 0
Accepted
time: 265ms
memory: 43580kb

input:

62509 200000
1505 1
1549 2
528 2
1592 3
493 3
1634 4
487 4
1675 5
476 5
1715 6
462 6
1754 7
450 7
1792 8
460 8
1829 9
537 9
1865 10
452 10
1900 11
477 11
1934 12
482 12
1967 13
505 13
1999 14
507 14
2030 15
543 15
2060 16
546 16
2089 17
479 17
2117 18
469 18
2144 19
491 19
2170 20
509 20
2195 21
476...

output:

YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
Y...

result:

ok 200000 token(s): yes count is 164258, no count is 35742

Test #40:

score: 0
Accepted
time: 218ms
memory: 37732kb

input:

62509 200000
1 1505
2 1549
2 456
3 1592
3 475
4 1634
4 465
5 1675
5 508
6 1715
6 501
7 1754
7 548
8 1792
8 523
9 1829
9 487
10 1865
10 500
11 1900
11 535
12 1934
12 536
13 1967
13 453
14 1999
14 483
15 2030
15 535
16 2060
16 451
17 2089
17 540
18 2117
18 508
19 2144
19 450
20 2170
20 513
21 2195
21 ...

output:

YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
NO
...

result:

ok 200000 token(s): yes count is 164573, no count is 35427

Test #41:

score: 0
Accepted
time: 157ms
memory: 37472kb

input:

29996 200000
15000 15000
15002 15000
15002 15002
14998 15002
14998 14996
15006 14996
15006 15006
14994 15006
14994 14992
15010 14992
15010 15010
14990 15010
14990 14988
15014 14988
15014 15014
14986 15014
14986 14984
15018 14984
15018 15018
14982 15018
14982 14980
15022 14980
15022 15022
14978 15022...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 199993, no count is 7

Test #42:

score: 0
Accepted
time: 210ms
memory: 37972kb

input:

29996 200000
15000 15000
15002 15000
15002 15002
14998 15002
14998 14996
15006 14996
15006 15006
14994 15006
14994 14992
15010 14992
15010 15010
14990 15010
14990 14988
15014 14988
15014 15014
14986 15014
14986 14984
15018 14984
15018 15018
14982 15018
14982 14980
15022 14980
15022 15022
14978 15022...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
Y...

result:

ok 200000 token(s): yes count is 187218, no count is 12782

Test #43:

score: 0
Accepted
time: 277ms
memory: 40060kb

input:

29996 200000
15000 15000
15002 15000
15002 15002
14998 15002
14998 14996
15006 14996
15006 15006
14994 15006
14994 14992
15010 14992
15010 15010
14990 15010
14990 14988
15014 14988
15014 15014
14986 15014
14986 14984
15018 14984
15018 15018
14982 15018
14982 14980
15022 14980
15022 15022
14978 15022...

output:

NO
YES
YES
NO
YES
NO
YES
YES
YES
NO
YES
NO
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
NO
NO
YES
YES
NO
YES
YES
YES
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YE...

result:

ok 200000 token(s): yes count is 167181, no count is 32819

Test #44:

score: 0
Accepted
time: 324ms
memory: 41740kb

input:

29996 200000
15000 15000
15002 15000
15002 15002
14998 15002
14998 14996
15006 14996
15006 15006
14994 15006
14994 14992
15010 14992
15010 15010
14990 15010
14990 14988
15014 14988
15014 15014
14986 15014
14986 14984
15018 14984
15018 15018
14982 15018
14982 14980
15022 14980
15022 15022
14978 15022...

output:

NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
YE...

result:

ok 200000 token(s): yes count is 154155, no count is 45845

Test #45:

score: 0
Accepted
time: 370ms
memory: 36360kb

input:

29996 200000
15000 15000
15002 15000
15002 15002
14998 15002
14998 14996
15006 14996
15006 15006
14994 15006
14994 14992
15010 14992
15010 15010
14990 15010
14990 14988
15014 14988
15014 15014
14986 15014
14986 14984
15018 14984
15018 15018
14982 15018
14982 14980
15022 14980
15022 15022
14978 15022...

output:

NO
YES
NO
YES
YES
NO
YES
NO
YES
NO
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
NO
YES
YES
NO
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
YES
YES
YES
YES
NO
YES
NO
NO
NO
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 140733, no count is 59267

Test #46:

score: 0
Accepted
time: 407ms
memory: 26356kb

input:

29996 200000
15000 15000
15002 15000
15002 15002
14998 15002
14998 14996
15006 14996
15006 15006
14994 15006
14994 14992
15010 14992
15010 15010
14990 15010
14990 14988
15014 14988
15014 15014
14986 15014
14986 14984
15018 14984
15018 15018
14982 15018
14982 14980
15022 14980
15022 15022
14978 15022...

output:

NO
NO
YES
YES
YES
NO
YES
YES
NO
YES
NO
YES
YES
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
YES
NO
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
NO
NO
YES
YES
NO
NO
NO
YES
YES
NO
NO
YES
YES
YES
YES
NO
YES
NO
YES
NO
YES
YES
YES
NO
YES
NO
YES
NO
YES
NO
NO
YES
YES
YES
YES
YES
NO
YE...

result:

ok 200000 token(s): yes count is 134060, no count is 65940

Test #47:

score: 0
Accepted
time: 281ms
memory: 55540kb

input:

29996 200000
15000 15000
15002 15000
15002 15002
14998 15002
14998 14996
15006 14996
15006 15006
14994 15006
14994 14992
15010 14992
15010 15010
14990 15010
14990 14988
15014 14988
15014 15014
14986 15014
14986 14984
15018 14984
15018 15018
14982 15018
14982 14980
15022 14980
15022 15022
14978 15022...

output:

YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
NO
YES
YES
NO
YES
YES
Y...

result:

ok 200000 token(s): yes count is 170337, no count is 29663

Test #48:

score: 0
Accepted
time: 1036ms
memory: 53212kb

input:

60000 200000
0 0
1 187
2 47
3 178
4 94
5 128
6 26
7 178
8 6
9 149
10 73
11 169
12 73
13 138
14 41
15 115
16 47
17 120
18 38
19 153
20 98
21 172
22 52
23 115
24 55
25 165
26 46
27 199
28 97
29 153
30 10
31 155
32 43
33 193
34 73
35 194
36 47
37 124
38 36
39 151
40 62
41 125
42 3
43 161
44 68
45 178
4...

output:

NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO...

result:

ok 200000 token(s): yes count is 5025, no count is 194975

Test #49:

score: 0
Accepted
time: 118ms
memory: 41548kb

input:

60000 200000
0 0
174 1
63 2
110 3
43 4
161 5
34 6
192 7
70 8
125 9
1 10
185 11
61 12
106 13
28 14
137 15
39 16
192 17
11 18
138 19
61 20
131 21
23 22
133 23
64 24
103 25
66 26
121 27
18 28
112 29
9 30
183 31
78 32
126 33
34 34
179 35
38 36
118 37
0 38
114 39
1 40
124 41
35 42
141 43
20 44
172 45
16 ...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 200000 token(s): yes count is 4884, no count is 195116

Test #50:

score: 0
Accepted
time: 908ms
memory: 39028kb

input:

60000 200000
0 0
1 1165
2 748
3 1876
4 983
5 1194
6 92
7 1422
8 722
9 1176
10 312
11 1539
12 913
13 1307
14 223
15 1354
16 409
17 1926
18 26
19 1924
20 574
21 1475
22 764
23 1098
24 466
25 1620
26 523
27 1574
28 651
29 1845
30 332
31 1013
32 751
33 1816
34 624
35 1860
36 394
37 1400
38 646
39 1895
4...

output:

YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
YES
YES
NO
NO
NO
NO
YES
NO
YES
YES
YES
NO
YES
YES
NO
NO
NO
YES
YES
NO
NO
NO
YES
NO
YES
NO...

result:

ok 200000 token(s): yes count is 48995, no count is 151005

Test #51:

score: 0
Accepted
time: 114ms
memory: 34324kb

input:

60000 200000
0 0
1200 1
550 2
1694 3
918 4
1315 5
209 6
1629 7
261 8
1119 9
969 10
1078 11
567 12
1045 13
895 14
1435 15
150 16
1370 17
641 18
1780 19
220 20
1217 21
965 22
1668 23
394 24
1279 25
916 26
1292 27
69 28
1902 29
208 30
1143 31
411 32
1155 33
71 34
1636 35
916 36
1424 37
58 38
1856 39
41...

output:

NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

result:

ok 200000 token(s): yes count is 48890, no count is 151110

Test #52:

score: 0
Accepted
time: 781ms
memory: 28872kb

input:

60000 200000
0 0
1 2722
2 1087
3 3220
4 2193
5 4448
6 1623
7 3577
8 1072
9 3777
10 864
11 4598
12 716
13 2634
14 1014
15 2504
16 687
17 4319
18 997
19 3196
20 2108
21 3423
22 433
23 4200
24 2211
25 3547
26 2112
27 2541
28 437
29 2734
30 597
31 3037
32 493
33 2565
34 459
35 3151
36 1857
37 3122
38 90...

output:

YES
YES
NO
YES
YES
NO
NO
YES
YES
NO
YES
NO
NO
YES
YES
NO
NO
YES
NO
YES
YES
NO
YES
NO
YES
NO
YES
NO
NO
NO
YES
YES
NO
YES
NO
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
NO
YES
YES
YES
NO
YES
YES
NO
YES
YES
NO
YES
NO
YES
NO
YES
NO
NO
NO
YES
NO
YES
NO
NO...

result:

ok 200000 token(s): yes count is 104563, no count is 95437

Test #53:

score: 0
Accepted
time: 117ms
memory: 52752kb

input:

60000 200000
0 0
2907 1
1395 2
4230 3
886 4
4275 5
1014 6
3804 7
385 8
3618 9
1034 10
4357 11
841 12
3852 13
1984 14
3402 15
158 16
3691 17
270 18
2812 19
2241 20
4234 21
1796 22
4212 23
1987 24
2802 25
2025 26
3495 27
1797 28
4449 29
2085 30
3138 31
712 32
2739 33
2069 34
2983 35
1142 36
3349 37
19...

output:

NO
NO
NO
NO
YES
YES
NO
YES
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
YES
YES
NO
YES
NO
YES
YES
NO
YES
YES
NO
NO
NO
YES
YES
NO
YES
NO
YES
NO
YES
YES
NO
YES
NO
NO
YES
YES
YES
NO
NO
NO
NO
YES
YES
NO
YES
NO
NO
NO
NO
YES
YES
NO
NO
YES
YES
YES
NO
YES
NO
YES
NO
NO
NO
YES
YES
NO
NO
YES
NO
YES
NO
NO
YES
YES
YES
YES
NO...

result:

ok 200000 token(s): yes count is 103594, no count is 96406

Test #54:

score: 0
Accepted
time: 345ms
memory: 53088kb

input:

60000 200000
0 0
1 7093
2 4947
3 8304
4 1884
5 8590
6 4362
7 9722
8 1699
9 5710
10 4768
11 9483
12 4224
13 6861
14 4368
15 7594
16 2874
17 5459
18 2725
19 9588
20 2997
21 9585
22 494
23 8634
24 1535
25 8633
26 4926
27 8153
28 3786
29 5969
30 2877
31 6569
32 2349
33 5093
34 334
35 8103
36 85
37 9778
...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES...

result:

ok 200000 token(s): yes count is 176996, no count is 23004

Test #55:

score: 0
Accepted
time: 119ms
memory: 53388kb

input:

60000 200000
0 0
8202 1
4102 2
7942 3
2273 4
6923 5
892 6
6163 7
4193 8
7890 9
3409 10
8011 11
181 12
6293 13
1345 14
7776 15
218 16
9851 17
2944 18
9911 19
476 20
7674 21
2497 22
7733 23
4737 24
6278 25
3676 26
7333 27
628 28
6785 29
2222 30
8947 31
1867 32
9102 33
2913 34
8612 35
3373 36
9853 37
6...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES...

result:

ok 200000 token(s): yes count is 177330, no count is 22670

Test #56:

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

input:

7 24
0 0
5 0
8 3
12 0
30000 0
6 30000
0 30000
1 1 12 1
1 1 13 2
1 1 14 3
1 1 13 4
1 1 12 5
1 1 11 6
1 2 12 1
1 2 13 2
1 2 14 3
1 2 13 4
1 2 12 5
1 2 13 6
1 3 14 1
1 3 13 2
1 3 12 3
1 3 13 4
1 3 14 5
1 3 13 6
1 4 14 1
1 4 14 2
1 4 14 3
1 4 14 4
1 4 14 5
1 4 14 6

output:

YES
YES
YES
YES
NO
NO
YES
YES
YES
NO
NO
NO
YES
YES
YES
NO
NO
NO
YES
YES
NO
NO
NO
NO

result:

ok 24 token(s): yes count is 12, no count is 12

Test #57:

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

input:

3 2
1 1
3 3
3 1
2 2 4 0
4 0 2 2

output:

YES
YES

result:

ok 2 token(s): yes count is 2, no count is 0

Test #58:

score: 0
Accepted
time: 378ms
memory: 53540kb

input:

199804 200000
0 30000
20005 29750
5 29500
20010 29750
10 29500
20015 29750
15 29500
20020 29750
20 29500
20025 29750
25 29500
20030 29750
30 29500
20035 29750
35 29500
20040 29750
40 29500
20045 29750
45 29500
20050 29750
50 29500
20055 29750
55 29500
20060 29750
60 29500
20065 29750
65 29500
20070 ...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 200000 token(s): yes count is 143, no count is 199857

Test #59:

score: 0
Accepted
time: 79ms
memory: 34468kb

input:

199804 200000
30000 0
29750 20005
29500 5
29750 20010
29500 10
29750 20015
29500 15
29750 20020
29500 20
29750 20025
29500 25
29750 20030
29500 30
29750 20035
29500 35
29750 20040
29500 40
29750 20045
29500 45
29750 20050
29500 50
29750 20055
29500 55
29750 20060
29500 60
29750 20065
29500 65
29750 ...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 200000 token(s): yes count is 159, no count is 199841

Test #60:

score: 0
Accepted
time: 343ms
memory: 53308kb

input:

199804 200000
0 30000
20005 29750
5 29500
20010 29750
10 29500
20015 29750
15 29500
20020 29750
20 29500
20025 29750
25 29500
20030 29750
30 29500
20035 29750
35 29500
20040 29750
40 29500
20045 29750
45 29500
20050 29750
50 29500
20055 29750
55 29500
20060 29750
60 29500
20065 29750
65 29500
20070 ...

output:

NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
YES
YES
NO
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
YES
YES
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
YES
YES
YES
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
YES
NO
YES
YES
NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
YES
YES
NO
NO
NO
...

result:

ok 200000 token(s): yes count is 48395, no count is 151605

Test #61:

score: 0
Accepted
time: 412ms
memory: 53840kb

input:

199804 200000
30000 0
29750 20005
29500 5
29750 20010
29500 10
29750 20015
29500 15
29750 20020
29500 20
29750 20025
29500 25
29750 20030
29500 30
29750 20035
29500 35
29750 20040
29500 40
29750 20045
29500 45
29750 20050
29500 50
29750 20055
29500 55
29750 20060
29500 60
29750 20065
29500 65
29750 ...

output:

NO
NO
YES
YES
YES
NO
NO
YES
YES
YES
NO
YES
NO
YES
NO
NO
NO
YES
YES
YES
NO
NO
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
NO
NO
YES
YES
NO
YES
NO
YES
YES
YES
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
NO
NO
YES
YES
YES
NO
NO
NO
YES
YES
YES
YES
YES
NO
YES
Y...

result:

ok 200000 token(s): yes count is 144431, no count is 55569

Test #62:

score: 0
Accepted
time: 298ms
memory: 53888kb

input:

199804 200000
0 30000
20005 29750
5 29500
20010 29750
10 29500
20015 29750
15 29500
20020 29750
20 29500
20025 29750
25 29500
20030 29750
30 29500
20035 29750
35 29500
20040 29750
40 29500
20045 29750
45 29500
20050 29750
50 29500
20055 29750
55 29500
20060 29750
60 29500
20065 29750
65 29500
20070 ...

output:

YES
YES
NO
YES
YES
YES
YES
NO
NO
YES
NO
YES
NO
NO
YES
NO
NO
NO
YES
YES
YES
NO
NO
YES
YES
YES
YES
NO
YES
NO
NO
YES
NO
YES
YES
YES
YES
NO
NO
YES
YES
NO
YES
NO
YES
YES
NO
YES
YES
NO
YES
NO
NO
YES
YES
YES
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
YES
NO
NO
YES
NO
NO
YES
YES
YES
NO
NO
YES
YE...

result:

ok 200000 token(s): yes count is 95873, no count is 104127

Test #63:

score: 0
Accepted
time: 391ms
memory: 54116kb

input:

199804 200000
30000 0
29750 20005
29500 5
29750 20010
29500 10
29750 20015
29500 15
29750 20020
29500 20
29750 20025
29500 25
29750 20030
29500 30
29750 20035
29500 35
29750 20040
29500 40
29750 20045
29500 45
29750 20050
29500 50
29750 20055
29500 55
29750 20060
29500 60
29750 20065
29500 65
29750 ...

output:

YES
YES
YES
NO
NO
NO
NO
NO
YES
NO
YES
YES
YES
YES
NO
NO
NO
NO
YES
YES
YES
NO
YES
YES
YES
YES
NO
NO
YES
NO
YES
YES
NO
NO
YES
YES
YES
NO
YES
NO
NO
NO
YES
YES
NO
NO
NO
YES
NO
NO
NO
YES
YES
YES
NO
YES
NO
YES
NO
YES
NO
NO
NO
YES
YES
YES
NO
YES
NO
NO
YES
YES
NO
NO
NO
YES
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO...

result:

ok 200000 token(s): yes count is 96536, no count is 103464

Test #64:

score: 0
Accepted
time: 199ms
memory: 53496kb

input:

199804 200000
0 30000
20005 29750
5 29500
20010 29750
10 29500
20015 29750
15 29500
20020 29750
20 29500
20025 29750
25 29500
20030 29750
30 29500
20035 29750
35 29500
20040 29750
40 29500
20045 29750
45 29500
20050 29750
50 29500
20055 29750
55 29500
20060 29750
60 29500
20065 29750
65 29500
20070 ...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES...

result:

ok 200000 token(s): yes count is 192343, no count is 7657

Test #65:

score: 0
Accepted
time: 454ms
memory: 42172kb

input:

199804 200000
30000 0
29750 20005
29500 5
29750 20010
29500 10
29750 20015
29500 15
29750 20020
29500 20
29750 20025
29500 25
29750 20030
29500 30
29750 20035
29500 35
29750 20040
29500 40
29750 20045
29500 45
29750 20050
29500 50
29750 20055
29500 55
29750 20060
29500 60
29750 20065
29500 65
29750 ...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YE...

result:

ok 200000 token(s): yes count is 192495, no count is 7505