Bytean Road Race 将于明天在 Bytetown 市中心举行。Bytetown 的街道构成了一个规则的网格：所有街道要么从南向北延伸，要么从西向东延伸。参赛者只允许使用给定的部分道路。

Byteasar 的任务是在一些交叉路口放置赞助商的横幅，为此他必须检查比赛的路线图。地图描绘了允许参赛者使用的街道段。地图上标记了 $n$ 个交叉路口以及若干垂直和水平的道路段。每一段道路的起点和终点都是某个交叉路口，且不包含其他交叉路口。道路段仅能在交叉路口处相交。

交叉路口编号为 $1$ 到 $n$。比赛将从 $1$ 号交叉路口开始，在 $n$ 号交叉路口结束。参赛者可以自行选择路线，但要求只能向南和向东奔跑，且只能沿着地图上标记的道路段行进。地图上的道路段选择方式保证了按照规则奔跑，可以从任何地方到达终点，且每个地方都可以从起点交叉路口到达。

Byteasar 希望以一种确保没有任何参赛者会看到同一个赞助商的横幅两次的方式放置横幅。因此，对于某些交叉路口对，Byteasar 必须检查是否有参赛者的路线可能同时经过这两个交叉路口。比赛明天就要举行了，因此急需一个程序来帮助他完成这项任务。

输入格式

第一行包含三个整数 $n, m$ 和 $k$ ($2 \leqslant n \leqslant 100\,000, 1 \leqslant m \leqslant 200\,000, 1 \leqslant k \leqslant 300\,000$)。它们分别表示比赛路线上的交叉路口数量、地图上标记的道路段数量以及需要检查的交叉路口对数量。

接下来的 $n$ 行描述了交叉路口的位置。第 $i$ 行包含第 $i$ 个交叉路口的坐标，由两个整数 $x_i, y_i$ 表示 ($-10^9 \leqslant x_i, y_i \leqslant 10^9$)。此外，$x_1 \leqslant x_n$ 且 $y_1 \geqslant y_n$。任意给定点最多只有一个交叉路口。坐标轴与现实世界的方位对应：OX 轴指向东方，OY 轴指向北方。

接下来的 $m$ 行每行包含一个地图上道路段的描述，由一对整数 $a_i, b_i$ ($1 \leqslant a_i, b_i \leqslant n, a_i \neq b_i$) 组成，表示由该段连接的交叉路口编号。所有这些段要么是垂直的，要么是水平的，并且它们只能在公共端点（交叉路口）处相交。

接下来的 $k$ 行包含需要检查的交叉路口对的描述。第 $i$ 行包含两个整数 $p_i, q_i$ ($1 \leqslant p_i, q_i \leqslant n, p_i \neq q_i$)。

输出格式

你的程序应输出 $k$ 行。如果某位参赛者的路线可能同时经过交叉路口 $p_i$ 和 $q_i$（顺序不限），则第 $i$ 行应包含单词 TAK（波兰语中的“是”）。否则，输出应为 NIE（波兰语中的“否”）。

样例

输入 1

9 10 4
1 6
2 6
4 4
1 4
3 4
4 6
6 4
3 1
6 1
1 2
4 1
2 6
3 6
5 4
5 3
5 8
3 7
7 9
9 8
4 8
2 5
8 7
7 6

输出 1

TAK
NIE
NIE
TAK