Satellites

Time limit4sMemory limit512 MB

Summary
Satellites appear and disappear above a half-disc planet; for each query decide whether two satellites have a common coverage point outside the planet that no other live satellite covers.
Level

Hard9 of 10

Topics
Geometry, Dynamic programming, Implementation, Brute force
Solved
No attempts yet

Problem

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

The planet sits at the very edge of the universe, so its shape is half of a circle. Its radius is r, and 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: no planet, no RCC satellites, nothing else. We introduce coordinates as follows: the origin is at the midpoint of segment AB, the OX axis coincides with line AB, and the planet lies entirely in the half-plane y > 0.

A satellite can be at any point of the universe except points of the planet. Satellites are never beyond the edge of the universe nor on the edge itself, that is, they have coordinate y > 0. Satellite antennas are directed so that they cover the angle whose vertex is at the satellite and whose sides point toward A and B. We call this area the satellite coverage area.

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

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

  1. 1 x y: launch a new satellite and put it at point (x, y). Satellites never move and stay at the point where they were launched. We number the i-th satellite i in order of launching, starting from one.
  2. 2 i: remove satellite number i.
  3. 3 i j: attempt to create a communication channel between satellites i and j. Creating a communication channel requires a repeater. It must not be inside the planet, but it may be on the planet's half-circle border or above it. The repeater must be in the coverage area of both satellites i and j. To avoid signal interference, it must not be in the coverage area of any other satellite. Of course, the repeater must be within the universe, so it must have coordinate y > 0.

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

The sample test has the following satellite locations.

Input

The first line of the input contains integers r and n, the radius of the planet and the number of events (1 ≤ r ≤ 10^9, 1 ≤ n ≤ 5·10^5).

Each of the following n lines describes an event in the specified format.

Satellite coordinates are integers satisfying |x| ≤ 10^9, 0 < y ≤ 10^9. No two satellites that exist simultaneously can occupy the same point. The distance from each satellite to the center of the planet is strictly greater than r.

Events of types 2 and 3 refer only to satellites that exist at that moment. For all events of type 3 the inequality i ≠ j holds.

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.

Examples1

  1. Example 1

    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
    Expected output
    NO
YES
YES