Real Cosmic Communications — самая крупная телекоммуникационная компания на далёкой планете на самом краю Вселенной. Основное направление деятельности RCC — запуск спутников связи.
Поскольку планета находится на краю Вселенной, она имеет форму полукруга. Его радиус равен r, концы диаметра — A и B. Прямая AB — это край Вселенной, поэтому в нижней полуплоскости нет ни планеты, ни спутников компании RCC, ни чего бы то ни было ещё. Введём систему координат следующим образом: начало отсчёта — в середине отрезка AB, ось OX совпадает с прямой AB, планета лежит в полуплоскости y > 0.
Спутник связи может находиться в любой точке Вселенной, кроме точек планеты. Спутник не находится за краем вселенной или на ее границе, то есть имеет координату y > 0. Антенны спутника направлены таким образом, что для связи ему доступен угол с вершиной в спутнике и сторонами, которые проходят через точки A и B. Будем называть эту область зоной покрытия спутника. Границы этой области тоже принадлежат зоне покрытия.
На рисунке показана система координат и зона покрытия одного спутника.
В момент основания RCC около планеты не было ни одного их спутника. С тех пор происходили события следующих типов:
- 1 x y — запустить новый спутник и поместить его в точку с координатами (x, y). Спутники компании RCC никуда не двигаются и остаются на месте, пока их не уберут. Спутник, запущенный i-м, получает номер i, нумерация с единицы.
- 2 i — убрать спутник номер i.
- 3 i j — попытаться установить связь между спутниками i и j. Для этого необходимо установить ретранслятор. Он не может располагаться внутри планеты, но может быть на поверхности или висеть над ней. Ретранслятор должен находиться в зоне покрытия спутников i и j. Кроме того, чтобы не создавать помех, он не должен находиться в зоне покрытия никакого другого спутника. Разумеется, ретранслятор должен находиться внутри вселенной, то есть иметь координату y > 0.
Для каждой попытки установить связь требуется определить, возможно ли это сделать.
В примере входных данных расположение спутников следующее:
В первой строке входных данных заданы целые числа r и n — радиус планеты и количество событий (1 ≤ r ≤ 109, 1 ≤ n ≤ 5·105).
В следующих n строках заданы события в приведённом выше формате.
Координаты спутников целые и удовлетворяют ограничениям |x| ≤ 109, 0 < y ≤ 109. Два спутника не могут одновременно находиться в одной точке. Расстояние от спутника до центра планеты строго больше r.
Гарантируется, что в событиях типа 2 и 3 спутники, которые в них задействованы, на момент события существуют. В событиях типа 3 выполнено i ≠ j.
Для каждого события типа 3 выведите в отдельной строке «YES», если возможно установить связь, и «NO» в противном случае.
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
NO
YES
YES
