Wi-Fi 네트워크

Hektor는 부자가 될 아이디어를 떠올렸다. 그는 잘 알려진 문제, 즉 집 안의 모든 컴퓨터가 Wi-Fi 공유기에 연결될 수 있도록 공유기를 배치하는 문제를 푸는 프로그램을 작성하기로 했다. 여기서 연결된다는 것은 공유기와 컴퓨터를 잇는 최단 경로가 어떤 벽도 통과하지 않는다는 뜻이다.

첫 번째 버전은 많이 단순화되어 있다. 컴퓨터가 최대 세 대인 집만 다루고, 공유기의 도달 범위는 무한하다. 범위가 무한하므로 공유기에서 컴퓨터까지의 최단 경로는 둘을 잇는 직선 선분이며, 따라서 그 선분이 어떤 벽과도 교차하지 않을 때 컴퓨터가 연결된다.

각 테스트 집합에 대해, 모든 컴퓨터가 연결되는 공유기 위치가 하나라도 존재하는지 판단하여라.

첫째 줄에 테스트 집합의 개수 $Z$가 주어진다 ($1 \le Z \le 10$). 이어서 각 테스트 집합이 주어진다.

각 집합의 첫째 줄에는 세 정수 $R$, $N$, $M$이 주어진다 ($2 \le R \le 10000$, $2 \le N \le 3$, $1 \le M \le 100$). 공유기를 놓을 후보 영역은 $-R < X < R$, $-R < Y < R$을 만족하는 점 $(X, Y)$로 제한된다. $N$은 컴퓨터의 수, $M$은 이 영역 안의 벽의 수이다.

다음 $N$개의 줄에는 각각 두 정수 $X$, $Y$가 주어지며 ($-R < X < R$, $-R < Y < R$), 컴퓨터의 위치를 나타낸다.

다음 $M$개의 줄에는 각각 네 정수 $x_0$, $y_0$, $x_1$, $y_1$이 주어지며 (모두 $-R$과 $R$ 사이), $(x_0, y_0)$에서 $(x_1, y_1)$까지의 선분으로 나타내는 하나의 벽을 의미한다.

어떤 두 벽도 서로 교차하지 않는다고 가정해도 좋다. 다만 끝점은 공유할 수 있다. 어떤 컴퓨터도 벽 위에 있지 않다.

각 테스트 집합에 대해, 신호가 벽을 통과하지 않고 모든 컴퓨터에 도달하도록 공유기를 놓을 수 있으면 TAK을, 그렇지 않으면 NIE를 한 줄에 하나씩 출력한다.