새란 무엇인가?

숲의 동물을 연구하면서 어떤 동물이 새이고 어떤 동물이 새가 아닌지 판별하려고 한다.

이를 위해 각 동물의 키와 몸무게라는 두 가지 수치를 측정한다. 어떤 동물이 새이려면 키가 어떤 범위 안에 있어야 하고 몸무게도 또 다른 범위 안에 있어야 하지만, 그 키와 몸무게의 범위가 무엇인지는 확실하지 않다. 또한 이 범위들을 만족하는 모든 동물은 새라는 사실을 알고 있다.

측정한 동물 중 일부를 생물학자들에게 보여 주었고, 생물학자들은 어떤 동물이 새이고 어떤 동물이 새가 아닌지 알려 주었다. 이를 통해 새의 키와 몸무게 범위가 반드시 어떠해야 하는지에 관한 정보를 얻었다. 나머지 동물에 대해서는, 주어진 정보로 그 동물이 확실히 새인지, 확실히 새가 아닌지, 아니면 알 수 없는지를 프로그램이 판별해야 한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ C ≤ 10 1 ≤ 모든 키와 몸무게 ≤ 1000000

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 10 1 ≤ M ≤ 10

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 1000 1 ≤ M ≤ 1000

입력의 테스트 케이스 수인 정수 C가 한 줄에 주어진다.

이어서 C개의 각 테스트 케이스마다 다음이 주어진다.

• 생물학자들에게 보여 준 동물의 수인 정수 N이 한 줄에 주어진다.

• 이 동물마다 하나씩 N개의 줄이 주어지며, 각 줄의 형식은 "H W X"이다. 여기서 H는 동물의 키, W는 동물의 몸무게이고, X는 문자열 "BIRD" 또는 "NOT BIRD" 중 하나이다. 모든 수는 양의 정수이다.

• 생물학자들에게 보여 주지 않은 동물의 수인 정수 M이 한 줄에 주어진다.

• 이 동물마다 하나씩 M개의 줄이 주어지며, 각 줄의 형식은 "H W"이다. 여기서 H는 동물의 키이고 W는 동물의 몸무게이다. 모든 수는 양의 정수이다.

C개의 각 테스트 케이스마다 다음을 출력한다.

• 문자열 "Case #X:"을 한 줄에 출력한다. 여기서 X는 1부터 시작하는 테스트 케이스의 번호이다.

• 각각 "BIRD", "NOT BIRD", "UNKNOWN" 중 하나를 담은 M개의 줄을 출력한다(따옴표는 명확성을 위해 표시한 것일 뿐 출력에 포함하면 안 된다).

케이스 1:

키와 몸무게의 각 범위에 1000과 2000이 포함된다는 사실을 알고 있으므로, 동물 "1500 1500"은 새의 범위 안에 있어야 한다.

동물 "900 900"은 새일 수도 있고 아닐 수도 있다. 키와 몸무게의 범위에 900이 포함되는지 알 수 없다.

동물 "1400 2020"은 새의 키 범위 안에 있지만, 2020이 몸무게 범위 안에 있다면 새가 아니라고 알고 있는 동물 "1500 2010"도 몸무게 범위 안에 있어야 한다.

케이스 2:

이 케이스에서는 새의 키가 501이어야 한다는 것을 알고 있다. 그러나 새의 몸무게 범위에 관해서는 몸무게 700을 포함한다는 것 외에는 알지 못한다.

케이스 3:

이 케이스에서는 키가 100이고 몸무게가 100인 것은 무엇이든 새가 아니라는 사실을 알고 있지만, 정작 무엇이 새인지는 알 수 없다.