#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int cansel_sync = (ios::sync_with_stdio(0), cin.tie(0), 0);
const int N = 200010;
const int inf = ~0u >> 2;
const long long INF = ~0ull >> 2;
long long read() {
  long long x;
  if (scanf("%lld", &x) == -1) exit(0);
  return x;
}
const double pi = acos(-1.0);
double readf() {
  double x;
  if (scanf("%lf", &x) == -1) exit(0);
  return x;
}
template <typename T>
void operator<<(vector<T> &a, T b) {
  a.push_back(b);
}
const long long mod = (1 ? 1000000007 : 998244353);
long long mul(long long a, long long b, long long m = mod) { return a * b % m; }
long long qpow(long long a, long long b, long long m = mod) {
  long long ans = 1;
  for (; b; a = mul(a, a, m), b >>= 1)
    if (b & 1) ans = mul(ans, a, m);
  return ans;
}
struct vec {
  double x, y;
  vec() {}
  vec(double x, double y) : x(x), y(y) {}
  vec operator-(const vec &b) { return vec(x - b.x, y - b.y); }
  vec operator+(const vec &b) { return vec(x + b.x, y + b.y); }
  vec operator*(double k) { return vec(k * x, k * y); }
  double len() { return hypot(x, y); }
  double sqr() { return x * x + y * y; }
  vec trunc(double k = 1) { return *this * (k / len()); }
  vec rotate(double th) {
    double c = cos(th), s = sin(th);
    return vec(x * c - y * s, x * s + y * c);
  }
  vec left() { return vec(-y, x).trunc(); }
  double theta() { return atan2(y, x); }
  friend double cross(vec a, vec b) { return a.x * b.y - a.y * b.x; };
  friend double cross(vec a, vec b, vec c) { return cross(a - c, b - c); }
  friend double dot(vec a, vec b) { return a.x * b.x + a.y * b.y; }
  friend vec trans(vec p, vec a, vec b) {
    swap(a.y, b.x);
    return vec(dot(a, p), dot(b, p));
  }
  friend vec arctrans(vec p, vec a, vec b) {
    double t = cross(a, b);
    return vec(-cross(b, p) / t, cross(a, p) / t);
  }
  void output() const { printf("%.12f %.12f\n", x, y); }
  bool operator<(vec b) const { return 0; }
};
multiset<pair<double, vec>> st;
vec c;
void push(vec v) { st.insert({v.theta(), v}); }
multiset<pair<double, vec>>::iterator find(vec v) {
  auto p = st.lower_bound({v.theta(), v});
  {
    if (p == st.begin()) p = st.end();
    --p;
  };
  return p;
}
const double eps = 1e-7;
bool out(vec v) {
  auto l = find(v), r = l;
  {
    ++r;
    if (r == st.end()) r = st.begin();
  };
  return cross(l->second, r->second, v) < -eps;
}
void Solve() {
  long long q = read();
  q -= 3;
  {
    long long x, y;
    read(), x = read(), y = read();
    vec v1(x, y);
    read(), x = read(), y = read();
    vec v2(x, y);
    read(), x = read(), y = read();
    vec v3(x, y);
    c = (v1 + v2 + v3) * (1.0 / 3);
    push(v1 - c);
    push(v2 - c);
    push(v3 - c);
  }
  while (q--) {
    long long op = read(), x = read(), y = read();
    vec v(x, y);
    v = v - c;
    if (op == 1) {
      if (!out(v)) continue;
      auto l = find(v), r = l;
      {
        ++r;
        if (r == st.end()) r = st.begin();
      };
      auto l2 = l;
      {
        if (l2 == st.begin()) l2 = st.end();
        --l2;
      };
      while (cross(l->second, l2->second, v) > 0) {
        {
          if (l == st.begin()) l = st.end();
          --l;
        };
        {
          if (l2 == st.begin()) l2 = st.end();
          --l2;
        };
      }
      auto r2 = r;
      {
        ++r2;
        if (r2 == st.end()) r2 = st.begin();
      };
      while (cross(r->second, r2->second, v) < 0) {
        {
          ++r;
          if (r == st.end()) r = st.begin();
        };
        {
          ++r2;
          if (r2 == st.end()) r2 = st.begin();
        };
      }
      {
        ++l;
        if (l == st.end()) l = st.begin();
      };
      if (*l <= *r)
        st.erase(l, r);
      else
        st.erase(l, st.end()), st.erase(st.begin(), r);
      st.insert({v.theta(), v});
    } else {
      cout << (!out(v) ? "YES" : "NO") << endl;
    }
  }
}
signed main() {
  long long T = 1;
  for (long long ca = (1), _ = (T + 1); ca < _; ca++) {
    Solve();
  }
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

Once a walrus professor Plato asked his programming students to perform the following practical task. 

The students had to implement such a data structure that would support a convex hull on some set of points S. The input to the program had q queries of two types: 

1. Add a point with coordinates (x, y) into the set S. Note that in this case the convex hull of S could have changed, and could have remained the same. 

2. Say whether a point with coordinates (x, y) belongs to an area limited by the convex hull, including the border. 

All the students coped with the task. What about you?

Input

The first line contains an integer q (4 ≤ q ≤ 105). 

Then follow q lines in the following way: "t x y", where t is the query type (1 or 2), and (x, y) are the coordinates of the point ( - 106 ≤ x, y ≤ 106, x and y are integers). 

There is at least one query of type 2.

It is guaranteed that the three queries of the first type follow first and the points given in the queries form a non-degenerative triangle. Also all the points added in S are distinct.

Output

For each query of the second type print one string containing "YES", if the point lies inside the convex hull or on its border. Otherwise, print "NO".

Examples

Input

8
1 0 0
1 2 0
1 2 2
2 1 0
1 0 2
2 1 1
2 2 1
2 20 -1


Output

YES
YES
YES
NO

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int cansel_sync = (ios::sync_with_stdio(0), cin.tie(0), 0);
const int N = 200010;
const int inf = ~0u >> 2;
const long long INF = ~0ull >> 2;
long long read() {
  long long x;
  if (scanf("%lld", &x) == -1) exit(0);
  return x;
}
const double pi = acos(-1.0);
double readf() {
  double x;
  if (scanf("%lf", &x) == -1) exit(0);
  return x;
}
template <typename T>
void operator<<(vector<T> &a, T b) {
  a.push_back(b);
}
const long long mod = (1 ? 1000000007 : 998244353);
long long mul(long long a, long long b, long long m = mod) { return a * b % m; }
long long qpow(long long a, long long b, long long m = mod) {
  long long ans = 1;
  for (; b; a = mul(a, a, m), b >>= 1)
    if (b & 1) ans = mul(ans, a, m);
  return ans;
}
struct vec {
  double x, y;
  vec() {}
  vec(double x, double y) : x(x), y(y) {}
  vec operator-(const vec &b) { return vec(x - b.x, y - b.y); }
  vec operator+(const vec &b) { return vec(x + b.x, y + b.y); }
  vec operator*(double k) { return vec(k * x, k * y); }
  double len() { return hypot(x, y); }
  double sqr() { return x * x + y * y; }
  vec trunc(double k = 1) { return *this * (k / len()); }
  vec rotate(double th) {
    double c = cos(th), s = sin(th);
    return vec(x * c - y * s, x * s + y * c);
  }
  vec left() { return vec(-y, x).trunc(); }
  double theta() { return atan2(y, x); }
  friend double cross(vec a, vec b) { return a.x * b.y - a.y * b.x; };
  friend double cross(vec a, vec b, vec c) { return cross(a - c, b - c); }
  friend double dot(vec a, vec b) { return a.x * b.x + a.y * b.y; }
  friend vec trans(vec p, vec a, vec b) {
    swap(a.y, b.x);
    return vec(dot(a, p), dot(b, p));
  }
  friend vec arctrans(vec p, vec a, vec b) {
    double t = cross(a, b);
    return vec(-cross(b, p) / t, cross(a, p) / t);
  }
  void output() const { printf("%.12f %.12f\n", x, y); }
  bool operator<(vec b) const { return 0; }
};
multiset<pair<double, vec>> st;
vec c;
void push(vec v) { st.insert({v.theta(), v}); }
multiset<pair<double, vec>>::iterator find(vec v) {
  auto p = st.lower_bound({v.theta(), v});
  {
    if (p == st.begin()) p = st.end();
    --p;
  };
  return p;
}
const double eps = 1e-7;
bool out(vec v) {
  auto l = find(v), r = l;
  {
    ++r;
    if (r == st.end()) r = st.begin();
  };
  return cross(l->second, r->second, v) < -eps;
}
void Solve() {
  long long q = read();
  q -= 3;
  {
    long long x, y;
    read(), x = read(), y = read();
    vec v1(x, y);
    read(), x = read(), y = read();
    vec v2(x, y);
    read(), x = read(), y = read();
    vec v3(x, y);
    c = (v1 + v2 + v3) * (1.0 / 3);
    push(v1 - c);
    push(v2 - c);
    push(v3 - c);
  }
  while (q--) {
    long long op = read(), x = read(), y = read();
    vec v(x, y);
    v = v - c;
    if (op == 1) {
      if (!out(v)) continue;
      auto l = find(v), r = l;
      {
        ++r;
        if (r == st.end()) r = st.begin();
      };
      auto l2 = l;
      {
        if (l2 == st.begin()) l2 = st.end();
        --l2;
      };
      while (cross(l->second, l2->second, v) > 0) {
        {
          if (l == st.begin()) l = st.end();
          --l;
        };
        {
          if (l2 == st.begin()) l2 = st.end();
          --l2;
        };
      }
      auto r2 = r;
      {
        ++r2;
        if (r2 == st.end()) r2 = st.begin();
      };
      while (cross(r->second, r2->second, v) < 0) {
        {
          ++r;
          if (r == st.end()) r = st.begin();
        };
        {
          ++r2;
          if (r2 == st.end()) r2 = st.begin();
        };
      }
      {
        ++l;
        if (l == st.end()) l = st.begin();
      };
      if (*l <= *r)
        st.erase(l, r);
      else
        st.erase(l, st.end()), st.erase(st.begin(), r);
      st.insert({v.theta(), v});
    } else {
      cout << (!out(v) ? "YES" : "NO") << endl;
    }
  }
}
signed main() {
  long long T = 1;
  for (long long ca = (1), _ = (T + 1); ca < _; ca++) {
    Solve();
  }
  return 0;
}

```