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
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)
	# print(i)
	v = arr1[n-1-i]
	# print(v)
	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 = " ")