Description:
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.
Input Format:
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 Format:
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.
Note:
None