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.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class P5 {
	static long mp = 1000000l;
	
	static class Pair{
		long x;
		long y;
		int flip;
		int index;
		int parent = -1;
		LinkedList<Pair> children= new LinkedList<Pair>();
		Pair(int index,long _x,long _y){
			this.index=index;
			flip=1;
			x=_x;
			y=_y;
		}
		int[] allchilds(int n){
			int[] result = new int[n];
			result[index] = flip;
			Queue<Pair> toProcess = new LinkedList<Pair>(children);
			while(!toProcess.isEmpty()){
				Pair nxt = toProcess.poll();
				result[nxt.index]=nxt.flip*result[nxt.parent];
				toProcess.addAll(nxt.children);
			}
			return result;
		}
		boolean canComb(Pair p){
			if(p==null)return false;
			long tx1 = x-p.x;
			long ty1 = y-p.y;
			long tx2 = x+p.x;
			long ty2 = y+p.y;
			return tx1*tx1+ty1*ty1<=  mp*mp || tx2*tx2+ty2*ty2<=  mp*mp;
			
		}
		void comb(Pair p){
			long tx1 = x-p.x;
			long ty1 = y-p.y;
			long tx2 = x+p.x;
			long ty2 = y+p.y;
			if(tx1*tx1+ty1*ty1<= mp*mp){
				p.parent=index;
				this.children.add(p);
				p.flip = -1;
				x=tx1;
				y=ty1;
				return;
			}
			if(tx2*tx2+ty2*ty2<=  mp*mp){
				p.parent=index;
				this.children.add(p);
				x=tx2;
				y=ty2;
				return;
			}
		}
		void forceComb(Pair p){
			//can force the bound of 2. 
			long tx1 = x-p.x;
			long ty1 = y-p.y;
			long tx2 = x+p.x;
			long ty2 = y+p.y;
			if(tx1*tx1+ty1*ty1<= mp*mp*2){
				p.parent=index;
				this.children.add(p);
				p.flip = -1;
				x=tx1;
				y=ty1;
				return;
			}
			if(tx2*tx2+ty2*ty2<=  mp*mp*2){
				p.parent=index;
				this.children.add(p);
				x=tx2;
				y=ty2;
				return;
			}
		}
	}
	public static void main(String[] args) throws Exception{
		/**
		 * 1.5 is generous, really only need sqrt(2)
		 * 
		 * 
		 */
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		if(n==1){
			br.readLine(); //<-clear input;
			bw.write("1\n");
			bw.flush();
			return;
		}
		StringTokenizer st = new StringTokenizer(br.readLine());
		Pair a = new Pair(0,Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
		a.index = 0;
		Pair b = null;
		long[] ogx=new long[n];
		long[] ogy=new long[n];
		ogx[0]=a.x;
		ogy[0]=a.y;
		for(int j=1;j<n;++j){
			st = new StringTokenizer(br.readLine());
			Pair nxt = new Pair(j,ogx[j]=Integer.parseInt(st.nextToken()),ogy[j]=Integer.parseInt(st.nextToken()));
			if(nxt.canComb(a)){
				nxt.comb(a);
				a=nxt;
			}
			else if(nxt.canComb(b)){
				nxt.comb(b);
				b=nxt;
			}
			else{
				//this forces b to be null, since it has to be able to do one or the other, insert it at b
				b=nxt;
			}
			if(a.canComb(b)){
				a.comb(b);
				b=null;
			}
		}
		//
		if(b!=null){
			a.forceComb(b);
		}
		int[] res = a.allchilds(n);
		for(int j=0;j<n;++j){
			if(j>0){
				bw.write(" ");
			}
			bw.write(""+res[j]);
		}
		bw.flush();
	}
}