11108 - Tautology

Problem D: Tautology

WFF 'N PROOF 是一個藉由骰子玩的邏輯遊戲，骰子的六面分別有可能有的字符 K, A, N, C, E, p, q, r, s, t。Well-formed formula (WFF) 定義為一個符合以下規則的字串：

• p, q, r, s, t  都屬於 WFFs
• 如果 w 屬於 WFF, 則 Nw 屬於WFF
• 如果 w 和 x 屬於 WFFs, 則 Kwx, Awx, Cwx, Ewx 也都屬於 WFFs.

WFF 字串的意思解釋如下：

• p, q, r, s, t 是 0 (false) 或 1 (true) 的邏輯代數。
• K, A, N, C, E 分別表示 and(&), or(|), not(!), implies(→), equals(==)，真值表如下：

Definitions of K, A, N, C, and E

w  x	Kwx	Awx	Nw	Cwx	Ewx
1  1	1	1	0	1	1
1  0	0	1	0	0	0
0  1	0	1	1	1	0
0  0	0	0	1	1	1

tautology (恆真式) 在 WFF 中，不管邏輯代數的值為何，計算出來值皆為 1 (true)。
例如：
ApNp 是恆真式，p and (not p) 代入 p = 0 or p = 1 都是 1 (true)。
ApNq 不是恆真式，因為當 p = 0, q = 1 計算得到 0 (false)。

寫程式判斷  WFF 是不是恆真式。


輸入有多組測資，每組只會有一行不超過 100 字元的 WFF。
最後一行以 0 結束程式。

對於每組測資，輸出 tautology 或 not。

Sample Input

ApNp
ApNq
0

Possible Output for Sample Input

tautology
not

---

Gordon V. Cormack