바이트랜드 월드비트 출판사

바이타사르는 바이트랜드 월드비트 출판사(BWP)의 관리자이다. 이 회사에는 작곡가 $n$명과 작사가 $m$명이 근무한다. 예술가들은 작곡가 한 명과 작사가 한 명으로 이루어진 짝을 지어 일한다.

바이타사르는 모든 직원의 역량을 알고 있어서, 어떤 작곡가-작사가 짝이 얼마나 생산적일지 가늠할 수 있다. 한 짝의 효율은 그 짝이 일주일에 쓰는 곡의 수로 나타낸다.

바이타사르는 서로 겹치지 않는 짝 $\min(n, m)$개를(각 예술가는 최대 한 짝에만 속한다) 만들어 일주일 동안 만들어지는 곡의 총수를 최대로 하려고 한다. 짝을 이루지 못한 예술가는 일하지 않는다.

자료를 분석한 뒤, 바이타사르는 일주일간 만들어지는 곡의 총수가 짝을 어떻게 짓든 상관없이 늘 같을 것이라고 짐작한다. 이 짐작이 맞는지 확인해 보자. 즉, 서로 겹치지 않는 짝 $\min(n, m)$개를 만드는 모든 방법이 항상 같은 총효율을 주는지 판정하라.

첫 줄에 정수 $t$ ($1 \le t \le 10$), 곧 테스트 케이스의 수가 주어진다. 이어서 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 세 정수 $n$, $m$, $k$ ($1 \le n, m \le 100000$, $1 \le k \le 300000$)가 주어진다. 각각 작곡가 수, 작사가 수, 효율을 설명하는 줄의 수이다. 작곡가는 $1$번부터 $n$번까지, 작사가는 $1$번부터 $m$번까지 번호가 매겨진다.

다음 $k$개의 줄에는 각각 네 정수 $a_i$, $b_i$, $c_i$, $p_i$ ($1 \le a_i \le n$, $1 \le b_i \le c_i \le m$, $1 \le p_i \le 10^9$)가 주어진다. 이는 작곡가 $a_i$가 $b_i$번부터 $c_i$번까지(양 끝 포함)의 어떤 작사가와 짝을 이루면 일주일에 $p_i$곡을 만든다는 뜻이다.

각 작곡가-작사가 짝은 최대 한 번만 설명된다. 입력에 나오지 않은 짝의 효율은 일주일에 $0$곡이지만, 그런 짝도 만들 수는 있다.

각 테스트 케이스마다 한 줄을 출력한다. 서로 겹치지 않는 짝 $\min(n, m)$개를 만드는 모든 방법이 항상 같은 총효율을 준다면 TAK(폴란드어로 "예")를, 그렇지 않다면 NIE(폴란드어로 "아니오")를 출력한다.