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 int N = 201010, inf = 1e6;
struct P {
  int x, y;
  P() {}
  P(int _x, int _y) { x = _x, y = _y; }
  P operator+(const P &c) const { return P(x + c.x, y + c.y); }
  P operator-(const P &c) const { return P(x - c.x, y - c.y); }
};
double dis(P a) { return sqrt(1. * a.x * a.x + 1. * a.y * a.y); }
int n, m, top;
int ls[N], rs[N], tag[N], sta[N], pre[N];
P p[N];
inline int newnode(P point) {
  p[++m] = point;
  tag[m] = 1;
  return m;
}
inline void gao() {
  for (int i = (0); i < (3); i++)
    for (int j = (i + 1); j < (3); j++) {
      double t;
      if ((t = dis(p[sta[top - i]] + p[sta[top - j]])) <= inf) {
        int u = newnode(p[sta[top - i]] + p[sta[top - j]]);
        ls[u] = sta[top - i];
        rs[u] = sta[top - j];
        sta[top - 2] = sta[top - 3 + i + j];
        sta[top - 1] = m;
        --top;
        return;
      }
      if ((t = dis(p[sta[top - i]] - p[sta[top - j]])) <= inf) {
        int u = newnode(p[sta[top - i]] - p[sta[top - j]]);
        ls[u] = sta[top - i];
        rs[u] = sta[top - j];
        tag[rs[u]] = -tag[rs[u]];
        sta[top - 2] = sta[top - 3 + i + j];
        sta[top - 1] = m;
        --top;
        return;
      }
    }
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  cin >> n;
  for (int i = (1); i < (n + 1); i++) {
    int x, y;
    cin >> x >> y;
    p[i] = P(x, y);
    tag[i] = 1;
    sta[++top] = i;
  }
  if (n == 1) {
    cout << 1 << "\n";
    return 0;
  }
  m = n;
  while (top >= 3) {
    gao();
  }
  int u;
  if (dis(p[sta[1]] + p[sta[2]]) < dis(p[sta[1]] - p[sta[2]])) {
    u = newnode(p[sta[1]] + p[sta[2]]);
    ls[u] = sta[1];
    rs[u] = sta[2];
  } else {
    u = newnode(p[sta[1]] - p[sta[2]]);
    ls[u] = sta[1];
    rs[u] = sta[2];
    tag[rs[u]] = -tag[rs[u]];
  }
  for (int i = (n + 1); i < (m + 1); i++) {
    pre[ls[i]] = pre[rs[i]] = i;
  }
  for (int i = m - 1; i; --i) {
    tag[i] *= tag[pre[i]];
  }
  for (int i = (1); i < (n + 1); i++) {
    cout << tag[i] << " ";
  }
  cout << "\n";
  return 0;
}