Real Cosmic Communications 是一个遥远星球上最大的电信公司,位于宇宙的最边缘。 RCC 发射通信卫星。
这颗行星位于宇宙的最边缘,因此它的形状是半个圆形。它的半径是r,其直径的两端是点A和B。线AB是宇宙的边缘,因此其中一个半平面不包含任何东西,既没有行星,也没有RCC卫星,也没有其他任何东西。我们这样介绍坐标:原点位于AB线段的中心,OX轴与AB线重合,行星完全在y>0半平面内。
卫星可以位于宇宙的任何一点,除了行星点。卫星永远不会位于宇宙边缘之外,也不位于边缘本身,也就是说,它们的坐标 y > 0。卫星天线的方向是覆盖与卫星顶点的角度,边缘指向 A 点和 B 点。我们将此区域称为卫星覆盖区域。
下图显示了卫星的坐标系和覆盖区域。
RCC 成立时,地球上还没有卫星。自那时起,发生了若干属于以下类型之一的事件:
1. 1 x y — 发射新卫星并将其放置到点 (x, y)。卫星永远不会移动并停留在发射点。让我们按照发射顺序将编号 i 分配给第 i 颗卫星,从一颗开始。
2. 2 i — 删除卫星号 i。
3. 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”。
示例
输入 #1
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
输出 #1
NO YES YES