Land of Riches

Mankind has recently discovered the secret wealth in Mars. Many powerful countries are trying to get hold of the riches of Mars. The map of Mars can be represented as a 2-Dimensional grid consisting of $N$ rows and $M$ columns numbered from $1$ to $N$ and $1$ to $M$. Cells can be represented with $X$ and $Y$. $X$ stands for the row and $Y$ stands for the column. Each cell contains $W_{XY}$ unit of wealth. Value of $W_{XY}$ equal to $0$ means empty cell.

$C$ countries are preparing their armies to collect as much wealth as they can. All the countries will land their armies on the same day. One day on Mars contains $24$ hours and $37$ minutes(60 minutes per hour). The army of $i^{th}$ country will land on cell $X_i$ $Y_i$. The time of landing will be given to you in format $hh:mm$. After landing on a cell, if there is any wealth in the cell they will immediately collect them. Otherwise, they will not continue their operation and return empty-handed. The time of collecting wealth is negligible. After collecting the wealth, the army will split and expand to the adjacent cells vertically and horizontally if there is any wealth in those cells. This process will be continued from each cell. If two armies try to advance in the same cell at the same time, the army with a smaller value of $i$ will get hold of the cell. Moving from one cell to another takes exactly one minute.

You have to calculate, how much wealth all the armies can collect and which army can collect how much wealth.

Input

The first line of input will consist of two integers $N$ and $M$ $(3 \leq N, M \leq 500)$.
Each of the next $N$ lines will contain $M$ integers $W$ $(0 \leq W \leq 100 )$ representing the wealth of the cell.
The next line will contain integer $C$ $(1 \leq C \leq N \times M)$.
$C$ line follows. $i^{th}$ line will contain the time of landing for the $i_{th}$ army in the format $hh_i : mm_i$$(00:00 \leq hh_i:mm_i \leq 24:36)$ and the cell $X_i, Y_i$ $(1 \leq X_i \leq N, 1 \leq Y_i \leq M)$ the army will land.

Output

In the first line print the total units of wealth $T$ that can be collected by the armies of the earth.
For the next $C$ lines, print one integer each. In the $i_{th}$ line, print the total amount of wealth will be collected by the $i_{th}$ army.

Sample

Input	Output
4 4 1 2 1 2 0 3 0 5 0 1 7 4 10 0 5 3 3 00:22 4 1 24:36 1 4 24:36 3 2	44 10 18 16
At $00:22$, the first army will land on the cell $4,1$ and collect $10$ units. At $24:36$, the $2_{nd}$ army will land on cell $1,4$ and collect 2 units. At the same time the $3_{rd}$ army will land on cell $3,2$ and collect $1$ unit. Next day, at $00:00$ the $2_{nd}$ army will spread to cells $1,3$ and $2,4$. They will collect $1$ and $5$ units respectively. At the same time, the $3_{rd}$ army will spread to cells $2,2$ and $3,3$. They will collect $3$ and $7$ units. At $00:01$ both army can occupy the cells $1,2$ and $3,4$. But the $2_{nd}$ army will occupy them because of lower $i$ value and they will collect $2$ and $4$ from these cells. At the same time, the $3_{rd}$ army will occupy cell $4,3$ and collect $5$ units. At $00:02$ the $2_{nd}$ army will occupy cells $1,1$ and $4,4$. They will collect $1$ and $3$ units from there. All the armies combined will collect $44$ units of wealth. The first, second, and third armies will collect $10$,$18$ and $16$ units respectively.