QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#113189#6375. LaLa and Magic Circle (LaLa Version)maroonrkAC ✓152ms26940kbC++2016.7kb2023-06-16 17:16:182023-06-16 17:16:20

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-16 17:16:20]
  • 评测
  • 测评结果:AC
  • 用时:152ms
  • 内存:26940kb
  • [2023-06-16 17:16:18]
  • 提交

answer

#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))
#ifdef LOCAL
void dmpr(ostream&os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ";
	dmpr(os,args...);
}
#define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
#else
#define dmp2(...) void(0)
#endif

using uint=unsigned;
using ull=unsigned long long;

template<class t,size_t n>
ostream& operator<<(ostream&os,const array<t,n>&a){
	return os<<vc<t>(all(a));
}

template<int i,class T>
void print_tuple(ostream&,const T&){
}

template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
	if(i)os<<",";
	os<<get<i>(t);
	print_tuple<i+1,T,Args...>(os,t);
}

template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
	os<<"{";
	print_tuple<0,tuple<Args...>,Args...>(os,t);
	return os<<"}";
}

ll read(){
	ll i;
	cin>>i;
	return i;
}

vi readvi(int n,int off=0){
	vi v(n);
	rep(i,n)v[i]=read()+off;
	return v;
}

pi readpi(int off=0){
	int a,b;cin>>a>>b;
	return pi(a+off,b+off);
}

template<class t>
void print_single(t x,int suc=1){
	cout<<x;
	if(suc==1)
		cout<<"\n";
	if(suc==2)
		cout<<" ";
}

template<class t,class u>
void print_single(const pair<t,u>&p,int suc=1){
	print_single(p.a,2);
	print_single(p.b,suc);
}

template<class T>
void print_single(const vector<T>&v,int suc=1){
	rep(i,v.size())
		print_single(v[i],i==int(v.size())-1?suc:2);
}

template<class T>
void print_offset(const vector<T>&v,ll off,int suc=1){
	rep(i,v.size())
		print_single(v[i]+off,i==int(v.size())-1?suc:2);
}

template<class T,size_t N>
void print_single(const array<T,N>&v,int suc=1){
	rep(i,N)
		print_single(v[i],i==int(N)-1?suc:2);
}

template<class T>
void print(const T&t){
	print_single(t);
}

template<class T,class ...Args>
void print(const T&t,const Args&...args){
	print_single(t,2);
	print(args...);
}

string readString(){
	string s;
	cin>>s;
	return s;
}

template<class T>
T sq(const T& t){
	return t*t;
}

void YES(bool ex=true){
	cout<<"YES\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void NO(bool ex=true){
	cout<<"NO\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void Yes(bool ex=true){
	cout<<"Yes\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void No(bool ex=true){
	cout<<"No\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
//#define CAPITAL
/*
void yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<"\n";
	#else
	cout<<"Yes"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void no(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<"\n";
	#else
	cout<<"No"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}*/
void possible(bool ex=true){
	#ifdef CAPITAL
	cout<<"POSSIBLE"<<"\n";
	#else
	cout<<"Possible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void impossible(bool ex=true){
	#ifdef CAPITAL
	cout<<"IMPOSSIBLE"<<"\n";
	#else
	cout<<"Impossible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}

constexpr ll ten(int n){
	return n==0?1:ten(n-1)*10;
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

int topbit(signed t){
	return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
	return t==0?-1:63-__builtin_clzll(t);
}
int topbit(ull t){
	return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
	return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
	return a==0?64:__builtin_ctzll(a);
}
int botbit(ull a){
	return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
	return __builtin_popcount(t);
}
int popcount(ll t){
	return __builtin_popcountll(t);
}
int popcount(ull t){
	return __builtin_popcountll(t);
}
int bitparity(ll t){
	return __builtin_parityll(t);
}
bool ispow2(int i){
	return i&&(i&-i)==i;
}
ll mask(int i){
	return (ll(1)<<i)-1;
}
ull umask(int i){
	return (ull(1)<<i)-1;
}
ll minp2(ll n){
	if(n<=1)return 1;
	else return ll(1)<<(topbit(n-1)+1);
}

bool inc(int a,int b,int c){
	return a<=b&&b<=c;
}

template<class t> void mkuni(vc<t>&v){
	sort(all(v));
	v.erase(unique(all(v)),v.ed);
}

ll rand_int(ll l, ll r) { //[l, r]
	//#ifdef LOCAL
	static mt19937_64 gen;
	/*#else
	static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
	#endif*/
	return uniform_int_distribution<ll>(l, r)(gen);
}

ll rand_int(ll k){ //[0,k)
	return rand_int(0,k-1);
}

template<class t>
void myshuffle(vc<t>&a){
	rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
}

template<class t>
int lwb(const vc<t>&v,const t&a){
	return lower_bound(all(v),a)-v.bg;
}
template<class t>
bool bis(const vc<t>&v,const t&a){
	return binary_search(all(v),a);
}

vvc<int> readGraph(int n,int m){
	vvc<int> g(n);
	rep(i,m){
		int a,b;
		cin>>a>>b;
		//sc.read(a,b);
		a--;b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	return g;
}

vvc<int> readTree(int n){
	return readGraph(n,n-1);
}

vc<ll> presum(const vi&a){
	vc<ll> s(si(a)+1);
	rep(i,si(a))s[i+1]=s[i]+a[i];
	return s;
}
//BIT で数列を管理するときに使う (CF850C)
template<class t>
vc<t> predif(vc<t> a){
	gnr(i,1,si(a))a[i]-=a[i-1];
	return a;
}
template<class t>
vvc<ll> imos(const vvc<t>&a){
	int n=si(a),m=si(a[0]);
	vvc<ll> b(n+1,vc<ll>(m+1));
	rep(i,n)rep(j,m)
		b[i+1][j+1]=b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j];
	return b;
}

//verify してないや
void transvvc(int&n,int&m){
	swap(n,m);
}
template<class t,class... Args>
void transvvc(int&n,int&m,vvc<t>&a,Args&...args){
	assert(si(a)==n);
	vvc<t> b(m,vi(n));
	rep(i,n){
		assert(si(a[i])==m);
		rep(j,m)b[j][i]=a[i][j];
	}
	a.swap(b);
	transvvc(n,m,args...);
}
//CF854E
void rotvvc(int&n,int&m){
	swap(n,m);
}
template<class t,class... Args>
void rotvvc(int&n,int&m,vvc<t>&a,Args&...args){
	assert(si(a)==n);
	vvc<t> b(m,vi(n));
	rep(i,n){
		assert(si(a[i])==m);
		rep(j,m)b[m-1-j][i]=a[i][j];
	}
	a.swap(b);
	rotvvc(n,m,args...);
}

//ソートして i 番目が idx[i]
//CF850C
template<class t>
vi sortidx(const vc<t>&a){
	int n=si(a);
	vi idx(n);iota(all(idx),0);
	sort(all(idx),[&](int i,int j){return a[i]<a[j];});
	return idx;
}
//vs[i]=a[idx[i]]
//例えば sortidx で得た idx を使えば単にソート列になって返ってくる
//CF850C
template<class t>
vc<t> a_idx(const vc<t>&a,const vi&idx){
	int n=si(a);
	assert(si(idx)==n);
	vc<t> vs(n);
	rep(i,n)vs[i]=a[idx[i]];
	return vs;
}
//CF850C
vi invperm(const vi&p){
	int n=si(p);
	vi q(n);
	rep(i,n)q[p[i]]=i;
	return q;
}

template<class t,class s=t>
s SUM(const vc<t>&a){
	return accumulate(all(a),s(0));
}

template<class t>
t MAX(const vc<t>&a){
	return *max_element(all(a));
}

template<class t>
t MIN(const vc<t>&a){
	return *min_element(all(a));
}

template<class t>
pair<t,int> MINi(const vc<t>&a){
	auto itr=min_element(all(a));
	return mp(*itr,itr-a.bg);
}

template<class t,class u>
pair<t,u> operator+(const pair<t,u>&a,const pair<t,u>&b){
	return mp(a.a+b.a,a.b+b.b);
}

vi vid(int n){
	vi res(n);iota(all(res),0);
	return res;
}

template<class S>
S getrev(S s){
	reverse(all(s));
	return s;
}

pi operator+(pi a,pi b){return pi(a.a+b.a,a.b+b.b);}

template<class t>
t gpp(vc<t>&vs){
	assert(si(vs));
	t res=move(vs.back());
	vs.pop_back();
	return res;
}

//copied from yosupo's library
//ptARTLY VERIFIED

//USACO 2022 January ptlatinum C

//#define GEOF

#ifdef GEOF
using ld=long double;
//using ld=double;
const ld PI=acos(ld(-1));
#else
using ld=ll;
#endif
const ld eps=1e-9;
int sgn(ld a){return a<-eps?-1:(a>eps?1:0);}
int sgn(ld a,ld b){return sgn(a-b);}
/*
using pt=complex<ld>;
#define x real()
#define y imag()
*/
struct pt {
    ld x,y;
    //pt(ld _x = ld(0), ld _y = ld(0)) : x(_x), y(_y) {}
    pt():x(0),y(0){}
    pt(ld xx,ld yy):x(xx),y(yy){}
    pt operator+(const pt& r) const { return {x + r.x, y + r.y}; }
    pt operator-(const pt& r) const { return {x - r.x, y - r.y}; }
    pt operator*(const pt& r) const {
        return {x * r.x - y * r.y, x * r.y + y * r.x};
    }
    pt inv()const{
		ld d=norm();
		return {x/d,-y/d};
	}
    pt operator/(const pt&r)const{
		return operator*(r.inv());
	}

    pt operator*(const ld& r) const { return {x * r, y * r}; }
    pt operator/(const ld& r) const { return {x / r, y / r}; }

    pt& operator+=(const pt& r) { return *this = *this + r; }
    pt& operator-=(const pt& r) { return *this = *this - r; }
    pt& operator*=(const pt& r) { return *this = *this * r; }
    pt& operator/=(const pt& r) { return *this = *this / r; }
    pt& operator*=(const ld& r) { return *this = *this * r; }
    pt& operator/=(const ld& r) { return *this = *this / r; }

    pt operator-() const { return {-x, -y}; }

	static int cmp(const pt&a,const pt&b){
		int v=sgn(a.x,b.x);
		return v?v:sgn(a.y,b.y);
	}
    bool operator<(const pt& r) const {
        return cmp(*this,r)<0;
    }
    bool operator<=(const pt& r) const {
        return cmp(*this,r)<=0;
    }
    bool operator>(const pt& r) const {
        return cmp(*this,r)>0;
    }
    bool operator==(const pt& r) const { return sgn((*this - r).rabs()) == 0; }
    bool operator!=(const pt& r) const { return !(*this == r); }

    ld norm() const { return x * x + y * y; }
    ld rabs() const { return max(std::abs(x), std::abs(y)); }  // robust abs
    pair<ld, ld> to_pair() const { return {x, y}; }
    #ifdef GEOF
    ld abs() const { return sqrt(norm()); }
    ld arg() const { return atan2(y, x); }
    static pt polar(ld le, ld th) { return {le * cos(th), le * sin(th)}; }
	#endif
};
istream& operator>>(istream& is, pt& p){
	return is>>p.x>>p.y;
}
ostream& operator<<(ostream& os, const pt& p) {
    return os << "pt(" << p.x << ", " << p.y << ")";
}
ld norm(const pt&a){
	return a.norm();
}
#ifdef GEOF
ld abs(const pt&a){
	return sqrt(norm(a));
}
//XXII Opencup Gpt of Ural K
pt normalized(const pt&a){
	return a/abs(a);
}
ld arg(const pt&a){return a.arg();}
//normalize to [-PI,PI)
//Contest 2: ptKU Contest 1, ptTZ Summer 2022 Day 4
ld normarg(ld a){
	ld res=fmod(a+PI,2*PI);
	if(res<0)res+=PI;
	else res-=PI;
	return res;
}
//AOJ1183
//arg between ab
//assume given lengths are valid
ld arg(ld a,ld b,ld c){
	return acos(min(max((a*a+b*b-c*c)/(2*a*b),ld(-1)),ld(1)));
}
#endif
ld norm(const pt&a,const pt&b){
	return (a-b).norm();
}
ld dot(const pt&a,const pt&b){return a.x*b.x+a.y*b.y;}
ld crs(const pt& a,const pt& b){return a.x*b.y-a.y*b.x;}
ld crs(const pt& a,const pt& b,const pt& c){return crs(b-a,c-a);}
int ccw(const pt& a,const pt& b){return sgn(crs(a,b));}
int ccw(const pt& a,const pt& b,const pt& c){return ccw(b-a,c-a);}
//(-pi,0](0,pi]
int argtype(const pt&a){
	if(sgn(a.y)==0)return a.x<0?1:0;
	return a.y<0?0:1;
}
int argcmp(const pt&a,const pt&b){
	int at=argtype(a),bt=argtype(b);
	if(at!=bt)return at<bt?-1:1;
	return -ccw(a,b);
};
bool argless(const pt&a,const pt&b){return argcmp(a,b)<0;}
//(-2)[a,-1](0)[b,1](2)
int bet(pt a,pt b,pt c){
	pt d=b-a;
	ld e=dot(d,c-a);
	if(sgn(e)<=0)return sgn(e)-1;
	return sgn(e-norm(d))+1;
}
//AOJ0153
//三角形 abc に d が含まれるか?0-no,1-edge,2-in
int cont(pt a,pt b,pt c,pt d){
	if(ccw(a,b,c)==-1) swap(b,c);
	return min({ccw(a,b,d),ccw(b,c,d),ccw(c,a,d)})+1;
}
//(a,b) を結ぶ直線を考え,x 座標との交点の y 座標を求める
//(分子,分母)を返す
pair<ld,ld> xcut(const pt&a,const pt&b,ld x){
	return mp(a.y*(b.x-x)-b.y*(a.x-x),b.x-a.x);
}
//XXII Opencup Gpt of Ural K
pt rot90(pt a){
	return pt(-a.y,a.x);
}
#ifdef GEOF
ld xcutval(const pt&a,const pt&b,ld x){
	auto [p,q]=xcut(a,b,x);
	return p/q;
}
//AOJ1183
//Xmas2010 E
//-+ の 順で返す
//a の符号により,small/large が決まる
int qeq(ld a,ld b,ld c,ld&d,ld&e){
	if(sgn(a)==0){
		if(sgn(b)==0)return 0;
		d=-c/b;
		return 1;
	}
	ld f=b*b-4*a*c;
	if(sgn(f)<0)return 0;
	ld g=sqrt(max(f,ld(0)));
	d=(-b-g)/(2*a);
	e=(-b+g)/(2*a);
	return sgn(f)+1;
}
#else
pt normdir(pt a){
	if(a==pt(0,0))return a;
	int g=gcd(a.x,a.y);
	return pt(a.x/g,a.y/g);
}
#endif

ld area2(const vc<pt>&ps){
	ld res=0;
	rep(i,si(ps))res+=crs(ps[i],ps[(i+1)%si(ps)]);
	return res;
}

//The 1st Universal Cup. Stage 15: Hangzhou J
struct S{
	//多分線分同士が端点以外で交わらないというケースだけ動くコード
	//線分に接するみたいな状況が発生すると話が変わってきてしまう
	pt a,b;
	S(){}
	S(const pt&aa,const pt&bb):a(min(aa,bb)),b(max(aa,bb)){assert(a<b);}
	bool operator<(const S&r)const{
		if(a==r.a)return ccw(a,b,r.b)>0;
		else if(a<r.a)return ccw(a,b,r.a)>0;
		else return ccw(r.a,r.b,a)<0;
	}
};

void flip(vc<pt>&vs){
	for(auto&[x,y]:vs)swap(x,y);
	reverse(all(vs));
}

template<class t>
struct BIT{
	vc<t> buf;
	int s;
	BIT(int n=0){init(n);}
	BIT(const vc<t>&a){init(a);}
	void init(int n){buf.clear();buf.resize(s=n);}
	void init(const vc<t>&a){
		s=si(a);
		buf.resize(s);
		rep(i,s)buf[i]=a[i];
		rep(i,s){
			int j=i+((i+1)&(-i-1));
			if(j<s)buf[j]+=buf[i];
		}
	}
	void add(int i,t v){
		for(;i<s;i+=(i+1)&(-i-1))
			buf[i]+=v;
	}
	t get(int i){
		t res=t();
		for(;i>=0;i-=(i+1)&(-i-1))
			res+=buf[i];
		return res;
	}
	t sum(int b,int e){
		return get(e-1)-get(b-1);
	}
	void add_range(int b,int e,t v){
		add(b,v);
		add(e,-v);
	}
	int kth(int k){
		int res=0;
		for(int i=topbit(s);i>=0;i--){
			int w=res+(1<<i);
			if(w<=s&&buf[w-1]<=k){
				k-=buf[w-1];
				res=w;
			}
		}
		return res;
	}
	//yukicoder No.1024
	int kth_helper(int k,int i){
		return kth(k+get(i-1));
	}
};

void slv(){
	int n;cin>>n;
	vc<pt> ps(n);
	rep(i,n)cin>>ps[i];
	
	vc<pt> ans;
	{
		vc<pt> dir;
		rep(i,n)dir.pb(ps[(i+1)%n]-ps[i]);
		sort(all(dir),argless);
		int s=0;
		for(int i=0;i<n;){
			int j=i;
			pt v;
			while(j<n&&ccw(dir[i],dir[j])==0)v+=dir[j++];
			dir[s++]=v;
			i=j;
		}
		dir.resize(s);
		pt cur;
		for(auto v:dir){
			ans.pb(cur);
			cur+=v;
		}
	}
	
	rep(_,2){
		vc<S> ss(n);
		vc<tuple<pt,int,int>> qs;
		vi kind(n);
		rep(i,n){
			pt a=ps[i],b=ps[(i+1)%n];
			ss[i]=S(a,b);
			qs.eb(ss[i].a,i,0);
			qs.eb(ss[i].b,i,1);
			kind[i]=a<b?0:1;
		}
		sort(all(qs));
		set<pair<S,int>> cur;
		vc<decltype(cur)::iterator> itrs(n);
		BIT<int> bit(n);
		auto work=[&](decltype(cur)::iterator itr,int w){
			if(itr==cur.ed||itr==cur.bg)return;
			int i=prev(itr)->b,j=itr->b;
			if(kind[i]==1&&kind[j]==0){
				if(i<j){
					bit.add_range(0,i+1,w);
					bit.add_range(j+1,n,w);
				}else{
					bit.add_range(j+1,i+1,w);
				}
			}
		};
		int mx=-inf;
		for(auto[x,y]:ps)chmax(mx,x);
		int pre=0;
		for(auto [pos,i,k]:qs){
			if(si(cur)){
				int b=cur.bg->b;
				mx+=(pos.x-pre)*bit.get(b);
			}
			pre=pos.x;
			if(k==0){
				auto obj=mp(ss[i],i);
				auto itr=cur.lower_bound(obj);
				work(itr,-1);
				itr=cur.insert(itr,obj);
				work(itr,1);
				work(next(itr),1);
				itrs[i]=itr;
			}else{
				auto itr=itrs[i];
				work(itr,-1);
				work(next(itr),-1);
				work(cur.erase(itr),1);
			}
		}
		int now=-inf;
		for(auto[x,y]:ans)chmax(now,x);
		mx-=now;
		for(auto&[x,y]:ans)x+=mx;
		flip(ps);
		flip(ans);
	}
	rotate(ans.bg,min_element(all(ans)),ans.ed);
	print(si(ans));
	for(auto[x,y]:ans)print(x,y);
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	//int t;cin>>t;rep(_,t)
	slv();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

6
0 2
1 0
6 0
12 3
9 4
3 3

result:

ok 13 numbers

Test #2:

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

input:

3
3 1
5 0
0 3

output:

3
0 3
3 1
5 0

result:

ok 7 numbers

Test #3:

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

input:

3
0 2
5 10
3 8

output:

3
0 2
5 10
3 8

result:

ok 7 numbers

Test #4:

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

input:

3
9 8
6 6
7 3

output:

3
6 6
7 3
9 8

result:

ok 7 numbers

Test #5:

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

input:

4
5 0
5 1
0 3
3 1

output:

4
0 3
3 1
5 0
5 1

result:

ok 9 numbers

Test #6:

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

input:

4
5 10
3 8
0 2
10 9

output:

4
0 2
10 9
5 10
3 8

result:

ok 9 numbers

Test #7:

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

input:

4
7 3
6 6
9 8
0 3

output:

4
0 3
7 3
10 5
9 8

result:

ok 9 numbers

Test #8:

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

input:

5
0 3
0 0
5 0
5 1
3 1

output:

5
0 0
5 0
5 1
2 3
0 3

result:

ok 11 numbers

Test #9:

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

input:

5
5 10
3 8
1 6
0 2
10 9

output:

4
0 2
10 9
5 10
1 6

result:

ok 9 numbers

Test #10:

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

input:

5
9 8
8 8
0 3
7 3
6 6

output:

5
0 3
7 3
10 5
9 8
8 8

result:

ok 11 numbers

Test #11:

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

input:

6
5 0
9 1
0 3
0 0
3 1
5 1

output:

5
0 -1
2 -1
6 0
9 1
0 3

result:

ok 11 numbers

Test #12:

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

input:

6
10 9
5 10
3 8
1 6
0 3
0 2

output:

5
0 2
10 9
5 10
1 6
0 3

result:

ok 11 numbers

Test #13:

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

input:

6
9 8
8 8
6 6
7 3
0 3
8 1

output:

5
-1 6
0 3
8 1
9 8
1 8

result:

ok 11 numbers

Test #14:

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

input:

7
0 3
0 0
3 1
5 1
5 0
9 1
4 5

output:

6
0 -1
2 -1
6 0
9 1
4 5
0 3

result:

ok 13 numbers

Test #15:

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

input:

7
0 3
0 2
10 9
8 10
5 10
3 8
1 6

output:

6
0 2
10 9
8 10
5 10
1 6
0 3

result:

ok 13 numbers

Test #16:

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

input:

7
1 4
0 3
8 1
7 3
6 6
9 8
8 8

output:

7
0 3
8 1
11 3
10 6
9 8
8 8
1 4

result:

ok 15 numbers

Test #17:

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

input:

8
0 3
0 0
5 0
9 1
5 6
5 1
4 5
3 1

output:

7
0 0
5 0
9 1
8 5
4 10
1 12
0 8

result:

ok 15 numbers

Test #18:

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

input:

8
0 3
0 2
10 9
8 10
5 10
3 8
1 6
1 5

output:

6
0 2
10 9
8 10
5 10
1 6
0 4

result:

ok 13 numbers

Test #19:

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

input:

8
6 6
7 3
0 3
8 1
9 2
9 8
8 8
1 4

output:

7
-6 4
-5 1
3 -1
8 1
9 2
9 8
1 8

result:

ok 15 numbers

Test #20:

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

input:

9
0 3
3 1
0 0
5 0
9 1
5 1
5 6
4 5
0 10

output:

9
-3 2
0 0
5 0
9 1
9 6
5 11
1 11
-2 10
-3 9

result:

ok 19 numbers

Test #21:

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

input:

9
1 5
1 6
0 3
0 2
10 9
8 10
7 9
5 10
3 8

output:

7
0 2
10 9
10 10
6 12
3 9
1 6
0 3

result:

ok 15 numbers

Test #22:

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

input:

9
8 1
9 2
7 3
6 6
9 8
8 8
3 6
1 4
0 3

output:

8
0 3
8 1
11 3
12 4
11 7
9 8
8 8
3 6

result:

ok 17 numbers

Test #23:

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

input:

10
0 3
0 0
3 1
2 8
5 0
5 1
9 1
4 5
5 6
0 10

output:

8
0 0
3 -8
7 -8
10 -7
11 -6
11 -5
10 2
0 10

result:

ok 17 numbers

Test #24:

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

input:

10
3 8
1 6
1 5
0 3
0 2
7 9
9 2
10 9
8 10
5 10

output:

8
0 2
2 -5
9 2
10 9
8 10
5 10
1 6
0 4

result:

ok 17 numbers

Test #25:

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

input:

10
6 5
7 3
1 4
0 3
8 1
9 2
9 8
6 6
8 8
3 6

output:

9
-4 6
-3 4
0 3
8 1
11 4
11 10
5 11
0 9
-3 7

result:

ok 19 numbers

Test #26:

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

input:

100
20746 24250
19390 27903
20738 28591
17627 29222
17257 29828
17643 27224
13645 28829
4947 29768
740 27903
8029 24475
12367 22096
20523 18385
19221 18188
20034 16153
23414 12434
17681 16102
22543 11459
16501 15789
20487 11789
22065 9374
13105 16558
18292 10164
23602 8359
17622 10015
15704 6154
161...

output:

100
-76364 59586
-76041 54017
-75873 51585
-75515 46493
-75129 43889
-73790 37860
-73358 35964
-72235 31789
-71416 29067
-70969 27722
-70802 27288
-69989 25253
-68411 22838
-66594 20143
-61407 13749
-58027 10030
-54041 6030
-49179 1387
-48283 558
-45383 -1752
-43783 -3018
-41556 -4504
-32688 -9857
-...

result:

ok 201 numbers

Test #27:

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

input:

100
12374 21622
8321 21323
7587 15256
8082 13844
4265 8190
2763 8830
3291 10667
4013 14045
3997 20828
1131 12972
2846 13803
2683 13530
1272 7720
2694 12951
1806 3030
6227 7277
8078 7151
10121 9887
5780 7623
4969 7097
7696 9828
10311 15510
10265 14615
11227 15213
11431 14991
12221 16529
9379 10613
13...

output:

100
-57449 -6736
-57017 -9772
-56197 -14797
-54491 -21242
-53996 -22654
-53652 -23409
-50351 -29118
-46848 -33209
-46644 -33431
-43966 -35933
-41253 -37419
-38125 -38602
-34810 -39294
-29135 -40475
-26298 -41057
-17140 -42298
-15289 -42424
-7547 -42510
16428 -42352
25820 -42055
37521 -41543
38375 -4...

result:

ok 201 numbers

Test #28:

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

input:

100
1891 21264
2730 21023
553 12585
45 9373
13 8094
4714 14911
5096 17289
6841 20444
10456 21687
9713 19115
11893 19506
7490 3528
5881 4644
7971 9597
8646 11939
8720 15832
6636 8306
3079 9218
146 4169
9359 401
10506 547
13112 11267
13113 5661
12337 4988
14710 2022
14673 2492
16140 1281
18258 462
201...

output:

100
-22303 -4740
-22302 -10346
-22272 -19790
-21967 -22348
-19387 -35419
-18930 -37259
-16371 -46713
-14515 -52565
-13247 -55097
-11379 -58001
-9846 -60157
-7473 -63123
-6476 -64348
-5009 -65559
-1465 -68167
898 -69646
2836 -70650
4914 -71712
7069 -72617
16282 -76385
18400 -77204
19239 -77445
22746 ...

result:

ok 201 numbers

Test #29:

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

input:

100
26057 12734
19510 5432
18986 786
18684 1409
18205 5568
16403 3744
14299 1226
11793 731
12947 424
15072 666
22618 475
23136 516
21000 913
25627 5785
27370 6400
29665 8519
24176 3212
24235 2794
27820 167
29867 2115
29968 4141
29497 16636
25418 17819
25673 18036
15173 17934
6258 15428
12595 18815
1...

output:

100
-87133 -5858
-87131 -8579
-87026 -19155
-86370 -24788
-86311 -25206
-86143 -26183
-85075 -30405
-83932 -33426
-80419 -39623
-79750 -40301
-76064 -43790
-72479 -46417
-68972 -48472
-66516 -49620
-59368 -52793
-57000 -53779
-55846 -54086
-48445 -55562
-47728 -55690
-46627 -55877
-42225 -56240
-403...

result:

ok 201 numbers

Test #30:

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

input:

100
5235 8435
5506 8395
7389 9541
8743 5302
9038 2214
9653 7695
10095 2077
14192 6657
15057 9556
11458 11896
13582 7685
10400 7658
9998 11454
9522 14757
9915 15496
3044 17952
4084 20359
7286 20631
6583 23625
7782 20946
8774 19434
10871 21821
12075 22237
15409 13842
12992 21009
14811 19290
16400 1825...

output:

100
-34009 23033
-33676 17146
-33234 11528
-32939 8440
-32210 5975
-29039 -4115
-27685 -8354
-23791 -18222
-20457 -26617
-16863 -35340
-16121 -37137
-12744 -44837
-11545 -47516
-6300 -58843
-3863 -63976
-1739 -68187
-747 -69699
3235 -75709
5683 -79370
6476 -80380
8787 -83038
11745 -86216
13564 -8793...

result:

ok 201 numbers

Test #31:

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

input:

100
17308 13120
16716 13797
16621 14502
18414 21427
19236 25231
20023 18658
20574 16947
21420 7250
21467 14843
24991 9025
23810 11409
21543 15706
27422 25400
28668 24087
27177 22970
25405 13514
23608 15846
26906 8053
11483 1389
26164 4799
21802 696
27892 2188
27077 12408
29533 20406
29964 25688
2818...

output:

100
-50234 2684
-50206 466
-50136 -3147
-49983 -10153
-49941 -11169
-49758 -15343
-48912 -25040
-48125 -31613
-47766 -33440
-46603 -39038
-45017 -45308
-44466 -47019
-43340 -50362
-43082 -51074
-41652 -54517
-38354 -62310
-36849 -65777
-33325 -71595
-32079 -72908
-28337 -75718
-24580 -78509
-22474 -...

result:

ok 201 numbers

Test #32:

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

input:

100
13195 8474
13243 13395
10382 16004
9971 20563
13095 24153
12568 22934
10824 20633
10742 18619
14481 26236
14148 26544
17988 25030
25716 27058
26269 28049
28237 22195
19999 24146
24878 21546
15004 20590
17801 23881
16777 23010
16461 23111
12223 18721
12327 18711
27929 21974
26948 19893
23739 1440...

output:

100
-65087 -29805
-65000 -30285
-63431 -38528
-62664 -42122
-60696 -47976
-59876 -49082
-58390 -50633
-56212 -52872
-54265 -54626
-51963 -56688
-47479 -60218
-42600 -62818
-38153 -65065
-35687 -66284
-26808 -70173
-22968 -71687
-18746 -73180
-14950 -73606
-14846 -73616
756 -70353
8484 -68325
9826 -6...

result:

ok 201 numbers

Test #33:

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

input:

100
25017 22553
25976 23127
27798 21537
28614 19976
29954 22715
25338 24110
23441 24015
27699 27208
19233 25469
28337 27680
18549 28742
15776 27115
15114 26390
15668 22761
12096 27867
11059 29765
8850 26693
7370 27499
2071 29618
1587 26581
51 22449
2286 23655
2544 24840
3246 24822
5628 19543
2799 28...

output:

100
-48994 35910
-48883 34640
-48523 30780
-48111 26383
-47221 20119
-46667 16490
-46063 13280
-45674 12043
-43292 6764
-42476 5203
-37980 -1708
-32904 -7053
-29458 -10384
-27636 -11974
-20631 -17367
-17512 -19692
-6693 -27092
-5287 -27861
-3611 -28586
-2371 -29025
-1339 -29314
1457 -29863
6343 -305...

result:

ok 201 numbers

Test #34:

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

input:

100
22149 5694
22996 3719
22887 2873
18805 1531
24090 2052
23300 7211
23266 7109
22074 13196
25396 9631
25429 8776
23787 9532
25098 4063
25910 4146
26233 3533
27367 6154
26267 10310
20585 15569
19036 15328
19959 16697
25320 14521
29432 12835
22706 17183
24387 17609
22624 19128
22485 20396
25557 2044...

output:

100
-12980 24568
-12819 3751
-12786 2896
-12196 -3533
-11526 -8056
-10215 -13525
-9105 -17244
-5607 -27118
-3106 -33858
-2259 -35833
-1518 -37480
1161 -43137
1484 -43750
2437 -45557
5503 -50393
6943 -52578
9290 -55261
12612 -58826
14799 -61162
16449 -62738
21824 -67531
22993 -68325
24215 -69049
2817...

result:

ok 201 numbers

Test #35:

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

input:

100
24257 8595
24091 12997
27162 15922
25559 2440
26639 9444
26241 2268
23168 1625
23315 460
25689 334
27781 4057
29131 18248
29125 10852
29364 22555
27704 19659
26217 21521
25891 21978
25167 23680
19955 24297
22902 23685
15239 24892
5833 28273
5544 29145
8454 28478
20412 28920
21445 28731
25445 267...

output:

100
-64897 -85387
-64496 -105456
-64432 -107228
-64285 -108393
-62923 -114070
-61089 -119265
-60117 -120786
-54886 -128610
-54292 -129296
-52455 -131265
-50061 -133729
-49412 -134343
-48900 -134685
-46752 -136057
-43841 -137581
-39841 -139554
-37423 -140590
-35911 -141208
-33001 -141875
-30054 -1424...

result:

ok 201 numbers

Test #36:

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

input:

1000
28654 780
29295 2825
29267 2395
29158 917
29693 467
29696 5837
29672 6102
29973 10077
28927 12389
29590 11122
29329 11754
29448 12201
29752 13049
29733 19345
29963 13786
29885 19045
29914 20554
29788 24129
29905 24813
29446 27670
29218 26208
28993 25001
29291 28117
29601 29380
28488 29895
27707...

output:

999
-161309 -50151
-161303 -50863
-161300 -51127
-161216 -56441
-161194 -57640
-161116 -61513
-161047 -64475
-160953 -68341
-160918 -69742
-160909 -70073
-160780 -74793
-160660 -78821
-160642 -79373
-160544 -82250
-160426 -85434
-160419 -85609
-160189 -91168
-160105 -92844
-159525 -104292
-159452 -1...

result:

ok 1999 numbers

Test #37:

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

input:

1000
3502 5911
3888 6070
4742 7895
4907 7226
4969 7097
5136 5618
6227 7277
7535 10516
6267 8155
5780 7623
6089 8332
8306 12100
12905 14524
11769 13230
11451 12932
12702 14015
11104 12426
9460 11587
8658 11334
11805 11468
10256 11406
10257 11609
12465 11915
13308 12906
14187 14486
14530 14912
16137 1...

output:

1000
-333863 65523
-333848 62879
-333807 60923
-333758 59348
-333726 58660
-333550 55296
-333535 55026
-333485 54249
-333274 51294
-333140 49505
-332653 44697
-332404 42287
-332237 40808
-332134 39909
-332025 38990
-331791 37270
-331643 36209
-331382 34688
-331278 34082
-331136 33282
-331009 32574
-...

result:

ok 2001 numbers

Test #38:

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

input:

1000
146 4169
444 7124
456 8436
3376 6808
3794 6549
4625 5934
5126 6525
5081 5586
4217 5568
1715 6792
3828 5580
3504 5258
981 6457
1037 6356
3432 4958
4402 4712
4378 5150
4518 5069
6307 3871
6945 3715
5881 4644
5643 5665
5847 4797
6566 5741
7179 5827
7029 6110
9183 5820
5705 7073
9321 6362
8373 7002...

output:

999
-224380 -13078
-224370 -16454
-224368 -16943
-224359 -18373
-224308 -22989
-224301 -23577
-224163 -30186
-224099 -33134
-224002 -37496
-223938 -40352
-223851 -43025
-223718 -46865
-223692 -47473
-223631 -48451
-223623 -48572
-223565 -49441
-223548 -49661
-223511 -50131
-223295 -52781
-223198 -53...

result:

ok 1999 numbers

Test #39:

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

input:

1000
28306 28709
27756 28602
28168 29138
27968 29655
23192 28927
19635 28418
21257 28629
21311 28313
24120 28436
25766 28497
23395 27915
22372 28307
21642 27941
22255 27005
22683 27012
24458 27654
22196 25696
21413 25370
20608 25388
20089 26041
19363 25967
21299 26467
19572 27090
18998 27141
18564 2...

output:

998
-293958 -28655
-293956 -29856
-293946 -34112
-293935 -37793
-293891 -51840
-293629 -74417
-293608 -75553
-293534 -78471
-293457 -81472
-293394 -83879
-293370 -84743
-293344 -85526
-293273 -87576
-293090 -92609
-292977 -95550
-292747 -101327
-292684 -102831
-292656 -103478
-292626 -104113
-292589...

result:

ok 1997 numbers

Test #40:

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

input:

1000
565 15947
673 16025
1508 14456
1936 15014
2093 10493
1937 9005
1797 9654
1755 6289
1654 4717
1615 4780
1441 4901
1516 3432
860 3185
187 2776
2069 2682
7358 5622
8571 6626
7932 5832
9418 7360
9653 7695
10739 8615
14897 13056
11092 9324
12139 10403
15259 13929
15409 13842
17001 15534
15791 13836
...

output:

1000
-257520 -173739
-257511 -174552
-257509 -174699
-257458 -177496
-257411 -178885
-257336 -181083
-257179 -185604
-257104 -187073
-257011 -188874
-256821 -192488
-256734 -193918
-256706 -194366
-256653 -195204
-256457 -198110
-256292 -200354
-256264 -200716
-256219 -201287
-256068 -202912
-256006...

result:

ok 2001 numbers

Test #41:

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

input:

1000
654 29657
7383 26552
9100 25461
8525 25702
9350 24959
11334 24668
10912 23539
13656 23277
12092 23300
20023 18658
19837 18430
16123 20567
16854 18913
16940 18283
17208 18023
18073 18093
14828 17246
16092 16815
16799 16802
16867 16573
15941 16291
16104 15547
16633 15325
18462 17231
18510 17431
1...

output:

1000
-222784 48489
-222780 46933
-222774 45004
-222733 42263
-222721 41494
-222573 33231
-222503 29618
-222481 28682
-222393 25162
-222325 23333
-222185 19955
-222105 18101
-222037 16666
-221592 8248
-221466 6316
-221387 5149
-221315 4127
-221175 2252
-221122 1555
-221006 119
-220536 -5181
-220109 -...

result:

ok 2001 numbers

Test #42:

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

input:

1000
17923 6211
17420 6963
17364 5148
18532 3007
19744 729
20516 883
22055 2020
22115 807
22174 2669
20677 1191
22453 3830
18742 6797
17913 7735
18236 8001
19512 6411
19402 6688
19283 7250
19345 7865
18705 7952
18986 8315
18336 8745
16952 9793
17340 8683
17756 9172
17551 8384
17031 8163
16460 10429
...

output:

1000
-230783 -35942
-230720 -38579
-230703 -39248
-230644 -41486
-230528 -44803
-230492 -45821
-230473 -46217
-230462 -46441
-230402 -47654
-230320 -49195
-230296 -49584
-230191 -51250
-230092 -52666
-229942 -54594
-229912 -54956
-229838 -55848
-229821 -56052
-229735 -57083
-229708 -57388
-229688 -5...

result:

ok 2001 numbers

Test #43:

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

input:

1000
12639 27424
12096 27867
17135 27895
11711 28035
11689 27976
9940 28085
11024 28423
13942 28064
14563 28350
11808 28559
20107 28088
14314 28613
11997 28556
7815 29143
6138 29349
20481 28522
18549 28742
17431 29011
16516 28911
15365 29048
11042 29328
16391 29125
14271 29468
23785 28776
24397 2879...

output:

1000
-291349 -20402
-291348 -20801
-291345 -21402
-291338 -22245
-291225 -29078
-291141 -31493
-291084 -32848
-291078 -32979
-290945 -35353
-290797 -37878
-290760 -38439
-290742 -38703
-290654 -39806
-290335 -43492
-290320 -43661
-290305 -43815
-290076 -46156
-289669 -49303
-289338 -51720
-288435 -5...

result:

ok 2001 numbers

Test #44:

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

input:

1000
515 24522
352 25014
2112 21822
1423 24459
2763 23823
3729 22462
4941 20740
3366 21949
2684 22752
1813 23549
1860 23093
3193 21226
3294 20687
2999 20449
3186 19723
4985 16066
5185 16012
4826 17157
6481 16253
6747 16253
7345 16119
6959 16620
5756 18354
5557 19323
7659 17176
7063 17561
11026 13217...

output:

1000
-300799 106394
-300797 105830
-300782 103194
-300642 95706
-300546 91522
-300267 80187
-300262 80018
-300192 77971
-300100 75782
-300063 74948
-300061 74907
-300023 74158
-299996 73750
-299843 71627
-299813 71223
-299609 68717
-299552 68055
-299505 67599
-298804 61349
-298758 60940
-298642 5991...

result:

ok 2001 numbers

Test #45:

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

input:

1000
5882 3788
4070 5227
4209 4230
4462 4175
2654 2513
3913 3502
3455 2944
10532 1578
13397 1035
14840 885
16385 699
14775 1084
13012 2035
17457 564
17044 1531
18237 450
22704 473
23315 460
23619 131
23437 280
20464 134
18303 211
15280 676
16056 355
11211 653
14312 683
10787 1348
8480 1735
7334 1533...

output:

1000
-225411 223109
-225396 213458
-225376 210439
-225336 205044
-225332 204668
-225276 202525
-225220 200420
-225126 196895
-225077 195358
-225030 194052
-224990 192941
-224842 188971
-224778 187599
-224752 187101
-224470 181959
-224423 181126
-224352 179948
-223971 173653
-223803 170929
-223686 16...

result:

ok 2001 numbers

Test #46:

score: 0
Accepted
time: 10ms
memory: 5696kb

input:

10000
21786 7378
21530 7264
21582 7197
21717 7084
21371 6790
21667 6711
21678 6475
21317 5665
21339 6329
21254 6494
21134 5397
21081 5356
21035 4898
21087 6718
21003 6088
20891 4542
20072 4270
19546 4055
19412 3989
18685 3793
18261 3738
18534 3803
18905 3947
19086 3999
18890 4168
19059 4041
19670 44...

output:

9650
-870078 -375256
-870076 -376403
-870075 -376907
-870074 -377396
-870073 -377686
-870072 -377960
-870070 -378440
-870069 -378638
-870065 -379334
-870054 -380906
-870052 -381152
-870044 -382101
-870029 -383729
-870027 -383943
-870023 -384370
-870019 -384790
-870014 -385311
-870008 -385935
-869996...

result:

ok 19301 numbers

Test #47:

score: 0
Accepted
time: 10ms
memory: 5432kb

input:

10000
14409 715
13309 796
14392 836
14245 939
14314 1065
14515 1214
13101 1068
12791 973
13362 1030
12480 883
12376 798
13423 688
12966 702
12046 625
11896 707
11655 788
11653 595
11183 756
11306 752
11036 769
10903 698
10568 660
10187 649
10062 535
10016 524
9443 630
9124 608
5671 318
5054 317
4946...

output:

9628
-1521329 -42898
-1521325 -44517
-1521323 -45267
-1521321 -45733
-1521320 -45939
-1521316 -46671
-1521311 -47510
-1521310 -47611
-1521302 -48395
-1521289 -49620
-1521283 -50144
-1521278 -50551
-1521265 -51594
-1521207 -55917
-1521201 -56341
-1521185 -57268
-1521169 -58185
-1521163 -58523
-152112...

result:

ok 19257 numbers

Test #48:

score: 0
Accepted
time: 15ms
memory: 5584kb

input:

10000
12565 5268
12689 5769
12577 5217
13113 5661
13317 5786
13468 6302
13723 6672
13599 6672
13536 6750
13278 6187
13264 5873
13204 6016
13075 6060
14071 8382
13571 7009
14095 7155
14093 6785
14033 6589
13768 6311
13293 5434
13613 5640
13422 5194
13657 5616
13978 6170
13827 5773
13897 5880
13870 57...

output:

9676
-786496 -60090
-786495 -60882
-786494 -61664
-786493 -62354
-786487 -66254
-786486 -66807
-786485 -67340
-786479 -70021
-786475 -71688
-786471 -73149
-786470 -73498
-786469 -73842
-786468 -74096
-786467 -74323
-786466 -74541
-786458 -76277
-786454 -77058
-786452 -77446
-786437 -80351
-786427 -8...

result:

ok 19353 numbers

Test #49:

score: 0
Accepted
time: 15ms
memory: 5436kb

input:

10000
15604 25876
14880 26175
14537 26330
14960 26073
14160 26437
13904 26571
13784 26625
14146 26377
14333 26309
15580 25604
14063 26115
13949 26156
14312 26108
13621 26438
12510 26911
12736 26930
13243 26801
13595 26510
13951 26420
15265 25773
14887 25979
12748 27071
12115 27127
11562 27335
11047 ...

output:

9651
-1172245 245973
-1172243 245025
-1172242 244579
-1172240 243828
-1172238 243156
-1172237 242839
-1172236 242540
-1172231 241063
-1172230 240790
-1172228 240374
-1172227 240181
-1172215 238100
-1172214 237936
-1172195 234991
-1172183 233350
-1172182 233215
-1172177 232620
-1172173 232164
-117216...

result:

ok 19303 numbers

Test #50:

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

input:

10000
2050 16933
2243 17485
2386 17490
2599 17531
2640 17802
2695 18081
2693 18084
3222 19338
3399 19459
3544 19300
3041 18176
2777 18004
2895 18425
2721 18087
2856 17749
3222 18192
3534 18611
2869 17766
3050 18135
3315 18597
3617 18914
3989 17662
3963 17567
4070 17285
4223 16999
4218 17179
4138 176...

output:

9647
-845930 128827
-845928 127440
-845927 126811
-845919 124431
-845911 122568
-845909 122116
-845908 121903
-845905 121398
-845900 120657
-845883 118289
-845842 112701
-845835 111815
-845813 109043
-845806 108188
-845803 107827
-845798 107242
-845793 106676
-845783 105587
-845774 104640
-845754 10...

result:

ok 19295 numbers

Test #51:

score: 0
Accepted
time: 15ms
memory: 5396kb

input:

10000
7481 8846
7714 8562
6791 9620
8352 7473
8013 8125
8868 7114
8937 7290
9169 7802
9383 7575
9254 7582
9103 7291
8903 7136
9126 6846
9182 7245
9212 6914
9314 7074
9372 7336
9690 6736
9638 6943
9615 7150
9637 7136
9786 6648
10017 6116
10743 5128
10224 5462
9494 5661
9482 5641
10008 4842
10860 3870...

output:

9617
-1080989 127415
-1080988 127145
-1080986 126629
-1080982 125844
-1080981 125678
-1080965 123166
-1080960 122498
-1080959 122372
-1080957 122126
-1080954 121777
-1080951 121484
-1080936 120034
-1080935 119940
-1080927 119224
-1080923 118915
-1080922 118847
-1080918 118594
-1080910 118090
-108090...

result:

ok 19235 numbers

Test #52:

score: 0
Accepted
time: 16ms
memory: 5736kb

input:

10000
25777 10251
25945 9963
25623 10799
25339 11234
25245 11675
25016 13036
25098 11622
24829 13500
24537 13883
22110 15173
24009 14168
24305 14029
24272 14177
24257 14302
24341 14202
24004 15795
23935 16182
23521 18133
23610 18193
23725 17755
23760 17768
23778 17825
23852 17051
23759 17102
23940 1...

output:

9668
-896167 387277
-896165 384343
-896156 378489
-896155 378082
-896148 375797
-896146 375197
-896136 372466
-896121 368791
-896116 367744
-896103 365790
-896100 365342
-896084 363012
-896070 361039
-896065 360343
-896060 359699
-896039 357178
-896034 356605
-896023 355381
-896022 355276
-896017 35...

result:

ok 19337 numbers

Test #53:

score: 0
Accepted
time: 9ms
memory: 5604kb

input:

10000
2098 26014
3747 26207
3717 26225
3972 26260
5866 26434
10188 26945
7901 26676
11334 27108
10289 26991
7969 26709
5570 26501
3022 26157
2567 26099
1985 26146
1391 26226
1639 26347
1587 26581
1541 26713
1504 26713
1065 26544
770 27084
962 26811
671 27705
627 26798
574 28073
621 28410
505 28563
4...

output:

9674
-999959 -38208
-999957 -40388
-999952 -43643
-999950 -44929
-999949 -45559
-999940 -49659
-999932 -51625
-999930 -52052
-999915 -55131
-999913 -55534
-999909 -56193
-999886 -59969
-999885 -60126
-999860 -63909
-999852 -65088
-999842 -66560
-999831 -67947
-999816 -69620
-999798 -71587
-999793 -7...

result:

ok 19349 numbers

Test #54:

score: 0
Accepted
time: 10ms
memory: 5452kb

input:

10000
26051 2211
26706 2644
26030 2486
25615 2560
26337 2760
27031 2833
27170 3186
27594 3108
27291 2686
27516 3052
27298 2756
27091 2396
26992 2304
26844 2195
26788 2246
26779 2006
27258 2489
28128 3477
28378 3762
28331 3599
28246 3472
27833 2976
25850 730
25368 770
25059 678
24005 891
23528 1232
2...

output:

9667
-1390076 -559982
-1390075 -560657
-1390074 -561273
-1390073 -561760
-1390069 -563697
-1390068 -564144
-1390067 -564534
-1390064 -565681
-1390061 -566256
-1390055 -567091
-1390052 -567480
-1390001 -573212
-1390000 -573307
-1389987 -574483
-1389978 -575202
-1389975 -575422
-1389943 -577754
-13899...

result:

ok 19335 numbers

Test #55:

score: 0
Accepted
time: 11ms
memory: 5396kb

input:

10000
19793 5647
19453 5794
19763 5628
20776 5097
20726 5309
21099 5159
20966 5378
21828 5237
21769 5491
21567 5436
21290 5461
21335 5640
21177 5700
21262 6502
21260 6515
21529 6374
21517 5903
22107 4978
22637 4520
22541 4509
22413 4432
22469 4276
21926 4596
21932 4533
22747 3916
22981 3864
23163 37...

output:

9644
-954170 209078
-954166 202714
-954164 200511
-954162 198330
-954160 196376
-954156 193869
-954155 193326
-954148 189987
-954146 189195
-954145 188828
-954139 186690
-954134 184933
-954133 184584
-954130 183545
-954128 182869
-954127 182580
-954116 179482
-954111 178213
-954107 177443
-954103 17...

result:

ok 19289 numbers

Test #56:

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

input:

4
0 0
1 1
2 1
4 5

output:

4
0 0
1 0
2 1
4 5

result:

ok 9 numbers

Test #57:

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

input:

8
0 0
1 1
3 5
6 14
7 14
11 30
12 30
16 46

output:

6
0 0
2 0
3 1
5 5
8 14
16 46

result:

ok 13 numbers

Test #58:

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

input:

12
0 0
1 1
3 5
6 14
10 30
15 55
16 55
22 91
23 91
29 127
30 127
36 163

output:

8
0 0
3 0
4 1
6 5
9 14
13 30
18 55
36 163

result:

ok 17 numbers

Test #59:

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

input:

16
0 0
1 1
3 5
6 14
10 30
15 55
21 91
28 140
29 140
37 204
38 204
46 268
47 268
55 332
56 332
64 396

output:

10
0 0
4 0
5 1
7 5
10 14
14 30
19 55
25 91
32 140
64 396

result:

ok 21 numbers

Test #60:

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

input:

20
0 0
1 1
3 5
6 14
10 30
15 55
21 91
28 140
36 204
45 285
46 285
56 385
57 385
67 485
68 485
78 585
79 585
89 685
90 685
100 785

output:

12
0 0
5 0
6 1
8 5
11 14
15 30
20 55
26 91
33 140
41 204
50 285
100 785

result:

ok 25 numbers

Test #61:

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

input:

24
0 0
1 1
3 5
6 14
10 30
15 55
21 91
28 140
36 204
45 285
55 385
66 506
67 506
79 650
80 650
92 794
93 794
105 938
106 938
118 1082
119 1082
131 1226
132 1226
144 1370

output:

14
0 0
6 0
7 1
9 5
12 14
16 30
21 55
27 91
34 140
42 204
51 285
61 385
72 506
144 1370

result:

ok 29 numbers

Test #62:

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

input:

28
0 0
1 1
3 5
6 14
10 30
15 55
21 91
28 140
36 204
45 285
55 385
66 506
78 650
91 819
92 819
106 1015
107 1015
121 1211
122 1211
136 1407
137 1407
151 1603
152 1603
166 1799
167 1799
181 1995
182 1995
196 2191

output:

16
0 0
7 0
8 1
10 5
13 14
17 30
22 55
28 91
35 140
43 204
52 285
62 385
73 506
85 650
98 819
196 2191

result:

ok 33 numbers

Test #63:

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

input:

32
0 0
1 1
3 5
6 14
10 30
15 55
21 91
28 140
36 204
45 285
55 385
66 506
78 650
91 819
105 1015
120 1240
121 1240
137 1496
138 1496
154 1752
155 1752
171 2008
172 2008
188 2264
189 2264
205 2520
206 2520
222 2776
223 2776
239 3032
240 3032
256 3288

output:

18
0 0
8 0
9 1
11 5
14 14
18 30
23 55
29 91
36 140
44 204
53 285
63 385
74 506
86 650
99 819
113 1015
128 1240
256 3288

result:

ok 37 numbers

Test #64:

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

input:

36
0 0
1 1
3 5
6 14
10 30
15 55
21 91
28 140
36 204
45 285
55 385
66 506
78 650
91 819
105 1015
120 1240
136 1496
153 1785
154 1785
172 2109
173 2109
191 2433
192 2433
210 2757
211 2757
229 3081
230 3081
248 3405
249 3405
267 3729
268 3729
286 4053
287 4053
305 4377
306 4377
324 4701

output:

20
0 0
9 0
10 1
12 5
15 14
19 30
24 55
30 91
37 140
45 204
54 285
64 385
75 506
87 650
100 819
114 1015
129 1240
145 1496
162 1785
324 4701

result:

ok 41 numbers

Test #65:

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

input:

40
0 0
1 1
3 5
6 14
10 30
15 55
21 91
28 140
36 204
45 285
55 385
66 506
78 650
91 819
105 1015
120 1240
136 1496
153 1785
171 2109
190 2470
191 2470
211 2870
212 2870
232 3270
233 3270
253 3670
254 3670
274 4070
275 4070
295 4470
296 4470
316 4870
317 4870
337 5270
338 5270
358 5670
359 5670
379 60...

output:

22
0 0
10 0
11 1
13 5
16 14
20 30
25 55
31 91
38 140
46 204
55 285
65 385
76 506
88 650
101 819
115 1015
130 1240
146 1496
163 1785
181 2109
200 2470
400 6470

result:

ok 45 numbers

Test #66:

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

input:

99941
0 0
1 1
300000 1
1 3
300000 3
1 5
300000 5
1 7
300000 7
1 9
300000 9
1 11
300000 11
1 13
300000 13
1 15
300000 15
1 17
300000 17
1 19
300000 19
1 21
300000 21
1 23
300000 23
1 25
300000 25
1 27
300000 27
1 29
300000 29
1 31
300000 31
1 33
300000 33
1 35
300000 35
1 37
300000 37
1 39
300000 39
...

output:

5
0 0
14990650031 0
14990650032 1
14990650031 200062
0 300000

result:

ok 11 numbers

Test #67:

score: 0
Accepted
time: 69ms
memory: 25412kb

input:

99943
0 0
300000 0
99941 1
99939 300000
99939 1
99937 300000
99937 1
99935 300000
99935 1
99933 300000
99933 1
99931 300000
99931 1
99929 300000
99929 1
99927 300000
99927 1
99925 300000
99925 1
99923 300000
99923 1
99921 300000
99921 1
99919 300000
99919 1
99917 300000
99917 1
99915 300000
99915 1
...

output:

5
0 0
300000 0
200060 14990950030
1 14990950031
0 14990950030

result:

ok 11 numbers

Test #68:

score: 0
Accepted
time: 63ms
memory: 25412kb

input:

99945
0 0
300000 0
99943 1
99941 300000
99941 1
99939 300000
99939 1
99937 300000
99937 1
99935 300000
99935 1
99933 300000
99933 1
99931 300000
99931 1
99929 300000
99929 1
99927 300000
99927 1
99925 300000
99925 1
99923 300000
99923 1
99921 300000
99921 1
99919 300000
99919 1
99917 300000
99917 1
...

output:

5
0 0
300000 0
200058 14991250029
1 14991250030
0 14991250029

result:

ok 11 numbers

Test #69:

score: 0
Accepted
time: 67ms
memory: 26224kb

input:

99947
0 0
300000 0
99945 1
99943 300000
99943 1
99941 300000
99941 1
99939 300000
99939 1
99937 300000
99937 1
99935 300000
99935 1
99933 300000
99933 1
99931 300000
99931 1
99929 300000
99929 1
99927 300000
99927 1
99925 300000
99925 1
99923 300000
99923 1
99921 300000
99921 1
99919 300000
99919 1
...

output:

5
0 0
300000 0
200056 14991550028
1 14991550029
0 14991550028

result:

ok 11 numbers

Test #70:

score: 0
Accepted
time: 67ms
memory: 25776kb

input:

99949
0 0
1 1
300000 1
1 3
300000 3
1 5
300000 5
1 7
300000 7
1 9
300000 9
1 11
300000 11
1 13
300000 13
1 15
300000 15
1 17
300000 17
1 19
300000 19
1 21
300000 21
1 23
300000 23
1 25
300000 25
1 27
300000 27
1 29
300000 29
1 31
300000 31
1 33
300000 33
1 35
300000 35
1 37
300000 37
1 39
300000 39
...

output:

5
0 0
14991850027 0
14991850028 1
14991850027 200054
0 300000

result:

ok 11 numbers

Test #71:

score: 0
Accepted
time: 78ms
memory: 25456kb

input:

99951
0 0
1 1
300000 1
1 3
300000 3
1 5
300000 5
1 7
300000 7
1 9
300000 9
1 11
300000 11
1 13
300000 13
1 15
300000 15
1 17
300000 17
1 19
300000 19
1 21
300000 21
1 23
300000 23
1 25
300000 25
1 27
300000 27
1 29
300000 29
1 31
300000 31
1 33
300000 33
1 35
300000 35
1 37
300000 37
1 39
300000 39
...

output:

5
0 0
14992150026 0
14992150027 1
14992150026 200052
0 300000

result:

ok 11 numbers

Test #72:

score: 0
Accepted
time: 60ms
memory: 25020kb

input:

99953
0 0
300000 0
99951 1
99949 300000
99949 1
99947 300000
99947 1
99945 300000
99945 1
99943 300000
99943 1
99941 300000
99941 1
99939 300000
99939 1
99937 300000
99937 1
99935 300000
99935 1
99933 300000
99933 1
99931 300000
99931 1
99929 300000
99929 1
99927 300000
99927 1
99925 300000
99925 1
...

output:

5
0 0
300000 0
200050 14992450025
1 14992450026
0 14992450025

result:

ok 11 numbers

Test #73:

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

input:

99955
0 0
300000 0
99953 1
99951 300000
99951 1
99949 300000
99949 1
99947 300000
99947 1
99945 300000
99945 1
99943 300000
99943 1
99941 300000
99941 1
99939 300000
99939 1
99937 300000
99937 1
99935 300000
99935 1
99933 300000
99933 1
99931 300000
99931 1
99929 300000
99929 1
99927 300000
99927 1
...

output:

5
0 0
300000 0
200048 14992750024
1 14992750025
0 14992750024

result:

ok 11 numbers

Test #74:

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

input:

99957
0 0
1 1
300000 1
1 3
300000 3
1 5
300000 5
1 7
300000 7
1 9
300000 9
1 11
300000 11
1 13
300000 13
1 15
300000 15
1 17
300000 17
1 19
300000 19
1 21
300000 21
1 23
300000 23
1 25
300000 25
1 27
300000 27
1 29
300000 29
1 31
300000 31
1 33
300000 33
1 35
300000 35
1 37
300000 37
1 39
300000 39
...

output:

5
0 0
14993050023 0
14993050024 1
14993050023 200046
0 300000

result:

ok 11 numbers

Test #75:

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

input:

99959
0 0
1 1
300000 1
1 3
300000 3
1 5
300000 5
1 7
300000 7
1 9
300000 9
1 11
300000 11
1 13
300000 13
1 15
300000 15
1 17
300000 17
1 19
300000 19
1 21
300000 21
1 23
300000 23
1 25
300000 25
1 27
300000 27
1 29
300000 29
1 31
300000 31
1 33
300000 33
1 35
300000 35
1 37
300000 37
1 39
300000 39
...

output:

5
0 0
14993350022 0
14993350023 1
14993350022 200044
0 300000

result:

ok 11 numbers

Test #76:

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

input:

99961
0 0
300000 0
99959 1
99957 300000
99957 1
99955 300000
99955 1
99953 300000
99953 1
99951 300000
99951 1
99949 300000
99949 1
99947 300000
99947 1
99945 300000
99945 1
99943 300000
99943 1
99941 300000
99941 1
99939 300000
99939 1
99937 300000
99937 1
99935 300000
99935 1
99933 300000
99933 1
...

output:

5
0 0
300000 0
200042 14993650021
1 14993650022
0 14993650021

result:

ok 11 numbers

Test #77:

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

input:

99963
0 0
300000 0
99961 1
99959 300000
99959 1
99957 300000
99957 1
99955 300000
99955 1
99953 300000
99953 1
99951 300000
99951 1
99949 300000
99949 1
99947 300000
99947 1
99945 300000
99945 1
99943 300000
99943 1
99941 300000
99941 1
99939 300000
99939 1
99937 300000
99937 1
99935 300000
99935 1
...

output:

5
0 0
300000 0
200040 14993950020
1 14993950021
0 14993950020

result:

ok 11 numbers

Test #78:

score: 0
Accepted
time: 60ms
memory: 25120kb

input:

99965
0 0
1 1
300000 1
1 3
300000 3
1 5
300000 5
1 7
300000 7
1 9
300000 9
1 11
300000 11
1 13
300000 13
1 15
300000 15
1 17
300000 17
1 19
300000 19
1 21
300000 21
1 23
300000 23
1 25
300000 25
1 27
300000 27
1 29
300000 29
1 31
300000 31
1 33
300000 33
1 35
300000 35
1 37
300000 37
1 39
300000 39
...

output:

5
0 0
14994250019 0
14994250020 1
14994250019 200038
0 300000

result:

ok 11 numbers

Test #79:

score: 0
Accepted
time: 74ms
memory: 25924kb

input:

99967
0 0
1 1
300000 1
1 3
300000 3
1 5
300000 5
1 7
300000 7
1 9
300000 9
1 11
300000 11
1 13
300000 13
1 15
300000 15
1 17
300000 17
1 19
300000 19
1 21
300000 21
1 23
300000 23
1 25
300000 25
1 27
300000 27
1 29
300000 29
1 31
300000 31
1 33
300000 33
1 35
300000 35
1 37
300000 37
1 39
300000 39
...

output:

5
0 0
14994550018 0
14994550019 1
14994550018 200036
0 300000

result:

ok 11 numbers

Test #80:

score: 0
Accepted
time: 69ms
memory: 25972kb

input:

99969
0 0
300000 0
99967 1
99965 300000
99965 1
99963 300000
99963 1
99961 300000
99961 1
99959 300000
99959 1
99957 300000
99957 1
99955 300000
99955 1
99953 300000
99953 1
99951 300000
99951 1
99949 300000
99949 1
99947 300000
99947 1
99945 300000
99945 1
99943 300000
99943 1
99941 300000
99941 1
...

output:

5
0 0
300000 0
200034 14994850017
1 14994850018
0 14994850017

result:

ok 11 numbers

Test #81:

score: 0
Accepted
time: 63ms
memory: 25948kb

input:

99971
0 0
300000 0
99969 1
99967 300000
99967 1
99965 300000
99965 1
99963 300000
99963 1
99961 300000
99961 1
99959 300000
99959 1
99957 300000
99957 1
99955 300000
99955 1
99953 300000
99953 1
99951 300000
99951 1
99949 300000
99949 1
99947 300000
99947 1
99945 300000
99945 1
99943 300000
99943 1
...

output:

5
0 0
300000 0
200032 14995150016
1 14995150017
0 14995150016

result:

ok 11 numbers

Test #82:

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

input:

99973
0 0
1 1
300000 1
1 3
300000 3
1 5
300000 5
1 7
300000 7
1 9
300000 9
1 11
300000 11
1 13
300000 13
1 15
300000 15
1 17
300000 17
1 19
300000 19
1 21
300000 21
1 23
300000 23
1 25
300000 25
1 27
300000 27
1 29
300000 29
1 31
300000 31
1 33
300000 33
1 35
300000 35
1 37
300000 37
1 39
300000 39
...

output:

5
0 0
14995450015 0
14995450016 1
14995450015 200030
0 300000

result:

ok 11 numbers

Test #83:

score: 0
Accepted
time: 66ms
memory: 24512kb

input:

99975
0 0
1 1
300000 1
1 3
300000 3
1 5
300000 5
1 7
300000 7
1 9
300000 9
1 11
300000 11
1 13
300000 13
1 15
300000 15
1 17
300000 17
1 19
300000 19
1 21
300000 21
1 23
300000 23
1 25
300000 25
1 27
300000 27
1 29
300000 29
1 31
300000 31
1 33
300000 33
1 35
300000 35
1 37
300000 37
1 39
300000 39
...

output:

5
0 0
14995750014 0
14995750015 1
14995750014 200028
0 300000

result:

ok 11 numbers

Test #84:

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

input:

99977
0 0
300000 0
99975 1
99973 300000
99973 1
99971 300000
99971 1
99969 300000
99969 1
99967 300000
99967 1
99965 300000
99965 1
99963 300000
99963 1
99961 300000
99961 1
99959 300000
99959 1
99957 300000
99957 1
99955 300000
99955 1
99953 300000
99953 1
99951 300000
99951 1
99949 300000
99949 1
...

output:

5
0 0
300000 0
200026 14996050013
1 14996050014
0 14996050013

result:

ok 11 numbers

Test #85:

score: 0
Accepted
time: 60ms
memory: 25316kb

input:

99979
0 0
300000 0
99977 1
99975 300000
99975 1
99973 300000
99973 1
99971 300000
99971 1
99969 300000
99969 1
99967 300000
99967 1
99965 300000
99965 1
99963 300000
99963 1
99961 300000
99961 1
99959 300000
99959 1
99957 300000
99957 1
99955 300000
99955 1
99953 300000
99953 1
99951 300000
99951 1
...

output:

5
0 0
300000 0
200024 14996350012
1 14996350013
0 14996350012

result:

ok 11 numbers

Test #86:

score: 0
Accepted
time: 73ms
memory: 25328kb

input:

99981
0 0
1 1
300000 1
1 3
300000 3
1 5
300000 5
1 7
300000 7
1 9
300000 9
1 11
300000 11
1 13
300000 13
1 15
300000 15
1 17
300000 17
1 19
300000 19
1 21
300000 21
1 23
300000 23
1 25
300000 25
1 27
300000 27
1 29
300000 29
1 31
300000 31
1 33
300000 33
1 35
300000 35
1 37
300000 37
1 39
300000 39
...

output:

5
0 0
14996650011 0
14996650012 1
14996650011 200022
0 300000

result:

ok 11 numbers

Test #87:

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

input:

99983
0 0
1 1
300000 1
1 3
300000 3
1 5
300000 5
1 7
300000 7
1 9
300000 9
1 11
300000 11
1 13
300000 13
1 15
300000 15
1 17
300000 17
1 19
300000 19
1 21
300000 21
1 23
300000 23
1 25
300000 25
1 27
300000 27
1 29
300000 29
1 31
300000 31
1 33
300000 33
1 35
300000 35
1 37
300000 37
1 39
300000 39
...

output:

5
0 0
14996950010 0
14996950011 1
14996950010 200020
0 300000

result:

ok 11 numbers

Test #88:

score: 0
Accepted
time: 73ms
memory: 25372kb

input:

99985
0 0
300000 0
99983 1
99981 300000
99981 1
99979 300000
99979 1
99977 300000
99977 1
99975 300000
99975 1
99973 300000
99973 1
99971 300000
99971 1
99969 300000
99969 1
99967 300000
99967 1
99965 300000
99965 1
99963 300000
99963 1
99961 300000
99961 1
99959 300000
99959 1
99957 300000
99957 1
...

output:

5
0 0
300000 0
200018 14997250009
1 14997250010
0 14997250009

result:

ok 11 numbers

Test #89:

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

input:

99987
0 0
300000 0
99985 1
99983 300000
99983 1
99981 300000
99981 1
99979 300000
99979 1
99977 300000
99977 1
99975 300000
99975 1
99973 300000
99973 1
99971 300000
99971 1
99969 300000
99969 1
99967 300000
99967 1
99965 300000
99965 1
99963 300000
99963 1
99961 300000
99961 1
99959 300000
99959 1
...

output:

5
0 0
300000 0
200016 14997550008
1 14997550009
0 14997550008

result:

ok 11 numbers

Test #90:

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

input:

99989
0 0
1 1
300000 1
1 3
300000 3
1 5
300000 5
1 7
300000 7
1 9
300000 9
1 11
300000 11
1 13
300000 13
1 15
300000 15
1 17
300000 17
1 19
300000 19
1 21
300000 21
1 23
300000 23
1 25
300000 25
1 27
300000 27
1 29
300000 29
1 31
300000 31
1 33
300000 33
1 35
300000 35
1 37
300000 37
1 39
300000 39
...

output:

5
0 0
14997850007 0
14997850008 1
14997850007 200014
0 300000

result:

ok 11 numbers

Test #91:

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

input:

99991
0 0
1 1
300000 1
1 3
300000 3
1 5
300000 5
1 7
300000 7
1 9
300000 9
1 11
300000 11
1 13
300000 13
1 15
300000 15
1 17
300000 17
1 19
300000 19
1 21
300000 21
1 23
300000 23
1 25
300000 25
1 27
300000 27
1 29
300000 29
1 31
300000 31
1 33
300000 33
1 35
300000 35
1 37
300000 37
1 39
300000 39
...

output:

5
0 0
14998150006 0
14998150007 1
14998150006 200012
0 300000

result:

ok 11 numbers

Test #92:

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

input:

99993
0 0
300000 0
99991 1
99989 300000
99989 1
99987 300000
99987 1
99985 300000
99985 1
99983 300000
99983 1
99981 300000
99981 1
99979 300000
99979 1
99977 300000
99977 1
99975 300000
99975 1
99973 300000
99973 1
99971 300000
99971 1
99969 300000
99969 1
99967 300000
99967 1
99965 300000
99965 1
...

output:

5
0 0
300000 0
200010 14998450005
1 14998450006
0 14998450005

result:

ok 11 numbers

Test #93:

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

input:

99995
0 0
300000 0
99993 1
99991 300000
99991 1
99989 300000
99989 1
99987 300000
99987 1
99985 300000
99985 1
99983 300000
99983 1
99981 300000
99981 1
99979 300000
99979 1
99977 300000
99977 1
99975 300000
99975 1
99973 300000
99973 1
99971 300000
99971 1
99969 300000
99969 1
99967 300000
99967 1
...

output:

5
0 0
300000 0
200008 14998750004
1 14998750005
0 14998750004

result:

ok 11 numbers

Test #94:

score: 0
Accepted
time: 54ms
memory: 24560kb

input:

99997
0 0
300000 0
99995 1
99993 300000
99993 1
99991 300000
99991 1
99989 300000
99989 1
99987 300000
99987 1
99985 300000
99985 1
99983 300000
99983 1
99981 300000
99981 1
99979 300000
99979 1
99977 300000
99977 1
99975 300000
99975 1
99973 300000
99973 1
99971 300000
99971 1
99969 300000
99969 1
...

output:

5
0 0
300000 0
200006 14999050003
1 14999050004
0 14999050003

result:

ok 11 numbers

Test #95:

score: 0
Accepted
time: 71ms
memory: 24404kb

input:

99999
0 0
1 1
300000 1
1 3
300000 3
1 5
300000 5
1 7
300000 7
1 9
300000 9
1 11
300000 11
1 13
300000 13
1 15
300000 15
1 17
300000 17
1 19
300000 19
1 21
300000 21
1 23
300000 23
1 25
300000 25
1 27
300000 27
1 29
300000 29
1 31
300000 31
1 33
300000 33
1 35
300000 35
1 37
300000 37
1 39
300000 39
...

output:

5
0 0
14999350002 0
14999350003 1
14999350002 200004
0 300000

result:

ok 11 numbers

Test #96:

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

input:

84346
50233 297807
50360 298249
50723 297811
51228 297120
50596 295439
51870 295783
50752 294903
50631 295096
50235 294179
50436 293932
51009 292907
50982 294272
52070 294353
51789 293481
52174 292595
52314 292233
52864 291350
52652 292177
52842 292492
52633 292874
52960 292738
53702 292004
53086 29...

output:

79048
-9528496 -6242618
-9528495 -6243920
-9528494 -6245017
-9528493 -6246089
-9528492 -6247132
-9528491 -6248116
-9528490 -6249053
-9528489 -6249972
-9528488 -6250768
-9528487 -6251518
-9528486 -6252230
-9528485 -6252857
-9528484 -6253452
-9528482 -6254548
-9528481 -6255085
-9528480 -6255619
-95284...

result:

ok 158097 numbers

Test #97:

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

input:

44
1 1
16 1
12 3
13 2
11 2
13 5
10 2
12 5
7 2
13 7
7 5
9 5
8 4
9 4
7 3
6 4
6 5
10 7
9 6
13 8
9 8
7 6
8 9
13 9
14 4
15 2
14 6
15 6
14 9
15 8
16 10
1 10
3 7
2 9
5 9
3 8
4 7
4 8
5 8
6 6
3 3
4 6
2 2
5 3

output:

23
-14 3
-13 -2
-11 -6
-9 -9
-6 -12
22 -12
25 -11
33 -7
39 -2
43 4
44 6
46 12
46 14
45 18
44 21
43 23
42 24
38 26
17 26
11 24
3 20
-2 17
-12 7

result:

ok 47 numbers

Test #98:

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

input:

20
1 1
3 2
2 2
3 4
5 2
4 4
7 4
6 2
8 4
9 2
8 2
10 1
10 8
7 6
9 6
6 5
5 5
2 6
4 6
1 8

output:

16
-3 -1
-2 -3
0 -5
2 -6
9 -6
11 -5
13 -3
14 -1
14 6
13 8
10 10
7 11
4 11
1 10
-2 8
-3 6

result:

ok 33 numbers

Test #99:

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

input:

110
1 5
5 2
4 5
6 2
10 4
14 2
12 4
18 3
14 3
18 2
19 4
19 3
21 2
20 4
23 4
21 3
23 2
25 4
25 2
26 3
26 6
24 5
17 5
16 4
15 5
10 6
13 5
7 5
7 4
5 4
5 6
6 6
6 5
7 7
3 7
4 6
2 6
3 13
5 12
4 10
4 12
3 8
8 8
8 6
12 7
16 5
22 6
15 6
12 8
9 7
9 9
4 9
9 10
10 8
14 9
13 9
14 11
13 11
13 10
10 9
14 12
12 11
1...

output:

40
-46 -6
-45 -8
-43 -11
-37 -17
-33 -20
-15 -29
-6 -32
2 -34
8 -35
19 -36
54 -36
63 -35
69 -34
74 -33
82 -31
88 -29
98 -24
102 -21
107 -16
112 -6
113 -3
114 4
115 13
115 26
114 29
113 31
110 34
104 38
100 39
85 42
-5 42
-12 41
-20 39
-29 36
-39 31
-41 29
-43 25
-44 21
-45 15
-46 6

result:

ok 81 numbers

Test #100:

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

input:

34
1 1
13 1
13 9
5 9
5 8
12 8
12 2
11 2
11 3
3 3
3 2
2 2
2 4
3 4
3 5
2 5
2 9
3 9
3 6
6 6
6 5
4 5
4 4
11 4
11 5
7 5
7 6
11 6
11 7
4 7
4 10
13 10
13 11
1 11

output:

4
-8 -4
36 -4
36 19
-8 19

result:

ok 9 numbers

Test #101:

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

input:

32
1 1
2 1
2 14
15 14
15 2
4 2
4 12
13 12
13 4
6 4
6 10
11 10
11 6
8 6
8 8
9 8
9 7
10 7
10 9
7 9
7 5
12 5
12 11
5 11
5 3
14 3
14 13
3 13
3 1
16 1
16 15
1 15

output:

4
-23 -27
34 -27
34 36
-23 36

result:

ok 9 numbers

Test #102:

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

input:

70
1 1
2 1
2 3
3 3
3 1
6 1
6 2
4 2
4 3
7 3
7 1
8 1
8 4
6 4
6 5
9 5
9 1
12 1
12 2
10 2
10 3
12 3
12 4
10 4
10 5
12 5
12 10
10 10
10 11
12 11
12 12
7 12
7 11
9 11
9 10
6 10
6 12
5 12
5 9
7 9
7 7
8 7
8 9
11 9
11 6
10 6
10 8
9 8
9 6
6 6
6 8
4 8
4 12
1 12
1 11
3 11
3 8
2 8
2 10
1 10
1 5
2 5
2 7
5 7
5 6
3...

output:

4
-15 -11
22 -11
22 24
-15 24

result:

ok 9 numbers

Test #103:

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

input:

106
2 2
11 1
6 2
15 1
12 2
15 4
15 3
13 2
15 2
16 5
15 6
15 7
14 5
13 4
15 5
12 3
11 2
10 3
10 2
8 3
4 3
4 5
3 7
4 9
3 11
6 11
4 10
5 9
5 10
7 11
10 11
9 10
12 10
11 11
12 11
13 9
14 7
13 7
13 8
12 6
13 6
12 5
11 6
9 5
11 5
10 4
8 5
8 4
7 5
7 7
8 6
8 8
7 8
8 9
10 8
11 7
10 7
9 8
9 6
10 6
12 7
11 8
1...

output:

25
-30 6
-29 -1
-26 -7
-18 -15
-12 -18
-8 -19
10 -21
29 -21
37 -17
40 -15
43 -12
47 -4
48 -1
48 17
45 23
35 33
27 37
24 38
19 39
-7 39
-13 36
-16 34
-25 25
-29 17
-30 14

result:

ok 51 numbers

Test #104:

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

input:

100000
47393 226720
46198 224964
45628 223776
44666 222475
43491 221608
45429 223924
46867 226254
48916 228743
47092 227140
46503 226964
45657 226288
45299 226950
47609 228485
46120 228198
45562 228105
46939 228638
47864 228957
48763 229051
49082 228907
51415 228607
52737 227791
51951 226714
52171 2...

output:

96592
-31997573 -331258
-31997572 -333574
-31997571 -335859
-31997570 -337951
-31997569 -339967
-31997568 -341981
-31997567 -343936
-31997563 -351586
-31997561 -354474
-31997560 -355893
-31997559 -357279
-31997558 -358564
-31997557 -359842
-31997549 -370063
-31997548 -371312
-31997539 -381278
-31997...

result:

ok 193185 numbers

Test #105:

score: 0
Accepted
time: 143ms
memory: 25844kb

input:

100000
36517 205322
36244 203790
36150 203114
36415 207464
37232 208061
37489 210247
36651 209728
35540 208660
35879 204304
35784 202603
35560 204851
35199 206268
34709 204514
32938 194927
34809 206251
34986 206797
35093 207576
34720 208344
34710 207143
34104 205001
34124 210363
34063 209402
33932 2...

output:

96804
-35704107 7398093
-35704106 7383522
-35704104 7365451
-35704103 7356627
-35704102 7348257
-35704097 7320463
-35704096 7314990
-35704094 7308240
-35704092 7303267
-35704091 7300784
-35704089 7295895
-35704087 7291366
-35704086 7289162
-35704081 7279186
-35704078 7273356
-35704069 7257571
-35704...

result:

ok 193609 numbers

Test #106:

score: 0
Accepted
time: 152ms
memory: 26656kb

input:

100000
299593 140653
299346 139986
299801 142290
299815 142113
299821 137311
299994 137246
299996 159863
299593 160016
299894 158785
299737 151131
299574 150499
299475 152281
299238 150919
299177 147885
299152 147995
298906 148213
299002 145286
298847 144150
299120 142051
299009 142250
299068 139728...

output:

96507
-27930195 -16056168
-27930193 -16068254
-27930191 -16080259
-27930190 -16085438
-27930189 -16089543
-27930188 -16092209
-27930187 -16094748
-27930185 -16099670
-27930184 -16101834
-27930180 -16109433
-27930179 -16111293
-27930176 -16116823
-27930173 -16121874
-27930172 -16123556
-27930171 -161...

result:

ok 193015 numbers

Test #107:

score: 0
Accepted
time: 127ms
memory: 26744kb

input:

100000
28927 223568
28314 225846
29820 222148
30380 219734
29189 220296
28804 220783
28236 218044
28227 217553
29366 216836
31099 217298
30989 216470
30083 216636
29398 216003
32229 212177
31889 213368
31989 216278
31336 217843
32463 216935
31774 219590
32458 219087
32565 218346
33073 216293
33394 2...

output:

96696
-30932586 10436509
-30932584 10409193
-30932583 10396480
-30932581 10389969
-30932576 10374768
-30932573 10365818
-30932572 10363529
-30932570 10358977
-30932566 10350205
-30932562 10341618
-30932546 10314239
-30932544 10310897
-30932538 10302867
-30932537 10301542
-30932536 10300271
-30932535...

result:

ok 193393 numbers

Test #108:

score: 0
Accepted
time: 144ms
memory: 26140kb

input:

100000
68001 177095
69139 177162
70005 177756
70056 179711
69243 178723
69243 180397
72223 181835
73930 182318
71216 182603
72893 183436
73385 184213
73210 184426
72290 184664
69417 185590
69768 185069
67586 185360
68002 185462
68608 185705
68233 185832
68661 185869
67976 186297
69636 185864
70592 1...

output:

96887
-36497966 15164076
-36497961 15154602
-36497959 15151610
-36497950 15138232
-36497949 15136771
-36497941 15126074
-36497932 15114193
-36497925 15105900
-36497923 15103797
-36497922 15102753
-36497921 15101721
-36497918 15098878
-36497914 15095254
-36497912 15093514
-36497895 15078777
-36497894...

result:

ok 193775 numbers

Test #109:

score: 0
Accepted
time: 141ms
memory: 26472kb

input:

100000
276258 136001
277857 135798
279046 134824
281572 133868
278845 135301
278896 135777
278704 136313
275053 136853
274276 137143
273045 137182
275341 137158
275050 137540
274729 137996
272359 138535
272346 138803
272830 138585
272563 144179
271826 142880
268815 143909
269713 144183
268996 144656...

output:

96605
-42897980 -3307317
-42897979 -3320205
-42897972 -3343122
-42897967 -3358503
-42897958 -3384551
-42897951 -3400322
-42897945 -3410132
-42897942 -3414573
-42897940 -3417403
-42897922 -3439481
-42897921 -3440660
-42897920 -3441821
-42897912 -3450674
-42897911 -3451742
-42897886 -3478224
-42897877...

result:

ok 193211 numbers

Test #110:

score: 0
Accepted
time: 148ms
memory: 25884kb

input:

100000
52346 167910
52680 169688
53398 166500
54159 162036
53959 163947
54767 159756
54856 160768
53628 166120
53105 168317
53582 167480
53753 168685
54597 164375
53778 170107
53409 168786
53097 170301
53246 173185
53090 174201
52990 175031
53147 172908
52757 171828
52581 177048
52303 178368
51711 1...

output:

96493
-31018089 -8382670
-31018088 -8387333
-31018087 -8390403
-31018086 -8392363
-31018085 -8394148
-31018084 -8395624
-31018082 -8398385
-31018079 -8402029
-31018075 -8406324
-31018074 -8407354
-31018071 -8410431
-31018065 -8416532
-31018061 -8420598
-31018060 -8421604
-31018059 -8422572
-31018058...

result:

ok 192987 numbers

Test #111:

score: 0
Accepted
time: 134ms
memory: 26444kb

input:

100000
10522 59526
10962 59546
11395 60138
11998 60126
11242 57902
12296 57676
12150 55302
12307 53491
12178 51717
10666 57540
11488 54446
11718 53948
11470 57450
11315 56044
10559 58000
10191 57695
11098 54255
11529 51073
11576 50317
11554 50378
10561 53519
9462 55657
11158 53208
10640 54223
7941 5...

output:

96692
-41668003 -5033141
-41668002 -5048833
-41667999 -5065887
-41667996 -5073564
-41667993 -5080935
-41667991 -5085380
-41667990 -5087124
-41667978 -5103303
-41667977 -5104627
-41667976 -5105649
-41667974 -5107686
-41667968 -5113669
-41667967 -5114456
-41667965 -5115990
-41667939 -5135725
-41667936...

result:

ok 193385 numbers

Test #112:

score: 0
Accepted
time: 139ms
memory: 26160kb

input:

100000
36329 152470
37352 152302
35959 153070
34660 153312
34727 154109
35058 154149
35099 154246
34948 154475
35036 155178
35546 155307
35332 155970
34716 157489
34601 154874
34014 154505
34542 154212
34615 152107
34626 151860
34135 152821
33255 152320
33369 151941
33169 152215
28702 156130
28575 1...

output:

96682
-40239012 -11813795
-40239011 -11815437
-40239010 -11816863
-40239008 -11819207
-40239007 -11820297
-40238999 -11828199
-40238995 -11832126
-40238990 -11836403
-40238989 -11837181
-40238982 -11842019
-40238980 -11843364
-40238978 -11844703
-40238976 -11845894
-40238973 -11847639
-40238972 -118...

result:

ok 193365 numbers

Test #113:

score: 0
Accepted
time: 123ms
memory: 26940kb

input:

100000
202867 44063
202760 43774
202116 42916
201375 43308
200927 42754
201114 40534
201991 40998
202912 42375
203631 42981
203697 43661
203666 45056
203667 43969
202934 45389
203093 46044
203074 45967
202422 47676
201765 47119
200889 47621
201563 46247
199364 47702
199131 47426
199960 48696
200046 ...

output:

96602
-24467144 9693483
-24467142 9679133
-24467120 9547568
-24467118 9537543
-24467114 9524501
-24467113 9521315
-24467112 9519054
-24467109 9512363
-24467101 9494971
-24467098 9488891
-24467097 9487010
-24467095 9483320
-24467094 9481520
-24467090 9474689
-24467089 9473144
-24467088 9471810
-24467...

result:

ok 193205 numbers