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.awt.*;
import java.awt.event.*;
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;

public class C {
	static BufferedReader br;
	static StringTokenizer st;
	static PrintWriter pw;

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		//int qq = 1;
		int qq = Integer.MAX_VALUE;
		//int qq = readInt();
		for(int casenum = 1; casenum <= qq; casenum++) {
			int n = readInt();
			ArrayList<State> l = new ArrayList<>();
			for(int i = 0; i < n; i++) {
				l.add(new State(readLong(), readLong(), i));
			}
			while(true) {
				Collections.shuffle(l);
				long x = 0;
				long y = 0;
				int[] ret = new int[n];
				for(State out: l) {
					long xInc = x + out.x;
					long yInc = y + out.y;
					long xDec = x - out.x;
					long yDec = y - out.y;
					if(xInc*xInc+yInc*yInc > xDec*xDec+yDec*yDec) {
						x = xDec;
						y = yDec;
						ret[out.i] = -1;
					}
					else {
						x = xInc;
						y = yInc;
						ret[out.i] = 1;
					}
				}
				if(x*x+y*y >= 1500000L*1500000) continue;
				for(int i = 0; i < n; i++) {
					pw.print(ret[i]);
					if(i == n-1) pw.println();
					else pw.print(" ");
				}
				break;
			}
		}
		pw.close();
	}

	static class State implements Comparable<State> {
		public long x, y;
		public int i;
		public State(long x, long y, int i) {
			super();
			this.x = x;
			this.y = y;
			this.i = i;
		}
		public long mag() {
			return x*x+y*y;
		}
		public int compareTo(State s) {
			return Long.compare(s.mag(), mag());
		}
	}

	public static void exitImmediately() {
		pw.close();
		System.exit(0);
	}

	public static int readInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	public static double readDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	public static long readLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	public static String nextLine() throws IOException {
		st = null;
		if(!br.ready()) {
			exitImmediately();
		}
		return br.readLine();
	}

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