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 long long BIG = 1000000000000000000LL;
void cpr(string s, vector<long long> v) {
  long long i = 0;
  for (char c : s) {
    if (c == '$')
      cout << v[i++];
    else
      cout << c;
  }
  cout << '\n';
}
void cpr(string s) { cpr(s, {}); }
void solve();
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();
  return 0;
}
const long long borne = (long long)(1e5) + 5;
vector<pair<pair<long long, long long>, long long> > quad[4];
vector<long long> rf[borne];
void rajouter(pair<pair<long long, long long>, long long> infos) {
  long long k1 = (infos.first.first > 0);
  long long k2 = (infos.first.second > 0);
  k2 *= 2;
  quad[k1 | k2].push_back(infos);
}
void fusion(long long a, long long b) {
  auto tp1 = quad[a].back();
  quad[a].pop_back();
  auto tp2 = quad[b].back();
  quad[b].pop_back();
  if (rf[tp1.second].size() < rf[tp2.second].size()) swap(tp1, tp2);
  long long c = 1;
  if (a == b) {
    c *= -1;
  }
  tp1.first.first += c * tp2.first.first;
  tp1.first.second += c * tp2.first.second;
  for (auto x : rf[tp2.second]) rf[tp1.second].push_back(c * x);
  rajouter(tp1);
}
long long nbVec;
void solve() {
  cin >> nbVec;
  for (long long i = (0); i < (nbVec); ++i) {
    long long x, y;
    cin >> x >> y;
    pair<pair<long long, long long>, long long> info = {{x, y}, i + 1};
    rf[i + 1].push_back(i + 1);
    rajouter(info);
  }
  bool b = true;
  long long x = nbVec;
  while (b) {
    b = false;
    for (long long i = (0); i < (4); ++i) {
      if (quad[i].size() >= 2U) {
        fusion(i, i);
        --x;
        b = true;
      }
      long long j = i ^ 3;
      if (!(quad[i].empty() || quad[j].empty())) {
        fusion(i, j);
        --x;
        b = true;
      }
    }
  }
  vector<long long> ans(nbVec);
  for (long long bm = (0); bm < (35); ++bm) {
    long long dx = 0, dy = 0;
    for (long long i = (0); i < (4); ++i) {
      if (!quad[i].empty()) {
        auto x = quad[i].back();
        long long c = 1;
        if (bm & (1 << i)) c = -1;
        dx += c * x.first.first;
        dy += c * x.first.second;
        vector<long long> &cibles = rf[x.second];
        assert(!cibles.empty());
        for (long long o : cibles) {
          ans[abs(o) - 1] = abs(o) / o;
          ans[abs(o) - 1] *= c;
        }
      }
    }
    double dd = sqrt(dx * dx + dy * dy);
    if (dd <= 1.4 * (double)(1e6)) break;
  }
  for (long long i = (0); i < (nbVec); ++i) cout << ans[i] << " ";
  cout << "\n";
}