Andy: “Billy the Kid 先开的枪！” Larry: “不，我确定我听到第一声枪响来自 John！”

在西部荒野某处发生了一场大枪战，审判期间双方争执不下。奇迹般的是，所有人都活了下来（尽管受了重伤），但没人能就开枪的准确顺序达成一致。已知每个人最多开了一枪，但一切发生得非常快。确定准确的开枪顺序对于判定罪责和惩罚至关重要。

但随后，治安官 Willy the Wise 打断了他们：“看，我拿到了枪战时的卫星图像，显示了每个人的确切位置。事实证明，Larry 距离 John 比距离 Billy the Kid 近得多，而 Andy 距离 John 仅比距离 Billy the Kid 稍微近一点。因此，由于声音以 $340$ 米每秒的有限速度传播，即使是 Billy the Kid 先开的枪，Larry 也可能先听到 John 的枪声。但是，尽管 Andy 距离 John 比距离 Billy the Kid 近，他却先听到了 Billy the Kid 的枪声——所以我们确定 Billy the Kid 是第一个开枪的人！”

你的任务是编写一个程序，在类似上述的情况下推断出准确的开枪顺序。

输入格式

第一行是一个正整数：测试用例的数量，最多 $100$ 个。每个测试用例包含：

• 一行包含两个整数 $n$ ($2 \le n \le 100$) 和 $m$ ($1 \le m \le 1000$)：涉及的人数和观察记录的数量。
• $n$ 行，每行包含一个字符串 $S$（由最多 $20$ 个大小写字母组成）和两个整数 $x$ 和 $y$ ($0 \le x, y \le 1\,000\,000$)：人的唯一标识符及其在笛卡尔坐标系中的位置（单位为米，相对于原点）。
• $m$ 行，格式为 “$S1$ heard $S2$ firing before $S3$”，其中 $S1$、$S2$ 和 $S3$ 是涉及人员的标识符，且 $S2 \neq S3$。

如果某人从未被提及为 $S2$ 或 $S3$，则可以假定此人从未开枪，仅作为目击者。没有两个人的位置相同。

测试用例的构造保证距离计算中小于 $10^{-7}$ 的误差不会影响输出。

输出格式

每个测试用例：

• 一行，包含与所有观察结果兼容的射手顺序，格式为以单个空格分隔的标识符。

如果存在多种不同的可能顺序，则输出 “UNKNOWN”。如果没有任何顺序与观察结果兼容，则输出 “IMPOSSIBLE”。

样例

输入 1

3
4 2
BillyTheKid 0 0
Andy 10 0
John 19 0
Larry 20 0
Andy heard BillyTheKid firing before John
Larry heard John firing before BillyTheKid
2 2
Andy 0 0
Beate 0 1
Andy heard Beate firing before Andy
Beate heard Andy firing before Beate
3 1
Andy 0 0
Beate 0 1
Charles 1 3
Beate heard Andy firing before Charles

输出 1

BillyTheKid John
IMPOSSIBLE
UNKNOWN