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

见题面

见题面