Satellites
Contest: Russian Code Cup 2017 - Finals [Unofficial Mirror, Div. 1 Only Recommended, Teams Allowed]
Difficulty rating: 3100

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.

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:

Input format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example output:
NO
YES
YES

Editorial:
Any point X can be given by two angles α = XAB and β = XBA.
The point (α2, β2) is in coverage area of a satellite at the point (α1, β1), if α2 ≤ α1 and β2 ≤ β1.
Let two satellites that want to create a communication channel are at points (α1, β1) and (α2, β2). Repeater must be positioned in such point (α0, β0), that α0 ≤ min(α1, α2) and β0 ≤ min(β1, β2). To make it harder for it to get to other satellites coverage area, it is reasonable to maximize α0 and β0: α0 = min(α1, α2), β0 = min(β1, β2).
Now let us move to a solution. Consider a query of type 3: you are given two satellites at points (α1, β1) and (α2, β2). You must check whether the point (α0, β0) = (min(α1, α2), min(β1, β2)) is not in the coverage area of any other satellite. That means that among all satellites with α ≥ α0 the maximum value of β is smaller than β0.
The solution is offline, it considers all satellites from the test data and just turns them on and off. Sort all satellites by α. Each moment for each satellite we store its β if it exists, or  - ∞ if it doesn't. Let us build a range tree for maximum, and update values as satellites come and go. The query is a range maximum. To avoid considering the satellites from the query, change their values to  - ∞ before the query, and restore them afterwards.
The next thing to do is to get rid of floating point numbers. Instead of calculating the angle values, we will only compare them using cross product. Similarly, instead of storing β values in range tree, we will store indices and compare them by cross product in integers.
The final remark: we need to check that the point (α0, β0) is not inside the planet. The point is inside the planet, if the angle AXB is obtuse, that can be checked by a scalar product of XA and XB. The point X can have non-integer coordinates, so we will not look for it, but will use colinear vectors from among those connecting satellite points to A and B.