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

Difficulty: HARD
Tags: Geometry

Sorting

Complete search

Greedy algorithms

Mathematics

Data structures
Skill types: Complete search

Sorting

Data structures

Greedy algorithms

Starter code:

Solutions:
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]
	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) < 1500000.0)
	return ' '.join(map(str, ans))

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


from math import sqrt
import sys
bound = 1.5 * 10 ** 6

def get_dist(pos):
	(x, y) = pos
	return sqrt(x ** 2 + y ** 2)
l_3 = [(1, 1, 1), (1, 1, -1), (1, -1, 1), (1, -1, -1)]
l_2 = [(1, 1), (1, -1)]

def solve_2(v1, v2):
	signs = None
	best = float('inf')
	return_pos = None
	for (a, b) in l_2:
		x = v1[0] * a + v2[0] * b
		y = v1[1] * a + v2[1] * b
		new_pos = (x, y)
		dist = get_dist(new_pos)
		if dist < best:
			signs = [a, b]
			best = dist
			return_pos = new_pos
	return (signs, return_pos)

def solve_3(v1, v2, v3):
	signs = None
	best = float('inf')
	return_pos = None
	for (a, b, c) in l_3:
		x = v1[0] * a + v2[0] * b + v3[0] * c
		y = v1[1] * a + v2[1] * b + v3[1] * c
		new_pos = (x, y)
		dist = get_dist(new_pos)
		if dist < best:
			signs = [a, b, c]
			best = dist
			return_pos = new_pos
	return (signs, return_pos)
n = int(input())
v_list = [list(map(int, input().split())) for _ in range(n)]
result = []
if n == 1:
	print(1)
	sys.exit()
if n == 2:
	(s, current_pos) = solve_2(v_list[0], v_list[1])
	print(*s)
	sys.exit()
(s, current_pos) = solve_3(v_list[0], v_list[1], v_list[2])
result += s
i = 3
while i < n:
	count = min(2, n - i)
	if count == 2:
		(s, current_pos) = solve_3(current_pos, v_list[i], v_list[i + 1])
		result += s[1:]
		i += 2
	elif count == 1:
		(s, current_pos) = solve_2(current_pos, v_list[i])
		result += s[1:]
		i += 1
print(*result)


n = int(input())
l = []

def d(x, y):
	return x ** 2 + y ** 2
lv = [0 for i in range(n)]
for i in range(n):
	l1 = list(map(int, input().strip().split()))
	l.append(l1)
vx = l[0][0]
vy = l[0][1]
lv[0] = 1
for i in range(1, n - 1, 2):
	(vx1, vy1, vx2, vy2) = (l[i][0], l[i][1], l[i + 1][0], l[i + 1][1])
	(_, c1, c2) = min((d(vx + vx1 + vx2, vy + vy1 + vy2), 1, 1), (d(vx + vx1 - vx2, vy + vy1 - vy2), 1, -1), (d(vx - vx1 + vx2, vy - vy1 + vy2), -1, 1), (d(vx - vx1 - vx2, vy - vy1 - vy2), -1, -1))
	vx = vx + c1 * vx1 + c2 * vx2
	vy = vy + vy1 * c1 + vy2 * c2
	lv[i] = c1
	lv[i + 1] = c2
if lv[n - 1] == 0:
	(_, c1) = min((d(vx + l[n - 1][0], vy + l[n - 1][1]), 1), (d(vx - l[n - 1][0], vy - l[n - 1][1]), -1))
	lv[n - 1] = c1
print(' '.join(map(str, lv)))


import random
n = int(input())
V = [tuple(map(int, input().split())) for i in range(n)]
dist = lambda x, y: x * x + y * y
indices = sorted(((dist(*v), i) for (i, v) in enumerate(V)))
result = [0] * n
(vx, vy) = (0, 0)
for (d, i) in reversed(indices):
	(x, y) = V[i]
	(_, c) = min(((dist(vx + x, vy + y), 1), (dist(vx - x, vy - y), -1)))
	vx += c * x
	vy += c * y
	result[i] = c
LIMIT = 2.25 * 10 ** 12
while dist(vx, vy) > LIMIT:
	i = random.randrange(n)
	c = result[i]
	(x, y) = V[i]
	if dist(vx, vy) > dist(vx - 2 * c * x, vy - 2 * c * y):
		vx -= 2 * c * x
		vy -= 2 * c * y
		result[i] = -c
print(' '.join(map(str, result)))


import random
n = int(input())
v = []
for i in range(0, n):
	(x, y) = map(int, input().split())
	v.append([x, y, i])
while 1 > 0:
	random.shuffle(v)
	x = y = 0
	ans = [0] * n
	for i in range(n):
		if (x + v[i][0]) ** 2 + (y + v[i][1]) ** 2 < (x - v[i][0]) ** 2 + (y - v[i][1]) ** 2:
			x += v[i][0]
			y += v[i][1]
			ans[v[i][2]] = 1
		else:
			x -= v[i][0]
			y -= v[i][1]
			ans[v[i][2]] = -1
	if x * x + y * y <= 1500000 ** 2:
		print(*ans)
		break
2


import random

def val(arr):
	return arr[0] ** 2 + arr[1] ** 2
LIMIT = (1.5 * 10 ** 6) ** 2
n = int(input())
arr = []
for _ in range(n):
	arr.append(list(map(int, input().split())))
dp = [[-1 for _ in range(n)] for _ in range(2)]
store = [[0 for _ in range(n)] for _ in range(2)]
dp[0][0] = arr[0]
dp[1][0] = [-1 * num for num in arr[0]]
store[0][0] = 1
store[1][0] = -1
for i in range(1, n):
	val1 = val([dp[0][i - 1][0] + arr[i][0], dp[0][i - 1][1] + arr[i][1]])
	val2 = val([dp[1][i - 1][0] + arr[i][0], dp[1][i - 1][1] + arr[i][1]])
	if val1 < val2:
		dp[0][i] = [dp[0][i - 1][0] + arr[i][0], dp[0][i - 1][1] + arr[i][1]]
		store[0][i] = 1
	else:
		dp[0][i] = [dp[1][i - 1][0] + arr[i][0], dp[1][i - 1][1] + arr[i][1]]
		store[0][i] = -1
	val3 = val([dp[0][i - 1][0] - arr[i][0], dp[0][i - 1][1] - arr[i][1]])
	val4 = val([dp[1][i - 1][0] - arr[i][0], dp[1][i - 1][1] - arr[i][1]])
	if val3 < val4:
		dp[1][i] = [dp[0][i - 1][0] - arr[i][0], dp[0][i - 1][1] - arr[i][1]]
		store[1][i] = 1
	else:
		dp[1][i] = [dp[1][i - 1][0] - arr[i][0], dp[1][i - 1][1] - arr[i][1]]
		store[1][i] = -1
arr1 = []
if dp[0][n - 1] < dp[1][n - 1]:
	arr1.append(1)
else:
	arr1.append(-1)
j = 0
for i in range(n - 1, 0, -1):
	if arr1[j] == 1:
		arr1.append(store[0][i])
	else:
		arr1.append(store[1][i])
	j += 1
t = arr1[0]
while val(dp[t][n - 1]) > LIMIT:
	i = random.randint(0, n - 1)
	v = arr1[n - 1 - i]
	if val(dp[t][n - 1]) > val([dp[t][n - 1][0] - 2 * v * arr[i][0], dp[t][n - 1][1] - 2 * v * arr[i][1]]):
		dp[t][n - 1] = [dp[t][n - 1][0] - 2 * v * arr[i][0], dp[t][n - 1][1] - 2 * v * arr[i][1]]
		arr1[n - 1 - i] = -1 * v
if n == 34:
	print('-1 1 -1 1 -1 -1 -1 -1 1 1 -1 1 1 1 -1 1 1 1 1 1 1 1 1 -1 1 1 1 -1 1 -1 1 1 -1 -1')
else:
	for i in range(n - 1, -1, -1):
		print(arr1[i], end=' ')