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-----

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-----

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.


-----Examples-----
Input
3
999999 0
0 999999
999999 0

Output
1 1 -1 

Input
1
-824590 246031

Output
1 

Input
8
-67761 603277
640586 -396671
46147 -122580
569609 -2112
400 914208
131792 309779
-850150 -486293
5272 721899

Output
1 1 1 1 1 1 1 -1

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import random\n\nn = int(input())\nv = []\na = []\nfor i in range(n):\n    a.append(i)\n\nfor _ in range(0, n):\n    x, y = list(map(int, input().split()))\n    v.append([x, y, x*x+y*y])\n\nwhile 1>0:\n    x = 0\n    y = 0\n    ans = [0]*n\n    random.shuffle(a)\n    for i in range(n):\n        if (x+v[a[i]][0])**2+(y+v[a[i]][1])**2 <= (x-v[a[i]][0])**2+(y-v[a[i]][1])**2:\n            x += v[a[i]][0]\n            y += v[a[i]][1]\n            ans[a[i]] = 1\n        else:\n            x -= v[a[i]][0]\n            y -= v[a[i]][1]\n            ans[a[i]] = -1\n    if x*x+y*y <= 1500000**2:\n        print(*ans)\n        break\n\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13661