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.io.*;
import java.math.*;
import java.util.*;
import java.util.Map.Entry;


                    public class CODE2{
                    	private static InputStream stream;
                        private static byte[] buf = new byte[1024];
                        private static int curChar;
                        private static int numChars;
                        private static SpaceCharFilter filter;
                        private static PrintWriter pw;
                        static int BIT[];
                        public final static int INF = (int) 1E9;
                        static ArrayList<Integer> adj[];
                        static boolean Visited[];
                        static HashSet<Integer> exc;
                        static long oddsum[]=new long[1000001];
                        static long co=0,ans=0;
                        static int parent[];
                        static int size[],color[],res[],k;
                        static ArrayList<Integer> al[];
                        static long MOD = (long)1e9 + 7;
                        static int[] levl,dist;
                        static int[] eat;
                        static int nm = 1000007;
                        static boolean divisor[];
                        static int[] phi;
                        static int mod = (int)1e9 + 7;
                        static HashSet<Integer> div ;
                     static double maxvector = 1.5 * (1e6);
                        
                        public static void solve(){
                        	   
                        	int n = nextInt();
                        	Edge edge[] = new Edge[n];
                        	
                        	for(int i=0;i<n;i++)
                        		edge[i] = new Edge(nextLong(),nextLong(),i);
                        	
                        	long a = 0,b = 0;
                        	
                        	Arrays.sort(edge);
                        	int ans[] = new  int[n];
                        	for(Edge e : edge)
                        	{
                        		long temp1 = (a+e.x)*(a+e.x) +(b+e.y)*(b+e.y);
                        		long temp2 = (a-e.x)*(a-e.x) +(b-e.y)*(b-e.y);
                        		if(temp1>temp2)
                        		{
                        			ans[(int)e.i] = -1;
                        			a -= e.x;
                        			b -= e.y;
                        		}
                        		else
                        		{
                        			ans[(int)e.i] = 1;
                        			a += e.x;
                        			b += e.y;
                        		}
                        	}
                        	if(a*a + b*b <=Math.pow(1.5*1e6,2))
                        	{
                        		for(int i:ans)
                        			pw.print(i+" ");
                        		return;
                        	}
                        	a=0;b=0;
                        	Arrays.sort(edge,Collections.reverseOrder());
                        	for(Edge e : edge)
                        	{
                        		long temp1 = (a+e.x)*(a+e.x) +(b+e.y)*(b+e.y);
                        		long temp2 = (a-e.x)*(a-e.x) +(b-e.y)*(b-e.y);
                        		if(temp1>temp2)
                        		{
                        			ans[(int)e.i] = -1;
                        			a -= e.x;
                        			b -= e.y;
                        		}
                        		else
                        		{
                        			ans[(int)e.i] = 1;
                        			a += e.x;
                        			b += e.y;
                        		}
                        	}
                        	if(a*a + b*b <=Math.pow(1.5*1e6,2))
                        	{
                        		for(int i:ans)
                        			pw.print(i+" ");
                        		return;
                        	}
                        	
                        	
                        	
                        	
                        	
                        	
                        	
                    	}	
public static void main(String args[]) {
    InputReader(System.in);
    pw = new PrintWriter(System.out); 
    new Thread(null ,new Runnable(){
       public void run(){
           try{
               solve();
               
               pw.close();
           } catch(Exception e){
               e.printStackTrace();
           }
       }
   },"1",1<<26).start();
   }
    static StringBuilder sb;
    public static void test(){
         sb=new StringBuilder();
        int t=nextInt();
        while(t-->0){
            
            solve();
           
        }
        pw.println(sb);
    }
    public static long pow(long n, long p,long mod) {
        if(p==0)
            return 1;
        if(p==1)
            return n%mod;
        if(p%2==0){
            long temp=pow(n, p/2,mod);
        return (temp*temp)%mod;
        }else{
                 long temp=pow(n,p/2,mod);
                 temp=(temp*temp)%mod;
                 return(temp*n)%mod;
                 
        }
    }
    public static long pow(long n, long p) {
        if(p==0)
            return 1;
        if(p==1)
            return n;
        if(p%2==0){
            long temp=pow(n, p/2);
        return (temp*temp);
        }else{
                 long temp=pow(n,p/2);
                 temp=(temp*temp);
                 return(temp*n);
                 
        }
    }
    public static long gcd(long x, long y) {
        if (x == 0)
            return y;
        else
            return gcd( y % x,x);
    }    
    
    public static boolean isPrime(int n) {
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
 
        if (n % 2 == 0 || n % 3 == 0)
            return false;
 
        for (int i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
        return true;
    }
        
      private static void buildgraph(int n){
            adj=new ArrayList[n+1];
            Visited=new boolean[n+1];
            levl=new int[n+1];
            
            for(int i=0;i<=n;i++){
                adj[i]=new ArrayList<Integer>();
            
            }


        }
 
       
      
   static void sprime()
   {
	   spf=new int[nm+1];
	   for(int i=2;i<nm;i++)
	   {
		   if(spf[i]!=0)
			   continue;
		   for(int j=i;j<nm;j+=i)
		   {
			   spf[j] = i;
		   }
	   }
   }
   
   
   
    
        static void toposort(int i)
        {
        	Visited[i] = true;
        	
        	for(int j : adj[i])
        	{
        		if(!Visited[j])
        			toposort(j);
        	}
        	
        }
        static void comp(int n)
        {
        	for(int i=1;i<=Math.sqrt(n);i++)
        	{
        		if(n%i==0)
        		{
        			if(i==n/i)
        				div.add(i);
        			else
        			{
        				div.add(i);
        				div.add(n/i);
        			}
        		}
        	}
        }
        static void calculatephi()
        {
        	int end = (int)1e6 + 5;
        	for(int i=1;i<end;i++)
        		phi[i] = i;
        	for(int i=2;i<end;i++)
        	{
        		if(phi[i]==i)
        		{
        			phi[i] = i - 1;
        			for(int j=2 * i;j<end;j=j+i)
            		{
            			phi[j] = (phi[j]/i) * (i-1);
            		}
        		}
        		
        	}
        	
        }
        static void randomize( long  arr[], int n)
        {
            Random r = new Random();
            for (int i = n-1; i > 0; i--) {
                int j = r.nextInt(i);
                long  temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }                 
        static class pa implements Comparator<Integer>
    	{
    		

    		
    		public int compare(Integer a,Integer b)
    		{
    			return b-a;
    					
    		}
    	}
        static class node implements Comparable<node>
    	{
    		long r;long i;
    		
    		node(long r,long i)
    		{
    			this.r = r;
    			this.i = i; 
    		}
    		
    		public int compareTo(node other)
    		{
    			return Long.compare(this.r,other.r);
    					
    		}
    	}
       
        
     /*   static void BITupdate(int x,int val)
        {
        	while(x<=n)
        	{
        		BIT[x]+=val;
        		x+= x & -x;
        	}
        }*/
     /*   static void update(int x,long val)
        {
      
        	val=val%MOD;
        	while(x<=n)
        	{
        		// System.out.println(x);
        	BIT[x]=(BIT[x]+val)%MOD;
        	x+=(x & -x);
        	}
        //	System.out.println("dfd");
        }*/
        static int BITsum(int x)
        		{
        	int sum=0;
        	while(x>0)
        	{
        		sum+=BIT[x];
        		x-= (x & -x);
        	}
        		return sum;
        		}
  /*      static long sum(int x)
        {
        	long sum=0;
        	while(x>0)
        	{
        		sum=(sum+BIT[x])%MOD;
        		x-=x & -x;
        	}
        	return sum;
        }*/
        static boolean union(int x,int y)
        {
        	int xr=find(x);
        	int yr=find(y);
        	if(xr==yr)
        		return false;
        	if(size[xr]<size[yr])
        	{
        		size[yr]+=size[xr];
        		parent[xr]=yr;
        	}
        	else
        	{
        		size[xr]+=size[yr];
        		parent[yr]=xr;
        		
        	}
        	return true;
        	
        }
        static int  find(int x)
        {
        	if(parent[x]==x)
        		return x;
        	else
        	{
        		parent[x]=find(parent[x]);
        		return parent[x];
        	}
        	
        }
        public static class Edge implements Comparable<Edge>
        {
        	long x, y,i;
			public Edge(long x,long y,int i) 
			{
				this.x = x;
				this.y = y;
				this.i = i;
				//this.s = s;
			}
			public int hashCode() 
			{
				return Objects.hash();
			}
			public int compareTo(Edge other) 
			{
				return Long.compare(x*x + y*y,other.x*other.x + other.y*other.y);
				
			}
			
        }
       
        static int col[];
   
static int no_vert=0;

    public static String reverseString(String s) {
        StringBuilder sb = new StringBuilder(s);
        sb.reverse();
        return (sb.toString());
    }
    
  



                  static int indeg[];
               /* private static void kahn(int n){
                    
                    PriorityQueue<Integer> q=new PriorityQueue<Integer>();
                    for(int i=1;i<=n;i++){
                        if(indeg[i]==0){
                            q.add(i);
                        }
                    }
                    while(!q.isEmpty()){
                        int top=q.poll();
                        st.push(top);
                        for(Node i:adj[top]){
                            indeg[i.to]--;
                            if(indeg[i.to]==0){
                                q.add(i.to);
                            }
                        }
                    }
                }
                    
                    static int state=1;
                    static long no_exc=0,no_vert=0;
                  static Stack<Integer> st;
                  static HashSet<Integer> inset;
                   private static void topo(int curr){
                        
                        Visited[curr]=true;
                        inset.add(curr);
                        for(int x:adj[curr]){
                            if(adj[x].contains(curr) || inset.contains(x)){
                                state=0;
                                return;
                            }
                            if(state==0)
                                return;
                            
                        }
                        st.push(curr);
                        
                        inset.remove(curr);
                    }*/
                    static HashSet<Integer> hs;
                   
                 
                     static boolean prime[];
                    static int spf[];
                    public static void sieve(int n){
                        prime=new boolean[n+1];
                        spf=new int[n+1];
                        
                        Arrays.fill(spf, 1);
                        Arrays.fill(prime, true);
                    prime[1]=false;
                        spf[2]=2;
                        
                    
                    for(int i=2;i*i<=n;i++){
                        if(prime[i]){
                            spf[i]=i;
                            for(int j=2*i;j<=n;j+=i){
                                
                                prime[j]=false;
                           
                            }
                        }
                    }
                    
                        
                    }
                     
                    // To Get Input
// Some Buffer Methods
 
                    
                    public static void InputReader(InputStream stream1) {
                        stream = stream1;
                    }
 
                    private static boolean isWhitespace(int c) {
                        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
                    }
 
                    private static boolean isEndOfLine(int c) {
                        return c == '\n' || c == '\r' || c == -1;
                    }
 
                    private static int read() {
                        if (numChars == -1)
                            throw new InputMismatchException();
                        if (curChar >= numChars) {
                            curChar = 0;
                            try {
                                numChars = stream.read(buf);
                            } catch (IOException e) {
                                throw new InputMismatchException();
                            }
                            if (numChars <= 0)
                                return -1;
                        }
                        return buf[curChar++];
                    }
 
                    private static int nextInt() {
                        int c = read();
                        while (isSpaceChar(c))
                            c = read();
                        int sgn = 1;
                        if (c == '-') {
        sgn = -1;
        c = read();
    }
    int res = 0;
    do {
        if (c < '0' || c > '9')
            throw new InputMismatchException();
        res *= 10;
        res += c - '0';
                            c = read();
                        } while (!isSpaceChar(c));
                        return res * sgn;
                    }
 
                    private static long nextLong() {
                        int c = read();
                        while (isSpaceChar(c))
                            c = read();
                        int sgn = 1;
                        if (c == '-') {
        sgn = -1;
        c = read();
    }
    long res = 0;
    do {
        if (c < '0' || c > '9')
            throw new InputMismatchException();
        res *= 10;
        res += c - '0';
                            c = read();
                        } while (!isSpaceChar(c));
                        return res * sgn;
                    }
 
                    private static String nextToken() {
                        int c = read();
                        while (isSpaceChar(c))
                            c = read();
                        StringBuilder res = new StringBuilder();
                        do {
                            res.appendCodePoint(c);
                            c = read();
                        } while (!isSpaceChar(c));
                        return res.toString();
                    }
 
                    private static String nextLine() {
                        int c = read();
                        while (isSpaceChar(c))
                            c = read();
                        StringBuilder res = new StringBuilder();
                        do {
                            res.appendCodePoint(c);
                            c = read();
                        } while (!isEndOfLine(c));
                        return res.toString();
                    }
 
                    private static int[] nextIntArray(int n) {
                        int[] arr = new int[n];
                        for (int i = 0; i < n; i++) {
                            arr[i] = nextInt();
                        }
                        return arr;
                    }
 
                    private static long[][] next2dArray(int n, int m) {
                        long[][] arr = new long[n][m];
                        for (int i = 0; i < n; i++) {
                            for (int j = 0; j < m; j++) {
                                arr[i][j] = nextLong();
                            }
                        }
                        return arr;
                    }
                    private static char[][] nextCharArray(int n,int m){
                        char [][]c=new char[n][m];
                        for(int i=0;i<n;i++){
                            String s=nextLine();
                            for(int j=0;j<s.length();j++){
                                c[i][j]=s.charAt(j);
                            }
                        }
                        return c;
                    }
 
                    private static long[] nextLongArray(int n) {
                        long[] arr = new long[n];
                        for (int i = 0; i < n; i++) {
                            arr[i] = nextLong();
                        }
                        return arr;
                    }
 
                    private static void pArray(int[] arr) {
                        for (int i = 0; i < arr.length; i++) {
                            pw.print(arr[i] + " ");
                        }
                        pw.println();
                        return;
                    }
 
                    private static void pArray(long[] arr) {
                        for (int i = 0; i < arr.length; i++) {
                            pw.print(arr[i] + " ");
                        }
                        pw.println();
                        return;
                    }
 
                    private static void pArray(boolean[] arr) {
                        for (int i = 0; i < arr.length; i++) {
                            pw.print(arr[i] + " ");
                        }
                        pw.println();
                        return;
                    }
 
                    private static boolean isSpaceChar(int c) {
                        if (filter != null)
                            return filter.isSpaceChar(c);
                        return isWhitespace(c);
                    }
 
                    private interface SpaceCharFilter {
                        public boolean isSpaceChar(int ch);
                    }
                    

}