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.util.*;

public class Main implements Runnable {

    int maxn = (int)1e5+111;
    int n,m,k;
    Pair a[] = new Pair[maxn];

    void solve() throws Exception {
        n = in.nextInt();
        for (int i=1; i<=n; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            a[i] = new Pair(x,y,i);
        }

        Arrays.sort(a, 1, n+1);
        Pair p = new Pair(0,0,0);
        for (int i=1; i<=n; i++) {
//            out.println(dist(a[i]));
            long left = dist(new Pair(p.x + a[i].x, p.y + a[i].y, -1));
            long right = dist(new Pair(p.x - a[i].x, p.y - a[i].y, -1));
            if (left < right) {
                p.x = p.x + a[i].x;
                p.y = p.y + a[i].y;
                a[i].ans = 1;
            } else {
                p.x = p.x - a[i].x;
                p.y = p.y - a[i].y;
                a[i].ans = -1;
            }
        }
        int ans[] = new int[maxn];
        for (int i=1; i<=n; i++) {
            ans[a[i].ind] = a[i].ans;
        }


        for (int i=1; i<=n; i++) {
            out.print(ans[i] + " ");
        }
    }

    public long dist(Pair p) {
        return p.x*p.x + p.y*p.y;
    }

    class Pair implements Comparable<Pair> {
        long x;
        long y;
        int ind;
        int ans;

        public Pair(long x, long y, int ind) {
            this.x = x;
            this.y = y;
            this.ind = ind;
        }

        @Override
        public int compareTo(Pair p) {
            long left = Math.abs(this.x - this.y);
            long right = Math.abs(p.x - p.y);
            if (left<right) return 1;
            else if (left==right) return 0;
            else return -1;
        }

        @Override
        public String toString() {
            return "Pair{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }

    String fileInName = "";

    boolean file = false;
    boolean isAcmp = false;

    static Throwable throwable;
    public static void main (String [] args) throws Throwable {
        Thread thread = new Thread(null, new Main(), "", (1 << 26));
        thread.start();
        thread.join();
        thread.run();
        if (throwable != null)
            throw throwable;
    }

    FastReader in;
    PrintWriter out;

    public void run() {
        String fileIn = "absum.in";
        String fileOut = "absum.out";

        try {
            if (isAcmp) {
                if (file) {
                    in = new FastReader(new BufferedReader(new FileReader(fileIn)));
                    out = new PrintWriter (fileOut);
                } else {
                    in = new FastReader(new BufferedReader(new InputStreamReader(System.in)));
                    out = new PrintWriter(System.out);
                }
            } else if (file) {
                in = new FastReader(new BufferedReader(new FileReader(fileInName+".in")));
                out = new PrintWriter (fileInName + ".out");
            } else {
                in = new FastReader(new BufferedReader(new InputStreamReader(System.in)));
                out = new PrintWriter(System.out);
            }

            solve();
        } catch(Exception e) {
            throwable = e;
        } finally {
            out.close();
        }

    }


}

class FastReader {
    BufferedReader bf;
    StringTokenizer tk = null;

    public FastReader(BufferedReader bf) {
        this.bf = bf;
    }

    public String nextToken () throws Exception {
        if (tk==null || !tk.hasMoreTokens()) {
            tk = new StringTokenizer(bf.readLine());
        }
        if (!tk.hasMoreTokens()) return nextToken();
        else
            return tk.nextToken();
    }

    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}