Leaving the Bar

有一堆向量，你可以将一些取反，使后所有向量之和的长度小于$1.5\times 10^6$，保证有解。 ## Input 第一行一个正整数$n$表示向量个数。 接下来$n$行每行两个正整数$x, y$描述一个向量。 ## Output $n$个数，如果取反输出$-1$，否则输出$1$。 ``` 有一堆向量，你可以将一些取反，使后所有向量之和的长度小于$1.5\times 10^6$，保证有解。 ## Input 第一行一个正整数$n$表示向量个数。 接下来$n$行每行两个正整数$x, y$描述一个向量。 ## Output $n$个数，如果取反输出$-1$，否则输出$1$。 ```

For a vector $ \vec{v} = (x, y) $ , define $ |v| = \sqrt{x^2 + y^2} $ . Allen had a bit too much to drink at the bar, which is at the origin. There are $ n $ vectors $ \vec{v_1}, \vec{v_2}, \cdots, \vec{v_n} $ . Allen will make $ n $ moves. As Allen's sense of direction is impaired, during the $ i $ -th move he will either move in the direction $ \vec{v_i} $ or $ -\vec{v_i} $ . In other words, if his position is currently $ p = (x, y) $ , he will either move to $ p + \vec{v_i} $ or $ p - \vec{v_i} $ . Allen doesn't want to wander too far from home (which happens to also be the bar). You need to help him figure out a sequence of moves (a sequence of signs for the vectors) such that his final position $ p $ satisfies $ |p| \le 1.5 \cdot 10^6 $ so that he can stay safe.

The first line contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the number of moves. Each of the following lines contains two space-separated integers $ x_i $ and $ y_i $ , meaning that $ \vec{v_i} = (x_i, y_i) $ . We have that $ |v_i| \le 10^6 $ for all $ i $ .

Output a single line containing $ n $ integers $ c_1, c_2, \cdots, c_n $ , each of which is either $ 1 $ or $ -1 $ . Your solution is correct if the value of $ p = \sum_{i = 1}^n c_i \vec{v_i} $ , satisfies $ |p| \le 1.5 \cdot 10^6 $ . It can be shown that a solution always exists under the given constraints.

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