#include <bits/stdc++.h>
using namespace std;
char string_in_buffer[(int)260];
void fast_scan(int &first) { scanf("%d", &first); }
void fast_scan(long long &first) { scanf("%lld", &first); }
void fast_scan(unsigned long long &first) { scanf("%llu", &first); }
void fast_scan(double &first) { scanf("%lf", &first); }
void fast_scan(long double &first) { scanf("%Lf", &first); }
void fast_scan(char &first) {
  scanf("%c", &first);
  if (first == '\n') {
    fast_scan(first);
  }
}
void fast_scan(string &first) {
  scanf("%s", string_in_buffer);
  first = string(string_in_buffer);
}
template <class TFirst, class TSecond>
void fast_scan(pair<TFirst, TSecond> &p) {
  fast_scan(p.first);
  fast_scan(p.second);
}
template <class T>
void fast_scan(vector<T> &v) {
  for (auto &first : v) fast_scan(first);
}
void fast_print(const int &first) { printf("%d", first); }
void fast_print(const long long &first) { printf("%lld", first); }
void fast_print(const unsigned long long &first) { printf("%llu", first); }
void fast_print(const double &first) { printf("%.15lf", first); }
void fast_print(const long double &first) { printf("%.15Lf", first); }
void fast_print(const char &first) { printf("%c", first); };
void fast_print(const string &first) { printf("%s", first.c_str()); }
void fast_print(const char v[]) { fast_print((string)v); }
template <class TFirst, class TSecond>
void fast_print(const pair<TFirst, TSecond> &p) {
  fast_print(p.first);
  fast_print(' ');
  fast_print(p.second);
}
template <class T>
void fast_print(const vector<T> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print(' ');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const vector<vector<T>> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print('\n');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const T &v) {
  for (const auto &first : v) {
    fast_print(first);
    fast_print(' ');
  }
}
using namespace std;
namespace smart_io {
string print_start = "";
string sep = " ";
bool first_print = false;
void precall_print() {
  fast_print(print_start);
  print_start = "\n";
  first_print = true;
}
void _print(deque<string>) {}
template <class T, class... Args>
void _print(deque<string> names, T kek, Args... args) {
  if (!first_print) {
    fast_print("\n");
  } else {
    first_print = false;
  }
  fast_print(names.front());
  fast_print(" = ");
  fast_print(kek);
  names.pop_front();
  _print(names, args...);
}
}  // namespace smart_io
template <class T>
ostream &operator,(ostream &os, const T &object) {
  if (!smart_io::first_print) {
    fast_print(smart_io::sep);
  } else {
    smart_io::first_print = false;
  }
  fast_print(object);
  return os;
}
template <class T>
istream &operator,(istream &is, T &object) {
  fast_scan(object);
  return is;
}
namespace typedefs {}
namespace numbers_operation {
template <class T>
T floor_mod(T a, T b) {
  if (a % b == 0) return 0;
  if (a >= 0 && b >= 0) return a % b;
  if (a <= 0 && b <= 0) return a % b;
  return abs(b) - (abs(a) % abs(b));
}
}  // namespace numbers_operation
using namespace numbers_operation;
using namespace typedefs;
int n;
vector<pair<long double, long double>> v;
long double angle(pair<long double, long double> a,
                  pair<long double, long double> b) {
  if (hypot(a.first, a.second) == 0) return 0;
  if (hypot(b.first, b.second) == 0) return 0;
  long double prod = a.first * b.first + a.second * b.second;
  long double ang =
      acos(prod / hypot(a.first, a.second) / hypot(b.first, b.second));
  while (ang < 0) {
    ang +=
        2 *
        (long double)3.141592653589793238462643383279502884197169399375105820974;
  }
  while (
      ang >
      2 * (long double)3.141592653589793238462643383279502884197169399375105820974) {
    ang -=
        2 *
        (long double)3.141592653589793238462643383279502884197169399375105820974;
  }
  ang = min(
      ang,
      2 * (long double)3.141592653589793238462643383279502884197169399375105820974 -
          ang);
  if (isnan(ang)) {
    return 0;
  }
  return ang;
}
pair<long double, long double> operator+(pair<long double, long double> a,
                                         pair<long double, long double> b) {
  return make_pair(a.first + b.first, a.second + b.second);
}
pair<long double, long double> operator-(pair<long double, long double> a,
                                         pair<long double, long double> b) {
  return make_pair(a.first - b.first, a.second - b.second);
}
pair<long double, long double> operator*(pair<long double, long double> p,
                                         long double d) {
  return make_pair(p.first * d, p.second * d);
}
long double length(pair<long double, long double> vec) {
  return hypot(vec.second, vec.first);
}
vector<int> final;
struct Vec {
  Vec *a = NULL, *b = NULL;
  bool inv = false;
  int id = -1;
  pair<long double, long double> cur;
  Vec() {}
  Vec(pair<long double, long double> _cur, int _id) {
    cur = _cur;
    id = _id;
  }
  friend Vec *merge(Vec *a, Vec *b) {
    Vec *rez = new Vec();
    rez->inv = false;
    rez->cur = a->cur + b->cur;
    rez->a = a;
    rez->b = b;
    return rez;
  }
  void invert() {
    cur.first *= -1;
    cur.second *= -1;
    inv ^= 1;
  }
  void finalize(bool par) {
    par ^= inv;
    if (!a) {
      final[id] = par ? -1 : 1;
    } else {
      a->finalize(par);
      b->finalize(par);
    }
  }
};
vector<Vec *> buf;
void splace() {
  int _a = -1;
  int _b = -1;
  long double _min = 1e18;
  for (int j = 0; j < ((int)buf.size()); j++) {
    for (int k = j + 1; k < ((int)buf.size()); k++) {
      long double ang = angle(buf[j]->cur, buf[k]->cur);
      if (_min > ang) {
        _min = ang;
        _a = j;
        _b = k;
      }
    }
  }
  if (length(buf[_a]->cur + buf[_b]->cur) >
      length(buf[_a]->cur - buf[_b]->cur)) {
    buf[_b]->invert();
  }
  Vec *rez = merge(buf[_a], buf[_b]);
  buf.erase(buf.begin() + _b);
  buf.erase(buf.begin() + _a);
  buf.push_back(rez);
}
signed main(signed argc, char *argv[]) {
  cin, n;
  v.resize(n);
  cin, v;
  for (int i = 0; i < (n); i++) {
    buf.push_back(new Vec(v[i], i));
    if (((int)buf.size()) > 8) {
      splace();
    }
  }
  while (((int)buf.size()) > 1) {
    splace();
  }
  final.resize(n, -2);
  buf[0]->finalize(0);
  smart_io::precall_print();
  cout, final;
}

### Prompt

Please create a solution in CPP to 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;
char string_in_buffer[(int)260];
void fast_scan(int &first) { scanf("%d", &first); }
void fast_scan(long long &first) { scanf("%lld", &first); }
void fast_scan(unsigned long long &first) { scanf("%llu", &first); }
void fast_scan(double &first) { scanf("%lf", &first); }
void fast_scan(long double &first) { scanf("%Lf", &first); }
void fast_scan(char &first) {
  scanf("%c", &first);
  if (first == '\n') {
    fast_scan(first);
  }
}
void fast_scan(string &first) {
  scanf("%s", string_in_buffer);
  first = string(string_in_buffer);
}
template <class TFirst, class TSecond>
void fast_scan(pair<TFirst, TSecond> &p) {
  fast_scan(p.first);
  fast_scan(p.second);
}
template <class T>
void fast_scan(vector<T> &v) {
  for (auto &first : v) fast_scan(first);
}
void fast_print(const int &first) { printf("%d", first); }
void fast_print(const long long &first) { printf("%lld", first); }
void fast_print(const unsigned long long &first) { printf("%llu", first); }
void fast_print(const double &first) { printf("%.15lf", first); }
void fast_print(const long double &first) { printf("%.15Lf", first); }
void fast_print(const char &first) { printf("%c", first); };
void fast_print(const string &first) { printf("%s", first.c_str()); }
void fast_print(const char v[]) { fast_print((string)v); }
template <class TFirst, class TSecond>
void fast_print(const pair<TFirst, TSecond> &p) {
  fast_print(p.first);
  fast_print(' ');
  fast_print(p.second);
}
template <class T>
void fast_print(const vector<T> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print(' ');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const vector<vector<T>> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print('\n');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const T &v) {
  for (const auto &first : v) {
    fast_print(first);
    fast_print(' ');
  }
}
using namespace std;
namespace smart_io {
string print_start = "";
string sep = " ";
bool first_print = false;
void precall_print() {
  fast_print(print_start);
  print_start = "\n";
  first_print = true;
}
void _print(deque<string>) {}
template <class T, class... Args>
void _print(deque<string> names, T kek, Args... args) {
  if (!first_print) {
    fast_print("\n");
  } else {
    first_print = false;
  }
  fast_print(names.front());
  fast_print(" = ");
  fast_print(kek);
  names.pop_front();
  _print(names, args...);
}
}  // namespace smart_io
template <class T>
ostream &operator,(ostream &os, const T &object) {
  if (!smart_io::first_print) {
    fast_print(smart_io::sep);
  } else {
    smart_io::first_print = false;
  }
  fast_print(object);
  return os;
}
template <class T>
istream &operator,(istream &is, T &object) {
  fast_scan(object);
  return is;
}
namespace typedefs {}
namespace numbers_operation {
template <class T>
T floor_mod(T a, T b) {
  if (a % b == 0) return 0;
  if (a >= 0 && b >= 0) return a % b;
  if (a <= 0 && b <= 0) return a % b;
  return abs(b) - (abs(a) % abs(b));
}
}  // namespace numbers_operation
using namespace numbers_operation;
using namespace typedefs;
int n;
vector<pair<long double, long double>> v;
long double angle(pair<long double, long double> a,
                  pair<long double, long double> b) {
  if (hypot(a.first, a.second) == 0) return 0;
  if (hypot(b.first, b.second) == 0) return 0;
  long double prod = a.first * b.first + a.second * b.second;
  long double ang =
      acos(prod / hypot(a.first, a.second) / hypot(b.first, b.second));
  while (ang < 0) {
    ang +=
        2 *
        (long double)3.141592653589793238462643383279502884197169399375105820974;
  }
  while (
      ang >
      2 * (long double)3.141592653589793238462643383279502884197169399375105820974) {
    ang -=
        2 *
        (long double)3.141592653589793238462643383279502884197169399375105820974;
  }
  ang = min(
      ang,
      2 * (long double)3.141592653589793238462643383279502884197169399375105820974 -
          ang);
  if (isnan(ang)) {
    return 0;
  }
  return ang;
}
pair<long double, long double> operator+(pair<long double, long double> a,
                                         pair<long double, long double> b) {
  return make_pair(a.first + b.first, a.second + b.second);
}
pair<long double, long double> operator-(pair<long double, long double> a,
                                         pair<long double, long double> b) {
  return make_pair(a.first - b.first, a.second - b.second);
}
pair<long double, long double> operator*(pair<long double, long double> p,
                                         long double d) {
  return make_pair(p.first * d, p.second * d);
}
long double length(pair<long double, long double> vec) {
  return hypot(vec.second, vec.first);
}
vector<int> final;
struct Vec {
  Vec *a = NULL, *b = NULL;
  bool inv = false;
  int id = -1;
  pair<long double, long double> cur;
  Vec() {}
  Vec(pair<long double, long double> _cur, int _id) {
    cur = _cur;
    id = _id;
  }
  friend Vec *merge(Vec *a, Vec *b) {
    Vec *rez = new Vec();
    rez->inv = false;
    rez->cur = a->cur + b->cur;
    rez->a = a;
    rez->b = b;
    return rez;
  }
  void invert() {
    cur.first *= -1;
    cur.second *= -1;
    inv ^= 1;
  }
  void finalize(bool par) {
    par ^= inv;
    if (!a) {
      final[id] = par ? -1 : 1;
    } else {
      a->finalize(par);
      b->finalize(par);
    }
  }
};
vector<Vec *> buf;
void splace() {
  int _a = -1;
  int _b = -1;
  long double _min = 1e18;
  for (int j = 0; j < ((int)buf.size()); j++) {
    for (int k = j + 1; k < ((int)buf.size()); k++) {
      long double ang = angle(buf[j]->cur, buf[k]->cur);
      if (_min > ang) {
        _min = ang;
        _a = j;
        _b = k;
      }
    }
  }
  if (length(buf[_a]->cur + buf[_b]->cur) >
      length(buf[_a]->cur - buf[_b]->cur)) {
    buf[_b]->invert();
  }
  Vec *rez = merge(buf[_a], buf[_b]);
  buf.erase(buf.begin() + _b);
  buf.erase(buf.begin() + _a);
  buf.push_back(rez);
}
signed main(signed argc, char *argv[]) {
  cin, n;
  v.resize(n);
  cin, v;
  for (int i = 0; i < (n); i++) {
    buf.push_back(new Vec(v[i], i));
    if (((int)buf.size()) > 8) {
      splace();
    }
  }
  while (((int)buf.size()) > 1) {
    splace();
  }
  final.resize(n, -2);
  buf[0]->finalize(0);
  smart_io::precall_print();
  cout, final;
}

```