C. Из бара домой
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для вектора $$$\vec{v} = (x, y)$$$, определим длину $$$|v| = \sqrt{x^2 + y^2}$$$.

Аллен немного перебрал в баре, который находится в начале координат. Существуют $$$n$$$ векторов $$$\vec{v_1}, \vec{v_2}, \cdots, \vec{v_n}$$$. Аллен сделает $$$n$$$ шагов. Так как Аллен дезориентирован, на $$$i$$$-м шаге он либо сделает шаг на вектор $$$\vec{v_i}$$$, либо на вектор $$$-\vec{v_i}$$$. Другими словами, если его позиция сейчас равна $$$p = (x, y)$$$, то он окажется либо в $$$p + \vec{v_i}$$$, либо в $$$p - \vec{v_i}$$$.

Аллен не хочет уйти далеко от дома (он также находится в баре). Помогите ему найти последовательность шагов (последовательность знаков векторов) такую, чтобы его финальная позиция $$$p$$$ удовлетворяла ограничению $$$|p| \le 1.5 \cdot 10^6$$$.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество шагов.

В каждой из следующих строк содержится два целых числа $$$x_i$$$ и $$$y_i$$$, описывающих вектор $$$\vec{v_i} = (x_i, y_i)$$$. Гарантируется, что $$$|v_i| \le 10^6$$$ выполняется для всех $$$i$$$.

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

Выведите единственною строку, содержащую $$$n$$$ целых чисел $$$c_1, c_2, \cdots, c_n$$$, каждое из которых равно либо $$$1$$$, либо $$$-1$$$. Ваше решение будет зачтено, если финальная позиция $$$p = \sum_{i = 1}^n c_i \vec{v_i}$$$ удовлетворяет $$$|p| \le 1.5 \cdot 10^6$$$.

Можно показать, что решение всегда существует при данных ограничениях.

Примеры
Входные данные
3
999999 0
0 999999
999999 0
Выходные данные
1 1 -1
Входные данные
1
-824590 246031
Выходные данные
1
Входные данные
8
-67761 603277
640586 -396671
46147 -122580
569609 -2112
400 914208
131792 309779
-850150 -486293
5272 721899
Выходные данные
1 1 1 1 1 1 1 -1