#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
const int maxn = 1e5 + 5;
pair<long long, long long> c[maxn];
const long long limit = 1.5 * 1e6;
const long long limit2 = limit * limit;
int ans[maxn];
bool check(long long x, long long y) { return (x * x + y * y) <= limit2; }
long long cal(long long x, long long y) { return x * x + y * y; }
struct node {
  long long x, y;
  node(long long _x, long long _y) : x(_x), y(_y) {}
  node() {}
  bool operator<(const node& b) const { return cal(x, y) < cal(b.x, b.y); }
};
int n;
void out() {
  for (int i = 1; i <= n; i++) {
    printf("%d ", ans[i]);
  }
  puts("");
}
bool work() {
  int times = 1e8;
  times /= n;
  bool flag = false;
  srand(time(NULL));
  for (int k = 0; k < times; k++) {
    long long x = 0, y = 0;
    for (int i = 1; i <= n; i++) {
      42;
      long long tmp1x = x + c[i].first;
      long long tmp1y = y + c[i].second;
      long long tmp2x = x - c[i].first;
      long long tmp2y = y - c[i].second;
      long long tmp1 = tmp1x * tmp1x + tmp1y * tmp1y;
      long long tmp2 = tmp2x * tmp2x + tmp2y * tmp2y;
      if (tmp1 < tmp2) {
        x = tmp1x;
        y = tmp1y;
        ans[i] = 1;
      } else if (tmp1 > tmp2) {
        x = tmp2x;
        y = tmp2y;
        ans[i] = -1;
      } else {
        bool f = rand() % 2;
        if (f) {
          x = tmp1x;
          y = tmp1y;
          ans[i] = 1;
        } else {
          x = tmp2x;
          y = tmp2y;
          ans[i] = -1;
        }
      }
    }
    if (check(x, y)) {
      flag = true;
      break;
    }
  }
  if (flag) {
    out();
  }
  return flag;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%lld %lld", &c[i].first, &c[i].second);
  }
  if (work()) {
    return 0;
  }
  int times = 1e8;
  times /= n;
  srand(time(NULL));
  vector<node> Q, Q2;
  map<pair<pair<long long, long long>, int>, node> M;
  Q.push_back(node(0, 0));
  for (int i = 1; i <= n; i++) {
    Q2.clear();
    for (auto v : Q) {
      long long tmp1x = v.x + c[i].first;
      long long tmp1y = v.y + c[i].second;
      long long tmp2x = v.x - c[i].first;
      long long tmp2y = v.y - c[i].second;
      Q2.push_back(node(tmp1x, tmp1y));
      Q2.push_back(node(tmp2x, tmp2y));
      M[make_pair(make_pair(tmp1x, tmp1y), i)] = v;
      M[make_pair(make_pair(tmp2x, tmp2y), i)] = v;
    }
    Q.clear();
    int sz = 50;
    sort(Q2.begin(), Q2.end());
    for (auto v : Q2) {
      Q.push_back(v);
      sz--;
      if (sz == 0) break;
    }
  }
  auto v = Q.begin();
  int now = n;
  long long nowx = v->x;
  long long nowy = v->y;
  42;
  for (auto v : M) {
    auto tmp1 = v.first;
    auto tmp2 = v.second;
    42;
    42;
  }
  while (now >= 1) {
    node lxt = M[make_pair(make_pair(nowx, nowy), now)];
    if (lxt.x + c[now].first == nowx && lxt.y + c[now].second == nowy) {
      ans[now] = 1;
    } else {
      ans[now] = -1;
    }
    now--;
    nowx = lxt.x;
    nowy = lxt.y;
  }
  for (int i = 1; i <= n; i++) {
    printf("%d ", ans[i]);
  }
  puts("");
  return 0;
}

### Prompt

In Cpp, your task is to solve the following 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 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
const int maxn = 1e5 + 5;
pair<long long, long long> c[maxn];
const long long limit = 1.5 * 1e6;
const long long limit2 = limit * limit;
int ans[maxn];
bool check(long long x, long long y) { return (x * x + y * y) <= limit2; }
long long cal(long long x, long long y) { return x * x + y * y; }
struct node {
  long long x, y;
  node(long long _x, long long _y) : x(_x), y(_y) {}
  node() {}
  bool operator<(const node& b) const { return cal(x, y) < cal(b.x, b.y); }
};
int n;
void out() {
  for (int i = 1; i <= n; i++) {
    printf("%d ", ans[i]);
  }
  puts("");
}
bool work() {
  int times = 1e8;
  times /= n;
  bool flag = false;
  srand(time(NULL));
  for (int k = 0; k < times; k++) {
    long long x = 0, y = 0;
    for (int i = 1; i <= n; i++) {
      42;
      long long tmp1x = x + c[i].first;
      long long tmp1y = y + c[i].second;
      long long tmp2x = x - c[i].first;
      long long tmp2y = y - c[i].second;
      long long tmp1 = tmp1x * tmp1x + tmp1y * tmp1y;
      long long tmp2 = tmp2x * tmp2x + tmp2y * tmp2y;
      if (tmp1 < tmp2) {
        x = tmp1x;
        y = tmp1y;
        ans[i] = 1;
      } else if (tmp1 > tmp2) {
        x = tmp2x;
        y = tmp2y;
        ans[i] = -1;
      } else {
        bool f = rand() % 2;
        if (f) {
          x = tmp1x;
          y = tmp1y;
          ans[i] = 1;
        } else {
          x = tmp2x;
          y = tmp2y;
          ans[i] = -1;
        }
      }
    }
    if (check(x, y)) {
      flag = true;
      break;
    }
  }
  if (flag) {
    out();
  }
  return flag;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%lld %lld", &c[i].first, &c[i].second);
  }
  if (work()) {
    return 0;
  }
  int times = 1e8;
  times /= n;
  srand(time(NULL));
  vector<node> Q, Q2;
  map<pair<pair<long long, long long>, int>, node> M;
  Q.push_back(node(0, 0));
  for (int i = 1; i <= n; i++) {
    Q2.clear();
    for (auto v : Q) {
      long long tmp1x = v.x + c[i].first;
      long long tmp1y = v.y + c[i].second;
      long long tmp2x = v.x - c[i].first;
      long long tmp2y = v.y - c[i].second;
      Q2.push_back(node(tmp1x, tmp1y));
      Q2.push_back(node(tmp2x, tmp2y));
      M[make_pair(make_pair(tmp1x, tmp1y), i)] = v;
      M[make_pair(make_pair(tmp2x, tmp2y), i)] = v;
    }
    Q.clear();
    int sz = 50;
    sort(Q2.begin(), Q2.end());
    for (auto v : Q2) {
      Q.push_back(v);
      sz--;
      if (sz == 0) break;
    }
  }
  auto v = Q.begin();
  int now = n;
  long long nowx = v->x;
  long long nowy = v->y;
  42;
  for (auto v : M) {
    auto tmp1 = v.first;
    auto tmp2 = v.second;
    42;
    42;
  }
  while (now >= 1) {
    node lxt = M[make_pair(make_pair(nowx, nowy), now)];
    if (lxt.x + c[now].first == nowx && lxt.y + c[now].second == nowy) {
      ans[now] = 1;
    } else {
      ans[now] = -1;
    }
    now--;
    nowx = lxt.x;
    nowy = lxt.y;
  }
  for (int i = 1; i <= n; i++) {
    printf("%d ", ans[i]);
  }
  puts("");
  return 0;
}

```