여왕벌

크기가 $M \times M$인 격자 모양 벌집이 있다. 각 칸에서 여왕벌이 될 애벌레가 한 마리씩 자란다.

좌표는 다음과 같이 정한다. 가장 왼쪽 위 칸이 $(0,0)$이다. 아래로 한 칸 내려갈 때마다 앞의 수가 1씩 커져서 $(1,0)$, $(2,0)$ 순으로 이어진다. 칸 $(i,0)$에서 오른쪽으로 한 칸 갈 때마다 뒤의 수가 1씩 커져서 $(i,1)$, $(i,2)$ 순으로 이어진다.

애벌레는 매일 정오에 한 번 자란다. 자라는 데 걸리는 시간은 매우 짧아 무시한다. 첫날 아침 모든 애벌레의 크기는 1이고, 이 과정을 $N$일 동안 반복한다.

애벌레가 하루에 자라는 정도는 0, 1, 2 중 하나이다. 자라는 정도를 정하는 규칙은 다음과 같다.

1. 가장 왼쪽 열과 가장 위쪽 행에 있는 애벌레는 자라는 정도를 스스로 정한다. 이 값은 입력으로 주어진다. 가장 왼쪽 아래 칸에서 시작해 위로 올라가고, 맨 위 칸에 도착하면 오른쪽으로 행 끝까지 이동하면서 자라는 정도를 읽는다고 하자. 모든 입력에서 이렇게 읽은 값의 수열은 감소하지 않는다.
2. 나머지 애벌레는 자신의 왼쪽(L), 왼쪽 위(D), 위쪽(U)에 있는 애벌레가 모두 자란 다음, 그 세 마리 중 그날 가장 많이 자란 애벌레만큼 자란다.

$M = 4$, $N = 2$인 예를 보자. 첫날 아침 각 칸에 있는 애벌레의 크기는 다음과 같다.

가장 왼쪽 열과 가장 위쪽 행에 있는 애벌레 7마리가 이틀 동안 자라는 정도를 위에서 설명한 순서대로 읽으면 다음과 같다고 하자.

• 1일: 0, 0, 1, 1, 1, 2, 2
• 2일: 1, 1, 1, 1, 1, 1, 2

첫날 저녁에 애벌레의 크기는 다음과 같다. 예를 들어 좌표 $(1,1)$의 애벌레는 왼쪽 애벌레가 1만큼, 왼쪽 위 애벌레가 1만큼, 위쪽 애벌레가 1만큼 자랐으므로 자신도 1만큼 자란다. 좌표 $(3,3)$의 애벌레는 같은 규칙에 따라 2만큼 자란다.

둘째 날이 지나면 같은 과정을 거쳐 다음과 같이 된다.

격자의 크기, 날짜 수, 날짜별로 가장 왼쪽 열과 가장 위쪽 행의 애벌레가 자라는 정도를 입력받아 마지막 날 저녁의 애벌레 크기를 출력하는 프로그램을 작성하라.

첫 줄에 격자 한 변의 길이 $M$ ($2 \le M \le 700$)과 날짜 수 $N$ ($1 \le N \le 1{,}000{,}000$)이 공백으로 구분되어 주어진다. 첫날 아침의 애벌레 크기는 모두 1이므로 입력에 주어지지 않는다.

다음 $N$개의 줄에는 첫날부터 순서대로 그날 가장 왼쪽 열과 가장 위쪽 행의 애벌레가 자라는 정도가 주어진다. 문제에서 설명한 순서로 읽은 $2M-1$개의 값은 감소하지 않으므로, 각 줄에는 그 수열에 들어 있는 0의 개수, 1의 개수, 2의 개수를 차례로 준다. 세 값의 합은 항상 $2M-1$이고, 셋 중에 0인 값이 있을 수 있다.

$M$개의 줄에 각각 $M$개의 자연수를 공백으로 구분해 출력한다. $i$번째 줄의 $j$번째 수는 좌표 $(i-1, j-1)$에 있는 애벌레의 마지막 날 저녁 크기이다.