2483. What are Birds?

输入格式

One line containing an integer C(1 ≤ C ≤ 10), the number of test cases in the input.

Then for each of the C test cases:

• One line containing an integer N(1 ≤ N ≤ 1000), the number of animals you have shown to the biologists.
• N lines, one for each of these animals, each of the format “H W X”, where H is the height of the animal, W is the weight of the animal, and X is either the string “BIRD” or “NOT BIRD”. All numbers are positive integers.
• One line containing an integer M(1 ≤ M ≤ 1000), the number of animals you have not shown to the biologists.
• M lines, one for each of these animals, each of the format “H W”, where H is the height of the animal and W is the weight of the animal. All numbers are positive integers.

1 ≤ all heights and weights ≤ 1000000

输出格式

For each of the C test cases:

• One line containing the string “Case #X:” where X is the number of the test case, starting from 1.
• M lines, each containing one of “BIRD”, “NOT BIRD”, or “UNKNOWN” (quotes are just for clarity and should not be part of the output).

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:
Case 1:
The animal "1500 1500" must be within the ranges for birds, since we know that the ranges for height and weight each include 1000 and 2000.
The animal "900 900" may or may not be a bird; we don't know if the ranges for height and weight include 900.
The animal "1400 2020" is within the height range for birds, but if 2020 was in the weight range, then the animal "1500 2010", which we know is not a bird, would also have to be within the weight range.
Case 2:
In this case we know that birds must have a height of 501. But we don't know what the weight range for a bird is, other than that it includes weight 700.
Case 3:
In this case, we know that anything with height 100 and weight 100 is not a bird, but we just don't know what birds are.