논리식

셰퍼 스트로크 함수(NAND)만으로 임의의 불 함수를 만들 수 있다는 사실은 잘 알려져 있다. 이 함수의 진리표는 다음과 같다.

각각 $N$개의 비트로 이루어진 두 이진수 $A$와 $B$를 더하는 상황을 생각하자. 각 수의 비트에는 최하위 비트인 $0$번부터 최상위 비트인 $N-1$번까지 번호가 매겨진다. 두 수의 합 $A+B$는 항상 $N+1$개의 비트로 나타낼 수 있으며, 그중 가장 높은 자리 비트($N$번 비트)를 오버플로 비트라고 부른다.

셰퍼 스트로크 함수만을 사용하여, 임의의 $A$, $B$에 대해 오버플로 비트의 값을 계산하는 논리식을 다음 규칙에 따라 구성하라.

1. Ai는 수 $A$의 $i$번 비트의 값을 나타내는 식이다.
2. Bi는 수 $B$의 $i$번 비트의 값을 나타내는 식이다.
3. (x|y)는 두 식 $x$, $y$에 대한 셰퍼 스트로크 함수의 결과를 나타내는 식이다.

비트 번호 $i$는 앞에 0을 붙이지 않은 십진수로 적는다. 예를 들어 $A$의 12번 비트는 A12로 적는다. 식은 규칙 3에 따라 완전히 괄호로 묶여야 하며, 공백이 있어서는 안 된다.

정수 $N$ 하나가 주어진다 ($1 \le N \le 100$).

정답은 문자열이 정확히 일치하는지로 채점되므로, 아래에 정의된 표준 식 $E_N$을 공백 없이 한 줄에 출력하라.

비트 번호 $i$(앞에 0을 붙이지 않은 십진수)에 대해 다음 세 문자열을 정의한다.

• notand(i) = (Ai|Bi)
• and(i) = ((Ai|Bi)|(Ai|Bi))
• or(i) = ((Ai|Ai)|(Bi|Bi))

여기서 Ai, Bi는 각각 문자 A 또는 B 바로 뒤에 십진수 $i$를 붙인 것이다. 다음과 같이 자리올림 식을 만든다.

• $E_1$ = and(0)
• $k = 1, 2, \ldots, N-1$에 대해, 문자열 $E_{k+1}$은 ( + notand(k) + |( + $E_k$ + | + or(k) + ))를 이어 붙인 것이다.

$E_N$을 출력하라.

참고: 스트로크 기호( | )는 십진수 코드가 124인 아스키 문자이다. 출력의 크기는 $50 \cdot N$ 바이트를 넘지 않는다.