정규형

모든 불리언 식은 논리합 정규형(DNF, Disjunctive Normal Form) 또는 논리곱 정규형(CNF, Conjunctive Normal Form)으로 나타낼 수 있다. 이 문제에서 DNF는 하나 이상의 CNF 식을 OR로 연결한 식이고, CNF는 하나 이상의 DNF 식을 AND로 연결한 식이다.

AND/OR 트리는 이러한 DNF 또는 CNF 불리언 식을 트리 형태로 표현한 것이다. DNF와 CNF는 서로를 부분식으로 포함하므로, 어떤 서브 트리가 트리에서 몇 번째 레벨에 있는지만 알면 그 서브 트리가 AND 트리인지 OR 트리인지 알 수 있다.

레벨은 트리의 맨 위(루트)를 레벨 1로 하여 아래로 한 단계 내려갈 때마다 1씩 증가한다. 예를 들어 식 $(A \lor (B \land C)) \land (D \lor E)$ 를 트리로 나타내면 루트인 레벨 1과 레벨 3은 AND 트리이고 레벨 2는 OR 트리이다. 즉 홀수 레벨은 AND 트리, 짝수 레벨은 OR 트리이다.

AND/OR 트리가 주어졌을 때, 그 식의 값을 계산하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 길이는 32,000글자를 넘지 않는다.

각 트리는 다음과 같은 형식으로 주어진다.

(E1 E2 ... En)

여기서 항상 $n > 0$ 이며, 각 $E_i$ 는 값이 참인 리터럴 T, 값이 거짓인 리터럴 F, 또는 같은 형식으로 주어지는 부분식(서브 트리) 중 하나이다.

트리의 맨 위(레벨 1, 루트)는 AND 트리이다. 입력의 마지막 줄에는 () 가 주어지며, 이는 입력의 끝을 나타낸다.

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

k. E

여기서 $k$ 는 테스트 케이스의 번호(1부터 시작)이고, $E$ 는 입력으로 주어진 식의 값으로 true 또는 false 이다.