2017 历史的进程 Week 5:「一场」测验赛

F. Wi-Fi

单点时限: 2.0 sec

内存限制: 256 MB

这又是一个 Wi-Fi 问题。然后你又要说,Wi-Fi 问题不就是装点路由器,算算覆盖面积,之类的吗?

确实如此。

我们要在一个 xOy 平面上进行路由器的安装和拆卸工作。有三种操作(前面是操作的格式,后面是操作的含义):

  • 1 A X Y 在 $(X,Y)$ 处增加一个编号为 $A$ 的路由器($A$ 是唯一的,同一个位置可能有多个路由器);
  • 2 A 移除编号为 $A$ 的路由器(保证该路由器当前是存在的);
  • 3 查询距 $(0,0)$ 欧氏距离最近的路由器的编号(如果有多个,输出编号最小的那个)。

注:两点间的欧氏距离定义为 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$。

同一个路由器可能被安装和拆卸多次,但不会在拆卸之前就被重新安装。

输入格式

第一行是一个整数 $Q$ $(1 \leq Q \leq 3 \cdot 10^5)$,表示操作个数。

接下来 $Q$ 行,每行一个操作,操作格式是题述的三种。其中 $A$ 是整数,$1 \leq A \leq 10^9$,$X, Y$ 是整数,$-10^9 \leq X, Y \leq 10^9$。

输出格式

对于每个以 3 开头的查询,输出一个整数,表示距离最近的路由器的编号。输入保证对于每次这样的查询,一定有答案。

样例

Input
9
1 2 1 1
1 1 1 1
3
1 3 1 2
2 1
3
1 1 -1 1
1 5 0 0
3
Output
1
2
5