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.util.*;
import java.io.*;

public class Eproblem
{
	public static void main(String[] args)
	{
		FastReader reader = new FastReader();
		PrintWriter writer = new PrintWriter(System.out);
		Random rand = new Random();

		int n = reader.nextInt();
		long[] x = new long[n];
		long[] y = new long[n];
		long[] ans = new long[n];
		int[] ind = new int[n];
		long px=0, py=0;

		for(int i=0; i<n; i++)
		{
			x[i] = reader.nextInt();
			y[i] = reader.nextInt();
			ind[i] = i;
		}

		long limit = 1500000;

		do
		{
			px = 0;
			py = 0;

			for (int i=1; i<n; i++)
			{
				long tempX = x[i];
				long tempY = y[i];
				int tempI = ind[i];

				int got = rand.nextInt(i);

				x[i] = x[got];
				y[i] = y[got];
				ind[i] = ind[got];

				x[got] = tempX;
				y[got] = tempY;
				ind[got] = tempI;
			}

			for (int i=0; i<n; i++)
			{
				long plus = (px + x[i])*(px + x[i]) + (py + y[i])*(py + y[i]);
				long mnus = (px - x[i])*(px - x[i]) + (py - y[i])*(py - y[i]);

				if (plus <= mnus)
				{
					px += x[i];
					py += y[i];

					ans[ind[i]] = 1;
				}
				else
				{
					px -= x[i];
					py -= y[i];

					ans[ind[i]] = -1;
				}
			}

			//writer.println("while");
			//writer.flush();
		}
		while (px*px + py*py > limit*limit);

		//long tx=0, ty=0;
		for (int i=0; i<n; i++)
		{
			//tx += ans[i]*x[i];
			//ty += ans[i]*y[i];

			writer.print(ans[i] + " ");
		}

		writer.println();
		//writer.println(px + " " + py + " " + (px*px + py*py) + " " + (limit*limit));
		writer.close();
	}

	static class FastReader
	{
		BufferedReader br;
		StringTokenizer st;

		public FastReader()
		{
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next()
		{
			while (st == null || !st.hasMoreElements())
			{
				try
				{
					st = new StringTokenizer(br.readLine());
				}
				catch (IOException e)
				{
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

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

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

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

		String nextLine()
		{
			String str = "";
			try
			{
				str = br.readLine();
			}
			catch (IOException e)
			{
				e.printStackTrace();
			}
			return str;
		}
	}
}