Bytean Road Race

The Bytean Road Race will be held tomorrow in the center of Bytetown. The city's streets form a regular grid: every street runs either south-to-north or west-to-east. Runners may use only certain marked parts of these streets.

Byteasar has to place the sponsors' banners at some of the crossings, so he studies the race map. The map shows the street segments the runners are allowed to use. There are $n$ crossings and $m$ horizontal or vertical road segments. Each segment begins and ends at a crossing and contains no crossing in its interior; two segments may meet only at a crossing.

The crossings are numbered from $1$ to $n$. The race starts at crossing $1$ and finishes at crossing $n$. Each runner chooses their own route, but may move only south and east, and only along the marked segments. The marked segments are arranged so that, obeying these rules, the finish can be reached from every crossing and every crossing can be reached from the start.

Byteasar wants no runner to see the same sponsor's banner twice. To arrange this he needs to know, for certain pairs of crossings, whether some runner's route can pass through both crossings of the pair. Help him answer these questions.

The first line contains three integers $n$, $m$, and $k$ ($2 \le n \le 100\,000$, $1 \le m \le 200\,000$, $1 \le k \le 300\,000$): the number of crossings, the number of marked segments, and the number of crossing pairs to check.

The next $n$ lines describe the crossings. The $i$-th of them contains two integers $x_i$ and $y_i$ ($-10^9 \le x_i, y_i \le 10^9$), the coordinates of crossing $i$. The $OX$ axis points east and the $OY$ axis points north. Moreover $x_1 \le x_n$ and $y_1 \ge y_n$, and no two crossings lie at the same point.

Each of the next $m$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$): the two crossings joined by one segment. Every segment is horizontal or vertical, and two segments meet only at a shared endpoint.

Each of the next $k$ lines contains two integers $p_i$ and $q_i$ ($1 \le p_i, q_i \le n$, $p_i \ne q_i$): a pair of crossings to check.

Output $k$ lines. The $i$-th line should contain TAK if some runner's route can pass through both crossings $p_i$ and $q_i$ (in either order), and NIE otherwise. (TAK means yes and NIE means no.)