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 EPS = 1e-13;
const long long INF = 1e18;
struct PT {
  long long x, y;
  PT() {}
  PT(long long x, long long y) : x(x), y(y) {}
  PT(const PT &p) : x(p.x), y(p.y) {}
  PT operator+(const PT &p) const { return PT(x + p.x, y + p.y); }
  PT operator-(const PT &p) const { return PT(x - p.x, y - p.y); }
  PT operator*(long long c) const { return PT(x * c, y * c); }
  PT operator/(long long c) const { return PT(x / c, y / c); }
  bool operator<(const PT &rhs) const {
    return make_pair(y, x) < make_pair(rhs.y, rhs.x);
  }
  bool operator==(const PT &rhs) const {
    return make_pair(y, x) == make_pair(rhs.y, rhs.x);
  }
};
long long dot(PT p, PT q) { return p.x * q.x + p.y * q.y; }
long long dist2(PT p, PT q) { return dot(p - q, p - q); }
long long cross(PT p, PT q) { return p.x * q.y - p.y * q.x; }
long long area2(PT a, PT b, PT c) {
  return cross(a, b) + cross(b, c) + cross(c, a);
}
ostream &operator<<(ostream &os, const PT &p) {
  os << "(" << p.x << "," << p.y << ")";
}
PT RotateCCW90(PT p) { return PT(-p.y, p.x); }
PT RotateCW90(PT p) { return PT(p.y, -p.x); }
PT RotateCCW(PT p, long long t) {
  return PT(p.x * cos(t) - p.y * sin(t), p.x * sin(t) + p.y * cos(t));
}
PT ProjectPointLine(PT a, PT b, PT c) {
  return a + (b - a) * dot(c - a, b - a) / dot(b - a, b - a);
}
PT ProjectPointSegment(PT a, PT b, PT c) {
  long long r = dot(b - a, b - a);
  if (fabs(r) < EPS) return a;
  r = dot(c - a, b - a) / r;
  if (r < 0) return a;
  if (r > 1) return b;
  return a + (b - a) * r;
}
long long DistancePointSegment(PT a, PT b, PT c) {
  return sqrt(dist2(c, ProjectPointSegment(a, b, c)));
}
long long DistancePointPlane(long long x, long long y, long long z, long long a,
                             long long b, long long c, long long d) {
  return fabs(a * x + b * y + c * z - d) / sqrt(a * a + b * b + c * c);
}
bool LinesParallel(PT a, PT b, PT c, PT d) {
  return fabs(cross(b - a, c - d)) < EPS;
}
bool LinesCollinear(PT a, PT b, PT c, PT d) {
  return LinesParallel(a, b, c, d) && fabs(cross(a - b, a - c)) < EPS &&
         fabs(cross(c - d, c - a)) < EPS;
}
int SegmentsIntersect(PT a, PT b, PT c, PT d) {
  if (LinesCollinear(a, b, c, d)) {
    if (dist2(a, c) < EPS || dist2(a, d) < EPS || dist2(b, c) < EPS ||
        dist2(b, d) < EPS)
      return 2;
    if (dot(c - a, c - b) > 0 && dot(d - a, d - b) > 0 && dot(c - b, d - b) > 0)
      return 0;
    return 2;
  }
  if (cross(d - a, b - a) * cross(c - a, b - a) > 0) return 0;
  if (cross(a - c, d - c) * cross(b - c, d - c) > 0) return 0;
  return 1;
}
PT ComputeLineIntersection(PT a, PT b, PT c, PT d) {
  b = b - a;
  d = c - d;
  c = c - a;
  assert(dot(b, b) > EPS && dot(d, d) > EPS);
  return a + b * cross(c, d) / cross(b, d);
}
PT ComputeCircleCenter(PT a, PT b, PT c) {
  b = (a + b) / 2;
  c = (a + c) / 2;
  return ComputeLineIntersection(b, b + RotateCW90(a - b), c,
                                 c + RotateCW90(a - c));
}
bool PointInPolygon(const vector<PT> &p, PT q) {
  bool c = 0;
  for (int i = 0; i < p.size(); i++) {
    int j = (i + 1) % p.size();
    if ((p[i].y <= q.y && q.y < p[j].y || p[j].y <= q.y && q.y < p[i].y) &&
        q.x < p[i].x + (p[j].x - p[i].x) * (q.y - p[i].y) / (p[j].y - p[i].y))
      c = !c;
  }
  return c;
}
bool PointOnPolygon(const vector<PT> &p, PT q) {
  for (int i = 0; i < p.size(); i++)
    if (dist2(ProjectPointSegment(p[i], p[(i + 1) % p.size()], q), q) < EPS)
      return true;
  return false;
}
vector<PT> CircleLineIntersection(PT a, PT b, PT c, long long r) {
  vector<PT> ret;
  b = b - a;
  a = a - c;
  long long A = dot(b, b);
  long long B = dot(a, b);
  long long C = dot(a, a) - r * r;
  long long D = B * B - A * C;
  if (D < -EPS) return ret;
  ret.push_back(c + a + b * (-B + sqrt(D + EPS)) / A);
  if (D > EPS) ret.push_back(c + a + b * (-B - sqrt(D)) / A);
  return ret;
}
vector<PT> CircleCircleIntersection(PT a, PT b, long long r, long long R) {
  vector<PT> ret;
  long long d = sqrt(dist2(a, b));
  if (d > r + R || d + min(r, R) < max(r, R)) return ret;
  long long x = (d * d - R * R + r * r) / (2 * d);
  long long y = sqrt(r * r - x * x);
  PT v = (b - a) / d;
  ret.push_back(a + v * x + RotateCCW90(v) * y);
  if (y > 0) ret.push_back(a + v * x - RotateCCW90(v) * y);
  return ret;
}
long long ComputeSignedArea(const vector<PT> &p) {
  long long area = 0;
  for (int i = 0; i < p.size(); i++) {
    int j = (i + 1) % p.size();
    area += p[i].x * p[j].y - p[j].x * p[i].y;
  }
  return area / 2.0;
}
long long ComputeArea(const vector<PT> &p) {
  return fabs(ComputeSignedArea(p));
}
PT ComputeCentroid(const vector<PT> &p) {
  PT c(0, 0);
  long long scale = 6.0 * ComputeSignedArea(p);
  for (int i = 0; i < p.size(); i++) {
    int j = (i + 1) % p.size();
    c = c + (p[i] + p[j]) * (p[i].x * p[j].y - p[j].x * p[i].y);
  }
  return c / scale;
}
bool IsSimple(const vector<PT> &p) {
  for (int i = 0; i < p.size(); i++) {
    for (int k = i + 1; k < p.size(); k++) {
      int j = (i + 1) % p.size();
      int l = (k + 1) % p.size();
      if (i == l || j == k) continue;
      if (SegmentsIntersect(p[i], p[j], p[k], p[l])) return false;
    }
  }
  return true;
}
bool between(const PT &a, const PT &b, const PT &c) {
  return (fabs(area2(a, b, c)) < EPS && (a.x - b.x) * (c.x - b.x) <= 0 &&
          (a.y - b.y) * (c.y - b.y) <= 0);
}
void ConvexHull(vector<PT> &pts) {
  sort(pts.begin(), pts.end());
  pts.erase(unique(pts.begin(), pts.end()), pts.end());
  vector<PT> up, dn;
  for (int i = 0; i < pts.size(); i++) {
    while (up.size() > 1 && area2(up[up.size() - 2], up.back(), pts[i]) >= 0)
      up.pop_back();
    while (dn.size() > 1 && area2(dn[dn.size() - 2], dn.back(), pts[i]) <= 0)
      dn.pop_back();
    up.push_back(pts[i]);
    dn.push_back(pts[i]);
  }
  pts = dn;
  for (int i = (int)up.size() - 2; i >= 1; i--) pts.push_back(up[i]);
  if (pts.size() <= 2) return;
  dn.clear();
  dn.push_back(pts[0]);
  dn.push_back(pts[1]);
  for (int i = 2; i < pts.size(); i++) {
    if (between(dn[dn.size() - 2], dn[dn.size() - 1], pts[i])) dn.pop_back();
    dn.push_back(pts[i]);
  }
  if (dn.size() >= 3 && between(dn.back(), dn[0], dn[1])) {
    dn[0] = dn.back();
    dn.pop_back();
  }
  pts = dn;
}
class dsu {
 public:
  vector<int> sets;
  void init(int n) {
    sets.resize(n);
    for (int i = 0; i < n; i++) {
      sets[i] = -1;
    }
  }
  int find_set(int x) {
    if (sets[x] < 0) return x;
    return sets[x] = find_set(sets[x]);
  }
  int union_sets(int x, int y) {
    int r[] = {find_set(x), find_set(y)};
    if (r[0] == r[1]) return -1;
    int l = (sets[r[0]] < sets[r[1]]) ? 0 : 1;
    sets[r[l]] += sets[r[l ^ 1]];
    sets[r[l ^ 1]] = r[l];
    return -sets[r[l]];
  }
};
const int N = 1e6 + 100;
PT p[N];
int ans[N];
int parmul[N];
const long long mx = 1.5e6 * 1.5e6;
PT calc(pair<PT, int> v[3]) {
  int best = 0;
  long long bestval = 1e18;
  for (int i = 0; i < 8; i++) {
    PT u(0, 0);
    for (int j = 0; j < 3; j++) {
      ans[v[j].second] = (i & (1 << j)) ? 1 : -1;
      u = u + v[j].first * ((long long)ans[v[j].second]);
    }
    long long d = dot(u, u);
    if (d <= bestval) {
      bestval = d;
      best = i;
    }
  }
  PT u(0, 0);
  int i = best;
  for (int j = 0; j < 3; j++) {
    ans[v[j].second] = (i & (1 << j)) ? 1 : -1;
    u = u + v[j].first * ((long long)ans[v[j].second]);
  }
  return u;
}
int main() {
  for (int i = 0; i < 1e6 + 10; i++) {
    parmul[i] = 1;
  }
  const int ui = N - 10;
  int n;
  scanf("%d", &n);
  PT u;
  for (int i = 0; i < n; i++) {
    scanf("%I64d%I64d", &u.x, &u.y);
    p[i] = u;
  }
  u = p[0];
  ans[0] = 1;
  for (int i = 1; i < n; i += 2) {
    pair<PT, int> v[3] = {make_pair(u, ui), make_pair(p[i], i),
                          make_pair(p[i + 1], i + 1)};
    u = calc(v);
    parmul[i - 1] = ans[ui];
  }
  for (int i = n - 1; i >= 0; i--) parmul[i] *= parmul[i + 1];
  for (int i = 0; i < n; i++) {
    printf("%d ", ans[i] * parmul[i]);
  }
  return 0;
}