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

Solution:
import java.util.*;
import java.lang.*;
public class C995
{
	public static void main(String[] args) 
	{
		/*class Obj implements Comparable<Obj>
		{
			int x;
			int y;
			int dir=1;
			public Obj(int x,int y)
			{
				this.x=x;
				this.y=y;
			}
			public int compareTo(Obj o)
			{
				if(Math.sqrt(x*x+y*y)<Math.sqrt((o.x*o.x)+(o.y*o.y)))
					return -1;
				else
					return 1;


			}

		}
		
		ArrayList<Obj> l=new ArrayList<>();
		HashMap<Integer,Obj> map=new HashMap<>();
		double dist=0;
		int xx,yy;
		long posx=0;
		long posy=0;
		for(int i=0;i<n;i++)
		{
			xx=s.nextInt();
			yy=s.nextInt();
			posx+=xx;
			posy+=yy;
			Obj qq=new Obj(xx,yy);
			map.put(i,qq);
			l.add(qq);
			dist=Math.sqrt((posx)*(posx)+((posy)*(posy)));
		}
		if(dist>1500000)
		{
			Collections.sort(l);
			for(int i=n-1;i>0;i--)
			{
				l.get(i).dir=-1;
				dist=Math.sqrt((dist*dist)-2*( ( (l.get(i).x)*(l.get(i).x))+((l.get(i).y)*(l.get(i).y)  )    )  );
				if(dist<=1500000)
					break;
			}
			if(dist>1500000)
			{
				System.out.println("ye kya ho gaya");
				System.exit(0);
			}

		}
		StringBuilder sb=new StringBuilder();
		for(int i=0;i<n;i++)
		{
			sb=sb.append(l.get(i).dir).append(" ");
		}
		System.out.println(sb);*/

















		Scanner s=new Scanner(System.in);
		int n=s.nextInt();
		StringBuilder sb2=new StringBuilder();
		StringBuilder sb=new StringBuilder();
		int x,y;
		int posx,posy;
		posx=s.nextInt();
		posy=s.nextInt();
		sb=sb.append(1).append(" ");
		sb2=sb2.append(-1).append(" ");
		int[] ans=new int[n];
		
		int[] aa;
		int[] ans2=new int[n];
		ans[0]=1;
		ans2[0]=-1;
		double dist=Math.sqrt(Math.pow(posx,2)+Math.pow(posy,2));
		double ddist=dist;
		double dist1,dist2,ddist1,ddist2;
		int pposx=-posx;
		int pposy=-posy;
		int temp1,temp2;
		double c1=dist,c2=dist;
		int [] xcord=new int[n];
		int[] ycord=new int[n];
		for(int i=1;i<n;i++)
		{
			temp1=s.nextInt();
			xcord[i]=temp1;
			temp2=s.nextInt();
			ycord[i]=temp2;
			dist1=Math.sqrt(Math.pow((posx+temp1),2)+Math.pow((posy+temp2),2));
			ddist1=Math.sqrt(Math.pow((pposx+temp1),2)+Math.pow((pposy+temp2),2));
			dist2=Math.sqrt(Math.pow((posx-temp1),2)+Math.pow((posy-temp2),2));
			ddist2=Math.sqrt(Math.pow((pposx-temp1),2)+Math.pow((pposy-temp2),2));
			if(dist1<=dist2)
			{
				posx+=temp1;
				posy+=temp2;
				sb=sb.append(1).append(" ");
				c1=dist1;
				ans[i]=1;
			}
			else
			{
				posx-=temp1;
				posy-=temp2;
				sb=sb.append(-1).append(" ");
				c1=dist2;
				ans[i]=-1;
			}
			if(ddist1<=ddist2)
			{
				pposx+=temp1;
				pposy+=temp2;
				sb2=sb2.append(1).append(" ");
				c2=ddist1;
				ans2[i]=1;
			}
			else
			{
				pposx-=temp1;
				pposy-=temp2;
				sb2=sb2.append(-1).append(" ");
				c2=ddist2;
				ans2[i]=-1;
			}

		}	
		double c;
		int fpx,fpy;
		if(c1<=c2)
		{
			c=c1;
			aa=ans;
			fpx=posx;
			fpy=posy;
		}
		else
		{
			fpx=pposx;
			fpy=pposy;
			c=c2;
			aa=ans2;

		}
		double tempdist;
		int i=0;
		int tempposx=fpx;
		int tempposy=fpy;
		while(c>1500000)
		{
			tempposx-=2*xcord[i]*aa[i];
			tempposy-=2*ycord[i]*aa[i];
			tempdist=Math.sqrt( tempposy*tempposy + tempposx*tempposx  );	
			if(tempdist<c)
			{
				c=tempdist;
				aa[i]=aa[i]*-1;
			}	
			i++;
			if(c<=1500000)
			{
				break;

			}
		}
		for ( i = 0; i < n; i++) {
               System.out.print(aa[i]+" ");
           }
			
			//aa=ans2;
			//System.out.println(sb2);

	}
}