주차장

주차 관리원의 하루는 어떤 모습일까? 겉으로 보기에는 어려운 일이 아니다. 손님이 차를 맡기고 가면 관리원이 그 차를 세워 두면 된다. 하지만 실제로는 그렇게 간단하지 않다. 관리원을 가장 괴롭히는 것은 사장이다.

어느 날 사장이 자기 마음대로 정한 배치대로 주차장의 차를 전부 다시 세우라고 지시했다. 관리원은 사장이 건넨 종이와 지금 배치가 적힌 종이를 번갈아 보며 이것이 가능하기는 한지 고민하고 있다. 관리원을 도와주자.

주차장은 평면 위에 놓인 높이 $w$의 직사각형이다. 설명을 쉽게 하려고 직사각형의 변과 평행한 좌표축을 잡고 원점을 직사각형의 왼쪽 아래 꼭짓점에 둔다. 주차장은 충분히 넓어서 오른쪽 변이 무한히 멀리 있다고 봐도 된다.

차도 좌표축과 평행한 직사각형으로 본다. 큰 차도 있고 작은 차도 있으므로 직사각형의 크기는 서로 다를 수 있다. 모든 차가 주차장 안에 있고 주차장의 어느 부분도 두 차가 동시에 차지하지 않으면 그 배치는 올바르다. 차를 나타내는 직사각형의 경계끼리 맞닿는 것은 허용한다.

관리원은 경력이 오래되어 차를 어느 방향으로든 원하는 대로 옮길 수 있다. 형식적으로 말하면 관리원은 아무 차나 골라 임의의 벡터만큼 평행이동할 수 있고, 옮기는 동안 차끼리 서로 파고들지만 않으면 된다. 대신 차를 회전시킬 수는 없다.

지금 배치에서 사장이 정한 배치로 차를 한 대도 망가뜨리지 않고 옮길 수 있는지 판정하라.

첫 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 20$)가 주어진다. 이어서 각 테스트 케이스가 차례로 주어진다.

각 테스트 케이스의 첫 줄에는 정수 $n$과 $w$ ($1 \le n \le 50000$, $1 \le w \le 10^9$)가 주어진다. $n$은 주차장에 있는 차의 수이고 $w$는 주차장을 나타내는 직사각형의 높이다.

다음 $n$개 줄에는 처음 배치가 주어진다. 그중 $i$번째 줄에는 정수 네 개 $x_1$, $y_1$, $x_2$, $y_2$ ($0 \le x_1, x_2 \le 10^9$, $0 \le y_1, y_2 \le w$)가 주어진다. 이는 두 점 $(x_1, y_1)$과 $(x_2, y_2)$를 마주 보는 꼭짓점으로 하는 직사각형, 곧 $i$번째 차를 뜻한다. 모든 직사각형의 넓이는 양수다.

그다음 $n$개 줄에는 목표 배치가 같은 형식으로 주어진다. 두 배치에서 차의 순서는 같아서 처음 배치의 $i$번째 차와 목표 배치의 $i$번째 차는 같은 차다. 같은 차라도 목표 배치에서는 처음 배치와 다른 꼭짓점 쌍으로 적혀 있을 수 있다. 두 배치는 모두 올바르다고 가정해도 된다.

$t$개 줄을 출력한다. $i$번째 줄에는 $i$번째 테스트 케이스에서 사장이 요구한 대로 차를 옮길 수 있으면 TAK을, 옮길 수 없으면 NIE를 출력한다. TAK과 NIE는 각각 폴란드어로 예와 아니오를 뜻한다.

그림은 예제 입력의 첫 번째 테스트 케이스다. 왼쪽이 처음 배치, 오른쪽이 목표 배치다. 3번 차를 제자리에 넣으려면 2번 차를 아래나 오른쪽으로 옮겨야 한다. 두 번째 테스트 케이스에서는 1번 차와 2번 차의 자리를 맞바꿔야 하는데, 그것은 불가능하다.