#define op operator
#define __ while
#define _0 return
typedef long long ll;
inline ll _(ll a,ll b){ll t;__(a){t=a;a=b%a;b=t;}_0 b;}
struct frac{
	ll u,d;
	frac(ll u=0,ll d=1):u(u),d(d){}
	frac op()(){ll _1=_(u,d);_0 frac(u/_1,d/_1);}
	frac op*(frac b){_0 (frac(u*b.u,d*b.d))();}
	frac op/(frac b){_0 (frac(u*b.d,d*b.u))();}
	frac op*(ll n){_0 (frac(u*n,d))();}
	frac op/(ll n){_0 (frac(u,d*n))();}
	frac op[](ll n){_0 frac(u*n,d*n);}
	frac op+(ll n){_0 frac(u+d*n,d);}
	frac op-(ll n){_0 frac(u-d*n,d);}
	frac op+(frac b){frac _1=(*this)[b.d],_2=b[d];_0 (frac(_1.u+_2.u,_1.d))();}
	frac op-(frac b){frac _1=(*this)[b.d],_2=b[d];_0 (frac(_1.u-_2.u,_1.d))();}
	void op=(ll b){d=1,u=b;}
	ll op()(frac b){return u*b.d-d*b.u;}//<=>
	bool op==(frac b){return u==b.u&&d==b.d;}
	bool op>(frac b){return b(*this)<0;}
	bool op<(frac b){return b(*this)>0;}
};
frac op/(ll a,frac b){_0 (frac(b.d*a,b.u))();}
frac op-(ll a,frac b){_0 frac(a)-b;}
frac op+(ll a,frac b){_0 frac(a)+b;}
frac op*(ll a,frac b){_0 (frac(a*b.u,b.d))();}
typedef struct vec{
	frac x,y;
	vec(frac x,frac y):x(x),y(y){};
	vec op+(vec b){_0 vec(x+b.x,y+b.y);}
	vec op-(vec b){_0 vec(x-b.x,y-b.y);}
	vec op*(frac b){_0 vec(x*b,y*b);}
	vec op/(frac b){_0 vec(x/b,y/b);}
	vec op*(ll b){_0 vec(x*b,y*b);}
	vec op/(ll b){_0 vec(x/b,y/b);}
	frac op*(vec b){_0 x*b.y-y*b.x;}//cross product
	frac op[](vec b){_0 x*b.x+y*b.y;}//dot product
	bool op==(vec b){_0 x==b.x&&y==b.y;}//equality test
} point;