Problem: Real Cosmic Communications is the largest telecommunication company on a far far away planet, located at the very edge of the universe. RCC launches communication satellites.

The planet is at the very edge of the universe, so its form is half of a circle. Its radius is r, the ends of its diameter are points A and B. The line AB is the edge of the universe, so one of the half-planes contains nothing, neither the planet, nor RCC satellites, nor anything else. Let us introduce coordinates in the following way: the origin is at the center of AB segment, OX axis coincides with line AB, the planet is completely in y > 0 half-plane.

The satellite can be in any point of the universe, except the planet points. Satellites are never located beyond the edge of the universe, nor on the edge itself — that is, they have coordinate y > 0. Satellite antennas are directed in such way that they cover the angle with the vertex in the satellite, and edges directed to points A and B. Let us call this area the satellite coverage area. 

The picture below shows coordinate system and coverage area of a satellite.

<image>

When RCC was founded there were no satellites around the planet. Since then there have been several events of one of the following types: 

  1. 1 x y — launch the new satellite and put it to the point (x, y). Satellites never move and stay at the point they were launched. Let us assign the number i to the i-th satellite in order of launching, starting from one. 
  2. 2 i — remove satellite number i. 
  3. 3 i j — make an attempt to create a communication channel between satellites i and j. To create a communication channel a repeater is required. It must not be located inside the planet, but can be located at its half-circle border, or above it. Repeater must be in coverage area of both satellites i and j. To avoid signal interference, it must not be located in coverage area of any other satellite. Of course, the repeater must be within the universe, it must have a coordinate y > 0. 



For each attempt to create a communication channel you must find out whether it is possible.

Sample test has the following satellites locations: 

<image>

Input

The first line of input data contains integers r and n — radius of the planet and the number of events (1 ≤ r ≤ 109, 1 ≤ n ≤ 5·105).

Each of the following n lines describe events in the specified format.

Satellite coordinates are integer, the satisfy the following constraints |x| ≤ 109, 0 < y ≤ 109. No two satellites that simultaneously exist can occupy the same point. Distance from each satellite to the center of the planet is strictly greater than r.

It is guaranteed that events of types 2 and 3 only refer to satellites that exist at the moment. For all events of type 3 the inequality i ≠ j is satisfied.

Output

For each event of type 3 print «YES» on a separate line, if it is possible to create a communication channel, or «NO» if it is impossible.

Example

Input

5 8
1 -5 8
1 -4 8
1 -3 8
1 2 7
3 1 3
2 2
3 1 3
3 3 4


Output

NO
YES
YES

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <class T>
void splitstr(const string &s, vector<T> &out) {
  istringstream in(s);
  out.clear();
  copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
static void redirect(int argc, const char **argv) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  if (argc > 1) {
    static filebuf f;
    f.open(argv[1], ios::in);
    cin.rdbuf(&f);
    if (!cin) {
      cerr << "Failed to open '" << argv[1] << "'" << endl;
      exit(1);
    }
  }
  if (argc > 2) {
    static filebuf f;
    f.open(argv[2], ios::out | ios::trunc);
    cout.rdbuf(&f);
    if (!cout) {
      cerr << "Failed to open '" << argv[2] << "'" << endl;
    }
  }
}
static inline long long dot(const std::complex<long long> &a,
                            const std::complex<long long> &b) {
  return real(conj(a) * b);
}
static inline long long cross(const std::complex<long long> &a,
                              const std::complex<long long> &b) {
  return imag(conj(a) * b);
}
static inline long long cross(const std::complex<long long> &a,
                              const std::complex<long long> &b,
                              const std::complex<long long> &c) {
  return cross(b - a, c - a);
}
class CompareAngle {
 private:
  const std::complex<long long> base;

 public:
  explicit CompareAngle(const std::complex<long long> &base) : base(base) {}
  bool operator()(const std::complex<long long> &a,
                  const std::complex<long long> &b) const {
    return cross(base, a, b) > 0;
  }
};
template <typename T, typename Op = std::plus<T>>
class SegTree {
  T identity;
  Op op;
  std::vector<T> nodes;

 public:
  explicit SegTree(std::size_t n = 0, const T &identity = T(),
                   const Op &op = Op())
      : identity(identity), op(op), nodes(2 * n, this->identity) {
    for (int i = n - 1; i > 0; i--)
      nodes[i] = this->op(nodes[2 * i], nodes[2 * i + 1]);
  }
  template <typename Iterator>
  SegTree(Iterator first, Iterator last, const T &identity = T(),
          const Op &op = Op())
      : identity(identity), op(op) {
    std::size_t n = std::distance(first, last);
    nodes.reserve(2 * n);
    nodes.resize(n, this->identity);
    nodes.insert(nodes.end(), first, last);
    for (int i = n - 1; i > 0; i--)
      nodes[i] = this->op(nodes[2 * i], nodes[2 * i + 1]);
  }
  std::size_t size() const { return nodes.size() / 2; }
  void set(std::size_t idx, T value) {
    assert(0 <= idx && idx < size());
    idx += size();
    nodes[idx] = std::move(value);
    while (idx > 0) {
      idx /= 2;
      nodes[idx] = op(nodes[2 * idx], nodes[2 * idx + 1]);
    }
  }
  const T &operator[](std::size_t idx) const {
    assert(0 <= idx && idx < size());
    return nodes[idx + size()];
  }
  T query(std::size_t a, std::size_t b) const {
    assert(0 <= a && a <= size());
    assert(0 <= b && b <= size());
    a += size();
    b += size();
    T left = identity, right = identity;
    while (a < b) {
      if (a & 1) left = op(left, nodes[a++]);
      if (b & 1) right = op(nodes[--b], right);
      a /= 2;
      b /= 2;
    }
    return op(left, right);
  }
};
struct opmin {
  pair<int, int> operator()(const pair<int, int> &a,
                            const pair<int, int> &b) const {
    return min(a, b);
  }
};
struct event {
  int t;
  int x, y;
};
static bool cut_within(const std::complex<long long> &a,
                       const std::complex<long long> &p,
                       const std::complex<long long> &b,
                       const std::complex<long long> &q) {
  std::complex<long long> dp = p - a;
  std::complex<long long> dq = q - b;
  return dot(dp, dq) < 0;
}
int main(int argc, const char **argv) {
  redirect(argc, argv);
  long long R, N;
  cin >> R >> N;
  vector<event> events;
  vector<std::complex<long long>> pnts;
  for (int i = 0; i < N; i++) {
    int t;
    cin >> t;
    if (t == 1) {
      int x, y;
      cin >> x >> y;
      events.push_back(event{1, ((int)(pnts).size()), -1});
      pnts.emplace_back(x, y);
    } else if (t == 2) {
      int idx;
      cin >> idx;
      idx--;
      events.push_back(event{2, idx, -1});
    } else {
      int a, b;
      cin >> a >> b;
      events.push_back(event{3, a - 1, b - 1});
    }
  }
  std::complex<long long> A(-R, 0);
  std::complex<long long> B(R, 0);
  int P = ((int)(pnts).size());
  vector<int> byA(P);
  for (int i = 0; i < P; i++) byA[i] = i;
  auto byB = byA;
  CompareAngle cmpA(A);
  CompareAngle cmpB(B);
  sort(begin(byA), end(byA),
       [&](int a, int b) { return cmpA(pnts[b], pnts[a]); });
  sort(begin(byB), end(byB),
       [&](int a, int b) { return cmpB(pnts[a], pnts[b]); });
  vector<pair<int, int>> rank(P);
  rank[byA[0]].first = 0;
  int nxt = 0;
  for (int i = 1; i < P; i++) {
    if (cmpA(pnts[byA[i]], pnts[byA[i - 1]])) nxt++;
    rank[byA[i]].first = nxt;
  }
  int NA = nxt + 1;
  rank[byB[0]].second = 0;
  nxt = 0;
  for (int i = 1; i < P; i++) {
    if (cmpB(pnts[byB[i - 1]], pnts[byB[i]])) nxt++;
    rank[byB[i]].second = nxt;
  }
  vector<set<pair<int, int>>> line(NA);
  for (int i = 0; i < NA; i++) line[i].emplace(INT_MAX, INT_MAX);
  auto get_sample = [&](int row) { return *line[row].begin(); };
  SegTree<pair<int, int>, opmin> seg(NA, get_sample(0));
  auto add = [&](int idx) {
    auto r = rank[idx];
    line[r.first].emplace(r.second, idx);
    seg.set(r.first, get_sample(r.first));
  };
  auto remove = [&](int idx) {
    auto r = rank[idx];
    line[r.first].erase(line[r.first].find(make_pair(r.second, idx)));
    seg.set(r.first, get_sample(r.first));
  };
  for (const event &ev : events) {
    if (ev.t == 1)
      add(ev.x);
    else if (ev.t == 2)
      remove(ev.x);
    else {
      std::complex<long long> p =
          cross(A, pnts[ev.x], pnts[ev.y]) >= 0 ? pnts[ev.x] : pnts[ev.y];
      std::complex<long long> q =
          cross(B, pnts[ev.x], pnts[ev.y]) >= 0 ? pnts[ev.y] : pnts[ev.x];
      bool good = true;
      if (cut_within(A, p, B, q))
        good = false;
      else {
        int ar = max(rank[ev.x].first, rank[ev.y].first);
        int br = max(rank[ev.x].second, rank[ev.y].second);
        remove(ev.x);
        remove(ev.y);
        pair<int, int> samp = seg.query(0, ar + 1);
        if (samp.first <= br) good = false;
        add(ev.x);
        add(ev.y);
      }
      cout << (good ? "YES\n" : "NO\n");
    }
  }
  return 0;
}