996_E. Leaving the Bar
For a vector \vec{v} = (x, y), define |v| = √{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}, ⋅⋅⋅, \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| ≤ 1.5 ⋅ 10^6 so that he can stay safe.

Input

The first line contains a single integer n (1 ≤ n ≤ 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| ≤ 10^6 for all i.

Output

Output a single line containing n integers c_1, c_2, ⋅⋅⋅, c_n, each of which is either 1 or -1. Your solution is correct if the value of p = ∑_{i = 1}^n c_i \vec{v_i}, satisfies |p| ≤ 1.5 ⋅ 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
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

def D(V, S):
    x = 0
    y = 0
    for s, v in zip(S, V):
        x += s*v[0]
        y += s*v[1]
    # error_print(math.sqrt(x**2+y**2))
    return math.sqrt(x**2+y**2)

def XY(V, S):
    x = 0
    y = 0
    for s, v in zip(S, V):
        x += s*v[0]
        y += s*v[1]
    return x, y
@mt
def slv(N, V):
    V1 = [[*v, i, 1] for i, v in enumerate(V) if v[0] * v[1] > 0]
    V2 = [[*v, i, 1] for i, v in enumerate(V) if v[0] * v[1] < 0]
    V3 = [[*v, i, 1] for i, v in enumerate(V) if v[0] == 0]
    V4 = [[*v, i, 1] for i, v in enumerate(V) if v[0] != 0 and v[1] == 0]

    V1.sort(reverse=True, key=lambda x: abs(x[0]) + abs(x[1]))
    V2.sort(reverse=True, key=lambda x: abs(x[0]) + abs(x[1]))
    V3.sort(reverse=True, key=lambda x: abs(x[0]) + abs(x[1]))
    V4.sort(reverse=True, key=lambda x: abs(x[0]) + abs(x[1]))

    def f(V):
        sx, sy = 0, 0
        for i, v in enumerate(V):
            if abs(sx + v[0]) + abs(sy + v[1]) < abs(sx - v[0]) + abs(sy - v[1]):
                v[3] = 1
            else:
                v[3] = -1
            sx += v[3]*v[0]
            sy += v[3]*v[1]
        return sx, sy
    
    SV = [f(V_) for V_ in [V1, V2, V3, V4]]
    
    S = min([(D(SV, s), s) for s in product([-1, 1], repeat=4)])
    for s, V_ in zip(S[1], [V1, V2, V3, V4]):
        for v in V_:
            v[3] *= s



    V1.extend(V2)
    V1.extend(V3)
    V1.extend(V4)
    V1.sort(key=lambda x: x[2])
    ans = [v[3] for v in V1]

    error_print(D(V, ans) < 1.5e+6)

    return ' '.join(map(str, ans))


def main():
    N = read_int()
    V = [read_int_n() for _ in range(N)]
    print(slv(N, V))


if __name__ == '__main__':
    main()

```