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;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
struct mint {
  long long x;
  mint(long long x = 0) : x((x % 1000000007 + 1000000007) % 1000000007) {}
  mint &operator+=(const mint a) {
    if ((x += a.x) >= 1000000007) x -= 1000000007;
    return *this;
  }
  mint &operator-=(const mint a) {
    if ((x += 1000000007 - a.x) >= 1000000007) x -= 1000000007;
    return *this;
  }
  mint &operator*=(const mint a) {
    (x *= a.x) %= 1000000007;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res -= a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res *= a;
  }
  mint pow(long long t) const {
    if (!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1) a *= *this;
    return a;
  }
  mint inv() const { return pow(1000000007 - 2); }
  mint &operator/=(const mint a) { return (*this) *= a.inv(); }
  mint operator/(const mint a) const {
    mint res(*this);
    return res /= a;
  }
};
struct combination {
  vector<mint> fact, ifact;
  combination(int n) : fact(n + 1), ifact(n + 1) {
    assert(n < 1000000007);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 1;
    return fact[n] * ifact[k] * ifact[n - k];
  }
};
mint choose(int n, int a) {
  mint x, y;
  x = y = 1;
  for (long long p = 0; p < a; p++) {
    x *= n - p;
    y *= p + 1;
  }
  return x / y;
}
struct vec {
  long long x, y, z;
};
long long n;
vec v[150005];
vector<long long> res(150005);
long long up = 1500000;
bool check(long long x, long long y) {
  return (1LL * x * x + 1LL * y * y) <= up;
}
void dfs(long long node, long long x, long long y) {
  if (node > n) {
    for (long long p = 1; p < n + 1; p++) cout << res[p] << " ";
    exit(0);
  }
  if (check(x + v[node].x, y + v[node].y)) {
    res[v[node].z] = 1;
    dfs(node + 1, x + v[node].x, y + v[node].y);
  }
  if (check(x - v[node].x, y - v[node].y)) {
    res[v[node].z] = -1;
    dfs(node + 1, x - v[node].x, y - v[node].y);
  }
}
int main() {
  long long t, i, j, k, m, x, y, ans;
  t = 1;
  while (t--) {
    up = up * up;
    cin >> n;
    for (long long p = 1; p < n + 1; p++) {
      cin >> x >> y;
      v[p].x = x;
      v[p].y = y;
      v[p].z = p;
    }
    random_shuffle(v + 1, v + 1 + n);
    dfs(1, 0, 0);
  }
  return 0;
}