CF1105D.Kilani and the Game

Kilani is playing a game with his friends. This game can be represented as a grid of size $n \times m$, where each cell is either empty or blocked, and every player has one or more castles in some cells (there are no two castles in one cell).

The game is played in rounds. In each round players expand turn by turn: firstly, the first player expands, then the second player expands and so on. The expansion happens as follows: for each castle the player owns now, he tries to expand into the empty cells nearby. The player $i$ can expand from a cell with his castle to the empty cell if it's possible to reach it in at most $s_i$ (where $s_i$ is player's expansion speed) moves to the left, up, right or down without going through blocked cells or cells occupied by some other player's castle. The player examines the set of cells he can expand to and builds a castle in each of them at once. The turned is passed to the next player after that.

The game ends when no player can make a move. You are given the game field and speed of the expansion for each player. Kilani wants to know for each player how many cells he will control (have a castle their) after the game ends.

基拉尼正在和朋友们玩一个游戏。该游戏可以表示为一个 $n \times m$ 的网格，其中每个格子要么为空，要么被阻塞；每位玩家在某些格子中拥有一座或多座城堡（同一格子中不会出现两座城堡）。

游戏按轮次进行。在每一轮中，玩家依次进行扩张：首先由第一位玩家扩张，然后是第二位玩家，依此类推。扩张规则如下：对于当前玩家所拥有的每一座城堡，他尝试向其邻近的空格子扩张。玩家 $i$ 可以从一座属于他的城堡所在格子向某个空格子扩张，当且仅当该空格子可通过至多 $s_i$ 步（其中 $s_i$ 为该玩家的扩张速度）向上、下、左、右移动到达，且路径中不经过任何阻塞格子或其他玩家城堡所在的格子。玩家检查所有他能够扩张到的格子，并同时在这些格子中建造城堡。随后轮到下一位玩家行动。

当没有任何玩家能再进行扩张操作时，游戏结束。你将获得游戏初始地图以及每位玩家的扩张速度。基拉尼想知道：游戏结束后，每位玩家各自控制（即拥有城堡）的格子数量是多少？

The first line contains three integers $n$, $m$ and $p$ ($1 \le n, m \le 1000$, $1 \le p \le 9$) — the size of the grid and the number of players.

The second line contains $p$ integers $s_i$ ($1 \le s \le 10^9$) — the speed of the expansion for every player.

The following $n$ lines describe the game grid. Each of them consists of $m$ symbols, where '.' denotes an empty cell, '#' denotes a blocked cell and digit $x$ ($1 \le x \le p$) denotes the castle owned by player $x$.

It is guaranteed, that each player has at least one castle on the grid.

第一行包含三个整数 $n$、$m$ 和 $p$（$1 \le n, m \le 1000$，$1 \le p \le 9$）—— 分别表示网格的尺寸以及玩家数量。

第二行包含 $p$ 个整数 $s_i$（$1 \le s_i \le 10^9$）—— 表示每位玩家的扩张速度。

接下来的 $n$ 行描述游戏网格。每行由 $m$ 个字符组成，其中 '.' 表示空单元格，'#' 表示被阻挡的单元格，数字 $x$（$1 \le x \le p$）表示属于玩家 $x$ 的城堡。

保证每位玩家在网格中至少拥有一座城堡。

Print $p$ integers — the number of cells controlled by each player after the game ends.

输出 $p$ 个整数——游戏结束后每位玩家所控制的格子数量。

The picture below show the game before it started, the game after the first round and game after the second round in the first example:

In the second example, the first player is "blocked" so he will not capture new cells for the entire game. All other player will expand up during the first two rounds and in the third round only the second player will move to the left.

下图展示了第一个样例中游戏开始前、第一轮结束后以及第二轮结束后的状态：

在第二个样例中，第一位玩家被“封锁”，因此在整个游戏中都无法占领新的格子。其余所有玩家将在前两轮中向上扩张；而在第三轮中，仅有第二位玩家向左移动。