Захват территорий

Виктор после уроков играет в одну интересную игру со своими друзьями. Поле для игры представляет из себя таблицу размером n×m, где каждая клетка или свободна, или недоступна (например, тетрадный листок). У каждого игрока есть один или несколько замков на поле (ни одна клетка не содержит более одного замка).

Игра происходит в несколько туров. В каждом туре игроки по очереди захватывают свободные клетки: сначала ходит первый игрок, затем ходит второй игрок, и так далее. Ход происходит следующим образом: игрок пытается захватить и построить в пустых клетках поблизости от каждого из имеющихся у него замков новые замки. Игрок i может расшириться из клетки со своим замком в свободную клетку, если до неё можно добраться за не более чем si (где si — это показатель скорости игрока) движений влево, вверх, вправо или вниз, не проходящих через недоступные клетки или клетки с замками других игроков. Игрок рассматривает множество клеток, в которые он может расшириться, и моментально строит во всех них свой замок. После этого ход переходит к следующему игроку.

Игра заканчивается тогда, когда никто из игроков больше не может сделать ход. Вам предоставлено поле игры и скорости расширения для каждого участника. Виктор хотел бы узнать, сколько клеток будет контролировать каждый игрок (иметь там замок) после того как игра закончится.

Входные данные
Первая строка содержит три целых числа n, m и p (1≤n,m≤1000, 1≤p≤9) — размеры поля и количество игроков.

Вторая строка содержит p целых чисел si (1≤s≤109) — скорости расширения для каждого игрока.

Следующие n строк задают игровое поле. Каждая из них состоит из m символов, где «.» обозначает свободную клетку, «#» обозначает недоступную клетку, а цифра x (1≤x≤p) обозначает замок, принадлежащий игроку x.

Гарантируется, что у каждого игрока есть хотя бы один замок на поле.

Выходные данные
Выведите p целых чисел — количество клеток, контролируемых каждым игроком после конца игры.

Примеры
входные данные
3 3 2
1 1
1..
...
..2
выходные данные
6 3
входные данные
3 4 4
1 1 1 1
....
#...
1234
выходные данные
1 4 3 3

Миниатюры

 

0