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.


-----Input-----

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.


-----Output-----

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


-----Examples-----
Input
3 3 2
1 1
1..
...
..2

Output
6 3 

Input
3 4 4
1 1 1 1
....
#...
1234

Output
1 4 3 3 



-----Note-----

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:

 [Image] 

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.

Difficulty: interview

Starter code:

Solutions:
n, m, p = list(map(int, input().split()))
speeds = list(map(int, input().split()))

field = []
for _ in range(n):
    s = list(input().strip())
    field.append(s)


def neighbours(i, j):
    for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        if 0 <= i+di < n and 0 <= j+dj < m:
            yield i+di, j+dj

def colors():
    return [str(i) for i in range(1, p+1)]


edges = {c:[] for c in colors()}
for c in colors():
    for i in range(n):
        for j in range(m):
            if field[i][j] == c:
                if not all(field[n_i][n_j] == c for (n_i, n_j) in neighbours(i, j)):
                    edges[c].append((i,j))
# print(edges)


def up_field(color):
    edge_color = edges[color]

    new_edge = []
    for (i,j) in edge_color:
        for (n_i, n_j) in neighbours(i, j):
            if field[n_i][n_j] == '.':
                field[n_i][n_j] = color
                new_edge.append((n_i, n_j))
    edges[color] = new_edge


def print_field():
    for l in field:
        print(l)
    print('-'*100)

# print_field()


while any(len(x) > 0 for x in list(edges.values())):
    for s, c in zip(speeds, colors()):
        for i in range(s):
            up_field(c)
            if len(edges[c]) == 0:
                break

    # print_field()


counts = {c:0 for c in colors()}
counts['.'] = 0
counts['#'] = 0

for i in range(n):
    for j in range(m):
        counts[field[i][j]] += 1

print(*(counts[c] for c in colors()))





from collections import defaultdict as dd, deque

n,m,p = list(map(int,input().split()))
S = [0]+[int(x) for x in input().split()]
M = [list(input())+['#'] for i in range(n)]
M.append(['#']*m)

front = [[], [],[],[],[],[],[],[],[],[]]

for i in range(n):
    for j in range(m):
        if M[i][j] not in '.#':
            a = int(M[i][j])
            front[a].append((i,j))
            M[i][j] = a

def expand(p):
    s = S[p]
    Q = deque()
    for i,j in front[p]:
        Q.append((i,j,0))

    new = False
    nfront = []
    while Q:
        i,j,d = Q.popleft()
        nfront.append((i,j))
        if d >= s:
            continue

        for di,dj in [(-1,0), (1,0), (0,1), (0,-1)]:
            if M[i+di][j+dj] == '.':
                new = True
                M[i+di][j+dj] = p
                Q.append((i+di,j+dj,d+1))

    nnfront = []
    for i,j in nfront:
        if M[i-1][j] == '.' or \
           M[i+1][j] == '.' or \
           M[i][j+1] == '.' or \
           M[i][j-1] == '.':
            nnfront.append((i,j))

    front[p] = nnfront
    return new


while any([expand(i) for i in range(1,p+1)]):
    #for _ in M:
    #    print(*_)
    pass

C = dd(int)
for i in range(n):
    for j in range(m):
        C[M[i][j]] += 1
print(*(C[i] for i in range(1,p+1)))


# import sys
#
# f = open('input1.txt', 'r')
#
#
# sys.stdin = f

n, m, p = list(map(int, input().split()))
s = list(map(int, input().split()))

q = [[] for _ in range(p)] # fromnt of each palyer
counts = [0] * p

field = []
for i in range(n):
    line = input()
    field.append([0] * m)
    for j, c in enumerate(line):
        if c == '.':
            field[i][j] = 0
        elif c == '#':
            field[i][j] = -1
        else:
            # player
            pi = int(c)
            field[i][j] = pi
            counts[pi-1] += 1

def get_neibs(i, j):
    up = (i - 1, j) if i > 0 else None
    down = (i + 1, j) if i < n - 1 else None
    left = (i, j - 1) if j > 0 else None
    right = (i, j + 1) if j < m - 1 else None
    nbs = [up, down, left, right]
    return [a for a in nbs if a is not None]



def init_bounds(field, q):
    for i in range(n):
        for j in range(m):
            if field[i][j] > 0:
                index  = field[i][j]-1
                nbs = get_neibs(i, j)
                neib_vals = [field[a[0]][a[1]] for a in nbs]
                if 0 in neib_vals:
                    q[index].append((i, j))

def step_one(index, field, front: list):
    new_front = []

    total_add = 0
    for i, j in front:
        nbs = get_neibs(i, j)
        for a in nbs:
            if field[a[0]][a[1]] == 0:
                # if not yet added
                field[a[0]][a[1]] = index+1
                counts[index] += 1
                total_add += 1
                new_front.append(a)


    return new_front, total_add





def  step(index, field, front, speed):
    added_len = 0
    while speed > 0:
        front, added_len = step_one(index, field, front)
        speed -= 1
        if added_len == 0:
            break

    q[index] = front
    return front, added_len

init_bounds(field, q)

while True:

    progress = 0
    added = 0
    for i in range(p):
        _, added = step(i, field, q[i], s[i])
        progress += added

    if progress == 0:
        break



print(" ".join(map(str, counts)))

# f.close()


from collections import deque

n, m, p = [int(v) for v in input().split()]
s = [int(v) for v in input().split()]

d = {'.': 0, '#': 10}
d.update({str(v) : v for v in range(1, p + 1)})

field = [[d[c] for c in input().strip()] for _ in range(n)]

ans = [0] * p
dists = [[[9999999 for _ in range(m)] for _ in range(n)] for _ in range(p)]
frontiers = [deque() for _ in range(p)]
for i in range(n):
    for j in range(m):
        pp = field[i][j]
        if 1 <= pp <= 9:
            frontiers[pp - 1].append((i, j, 0))
            ans[pp - 1] += 1
            dists[pp - 1][i][j] = 0

off = [(1, 0), (0, 1), (-1, 0), (0, -1)]
curr_lim = s[:]

def dump():
    for line in field:
        print(line)
    print()

while True:
    was = False
    for pp in range(1, p + 1):
        # dump()
        while frontiers[pp - 1]:
            i, j, dist = frontiers[pp - 1].popleft()
            if field[i][j] not in (0, pp):
                continue
            if dist > curr_lim[pp - 1]:
                frontiers[pp - 1].appendleft((i, j, dist))
                break
            if field[i][j] != pp:
                field[i][j] = pp
                ans[pp - 1] += 1
                was = True
            for di, dj in off:
                ni, nj = i + di, j + dj
                if 0 <= ni < n and 0 <= nj < m and field[ni][nj] == 0:
                    # print(ni, nj)
                    new_dist = dist + 1
                    if new_dist < dists[pp - 1][ni][nj]:
                        frontiers[pp - 1].append((ni, nj, new_dist))
                        dists[pp - 1][ni][nj] = new_dist
    if was:
        for i in range(p):
            curr_lim[i] += s[i]
    else:
        break

print(' '.join(str(v) for v in ans))


# -*- coding: utf-8 -*-
# @Time    : 2019/1/20 21:02
# @Author  : LunaFire
# @Email   : gilgemesh2012@gmail.com
# @File    : D. Kilani and the Game.py

# import atexit
# import io
# import sys
#
# _INPUT_LINES = sys.stdin.read().splitlines()
# input = iter(_INPUT_LINES).__next__
# _OUTPUT_BUFFER = io.StringIO()
# sys.stdout = _OUTPUT_BUFFER
#
#
# @atexit.register
# def write():
#     sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())


from collections import deque


def check_empty(deque_array):
    count = 0
    for q in deque_array:
        count += len(q)
    return count == 0


def print_grid(grid):
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            print(grid[i][j], end='')
        print()
    print()


def main():
    n, m, p = map(int, input().split())
    s = list(map(int, input().split()))
    grid = [list(input()) for _ in range(n)]

    deque_array = [deque() for _ in range(p)]
    for i in range(n):
        for j in range(m):
            if '1' <= grid[i][j] <= '9':
                x = int(grid[i][j])
                deque_array[x - 1].append((i, j, 0))

    # print(deque_array)
    curr_round = 1
    while not check_empty(deque_array):
        for r in range(p):
            while deque_array[r]:
                x, y, step = deque_array[r].popleft()
                if step >= s[r] * curr_round:
                    deque_array[r].appendleft((x, y, step))
                    break

                for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    nx, ny = x + dx, y + dy
                    # print(nx, ny)
                    if nx < 0 or nx >= n or ny < 0 or ny >= m or grid[nx][ny] != '.':
                        continue
                    grid[nx][ny] = str(r + 1)
                    deque_array[r].append((nx, ny, step + 1))
        # print_grid(grid)
        curr_round += 1

    cell_count = [0] * p
    for i in range(n):
        for j in range(m):
            if '1' <= grid[i][j] <= '9':
                x = int(grid[i][j])
                cell_count[x - 1] += 1
    for r in range(p):
        print(cell_count[r], end=' ')
    print()


def __starting_point():
    main()

__starting_point()

# import sys
#
# f = open('input1.txt', 'r')
#
#
# sys.stdin = f

n, m, p = list(map(int, input().split()))
s = list(map(int, input().split()))

q = [[] for _ in range(p)] # fromnt of each palyer
counts = [0] * p

field = []
for i in range(n):
    line = input()
    field.append([0] * m)
    for j, c in enumerate(line):
        if c == '.':
            field[i][j] = 0
        elif c == '#':
            field[i][j] = -1
        else:
            # player
            pi = int(c)
            field[i][j] = pi
            counts[pi-1] += 1

def get_neibs(i, j):
    up = (i - 1, j) if i > 0 else None
    down = (i + 1, j) if i < n - 1 else None
    left = (i, j - 1) if j > 0 else None
    right = (i, j + 1) if j < m - 1 else None
    nbs = [up, down, left, right]
    return [a for a in nbs if a is not None]



def init_bounds(field, q):
    for i in range(n):
        for j in range(m):
            if field[i][j] > 0:
                index  = field[i][j]-1
                nbs = get_neibs(i, j)
                neib_vals = [field[a[0]][a[1]] for a in nbs]
                if 0 in neib_vals:
                    q[index].append((i, j))

def step_one(index, field, front: list):
    new_front = []

    total_add = 0
    for i, j in front:
        nbs = get_neibs(i, j)
        for a in nbs:
            if field[a[0]][a[1]] == 0:
                # if not yet added
                field[a[0]][a[1]] = index+1
                counts[index] += 1
                total_add += 1
                new_front.append(a)


    return new_front, total_add





def  step(index, field, front, speed):
    added_len = 0
    while speed > 0:
        front, added_len = step_one(index, field, front)
        speed -= 1
        if added_len == 0:
            break

    q[index] = front
    return front, added_len

init_bounds(field, q)

while True:

    progress = 0
    added = 0
    for i in range(p):
        _, added = step(i, field, q[i], s[i])
        progress += added

    if progress == 0:
        break



print(" ".join(map(str, counts)))

# f.close()


n, m, p=map(int, input().split())
s=list(map(int, input().split()))
a=[]
front=[set() for i in range(p)] 
for i in range(n):
    a.append([(int(0) if ch=='.' else (-1 if ch=='#' else (int(ch) if not front[int(ch)-1].add( (i, j) ) else -99 ))) for j, ch in enumerate(input())])

move=[(-1, 0), (1, 0), (0, -1), (0, 1)]
i=0
blocked=[False]*p
activeplayers=p

i=0
while activeplayers>0:
    if blocked[i]:
        i=(i+1)%p
        continue
    aset=front[i]
    mademove=False
    for gtime in range(s[i]):
        newset=set()
        for x,y in aset:
            for dx, dy in move:
                if 0<=x+dx<n and 0<=y+dy<m:
                    if a[x+dx][y+dy]==0:
                        newset.add( (x+dx, y+dy) )
                        a[x+dx][y+dy]=(i+1)
                        mademove=True
        aset=newset
        if len(aset)==0:
            mademove=False
            break
    front[i]=aset
    if not mademove:
        blocked[i]=True
        activeplayers=activeplayers-1
    i=(i+1)%p

res=[0]*p


for i in range(n):
    for j in range(m):
        if a[i][j]>0:
            res[int(a[i][j])-1]=res[int(a[i][j])-1]+1

for i in range(p):
    print(res[i], end=' ')


import sys
from collections import deque as dq

h,w,P = [int(x) for x in input().split()]
S = [int(x) for x in input().split()]

board = []
for b in sys.stdin.read():
    for c in b:
        if c=='.':
            board.append(-1)
        elif 0<=ord(c)-49<=9:
            board.append(ord(c)-49)
        elif c=='#':
            board.append(-2)

new_castles = [dq() for _ in range(P)]

for pos in range(h*w):
    if board[pos]>=0:
        new_castles[board[pos]].append((pos,0))

Q = dq()
player_Q = dq(p for p in range(P) if new_castles[p])
while player_Q:
    p = player_Q.popleft()
    Q = new_castles[p]
    # Do S[p] moves
    goal = Q[-1][1] + S[p]
    while Q and Q[0][1] != goal:
        pos,moves = Q.popleft()
        y = pos//w
        x = pos - y*w
        
        if 0<x and board[pos-1]==-1:
            board[pos-1]=p
            Q.append((pos-1,moves+1))
        
        if x<w-1 and board[pos+1]==-1:
            board[pos+1]=p
            Q.append((pos+1,moves+1))
    
        if 0<y and board[pos-w]==-1:
            board[pos-w]=p
            Q.append((pos-w,moves+1))
        
        if y<h-1 and board[pos+w]==-1:
            board[pos+w]=p
            Q.append((pos+w,moves+1))
    if Q:
        player_Q.append(p)

count = [0 for _ in range(P)]
for x in board:
    if x >= 0:
        count[x] += 1
print(*count)

import sys
from collections import deque as dq

h,w,P = [int(x) for x in input().split()]
S = [int(x) for x in input().split()]

board = []
inp = sys.stdin.read()
for ind in range(len(inp)):
    if inp[ind]=='.':
        board.append(-1)
    elif 49<=ord(inp[ind])<=58:
        board.append(ord(inp[ind])-49)
    elif inp[ind]=='#':
        board.append(-2)

new_castles = [dq() for _ in range(P)]

for pos in range(h*w):
    if board[pos]>=0:
        new_castles[board[pos]].append((pos,0))

player_Q = dq(p for p in range(P) if new_castles[p])
while player_Q:
    p = player_Q.popleft()
    Q = new_castles[p]

    goal = Q[-1][1] + S[p]
    while Q and Q[0][1] != goal:
        pos,moves = Q.popleft()
        y = pos//w
        x = pos - y*w
        
        if 0<x and board[pos-1]==-1:
            board[pos-1]=p
            Q.append((pos-1,moves+1))
        
        if x<w-1 and board[pos+1]==-1:
            board[pos+1]=p
            Q.append((pos+1,moves+1))
    
        if 0<y and board[pos-w]==-1:
            board[pos-w]=p
            Q.append((pos-w,moves+1))
        
        if y<h-1 and board[pos+w]==-1:
            board[pos+w]=p
            Q.append((pos+w,moves+1))
    if Q:
        player_Q.append(p)

count = [0 for _ in range(P)]
for x in board:
    if x >= 0:
        count[x] += 1
print(' '.join(str(x) for x in count))

import sys
h,w,P = [int(x) for x in input().split()]
S = [int(x) for x in input().split()]

board = []
inp = sys.stdin.read()
for ind in range(len(inp)):
    if inp[ind]=='.':
        board.append(-1)
    elif 49<=ord(inp[ind])<=58:
        board.append(ord(inp[ind])-49)
    elif inp[ind]=='#':
        board.append(-2)

new_castles = [[] for _ in range(P)]
new_castles_ind = [0 for _ in range(P)]

for pos in range(h*w):
    if board[pos]>=0:
        new_castles[board[pos]].append((pos,0))

player_Q = [p for p in range(P) if new_castles[p]]
player_Q_ind = 0

while player_Q_ind != len(player_Q):
    p = player_Q[player_Q_ind]
    player_Q_ind += 1
    Q = new_castles[p]
    Q_ind = new_castles_ind[p]

    goal = Q[Q_ind][1] + S[p]
    while Q_ind != len(Q) and Q[Q_ind][1] != goal:
        pos,moves = Q[Q_ind]
        Q_ind += 1
        y = pos//w
        x = pos - y*w
        
        if 0<x and board[pos-1]==-1:
            board[pos-1]=p
            Q.append((pos-1,moves+1))
        
        if x<w-1 and board[pos+1]==-1:
            board[pos+1]=p
            Q.append((pos+1,moves+1))
    
        if 0<y and board[pos-w]==-1:
            board[pos-w]=p
            Q.append((pos-w,moves+1))
        
        if y<h-1 and board[pos+w]==-1:
            board[pos+w]=p
            Q.append((pos+w,moves+1))
    if Q_ind != len(Q):
        player_Q.append(p)
        new_castles_ind[p] = Q_ind

count = [0 for _ in range(P)]
for x in board:
    if x >= 0:
        count[x] += 1
print(' '.join(str(x) for x in count))

import sys

h,w,P = [int(x) for x in input().split()]
S = [int(x) for x in input().split()]

board = []
inp = sys.stdin.read()
for ind in range(len(inp)):
    c = inp[ind]
    if c=='.':
        board.append(-1)
    elif 49<=ord(c)<=58:
        board.append(ord(c)-49)
    elif c=='#':
        board.append(-2)

new_castles = [[] for _ in range(P)]
new_castles_ind = [0 for _ in range(P)]

for pos in range(h*w):
    if board[pos]>=0:
        new_castles[board[pos]].append((pos,0))

player_Q = [p for p in range(P) if new_castles[p]]
player_Q_ind = 0

while player_Q_ind != len(player_Q):
    p = player_Q[player_Q_ind]
    player_Q_ind += 1
    Q = new_castles[p]
    Q_ind = new_castles_ind[p]

    goal = Q[Q_ind][1] + S[p]
    while Q_ind != len(Q) and Q[Q_ind][1] != goal:
        pos,moves = Q[Q_ind]
        Q_ind += 1
        y = pos//w
        x = pos - y*w
        
        if 0<x and board[pos-1]==-1:
            board[pos-1]=p
            Q.append((pos-1,moves+1))
        
        if x<w-1 and board[pos+1]==-1:
            board[pos+1]=p
            Q.append((pos+1,moves+1))
    
        if 0<y and board[pos-w]==-1:
            board[pos-w]=p
            Q.append((pos-w,moves+1))
        
        if y<h-1 and board[pos+w]==-1:
            board[pos+w]=p
            Q.append((pos+w,moves+1))
    if Q_ind != len(Q):
        player_Q.append(p)
        new_castles_ind[p] = Q_ind

print(*[len(new_castles[p]) for p in range(P)])

import sys

h,w,P = [int(x) for x in input().split()]
S = [int(x) for x in input().split()]

board = []
for c in sys.stdin.read():
    if c=='.':
        board.append(-1)
    elif 49<=ord(c)<=58:
        board.append(ord(c)-49)
    elif c=='#':
        board.append(-2)

new_castles = [[] for _ in range(P)]
new_castles_ind = [0 for _ in range(P)]

for pos in range(h*w):
    if board[pos]>=0:
        new_castles[board[pos]].append((pos,0))

player_Q = [p for p in range(P) if new_castles[p]]
player_Q_ind = 0

while player_Q_ind != len(player_Q):
    p = player_Q[player_Q_ind]
    player_Q_ind += 1
    Q = new_castles[p]
    Q_ind = new_castles_ind[p]

    goal = Q[Q_ind][1] + S[p]
    while Q_ind != len(Q) and Q[Q_ind][1] != goal:
        pos,moves = Q[Q_ind]
        Q_ind += 1
        y = pos//w
        x = pos - y*w
        
        if 0<x and board[pos-1]==-1:
            board[pos-1]=p
            Q.append((pos-1,moves+1))
        
        if x<w-1 and board[pos+1]==-1:
            board[pos+1]=p
            Q.append((pos+1,moves+1))
    
        if 0<y and board[pos-w]==-1:
            board[pos-w]=p
            Q.append((pos-w,moves+1))
        
        if y<h-1 and board[pos+w]==-1:
            board[pos+w]=p
            Q.append((pos+w,moves+1))
    if Q_ind != len(Q):
        player_Q.append(p)
        new_castles_ind[p] = Q_ind

print(*[len(new_castles[p]) for p in range(P)])

from collections import deque
import math


def add(x, y):
    return (x[0] + y[0], x[1] + y[1])


h, w, n = list(map(int, input().split()))
speeds = list(map(int, input().split()))
arr = [None] * h
castles = [deque() for _ in range(n)]
castles_count = [0] * n
for i in range(h):
    arr[i] = list(input())
    for j in range(w):
        if arr[i][j] not in ('.', '#'):
            arr[i][j] = int(arr[i][j]) - 1
            castles[arr[i][j]].append((i, j))
            castles_count[arr[i][j]] += 1


def get(x):
    if (x[0] >= 0) and (x[1] >= 0) and (x[0] < h) and (x[1] < w):
        return arr[x[0]][x[1]]
    return None


has_changes = True
while has_changes:
    has_changes = False
    for p in range(n):
        cur_lvl = castles[p]
        cur_lvl_num = 0
        while (cur_lvl_num < speeds[p]) and cur_lvl:
            next_lvl = []
            for cell in cur_lvl:
                for move in ((0, 1), (0, -1), (-1, 0), (1, 0)):
                    next_cell = add(cell, move)
                    val = get(next_cell)
                    if val == '.':
                        has_changes = True
                        next_lvl.append(next_cell)
                        arr[next_cell[0]][next_cell[1]] = p
                        castles_count[p] += 1
            cur_lvl_num += 1
            cur_lvl = next_lvl
        castles[p] = cur_lvl

print(' '.join(map(str, castles_count)))


import sys
from collections import deque, Counter

def __starting_point():
    n, m, p = list(map(int, input().split()))
    speeds = list(map(int, input().split()))
    field = sys.stdin.readlines()

    lands = [-1] * (n * m)

    graph = [[] for _ in range(n * m)]

    starts = [deque() for _ in range(p)]

    levels = [-1] * n * m

    def calc(x, y): return x * m + y


    for i in range(n):
        for j in range(m):
            point = calc(i, j)
            if field[i][j].isdigit():
                player = int(field[i][j]) - 1
                starts[player].appendleft(point)
                lands[point] = player
                levels[point] = 0
            elif field[i][j] == '#':
                continue

            if 0 <= i - 1 and field[i - 1][j] == '.':
                graph[point].append(calc(i - 1, j))
            if i + 1 < n and field[i + 1][j] == '.':
                graph[point].append(calc(i + 1, j))
            if 0 <= j - 1 and field[i][j - 1] == '.':
                graph[point].append(calc(i, j - 1))
            if j + 1 < m and field[i][j + 1] == '.':
                graph[point].append(calc(i, j + 1))

    cnt = 0
    while [s for s in starts if s]:
        player = cnt % p
        turn = cnt // p + 1

        while starts[player]:
            if levels[starts[player][-1]] == speeds[player] * turn:
                break

            node = starts[player].pop()

            for nxt in graph[node]:
                if lands[nxt] != -1:
                    continue
                level = levels[node] + 1
                lands[nxt] = player
                levels[nxt] = levels[node] + 1
                starts[player].appendleft(nxt)

        cnt += 1

    cnt = list(Counter([l for l in lands if l != -1]).items())
    cnt.sort()

    print(" ".join([str(x[1]) for x in cnt]))



__starting_point()

n, m, p = list(map(int, input().split()))
s = [int(i) for i in input().split()]

p_size = [0] * p
field = []
field_free = 0
pp = [set() for _ in range(p)]
for y in range(n):
    for x,i in enumerate(input()):
        if not (i == '.' or i == '#'):
            pp[int(i)-1].add(x + y*m)
        c = i != '#'
        field_free += int(c)
        field.append(c)

def append_nearest(fp, ppn, pi):
    nonlocal field_free
    nonlocal p_size
    if not field[fp]:
        return
    if fp % m > 0 and field[fp-1]:
        ppn.add(fp - 1)
    if fp % m < m-1 and field[fp+1]:
        ppn.add(fp + 1)
    if fp // m > 0 and field[fp - m]:
        ppn.add(fp - m)
    if fp // m < n-1 and field[fp + m]:
        ppn.add(fp + m)
    field[fp] = False
    field_free -= 1
    p_size[pi] += 1

for pi in range(p):
    ppi = pp[pi]
    ppn = pp[pi] = set()
    for fp in ppi:
        append_nearest(fp, ppn, pi)
    del ppi

ppn = set()
for pi in range(p):
    ppi = pp[pi]
    if len(ppi) > 0:
        for _ in range(s[pi]):
            for fp in ppi:
                append_nearest(fp, ppn, pi)
            ppi.clear()
            ppi,ppn = ppn,ppi

            if field_free == 0 or len(ppi) == 0:
                break
        pp[pi] = ppi

        if field_free == 0:
            break
nmlp = n*m - m
ssss = True
while field_free > 0 and ssss:
    ssss = False
    for pi in range(p):
        ppi = pp[pi]
        if len(ppi) > 0:
            for _ in range(s[pi]):
                for fp in ppi:
                    if not field[fp]:
                        continue
                    if fp % m > 0 and field[fp-1]:
                        ppn.add(fp - 1)
                    if fp % m < m-1 and field[fp+1]:
                        ppn.add(fp + 1)
                    if fp > m-1 and field[fp - m]:
                        ppn.add(fp - m)
                    if fp < nmlp and field[fp + m]:
                        ppn.add(fp + m)
                    field[fp] = False
                    field_free -= 1
                    p_size[pi] += 1
                ppi.clear()
                ppi,ppn = ppn,ppi
            pp[pi] = ppi
            ssss |= len(ppi) > 0


print(' '.join(map(str, p_size)))


from collections import deque
import sys
DBG =   False
n,m,p = list(map(int, input().split()))
spd = list(map(int, input().split()))
spd.insert(0,-1)  # p starts at 1
grid = [ [0] * m for i in range(n) ]
c2d = { "#":-1, ".":0, "1":1, "2":2, "3":3, "4":4,
        "5":5, "6":6, "7":7, "8":8, "9":9 }
castle = [ [] for i in range(p+1)]

for i in range(n):
  s = input()
  for j in range(m):
    v = c2d[s[j]]
    grid[i][j] = v
    if v>0:
      castle[v].append([i,j])

if DBG:
  print(grid)
  print("\n")
  print(spd)
  print("\n")

def mark(proc,t):
  nonlocal changed, grid, castle, newcastle
  dir = [ [1,0], [-1,0], [0,1], [0,-1] ]
  while len(proc) > 0:
    ent = proc.popleft()
    c = ent[0]
    s = ent[1]
    for d in dir:
      x = c[0]+d[0]
      y = c[1]+d[1]
      if x<0 or n<=x or y<0 or m<=y or grid[x][y]!=0:
          continue
      changed = True
      grid[x][y] = t
      if s>1:
        proc.append([ [x,y], s-1 ])
      else:
        newcastle.append([x,y])


changed = True
while changed:
  if DBG:
    print("---- new loop ----")
  changed = False
  for t in range(1,p+1):
    newcastle = []
    proc = deque([])
    for c in castle[t]:
        proc.append([c, spd[t]])
    mark(proc, t)
    if False and DBG:
        print(("turn for %d, (%d,%d) ended" %
                     (t,c[0],c[1])))
        print(grid)
    #for x in $newcastle
    #  $castle[t] << x
    #end
    castle[t] = newcastle

a = [ 0 for i in range(p+1) ]
for x in range(n):
  for y in range(m):
    if grid[x][y] != -1:
      a[grid[x][y]] += 1

for i in range(1,p+1):
  sys.stdout.write("%d " % a[i])
print("")


import time


def get_frontiers(feild, n, m, p):
    # print(feild)
    # print(n, m)
    frontiers = [[] for i in range(p)]
    for i in range(n):
        for j in range(m):
            ele = feild[i][j]
            if 1 <= ele <= 9:
                # print('ele:', ele)
                frontiers[ele - 1].append((i, j))
    return frontiers

def go(player_id, frontier, n_turn, feild, n, m):
    frontier = frontier
    # print('In go:', player_id, frontier, n_turn)
    while n_turn and frontier:
        n_turn -= 1
        new_frontier = []
        for i, j in frontier:
            # Down.
            if i + 1 < n:
                new_space = feild[i + 1][j]
                if not new_space:
                    feild[i + 1][j] = player_id
                    new_frontier.append((i + 1, j))
            # Up.
            if i - 1 >= 0:
                new_space = feild[i - 1][j]
                if not new_space:
                    feild[i - 1][j] = player_id
                    new_frontier.append((i - 1, j))
            # Rigth.
            if j + 1 < m:
                new_space = feild[i][j + 1]
                if not new_space:
                    feild[i][j + 1] = player_id
                    new_frontier.append((i, j + 1))
            # Left.
            if j - 1 >= 0:
                new_space = feild[i][j - 1]
                if not new_space:
                    feild[i][j - 1] = player_id
                    new_frontier.append((i, j - 1))

            # for d_i, d_j in (-1, 0), (1, 0), (0, 1), (0, -1):
                # check boarder.
                # new_i, new_j = i + d_i, j + d_j
                # if new_i < 0 or new_j < 0 or new_i > n - 1 or new_j > m - 1:
                    # continue
                # new_space = feild[new_i][new_j]
                # if new_space == 0:
                    # feild[new_i][new_j] = player_id
                    # new_frontier.append((new_i, new_j))
        frontier = new_frontier
                # print('haha:', frontier)
        # print('player:', player_id)

        # for ele in feild:
            # print(ele)
    # print('Got new frontier:', frontier)
    return frontier

def solve(speeds, feild, n, m, p):
    frontiers = get_frontiers(feild, n, m, p)
    # print('f:', frontiers)
    hope = set(range(p))
    while hope:
        new_hope = set()
        for i in hope:
            n_turn = speeds[i]
            frontier = frontiers[i]
            new_frontier = go(i + 1, frontier, n_turn, feild, n, m)
            # print('i:', i)
            # print(new_frontier)
            if new_frontier:
                new_hope.add(i)
            frontiers[i] = new_frontier
        hope = new_hope
    result = get_frontiers(feild, n, m, p)
    return [len(ele) for ele in result]

def test():
    n, m, p = 1000, 1000, 9
    speeds = [1000000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 1]
    feild = [[0, -1] * (m // 2) for i in range(n)]
    for i in range(m):
        if i % 4 != 1:
            feild[0][i] = 0
        if i % 4 != 3:
            feild[n - 1][i] = 0
    # feild[0][0] = 1
    for i in range(9):
        feild[0][i * 8] = i + 1    
    # for ele in feild:
        # print(ele)
    tick = time.time()
    result = solve(speeds, feild, n, m, p)
    tock = time.time()
    print(' '.join(map(str, result)))
    print('T:', round(tock - tick, 5))

def main():
    d = {str(i): i for i in range(1, 10)}
    d['.'] = 0
    d['#'] = -1
    n, m, p = map(int, input().split())
    speeds = list(map(int, input().split()))
    feild = []
    for i in range(n):
        feild.append(list(map(d.get, input())))
    # for ele in feild:
        # print(ele)
    result = solve(speeds, feild, n, m, p)
    print(' '.join(map(str, result)))
    # for ele in feild:
        # print(ele)

def __starting_point():
    main()
__starting_point()

import time


def get_frontiers(feild, n, m, p):
    # print(feild)
    # print(n, m)
    frontiers = [[] for i in range(p)]
    for i in range(n):
        for j in range(m):
            ele = feild[i][j]
            if 1 <= ele <= 9:
                # print('ele:', ele)
                frontiers[ele - 1].append((i, j))
    return frontiers

def go(player_id, frontier, n_turn, feild, n, m):
    frontier = frontier
    # print('In go:', player_id, frontier, n_turn)
    while n_turn and frontier:
        n_turn -= 1
        new_frontier = []
        for i, j in frontier:
            # Down.
            if i + 1 < n:
                new_space = feild[i + 1][j]
                if not new_space:
                    feild[i + 1][j] = player_id
                    new_frontier.append((i + 1, j))
            # Up.
            if i - 1 >= 0:
                new_space = feild[i - 1][j]
                if not new_space:
                    feild[i - 1][j] = player_id
                    new_frontier.append((i - 1, j))
            # Rigth.
            if j + 1 < m:
                new_space = feild[i][j + 1]
                if not new_space:
                    feild[i][j + 1] = player_id
                    new_frontier.append((i, j + 1))
            # Left.
            if j - 1 >= 0:
                new_space = feild[i][j - 1]
                if not new_space:
                    feild[i][j - 1] = player_id
                    new_frontier.append((i, j - 1))

            # for d_i, d_j in (-1, 0), (1, 0), (0, 1), (0, -1):
                # check boarder.
                # new_i, new_j = i + d_i, j + d_j
                # if new_i < 0 or new_j < 0 or new_i > n - 1 or new_j > m - 1:
                    # continue
                # new_space = feild[new_i][new_j]
                # if new_space == 0:
                    # feild[new_i][new_j] = player_id
                    # new_frontier.append((new_i, new_j))
        frontier = new_frontier
                # print('haha:', frontier)
        # print('player:', player_id)

        # for ele in feild:
            # print(ele)
    # print('Got new frontier:', frontier)
    return frontier

def solve(speeds, feild, n, m, p):
    frontiers = get_frontiers(feild, n, m, p)
    # print('f:', frontiers)
    hope = set(range(p))
    while hope:
        lost_hope = set()
        for i in hope:
            n_turn = speeds[i]
            frontier = frontiers[i]
            new_frontier = go(i + 1, frontier, n_turn, feild, n, m)
            # print('i:', i)
            # print(new_frontier)
            if not new_frontier:
                lost_hope.add(i)
            frontiers[i] = new_frontier
        hope -= lost_hope
    result = get_frontiers(feild, n, m, p)
    return [len(ele) for ele in result]

def test():
    n, m, p = 1000, 1000, 9
    speeds = [1000000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 1]
    feild = [[0, -1] * (m // 2) for i in range(n)]
    for i in range(m):
        if i % 4 != 1:
            feild[0][i] = 0
        if i % 4 != 3:
            feild[n - 1][i] = 0
    # feild[0][0] = 1
    for i in range(9):
        feild[0][i * 8] = i + 1    
    # for ele in feild:
        # print(ele)
    tick = time.time()
    result = solve(speeds, feild, n, m, p)
    tock = time.time()
    print(' '.join(map(str, result)))
    print('T:', round(tock - tick, 5))

def main():
    d = {str(i): i for i in range(1, 10)}
    d['.'] = 0
    d['#'] = -1
    n, m, p = map(int, input().split())
    speeds = list(map(int, input().split()))
    feild = []
    for i in range(n):
        feild.append(list(map(d.get, input())))
    # for ele in feild:
        # print(ele)
    result = solve(speeds, feild, n, m, p)
    print(' '.join(map(str, result)))
    # for ele in feild:
        # print(ele)

def __starting_point():
    main()
__starting_point()

[n, m, p] = [int(x) for x in input().split()]
s = [int(x) for x in input().split()]


coord_change = [[0,1],[0,-1],[1,0],[-1,0]]

grid = []

visited = [[False]*1010 for x in range(1010)]

queue = [[] for x in range(10)]
controlled = [0]*10

for i in range(n):
    grid.append(input())
    for j in range(m):
        if grid[i][j] == '.':
            continue
        elif grid[i][j] == '#':
            visited[i][j] = True
        else:
            player = int(grid[i][j])-1
            visited[i][j] = True
            queue[player].append([i,j])
            controlled[player] += 1



curr_p = 0
while any(queue):
    moves = 0
    # print(curr_p, queue,s)
    while moves < s[curr_p] and queue[curr_p]:
        new_queue = []
        curr_queue = queue[curr_p]
        for coord in curr_queue:
            for change in coord_change:
                new_coord = [coord[0]+change[0],coord[1]+change[1]]
                if new_coord[0] < 0 or new_coord[1] < 0 or new_coord[0] >= n or new_coord[1] >= m:
                    continue
                if visited[new_coord[0]][new_coord[1]]:
                    continue

                visited[new_coord[0]][new_coord[1]] = True
                controlled[curr_p] += 1
                new_queue.append(new_coord)
        moves += 1
        queue[curr_p] = new_queue
    curr_p += 1
    curr_p %= p

# print(grid[0])
# print(controlled)
for i in range(p):
    print(controlled[i],end=' ')

import sys
import math
from collections import defaultdict,deque
import heapq
mod=998244353
def check(x,y,n,m):
	return (0<=x<n and 0<=y<m)
n,m,k=list(map(int,sys.stdin.readline().split()))
grid=[]
s=list(map(int,sys.stdin.readline().split()))
for i in range(n):
	grid.append(list(sys.stdin.readline()[:-1]))
q=deque()
dic=defaultdict(deque)
for i in range(n):
	for j in range(m):
		if grid[i][j]!='.' and grid[i][j]!='#':
			dic[int(grid[i][j])].append([i,j])
			#q.append([int(grid[i][j]),i,j])
q=True
dirs=[[0,1],[0,-1],[1,0],[-1,0]]
while q:
	z=True
	for i in range(k):
		nq=deque()
		while dic[i+1]:
			j=dic[i+1].popleft()
			#print(j,'j')
			nq.append(j+[s[i]])
			z=False
		p=i+1
		while nq:
			#print(nq,'nq')
			x,y,dis=nq.popleft()
			if dis==0:
				dic[p].append([x,y])
			else:
				for i,j in dirs:
					nx,ny=x+i,y+j
					if check(nx,ny,n,m) and grid[nx][ny]=='.':
						grid[nx][ny]=p
						#print(nx,'nx',ny,'ny',dis-1,'dis-1')
						nq.append([nx,ny,dis-1])
		
	if z:
		q=False

'''for i in range(k):
	for j in dic[i+1]:
		q.append([i+1]+j)
#print(q,'q')

while q:
	p,curx,cury=q.popleft()

	#print(p,'p',curx,'curx',cury,'cury',s[p-1])
	nq=deque()
	nq.append([curx,cury,s[p-1]])
	if int(grid[curx][cury])==p:
		while nq:
			x,y,dis=nq.popleft()
			#print(x,'x',y,'y',dis,'dis')
			if dis==0:
				q.append([p,x,y])
			else:
				for i,j in dirs:
					nx,ny=x+i,y+j
					if check(nx,ny,n,m) and grid[nx][ny]=='.':
						grid[nx][ny]=p
						#print(nx,'nx',ny,'ny',dis-1,'dis-1')
						nq.append([nx,ny,dis-1])
	for i in range(n):
		print(grid[i])
	print('\n')'''
ans=[0 for _ in range(k)]
#print(ans,'ans')
for i in range(n):
	for j in range(m):
		if grid[i][j]!='.' and grid[i][j]!='#':
			ans[int(grid[i][j])-1]+=1
#print(grid,'grid')
print(*ans)