Contests Virtual Contests Problems Submit Runs Status Rank List Forum

2882.   Strange Expression
Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 221   Accepted Runs: 113

We define the logic operators as follows (T stands for true, F stands for false)

!T = F, !F = T
T & T = T, T & F = F, F & T = F, F & F = F
T | T = T, T | F = T, F | T = T, F | F = F
T -> T = T, T -> F = F, F -> T = T, F -> F = T
In fact, all the logic expressions can be rewritten only using '!' and '→'. For example, A | B is equivalent to !A → B.

Given some expressions only contain '!', '→', '(' and ')', you should tell whether they are tautologies. ("Tautologies" means that no matter what values the variables are, the expression is always true.)

Please note the priority of '!' is higher than '→', e.g., !A→B should be considered as (!A)→B. And multiple '→' bind from left to right, e.g., A→B→C should be considered as (A→B)→C. However, !!A should be considered as !(!A).

### Input

Each line of the input contains one expression. The operators includes '!', '->', '(', ')', only. And there are 3 variances A,B,C at most.

You can assume all expressions are valid, and contain no more than 100 characters.

### Output

Output one line for each case. If the expression is tautologies, output "tautologies", or else output "not tautologies".

A->B->C
(!A->!B)->(B->A)
!!(A)

### Sample Output

not tautologies
tautologies
not tautologies

Source: TJU Team Selection Contest 2007 (5)
Submit   List    Runs   Forum   Statistics

Tianjin University Online Judge v1.3.0
Maintance:G.D.Retop. Developer: SuperHacker, G.D.Retop