Queen Bee

A hive is a grid of $M \times M$ cells, and one larva that can become a queen bee grows in each cell. The top left cell has coordinates $(0, 0)$. Moving down one cell increases the first coordinate by 1, and moving right one cell increases the second coordinate by 1, so cell $(i, j)$ is in row $i + 1$ from the top and column $j + 1$ from the left.

On the first morning every larva has size 1. Each larva grows once a day at noon, and the growing itself takes so little time that you can ignore it. This repeats for $N$ days. In one day a larva grows by 0, 1, or 2.

The $2M - 1$ larvae in the leftmost column and the top row decide on their own how much they grow that day, and those amounts are given in the input. Read the amounts starting at the bottom left cell $(M - 1, 0)$, going up to $(0, 0)$, then turning right and going to $(0, M - 1)$. Read in this order, the amounts never decrease.

Every other larva $(i, j)$ grows after the three larvae to its left $(i, j - 1)$, to its upper left $(i - 1, j - 1)$, and above it $(i - 1, j)$ have finished growing. It follows one of those three and grows by the same amount that one grew. Which one it follows is decided by the triple of amounts the three larvae grew, written in that order. There are 27 triples, and for the same triple two larvae can follow different neighbours. The choice each larva makes for each triple is given in the input.

Find the size of every larva on the evening of the last day, day $N$.

The first line contains the side length $M$ ($2 \le M \le 700$) and the number of days $N$ ($1 \le N \le 10^6$). The sizes on the first morning are all 1, so they are not given in the input.

The next $(M - 1) \times (M - 1)$ lines give the choices of the larvae that follow a neighbour, in the row major order $(1, 1), (1, 2), \dots, (1, M - 1), (2, 1), \dots, (M - 1, M - 1)$. Each line is a string of length 27 made only of the letters L, D and U. When the left larva grew by $a$, the upper left larva grew by $b$, and the upper larva grew by $c$, the larva follows the neighbour written at character $9a + 3b + c$ of that string, counting the first character as character 0. That is the order you get by sorting the triples $(a, b, c)$ ascending by $a$, then by $b$, then by $c$: $(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 0), \dots, (2, 2, 2)$. The letter L means the larva grows as much as the left larva did, D means the upper left larva, and U means the upper larva.

The next $N$ lines give, in order from the first day, how much the larvae in the leftmost column and the top row grow that day. Each line holds three integers: the number of 0s, the number of 1s, and the number of 2s in the sequence read in the order described above. That sequence never decreases, so the three counts determine it. The three numbers always add up to $2M - 1$, and any of them can be 0.

Print $M$ lines with $M$ integers each, separated by single spaces. The $j$th number on the $i$th line is the size of the larva in cell $(i - 1, j - 1)$ on the evening of the last day.