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:
//package com.company;

import java.io.*;
import java.util.*;

public class Main {
    static long TIME_START, TIME_END;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
//        Scanner sc = new Scanner(new FileInputStream("Test.in"));
        PrintWriter pw = new PrintWriter(System.out);
//        PrintWriter pw = new PrintWriter(new FileOutputStream("Test.out"));
//        PrintWriter pw = new PrintWriter(new FileOutputStream("Test.in"));

        Runtime runtime = Runtime.getRuntime();
        long usedMemoryBefore = runtime.totalMemory() - runtime.freeMemory();
        TIME_START = System.currentTimeMillis();
        Task.solve(sc, pw);
        TIME_END = System.currentTimeMillis();
        long usedMemoryAfter = runtime.totalMemory() - runtime.freeMemory();
        pw.close();
        System.out.println("Memory increased:" + (usedMemoryAfter-usedMemoryBefore) / 1000000 );
        System.out.println("Time used: " + (TIME_END - TIME_START) + ".");
    }

    public static class Task {
        public static int[][] findBest(int[][] list, int ex, int ey) {
            int n = list.length;
            int[] best = new int[n];
            int[] val = new int[2];
            long bestVal = Long.MAX_VALUE;
            for (int i = 0; i < 1 << n; i++) {
                int[] ret = new int[n];
                for (int j = 0; j < n; j++) {
                    ret[j] = (i & (1 << j)) == 0 ? -1 : 1;
                }
                int[] sum = new int[2];
                sum[0] = ex; sum[1] = ey;
                for (int j = 0; j < 2; j++) {
                    for (int k = 0; k < n; k++) {
                        sum[j] += list[k][j] * ret[k];
                    }
                }
                long v = (long) sum[0] * sum[0] + (long) sum[1] * sum[1];
                if (v < bestVal) {
                    bestVal = v;
                    best = Arrays.copyOf(ret, n);
                    val = Arrays.copyOf(sum, 2);
                }
            }
            return new int[][]{best, val};
        }

        public static void solve(Scanner sc, PrintWriter pw) throws IOException {
            int n = sc.nextInt();
            int[] x = new int[n];
            int[] y = new int[n];
            int[] res = new int[n];
            for (int i = 0; i < n; i++) {
                x[i] = sc.nextInt();
                y[i] = sc.nextInt();
            }
            while (true) {
                long timeEllap = System.currentTimeMillis() - TIME_START;
                if (timeEllap > 1900) break;
                int lookUpSize = 5;
                int curx = 0, cury = 0;
                for (int i = 0; i < n; i += lookUpSize) {
                    int[][] send = new int[lookUpSize][2];
                    for (int j = 0; j < Math.min(lookUpSize, n - i); j++) {
                        send[j][0] = x[j + i];
                        send[j][1] = y[j + i];
                    }
                    int[][] bt = findBest(send, curx, cury);
                    for (int j = 0; j < Math.min(lookUpSize, n - i); j++) {
                        res[i + j] = bt[0][j];
                    }
                    curx = bt[1][0];
                    cury = bt[1][1];
                }
                if ((long) curx * curx + (long) cury * cury <= 225_00000_00000L) {
                    break;
                }
            }
            for (int i = 0; i < n; i++) {
                pw.print(res[i] + " ");
            }

        }
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s){  br = new BufferedReader(new InputStreamReader(s));}

        public Scanner(FileReader s) throws FileNotFoundException {br = new BufferedReader(s);}

        public String next() throws IOException
        {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

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

        public long nextLong() throws IOException {return Long.parseLong(next());}

        public String nextLine() throws IOException {return br.readLine();}

        public double nextDouble() throws IOException { return Double.parseDouble(next()); }

        public boolean ready() throws IOException {return br.ready();}
    }
}