给定 $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$。

你需要找到一组 $c_i$ 使得 $|S|^2 \leq 1.2 \sum\limits_{i=1}^n (x_i^2 + y_i^2)$，即合力大小的平方不大于 $1.2$ 倍的向量模长平方和。

可以证明在本题的约束下始终有解。

数据规模：

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

所有向量的每一维分量都是绝对值不超过 $10^9$ 的整数。

输入

输入的第一行为一个正整数 $n$。 接下来 $n$ 行，每行两个整数表示一个二维向量。

输出

你需要输出一行 $n$ 个整数，表示你给向量赋予的方向。若方向为 $+1$，则输出 "1"；若方向为 $-1$，则输出 "-1"（均不含引号）。

样例输入

3
1 0
0 1
1 1

样例输出

1 1 -1