G++ 언어

세계 최고의 천재 교준이는 몇 년간의 연구 끝에 새로운 프로그래밍 언어 G++를 만들었다! G++는 다음과 같은 연산을 지원한다:

• "INPUT $x$": 입력에서 정수 하나를 읽어 $x$번 메모리에 쓴다. 더 이상 읽을 정수가 없으면 Input Error가 발생한다.
• "NOT $x$ $y$": $x$번 메모리에 쓰인 값의 논리적 부정을 $y$번 메모리에 쓴다.
• "BNOT $x$ $y$": $x$번 메모리에 쓰인 값의 비트 NOT을 $y$번 메모리에 쓴다.
• "AND $n$ $x\_1$ … $x\_n$ $y$": $x\_1$ … $x\_n$번 메모리에 쓰인 $n$개의 값을 비트 AND한 결과를 $y$번 메모리에 쓴다. $x\_1$, …, $x\_n$은 모두 달라야 하며, $n≥2$여야 한다. 이를 만족하지 않으면 Index Error가 발생한다.
• "OR $n$ $x\_1$ … $x\_n$ $y$": $x\_1$ … $x\_n$번 메모리에 쓰인 $n$개의 값을 비트 OR한 결과를 $y$번 메모리에 쓴다. $x\_1$, …, $x\_n$은 모두 달라야 하며, $n≥2$여야 한다. 이를 만족하지 않으면 Index Error가 발생한다.
• "XOR $n$ $x\_1$ … $x\_n$ $y$": $x\_1$ … $x\_n$번 메모리에 쓰인 $n$개의 값을 비트 XOR한 결과를 $y$번 메모리에 쓴다. $x\_1$, …, $x\_n$은 모두 달라야 하며, $n≥2$여야 한다. 이를 만족하지 않으면 Index Error가 발생한다.
• "LSHIFT $x\_1$ $x\_2$ $y$": $x\_1$번 메모리에 쓰인 값을 $x\_2$번 메모리에 쓰인 값만큼 비트 왼쪽 시프트한 결과를 $y$번 메모리에 쓴다.
• "RSHIFT $x\_1$ $x\_2$ $y$": $x\_1$번 메모리에 쓰인 값을 $x\_2$번 메모리에 쓰인 값만큼 비트 오른쪽 시프트한 결과를 $y$번 메모리에 쓴다.

G++ 코드는 가장 첫 번째 연산부터 순서대로 실행된다. 실행 즉시 int형 변수 $10^3$개를 담을 메모리가 할당된다. 코드가 $x$번 메모리에 접근한다면 $0≤x<10^3$이어야 하며, 그렇지 않으면 Memory Error가 발생한다. 실행 초기에 $10^3$개의 변수는 모두 $0$으로 초기화되어 있다.

G++ 코드의 총 연산 횟수는 $10^5$을 넘지 않아야 한다. 넘으면 Time Limit Exceeded Error가 발생한다.

G++ 코드의 총 메모리 접근 횟수는 $10^5$을 넘지 않아야 한다. 넘으면 Access Limit Exceeded Error가 발생한다.

교준이는 완벽주의자다. 따라서 G++ 코드에는 불필요한 공백이나 개행이 있으면 안 된다. 또한 G++ 코드의 마지막 문자는 개행 문자여야 한다. 그렇지 않으면 Compile Error가 발생한다.

더불어 G++ 코드가 Undefined Behavior를 일으키려 하면 Runtime Error가 발생한다. G++ 코드를 실행할 때 Undefined Behavior가 발생하는 경우는 다음과 같다:

• $x$를 $y$만큼 비트 왼쪽 시프트할 때, $y≥0$과 $x × 2^y < 2^{31}$을 모두 만족해야 한다. 또한 $x<0$이면 $y=0$이어야 한다. 그렇지 않으면 Undefined Behavior가 발생한다.
• $x$를 $y$만큼 비트 오른쪽 시프트할 때, $y≥0$을 만족하지 않으면 Undefined Behavior가 발생한다.

입력이 "2 16 5"일 때 다음과 같은 G++ 코드를 실행하면 4번 메모리에 쓰인 값은 5다.

INPUT 2
NOT 2 3
NOT 3 2
INPUT 0
INPUT 0
XOR 3 0 1 2 1
OR 3 3 1 2 4

이제 다음 문제를 G++로 풀어야 한다:

가로 $W$칸, 세로 $H$칸인 크기 $H×W$의 이차원 격자판이 있다. 격자판의 가장 왼쪽 윗칸의 좌표는 $(0, 0)$, 가장 오른쪽 아랫칸의 좌표는 $(H-1, W-1)$이다. 좌표 $(i, j)$인 칸에는 수 $A_{i×W+j}$가 적혀 있다.

격자판에서 왼쪽 위의 좌표가 $(a, b)$, 오른쪽 아래의 좌표가 $(c, d)$인 직사각형을 생각하자. 이 직사각형에 포함된 칸에 적힌 수의 합을 $S$라 하자. 여러분은 다음과 같은 입력에 대하여, 실행 후 0번 메모리에 쓰인 값이 $S$이고 이를 제외한 나머지 메모리에 쓰인 값이 전부 $0$이 되도록 하는 G++ 코드를 작성해야 한다.

G++ 프로그램에 제공되는 입력은 다음과 같다:

$H$ $W$ $A_0$ $A_1$ … $A_{H×W-1}$ $a$ $b$ $c$ $d$

여러분에게는 오직 두 정수 $H$, $W$가 주어진다. 즉, 여러분이 제출하는 코드는 $H$와 $W$의 값만 읽어들일 수 있다. $A_0$, …, $A_{H×W-1}$, $a$, $b$, $c$, $d$의 값은 제공되지 않음에 유의하라.

실행 후 0번 메모리에는 $S$가, 그 밖의 모든 메모리에는 $0$이 적혀 있어야 한다. G++ 코드를 출력하라.

모든 데이터는 다음 조건을 만족한다:

• $H$, $W$, $A_0$, …, $A_{H×W-1}$는 모두 자연수다.
• $H×W≤16$.
• $0 ≤ i < H×W$를 만족하는 모든 정수 $i$에 대하여, $A_i ≤ 100$.
• $a$, $b$, $c$, $d$는 모두 정수다.
• $0 ≤ a ≤ c < H$, $0 ≤ b ≤ d < W$.