Kilani và trò chơi

Có một bàn chơi dạng lưới kích thước $n\times m$. Mỗi ô hoặc là ô trống, hoặc là ô bị chặn, hoặc chứa lâu đài của một người chơi (mỗi ô có nhiều nhất một lâu đài). Có $p$ người chơi, mỗi người sở hữu ít nhất một lâu đài lúc ban đầu.

Trò chơi diễn ra theo các vòng. Trong mỗi vòng, các người chơi lần lượt mở rộng theo thứ tự: người chơi $1$ mở rộng trước, rồi đến người chơi $2$, và cứ thế đến người chơi $p$.

Khi đến lượt, người chơi $i$ xét toàn bộ các lâu đài mình đang sở hữu. Với mỗi ô trống mà từ một lâu đài của người chơi $i$ có thể đi tới trong tối đa $s_i$ bước theo bốn hướng (lên, xuống, trái, phải), mà không đi qua ô bị chặn hay ô đã bị người chơi khác chiếm, thì người chơi $i$ sẽ đặt lâu đài lên ô đó. Tất cả các ô thoả điều kiện được chiếm đồng thời trong lượt này, sau đó mới chuyển lượt cho người kế tiếp.

Trò chơi kết thúc khi không người chơi nào có thể chiếm thêm ô nào. Hãy cho biết số ô mà mỗi người chơi kiểm soát khi trò chơi kết thúc.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $p$: kích thước lưới và số người chơi.
• Dòng thứ hai chứa $p$ số nguyên $s_1,s_2,\dots ,s_p$: tốc độ mở rộng của từng người chơi.
• $n$ dòng tiếp theo, mỗi dòng gồm $m$ ký tự mô tả lưới: ký tự . là ô trống, ký tự # là ô bị chặn, và chữ số $x$ ($1\le x\le p$) là ô chứa lâu đài của người chơi $x$.

Dữ liệu ra

In ra $p$ số nguyên: số ô mà mỗi người chơi kiểm soát sau khi trò chơi kết thúc.

Ràng buộc

• $1\le n,m\le 1000$
• $1\le p\le 9$
• $1\le s_i\le {10}^9$
• Mỗi người chơi có ít nhất một lâu đài trên lưới.

Ví dụ