Queen Bee

A beehive is an $M \times M$ grid. One larva that will become a queen bee grows in each cell.

Coordinates are set like this. The top left cell is $(0,0)$. Each step down increases the first number by 1, giving $(1,0)$, $(2,0)$, and so on. Each step right from cell $(i,0)$ increases the second number by 1, giving $(i,1)$, $(i,2)$, and so on.

Every larva grows once a day, at noon. The growing takes so little time that you can ignore it. On the morning of the first day every larva has size 1, and the process repeats for $N$ days.

A larva grows by 0, 1, or 2 in a day. The rules that fix the amount are these.

1. The larvae in the leftmost column and in the top row decide their own growth. Those amounts are given in the input. Read them starting at the bottom left cell, moving up to the top left cell, then moving right to the end of the top row. In every input the sequence read this way is non-decreasing.
2. Every other larva waits until the larvae to its left (L), to its upper left (D), and above it (U) have grown, then grows by as much as whichever of those three grew the most that day.

Here is an example with $M = 4$ and $N = 2$. The sizes on the morning of the first day are:

Suppose that the growth of the 7 larvae in the leftmost column and the top row, read in the order described above, is:

• Day 1: 0, 0, 1, 1, 1, 2, 2
• Day 2: 1, 1, 1, 1, 1, 1, 2

On the evening of the first day the sizes are as follows. For example, the larva at $(1,1)$ has a left neighbour that grew by 1, an upper left neighbour that grew by 1, and an upper neighbour that grew by 1, so it grows by 1 too. The larva at $(3,3)$ grows by 2 under the same rule.

After the second day the same process gives:

Write a program that reads the grid size, the number of days, and the daily growth of the larvae in the leftmost column and the top row, then prints the size of every larva on the evening of the last day.

The first line contains the side length of the grid $M$ ($2 \le M \le 700$) and the number of days $N$ ($1 \le N \le 1{,}000{,}000$), separated by a space. The sizes on the first morning are all 1, so they are not given.

Each of the next $N$ lines describes one day, in order from the first day, and gives the growth of the larvae in the leftmost column and the top row on that day. The $2M-1$ values read in the order described in the statement are non-decreasing, so each line gives the number of 0s, the number of 1s, and the number of 2s in that sequence, in that order. The three numbers always add up to $2M-1$, and any of them can be 0.

Print $M$ lines with $M$ natural numbers each, separated by spaces. The $j$-th number on the $i$-th line is the size of the larva at coordinate $(i-1, j-1)$ on the evening of the last day.