An airstrike, also known as an aerial strike, is a common long-range support tactic used in complex terrain. Typically, a scout designates a target, and the nearest friendly air support unit launches a missile to strike it. Airstrikes are characterized by high flexibility, high lethality, and a significant miss rate. Since a missile requires a certain amount of time to travel from launch to impact, it is very difficult to hit a moving target. Therefore, experienced friendly air support units will predict the target's movement and strike the estimated location at the time of arrival (rather than the target's current position). Currently, our scout GloryKen is practicing how to conduct an airstrike on a "Bloodthirsty Predator" (also known as a "Level 3 Dog"). This enemy unit moves quickly and erratically and is usually a scout's nemesis, but a single airstrike is enough to eliminate one "Level 3 Dog." The terrain can be viewed as an $N \times M$ grid, where some cells contain obstacles that are impassable. An enemy "Level 3 Dog" is located on an empty cell. Over the next period, the scout GloryKen will conduct several airstrikes against it. The process can be described in turns. The Level 3 Dog starts at coordinates $(x, y)$ and faces one of the four cardinal directions.

Each turn consists of the following stages:

1. GloryKen issues an "airstrike order," and the friendly air support unit immediately launches a missile. This missile will hit the cell $a_i$ units in front of the Level 3 Dog's current position after $a_i$ turns (here, "in front" refers to the direction the Level 3 Dog is currently facing). If this position is outside the map, the airstrike fails.
2. The Level 3 Dog performs a "move." It can move one cell up, down, left, or right (it cannot go out of bounds or enter a cell with an obstacle), or it can choose to stay in its current cell. If it moves, its orientation changes to the direction of movement; otherwise, its orientation remains unchanged.
3. All missiles previously scheduled to arrive in this turn hit their target locations simultaneously. If the Level 3 Dog is hit by a missile, it dies immediately. Missiles do not affect the terrain; they neither destroy obstacles nor create new ones.

Now, GloryKen wants to know, after $T$ turns of airstrikes, if the Level 3 Dog is still alive, where could it possibly be? You need to calculate, for each cell, how many ways the Level 3 Dog can reach that cell at the end of turn $T$ while remaining alive. Two ways are considered different if and only if the Level 3 Dog's movement choices differ in at least one turn.

Input

The first line contains three integers $N$, $M$, and $T$, representing the grid size and the number of turns. The next $N$ lines, each containing $M$ characters, describe the map:

• . represents an empty cell;
• * represents an obstacle;

• A digit (0, 1, 2, or 3) represents the position of the Level 3 Dog. There is exactly one digit in the entire map, and it is located on an empty cell. This digit indicates the Level 3 Dog's orientation:

• 0 means moving 1 step in this direction results in $x$ coordinate $+1$

• 1 means moving 1 step in this direction results in $y$ coordinate $+1$
• 2 means moving 1 step in this direction results in $x$ coordinate $-1$
• 3 means moving 1 step in this direction results in $y$ coordinate $-1$

The next $T-1$ lines each contain an integer $a_i$, representing that the airstrike missile will hit the cell $a_i$ units in front of the Level 3 Dog's current position after $a_i$ turns. Obviously, the airstrike in the $T$-th turn is meaningless, so the input does not contain information for the $T$-th turn's airstrike.

Output

Output $N$ lines, each containing $M$ integers separated by a space, representing the number of ways the Level 3 Dog can reach that cell at the end of turn $T$ while remaining alive (although the answer for cells with obstacles must be 0, please output this value for the sake of formatting). To avoid large numbers, output all answers modulo $1\,000\,000\,007$.

Examples

Input 1

3 2 2
1.
*.
..
1

Output 1

2 0
0 1
0 0

Note 1

Initially, the Level 3 Dog is at (1, 1) facing right. Turn 1, Stage 1: An airstrike is scheduled to hit 1 cell in front of the dog (i.e., (1, 2)) after 1 turn (at turn 2). Turn 1, Stage 2: The dog can choose to stay (1, 1, right) or move forward (1, 2, right). Turn 1, Stage 3: No missiles arrive.

Turn 2, Stage 1: This is the last turn, the airstrike is meaningless. Turn 2, Stage 2: The dog moves. If it previously chose to stay (1, 1, right), it can now choose to stay (1, 1, right) or move forward (1, 2, right). If it previously chose to move forward (1, 2, right), it can now choose to stay (1, 2, right), move left (1, 1, left), or move down (2, 2, down). Turn 2, Stage 3: The missile arrives at (1, 2); if the dog is at (1, 2) at this time, it is killed.

In summary, there are two ways for the dog to be at (1, 1) and alive at the end of turn 2, and one way for it to be at (2, 2) and alive.

Constraints

For $100\%$ of the data, $1 \le N, M \le 20$, $1 \le a_i \le 12$, $1 \le T \le 50$.