시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.1 초 (추가 시간 없음) 256 MB126361321.667%

문제

세계 최고 천재인 교준이는 몇 년간의 심도 있는 연구 끝에 새로운 프로그래밍 언어 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 $.

예제 입력 1

1 1

예제 출력 1

INPUT 0
INPUT 0
INPUT 0

$ H = W = 1 $이므로 $ a = b = c = d = 0 $다. 따라서 $ S = A_0 $다.
위의 G++ 코드를 실행할 경우, 항상 0번 메모리에는 $A_0$이 적혀있다.
고로 위의 출력은 올바르다.

출처

  • 문제를 만든 사람: yclock

채점 및 기타 정보

  • 예제는 채점하지 않는다.