CF995C Leaving the Bar

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.