#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long ans = 0;
  bool f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f ^= 1;
    ch = getchar();
  }
  while (isdigit(ch)) ans = (ans << 3) + (ans << 1) + (ch ^ 48), ch = getchar();
  return f ? ans : -ans;
}
struct pot {
  long long x, y;
  long double ang;
  pot(long long _x = 0, long long _y = 0) : x(_x), y(_y) {}
  pot(long long _x, long long _y, long double _ang) : x(_x), y(_y), ang(_ang) {}
  friend inline pot operator+(const pot& a, const pot& b) {
    return pot(a.x + b.x, a.y + b.y);
  }
  friend inline pot operator-(const pot& a, const pot& b) {
    return pot(a.x - b.x, a.y - b.y);
  }
  friend inline long long operator^(const pot& a, const pot& b) {
    return (long long)a.x * b.y - (long long)a.y * b.x;
  }
  friend inline bool operator<(const pot& a, const pot& b) {
    return a.ang < b.ang;
  }
} a[102000];
multiset<pot> S;
long long n;
long long ans = 0;
inline long long Area(const pot& a, const pot& b, const pot& c) {
  return (a - c) ^ (b - c);
}
inline long long labs(const long long& x) { return x > 0 ? x : -x; }
inline pot Pre(const pot& now) {
  if (S.count(now) > 0) {
    set<pot>::iterator it = S.lower_bound(now);
    return *it;
  }
  set<pot>::iterator it = S.lower_bound(now);
  if (it == S.begin()) it = S.end();
  return *(--it);
}
inline pot Suf(const pot& now) {
  set<pot>::iterator it = S.upper_bound(now);
  if (it == S.end()) it = S.begin();
  return *it;
}
inline bool check(const pot& x) { return Area(x, Suf(x), Pre(x)) <= 0; }
inline void insert(const pot& x) {
  auto it = Pre(x);
  it = Suf(x);
  if (check(x)) return;
  ans += labs(Area(x, Suf(x), Pre(x)));
  while (1) {
    pot p1 = Pre(x), p2;
    S.erase(p1);
    p2 = Pre(x);
    if (Area(x, p2, p1) >= 0) {
      S.insert(p1);
      break;
    }
    ans += labs(Area(x, p2, p1));
  }
  while (1) {
    pot p1 = Suf(x), p2;
    S.erase(p1);
    p2 = Suf(x);
    if (Area(x, p2, p1) <= 0) {
      S.insert(p1);
      break;
    }
    ans += labs(Area(p1, p2, x));
  }
  S.insert(x);
}
int op[200000];
signed main() {
  srand(time(NULL));
  long long xxx = rand(), yyy = rand(), zzz = rand(), ttt = xxx + yyy + zzz;
  long double X, Y;
  int n;
  n = read();
  for (int i = 1; i <= n; i++) {
    op[i] = read();
    a[i].x = read();
    a[i].y = read();
  }
  X = (long double)((long long)a[1].x * xxx + (long long)a[2].x * yyy +
                    (long long)a[3].x * zzz) /
      ttt;
  Y = (long double)((long long)a[1].y * xxx + (long long)a[2].y * yyy +
                    (long long)a[3].y * zzz) /
      ttt;
  for (int i = 1; i <= n; i++) {
    if (op[i] == 1) {
      if (S.size() < 3) {
        pot t(a[i].x, a[i].y, atan2(a[i].y - Y, a[i].x - X));
        S.insert(t);
      } else
        insert(pot(a[i].x, a[i].y, atan2(a[i].y - Y, a[i].x - X)));
    } else {
      pot t(a[i].x, a[i].y, atan2(a[i].y - Y, a[i].x - X));
      auto pre = Pre(t);
      auto suf = Suf(t);
      if (((t - suf) ^ (pre - suf)) >= 0) {
        puts("YES");
      } else
        puts("NO");
    }
  }
  return 0;
}

### Prompt

Your task is to create a CPP solution to the following problem:

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;
inline long long read() {
  long long ans = 0;
  bool f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f ^= 1;
    ch = getchar();
  }
  while (isdigit(ch)) ans = (ans << 3) + (ans << 1) + (ch ^ 48), ch = getchar();
  return f ? ans : -ans;
}
struct pot {
  long long x, y;
  long double ang;
  pot(long long _x = 0, long long _y = 0) : x(_x), y(_y) {}
  pot(long long _x, long long _y, long double _ang) : x(_x), y(_y), ang(_ang) {}
  friend inline pot operator+(const pot& a, const pot& b) {
    return pot(a.x + b.x, a.y + b.y);
  }
  friend inline pot operator-(const pot& a, const pot& b) {
    return pot(a.x - b.x, a.y - b.y);
  }
  friend inline long long operator^(const pot& a, const pot& b) {
    return (long long)a.x * b.y - (long long)a.y * b.x;
  }
  friend inline bool operator<(const pot& a, const pot& b) {
    return a.ang < b.ang;
  }
} a[102000];
multiset<pot> S;
long long n;
long long ans = 0;
inline long long Area(const pot& a, const pot& b, const pot& c) {
  return (a - c) ^ (b - c);
}
inline long long labs(const long long& x) { return x > 0 ? x : -x; }
inline pot Pre(const pot& now) {
  if (S.count(now) > 0) {
    set<pot>::iterator it = S.lower_bound(now);
    return *it;
  }
  set<pot>::iterator it = S.lower_bound(now);
  if (it == S.begin()) it = S.end();
  return *(--it);
}
inline pot Suf(const pot& now) {
  set<pot>::iterator it = S.upper_bound(now);
  if (it == S.end()) it = S.begin();
  return *it;
}
inline bool check(const pot& x) { return Area(x, Suf(x), Pre(x)) <= 0; }
inline void insert(const pot& x) {
  auto it = Pre(x);
  it = Suf(x);
  if (check(x)) return;
  ans += labs(Area(x, Suf(x), Pre(x)));
  while (1) {
    pot p1 = Pre(x), p2;
    S.erase(p1);
    p2 = Pre(x);
    if (Area(x, p2, p1) >= 0) {
      S.insert(p1);
      break;
    }
    ans += labs(Area(x, p2, p1));
  }
  while (1) {
    pot p1 = Suf(x), p2;
    S.erase(p1);
    p2 = Suf(x);
    if (Area(x, p2, p1) <= 0) {
      S.insert(p1);
      break;
    }
    ans += labs(Area(p1, p2, x));
  }
  S.insert(x);
}
int op[200000];
signed main() {
  srand(time(NULL));
  long long xxx = rand(), yyy = rand(), zzz = rand(), ttt = xxx + yyy + zzz;
  long double X, Y;
  int n;
  n = read();
  for (int i = 1; i <= n; i++) {
    op[i] = read();
    a[i].x = read();
    a[i].y = read();
  }
  X = (long double)((long long)a[1].x * xxx + (long long)a[2].x * yyy +
                    (long long)a[3].x * zzz) /
      ttt;
  Y = (long double)((long long)a[1].y * xxx + (long long)a[2].y * yyy +
                    (long long)a[3].y * zzz) /
      ttt;
  for (int i = 1; i <= n; i++) {
    if (op[i] == 1) {
      if (S.size() < 3) {
        pot t(a[i].x, a[i].y, atan2(a[i].y - Y, a[i].x - X));
        S.insert(t);
      } else
        insert(pot(a[i].x, a[i].y, atan2(a[i].y - Y, a[i].x - X)));
    } else {
      pot t(a[i].x, a[i].y, atan2(a[i].y - Y, a[i].x - X));
      auto pre = Pre(t);
      auto suf = Suf(t);
      if (((t - suf) ^ (pre - suf)) >= 0) {
        puts("YES");
      } else
        puts("NO");
    }
  }
  return 0;
}

```