배열 돌리기 6

시간 제한1초메모리 제한512 MB

요약

2^N x 2^N 격자에 대해 크기 2^l인 블록을 뒤집거나 회전하고 블록 자체를 재배치하는 연산을 R번 순서대로 적용한 뒤 결과 격자를 출력한다.

난이도: 보통10점 중 6점
유형: 구현, 시뮬레이션, 행렬, 분할 정복
정답자: 아직 제출이 없습니다

문제

크기가 $2^N \times 2^N$ 인 배열이 있을 때, 배열에 연산을 $R$ 번 적용하려고 한다. 연산은 8가지가 있고, 연산에는 단계 $\ell$ ( $0 \le \ell < N$ )이 있다. 단계 $\ell$ 은 배열을 부분 배열로 나눌 때 사용하는 값이며, 부분 배열의 크기는 $2^\ell \times 2^\ell$ 가 되어야 한다. 단계는 연산을 수행할 때마다 정한다.

다음은 크기가 $2^3 \times 2^3$ 인 배열을 단계 $\ell$ 의 값에 따라 부분 배열로 나눈 것이다. 같은 부분 배열은 같은 색상으로 표시했다.



$\ell = 0$	$\ell = 1$	$\ell = 2$

1번 연산은 각 부분 배열을 상하 반전시키는 연산이다.



배열	$\ell = 1$ , 1번 연산 적용

2번 연산은 각 부분 배열을 좌우 반전시키는 연산이다.



배열	$\ell = 2$ , 2번 연산 적용

3번 연산은 각 부분 배열을 오른쪽으로 90도 회전시키는 연산이다.



배열	$\ell = 1$ , 3번 연산 적용

4번 연산은 각 부분 배열을 왼쪽으로 90도 회전시키는 연산이다.



배열	$\ell = 2$ , 4번 연산 적용

5, 6, 7, 8번 연산은 부분 배열을 한 칸으로 생각하고 적용시킨다. 즉, 부분 배열의 안에 있는 값은 변하지 않는다.

5번 연산은 배열을 상하 반전시키는 연산이다.



배열	$\ell = 2$ , 5번 연산 적용

6번 연산은 배열을 좌우 반전시키는 연산이다.



배열	$\ell = 1$ , 6번 연산 적용

7번 연산은 오른쪽으로 90도 회전시키는 연산이다.



배열	$\ell = 1$ , 7번 연산 적용

8번 연산은 왼쪽으로 90도 회전시키는 연산이다.



배열	$\ell = 2$ , 8번 연산 적용

입력

첫째 줄에 $N$ , $R$ 이 주어진다. 둘째 줄부터 $2^N$ 개의 줄에 배열의 원소 $A[i][j]$ 가 주어진다. $i$ 번째 줄의 $j$ 번째 정수는 $A[i][j]$ 를 의미한다.

다음 $R$ 개의 줄에 배열에 적용시켜야 하는 연산이 한 줄에 하나씩 주어진다. 연산은 두 정수 $k$ , $\ell$ 로 이루어져 있고, $k$ 번 연산을 단계 $\ell$ 로 적용한다는 의미이다.

출력

입력으로 주어진 배열에 $R$ 개의 연산을 순서대로 수행한 결과를 출력한다.

제한

$1 \le N \le 7$
$1 \le R \le 1,000$
$1 \le k \le 8$
$0 \le \ell < N$
$-999 \le A[i][j] \le 999$

예제4

예제 1

입력

3 8
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
1 1
2 2
3 1
4 2
5 2
6 1
7 1
8 2

예상 출력

64 63 62 61 60 59 58 57
56 55 54 53 52 51 50 49
48 47 46 45 44 43 42 41
40 39 38 37 36 35 34 33
32 31 30 29 28 27 26 25
24 23 22 21 20 19 18 17
16 15 14 13 12 11 10 9
8 7 6 5 4 3 2 1

예제 2

입력

3 4
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
1 0
2 0
3 0
4 0

예상 출력

1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

예제 3

입력

3 4
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
5 0
6 0
7 0
8 0

예상 출력

64 63 62 61 60 59 58 57
56 55 54 53 52 51 50 49
48 47 46 45 44 43 42 41
40 39 38 37 36 35 34 33
32 31 30 29 28 27 26 25
24 23 22 21 20 19 18 17
16 15 14 13 12 11 10 9
8 7 6 5 4 3 2 1

예제 4

입력

3 8
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
1 2
8 1
7 2
4 0
3 2
5 1
6 1
2 2

예상 출력

45 37 47 39 41 33 43 35
46 38 48 40 42 34 44 36
61 53 63 55 57 49 59 51
62 54 64 56 58 50 60 52
13 5 15 7 9 1 11 3
14 6 16 8 10 2 12 4
29 21 31 23 25 17 27 19
30 22 32 24 26 18 28 20