What Are Birds? (Large)

You are studying animals in a forest and want to work out which of them are birds.

You do this by measuring the height and the weight of every animal. An animal is a bird exactly when its height falls inside one range and its weight falls inside another range. You do not know what those two ranges are. Conversely, every animal that satisfies both ranges is a bird, with no exceptions.

You showed some of the measured animals to biologists, and they told you which ones are birds and which ones are not. Those answers give you partial information about what the height range and the weight range must be. For the remaining animals, write a program that decides whether each one is definitely a bird, definitely not a bird, or impossible to classify from the information you have.

The answers from the biologists come from the two real ranges, so the input never contradicts itself: at least one pair of a height range and a weight range agrees with every answer given.

The first line contains an integer $C$, the number of test cases.

Then each of the $C$ test cases is given as follows.

• One line containing an integer $N$, the number of animals you showed to the biologists.
• $N$ lines, one animal each, in the format "$H$ $W$ $X$", where $H$ is the height, $W$ is the weight, and $X$ is either the string "BIRD" or the string "NOT BIRD".
• One line containing an integer $M$, the number of animals you did not show to the biologists.
• $M$ lines, one animal each, in the format "$H$ $W$", where $H$ is the height and $W$ is the weight.

All heights and weights are positive integers.

Limits

• $1 \le C \le 10$
• $1 \le N \le 1000$
• $1 \le M \le 1000$
• $1 \le H \le 1000000$
• $1 \le W \le 1000000$

For each test case, print the following.

• One line containing the string "Case #$X$:", where $X$ is the number of the test case, starting from 1.
• Then $M$ lines, one for each animal you did not show to the biologists, in input order. Print "BIRD" if the animal is a bird under every pair of ranges that agrees with the answers, "NOT BIRD" if it is not a bird under every such pair, and "UNKNOWN" otherwise. Do not print the quotation marks.

In the first test case of the example, the height range and the weight range both contain 1000 and 2000. The animal of height 1500 and weight 1500 therefore falls inside both ranges, so it is a bird.

The animal of height 900 and weight 900 cannot be decided. Nothing tells you whether the two ranges contain 900.

The animal of height 1400 and weight 2020 is inside the height range. But if the weight range contained 2020, then the animal of height 1500 and weight 2010, which is known not to be a bird, would fall inside both ranges as well.

In the second test case you can tell that a bird must have height 501. About the weight range you know only that it contains 700.

In the third test case you know that an animal of height 100 and weight 100 is not a bird, and nothing else about what birds are.