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

Solution (in PYTHON3):

Solution:
import random

n = int(input())

vec = [list(map(int, input().rstrip('\n').split(' '))) for i in range(n)]

bo = 10**6

coef = [[1, 1, 0], [1, -1, 0], [-1, 1, 0], [-1, -1, 0],
[1, 0, 1], [1, 0, -1], [-1, 0, 1], [-1, 0, -1],
[0, 1, 1], [0, 1, -1], [0, -1, 1], [0, -1, -1]]

def lv(x):
	return (x[0]**2 + x[1]**2)**0.5

if n == 1:
	res = [1]
elif n == 2:
	if vec[0][0]*vec[1][0] + vec[0][1]*vec[1][1] <= 0:
		res = [1, 1]
	else:
		res = [1, -1]
else:
	res = [0 for i in range(n)]
	fer = [[vec[0], vec[1], vec[2]],[[0], [1], [2]]]
	for l in range(len(vec)-2):
		for j in coef:
			der = [0, 0]
			der[0] = j[0]*fer[0][0][0] + j[1]*fer[0][1][0] + j[2]*fer[0][2][0]
			der[1] = j[0]*fer[0][0][1] + j[1]*fer[0][1][1] + j[2]*fer[0][2][1]
			if lv(der) <= bo:
				ner = []
				for i in range(3):
					if j[i] != 0:
						ner.append(i)
				if len(fer[1][ner[0]]) == 1:
					res[fer[1][ner[0]][0]] = j[ner[0]]
				elif j[ner[0]] == -1:
					for k in fer[1][ner[0]]:
						res[k] *= -1
				fer[0][ner[0]] = der
				fer[1][ner[0]] += fer[1][ner[1]]
				if len(fer[1][ner[1]]) == 1:
					res[fer[1][ner[1]][0]] = j[ner[1]]
				elif j[ner[1]] == -1:
					for k in fer[1][ner[1]]:
						res[k] *= -1
				if l == len(vec)-3:
					del fer[0][ner[1]]
					del fer[1][ner[1]]
				else:
					fer[0][ner[1]] = vec[3+l]
					fer[1][ner[1]] = [3+l]
				break
	if fer[0][0][0]*fer[0][1][0] + fer[0][0][1]*fer[0][1][1] <= 0:
		if len(fer[1][0]) == 1:
			res[fer[1][0][0]] = 1
		if len(fer[1][1]) == 1:
			res[fer[1][1][0]] = 1
	else:
		if len(fer[1][0]) == 1:
			res[fer[1][0][0]] = -1
		elif len(fer[1][1]) == 1:
			res[fer[1][1][0]] = -1
		else:
			for k in fer[1][0]:
				res[k] *= -1
res1 = ''
for i in res:
	res1 += str(i)+' '
res1 = res1[:-1]
print(res1)