Niech W będzie wyrażeniem rachunku zdań składającym się z n zmiennych zdaniowych p_0, p_1, …, p_(n-1), oraz operatorów logicznych:

 - koniunkcji, symbol ‘*’ (kod ASCII 42),

 - alternatywy , symbol ‘+’ (kod ASCII 43),

 - alternatywy wykluczającej, tj. XOR, symbol ‘@’ (kod ASCII 64),

 - implikacji lewostronnej, symbol ‘>’ (kod ASCII 62),

 - implikacji prawostronnej, symbol ‘<’ (kod ASCII 60),

 - równoważności, symbol ‘=’ (kod ASCII 61),

 - negacji koniunkcji, tj. NAND, symbol ‘/’ (kod ASCII 47),

 - negacji alternatywy, tj. NOR, symbol ‘-’ (kod ASCII 45),

realizowanych w kolejności ustalonej ich łącznością lewostronną, np. 0+1+2+3=((0+1)+2)+3, przy jednoczesnym zachowaniu jednakowego priorytetu rozważanych działań. Dodatkowo łączna liczba zmiennych zdaniowych występujących w wyrażeniu W, z uwzględnieniem krotności ich powtórzeń, jest równa m.

Ustal, czy wyrażenie W jest tautologiom rachunku zdań. Dodatkowo podaj liczbę wartościowań zmiennych zdaniowych, dla których rozważane wyrażenie jest kolejno prawdziwe albo fałszywe.



WEJŚCIE

Wiersz zawierający liczby n, oraz m oddzielone znakiem odstępu  (kod ASCII 32) i zakończony znakiem nowej linii (kod ASCII 10). Następnie wiersz opisujący elementy wyrażenia W oddzielone znakiem odstępu.



WYJŚCIE

Wiersz zakończony znakiem nowej linii, zawierający słowo odpowiednio TAK/NIE (w zależności od rozwiązania zadania) oraz liczby naturalne reprezentujące liczby wartościowań zmiennych zdaniowych, dla których wyrażenie W jest stosownie prawdziwe albo fałszywe, oddzielone znakiem odstępu.



OGRANICZENIA

Liczba n dostępnych zmiennych zdaniowych zawarta w przedziale od 1 do 2^4. Liczba m zmiennych zdaniowych występujących w wyrażeniu W, z uwzględnieniem krotności ich powtórzeń, nie mniejsza niż 1 i nie większa niz 2^20.



PRZYKŁAD 1

wejście:

2 4


p_0 + p_1 @ p_1 > p_0

wyjście:

TAK 4 0



/* KOMENTARZ DO ROZWIĄZANIA


Kolejno n=2 oraz m=4. Korzystając z klasycznych oznaczeń operatorów logicznych wyrażenie W możemy przedstawić jako


p_0 OR p_1 XOR p1 => p_0.


Dalej rozważamy cztery możliwe wartościowania zmiennych zdaniowych p_0 i p_1, oraz wyznaczamy wartość logiczną wyrażenia W względem tych wartościowań:


 - p_0=0, p_1=0, wtedy: 0 OR 0 XOR 0 => 0, czyli (((0 OR 0) XOR 0) => 0)=((0 XOR 0) => 0)=(0 => 0)=1,


 - p_0=0, p_1=1, wtedy: 0 OR 1 XOR 1 => 0, czyli (((0 OR 1) XOR 1) => 0)=((1 XOR 1) => 0)=(0 => 0)=1,


 - p_0=1, p_1=0, wtedy: 1 OR 0 XOR 0 => 1, czyli (((1 OR 0) XOR 0) => 1)=((1 XOR 0) => 1)=(1 => 1)=1,


 - p_0=1, p_1=1, wtedy: 1 OR 1 XOR 1 => 1, czyli (((1 OR 1) XOR 1) => 1)=((1 XOR 1) => 1)=(0 => 1)=1.


Ostatecznie, niezależnie od przyjętego wartościowania zmiennych p_0 i p_1 wyrażenie W jest zawsze prawdziwe, czyli jest tautologią rachunku zdań. Dodatkowo 4 wartościowania i 0 wartościowań rozważanych zmiennych zdaniowych ustala odpowiednio prawdę oraz fałsz wyrażenia W. Stąd odpowiedzią jest TAK 4 0. */



PRZYKŁAD 2

wejście:

4 8


p_1 @ p_0 / p_0 < p_3 - p_3 = p_0 < p_2 / p_2

wyjście:

NIE 12 4



PRZYKŁAD 3

wejście:

10 100


p_5 = p_8 / p_7 / p_4 - p_9 - p_9 / p_2 = p_9 / p_9 @ p_8 @ p_4 * p_6 > p_5 * p_8 @ p_7 > p_4 > p_8 < p_7 @ p_8 = p_8 * p_9 / p_5 - p_0 + p_8 @ p_2 - p_7 < p_2 * p_0 = p_9 + p_9 + p_6 - p_6 < p_3 > p_7 * p_1 - p_5 @ p_2 + p_3 < p_9 / p_1 * p_8 * p_6 = p_7 / p_8 @ p_2 < p_4 * p_0 < p_8 > p_1 > p_1 > p_4 = p_0 * p_4 - p_4 > p_9 @ p_6 = p_9 - p_7 + p_3 < p_8 = p_9 @ p_7 @ p_2 > p_2 > p_9 @ p_2 @ p_5 / p_9 > p_6 + p_0 > p_7 + p_3 @ p_5 > p_9 > p_4 @ p_8 < p_1 = p_9 > p_8 > p_6 < p_9 * p_1 = p_7 + p_8 / p_4 * p_9 = p_4 < p_2 = p_9 - p_3 > p_5 > p_2 @ p_7 - p_3 @ p_9 / p_9 * p_8 @ p_2 - p_5 - p_6

wyjście:

NIE 384 640