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 pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cout << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; }
template<class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

void compress(vector<pii>& vec) {
	vi xs, ys;
	for (auto &p : vec) {
		xs.pb(p.fi);
		ys.pb(p.se);
	}
	sort(ALL(xs));
	sort(ALL(ys));
	xs.erase(unique(ALL(xs)), xs.end());
	ys.erase(unique(ALL(ys)), ys.end());	
	rep(i, vec.size()) {
		int a = lower_bound(ALL(xs), vec[i].fi) - xs.begin();
		int b = lower_bound(ALL(ys), vec[i].se) - ys.begin();
		vec[i] = mp(a, b); 
	}
}

void rot(vector<pii>& vec) {
	rep(i, vec.size()) {
		int x = vec[i].fi, y = vec[i].se;
		vec[i] = mp(-y, x);
	}
}

vector<pii> gen(vi a) {
	int n = a.size();
	if (n == 4) {
		vector<pii> res = {mp(0, 0), mp(1, 0), mp(1, 1), mp(0, 1)};
		return res;
	} else {
		rep(i, n) {
			int j = (i + 1) % n;
			if (a[i] == 90 && a[j] == 270) {
				vi nx;

				rep(k, n) {
					if (k != i && k != j) {
						nx.pb(a[k]);
					}
				}

				auto _pl = gen(nx);
				for (auto &p : _pl) {
					p.fi *= 2;
					p.se *= 2;
				}

				int l = (i - 1 + n) % n;
				int r = (j + 1) % n;

				vector<pii> pl(n);
				{
					int now = 0;
					rep(k, n) {
						if (k != i && k != j) {
							pl[k] = _pl[now++];
						}
					}
					pl[i] = pl[j] = pl[l];
				}

				rep(t, 4) {
					if (pl[l].fi < pl[r].fi && pl[l].se == pl[r].se) {
						break;
					}
					rot(pl);
				}
				pl[i].fi++; 
				pl[j].fi++; pl[j].se++;
				pl[r].se++;

				compress(pl);
				return pl;
			}
		}
	}
}

int main() {
	int N; cin >> N;
	vi a(N);
	int s = 0;

	rep(i, N) {
		cin >> a[i];
		s += a[i];
	}

	if (s != 180 * (N-2)) {
		puts("-1");
		return 0;
	}

	auto pts = gen(a);
	for (auto p : pts) {
		cout << p.fi << " " << p.se << endl;
	}
	return 0;
}