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>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC optimize("fast-math")
using namespace std;
const int INF = 1e9;
const long long INFll = 2e18;
const int BASE1 = 179;
const int BASE2 = 653;
const long long MOD = 1e9 + 7;
const int MAXN = 1e5 + 10;
const long double PI = 3.1415926535;
const long double EPS = 1e-10;
struct Point {
  long long x, y;
  Point() {
    x = 0;
    y = 0;
  }
  Point(long long x, long long y) : x(x), y(y){};
  long double polar_angle() { return atan2(y, x); }
};
struct Vector {
  long long x, y;
  Vector() {
    x = 0;
    y = 0;
  }
  Vector(long long x, long long y) : x(x), y(y){};
  Vector(Point A, Point B) {
    x = B.x - A.x;
    y = B.y - A.y;
  }
  long long dist() { return x * x + y * y; }
};
istream& operator>>(istream& in, Point& A) {
  in >> A.x >> A.y;
  return in;
}
ostream& operator<<(ostream& out, const Point& A) {
  out << A.x << " " << A.y;
  return out;
}
Vector operator+(const Vector& a, const Vector& b) {
  return Vector(a.x + b.x, a.y + b.y);
}
Vector operator-(const Vector& a, const Vector& b) {
  return Vector(a.x - b.x, a.y - b.y);
}
long long dot(const Vector& A, const Vector& B) {
  return A.x * B.x + A.y * B.y;
}
long long cross(const Vector& A, const Vector& B) {
  return A.x * B.y - A.y * B.x;
}
long double angle_vectors(Vector A, Vector B) {
  return abs(atan2(cross(A, B), dot(A, B)));
}
int check(long double angle) {
  if (angle - PI / 2 > EPS)
    return 2;
  else if (angle - PI / 2 < EPS && angle - PI / 2 >= 0)
    return 1;
  else
    return 0;
}
bool ok(long long a, long long b) {
  return a >= 0 && b <= 0 || a <= 0 && b >= 0;
}
bool ok2(long long a, long long b, long long c, long long d) {
  if (a > b) swap(a, b);
  if (c > d) swap(c, d);
  return max(a, c) <= min(b, d);
}
bool intersect(Point A, Point B, Point C, Point D) {
  Vector AB(A, B), AC(A, C), AD(A, D);
  Vector CD(C, D), CA(C, A), CB(C, B);
  if (cross(AB, CD) == 0) {
    if (ok2(A.x, B.x, C.x, D.x) && ok2(A.y, B.y, C.y, D.y))
      return true;
    else
      return false;
    ;
  }
  if (ok(cross(AB, AC), cross(AB, AD)) && ok(cross(CD, CB), cross(CD, CA)))
    return true;
  else
    return false;
}
long long sub(long long a, long long b, long long mod) {
  a -= b;
  if (a < 0) a += mod;
  return a;
}
long long sum(long long a, long long b, long long mod) {
  a += b;
  if (a >= mod) a -= mod;
  return a;
}
struct myv {
  vector<pair<int, int>> c;
  int rev;
  int x, y;
  myv() {
    rev = 0;
    x = -1, y = -1;
  }
};
void solve() {
  long long n;
  cin >> n;
  long long r = 1e6;
  vector<pair<Vector, int>> v(n);
  for (int i = 0; i < (n); i++) {
    cin >> v[i].first.x >> v[i].first.y;
    v[i].second = i;
  }
  if (n == 1) {
    cout << 1 << "\n";
    return;
  }
  vector<myv> dop(n);
  for (int i = 0; i < (n); i++) {
    dop[i].c.emplace_back(make_pair(i, 1));
    dop[i].x = v[i].first.x;
    dop[i].y = v[i].first.y;
    dop[i].rev = 0;
  }
  for (int q = 0; q < (n - 2); q++) {
    bool fl = false;
    for (int i = 0; i < (6); i++) {
      if (fl) break;
      for (int j = 0; j < (6); j++) {
        if (i % 3 == j % 3) continue;
        Vector v1(dop[q + i % 3].x, dop[q + i % 3].y);
        Vector v2(dop[q + j % 3].x, dop[q + j % 3].y);
        if (i >= 3) v1.x = -v1.x, v1.y = -v1.y;
        if (j >= 3) v2.x = -v2.x, v2.y = -v2.y;
        Vector v3 = v1 + v2;
        if (v3.dist() > ((r) * (r))) continue;
        fl = true;
        if (i >= 3) dop[q + i % 3].rev ^= 1;
        if (j >= 3) dop[q + j % 3].rev ^= 1;
        0;
        0;
        if (i % 3 > j % 3) swap(i, j);
        if (i % 3 == 0 && j % 3 == 1) {
          if (((int)(dop[q].c).size()) > ((int)(dop[q + 1].c).size())) {
            for (auto [e, c] : dop[q + 1].c) {
              if (dop[q + 1].rev && !dop[q].rev ||
                  !dop[q + 1].rev && dop[q].rev)
                dop[q].c.emplace_back(make_pair(e, -c));
              else
                dop[q].c.emplace_back(make_pair(e, c));
            }
            dop[q].x = v3.x, dop[q].y = v3.y;
            swap(dop[q], dop[q + 1]);
          } else {
            for (auto [e, c] : dop[q].c) {
              if (dop[q + 1].rev && !dop[q].rev ||
                  !dop[q + 1].rev && dop[q].rev)
                dop[q + 1].c.emplace_back(make_pair(e, -c));
              else
                dop[q + 1].c.emplace_back(make_pair(e, c));
            }
            dop[q + 1].x = v3.x, dop[q + 1].y = v3.y;
          }
        } else if (i % 3 == 0 && j % 3 == 2) {
          if (((int)(dop[q].c).size()) > ((int)(dop[q + 2].c).size())) {
            for (auto [e, c] : dop[q + 2].c) {
              if (dop[q + 2].rev && !dop[q].rev ||
                  !dop[q + 2].rev && dop[q].rev)
                dop[q].c.emplace_back(make_pair(e, -c));
              else
                dop[q].c.emplace_back(make_pair(e, c));
            }
            dop[q].x = v3.x, dop[q].y = v3.y;
            swap(dop[q + 1], dop[q + 2]);
            swap(dop[q], dop[q + 1]);
          } else {
            for (auto [e, c] : dop[q].c) {
              if (dop[q + 2].rev && !dop[q].rev ||
                  !dop[q + 2].rev && dop[q].rev)
                dop[q + 2].c.emplace_back(make_pair(e, -c));
              else
                dop[q + 2].c.emplace_back(make_pair(e, c));
            }
            dop[q + 2].x = v3.x, dop[q + 2].y = v3.y;
          }
        } else {
          if (((int)(dop[q + 1].c).size()) > ((int)(dop[q + 2].c).size())) {
            for (auto [e, c] : dop[q + 2].c) {
              if (dop[q + 1].rev && !dop[q + 2].rev ||
                  !dop[q + 1].rev && dop[q + 2].rev)
                dop[q + 1].c.emplace_back(make_pair(e, -c));
              else
                dop[q + 1].c.emplace_back(make_pair(e, c));
            }
            dop[q + 1].x = v3.x, dop[q + 1].y = v3.y;
            swap(dop[q], dop[q + 2]);
          } else {
            for (auto [e, c] : dop[q + 1].c) {
              if (dop[q + 1].rev && !dop[q + 2].rev ||
                  !dop[q + 1].rev && dop[q + 2].rev)
                dop[q + 2].c.emplace_back(make_pair(e, -c));
              else
                dop[q + 2].c.emplace_back(make_pair(e, c));
            }
            dop[q + 2].x = v3.x, dop[q + 2].y = v3.y;
            swap(dop[q + 1], dop[q]);
          }
        }
        break;
      }
    }
  }
  vector<int> c(n);
  Vector v3(dop[n - 2].x, dop[n - 2].y);
  v3.x += dop[n - 1].x, v3.y += dop[n - 1].y;
  0;
  0;
  0;
  if (v3.dist() <= ((1500000ll) * (1500000ll))) {
    for (auto [e, q] : dop[n - 2].c) {
      if (dop[n - 2].rev)
        c[e] = -q;
      else
        c[e] = q;
    }
    for (auto [e, q] : dop[n - 1].c) {
      if (dop[n - 1].rev)
        c[e] = -q;
      else
        c[e] = q;
    }
  } else {
    for (auto [e, q] : dop[n - 2].c) {
      if (dop[n - 2].rev)
        c[e] = q;
      else
        c[e] = -q;
    }
    for (auto [e, q] : dop[n - 1].c) {
      if (dop[n - 1].rev)
        c[e] = -q;
      else
        c[e] = q;
    }
  }
  for (int i = 0; i < (n); i++) cout << c[i] << " ";
  cout << "\n";
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(15);
  int t = 1;
  while (t--) solve();
  return 0;
}