QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#672548#5067. Two Wallsqinglu09AC ✓108ms3752kbC++238.6kb2024-10-24 17:21:242024-10-24 17:21:25

Judging History

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

  • [2024-10-24 17:21:25]
  • 评测
  • 测评结果:AC
  • 用时:108ms
  • 内存:3752kb
  • [2024-10-24 17:21:24]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
#define endl '\n'
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
typedef pair<int,int> PII;
typedef long double ld;
#define double ll
const int N=1e5+10;
const ld eps=1e-12;
#define debug(x) cout<<#x<<": "<<x<<endl

const double pi = acos(-1.0);
const double pi1=pi/180,pi2=180/pi;
double dtopi(double x) {return x*pi1;}
double pitod(double x) {return x*pi2;}


int sgn(double x) 
{
    if(fabs(x)<eps) return 0;	// x == 0, 精度范围内的近似相等
    return x>0?1:-1;			// 返回正负
}

typedef struct point 
{
    double x,y;
    point(double x = 0, double y = 0) : x(x), y(y) {}
    double operator * (point b) {return x*b.x+y*b.y;}//点乘
	double operator ^ (point b) {return x*b.y-y*b.x;}//叉乘
	point operator + (point b) {return point(x+b.x,y+b.y);}
	point operator - (point b) {return point(x-b.x,y-b.y);}
	bool operator == (const point &b) const {return sgn(x-b.x)==0&&sgn(y-b.y)==0;}
	bool operator < (const point &b) const {return sgn(x-b.x)==0?sgn(y-b.y)<0:x<b.x;}
	bool operator > (point b) {return !(*this<b);}
	point operator * (double k) {return point(k*x,k*y);}//数乘
	point operator / (double k) {return point(x/k,y/k);}//数除
    double len() {return hypot(x,y);}//模长
	double len2() {return x*x+y*y;}//模长平方
	point trunc(double r) {double l=len();r/=l;return point(x*r,y*r);}//变模长为r
	double dis(point b){return hypot(x-b.x,y-b.y);}
	double angle() {return atan2(y,x);}
	int quad() {return sgn(y)>0||sgn(y)==0&&sgn(x)>0;}//0:[-π,0)  1:[0,π)
	point unit() {return *this/len();}//单位向量
}Vector;
double len(Vector a) {return sqrt(a*a);}//模长
double len2(Vector a) {return a*a;}//模长
double dis(point a,point b) {return (a-b).len();}
double dis2(point a,point b) {return (a-b).len2();}
double norm(double x)//返回弧度[0,2π)
{
    while(x<0) x+=2*pi;
    while(x>=2*pi) x-=2*pi;
    return x;
}

double angle(Vector a,Vector b)//a到b的夹角
{
    double t=acos((a*b)/len(a)/len(b));
    return t;           // 返回 [0,π]
    //return pitod(t);  // 返回 [0,180]
}

double rad(Vector a,Vector b)//角aob弧度大小
{
	return fabs(atan2(fabs(a^b),a*b));
}

point rotleft(point a) {return point(-a.y,a.x);}//逆时针旋转90度
point rotright(point a) {return point(a.y,-a.x);}//顺时针旋转90度
point rotate(point a,point o,double angle)//点a绕点p逆时针旋转弧度angle [0,π]
{
	point v=a-o;
	double c=cos(angle),s=sin(angle);
	return point(o.x+v.x*c-v.y*s,o.y+v.x*s+v.y*c);
}
Vector Rotate(Vector a,double angle)//向量旋转弧度angle [0,π]
{
    Vector b(sin(angle),cos(angle));
    return Vector(a^b,a*b);
}

//1:  b在a的逆时针方向
//-1: b在a的顺时针方向
//2:  b与a同向共线
//-2: b在a反向共线
int cross(Vector a,Vector b)//向量b与a的方位关系
{
	int x=sgn(a^b),y=sgn(a*b);
	if(x!=0) return x;
	else return 2*y;
}
bool sameline(point a,point b,point c) {return sgn((b-a)^(c-b))==0;}//三点共线
double cross(point a,point b,point c) {return (b-a)^(c-a);}//ab叉乘ac
double dot(point a,point b,point c) {return (b-a)*(c-a);}//ab点乘ac

typedef struct line
{
	point s,e;
	line(){}
	line(point _s,point _e) {s =_s; e= _e;}
	line(point p,double angle)//点斜
	{
		s=p;
		if(sgn(angle-pi/2)==0)  e=(s+point(0,1));
		else e=(s+point(1,tan(angle)));
	}
	line(double a,double b,double c)//ax+by+c=0;
	{
		if(sgn(a)==0) {s=point(0,-c/b);e=point(1,-c/b);}
		else if(sgn(b)==0) {s=point(-c/a,0);e=point(-c/a,1);}
		else {s=point(0,-c/b);e=point(1,(-c-a)/b);}
	}
	double length() {return s.dis(e);}//线段长度
	double angle1()//返回[0,π]的基于x轴的斜倾角(弧度制)
	{
		double k=atan2(e.y-s.y,e.x-s.x);
		if(sgn(k)<0) k+=pi;
		if(sgn(k-pi)==0) k-=pi;
		return k;
	}
	double angle2()//返回(-π,π]的基于x正半轴的斜倾角(弧度制)
	{
		return atan2(e.y-s.y,e.x-s.x);
	}
}seg;

//-1: 在右侧(顺时针)
//1:  在左侧(逆时针)
//0:  在直线上
int relation_p_l(point p,line l) {return sgn((p-l.s)^(l.e-l.s));}//点与直线关系

double dis_p_l(point p,line l) {return fabs((p-l.s)^(l.e-l.s))/l.length();}//点到直线的距离

point prog(point p,line l)//点p在直线l上的投影点(垂足)
{
	point x=l.e-l.s;
	return l.s+((x*(x*(p-l.s)))/(x.len2()));
}

point mirror(point p,line l)//点p在直线l上的对称点
{
	point q=prog(p,l);
	return point(2*q.x-p.x,2*q.y-p.y);
}

bool relation_p_seg(point p,seg l)//点是否在线段上
{
	return sgn((p-l.s)^(l.e-l.s))==0&&sgn((p-l.s)*(p-l.e))<=0;
}

double dis_p_seg(point p,seg l)//点到线段的距离
{
	if(sgn((p-l.s)*(l.e-l.s))<0||sgn((p-l.e)*(l.s-l.e))<0)
		return min(p.dis(l.s),p.dis(l.e));
	return dis_p_l(p,l);
}

bool parallel(line l,line v) {return sgn((l.e-l.s)^(v.e-v.s))==0;}//判断平行

//0:  平行
//1:  共线
//-1: 相交
int relation_l_l(line l,line v)//判断两直线的位置关系
{
	if(parallel(l,v)) return relation_p_l(l.s,v)==0;
	return -1;
}

//-1: 规范相交
//1:  非规范相交(顶点处相交)
//0:  不相交
int relation_l_seg(line l,seg v)//直线与线段位置关系
{
	int d1=sgn((l.e-l.s)^(v.s-l.s));
	int d2=sgn((l.e-l.s)^(v.e-l.s));
	if((d1^d2)==-2) return -1;
	return (d1==0||d2==0);
}

//-1: 规范相交(恰有一个交点且非端点,即互相穿过)
//1:  非规范相交
//0:  不相交
int relation_seg_seg(seg l,seg v)//两线段相交判断
{
	int d1=sgn((l.e-l.s)^(v.s-l.s));
	int d2=sgn((l.e-l.s)^(v.e-l.s));
	int d3=sgn((v.e-v.s)^(l.s-v.s));
	int d4=sgn((v.e-v.s)^(l.e-v.s));
	if ((d1^d2)==-2&&(d3^d4)==-2) return -1;
	
	return (d1==0&&sgn((v.s-l.s)*(v.s-l.e))<=0)||
	(d2==0&&sgn((v.e-l.s)*(v.e-l.e))<=0)||
	(d3==0&&sgn((l.s-v.s)*(l.s-v.e))<=0)||
	(d4==0&&sgn((l.e-v.s)*(l.e-v.e))<=0);
}

double dis_seg_seg(seg l,seg v)//线段到线段的距离
{
	if(relation_seg_seg(l,v)) return 0; 
	return min(min(dis_p_seg(v.s,l),dis_p_seg(v.e,l)),min(dis_p_seg(l.s,v),dis_p_seg(l.e,v)));
}

bool lcrossl(line a,line b)//求两直线的交点(需要保证直线不平行或共线)
{	
	// double operator ^ (point b) {return x*b.y-y*b.x;}//叉乘
	point u=a.s-b.s,v=a.e-a.s,w=b.e-b.s;

	//***************************
	if((w^v)==0)//o2优化出问题的时候直接返回mle,
	{
		vector<int>q;
		while(1) q.push_back(1);
	}
	//***************************

  	return ((sgn(u^w)*sgn(w^v))>=0);
}

void solve()
{
	point a,b;
	cin>>a.x>>a.y;
	cin>>b.x>>b.y;
	point h1,h2,g1,g2;
	cin>>h1.x>>h1.y>>h2.x>>h2.y;
	cin>>g1.x>>g1.y>>g2.x>>g2.y;
	seg now(a,b),h(h1,h2),g(g1,g2);
    if(a==b)
    {
        cout<<0<<endl;
        return;
    }
	if(relation_seg_seg(now,h)==0&&relation_seg_seg(now,g)==0)
	{
		cout<<0<<endl;
	}
	else
	{
		if(relation_p_seg(h1,now)==1&&relation_p_seg(h2,now)==1&&relation_p_seg(g1,now)==1&&relation_p_seg(g2,now)==1)
		{
			cout<<1<<endl;
			return;
		}
		vector<line>A,B;
		if(relation_seg_seg(seg(a,h1),g)!=-1) A.push_back(line(a,h1));
		if(relation_seg_seg(seg(a,h2),g)!=-1) A.push_back(line(a,h2));
		if(relation_seg_seg(seg(a,g1),h)!=-1) A.push_back(line(a,g1));
		if(relation_seg_seg(seg(a,g2),h)!=-1) A.push_back(line(a,g2));
		if(relation_seg_seg(seg(b,h1),g)!=-1) B.push_back(line(b,h1));
		if(relation_seg_seg(seg(b,h2),g)!=-1) B.push_back(line(b,h2));
		if(relation_seg_seg(seg(b,g1),h)!=-1) B.push_back(line(b,g1));
		if(relation_seg_seg(seg(b,g2),h)!=-1) B.push_back(line(b,g2));
		for(auto x:A)
		{
			for(auto y:B)
			{
				if(relation_l_l(x,y)==-1)
                {
                    if(lcrossl(x,y) && lcrossl(y, x))
					{
						cout<<1<<endl;
						return;
					}
                    // Vector u=point(x.e-x.s);
                    // Vector v=point(z-x.s);
                    // Vector u1=point(y.e-y.s);
                    // Vector v1=point(z-y.s);
                    // if(sgn(u*v)>0&&sgn(u1*v1)>0)
                    // {
					// 	// debug(x.e.x);
					// 	// debug(x.e.y);
					// 	// debug(x.s.x);
					// 	// debug(x.s.y);
					// 	// debug(y.e.x);
					// 	// debug(y.e.y);
					// 	// debug(y.s.x);
					// 	// debug(y.s.y);
					// 	// debug(z.x);
					// 	// debug(z.y);
					// 	// debug(u.x);
					// 	// debug(u.y);
					// 	// debug(v.x);
					// 	// debug(v.y);
                    //     cout<<1<<endl;
                    //     return;
                    // }
                }
			}
		}
		cout<<2<<endl;
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	int T=1;
	cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0 0
1 1
2 2 3 3
4 4 5 5
0 0
1 1
2 2 3 3
2 2 3 3
0 0
10 10
10 0 0 10
1 1 2 2

output:

0
0
1

result:

ok 3 number(s): "0 0 1"

Test #2:

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

input:

2
-999999999 999999998
999999999 999999998
-1000000000 -1000000000 1000000000 1000000000
1000000000 -1000000000 -1000000000 1000000000
-999999999 999999998
999999999 999999998
-999999998 -999999998 1000000000 1000000000
999999998 -999999998 -1000000000 1000000000

output:

2
1

result:

ok 2 number(s): "2 1"

Test #3:

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

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #4:

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

input:

100000
-851839419 34688642
-667081997 395784949
-624068418 -155389155 119194510 -758711821
-992436155 -812775173 851861070 -592596572
974613003 -179673992
-485749861 520596304
-115838823 -265233646 -573799007 -222234500
608830643 -887109945 483106217 -906910755
-597593284 384264657
940783 476657007
...

output:

0
0
0
0
0
0
1
0
0
0
0
1
0
0
1
1
0
0
1
1
1
0
1
0
0
1
0
1
0
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
1
1
1
1
1
0
1
1
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
1
1
0
1
0
0
1
0
0
0
0
1
1
1
1
1
1
0
0
0
1
1
1
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
1
1
0
1
1
0
0
0
0
0
0
1
0
1
1
0
1
0
0
1
0
0
1
1
0
0
0
1
0
1
0
1
0
0
0
1
1
...

result:

ok 100000 numbers

Test #5:

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

input:

100000
-496405053 -492673762
111401587 764822338
-588077735 774345046 959995351 -972693439
-729349041 -573156496 326664422 645305810
-477016787 -561855978
697257071 461011057
-416669921 377733217 784674141 -204150537
695471214 -642123788 -968584097 801626277
-329331824 68483816
945230774 982358552
-...

output:

1
1
1
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
1
1
0
1
1
1
1
1
0
1
1
0
1
1
1
0
0
1
1
0
1
0
0
0
0
0
1
0
0
0
0
0
0
1
0
1
1
0
1
0
1
0
0
0
0
1
1
0
1
1
0
0
0
1
1
1
1
1
1
0
1
1
0
0
0
0
0
1
0
1
0
1
1
1
0
1
1
1
1
1
1
1
1
0
0
0
0
0
1
0
1
0
0
1
1
0
1
0
1
0
1
0
0
1
1
1
0
0
0
0
0
0
0
1
1
1
1
...

result:

ok 100000 numbers

Test #6:

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

input:

100000
153996608 390029247
838007668 -918017777
-257119758 -244043252 390730779 813324945
-761229221 -38570526 634492154 -116791808
19475923 760994742
-119735998 991360398
-665623518 -632455126 -394909798 -481033868
-974798424 140919454 -715241704 510163308
-61070363 -542264319
-353569028 -511939904...

output:

1
0
0
1
1
1
0
0
0
1
1
0
1
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
0
1
0
0
0
1
1
0
0
1
0
0
1
1
0
0
0
1
0
0
0
1
0
1
1
0
1
0
1
0
1
1
1
0
0
0
1
0
0
0
0
0
1
1
1
0
0
0
1
0
1
0
0
1
0
1
1
0
1
0
1
0
0
1
0
0
0
0
0
0
1
0
1
1
0
0
1
0
0
0
0
1
0
0
1
0
1
1
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
1
1
1
1
0
0
1
0
0
0
...

result:

ok 100000 numbers

Test #7:

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

input:

100000
509430974 -432300451
-140418957 -600857890
-464218867 442601156 -768468380 61286241
-203174812 201048150 404262799 826143280
567846134 673780049
525213848 983652653
-671487323 600446325 963563350 -462949905
-888157854 628995403 -166932017 218700340
207191097 898865049
590720963 288728935
4143...

output:

0
0
0
1
0
0
1
1
0
0
1
0
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
1
1
1
0
0
1
1
0
1
1
0
1
0
0
0
0
0
0
1
0
1
0
1
1
0
0
0
0
0
0
1
0
1
1
0
0
0
1
1
0
0
0
0
0
0
1
0
1
0
1
0
0
0
1
1
1
0
0
0
1
1
0
0
0
1
0
0
0
0
1
1
0
0
1
0
1
1
0
1
1
1
0
0
0
0
0
0
0
1
1
1
0
0
1
1
0
0
0
0
0
0
1
1
1
0
1
0
0
1
0
0
0
0
0
1
1
0
1
0
...

result:

ok 100000 numbers

Test #8:

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

input:

100000
-840167367 450402558
586187125 -231820501
-428228185 -627664644 367299755 142271917
59912302 735634121 469000739 64045662
-935661158 291598063
-291779221 -780965301
-920440920 -409742018 -216020590 965199471
-801517283 -587961356 -156679415 465294457
423575055 583084208
-759956341 794430480
8...

output:

1
1
1
0
0
1
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
1
0
1
0
1
0
0
0
1
1
0
0
1
0
0
1
1
1
0
1
0
1
0
0
1
0
0
0
1
1
1
0
0
0
0
0
0
1
1
0
1
0
1
0
0
0
1
0
1
1
0
1
0
0
1
0
0
1
1
1
0
1
1
0
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
0
1
1
1
0
0
0
0
1
1
0
0
0
0
1
1
0
0
1
0
0
0
0
1
0
0
1
1
1
0
1
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 numbers

Test #9:

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

input:

100000
-779700294 -76959846
-340361999 380306679
-392237502 58979764 -201964817 -314799493
28032122 -729779910 -56195909 -454962165
-387290947 -142461426
891227711 -493705752
778727982 823159433 899362766 983283434
-471786920 -48007905 391630272 173831488
691836515 -322631221
236211152 -699867976
-3...

output:

0
0
0
0
0
1
0
0
1
1
0
1
0
0
1
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
1
0
1
0
0
0
0
0
1
0
1
1
1
0
0
0
1
1
0
1
0
0
0
1
0
1
0
0
1
0
0
0
0
0
0
0
1
1
1
1
0
0
0
1
0
0
0
0
0
1
1
0
0
1
0
0
0
1
0
1
0
0
0
0
0
1
0
0
1
1
1
1
0
1
0
0
0
0
0
0
1
1
0
0
0
1
0
0
1
0
0
0
0
1
0
0
1
0
1
0
1
1
0
0
0
...

result:

ok 100000 numbers

Test #10:

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

input:

100000
-181176136 805743163
681211377 454376774
-599336611 988713965 638836024 -823748404
586086531 -490161233 251631822 782940218
-133888029 -524643413
74234642 -553290999
529774386 -533873706 -332098675 -998632604
-385146349 735035338 350005371 -412598775
960097976 -638412062
-819498858 -194166431...

output:

1
0
1
1
1
0
1
0
0
1
0
0
0
1
1
0
0
1
0
1
0
0
1
0
0
0
0
0
1
0
1
0
1
1
1
0
1
1
1
1
1
1
0
0
0
0
1
0
1
1
0
1
1
0
1
0
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
1
0
0
1
0
0
0
1
0
0
0
1
0
1
1
0
1
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
1
0
0
1
1
0
0
0
1
0
0
0
1
1
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
1
...

result:

ok 100000 numbers

Test #11:

score: 0
Accepted
time: 92ms
memory: 3752kb

input:

100000
469225525 -311553829
-592182543 -933496047
-268378634 -29674334 -225395842 -985852520
849173645 44424737 21402468 20842600
657571974 -906825400
-742758427 -266031450
228943287 455937953 783284681 724484066
-593473073 -776888715 603347764 -460971951
-528550773 -954192903
-170176161 68445323
76...

output:

1
1
0
0
1
1
1
0
1
0
0
0
0
0
1
1
1
0
0
1
0
1
1
0
1
0
1
1
1
0
0
0
0
1
1
1
0
1
1
1
0
0
1
0
0
0
0
1
1
0
1
0
1
0
0
0
1
0
0
0
0
1
1
0
0
1
0
0
0
1
1
0
0
0
0
0
0
1
0
1
1
0
0
0
1
1
1
0
1
1
1
1
1
0
0
0
0
1
0
0
0
0
0
0
1
0
0
1
1
1
0
0
1
0
0
1
1
1
1
1
1
0
0
1
1
0
1
0
1
1
0
1
0
1
0
1
1
0
1
1
0
1
0
0
0
0
1
0
1
0
...

result:

ok 100000 numbers

Test #12:

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

input:

100000
824659891 866116474
429390833 -564458658
-232387951 656970075 910372293 505198569
817293465 579010708 86140408 963777688
616007597 416025321
440248505 -325616697
-20010310 -311160598 -101331964 742568030
-506832502 -236935264 -848342550 -752434920
-850223901 435058963
825991332 574146868
-776...

output:

1
0
0
0
1
1
1
0
0
1
0
0
1
0
1
0
1
1
0
1
0
0
0
1
0
0
1
1
0
0
1
0
1
1
0
0
0
1
1
0
0
1
0
0
1
1
0
1
0
1
1
0
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
1
0
1
1
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
1
1
0
1
0
1
0
1
0
1
1
1
1
1
0
1
1
0
0
1
1
0
0
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0
1
0
1
0
0
1
0
0
1
1
0
0
1
0
1
1
1
...

result:

ok 100000 numbers

Test #13:

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

input:

100000
-181402541 -196228170
624722764 328251238
783857631 682518931 547715844 969228879
823684584 -149364638 -913952210 833196798
62726516 -554264004
664711179 426420047
-418659204 986117749 725195722 -692340474
963934566 206423874 688322091 -850621504
-259681786 -92095128
52318280 220754482
262610...

output:

1
1
0
1
0
0
0
1
1
0
0
0
1
0
0
1
0
1
1
0
0
0
0
1
1
0
1
1
0
1
1
0
0
0
0
0
1
1
0
0
1
0
0
0
0
1
1
0
0
0
0
0
1
0
0
1
1
0
1
1
0
0
1
1
1
1
0
0
0
0
1
0
0
1
0
1
0
0
0
1
1
1
0
0
0
1
1
0
0
0
0
0
1
1
0
0
1
0
1
0
1
1
1
0
1
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
1
1
0
0
1
0
1
0
0
1
0
0
1
1
0
0
1
0
1
0
1
1
1
...

result:

ok 100000 numbers

Test #14:

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

input:

100000
417121618 686474839
-353703861 697288626
-885184394 -630836661 -611483316 755247261
-618261009 -204713255 855818437 -223868114
316129433 -641478697
-152281890 661802094
-962580095 219019198 -159420924 -969223805
-654457570 989467117 -763368223 562948234
251669466 -702843263
996608271 -9785766...

output:

0
0
1
0
0
0
0
1
0
0
1
0
0
0
0
1
0
0
0
1
1
1
1
0
0
0
0
0
1
1
0
1
1
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
1
1
0
0
1
0
0
1
1
1
0
0
1
1
0
1
0
0
1
0
0
0
1
0
0
1
1
0
0
1
0
0
0
1
0
1
0
0
1
1
0
0
0
1
1
0
1
0
0
1
0
1
1
0
1
0
0
0
1
0
0
0
0
1
0
1
0
1
0
1
1
0
0
1
0
1
1
0
1
0
0
0
0
1
1
0
0
0
1
0
0
1
1
1
0
0
0
0
1
0
1
...

result:

ok 100000 numbers

Test #15:

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

input:

100000
-932476723 -135854859
667869515 -985551488
-849193711 593864833 819252113 298175852
-650141189 329872715 -836353833 -985965732
-892410565 976339317
-969274959 654094349
-968443900 -791169144 660995138 -951139842
-567817000 -470579434 -510025830 566452559
519930927 686408603
-302191531 -472875...

output:

1
0
1
1
0
0
1
1
0
0
0
1
0
0
1
1
1
0
0
0
0
0
1
0
1
1
1
1
1
1
0
0
1
1
0
1
0
1
1
0
0
1
0
0
0
0
1
0
0
1
0
0
0
1
0
0
1
0
0
0
0
1
0
0
1
0
0
0
1
1
1
0
1
1
0
1
0
0
0
0
0
0
1
1
0
1
0
1
0
0
0
1
1
1
0
1
0
0
0
0
0
0
1
0
1
0
1
0
1
0
0
0
1
0
1
0
1
1
1
1
1
0
1
1
0
1
0
1
0
0
1
0
1
0
1
0
0
1
1
1
1
0
0
0
0
0
1
0
0
0
...

result:

ok 100000 numbers

Test #16:

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

input:

100000
-577042357 -958184557
-553646903 -616514099
-761325526 -719490759 -44979753 -210773060
-387054074 864458686 638449520 546903944
-639007648 299190036
213731973 889476396
782602504 -148202282 19468285 -933055879
-238086637 17496515 -204805935 518079383
493225093 127537970
642098459 32826410
215...

output:

0
0
0
0
1
0
1
0
0
0
1
0
1
1
0
0
1
0
0
0
1
0
1
0
0
1
1
0
1
1
1
1
1
1
1
0
1
0
0
1
1
0
1
1
1
0
0
0
0
0
0
0
1
0
1
1
1
1
1
0
0
1
1
1
0
0
0
1
1
0
0
0
1
1
0
0
1
1
1
1
1
1
1
1
1
1
0
0
0
1
0
1
0
0
0
0
1
1
0
1
0
0
0
1
0
1
0
0
0
1
0
1
1
1
1
0
1
1
0
0
1
0
0
0
1
0
0
1
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
1
0
0
1
1
1
...

result:

ok 100000 numbers

Test #17:

score: 0
Accepted
time: 93ms
memory: 3564kb

input:

100000
-516575284 219485746
172959179 -299354213
979697864 -32846351 795821088 -372877176
171000334 -895922639 703187460 -510160968
-142514938 -82991950
-308293802 881768651
776738700 -915300832 839884347 790060792
-151446066 800539757 48536459 226616414
709609051 -188242871
-656701343 538527956
912...

output:

0
0
1
1
1
1
0
0
1
1
0
0
0
1
1
0
0
0
0
1
1
0
0
0
1
1
0
0
1
0
1
1
1
1
0
1
0
0
0
1
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
1
1
0
0
1
1
0
0
1
0
1
0
0
0
1
0
0
1
1
1
1
0
0
1
1
0
1
0
0
0
1
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
0
1
1
0
0
0
1
1
0
1
0
1
0
0
1
0
1
1
0
1
1
0
1
1
0
0
0
0
0
0
0
0
0
0
1
1
0
1
1
0
1
0
0
0
0
1
0
1
...

result:

ok 100000 numbers

Test #18:

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

input:

100000
133826376 -897811246
-805467447 69683176
-984311454 896887850 226556516 -881826087
139120154 -361336668 472958105 727741414
110887979 -465173937
631623338 -882849303
475907601 74510826 -44732299 513177461
-359772790 -416417001 596846146 -64846555
977870511 -798991006
287588648 -955770500
-633...

output:

0
0
0
1
0
0
0
0
0
1
0
1
1
0
0
1
0
1
1
0
0
0
0
1
0
1
0
1
0
0
1
0
1
0
0
0
0
1
1
0
0
1
1
0
0
0
0
0
0
0
1
0
1
1
0
0
0
1
0
0
0
0
0
1
0
1
1
0
0
0
0
1
0
0
0
0
1
1
1
1
1
0
0
0
1
0
1
1
0
0
0
0
0
0
0
0
1
0
1
1
1
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
1
1
0
0
0
1
0
1
0
0
0
0
1
0
0
0
1
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
...

result:

ok 100000 numbers

Test #19:

score: 0
Accepted
time: 95ms
memory: 3540kb

input:

100000
489260742 -15108237
-78861365 681810357
-896443270 -416467743 -932642644 904192296
402207268 173249302 537696045 -329323498
902347982 -899233426
-480337024 -595589754
-68013290 -692587724 -981226446 531261424
-30042427 123536449 850188539 -356309523
-753868029 885228154
936911345 -450068955
1...

output:

1
1
1
0
0
0
1
0
1
1
1
1
0
0
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
1
1
1
0
1
0
1
0
0
1
0
0
0
0
0
1
0
0
1
1
1
0
0
1
1
1
0
0
0
0
0
0
1
0
0
1
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
1
0
0
1
0
1
0
1
1
0
0
1
0
0
0
0
0
1
0
1
1
0
1
0
0
0
0
1
1
0
0
0
0
0
1
0
0
1
0
1
0
1
0
0
1
0
0
1
0
1
1
1
1
0
0
...

result:

ok 100000 numbers

Test #20:

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

input:

100000
-617247806 -542470641
699622219 998970243
-860452587 565143960 203125491 447120886
960261677 707835273 550556483 908578885
-844249102 718584588
702669908 -360207707
-73877095 297223934 -160810384 254378093
56598144 611612398 -601501775 -109715406
-780573863 569447313
-361888457 350599884
5702...

output:

1
1
0
0
1
1
0
0
0
0
1
0
1
1
1
0
0
1
0
0
1
1
0
1
1
0
1
0
0
0
1
1
1
1
0
0
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
0
0
1
0
0
1
0
0
1
0
1
0
0
0
0
0
0
1
1
0
1
1
1
1
0
1
0
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
1
0
1
1
0
1
0
1
0
0
0
0
0
0
0
0
1
1
0
1
0
1
0
0
0
0
1
1
1
0
0
1
0
0
1
0
0
0
0
0
1
0
0
...

result:

ok 100000 numbers

Test #21:

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

input:

100000
-261813440 340232368
-573771701 -631992369
-529494610 -505121840 -661106375 233139268
928381497 947453949 320327128 389571058
-52789098 336402602
-114323161 -124825660
-617797985 940190796 659605678 272462056
143238715 -605344361 -591249174 -401178375
-269222611 -41300822
877368828 856301429
...

output:

1
0
0
0
0
0
0
1
0
0
1
1
1
0
1
1
0
0
1
1
1
1
1
0
0
0
0
0
0
1
1
1
0
1
0
1
1
1
1
1
1
1
1
1
0
0
1
1
1
0
0
1
1
0
1
1
0
1
1
0
1
0
1
0
0
1
0
0
1
1
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
1
0
1
0
1
0
0
1
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
0
1
0
1
0
0
1
1
0
1
0
1
0
1
1
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
1
0
0
0
0
...

result:

ok 100000 numbers

Test #22:

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

input:

100000
-201346367 -482097330
742768969 -19865188
-736593719 -113444726 474661760 -223932141
-808531390 -517960081 90097774 -667493854
200613819 -45779385
-931316230 -132533405
-623661790 -69997546 18078824 -4421275
767936371 -65390910 -337906780 -987608637
-961151 -652048957
-473308476 -637997027
-5...

output:

1
0
0
0
0
0
1
0
0
1
0
1
1
1
1
1
0
1
0
1
0
0
1
1
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
1
0
0
1
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
0
1
1
1
0
0
0
1
0
1
1
1
0
0
0
1
0
0
1
0
1
1
0
0
0
0
0
0
0
1
0
1
0
1
0
0
0
0
1
1
0
0
0
0
1
1
0
1
0
1
0
1
0
0
1
1
0
1
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
1
0
0
1
0
0
0
...

result:

ok 100000 numbers

Test #23:

score: 0
Accepted
time: 96ms
memory: 3724kb

input:

100000
889700307 83152852
81040013 -449413311
374958682 300600303 -247400099 -855076598
-624900532 -785317715 857266066 -410224840
872271274 -850603331
-975572718 973091933
421906561 -222540906 -675309230 591089749
-544630032 -809400213 70027428 -810848022
902977690 -179653965
-183689299 262567523
7...

output:

0
1
0
0
1
1
0
0
0
1
1
0
1
0
0
1
0
0
0
1
1
1
0
0
1
0
0
0
1
0
0
0
0
0
1
0
1
0
1
1
1
1
0
1
0
1
1
0
0
0
0
1
0
0
0
0
0
1
0
1
1
2
1
0
0
1
1
0
0
1
1
1
1
1
1
0
0
0
1
0
1
0
0
0
0
1
0
0
1
1
1
1
0
0
0
1
0
0
0
0
1
0
0
0
1
1
0
1
1
1
1
0
0
0
1
1
1
1
0
0
1
0
0
0
1
1
0
0
0
1
1
1
0
1
0
0
0
0
1
0
0
0
0
1
1
1
1
0
0
1
...

result:

ok 100000 numbers

Test #24:

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

input:

45369
0 0
0 -1
999999997 999999997 -999999997 -999999998
-999999997 -999999997 999999997 999999998
0 0
0 -1
999999997 999999997 -999999997 -1000000000
-999999997 -999999997 999999997 999999998
0 0
0 -1
999999997 999999997 -999999998 -999999997
-999999997 -999999997 999999997 999999998
0 0
0 -1
99999...

output:

1
0
0
1
1
0
0
1
0
0
0
1
0
0
1
1
0
0
1
0
0
0
1
0
0
1
1
0
0
1
0
0
0
2
1
1
2
2
1
1
2
1
1
1
1
0
0
1
1
0
0
1
0
0
0
1
0
0
1
1
0
0
1
0
0
0
2
1
1
2
2
1
1
2
1
1
1
2
1
1
2
2
1
1
2
1
1
1
1
0
0
1
1
0
0
1
0
0
0
1
0
0
1
1
0
0
1
0
0
0
2
1
1
2
2
1
1
2
1
1
1
2
1
1
2
2
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
0
0
...

result:

ok 45369 numbers

Test #25:

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

input:

100000
-1 -1
0 -2
2 1 0 0
-1 1 1 -1
-2 -1
-2 -1
0 -1 -1 0
2 2 0 -2
0 2
1 -2
0 -2 -2 0
2 -1 -2 0
0 2
-2 -2
-2 0 2 1
1 2 1 0
1 0
1 -1
0 -1 2 0
2 2 1 2
2 1
0 0
-2 1 1 2
-1 1 -1 2
0 0
2 1
2 -2 -2 1
-2 -2 1 -2
-1 -1
1 2
-2 -2 0 1
-2 1 -1 -2
-2 1
-1 1
-1 2 2 0
-1 2 -2 -2
0 2
0 1
1 -2 1 0
1 1 0 0
2 1
1 -2
...

output:

0
0
1
1
1
0
0
0
1
0
1
1
0
0
0
0
1
0
0
0
0
1
0
0
1
1
1
0
0
0
0
0
0
1
1
0
0
0
1
0
0
1
1
1
0
0
1
0
1
0
0
0
1
0
0
0
0
1
0
1
1
1
0
1
0
0
1
1
0
1
1
1
1
0
1
0
1
0
1
1
0
0
0
0
1
0
1
0
1
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
1
0
0
1
1
0
0
0
1
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
...

result:

ok 100000 numbers

Test #26:

score: 0
Accepted
time: 65ms
memory: 3564kb

input:

100000
2 2
-2 -1
-1 0 -2 2
0 2 0 -2
1 -2
2 0
-1 -1 -2 -1
-1 0 -1 -2
-1 1
2 0
-2 2 -2 1
-2 2 0 -2
2 2
2 1
0 2 -2 -1
2 -2 2 0
-2 0
-1 1
2 0 1 2
2 -2 0 0
-2 1
-1 2
1 -2 -1 0
0 0 -2 -1
0 0
0 0
2 2 0 -1
2 -2 0 -1
-1 1
1 1
2 2 1 -1
0 2 0 -2
0 1
2 2
1 2 1 -1
-1 -1 0 2
-1 -2
1 -2
1 2 -2 2
-1 -1 2 -2
0 -1
-1...

output:

1
0
0
0
0
0
0
1
1
0
1
0
1
0
1
0
0
0
0
0
0
1
0
1
0
1
1
0
0
1
0
1
0
0
1
0
0
1
0
0
1
0
1
1
1
1
0
0
1
0
0
1
0
0
0
0
0
0
0
0
1
1
0
0
1
1
1
1
1
0
1
0
0
0
1
1
0
1
1
0
1
0
0
0
0
0
1
1
1
0
0
1
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
0
0
1
1
0
1
0
0
0
0
1
0
0
0
0
1
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
1
0
1
...

result:

ok 100000 numbers

Test #27:

score: 0
Accepted
time: 61ms
memory: 3684kb

input:

100000
-5 -4
0 -1
-1 5 5 -1
1 1 -3 -4
-3 2
5 0
3 -5 -5 -4
2 0 -4 -1
-1 5
2 3
-2 -1 3 2
3 2 4 -1
-5 2
-1 0
-5 -1 3 -3
-1 4 -4 -2
2 3
4 -4
-4 0 2 -1
3 -1 4 3
-1 -5
-5 1
-4 2 -4 3
-3 -5 -3 -4
-2 2
3 -2
0 5 -1 -2
-4 -5 3 1
0 4
1 2
2 -2 2 -4
-3 4 -3 -5
-1 3
-2 2
-2 -3 -1 -1
0 -5 5 3
-2 -5
1 -2
-5 -2 -3 -...

output:

1
0
0
1
1
0
1
0
0
0
0
0
0
0
1
0
1
1
1
0
0
0
1
0
0
1
0
1
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
0
1
0
0
1
0
0
0
1
1
0
0
0
1
1
0
0
1
0
1
1
0
1
0
0
0
0
0
1
0
1
0
0
0
1
1
1
0
0
1
1
1
1
1
0
1
1
1
0
1
0
0
1
0
0
1
0
1
0
0
0
0
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
0
1
1
0
1
0
1
1
0
1
0
1
0
0
0
...

result:

ok 100000 numbers

Test #28:

score: 0
Accepted
time: 59ms
memory: 3532kb

input:

100000
-3 4
-4 0
-3 0 -2 2
4 5 0 4
-2 3
-2 4
-5 1 3 3
-5 1 1 -4
-2 -2
1 5
5 0 3 4
4 -1 -2 3
4 0
5 4
3 1 -3 2
-4 0 3 -3
4 -4
-1 -3
-3 2 -5 5
-2 -3 4 4
-1 -5
4 3
-5 -5 5 -4
0 -1 -5 3
1 5
1 2
-4 3 -2 0
0 0 -2 -4
-1 1
5 1
-1 -5 2 4
4 -1 1 -1
-4 4
-5 1
-5 5 -1 -3
1 5 -2 3
5 5
-5 1
0 -2 -2 0
0 -4 5 -4
4 -...

output:

0
0
1
0
0
1
0
1
1
0
0
0
0
0
0
0
0
0
1
0
1
1
1
1
1
0
1
0
0
0
0
1
0
1
0
0
0
0
0
1
0
1
0
0
0
1
1
0
0
0
1
0
1
1
0
0
1
0
1
0
1
0
0
0
0
0
1
0
1
0
1
1
0
0
1
0
0
0
1
0
1
0
0
1
0
1
1
1
1
1
0
0
1
1
1
0
1
1
0
0
0
0
0
0
1
0
0
0
0
1
0
1
0
1
1
1
1
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
0
0
1
0
1
0
1
1
...

result:

ok 100000 numbers

Test #29:

score: 0
Accepted
time: 65ms
memory: 3604kb

input:

100000
8 -1
-5 9
-7 0 -6 -2
-2 -9 0 5
6 -3
2 7
6 -5 7 -7
-4 4 1 5
-9 5
-5 -3
3 -6 8 8
-9 -9 5 -5
2 -5
10 -5
0 7 -9 5
-4 0 1 -4
-1 -5
9 3
-5 8 -2 8
-9 1 -5 2
7 -9
0 0
-9 -10 1 -4
-9 -10 2 4
10 10
-6 0
7 -6 -7 -9
7 3 -7 4
-6 -4
-9 5
-6 -2 8 -8
8 1 -4 -4
-6 -6
-4 6
-7 -4 10 -3
-4 -4 7 -3
-4 6
8 -8
-10 ...

output:

0
0
0
0
0
0
1
0
1
1
0
1
0
1
0
0
0
0
1
1
1
0
1
0
0
0
1
0
1
0
0
0
1
1
0
1
0
1
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
1
1
0
0
0
0
0
0
0
0
1
1
1
0
0
1
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
1
0
0
0
0
0
1
0
1
1
0
1
0
0
0
1
0
0
0
0
1
1
0
1
0
1
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
1
1
0
0
0
1
0
1
...

result:

ok 100000 numbers

Test #30:

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

input:

100000
-5 -1
-1 -4
0 10 -2 -9
-5 1 -2 -8
-9 -7
6 -10
5 4 -10 9
-4 5 9 -4
4 6
-10 6
-6 -9 -10 4
4 10 -2 9
9 -6
6 8
-6 0 7 9
-5 -2 0 7
1 -7
1 0
-4 -6 -4 1
-7 5 -8 4
-8 3
6 6
4 -2 -4 -1
-7 10 8 2
-5 6
-3 2
2 8 -5 -2
4 2 1 3
4 -2
10 1
-4 -3 8 8
-4 2 -6 -1
-10 2
-9 6
7 5 -7 2
2 -5 9 6
-10 1
10 -4
-9 1 8 ...

output:

1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
1
0
1
0
0
0
0
1
0
1
1
0
1
1
1
1
1
0
1
1
1
0
0
1
0
0
0
1
0
1
0
1
0
1
0
1
1
0
2
0
1
1
0
0
1
0
1
0
1
0
0
0
1
0
0
0
1
0
1
1
1
0
1
1
0
1
0
1
1
1
1
0
0
1
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
1
1
1
1
0
0
0
0
1
0
1
0
0
0
1
1
1
0
0
1
1
0
1
1
0
1
0
1
1
0
0
1
0
1
0
1
0
1
0
1
1
1
0
1
0
0
...

result:

ok 100000 numbers

Test #31:

score: 0
Accepted
time: 68ms
memory: 3564kb

input:

100000
26 -52
16 -54
-42 56 92 -51
100 -58 57 52
-84 -98
-71 -28
21 12 -3 -82
72 -30 -66 94
-50 96
-77 -41
-42 -41 -13 -55
0 12 -50 -99
65 -5
-96 -48
73 -80 72 -92
53 59 -67 -66
2 -75
45 56
3 10 -46 -23
80 -92 -22 -88
-96 -63
78 -58
-4 -70 53 -42
85 -47 -35 35
-26 -42
-13 -94
40 -20 82 62
50 3 -28 -...

output:

0
0
0
1
0
1
1
0
0
0
1
1
1
0
1
0
1
0
1
0
0
1
1
0
1
1
0
1
0
1
1
1
0
0
1
1
0
0
0
1
1
2
1
0
0
1
1
1
1
1
0
1
0
0
0
0
1
1
0
1
0
1
1
0
1
1
0
0
1
0
1
0
1
0
0
0
0
1
0
1
1
1
0
1
0
0
1
0
0
0
1
0
0
0
0
0
0
1
1
0
1
1
0
0
1
1
1
1
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
1
0
0
1
0
0
0
1
0
0
0
0
0
0
1
0
...

result:

ok 100000 numbers

Test #32:

score: 0
Accepted
time: 65ms
memory: 3560kb

input:

100000
-13 -58
-42 96
59 87 39 58
9 75 -66 -81
86 84
22 -19
-20 0 26 67
0 28 -82 51
-33 32
-6 -63
-84 96 47 79
76 -13 -21 -79
-82 -61
62 88
-20 -27 100 77
51 43 -60 85
70 -65
60 22
-12 22 -43 -5
-92 24 -45 -87
73 70
58 -48
60 -84 2 -13
-99 31 25 80
86 -49
17 21
60 -98 -74 54
91 -25 -36 28
1 -86
25 5...

output:

1
0
0
1
0
0
1
0
0
0
0
1
0
0
1
0
1
1
0
1
0
0
1
0
1
1
1
1
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
1
0
1
0
1
0
1
1
0
0
1
0
1
1
1
0
1
1
1
0
0
1
1
0
0
0
1
1
0
0
0
0
1
1
0
0
0
1
1
0
0
0
0
1
1
1
1
0
0
0
1
1
0
0
0
1
1
0
1
0
1
0
0
0
0
0
0
0
1
0
1
1
0
0
0
1
1
0
0
0
0
1
0
0
0
1
1
0
1
0
1
1
1
1
1
1
0
1
1
1
0
0
0
1
1
0
...

result:

ok 100000 numbers

Test #33:

score: 0
Accepted
time: 75ms
memory: 3724kb

input:

100000
-6187 -6551
-5183 8419
-1712 5889 -2510 4471
3583 -1832 -1340 -1489
-1709 -9857
-7578 5359
7470 -5381 -1699 2176
-7624 9711 -5027 -5606
-2310 -9964
9847 -3618
260 -1879 -3363 -120
-2145 6107 -6795 -9022
-154 -5505
-8094 -3540
-850 9272 -4615 3414
-5472 -536 -9369 8371
3318 6525
-9020 -5352
80...

output:

0
1
0
0
0
1
0
1
0
0
0
1
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
0
0
1
1
0
0
0
1
1
0
1
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
1
0
0
0
1
0
0
1
1
1
1
1
0
0
0
0
2
0
0
0
0
0
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
1
0
1
1
1
0
0
0
0
0
1
1
1
0
1
0
0
1
0
0
0
0
0
0
0
1
1
0
1
1
1
0
0
1
0
1
0
0
0
1
1
1
1
1
0
0
1
0
1
0
...

result:

ok 100000 numbers

Test #34:

score: 0
Accepted
time: 75ms
memory: 3504kb

input:

100000
-8170 -3968
2229 469
-7086 7497 1736 -498
6745 8054 8151 -3573
5616 -8837
-2202 -951
1279 -3013 -5990 4474
2080 7654 6095 6877
5033 -8252
732 6485
-7472 -1348 -5459 466
-106 6012 6371 6706
-2888 3799
9827 2871
191 877 -3980 -4079
-1013 2191 -9422 -8101
1414 -382
-6192 2251
-272 75 473 1805
64...

output:

1
0
1
0
1
0
0
1
1
0
1
1
0
0
1
0
0
1
1
1
0
0
0
0
0
0
1
0
0
1
1
1
1
0
0
0
1
1
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
1
0
0
0
0
1
1
0
1
0
1
1
1
1
1
1
0
0
0
1
0
1
0
1
1
0
0
0
0
0
1
1
0
1
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
0
0
0
1
0
1
0
0
1
0
0
1
1
0
0
0
0
0
1
1
0
1
...

result:

ok 100000 numbers

Test #35:

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

input:

100000
275163 496652
-280971 712704
195720 -491146 -205978 -595391
-10484 -818942 -458101 -560260
713584 822852
-908965 852248
-667176 -299029 -980479 -932459
445314 352581 -953133 482726
392725 -910835
-120588 -842013
-263607 -418011 646409 -806763
956885 352325 -825391 -960489
986514 534108
872846...

output:

0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
1
1
0
0
0
0
0
1
0
1
0
0
1
0
1
1
1
0
0
1
1
1
1
1
0
0
1
0
0
1
1
0
0
0
1
1
0
0
0
0
1
1
0
0
1
0
0
1
1
1
0
0
0
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
1
1
1
0
1
0
0
0
0
1
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
1
1
0
1
1
0
0
1
0
1
0
0
1
0
0
0
1
1
0
1
1
0
1
1
1
0
0
1
0
1
0
1
...

result:

ok 100000 numbers

Test #36:

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

input:

100000
-79574 -541307
782373 -953436
368820 223194 193195 -516619
-764834 808130 -499844 -638978
-124135 206465
134 -461247
-703640 735077 659058 -444665
653535 528043 -585095 516264
-743477 874059
-812173 -320452
-15504 974433 -891440 134639
627889 -345389 -963842 439708
-973987 467402
-86000 94028...

output:

0
0
1
0
0
0
1
0
0
0
0
0
0
1
1
0
1
0
1
1
0
0
0
0
0
1
1
1
0
1
0
0
0
0
0
0
0
1
0
1
0
1
0
0
1
0
0
1
0
0
1
0
0
0
1
1
0
1
1
0
0
0
0
0
1
1
1
0
1
0
0
0
0
0
1
0
0
1
0
1
1
0
1
1
0
1
0
0
1
0
0
1
0
1
0
1
0
0
1
1
1
1
0
0
0
1
1
0
1
0
1
0
0
1
1
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
1
1
0
0
1
0
1
0
0
0
0
0
1
0
...

result:

ok 100000 numbers

Test #37:

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

input:

100000
77667542 -10213443
68613142 -64993975
-91517331 92815352 94352168 -50791026
37243016 -48172320 -2333003 -68764982
-41825820 -84725493
-10000675 34032144
23188984 -86230348 83520213 -73883938
61843575 -45694747 -72062901 91267978
-42057853 68190387
88941772 -96036839
10262381 -96466291 -225385...

output:

1
1
0
0
1
1
0
0
0
0
1
0
0
1
0
1
1
1
1
0
0
1
0
1
0
1
1
0
0
1
1
0
0
1
0
1
1
1
0
0
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
1
0
0
1
0
0
1
1
0
0
0
1
0
0
1
1
1
0
1
0
1
1
0
1
0
0
0
0
0
0
1
1
1
0
0
0
1
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
0
0
1
0
0
0
1
0
1
0
1
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
1
...

result:

ok 100000 numbers

Test #38:

score: 0
Accepted
time: 95ms
memory: 3504kb

input:

100000
70071569 -36261235
53681639 -87747065
30164720 -54883925 -36622371 8561907
-72623483 -90720032 41335717 -53052419
6681207 53253800
-76962574 -52828785
38407155 93554742 -73075898 -8626463
84835071 -76751856 21543045 -59329345
50713392 14590006
75134873 -56869370
-78045136 -2701952 -30898875 1...

output:

0
0
1
1
0
1
1
1
1
1
1
0
1
0
0
0
1
1
1
0
1
0
0
0
1
0
0
1
1
0
0
1
0
1
1
0
0
1
0
1
0
0
0
1
1
0
0
0
0
0
1
1
1
1
1
0
0
0
1
1
0
1
0
0
0
1
1
0
0
0
1
1
1
0
1
0
0
1
1
0
0
1
0
0
0
1
0
0
1
1
0
0
1
1
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
0
1
1
0
0
0
0
0
1
0
1
1
1
1
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
0
0
1
1
0
1
1
1
1
0
1
1
...

result:

ok 100000 numbers

Test #39:

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

input:

22
0 999999999
0 -999999999
1000000000 1000000000 -1000000000 -1000000000
-1000000000 999999998 1000000000 -999999998
0 999999999
0 -999999999
999999999 1000000000 -1000000000 -1000000000
-1000000000 999999998 1000000000 -999999998
0 999999999
0 -999999999
999999999 1000000000 -1000000000 -100000000...

output:

2
2
2
1
2
1
2
2
1
2
1
1
1
1
2
1
2
2
2
2
1
1

result:

ok 22 numbers

Test #40:

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

input:

5
-2 0
-2 0
2 -2 0 -1
0 -2 1 -1
-2 -2
-2 0
-2 -1 -1 2
-1 -1 -2 1
2 -1
2 -1
0 1 0 1
0 0 1 0
1 1
-999999998 -999999999
0 0 999999999 1000000000
0 0 999999999 1000000000
-1 -1
999999998 999999999
0 0 999999999 1000000000
0 0 999999999 1000000000

output:

0
1
0
0
0

result:

ok 5 number(s): "0 1 0 0 0"

Test #41:

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

input:

100000
-999999999 999999999
1000000000 -999999998
999999998 -1000000000 999999998 1000000000
-1000000000 1000000000 1000000000 1000000000
-999999998 -1000000000
999999999 999999998
-1000000000 -999999998 999999998 -1000000000
999999998 999999998 1000000000 999999999
-999999998 -999999999
-999999998 ...

output:

1
1
1
0
1
0
0
0
1
1
2
0
0
0
0
0
1
1
1
0
1
0
0
1
1
1
0
1
1
0
0
0
0
1
1
1
0
1
0
1
0
1
0
1
0
0
1
0
1
1
1
1
0
1
0
0
1
1
0
0
0
1
0
0
1
0
0
1
0
1
0
0
0
0
1
1
1
1
1
0
0
0
1
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
1
1
0
1
1
1
0
1
1
0
0
0
0
0
1
1
1
0
0
1
0
0
0
1
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
1
1
0
...

result:

ok 100000 numbers