여왕벌

$M \times M$ 격자 모양의 벌집이 있고, 각 칸에서 여왕벌이 될 애벌레가 한 마리씩 자란다. 제일 왼쪽 위 칸의 좌표는 $(0, 0)$이다. 한 칸 아래로 내려가면 첫 번째 좌표가 1 커지고, 한 칸 오른쪽으로 가면 두 번째 좌표가 1 커진다. 곧 칸 $(i, j)$는 위에서 $i + 1$번째 행, 왼쪽에서 $j + 1$번째 열에 있다.

첫날 아침 모든 애벌레의 크기는 1이다. 애벌레는 매일 정오에 한 번 자라며, 자라는 데 걸리는 시간은 무시할 만큼 짧다. 이 과정을 $N$일 동안 반복한다. 하루에 자라는 정도는 0, 1, 2 중 하나다.

제일 왼쪽 열과 제일 위쪽 행에 있는 애벌레 $2M - 1$마리는 그날 얼마나 자랄지 스스로 정하고, 그 값은 입력으로 주어진다. 이 값들을 제일 왼쪽 아래 칸 $(M - 1, 0)$에서 시작해 위로 올라가며 읽고, $(0, 0)$에 도착하면 오른쪽으로 이동하며 $(0, M - 1)$까지 읽는다. 이렇게 읽은 수열은 감소하지 않는다.

나머지 애벌레 $(i, j)$는 왼쪽 $(i, j - 1)$, 왼쪽 위 $(i - 1, j - 1)$, 위쪽 $(i - 1, j)$의 세 애벌레가 모두 자란 뒤에 자란다. 이 애벌레는 세 애벌레 중 하나를 골라 그 애벌레가 자란 만큼 자란다. 누구를 따를지는 세 애벌레가 자란 정도를 이 순서로 적은 순서쌍이 정한다. 순서쌍은 27가지이고, 같은 순서쌍이라도 따르는 대상은 애벌레마다 다를 수 있다. 애벌레마다 정해진 이 대응 관계는 입력으로 주어진다.

마지막 날 저녁, 곧 $N$일째 저녁의 모든 애벌레의 크기를 구하라.

첫 줄에 벌집 한 변의 칸 수 $M$ ($2 \le M \le 700$)과 날짜 수 $N$ ($1 \le N \le 10^6$)이 주어진다. 첫날 아침의 크기는 모두 1이므로 입력에 주어지지 않는다.

다음 $(M - 1) \times (M - 1)$개의 줄에는 다른 애벌레를 따라 자라는 애벌레의 대응 관계가 $(1, 1), (1, 2), \dots, (1, M - 1), (2, 1), \dots, (M - 1, M - 1)$의 행 우선 순서로 주어진다. 각 줄은 L, D, U로만 이루어진 길이 27인 문자열이다. 왼쪽 애벌레가 $a$, 왼쪽 위 애벌레가 $b$, 위쪽 애벌레가 $c$만큼 자란 경우에 따를 대상은 이 문자열의 $9a + 3b + c$번째 문자에 적혀 있다. 맨 앞 문자를 0번째로 센다. 곧 순서쌍 $(a, b, c)$를 $a$, 그다음 $b$, 마지막으로 $c$에 대해 오름차순으로 정렬한 $(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 0), \dots, (2, 2, 2)$의 순서다. 문자가 L이면 왼쪽 애벌레, D이면 왼쪽 위 애벌레, U이면 위쪽 애벌레가 자란 만큼 자란다.

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

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