{"raw_statement":[{"iden":"statement","content":"For a vector $\\vec{v} = (x, y)$, define $|v| = \\sqrt{x^2 + y^2}$.\n\nAllen 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}$.\n\nAllen 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."},{"iden":"input","content":"The first line contains a single integer $n$ ($1 \\le n \\le 10^5$) — the number of moves.\n\nEach 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$."},{"iden":"output","content":"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$.\n\nIt can be shown that a solution always exists under the given constraints."},{"iden":"examples","content":"Input\n\n3\n999999 0\n0 999999\n999999 0\n\nOutput\n\n1 1 -1 \n\nInput\n\n1\n-824590 246031\n\nOutput\n\n1 \n\nInput\n\n8\n-67761 603277\n640586 -396671\n46147 -122580\n569609 -2112\n400 914208\n131792 309779\n-850150 -486293\n5272 721899\n\nOutput\n\n1 1 1 1 1 1 1 -1"}],"translated_statement":[{"iden":"statement","content":"对于向量 $\\vec{v} = (x, y)$，定义 $| \\vec{v} | = \\sqrt{x^2 + y^2}$。\n\n艾伦在酒吧喝得太多，而酒吧位于原点。现在有 $n$ 个向量 $\\vec{v_1}, \\vec{v_2}, \\dots, \\vec{v_n}$。艾伦将进行 $n$ 次移动。由于他的方向感受损，在第 $i$ 次移动中，他将沿着 $\\vec{v_i}$ 或 $-\\vec{v_i}$ 的方向移动。换句话说，如果他当前的位置是 $p = (x, y)$，他将移动到 $p + \\vec{v_i}$ 或 $p - \\vec{v_i}$。\n\n艾伦不希望离家（也就是酒吧）太远。你需要帮他找出一个移动序列（即每个向量的符号序列），使得他的最终位置 $p$ 满足 $| p | \\leq 1.5 \\times 10^6$，从而保证他的安全。\n\n第一行包含一个整数 $n$（$1 \\leq n \\leq 10^5$）——移动次数。\n\n接下来的每一行包含两个用空格分隔的整数 $x_i$ 和 $y_i$，表示 $\\vec{v_i} = (x_i, y_i)$。我们保证对所有 $i$ 都有 $| \\vec{v_i} | \\leq 10^6$。\n\n输出一行包含 $n$ 个整数 $c_1, c_2, \\dots, c_n$，每个整数为 $1$ 或 $-1$。你的解是正确的，当且仅当 $p = \\sum_{i=1}^n c_i \\vec{v_i}$ 满足 $| p | \\leq 1.5 \\times 10^6$。\n\n可以证明，在给定约束下，解总是存在的。"},{"iden":"input","content":"第一行包含一个整数 $n$（$1 \\leq n \\leq 10^5$）——移动次数。接下来的每一行包含两个用空格分隔的整数 $x_i$ 和 $y_i$，表示 $\\vec{v_i} = (x_i, y_i)$。我们保证对所有 $i$ 都有 $| \\vec{v_i} | \\leq 10^6$。"},{"iden":"output","content":"输出一行包含 $n$ 个整数 $c_1, c_2, \\dots, c_n$，每个整数为 $1$ 或 $-1$。你的解是正确的，当且仅当 $p = \\sum_{i=1}^n c_i \\vec{v_i}$ 满足 $| p | \\leq 1.5 \\times 10^6$。可以证明，在给定约束下，解总是存在的。"},{"iden":"examples","content":"输入\n3\n999999 0\n0 999999\n999999 0\n输出\n1 1 -1\n\n输入\n1\n-824590 246031\n输出\n1\n\n输入\n8\n-67761 603277\n640586 -396671\n46147 -122580\n569609 -211240\n0 914208\n131792 309779\n-850150 -486293\n5272 721899\n输出\n1 1 1 1 1 1 1 -1"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of vectors.  \nLet $ \\vec{v}_i = (x_i, y_i) \\in \\mathbb{R}^2 $ for $ i = 1, \\dots, n $, with $ \\|\\vec{v}_i\\| \\leq 10^6 $.  \nLet $ c_i \\in \\{-1, 1\\} $ be the sign chosen for vector $ \\vec{v}_i $.  \n\nDefine the final position:  \n$$\n\\vec{p} = \\sum_{i=1}^n c_i \\vec{v}_i\n$$\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ \\|\\vec{v}_i\\| \\leq 10^6 $ for all $ i \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nFind a sequence $ (c_1, c_2, \\dots, c_n) \\in \\{-1, 1\\}^n $ such that:  \n$$\n\\|\\vec{p}\\| \\leq 1.5 \\times 10^6\n$$","simple_statement":null,"has_page_source":false}