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 PYTHON):

Solution:
from math import *
def merge(arr,temp, l, m, r):
    n1 = m - l + 1
    n2 = r- m
 
    # create temp arrays
    L1 = [-1000000,-1000000] *n1
    L2= [-1000000]*n1
    R1 = [-1000000,-1000000] *n2
    R2 = [-1000000] *n2
    # Copy data to temp arrays L[] and R[]
    for i in range(0 , n1):
        L1[i] = arr[l + i]
        L2[i] = temp[l + i]
    for j in range(0 , n2):
        R1[j] = arr[m + 1 + j]
        R2[j] = temp[m + 1 + j]
 
    # Merge the temp arrays back into arr[l..r]
    i = 0     # Initial index of first subarray
    j = 0     # Initial index of second subarray
    k = l     # Initial index of merged subarray
 
    while i < n1 and j < n2 :
        if abs(L1[i][0])+abs(L1[i][1]) <= abs(R1[j][0])+abs(R1[j][1]):
            arr[k] = L1[i]
            temp[k]= L2[i]
            i += 1
        else:
            arr[k] = R1[j]
            temp[k]= R2[j]
            j += 1
        k += 1
 
    # Copy the remaining elements of L[], if there
    # are any
    while i < n1:
        arr[k] = L1[i]
        temp[k] = L2[i]
        i += 1
        k += 1
 
    # Copy the remaining elements of R[], if there
    # are any
    while j < n2:
        arr[k] = R1[j]
        temp[k] = R2[j]
        j += 1
        k += 1
 
# l is for left index and r is right index of the
# sub-array of arr to be sorted
def mergeSort(arr,temp,l,r):
    if l < r:
 
        # Same as (l+r)/2, but avoids overflow for
        # large l and h
        m = (l+(r-1))//2
 
        # Sort first and second halves
        mergeSort(arr,temp, l, m)
        mergeSort(arr,temp, m+1, r)
        merge(arr,temp, l, m, r)
# Driver code to test above
n=int(raw_input())
temp=[]
for i in range(n):
    temp.append(i)
arr=[]
arrx=[0]*n
for i in range(n):
	x,y=map(int,raw_input().split())
	arr.append([x,y])
mergeSort(arr,temp,0,n-1)
dict1={}
for i in range(n):
	dict1[temp[i]]=i
#print(dict1)
x=0
y=0
i=n-1
while(i>=0):
	#print(dict1[i],dict1[j])
	#print(arr[dict1[i]])
	x1=x+arr[i][0]
	y1=y+arr[i][1]
	x2=x-arr[i][0]
	y2=y-arr[i][1]
	z1=pow(x1,2)+pow(y1,2)
	z2=pow(x2,2)+pow(y2,2)
	if(z1>z2):
		arrx[temp[i]]=-1
		x-=arr[i][0]
		y-=arr[i][1]
	else:
		arrx[temp[i]]=1
		x+=arr[i][0]
		y+=arr[i][1]
	#print(arrx)
	i-=1
#print(i,j)
#print(arrx)
print(" ".join(str(i) for i in arrx))