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.

Source: codeforces | Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Implementation

Shortest paths


Solutions:
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]
	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)


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)))


from collections import deque
import sys
DBG = False
(n, m, p) = map(int, input().split())
spd = list(map(int, input().split()))
spd.insert(0, -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):
	global 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)
		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('')


(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)))


import time

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

def go(player_id, frontier, n_turn, feild, n, m):
	frontier = frontier
	while n_turn and frontier:
		n_turn -= 1
		new_frontier = []
		for (i, j) in frontier:
			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))
			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))
			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))
			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))
		frontier = new_frontier
	return frontier

def solve(speeds, feild, n, m, p):
	frontiers = get_frontiers(feild, n, m, p)
	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)
			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
	for i in range(9):
		feild[0][i * 8] = i + 1
	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())))
	result = solve(speeds, feild, n, m, p)
	print(' '.join(map(str, result)))
main()


import sys
input = sys.stdin.readline
import gc, os
from collections import deque
from os import _exit
gc.disable()

def safe(i, j):
	return i < n and j < m and (i >= 0) and (j >= 0) and (mat[i][j] == '.')

def bfs(h):
	while any(h):
		for i in range(1, p + 1):
			h[i] = bfs2(i)

def bfs2(c):
	global mat
	s = l[c - 1]
	q = deque()
	for (i, j) in h[c]:
		q.append((i, j, 0))
	ans = []
	while q:
		(i, j, k) = q.popleft()
		if k >= s:
			ans.append((i, j))
			continue
		for (dx, dy) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
			(x, y) = (i + dx, j + dy)
			if safe(x, y):
				mat[x][y] = str(c)
				q.append((x, y, k + 1))
	return ans
(n, m, p) = map(int, input().split())
l = list(map(int, input().split()))
mat = [list(input()) for i in range(n)]
q = []
h = [[] for _ in range(p + 1)]
for i in range(n):
	for j in range(m):
		if mat[i][j] not in '.#':
			z = int(mat[i][j])
			h[z].append((i, j))
bfs(h)
count = [0] * p
for i in range(n):
	for j in range(m):
		if mat[i][j] not in '.#':
			count[int(mat[i][j]) - 1] += 1
print(*count)
sys.stdout.flush()
_exit(0)


[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
	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
for i in range(p):
	print(controlled[i], end=' ')


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))
	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)
					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))
		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 os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def pre(s):
	n = len(s)
	pi = [0] * n
	for i in range(1, n):
		j = pi[i - 1]
		while j and s[i] != s[j]:
			j = pi[j - 1]
		if s[i] == s[j]:
			j += 1
		pi[i] = j
	return pi

def prod(a):
	ans = 1
	for each in a:
		ans = ans * each
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
from collections import deque
for _ in range(int(input()) if not True else 1):
	(n, m, pp) = map(int, input().split())
	s = list(map(int, input().split()))
	a = [''] * n
	ans = [0] * pp
	occupied = [[False] * m for __ in range(n)]
	for i in range(n):
		a[i] = input()
	queues = [deque([]) for __ in range(pp)]
	qc = list(queues)
	for i in range(n):
		for j in range(m):
			dig = a[i][j].isdigit()
			if dig:
				ans[int(a[i][j]) - 1] += 1
				queues[int(a[i][j]) - 1].append(i * m + j + 1)
				occupied[i][j] = True
			if a[i][j] == '#':
				occupied[i][j] = True
	cur = 0
	while True:
		i = cur % pp
		count = 0
		while count < s[i] and queues[i]:
			lq = len(queues[i])
			for ___ in range(lq):
				x = queues[i][0]
				queues[i].popleft()
				(p, q) = ((x - 1) // m, (x - 1) % m)
				if p != 0 and (not occupied[p - 1][q]):
					queues[i].append((p - 1) * m + q + 1)
					occupied[p - 1][q] = True
					ans[i] += 1
				if p != n - 1 and (not occupied[p + 1][q]):
					queues[i].append((p + 1) * m + q + 1)
					occupied[p + 1][q] = True
					ans[i] += 1
				if q != 0 and (not occupied[p][q - 1]):
					queues[i].append(p * m + q)
					occupied[p][q - 1] = True
					ans[i] += 1
				if q != m - 1 and (not occupied[p][q + 1]):
					queues[i].append(p * m + q + 2)
					occupied[p][q + 1] = True
					ans[i] += 1
			count += 1
		cur += 1
		pos = True
		for i in queues:
			if i:
				pos = False
				break
		if pos:
			break
	print(*ans)


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) = 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 = 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()
			nq.append(j + [s[i]])
			z = False
		p = i + 1
		while 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
						nq.append([nx, ny, dis - 1])
	if z:
		q = False
ans = [0 for _ in range(k)]
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(*ans)


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
(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):
		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):
					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)))


(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))

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)
while any((len(x) > 0 for x in edges.values())):
	for (s, c) in zip(speeds, colors()):
		for i in range(s):
			up_field(c)
			if len(edges[c]) == 0:
				break
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()))


import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict, deque, Counter, OrderedDict
import threading
from heapq import *
(dx, dy) = ([1, -1, 0, 0], [0, 0, 1, -1])

def main():
	(n, m, p) = map(int, input().split())
	s = [*map(int, input().split())]
	D = [[*input()] for _ in range(n)]
	S = [[-1] * m for _ in range(n)]
	ans = [0] * p
	q = [deque() for _ in range(p)]
	new_q = [deque() for _ in range(p)]
	for i in range(n):
		for j in range(m):
			if 49 <= ord(D[i][j]) <= 57:
				x = int(D[i][j])
				S[i][j] = x
				q[x - 1].append([i, j, x, 0])
				ans[x - 1] += 1
	while 1:
		flag = False
		for i in range(p):
			if len(q[i]):
				flag = True
		if not flag:
			break
		for i in range(p):
			while q[i]:
				(x, y, num, move) = q[i].popleft()
				for j in range(4):
					(nx, ny) = (x + dx[j], y + dy[j])
					if 0 <= nx < n and 0 <= ny < m and (D[nx][ny] == '.') and (S[nx][ny] == -1) and (move < s[num - 1]):
						S[nx][ny] = num
						ans[num - 1] += 1
						if move + 1 == s[num - 1]:
							new_q[i].append([nx, ny, num, 0])
						else:
							q[i].append([nx, ny, num, move + 1])
			if len(new_q[i]):
				q[i] = new_q[i]
				new_q[i] = deque()
	print(*ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


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) = 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=' ')


(n, m, p) = list(map(int, input().split()))
s = list(map(int, input().split()))
q = [[] for _ in range(p)]
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:
			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:
				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)))


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)))


from collections import deque
(n, m, p) = map(int, input().split())
spd = list(map(int, input().split()))
spd.insert(0, -1)
d = {'.': 0, '#': -1}
d.update({str(v): v for v in range(1, p + 1)})
g = [[d[c] for c in input().strip()] for _ in range(n)]
h = [0 for i in range(10)]
dist = [[[9999999 for _ in range(m)] for _ in range(n)] for _ in range(p + 1)]
Q = [deque() for i in range(p + 1)]
for i in range(n):
	for j in range(m):
		v = g[i][j]
		if v > 0:
			Q[v].append([i, j, 0])
			h[v] += 1
			dist[v][i][j] = 0
ok = False
spd2 = spd[:]
while True:
	ok = False
	for u in range(1, p + 1):
		while Q[u]:
			(x, y, d) = Q[u].popleft()
			if g[x][y] not in (0, u):
				continue
			if d > spd2[u]:
				Q[u].appendleft([x, y, d])
				break
			if g[x][y] != u:
				g[x][y] = u
				h[u] += 1
				ok = True
			if x - 1 >= 0 and g[x - 1][y] == 0:
				if d + 1 < dist[u][x - 1][y]:
					dist[u][x - 1][y] = d + 1
					Q[u].append([x - 1, y, dist[u][x - 1][y]])
			if y - 1 >= 0 and g[x][y - 1] == 0:
				if d + 1 < dist[u][x][y - 1]:
					dist[u][x][y - 1] = d + 1
					Q[u].append([x, y - 1, dist[u][x][y - 1]])
			if x + 1 < n and g[x + 1][y] == 0:
				if d + 1 < dist[u][x + 1][y]:
					dist[u][x + 1][y] = d + 1
					Q[u].append([x + 1, y, dist[u][x + 1][y]])
			if y + 1 < m and g[x][y + 1] == 0:
				if d + 1 < dist[u][x][y + 1]:
					dist[u][x][y + 1] = d + 1
					Q[u].append([x, y + 1, dist[u][x][y + 1]])
	for i in range(1, p + 1):
		spd2[i] += spd[i]
	if ok == False:
		break
for i in range(10):
	if h[i] > 0:
		print(h[i], end=' ')


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)]):
	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)))