WFF ‘N PROOF is a logic game played with dice. Each die has six faces representing some subset of the possible symbols K, A, N, C, E, p, q, r, s, t. A Well-formed formula (WFF) is any string of these symbols obeying the following rules:

• p, q, r, s, and t are WFFs
• if w is a WFF, Nw is a WFF
• if w and x are WFFs, Kwx, Awx, Cwx, and Ewx are WFFs.

• p, q, r, s, and t are logical variables that may take on the value 0 (false) or 1 (true).
• K, A, N, C, E mean and, or, not, implies, and equals as defined in the truth table below.

A tautology is a WFF that has value 1 (true) regardless of the values of its variables. For example, ApNp is a tautology because it is true regardless of the value of p. On the other hand, ApNq is not, because it has the value 0 for p=0, q=1.

You must determine whether or not a WFF is a tautology.

Input consists of several test cases. Each test case is a single line containing a WFF with no more than 100 symbols. A line containing 0 follows the last case.

For each test case, output a line containing tautology or not as appropriate.

#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>#include <set>#include <map>#include <vector>#include <queue>#include <string>#define inf 0x3fffffff#define eps 1e-10using namespace std;struct node{    char op;    int val;    node *left;    node *right;};bool a[5];bool visit[5];int Do(char op, int x, int y){    switch (op)    {        case ‘K‘:            return x&&y;        case ‘A‘:            return x||y;        case ‘N‘:            return !x;        case ‘C‘:            return !x || y;        case ‘E‘:            return x == y;    }}bool Input(node *p){    char ch;    ch = getchar();    if (ch == ‘0‘)        return 0;    p->op = ch;    p->val = -1;    switch (ch)    {        case ‘p‘:            p->val = 0;            visit[0] = 1;            return 1;        case ‘q‘:            p->val = 1;            visit[1] = 1;            return 1;        case ‘r‘:            p->val = 2;            visit[2] = 1;            return 1;        case ‘s‘:            p->val = 3;            visit[3] = 1;            return 1;        case ‘t‘:            p->val = 4;            visit[4] = 1;            return 1;        case ‘N‘:            p->left = (node *)malloc(sizeof(node));            return Input(p->left);        default:            p->left = (node *)malloc(sizeof(node));            p->right = (node *)malloc(sizeof(node));            Input(p->left);            return Input(p->right);    }}bool caculate(node *p){    if (p->val != -1)        return a[p->val];    if (p->op == ‘N‘)        return Do(p->op, caculate(p->left), 1);    else        return Do(p->op, caculate(p->left), caculate(p->right));}bool dfs(int now, node *head){    if (now == 5)        return caculate(head);    if (visit[now] == 0)        return dfs(now+1, head);    int ii, jj;    a[now] = 0;    ii = dfs(now+1, head);    a[now] = 1;    jj = dfs(now+1, head);    return ii && jj;}bool qt(node *head){    if (dfs(0, head))        printf("tautology\n");    else        printf("not\n");}int main(){    //freopen("test.txt", "r", stdin);    node *head;    for (;;)    {        memset(visit, 0, sizeof(visit));        head = (node *)malloc(sizeof(node));        if(!Input(head))            break;        getchar();        qt(head);    }    return 0;}