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 
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;
template <class T>
ostream &operator<<(ostream &os, const V<T> &v) {
  cout << "[";
  for (auto p : v) cout << p << ", ";
  cout << "]";
  return os;
}
using D = int;
const D EPS = 0;
int sgn(D a) { return (abs(a) <= EPS) ? 0 : (a < 0 ? -1 : 1); }
int sgn(D a, D b) { return sgn(a - b); }
struct Pt2 {
  D x, y;
  Pt2(D _x = D(), D _y = D()) : x(_x), y(_y) {}
  Pt2 operator+(const Pt2 &r) const { return Pt2(x + r.x, y + r.y); }
  Pt2 operator-(const Pt2 &r) const { return Pt2(x - r.x, y - r.y); }
  Pt2 operator*(const Pt2 &r) const {
    return Pt2(x * r.x - y * r.y, x * r.y + y * r.x);
  }
  Pt2 operator*(const D &r) const { return Pt2(x * r, y * r); }
  Pt2 &operator+=(const Pt2 &r) { return *this = *this + r; }
  Pt2 &operator-=(const Pt2 &r) { return *this = *this - r; }
  Pt2 &operator*=(const Pt2 &r) { return *this = *this * r; }
  Pt2 &operator*=(const D &r) { return *this = *this * r; }
  Pt2 operator-() const { return Pt2(-x, -y); }
  bool operator<(const Pt2 &r) const {
    return 2 * sgn(x, r.x) + sgn(y, r.y) < 0;
  }
  bool operator==(const Pt2 &r) const { return sgn((*this - r).rabs()) == 0; }
  D norm() const { return x * x + y * y; }
  D rabs() const { return max(std::abs(x), std::abs(y)); }
  pair<D, D> to_pair() const { return make_pair(x, y); }
};
using P = Pt2;
struct Node {
  P p;
  int id;
  bool neg;
  Node *l;
  Node *r;
};
Node *tr[3] = {nullptr, nullptr, nullptr};
int get_ty(P p) {
  if (p.x >= 0 && p.y <= 2 * p.x) return 0;
  if (p.x <= 0 && p.y <= -2 * p.x) return 2;
  return 1;
}
void add(Node *n) {
  if (n->p.y < 0) {
    n->p = -(n->p);
    n->neg = !(n->neg);
  }
  int ty = get_ty(n->p);
  auto m = tr[ty];
  if (m == nullptr) {
    tr[ty] = n;
    return;
  }
  n->neg = !(n->neg);
  tr[ty] = nullptr;
  add(new Node{m->p - n->p, -1, false, n, m});
}
V<char> sig;
void dfs(Node *n, bool neg) {
  if (n == nullptr) return;
  if (n->neg) neg = !neg;
  if (n->id >= 0) {
    sig[n->id] = neg;
  }
  dfs(n->l, neg);
  dfs(n->r, neg);
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(20) << fixed;
  int n;
  cin >> n;
  sig = V<char>(n);
  V<P> mv(n);
  for (int ph = 0; ph < n; ph++) {
    D x, y;
    cin >> x >> y;
    mv[ph] = P(x, y);
    add(new Node{mv[ph], ph, false, nullptr, nullptr});
  }
  for (int ph = 0; ph < 3; ph++) {
    dfs(tr[ph], (ph % 2) == 0);
  }
  P p = P(0, 0);
  for (int ph = 0; ph < n; ph++) {
    if (sig[ph])
      p += mv[ph];
    else
      p -= mv[ph];
  }
  for (int ph = 0; ph < n; ph++) {
    if (sig[ph])
      cout << "1 ";
    else
      cout << "-1 ";
  }
  cout << endl;
  return 0;
}
