#define i128 long long
inline i128 ABS(i128 x){return x<0?-x:x;}
struct frac{
i128 x,y;
frac(){}
frac(i128 xx,i128 yy=1ll):x(xx),y(yy){
if(y<0)x=-x,y=-y;
}
friend frac operator +(frac a,frac b){return frac(a.x*b.y+a.y*b.x,a.y*b.y);}
friend frac operator -(frac a,frac b){return frac(a.x*b.y-a.y*b.x,a.y*b.y);}
friend frac operator *(frac a,frac b){return frac(a.x*b.x,a.y*b.y);}
friend frac operator /(frac a,frac b){return a*frac(b.y,b.x);}
friend bool operator <(frac a,frac b){return a.x*b.y<b.x*a.y;}
friend bool operator >(frac a,frac b){return a.x*b.y>b.x*a.y;}
friend bool operator <=(frac a,frac b){return !(a>b);}
friend bool operator >=(frac a,frac b){return !(a<b);}
friend bool operator ==(frac a,frac b){return a.x*b.y==b.x*a.y;}
friend bool operator !=(frac a,frac b){return !(a==b);}
frac operator - () {return frac(0)-x;}
};
struct P{
int x,y;
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));}
};
const double eps=1e-10,pi=3.14159265358979323846;
struct P{
double x,y;
P(double x=0,double 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 *=(double o){return x*=o,y*=o,*this;}
P&operator /=(double 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,double b){return a*=b;}
friend P operator /(P a,double b){return a/=b;}
friend bool operator <(P a,P b){return fabs(a.x-b.x)<eps?a.y<b.y:a.x<b.x;}
friend double operator *(P a,P b){return a.x*b.x+a.y*b.y;} // dot
friend double operator %(P a,P b){return a.x*b.y-a.y*b.x;} // cross
inline void spin(double o){double s=sin(o),c=cos(o),xx=x*c-y*s,yy=x*s-y*c;x=xx,y=yy;}
inline double ang(){return atan2(y,x);}
inline double l(){return sqrt((*this)*(*this));}
void in(){cin>>x>>y;}
};
inline double d(P a,P b){return (a-b).l();}
struct line{
P a,b;double c;
line(){}
line(P a,P b):a(a),b(b){c=b.ang();}
friend P operator * (line a,line b){return a.a+a.b*(b.b%(a.a-b.a)/(a.b%b.b));}
friend bool operator <(line a,line b){return fabs(a.c-b.c)<eps?(b.a-a.a)%a.b<0:a.c<b.c;}
};
P dir(line a){
return a.b/(a.b.l());
}
double dis(line a,P b){
return (((b-a.a)%a.b)/(a.b.l()));
}
struct cir{
P o; double r;
bool operator <(const cir&b)const{return r<b.r;}
};
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])<eps) 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])<eps) p.pop_back();
if(i)p.pb(o[i]);
}
return p;
}
vector<P>halfplane(vector<line>l)
{
vector<P>res;
sort(l.begin(),l.end());
deque<P>p; deque<line>q;
for(auto o:l){
while(p.size()&&(p.back()-o.a)%o.b>0) q.pop_back(),p.pop_back();
while(p.size()&&(p.front()-o.a)%o.b>0)q.pop_front(),p.pop_front();
if (q.size()&&fabs(o.b%q.back().b)<eps){
if (fabs(o.b.ang()-q.back().b.ang()) > eps)
return p.clear(),res;
q.pop_back(); if(p.size())p.pop_back();
}
if(q.size())p.pb(q.back()*o); q.pb(o);
}
while(p.size()&&(p.back()-q.front().a)%(q.front().b)>0)
q.pop_back(),p.pop_back();
if(q.size()<3)p.clear();
else p.pb(q.front()*q.back());
while(p.size())res.pb(p.front()),p.pop_front();
return res;
}