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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
inline double cross(double x1, double y1010101010101, double x2, double y2) {
  return x1 * x2 + y1010101010101 * y2;
}
inline double len(double x, double y) { return sqrt(x * x + y * y); }
inline double angle(double x1, double y1010101010101, double x2, double y2) {
  if (x1 == 0 && y1010101010101 == 0) return pi;
  if (x2 == 0 && y2 == 0) return pi;
  return acos(cross(x1, y1010101010101, x2, y2) / len(x1, y1010101010101) /
              len(x2, y2));
}
int n, x[100005], y[100005], cur = 0;
struct data {
  double tx, ty;
  int fx, fy;
  int cx, cy;
  data operator~() {
    data ans = *this;
    ans.tx = -ans.tx;
    ans.ty = -ans.ty;
    ans.cx = -ans.cx;
    ans.cy = -ans.cy;
    return ans;
  }
} d[100005 << 5];
inline data add(int x, int y, int cx, int cy) {
  data ans;
  ans.tx = d[x].tx * cx + d[y].tx * cy;
  ans.ty = d[x].ty * cx + d[y].ty * cy;
  ans.cx = cx;
  ans.cy = cy;
  ans.fx = x;
  ans.fy = y;
  return ans;
}
int neg[100005 << 5];
inline void dump(int x) {
  if (x <= n) return;
  neg[d[x].fx] = neg[x] * d[x].cx;
  neg[d[x].fy] = neg[x] * d[x].cy;
  dump(d[x].fx);
  dump(d[x].fy);
}
inline void dfs(int x, int y, int z, int w) {
  if (z == n + 1) {
    d[++cur] = ~d[x];
    d[++cur] = ~d[y];
    vector<int> t;
    t.push_back(x);
    t.push_back(y);
    t.push_back(cur - 1);
    t.push_back(cur);
    for (int i = 0; i < 4; i += 2)
      for (int j = 1; j < 4; j += 2) {
        int u = t[i], v = t[j];
        if (len(d[u].tx + d[v].tx, d[u].ty + d[v].ty) <= 1500000.0) {
          if (i == 2)
            neg[x] = -1;
          else
            neg[x] = 1;
          if (j == 3)
            neg[y] = -1;
          else
            neg[y] = 1;
          dump(x);
          dump(y);
          return;
        }
      }
  }
  d[++cur] = ~d[x];
  d[++cur] = ~d[y];
  d[++cur] = ~d[z];
  vector<int> t;
  t.push_back(x);
  t.push_back(y);
  t.push_back(z);
  t.push_back(cur - 2);
  t.push_back(cur - 1);
  t.push_back(cur);
  for (int i = 0; i < 6; i++)
    for (int j = 0; j < i; j++) {
      if ((i % 3) == (j % 3)) continue;
      int a = t[i], b = t[j];
      if (angle(d[a].tx, d[a].ty, d[b].tx, d[b].ty) >= 2.0 * pi / 3) {
        d[++cur] = add(a, b, 1, 1);
        int nxt = 3 - (i % 3) - (j % 3);
        if (nxt == 0) dfs(cur, x, w, w + 1);
        if (nxt == 1) dfs(cur, y, w, w + 1);
        if (nxt == 2) dfs(cur, z, w, w + 1);
        return;
      }
    }
}
int main() {
  scanf("%d", &n);
  if (n == 1) return puts("1"), 0;
  for (int i = 1; i <= n; i++) scanf("%d%d", &x[i], &y[i]);
  for (int i = 1; i <= n; i++) {
    d[i].tx = x[i];
    d[i].ty = y[i];
    d[i].fx = i;
    d[i].fy = 0;
    d[i].cx = 1;
    d[i].cy = 0;
  }
  cur = n;
  dfs(1, 2, 3, 4);
  for (int i = 1; i <= n; i++) printf("%d ", neg[i]);
  return 0;
}