Soit $n$ vecteurs en deux dimensions $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$.

Vous pouvez assigner à chaque vecteur une direction $c_i \in \{-1, +1\}$, et obtenir la force résultante $S = \sum\limits_{i=1}^n c_i (x_i, y_i)$.

Soit $S = (S_x, S_y)$, on définit le carré de la norme de la force résultante par $|S|^2 = S_x^2 + S_y^2$.

Vous devez trouver un ensemble de $c_i$ tel que $|S|^2 \leq 1.2 \sum\limits_{i=1}^n (x_i^2 + y_i^2)$, c'est-à-dire que le carré de la norme de la force résultante n'est pas supérieur à $1,2$ fois la somme des carrés des normes des vecteurs.

On peut montrer qu'il existe toujours une solution sous les contraintes de ce problème.

Contraintes

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

Toutes les coordonnées des vecteurs sont des entiers dont la valeur absolue ne dépasse pas $10^9$.

Entrée

La première ligne de l'entrée contient un entier positif $n$.
Les $n$ lignes suivantes contiennent chacune deux entiers représentant un vecteur en deux dimensions.

Sortie

Vous devez afficher une ligne contenant $n$ entiers, indiquant la direction assignée à chaque vecteur. Si la direction est $+1$, affichez "1" ; si la direction est $-1$, affichez "-1" (sans les guillemets).

Exemples

Entrée 1

3
1 0
0 1
1 1

Sortie 1

1 1 -1