由于他的辛勤工作，约翰（以前叫强尼）成为了体面的“富豪俱乐部”（Well Off Club）的成员。该俱乐部有 $n$ 个成员，编号从 $1$ 到 $n$；第 $i$ 个成员拥有的财富值为 $x_i$。这些财富值可以是任意数值，包括负数。这是因为俱乐部的会员资格是终身制的，也就是说，无论是变穷还是破产都不会被驱逐出俱乐部。

俱乐部成员们乐于比较他们的资产价值，但他们避免直接透露具体的数字；他们的习惯是通过交流来确定他们的财富 $x_i$ 和 $x_j$ 满足以下不等式之一：$x_i + x_j > 0$、$x_i - x_j > 0$、$-x_i + x_j > 0$ 或 $-x_i - x_j > 0$。

强尼今天在俱乐部里（无意中）听到了许多这样的不等式，但他怀疑其中一些成员在撒谎。请帮助他确定是否所有的不等式都有可能同时成立，即是否存在一组财富值能够同时满足所有的不等式。编写一个程序：读取强尼听到的不等式，判断它们是否可以被同时满足，并将答案输出到标准输出。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 100\,000$，$1 \le m \le 500\,000$），由单个空格分隔。它们分别表示俱乐部成员的数量以及涉及他们财富的不等式数量。

接下来的 $m$ 行，每行描述一个不等式，由一个 + 或 - 符号、一个整数 $i$（$1 \le i \le n$）、另一个 + 或 - 符号以及一个整数 $j$（$1 \le j \le n$）组成，彼此之间用单个空格分隔。这对应于不等式 $\pm x_i \pm x_j > 0$（符号与描述中 $i$ 和 $j$ 前面的符号一致）。可能会出现 $i = j$ 的情况。

输出格式

输出的第一行且仅有一行应包含一个单词：如果该不等式组是可满足的，则输出 “TAK”；否则输出 “NIE”。

样例

输入样例 1

3 3
+ 1 - 2
- 3 + 1
+ 2 - 3

输出样例 1

TAK

输入样例 2

3 3
+ 1 - 2
+ 3 - 1
+ 2 - 3

输出样例 2

NIE

说明

在样例 1 中，不等式组是可满足的，例如取 $x_1 = 3, x_2 = 2, x_3 = 1$。

在样例 2 中，不等式组是不可满足的。