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;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

struct Point {
	int x, y;
	Point operator*(int a) const { return Point{ x * a, y * a }; }
	Point operator+(const Point &that) const { return Point{ x + that.x, y + that.y }; }
};

int main() {
	int N;
	mt19937 re;
	while(~scanf("%d", &N)) {
		vector<int> a(N);
		for(int i = 0; i < N; ++ i) {
			scanf("%d", &a[i]);
			if(a[i] == 270)
				a[i] = -90;
		}
		if(accumulate(a.begin(), a.end(), 0) != 360) {
			puts("-1");
			continue;
		}
		function<vector<Point>(vector<int>)> rec = [&rec](vector<int> a) -> vector<Point> {
			vector<Point> P;
			int N = (int)a.size();
			if(N == 4) {
				assert(count(a.begin(), a.end(), 90) == 4);
				P.push_back({ 0, 0 });
				P.push_back({ 1, 0 });
				P.push_back({ 1, 1 });
				P.push_back({ 0, 1 });
				return P;
			}
			int mid = -1;
			rep(i, N) if(a[i] == 90 && a[(i + 1) % a.size()] == -90) {
				mid = i == 0 ? N - 1 : i - 1;
				break;
			}
			assert(mid != -1);
			rotate(a.begin(), a.begin() + mid, a.end());
			assert(a[1] == 90 && a[2] == -90);
			vector<int> b = a;
			b.erase(b.begin() + 1, b.begin() + 3);
			vector<Point> Q = rec(b);
			while(!(Q[0].y == Q[1].y && Q[0].x < Q[1].x)) {
				for(auto &p : Q)
					swap(p.x, p.y), p.x *= -1;
			}
			P.push_back(Q[0] * 2);
			P.push_back(Q[0] * 2 + Point{ 1, 0 });
			P.push_back(Q[0] * 2 + Point{ 1, 1 });
			P.push_back(Q[1] * 2 + Point{ 0, 1 });
			reu(i, 2, Q.size())
				P.push_back(Q[i] * 2);
			vector<int> xs, ys;
			for(auto p : P) {
				xs.push_back(p.x);
				ys.push_back(p.y);
			}
			sort(xs.begin(), xs.end());
			xs.erase(unique(xs.begin(), xs.end()), xs.end());
			sort(ys.begin(), ys.end());
			ys.erase(unique(ys.begin(), ys.end()), ys.end());
			for(auto &p : P) {
				p.x = (int)(lower_bound(xs.begin(), xs.end(), p.x) - xs.begin());
				p.y = (int)(lower_bound(ys.begin(), ys.end(), p.y) - ys.begin());
			}
			rotate(P.rbegin(), P.rbegin() + mid, P.rend());
			return P;
		};
		vector<Point> P = rec(a);
		for(auto p : P)
			printf("%d %d\n", p.x, p.y);
	}
	return 0;
}