年轻的 Bytensson 喜欢在港口酒馆里消磨时光，在那里他经常听海员们讲述他们的航海故事。起初，他对这些故事深信不疑，无论它们听起来多么不可思议。但随着时间的推移，他开始产生怀疑。他决定编写一个程序，来验证这些离奇的故事中是否有一丝真实性。Bytensson 认为，虽然他无法判断海员们是否真的经历过那些风暴，但他至少可以查明他们的航行路线是否合理。这是一项程序员的工作，而不幸的是，Bytensson 并不是程序员。请帮帮他！

在海员们经常出没的海域，有 $n$ 个港口和 $m$ 条连接它们的航道。如果两个港口之间有航道，那么就可以在它们之间航行。任何航道都可以双向通行。

Bytensson 听到了 $k$ 个航海故事。每个故事都讲述了一名水手从一个港口出发，航行了若干条航道，最后到达另一个港口（可能是出发时的那个港口）。故事中的水手可能多次经过同一条航道，且每次航行方向不限。

输入格式

标准输入的第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n \le 5\,000$，$1 \le m \le 5\,000$，$1 \le k \le 1\,000\,000$）。它们分别表示：海员们经常出没的海域中的港口数量、航道数量以及故事的数量。

接下来的 $m$ 行描述了航道。每条航道的描述占一行，包含两个整数 $a$ 和 $b$（$1 \le a, b \le n$，$a \ne b$），由空格分隔，表示该航道两端的港口编号。

接下来的 $k$ 行描述了 Bytensson 听到的故事。每个故事的描述占一行，包含三个整数 $s$、$t$ 和 $d$（$1 \le s, t \le n$，$1 \le d \le 1\,000\,000\,000$），由空格分隔。这表示故事的主人公从 $s$ 号港口出发，在 $t$ 号港口结束航行，并且恰好航行了 $d$ 次航道。

输出格式

你的程序应向标准输出打印恰好 $k$ 行；如果第 $i$ 个故事中描述的航行可能发生，则第 $i$ 行应包含单词 TAK（波兰语，意为“是”）。如果不可能发生，则该行应包含单词 NIE（波兰语，意为“否”）。

样例

输入 1

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

输出 1

TAK
NIE
TAK
NIE