题目描述

很久以前，Han 曾是一个繁荣的王国。后来瘟疫和蛮族入侵摧毁了王国中的道路，只留下了一些彼此孤立的要塞。多年之后，人们终于开始重建王国，而第一件事就是重新修建道路，使所有要塞连通。

每个要塞都采用如下方案：选择离自己最近的另一个要塞，并朝它修建一条直线道路。

如果有两个要塞与它的距离相同，则选择名字按字典序更小的那个要塞作为目标。

每个要塞都有自己的修路速度，单位为英尺/小时。所有要塞在新年开始时同时开工，并且道路全天连续施工。施工地点就是当前道路的末端，它会沿着目标要塞的方向不断前进。

如果正在修建的道路碰到了另一条道路或某个城市，则这条道路立即停止继续施工。

蛮族正在暗中观察道路的修建过程，并提出两类问题：

1. 在开工恰好 $t$ 小时后，为了使所有城市连通，至少还需要额外修建多长的道路？这些额外道路可以连接两个城市、两个施工地点，或一个城市和一个施工地点。
2. 从开工开始，最少需要经过多少小时，才能使“仍需额外修建的最短道路总长度”不超过 $l$？

请根据王国的施工计划回答这些问题。

输入格式

输入包含多组测试数据。

每组测试数据的第一行包含一个正整数 $N$，表示要塞数量：

接下来 $N$ 行，每行描述一个要塞，包含：

• 要塞名字：仅由小写字母 a 到 z 组成；
• 该要塞的横坐标 $x$；
• 纵坐标 $y$；
• 修路速度 $s$，单位为英尺/小时。

随后给出若干询问。

每个询问的第一个整数为 $1$ 或 $2$：

• 1 t：询问开工 $t$ 小时后，至少还需修建多少英尺的额外道路才能使所有城市连通；
• 2 l：询问最早经过多少小时后，至少还需修建的道路长度不超过 $l$。

一行单独的 0 表示本组询问结束。

整个输入以一行单独的 0 结束，该行不需要处理。

输出格式

对于第 $k$ 组测试数据，首先输出：

Kingdom k

对于第一类询问 1 t，按照如下格式输出：

x feet left at time t

其中 $x$ 是此时至少仍需额外修建的道路总长度。

对于第二类询问 2 l：

• 如果存在答案，则输出：

t hours before l feet left

• 如果无论经过多久，都不可能使所需额外道路长度不超过 $l$，则输出：

NEVER

所有数值答案与标准答案的误差不得超过 $0.01$。

处理完全部测试数据后，输出：

End

样例输入

4
portland 0 0 3
seattle 0 10 2
newyork 20 6 1
boston 20 0 1
1 0
1 2.0
1 3.0
2 29
2 1.0
0
2
bree -10 -10 1
buckland 10 10 2
1 5
0
0

样例输出

Kingdom 1
36.000 feet left at time 0.000
22.000 feet left at time 2.000
20.000 feet left at time 3.000
1.000 hours before 29.000 feet left
NEVER

Kingdom 2
13.284 feet left at time 5.000

End