HKBU ICPC Seminar 4-6

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) 欧氏距离最近的路由器的编号(如果有多个,输出编号最小的那个)。

注:两点间的欧氏距离定义为 (x1x2)2+(y1y2)2

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

输入格式

第一行是一个整数 Q (1Q3105),表示操作个数。

接下来 Q 行,每行一个操作,操作格式是题述的三种。其中 A 是整数,1A109X,Y 是整数,109X,Y109

输出格式

对于每个以 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