Problem: Construct an N-gon that satisfies the following conditions:

* The polygon is simple (see notes for the definition).
* Each edge of the polygon is parallel to one of the coordinate axes.
* Each coordinate is an integer between 0 and 10^9, inclusive.
* The vertices are numbered 1 through N in counter-clockwise order.
* The internal angle at the i-th vertex is exactly a_i degrees.



In case there are multiple possible answers, you can output any.

Constraints

* 3 ≤ N ≤ 1000
* a_i is either 90 or 270.

Input

The input is given from Standard Input in the following format:


N
a_1
:
a_N


Output

In case the answer exists, print the answer in the following format:


x_1 y_1
:
x_N y_N


Here (x_i, y_i) are the coordinates of the i-th vertex.

In case the answer doesn't exist, print a single `-1`.

Examples

Input

8
90
90
270
90
90
90
270
90


Output

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


Input

3
90
90
90


Output

-1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
vector<int> A;

vector<pair<int,int>> hoge(vector<int> A) {
	if(A.size()==4) {
		return {{0,0},{1,0},{1,1},{0,1}};
	}
	int i,N=A.size(),j;
	
	FOR(i,N) {
		if(A[i]==1 && A[(i+1)%N]==0) break;
	}
	vector<int> B;
	B.push_back(A[(i+N-1)%N]);
	FOR(j,N-3) B.push_back(A[(i+2+j)%N]);
	vector<pair<int,int>> P=hoge(B),R;
	while(P[0].first>=P[1].first) {
		FORR(p,P) {
			swap(p.first,p.second);
			p.first=-p.first;
		}
	}
	
	FORR(p,P) p.first*=2,p.second*=2;
	P.insert(P.begin()+1,{P[0].first+1,P[0].second});
	P.insert(P.begin()+2,{P[0].first+1,P[0].second+1});
	P[3].second++;
	vector<int> Xs,Ys;
	FORR(p,P) {
		Xs.push_back(p.first);
		Ys.push_back(p.second);
	}
	sort(ALL(Xs));
	sort(ALL(Ys));
	Xs.erase(unique(ALL(Xs)),Xs.end());
	Ys.erase(unique(ALL(Ys)),Ys.end());
	
	
	FOR(j,N) {
		int x=lower_bound(ALL(Xs),P[(j-(i-1)+N)%N].first)-Xs.begin();
		int y=lower_bound(ALL(Ys),P[(j-(i-1)+N)%N].second)-Ys.begin();
		R.push_back({x,y});
	}
	
	return R;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int rot=0;
	FOR(i,N) {
		cin>>x;
		A.push_back(x==90);
		if(A[i]==1) rot++;
		else rot--;
	}
	if(rot!=4) return _P("-1\n");
	
	auto ret=hoge(A);
	FORR(r,ret) cout<<r.first<<" "<<r.second<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}