11103 - WFF 'N PROOF

Problem D: WFF 'N PROOF

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 的字串，最後一組有一個 0 不用處理。

對於每組測資，輸出一個最長的 WFF。如果有多組解，任何一組都可以。如果無法湊出任合一組，輸出 "no WFF possible"，不包括雙引號。

Sample Input

qKpNq
KKN
0

Possible Output for Sample Input

KqNq
no WFF possible

---

Gordon V. Cormack