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;
struct Point {
  long long x, y, ind;
  Point(long long x, long long y) : x(x), y(y) {}
  Point() {}
  Point operator+(const Point &P) const { return Point(P.x + x, P.y + y); }
  Point operator-(const Point &P) const { return Point(x - P.x, y - P.y); }
  long long square() { return x * x + y * y; }
};
long long getBit(long long x, long long i) { return (x >> i) & 1LL; }
const long long MX = 4e5;
long long sgn[MX];
vector<long long> tree[MX];
long long n;
void dfs(long long u, long long s = 1) {
  for (long long v : tree[u]) {
    dfs(v, s * sgn[u]);
  }
  if (tree[u].empty()) {
    sgn[u] *= s;
    assert(u < n);
  }
}
const long long LIMIT = 1e6;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n;
  deque<Point> P(n);
  for (long long i = 0; i < (long long)n; i++) {
    cin >> P[i].x >> P[i].y;
    P[i].ind = i;
  }
  if (n == 1) {
    cout << "1\n";
    return 0;
  }
  for (long long i = 0; i < 2 * n; i++) {
    sgn[i] = -2;
  }
  long long cnt = n;
  for (long long i = 0; i < n - 2; i++) {
    assert(P[0].square() <= LIMIT * LIMIT);
    assert(P[1].square() <= LIMIT * LIMIT);
    long long best = 1e18;
    long long choiceMask;
    for (long long mask = 0; mask < (1LL << 3); mask++) {
      if (__builtin_popcount(mask) != 2) continue;
      vector<long long> v;
      for (long long k = 0; k < 3; k++) {
        if (getBit(mask, k) == 1) {
          v.push_back(k);
        }
      }
      long long posi = (P[v[0]] + P[v[1]]).square();
      long long nega = (P[v[0]] - P[v[1]]).square();
      if (min(posi, nega) < best) {
        best = min(posi, nega);
        choiceMask = mask;
      }
    }
    if (choiceMask == 6) {
      swap(P[0], P[2]);
    } else if (choiceMask == 5) {
      swap(P[1], P[2]);
    }
    Point P0 = P[0];
    Point P1 = P[1];
    P.pop_front();
    P.pop_front();
    long long posi = (P0 + P1).square();
    long long nega = (P0 - P1).square();
    assert(sgn[P0.ind] == -2);
    assert(sgn[P1.ind] == -2);
    if (posi < nega) {
      sgn[P0.ind] = 1;
      sgn[P1.ind] = 1;
      Point sum = P0 + P1;
      sum.ind = cnt;
      P.push_back(sum);
    } else {
      sgn[P0.ind] = 1;
      sgn[P1.ind] = -1;
      Point minus = P0 - P1;
      minus.ind = cnt;
      P.push_back(minus);
    }
    tree[cnt].push_back(P0.ind);
    tree[cnt].push_back(P1.ind);
    cnt++;
  }
  assert(P.size() == 2);
  long long posi = (P[0] + P[1]).square();
  long long nega = (P[0] - P[1]).square();
  assert(sgn[P[0].ind] == -2);
  assert(sgn[P[1].ind] == -2);
  if (posi < nega) {
    sgn[P[0].ind] = 1;
    sgn[P[1].ind] = 1;
  } else {
    sgn[P[0].ind] = 1;
    sgn[P[1].ind] = -1;
  }
  sgn[cnt] = 1;
  tree[cnt].push_back(P[0].ind);
  tree[cnt].push_back(P[1].ind);
  dfs(cnt);
  for (long long i = 0; i < (long long)n; i++) cout << sgn[i] << " ";
  return 0;
}