CODE FESTIVAL 2016 Grand Final

I - 90 and 270


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 1500

問題文

以下の条件を満たす N 角形を一つ構成してください:

  • 多角形は単純である。 (ノートを見てください)
  • 多角形の各辺は座標軸に平行である。
  • 多角形の頂点の座標は 0 以上 10^9 以下の整数である。
  • 多角形の頂点は反時計回りに 1 から N まで番号がつけられている。
  • i 番目の頂点の内角は a_i 度である。

解が複数通り考えられる場合は、どれを出力してもかまいません。

ノート

全ての辺が正の長さを持ち、どの二つの辺も (隣接する辺が頂点で接するのを除いて) 共通部分を持たないとき、多角形は単純であるという。

制約

  • 3 ≤ N ≤ 1000
  • a_i90 または 270

入力

入力は以下の形式で標準入力から与えられる。

N
a_1
:
a_N

出力

解が存在する場合は、以下の形式で出力せよ:

x_1 y_1
:
x_N y_N

ここで (x_i, y_i)i 番目の頂点の座標である。

解が存在しない場合は、 -1 と出力せよ。


入力例 1

8
90
90
270
90
90
90
270
90

出力例 1

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

入力例 2

3
90
90
90

出力例 2

-1

Score : 1500 points

Problem Statement

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.

Notes

A polygon is called simple if each edge has a positive length, and no two edges have a common point (except for adjacent edges touching at a vertex).

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.


Sample Input 1

8
90
90
270
90
90
90
270
90

Sample Output 1

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

Sample Input 2

3
90
90
90

Sample Output 2

-1

Submit提出する