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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/**
 * @author Don Li
 */
public class LeavingTheBar {
    
    int N = (int) 2e5;
    int LIMIT = (int) 1e6;
    
    int sz = 0;
    int[] fr = new int[N], to = new int[N];
    int[][] G;
    int[] res = new int[N];
    
    void solve() {
        int n = in.nextInt();
        
        List<Vector> list = new ArrayList<>();
        for (int i = 0, nxt = n; i < n; i++) {
            list.add(new Vector(in.nextInt(), in.nextInt(), i));
            if (list.size() < 3) continue;
            L:
            for (int j = 0; j < 3; j++) {
                for (int k = j + 1; k < 3; k++) {
                    for (int sign = -1; sign <= 1; sign += 2) {
                        Vector a = list.get(j), b = list.get(k);
                        if (ok(a, b, sign)) {
                            Vector c = add(a, b, sign, nxt++);
                            res[a.id] = 1;
                            res[b.id] = sign;
                            list.remove(k);
                            list.remove(j);
                            list.add(c);
                            addEdge(c.id, a.id);
                            addEdge(c.id, b.id);
                            break L;
                        }
                    }
                }
            }
            assert list.size() < 3;
        }
        
        G = build_graph(2 * n - 1, fr, to);
        
        Vector u = list.get(0);
        res[u.id] = 1;
        if (list.size() > 1) {
            Vector v = list.get(1);
            Vector plus = add(u, v, 1, -1), minus = add(u, v, -1, -1);
            if (plus.dist() <= minus.dist()) {
                res[v.id] = 1;
            } else {
                res[v.id] = -1;
            }
        } 
        for (Vector v : list) dfs(v.id);
        
        for (int i = 0; i < n; i++) {
            if (i > 0) out.print(' ');
            out.print(res[i]);
        }
    }
    
    void dfs(int u) {
        for (int v : G[u]) {
            res[v] *= res[u];
            dfs(v);
        }
    }
    
    int[][] build_graph(int n, int[] from, int[] to) {
        int[][] G = new int[n][];
        int[] cnt = new int[n];
        for (int i = 0; i < sz; i++) {
            cnt[from[i]]++;
        }
        for (int i = 0; i < n; i++) G[i] = new int[cnt[i]];
        for (int i = 0; i < sz; i++) {
            G[from[i]][--cnt[from[i]]] = to[i];
        }
        return G;
    }
    
    void addEdge(int u, int v) {
        fr[sz] = u;
        to[sz++] = v;
    }
    
    Vector add(Vector a, Vector b, int sign, int id) {
        return new Vector(a.x + sign * b.x, a.y + sign * b.y, id);
    }
    
    boolean ok(Vector a, Vector b, int sign) {
        int x = a.x + sign * b.x;
        int y = a.y + sign * b.y;
        return (long) x * x + (long) y * y <= (long) LIMIT * LIMIT;
    }
    
    static class Vector {
        int x, y;
        int id;
        
        Vector(int x, int y, int id) {
            this.x = x;
            this.y = y;
            this.id = id;
        }
        
        long dist() {
            return (long) x * x + (long) y * y;
        }
    }
    
    public static void main(String[] args) {
        in = new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(System.out);
        new LeavingTheBar().solve();
        out.close();
    }
    
    static FastScanner in;
    static PrintWriter out;
    
    static class FastScanner {
        BufferedReader in;
        StringTokenizer st;
        
        public FastScanner(BufferedReader in) {
            this.in = in;
        }
        
        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        public int nextInt() {
            return Integer.parseInt(nextToken());
        }
        
        public long nextLong() {
            return Long.parseLong(nextToken());
        }
        
        public double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}