N x M 크기의 격자판 위에 카카오 앱들이 존재합니다. 격자에서 가장 왼쪽 위칸은 1행 1열, 가장 오른쪽 아래칸은 N행 M열입니다. 모든 앱들은 정사각형 모양이며 크기는 제각각 다를 수 있습니다.

예를 들어, N = 6, M = 8일 때 아래 그림과 같이 앱들이 배치되어 있습니다.

• 6개의 앱이 격자판 위에 존재합니다.

당신은 해당 앱들 중 하나를 골라 상하좌우 중 한 방향으로 한 칸 밀 수 있습니다. 이때, 해당 방향에 다른 앱이 존재한다면 해당 앱도 같은 방향으로 한 칸 밀려납니다. 위 예시에서 카카오톡 앱을 오른쪽으로 한 칸 밀면 아래와 같이 됩니다.

• 빨간색으로 표시된 카카오톡 앱을 오른쪽으로 한 칸 밉니다.
• 초록색으로 표시된 4개의 앱들은 카카오톡에 의해 영향을 받은 앱들을 나타냅니다.

만약 앱이 격자 밖으로 이동하게 된다면, 해당 앱은 격자 반대편으로 이어져 나오게 됩니다. 이때, 크기가 2x2 이상인 앱은 한 칸이라도 격자 밖으로 이동하게 되면 반대편으로 이동하게 됩니다. 격자 반대편으로 이동할 때 해당 위치에 다른 앱이 있다면 그 앱도 같은 방향으로 밀려납니다. 위 예시에서 카카오톡 앱을 오른쪽으로 한 칸 밀면 아래와 같이 됩니다.

• 카카오 뱅크앱이 격자 밖으로 이동하게 되어 격자 반대편으로 이동하게 됩니다.
• 카카오 웹툰앱(w)의 일부가 격자 밖으로 이동하게 되어 격자 반대편으로 이동하게 됩니다. 이 과정에서 카카오 뮤직 앱이 오른쪽으로 밀리게 됩니다.

격자와 앱의 위치 정보를 담은 2차원 정수 배열 board와 앱의 이동 명령을 순서대로 담은 2차원 정수 배열 commands가 매개변수로 주어집니다. 주어진 규칙에 따라 앱을 이동시킨 후 앱의 위치 정보를 2차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 2 ≤ board의 길이 = N ≤ 10
  • 2 ≤ board[i]의 길이 = M ≤ 10
  • 0 ≤ board[i][j] ≤ 100
  • board[i][j]는 앱의 유일한 ID를 나타내며, board의 i+1번째 행 j+1번째 열에 ID가 board[i][j]인 앱이 존재함을 나타냅니다. 각 앱의 ID는 1번부터 앱의 가짓수번까지 번호가 붙어 있습니다.
  • board[i][j]가 같은 원소면 정사각형 모양으로 붙어 있습니다.
  • board[i][j]가 0이면 해당 격자는 빈 칸임을 나타냅니다.
• 1 ≤ commands의 길이 ≤ 1,000
  • commands[i]는 [ID, arrow]형태로 ID가 ID인 앱을 arrow방향으로 한 칸 움직임을 나타냅니다.
  • 1 ≤ ID ≤ board[i][j]의 최댓값
  • 1 ≤ arrow ≤ 4
  • 1은 오른쪽, 2는 아래쪽, 3은 왼쪽, 4는 위쪽 방향을 나타냅니다.

테스트 케이스 구성 안내

아래는 테스트 케이스 구성을 나타냅니다. 각 그룹은 하나 이상의 하위 그룹으로 이루어져 있으며, 하위 그룹의 모든 테스트 케이스를 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.

입출력 예

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

아래 그림과 같이 앱들이 배치되어 있습니다.

2번 앱(카카오 뮤직)을 오른쪽으로 한 칸 움직이면 아래와 같이 됩니다.

3번 앱(카카오 페이)을 오른쪽으로 한 칸 움직이면 아래와 같이 됩니다.

9번 앱(카카오톡)을 아래쪽으로 한 칸 움직이면 아래와 같이 됩니다. 카카오 웹툰 앱이 위쪽으로 이동하게 되어 카카오톡 앱이 아래로 한 칸 더 밀립니다.

4번 앱(카카오 페이지)을 오른쪽으로 한 칸 움직이면 아래와 같이 됩니다.

입출력 예 #3

아래 그림과 같이 앱이 배치되어 있습니다.

1번 앱(프로그래머스)을 위쪽으로 한 칸 움직이면 아래와 같이 됩니다.

1번 앱(프로그래머스)을 왼쪽으로 한 칸 움직이면 아래와 같이 됩니다.

1번 앱(프로그래머스)을 아래쪽으로 한 칸 움직이면 아래와 같이 됩니다.