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;
template <class T>
void dbs(string str, T t) {
  cerr << str << " : " << t << "\n";
}
template <class T, class... S>
void dbs(string str, T t, S... s) {
  int idx = str.find(',');
  cerr << str.substr(0, idx) << " : " << t << ", ";
  dbs(str.substr(idx + 1), s...);
}
template <class S, class T>
ostream& operator<<(ostream& os, const pair<S, T>& p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class S, class T>
ostream& operator<<(ostream& os, const map<S, T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
void prc(T a, T b) {
  cerr << "[";
  for (T i = a; i != b; ++i) {
    if (i != a) cerr << ", ";
    cerr << *i;
  }
  cerr << "]\n";
}
bool isvalid(pair<long long, long long>& a, pair<long long, long long>& b1,
             int op) {
  pair<long long, long long> b(make_pair(op * b1.first, op * b1.second));
  long long mag = (a.first + b.first) * (a.first + b.first) +
                  (a.second + b.second) * (a.second + b.second);
  if (mag <= (long long)1e12)
    return true;
  else
    return false;
}
struct node {
  pair<long long, long long> p;
  long long index = -1;
  node* a = NULL;
  node* b = NULL;
  int op = 0;
  node(pair<long long, long long> p, long long index = -1, node* a = NULL,
       node* b = NULL, int op = 0) {
    this->p = p;
    this->index = index;
    this->a = a;
    this->b = b;
    this->op = op;
  }
};
void dfs(node* nd, int par, vector<int>& sign) {
  if (nd->index != -1) {
    sign[nd->index] = par;
    return;
  }
  dfs(nd->a, par, sign);
  dfs(nd->b, par * (nd->op), sign);
}
void code() {
  long long n;
  cin >> n;
  vector<pair<long long, long long>> v(n);
  deque<node*> q;
  for (long long i = 0; i < (long long)(n); ++i) {
    cin >> v[i].first >> v[i].second;
    node* temp = new node(make_pair(v[i].first, v[i].second), i, NULL, NULL, 0);
    q.push_back(temp);
  }
  vector<node*> el;
  while (!q.empty()) {
    el.clear();
    int i;
    for (i = 0; i < 3 && !q.empty(); i++) {
      el.push_back((q.front()));
      q.pop_front();
    }
    if (i != 1) {
      long long flag = 1;
      for (int j = 0; j < el.size() && flag; j++)
        for (int k = j + 1; k < el.size() && flag; k++)
          for (int op = -1; op <= 1 && flag; op += 2) {
            if (isvalid(el[j]->p, el[k]->p, op)) {
              node* temp =
                  new node(make_pair(el[j]->p.first + op * (el[k]->p.first),
                                     el[j]->p.second + op * (el[k]->p.second)),
                           (long long)-1, el[j], el[k], op);
              q.push_back(temp);
              if (i == 3) q.push_back(el[3 - j - k]);
              flag = 0;
            }
          }
    }
  }
  vector<int> sign(n);
  for (auto e : el) {
    dfs(e, 1, sign);
  }
  long long X = 0, Y = 0;
  for (long long i = 0; i < (long long)(n); ++i) {
    cout << sign[i] << " ";
    X += sign[i] * v[i].first;
    Y += sign[i] * v[i].second;
  }
}
int main() {
  int t = 1;
  for (auto i = (1); i != (t + 1); i++) {
    code();
  }
  return 0;
}
