Problem description

Dzięki swej ciężkiej pracy Jan, dawniej Jasio, stał się członkiem szanowanego Klubu Bogaczy. Klub ma N członków ponumerowanych kolejnymi liczbami naturalnymi od 1 do N; członek Klubu numer i ma majątek warty X_i. Z Klubu nie można zostać usuniętym z powodu zubożenia lub bankructwa, dlatego też wartość majątku każdego z członków może być dowolną liczbą, w tym ujemną.

Członkowie Klubu lubią porównywać swe majątki, nie lubią jednak bezpośrednio podawać kwot; zwyczajowo po krótkiej wymianie zdań ustalają, że wartości ich majątków X_i oraz X_j spełniają jedną z nierówności X_i + X_j > 0, X_i − X_j > 0,  − X_i + X_j > 0 lub  − X_i − X_j > 0.

Jan usłyszał dzisiaj w Klubie wiele tego typu nierówności, podejrzewa jednak, że niektórzy członkowie klubu kłamią. Pomóż mu sprawdzić, czy nierówności mogą odpowiadać faktycznym majątkom członków klubu. Napisz program, który: wczyta opis nierówności usłyszanych przez Jana, ustali, czy mogą one odpowiadać wartościom majątków członków Klubu i wypisze odpowiedź.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N oraz M, oddzielone pojedynczym odstępem. Określają one odpowiednio liczbę członków Klubu oraz liczbę usłyszanych nierówności między ich majątkami.

Każdy z następnych M wierszy zawiera opis jednej nierówności. Pojedynczy opis składa się ze znaku + lub −, liczby naturalnej i (1 ≤ i ≤ N), znaku + lub −, liczby naturalnej j (1 ≤ j ≤ N), oddzielonych pojedynczymi odstępami; odpowiada on pojedynczej nierówności  ± X_i ± X_j > 0 (zależnie od znaków występujących przed i oraz j). Może się zdarzyć, że i = j.

Wyjście

Pierwszy i jednocześnie jedyny wiersz wyjścia powinien zawierać jedno słowo: TAK, jeżeli usłyszane nierówności mogą odpowiadać wartościom majątków członków Klubu lub NIE w przeciwnym przypadku.

Ograniczenia

1 ≤ N ≤ 10⁵, 1 ≤ M ≤ 5 ⋅ 10⁵.

Przykład

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

TAK

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

NIE