Well Off

Thanks to his hard work, John, formerly Johnny, has become a member of the respectable Well Off Club. The club has $n$ members, numbered from 1 to $n$. The $i$-th member has a fortune worth $x_i$. These can be arbitrary numbers, including negative ones. Club membership is for life. Neither impoverishment nor even bankruptcy results in an ousting.

The members enjoy comparing their assets, but they never state the numbers directly. Instead, they hold a conversation that establishes whether $x_i$ and $x_j$ satisfy one of $x_i + x_j > 0$, $x_i - x_j > 0$, $-x_i + x_j > 0$, or $-x_i - x_j > 0$.

Johnny heard many such inequalities at the club today, but he suspects some members are lying. Write a program that reads the inequalities he heard, determines whether they can all be true at once, that is, whether some set of fortunes satisfies all of them simultaneously, and prints the answer to standard output.

The first line contains two integers $n$ and $m$ separated by a space ($1 \le n \le 100\,000$, $1 \le m \le 500\,000$). $n$ is the number of club members and $m$ is the number of inequalities relating their fortunes.

Each of the next $m$ lines contains a sign + or -, an integer $i$ ($1 \le i \le n$), another sign + or -, and an integer $j$ ($1 \le j \le n$), separated by single spaces. This encodes the inequality $\pm x_i \pm x_j > 0$, where each sign is the one written directly before $i$ or $j$. It is possible that $i = j$.

Print a single word on the only line of output. Print TAK if the system of inequalities is satisfiable, and NIE otherwise.

In Sample 1, the system is satisfiable, for example with $x_1 = 3$, $x_2 = 2$, $x_3 = 1$. In Sample 2, the system is not satisfiable.