P12065 [THOI 2012] 森林旅店

搬运自 [2012 年清华大学信息学邀请赛](https://gitlink.org.cn/thusaa/thoi2012)。

小 H 家旁边的树林可是一年四季度假的好地方。为了整合资源扩大效益，小 H 打算在树林中建立一些“泰山的小屋”，即在一些树木上建造一些小屋，让大家更加近距离地体会自然的美。 不过有一个问题一直困扰着小 H 的计划，那就是森林中白蚁泛滥。大家都知道白蚁对于树木和木制品的危害，如果建造的房子周围白蚁成灾，那无疑就是将游客的人身安全置于一个危险的境地中了。因此小 H 在建造小屋的时候必须更加合理地考量房子的安全性。 简而言之，我们可以认为森林里有许多的树木，其中有 $N$ 个白蚁穴在这些树木上。在同一棵树上最多只有一个白蚁穴。 小 H 想知道，如果他希望在某棵树上建立一座小屋，那么周围离它最近的 $P$ 个白蚁穴的距离分别是多少呢？ 同时由于随时可能发现新的白蚁穴，你的程序还应该支持动态地加入新发现的蚁穴。

第一行包含四个整数 $N,Q,K$ 和 $P$。$N$ 为初始时的白蚁穴数量，$Q$ 是操作数量，$K$ 是距离度量函数的参数，$P$ 为每次查询要输出的蚁穴个数。 对于坐标位置为 $(X_1,X_2)$ 和 $(Y_1,Y_2)$ 的距离，我们定义为： $$(|X_1-X_2|^K+|Y_1-Y_2|^K)^{\frac{1}{K}}$$ 接下来 $N$ 行，每行两个整数，表示初始时白蚁穴的坐标。 再接下来 $Q$ 行，每行有一个字符 $C$ 和两个整数 $X$ 和 $Y$。字符 $C$ 是 `A` 表示加入一个坐标为 $(X,Y)$ 的白蚁穴，`Q` 表示询问如果在 $(X,Y)$ 建造一个小屋，请告知周边的蚁穴情况。

对于每组询问，输出 $P$ 个实数，以单个空格隔开，表示距离最近的 $P$ 个蚁穴的距离，按照升序排序，精确到小数点后 $4$ 位。

本题的测试数据均以以下方式生成。 假设所有出现的蚁穴是：$\{(X_i,Y_i)\}$，$1\le i\le M$。设函数 $f(x),g(x)$ 是两个单调函数。数据生成方法如下： - 生成 $M$ 个随机点 $(x_i,y_i)$，满足 $0\le x_i,y_i\le 1$； - 最终输入数据为 $X_i=f(x_i),Y_i=g(y_i)$，且满足 $0\le X_i,Y_i\le10^7$。 测试数据共分 $10$ 组，每组包括 $5$ 个测试点，共 $50$ 个测试点。同一组的 $5$ 个测试数据的蚁穴的初始位置由同一组随机点经不同的函数变换产生。  表中所有数据均为数据上界。 每组测试点集合中 $40\%$ 的数据不包含插入操作。 所有数据中查询次数不超过 $5000$ 次。