$n$ 個の二次元ベクトル $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$ が与えられます。

各ベクトルに対して方向 $c_i \in \{-1, +1\}$ を割り当てることができ、最終的に合力 $S = \sum\limits_{i=1}^n c_i (x_i, y_i)$ が得られます。

$S = (S_x, S_y)$ とし、合力の大きさの二乗を $|S|^2 = S_x^2 + S_y^2$ と定義します。

あなたは $|S|^2 \leq 1.2 \sum\limits_{i=1}^n (x_i^2 + y_i^2)$ を満たすような $c_i$ の組を見つける必要があります。すなわち、合力の大きさの二乗がベクトルの長さの二乗和の $1.2$ 倍以下となるようにします。

この問題の制約の下では、常に解が存在することが証明できます。

制約

$1 \leq n \leq 3 \times 10^5$

すべてのベクトルの各次元の成分は絶対値が $10^9$ を超えない整数である。

入力

入力の最初の行は正の整数 $n$ である。続く $n$ 行には、各二次元ベクトルを表す二つの整数が与えられる。

出力

あなたは $n$ 個の整数を一行で出力せよ。これらは各ベクトルに割り当てた方向を表す。方向が $+1$ の場合は "1" を、方向が $-1$ の場合は "-1" を出力せよ（引用符は含めない）。

入出力例

入力 1

3
1 0
0 1
1 1

出力 1

1 1 -1