폰

$n \times n$ 크기의 체스판이 있습니다. 각 칸은 검은색 또는 흰색입니다. 폰은 지금 서 있는 칸에서 가로, 세로, 대각선으로 맞닿은 최대 8개의 이웃 칸 중 하나로 움직일 수 있는데, 그 이웃 칸의 색이 지금 서 있는 칸의 색과 같을 때에만 움직일 수 있습니다. 즉 폰은 색을 바꾸지 못하며, 같은 색으로 이어진 영역 안에서만 이동합니다.

이동이 가능한 예시입니다.

여러 칸 쌍에 대해, 첫 번째 칸에 놓인 폰이 이런 이동만으로 두 번째 칸에 도달할 수 있는지 판정하세요.

첫 번째 줄에 세 정수 $n$, $m$, $p$ ($1 \le n \le 100000$, $1 \le m \le 1000000$, $1 \le p \le 1000$)가 주어집니다. 각각 체스판 한 변의 길이, 색칠을 설명하는 검은색 조각의 개수, 질의의 개수입니다. 행과 열은 $1$부터 $n$까지 번호가 매겨집니다.

이어지는 $m$개의 줄에는 각각 세 정수 $w_i$, $k_{i,1}$, $k_{i,2}$ ($1 \le w_i \le n$, $1 \le k_{i,1} \le k_{i,2} \le n$)가 주어지며, $w_i$행에서 열 번호가 $k_{i,1}$ 이상 $k_{i,2}$ 이하인 모든 칸이 검은색임을 뜻합니다. 조각끼리는 서로 겹칠 수 있습니다. 어떤 조각에도 포함되지 않는 칸은 흰색입니다.

이어지는 $p$개의 줄에는 각각 네 정수 $a_{i,1}$, $b_{i,1}$, $a_{i,2}$, $b_{i,2}$ ($1 \le a_{i,1}, b_{i,1}, a_{i,2}, b_{i,2} \le n$)가 주어집니다. $a_{i,1}$행 $b_{i,1}$열의 칸에서 $a_{i,2}$행 $b_{i,2}$열의 칸으로 폰이 이동할 수 있는지 묻는 질의입니다.

질의마다 한 줄씩, 입력에 주어진 순서대로 총 $p$개의 줄을 출력합니다. 폰이 다른 색의 칸을 밟지 않고 첫 번째 칸에서 두 번째 칸으로 이동할 수 있으면 TAK(가능하다는 뜻)을, 그렇지 않으면 NIE(불가능하다는 뜻)를 출력합니다.

예제에 쓰인 체스판과 질의입니다.