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 <typename T, typename U>
inline void smin(T &a, U b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, U b) {
  if (a < b) a = b;
}
template <class T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T, class T1>
inline void gn(T &first, T1 &second) {
  gn(first);
  gn(second);
}
template <class T, class T1, class T2>
inline void gn(T &first, T1 &second, T2 &z) {
  gn(first);
  gn(second);
  gn(z);
}
template <class T>
inline void print(T first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
template <class T>
inline void printsp(T first) {
  print(first);
  putchar(' ');
}
template <class T>
inline void println(T first) {
  print(first);
  putchar('\n');
}
template <class T, class U>
inline void print(T first, U second) {
  printsp(first);
  println(second);
}
template <class T, class U, class V>
inline void print(T first, U second, V z) {
  printsp(first);
  printsp(second);
  println(z);
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
struct point {
  int first, second, id;
  point(int first = 0, int second = 0, int id = 0)
      : first(first), second(second), id(id) {}
  point operator-(point a) { return point(first - a.first, second - a.second); }
  point operator+(point a) { return point(first + a.first, second + a.second); }
  point operator*(int a) { return point(first * a, second * a); }
  point conj() { return point(-second, first); }
  long long operator^(point a) {
    return (long long)first * a.second - (long long)second * a.first;
  }
  long long operator*(point a) {
    return (long long)first * a.first + (long long)second * a.second;
  }
  double nor() { return sqrt(*this * *this); }
  bool operator<(const point &a) const {
    if (first != a.first) return first < a.first;
    return second < a.second;
  }
  bool operator>(const point &a) const {
    if (first != a.first) return first > a.first;
    return second > a.second;
  }
  bool operator==(const point &a) const {
    if (first != a.first) return 0;
    return second == a.second;
  }
  void input() { gn(first, second); }
  void print() { ::print(first, second); }
};
const long long MX = 2250000000000LL;
bool flag[101010 * 300];
point p[101010];
int ans[101010];
point solve(int u, int L, int R) {
  if (L + 6 >= R) {
    point res;
    long long mxv = 1LL << 60;
    int k = -1;
    for (int i = 0, mx = R - L - 1; i < 1 << mx; i++) {
      point d = p[L];
      for (int j = 0; j < mx; j++) {
        if ((((i) >> (j)) & 1))
          d = d - p[L + j + 1];
        else
          d = d + p[L + j + 1];
      }
      long long a = ((d) * (d));
      if (a < mxv) mxv = a, k = i, res = d;
    }
    while (k) ans[p[L + (__builtin_ctz(k)) + 1].id] ^= 1, k = k ^ (k & -k);
    return res;
  }
  point a[5];
  for (int i = 0; i < 5; i++)
    a[i] = solve(u * 5 + i + 1, L + (R - L) * i / 5, L + (R - L) * (i + 1) / 5);
  long long mx = 1LL << 60;
  int k = -1;
  point e;
  for (int i = 0; i < 16; i++) {
    point d = a[0];
    for (int j = 0; j < 4; j++) {
      if ((((i) >> (j)) & 1))
        d = d - a[j + 1];
      else
        d = d + a[j + 1];
    }
    long long a = ((d) * (d));
    if (a < mx) mx = a, k = i, e = d;
  }
  assert(~k);
  for (int i = 0; i < 4; i++)
    if ((((k) >> (i)) & 1)) flag[u * 5 + i + 2] ^= 1;
  return e;
}
void update(int u, int L, int R) {
  if (L + 6 >= R) {
    for (int i = L; i < R; i++) ans[p[i].id] ^= flag[u];
    return;
  }
  for (int j = 0; j < 5; j++) {
    if (flag[u]) flag[u * 5 + j + 1] ^= 1;
    update(u * 5 + j + 1, L + (R - L) * j / 5, L + (R - L) * (j + 1) / 5);
  }
}
bool cmp(point a, point b) { return a * a < b * b; }
bool cmp1(point a, point b) { return a.id < b.id; }
int main() {
  int n;
  gn(n);
  for (int i = 0; i < n; i++) p[i].input(), p[i].id = i;
  sort(p, p + n, cmp);
  point a = solve(1, 0, n);
  assert((long long)a.first * a.first + (long long)a.second * a.second <= MX);
  update(1, 0, n);
  for (int i = 0; i < n; i++) printsp(ans[i] ? -1 : 1);
  point b;
  sort(p, p + n, cmp1);
  for (int i = 0; i < n; i++) {
    if (ans[i])
      b = b - p[i];
    else
      b = b + p[i];
  }
  assert((long long)b.first * b.first + (long long)b.second * b.second <= MX);
  return 0;
}
