Pawn

You are given an $n \times n$ chessboard. Every square is either black or white. A pawn stands on one square and moves as follows: from its current square it may step to any of the up to eight squares that touch it horizontally, vertically, or diagonally, but only if that neighbouring square has the same colour as the square the pawn currently occupies. In other words, the pawn never changes colour and can only walk within a connected region of same-coloured squares.

Examples of valid moves.

For several pairs of squares, decide whether a pawn placed on the first square of the pair can reach the second square using only such moves.

The first line contains three integers $n$, $m$, and $p$ ($1 \le n \le 100000$, $1 \le m \le 1000000$, $1 \le p \le 1000$): the side length of the board, the number of black fragments that describe the colouring, and the number of queries. Rows and columns are numbered from $1$ to $n$.

Each of the next $m$ lines contains three integers $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$), meaning that in row $w_i$ every square whose column lies between $k_{i,1}$ and $k_{i,2}$ (inclusive) is black. Fragments may overlap. Every square not covered by any fragment is white.

Each of the next $p$ lines contains four integers $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 query asking whether a pawn can travel from the square in row $a_{i,1}$, column $b_{i,1}$ to the square in row $a_{i,2}$, column $b_{i,2}$.

Print $p$ lines, one per query, in the same order as the input. For each query print TAK (meaning yes) if a pawn can move from the first square to the second one without ever stepping onto a square of a different colour, or NIE (meaning no) otherwise.

The chessboard and the queries used in the sample test.