Wizard Shark and Blizzard

Wizard Shark can cast Fireball, Tornado, Firestorm, Water Copy Bug, and Vivara magic. The magic he learned today is Blizzard, and he is going to practice it on an N×N grid. N is always odd, and (r, c) means row r, column c of the grid. The top-left cell of the grid is (1, 1), the bottom-right cell is (N, N), and Wizard Shark is at ((N+1)/2, (N+1)/2).

Walls stand between some pairs of adjacent cells. Below are examples for N = 3, 5, 7. A solid line is a wall and a dashed line is not a wall. The number written in a cell is the cell's index.

N = 3	N = 5	N = 7

Initially, every cell except the one the shark occupies can hold one marble. Marbles come in type 1, type 2, and type 3. If marbles with the same number occupy consecutive-index cells, they are called consecutive marbles. Below is an example for N = 7.

To cast Blizzard magic, the shark chooses a direction di and a distance si. There are four directions ↑, ↓, ←, →, written as the integers 1, 2, 3, 4. The shark throws ice shards in direction di at every cell within distance si, destroying all marbles in those cells. A destroyed marble leaves its cell empty. The ice shards pass over walls, so walls are not destroyed.

The next example uses direction down and distance 2.

Ice shards fall on the cells marked in red.	After the marbles are destroyed.

If the cell whose index is one less than that of a cell A is empty, the marble in A moves to that empty cell. This movement repeats until no marble moves any further. So after marbles are destroyed, the empty cells that appear make marbles move, and the result after all marbles have moved is as follows.

Now comes the explosion step. Explosions happen when four or more consecutive marbles exist. In the figures below, the left figure marks the cells containing marbles that explode in the above state in blue and green, and the right figure shows the state after the marbles explode.

Before the marbles explode.	After the marbles explode.

The explosion left empty cells, so the marbles move again. After they move, the explosion step happens again, and this repeats until no more marbles explode. In the state after the explosion, the marbles move as follows.

This state has four or more consecutive marbles, so the marbles explode once more.

Before the marbles explode.	After the marbles explode and move.

Now that no more marbles explode, the transformation step begins. Consecutive marbles form one group. In the figure below, type 1 marbles are red, type 2 marbles are blue, and type 3 marbles are purple.

One group turns into two marbles A and B. Marble A's number is the count of marbles in the group, and B is the number of the marbles making up the group. The marbles go back into cells in group order, starting from cell 1, in the order A, B. The figure below shows the state after the transformation, using the same colors as the groups in the figure above. If there are more marbles than cells and some cannot fit, those marbles disappear.

Wizard Shark has cast Blizzard M times in total. Given the information on the cast magic, find 1×(number of exploded type 1 marbles) + 2×(number of exploded type 2 marbles) + 3×(number of exploded type 3 marbles).

The first line gives N and M. From the second line, N lines give the information on the marbles in the grid. The c-th integer of the r-th row is the number of the marble in (r, c). If a cell has no marble, 0 is given. The cell the shark occupies is always 0 as well.

The following M lines give the direction di and distance si of a Blizzard magic, one per line, in the order the magic was cast.

On the first line, print 1×(number of exploded type 1 marbles) + 2×(number of exploded type 2 marbles) + 3×(number of exploded type 3 marbles).

• 3 ≤ N ≤ 49
• N is odd
• 1 ≤ M ≤ 100
• 1 ≤ di ≤ 4
• 1 ≤ si ≤ (N-1)/2
• If the cells hold K marbles, the indices of the cells holding marbles are 1 through K.
• The grid given as input has no four or more consecutive marbles.