对于向量 $$$\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$$$。
可以证明,在给定的约束条件下,解总是存在。
示例
输入 #1
3 999999 0 0 999999 999999 0
输出 #1
1 1 -1
输入 #2
1 -824590 246031
输出 #2
1
输入 #3
8 -67761 603277 640586 -396671 46147 -122580 569609 -2112 400 914208 131792 309779 -850150 -486293 5272 721899
输出 #3
1 1 1 1 1 1 1 -1