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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.Collection;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.io.BufferedReader;
import java.util.LinkedList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Hieu Le
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        private static final long R = 1000000;
        private static final long P = 1500000;
        private static final int COMPOSITE = -1;
        private static final int[] SIGNS = {1, -1};

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            Queue<TaskC.Node> nodes = new LinkedList<>();
            for (int i = 0; i < n; ++i)
                nodes.add(new TaskC.Node(i, in.nextInt(), in.nextInt()));

            Pair<Long, Long>[] vec = new Pair[n];
            int index = 0;
            for (TaskC.Node node : nodes)
                vec[index++] = new Pair<>(node.x, node.y);

            while (nodes.size() >= 3) {
                TaskC.Node a = nodes.poll();
                TaskC.Node b = nodes.poll();
                TaskC.Node c = nodes.poll();

                if (merge(a, b, R, nodes)) {
                    nodes.add(c);
                } else if (merge(a, c, R, nodes)) {
                    nodes.add(b);
                } else if (merge(b, c, R, nodes)) {
                    nodes.add(a);
                } else {
                    throw new RuntimeException();
                }
            }

            int[] signs = new int[n];
            if (nodes.size() == 2)
                merge(nodes.poll(), nodes.poll(), P, nodes);
            TaskC.Node root = nodes.peek();
            root.sign = 1;
            root.disperse(1, signs);

            long x = 0, y = 0;
            index = 0;
            for (int sign : signs) {
                x += vec[index].first * sign;
                y += vec[index].second * sign;
                ++index;
                out.print(sign + " ");
            }

            System.err.printf("%d %d\n", x, y);
            if (x * x + y * y > P * P)
                throw new RuntimeException();
        }

        private boolean merge(TaskC.Node a, TaskC.Node b, long limit, Queue<TaskC.Node> nodes) {
            for (int sa : SIGNS) {
                for (int sb : SIGNS) {
                    long x = a.x * sa + b.x * sb;
                    long y = a.y * sa + b.y * sb;
                    if (x * x + y * y <= limit * limit) {
                        a.sign = sa;
                        b.sign = sb;
                        TaskC.Node c = new TaskC.Node(COMPOSITE, x, y);
                        c.left = a;
                        c.right = b;
                        nodes.add(c);
                        return true;
                    }
                }
            }

            return false;
        }

        private static class Node {
            private int index;
            private int sign;
            private TaskC.Node left;
            private TaskC.Node right;
            private long x;
            private long y;

            private Node(int index, long x, long y) {
                this.index = index;
                this.x = x;
                this.y = y;
            }

            private void disperse(int soFar, int[] signs) {
                soFar *= sign;
                if (index == COMPOSITE) {
                    left.disperse(soFar, signs);
                    right.disperse(soFar, signs);
                } else {
                    signs[index] = soFar;
                }
            }

        }

    }

    static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;
        private static final int BUFFER_SIZE = 32768;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(
                    new InputStreamReader(stream), BUFFER_SIZE);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }

    static class Pair<U extends Comparable<U>, V extends Comparable<V>> implements Comparable<Pair<U, V>> {
        public U first;
        public V second;

        public Pair(U first, V second) {
            this.first = first;
            this.second = second;
        }

        public int hashCode() {
            return (first == null ? 0 : first.hashCode() * 31) + (second == null ? 0 : second.hashCode());
        }

        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Pair<U, V> p = (Pair<U, V>) o;
            return (first == null ? p.first == null : first.equals(p.first)) && (second == null ? p.second == null : second.equals(p.second));
        }

        public int compareTo(Pair<U, V> b) {
            int cmpU = first.compareTo(b.first);
            return cmpU != 0 ? cmpU : second.compareTo(b.second);
        }

    }
}