题目描述

Byteotia 国际象棋越来越流行，因此出现了许多不同的玩法。

传统版本在无限棋盘上进行，但这并不总是方便，因此有时会使用大小不超过 $10^5\times10^5$ 的有限棋盘。

棋盘中的一些格子是黑色，其余格子是白色，具体的染色方式由输入决定。

有一枚棋子在棋盘上移动。每一步，它可以移动到竖直、水平或斜方向上的任意一个相邻格子，也就是说一共有至多 8 个相邻格子可以选择。

但是棋子的移动受到一个限制：

它只能移动到与当前所在格子颜色相同的相邻格子。

现在给出若干对格子。对于每一对格子，你需要判断棋子能否从其中一个格子移动到另一个格子，并且整个过程中始终只经过同一种颜色的格子。

输入格式

第一行包含三个整数 $n,m,p$：

• $1\le n\le10^5$：棋盘边长，棋盘大小为 $n\times n$；
• $1\le m\le10^6$：用于描述黑色区域的区间数量；
• $1\le p\le10^3$：询问数量。

棋盘上的行、列编号均为 $1,2,\ldots,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})$？

输出格式

对于每个询问输出一行：

• 若可以在整个过程中不经过另一种颜色的格子，从起点到达终点，输出 TAK；
• 否则输出 NIE。

样例

4 5 2
1 1 1
2 3 4
3 2 2
4 2 2
4 2 2
1 1 3 2
1 2 4 4

NIE
TAK