Problem description

Jasio bardzo lubi problemy NP-trudne. Ostatnio zainteresował się problemem 3-SAT, w którym dana jest formuła logiczna będąca koniunkcją M klauzul, a każda klauzula jest alternatywą trzech literałów: każdy z nich jest jedną z N zmiennych logicznych lub zaprzeczeniem jednej z tych zmiennych. Przykładowa formuła 3-SAT pokazana jest poniżej:

(x₁∨¬x₂∨x₄) ∧ (¬x₁∨x₂∨x₃) ∧ (x₂∨¬x₃∨¬x₄)

Zadanie polega na znalezieniu wartościowania zmiennych (tj. przypisania zmiennym wartości logicznych prawda lub fałsz), tak aby formuła była spełniona (jej wartością logiczną ma być prawda).

Napisz program, który: wczyta formułę problemu 3-SAT, wyznaczy wartościowanie spełniające (lub stwierdzi, że takie nie istnieje) i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu znajdują się dwie liczby naturalne N oraz M, oddzielone pojedynczym odstępem i określające kolejno: liczbę zmiennych oraz liczbę klauzul formuły. W kolejnych M wierszach znajduje się opis kolejnych klauzul, po jednej w wierszu. Opis każdej klauzuli składa się z trzech liczb całkowitych A_i, B_i oraz C_i, pooddzielanych pojedynczymi odstępami, określających numery zmiennych występujących w i-tej klauzuli. Wartość dodatnia oznacza zmienną, zaś ujemna – negację zmiennej.

Wyjście

W pierwszym wierszu wyjścia należy wypisać słowo TAK, jeśli jest możliwe spełnienie formuły z wejścia. W takim przypadku w drugim wierszu wejścia powinien się znaleźć ciąg znaków długości N, i-ty znak tego ciągu ma być P jeśli i-ta zmienna powinna być prawdą, lub F w przeciwnym przypadku.

Jeśli nie jest możliwe spełnienie formuły z wejścia należy wypisać jedno słowo NIE. Jeśli istnieje wiele możliwych rozwiązań, należy wypisać dowolne z nich.

Ograniczenia

3 ≤ N ≤ 50 000, 1 ≤ M ≤ 500 000, 1 ≤ |A_i| < |B_i| < |C_i| ≤ N, |C_i| − |A_i| < 8.

Przykład

4 3
1 -2 4
-1 2 3
2 -3 -4

TAK
PPPF