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.io.*;
import java.math.*;
public class Main1
{
    static class Reader 
    { 
        private InputStream mIs;private byte[] buf = new byte[1024];private int curChar,numChars;public Reader() { this(System.in); }public Reader(InputStream is) { mIs = is;} 
        public int read() {if (numChars == -1) throw new InputMismatchException();if (curChar >= numChars) {curChar = 0;try { numChars = mIs.read(buf);} catch (IOException e) { throw new InputMismatchException();}if (numChars <= 0) return -1; }return buf[curChar++];} 
        public 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() ;} 
        public String s(){int c = read();while (isSpaceChar(c)) c = read();StringBuilder res = new StringBuilder();do {res.appendCodePoint(c);c = read();}while (!isSpaceChar(c));return res.toString();} 
        public long l(){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;} 
        public int i(){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;} 
        public double d() throws IOException {return Double.parseDouble(s()) ;}
        public boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } 
        public boolean isEndOfLine(int c) { return c == '\n' || c == '\r' || c == -1; } 
        public int[] arr(int n){int[] ret = new int[n];for (int i = 0; i < n; i++) {ret[i] = i();}return ret;}
    }
    
    
    ///////////////////////////////////////////////////////////////////////////////////////////
    //    RRRRRRRRR            AAA             HHH     HHH     IIIIIIIIIIIII   LLL           //
    //    RR    RRR           AAAAA            HHH     HHH      IIIIIIIIIII    LLL           //
    //    RR   RRR           AAAAAAA           HHH     HHH          III        LLL           //
    //    RR  RRR           AAA   AAA          HHHHHHHHHHH          III        LLL           //
    //    RRRRRR           AAA     AAA         HHHHHHHHHHH          III        LLL           //
    //    RR  RRR         AAAAAAAAAAAAA        HHH     HHH          III        LLL           //
    //    RR    RRR      AAA         AAA       HHH     HHH      IIIIIIIIIII    LLLLLLLLLLLL  //
    //    RR     RRR    AAA           AAA      HHH     HHH     IIIIIIIIIIIII   LLLLLLLLLLLL  //
    ///////////////////////////////////////////////////////////////////////////////////////////
    
    static class B implements Comparable<B>
    {
        int x;int y;int index;
        public B(int a,int b,int c) 
        {
            x=a;
            y=b;
            index =c;
        }
        public int compareTo(B num) 
        {
            return (int)(Math.sqrt((long)num.x*num.x+(long)num.y*num.y)-Math.sqrt((long)x*x+(long)y*y));
        }
    }
    static PrintWriter out;
    static int n;
    static B arr[];
    static int store[];
    public static int rec(int x,int y,int pos)
    {
        if(Math.sqrt((long)x*x+(long)y*y)>1500000)
        return 0;
        if(pos==n)
        {
            for(int i=0;i<n;i++)
            out.print(store[i]+" "); 
            out.flush();
            System.exit(0);
        }
        int r=(int)(Math.random()*2);
        if(r==0)
        {
            x+=arr[pos].x;
            y+=arr[pos].y;
            store[arr[pos].index]=1;
            int val=rec(x,y,pos+1);
            if(val==0)
            {
                x-=2*arr[pos].x;
                y-=2*arr[pos].y;
                store[arr[pos].index]=-1;
                rec(x,y,pos+1);
            }
        }
        else
        {
            x-=arr[pos].x;
            y-=arr[pos].y;
            store[arr[pos].index]=-1;
            int val=rec(x,y,pos+1);
            if(val==0)
            {
                x+=2*arr[pos].x;
                y+=2*arr[pos].y;
                store[arr[pos].index]=1;
                rec(x,y,pos+1);
            }
        }
        return 0;
    }
    public static void main(String[] args)throws IOException
    {
        out= new PrintWriter(System.out);
        Reader sc=new Reader();
        n=sc.i();
        arr=new B[n];
        for(int i=0;i<n;i++)
        arr[i]=new B(sc.i(),sc.i(),i);
        long distance=0;
        int x=0;
        int y=0;
        store=new int[n];
        while(true)
        {
            rec(0,0,0);
            Collections.shuffle(Arrays.asList(arr));
        }
    }
}