Заданы $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" (без кавычек).

Примеры

Входные данные 1

3
1 0
0 1
1 1

Выходные данные 1

1 1 -1