Description

你正在研究森林中的动物，并试图判断哪些动物是鸟，哪些不是鸟。

你通过测量每只动物的身高和体重来进行判断。要成为一只鸟，动物的身高需要在某个范围内，体重也需要在另一个范围内，但你并不确定这两个范围具体是多少。你还知道，所有满足这两个范围的动物一定是鸟。

你已经将部分测量过的动物展示给生物学家，他们告诉你哪些是鸟，哪些不是。这为你提供了一些关于鸟类身高和体重范围的信息。对于剩下的动物，你的程序需要判断它们是否一定是鸟、一定不是鸟，或者根据已有信息无法确定。

Input Format

第一行包含一个整数 $C$，表示测试用例的数量。

接下来对于每个测试用例：

• 第一行包含一个整数 $N$，表示你已经展示给生物学家的动物数量。
• 接下来的 $N$ 行，每行格式为 "H W X"，其中 $H$ 表示动物的身高，$W$ 表示动物的体重，$X$ 为字符串 "BIRD" 或 "NOT BIRD"。所有数字均为正整数。
• 接下来一行包含一个整数 $M$，表示你未展示给生物学家的动物数量。
• 接下来的 $M$ 行，每行格式为 "H W"，其中 $H$ 表示动物的身高，$W$ 表示动物的体重。所有数字均为正整数。

Output Format

对于每个测试用例：

• 输出一行，格式为 "Case #$X$: "，其中 $X$ 为测试用例编号，从 1 开始。
• 接下来 $M$ 行，每行输出 "BIRD"、"NOT BIRD" 或 "UNKNOWN"（不包含引号），分别表示该动物一定是鸟、一定不是鸟或无法确定。

3
5
1000 1000 BIRD
2000 1000 BIRD
2000 2000 BIRD
1000 2000 BIRD
1500 2010 NOT BIRD
3
1500 1500
900 900
1400 2020
3
500 700 NOT BIRD
501 700 BIRD
502 700 NOT BIRD
2
501 600
502 501
1
100 100 NOT BIRD
3
107 93
86 70
110 115

Case #1:
BIRD
UNKNOWN
NOT BIRD
Case #2:
UNKNOWN
NOT BIRD
Case #3:
UNKNOWN
UNKNOWN
UNKNOWN

Hint

样例解释

第 $1$ 组：

动物 “1500 1500” 必然在鸟类的范围内，因为我们知道身高和体重的范围都包含 $1000$ 和 $2000$。

动物 “900 900” 可能是鸟，也可能不是；我们无法确定身高和体重的范围是否包含 $900$。

动物 “1400 2020” 的身高在鸟类范围内，但如果体重 $2020$ 也在范围内，那么 “1500 2010” 这只我们已知不是鸟的动物也必须在体重范围内。

第 $2$ 组：

在这种情况下，我们知道鸟的身高必须是 $501$。但我们只知道鸟的体重范围包含 $700$，其他不确定。

第 3 组：

在这种情况下，我们知道身高 $100$ 且体重 $100$ 的动物不是鸟，但我们对鸟的范围一无所知。

数据范围

• $1 \leq C \leq 10$
• $1 \leq$ 所有身高和体重 $\leq 1000000$

小数据集（5 分，测试点 1 - 可见）

• $1 \leq N \leq 10$
• $1 \leq M \leq 10$

大数据集（12 分，测试点 2 - 隐藏）

• $1 \leq N \leq 1000$
• $1 \leq M \leq 1000$

由 ChatGPT 4.1 翻译