Kilani is playing a game with his friends. This game can be represented as a grid of size n × 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 ≤ n, m ≤ 1000, 1 ≤ p ≤ 9) — the size of the grid and the number of players.

The second line contains p integers s_i (1 ≤ s ≤ 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 ≤ x ≤ 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.
/*
ID: davidzh8
PROG: subset
LANG: JAVA
 */

import java.io.*;
import java.util.*;
import java.lang.*;

//        .--------------.
//        | Try First One|
//        '--------------'
//                |     .--------------.
//                |     |              |
//                V     V              |
//              .--------------.       |
//              |      AC.     |<---.  |
//              '--------------'    |  |
//              (True)|  |(False)   |  |
//           .--------'  |          |  |
//           |           V          |  |
//           |  .--------------.    |  |
//           |  |   Try Again  |----'  |
//           |  '--------------'       |
//           |                         |
//           |  .--------------.       |
//           '->| Try Next One |-------'
//              '--------------'
public class kilani {
    //Start Stub
    static long startTime = System.nanoTime();

    //Globals Go Here
    static int[] dx= new int[]{0,-1, 0, 1};
    static int[] dy= new int[]{-1, 0, 1, 0};
    static int n;
    static int m;
    //Globals End
    public static void main(String[] args) throws IOException {
        FastScanner sc = new FastScanner("kilani.in", true);
        FastWriter pw = new FastWriter("kilani.out", true);
        n= sc.ni();
        m= sc.ni();
        int p= sc.ni();
        int[] speed= new int[p];
        for (int x=0; x<p; x++){
            speed[x]= sc.ni();
        }
        int[][] graph= new int[n][m];
        Comparator<Node> comp= new Comparator<Node>() {
            @Override
            public int compare(Node a, Node b) {
                if (graph[a.a][a.b]!= graph[b.a][b.b]) return graph[a.a][a.b]-graph[b.a][b.b];
                if (a.steps != b.steps) return a.steps-b.steps;
                if (a.a != b.a) return a.a-b.a;
                return a.b-b.b;
            }
        };
        PriorityQueue<Node> dq= new PriorityQueue<>(comp);
        for (int i = 0; i < n; i++) {
            String line= sc.next();
            int j=0;
            for (char c: line.toCharArray()){
                if (c=='#') graph[i][j]= -2;
                else if (c=='.') graph[i][j]= -1;
                else {
                    graph[i][j]= c-'0'-1;
                    dq.offer(new Node(i, j, 0));
                }
                j++;
            }
        }

        PriorityQueue<Node> ids= new PriorityQueue<>(comp);

        while (!dq.isEmpty()){
            while (!dq.isEmpty()){
                ids.offer(dq.poll());
            }
            while (!ids.isEmpty()){
                Node cur = ids.poll();
                int curx = cur.a;
                int cury = cur.b;
                for (int x = 0; x < 4; x++) {
                    int movex = curx+dx[x];
                    int movey = cury+ dy[x];

                    if (valid(movex, movey) && graph[movex][movey]==-1){
                        if (cur.steps== speed[graph[curx][cury]]) dq.offer(new Node(curx, cury, 0));
                        else{
                            graph[movex][movey]= graph[curx][cury];
                            ids.offer(new Node(movex, movey, cur.steps+1));
                        }
                    }

                }

            }
/*
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    System.out.print(graph[i][j]+" ");
                }
                System.out.println();
            }
            System.out.println("NEW LINE");
            
 */


        }
        int[] count= new int[p];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (graph[i][j]>=0) count[graph[i][j]]++;
            }
        }
        for (int i: count){
            pw.print(i+" ");
        }






        /* End Stub */
        long endTime = System.nanoTime();
        //System.out.println("Execution Time: " + (endTime - startTime) / 1e9 + " s");
        pw.close();
    }
    public static boolean valid(int a, int b){
        return a>=0 && a<n && b>=0 && b<m;
    }


    static class Edge implements Comparable<Edge> {
        int w;
        int a;
        int b;

        public Edge(int w, int a, int b) {
            this.w = w;
            this.a = a;
            this.b = b;

        }

        public int compareTo(Edge obj) {
            if (obj.w == w) {
                if (obj.a == a) {
                    return b - obj.b;
                }
                return a - obj.a;
            } else return w - obj.w;
        }
    }

    static class Node {
        int a;
        int b;
        int steps;
        public Node(int a, int b, int s) {
            this.a = a;
            this.b = b;
            this.steps=s;
        }


    }

    static class SegmentTree {
        public long[] arr;
        public long[] tree;
        public int N;

        //Zero initialization
        public SegmentTree(int n) {
            N = n;
            arr = new long[N];
            tree = new long[4 * N + 1];
        }

        public long query(int treeIndex, int lo, int hi, int i, int j) {
            // query for arr[i..j]
            if (lo > j || hi < i)
                return 0;
            if (i <= lo && j >= hi)
                return tree[treeIndex];
            int mid = lo + (hi - lo) / 2;

            if (i > mid)
                return query(2 * treeIndex + 2, mid + 1, hi, i, j);
            else if (j <= mid)
                return query(2 * treeIndex + 1, lo, mid, i, j);

            long leftQuery = query(2 * treeIndex + 1, lo, mid, i, mid);
            long rightQuery = query(2 * treeIndex + 2, mid + 1, hi, mid + 1, j);

            // merge query results
            return merge(leftQuery, rightQuery);
        }

        public void update(int treeIndex, int lo, int hi, int arrIndex, long val) {
            if (lo == hi) {
                tree[treeIndex] = val;
                arr[arrIndex] = val;
                return;
            }

            int mid = lo + (hi - lo) / 2;

            if (arrIndex > mid)
                update(2 * treeIndex + 2, mid + 1, hi, arrIndex, val);
            else if (arrIndex <= mid)
                update(2 * treeIndex + 1, lo, mid, arrIndex, val);

            // merge updates
            tree[treeIndex] = merge(tree[2 * treeIndex + 1], tree[2 * treeIndex + 2]);
        }

        public long merge(long a, long b) {
            return (a + b);
        }
    }

    static class djset {
        int N;
        int[] parent;

        // Creates a disjoint set of size n (0, 1, ..., n-1)
        public djset(int n) {
            parent = new int[n];
            N = n;
            for (int i = 0; i < n; i++)
                parent[i] = i;
        }

        public int find(int v) {

            // I am the club president!!! (root of the tree)
            if (parent[v] == v) return v;

            // Find my parent's root.
            int res = find(parent[v]);

            // Attach me directly to the root of my tree.
            parent[v] = res;
            return res;
        }

        public boolean union(int v1, int v2) {

            // Find respective roots.
            int rootv1 = find(v1);
            int rootv2 = find(v2);

            // No union done, v1, v2 already together.
            if (rootv1 == rootv2) return false;

            // Attach tree of v2 to tree of v1.
            parent[rootv2] = rootv1;
            return true;
        }


    }

    static class FastScanner {
        public BufferedReader br;
        public StringTokenizer st;
        public InputStream is;

        public FastScanner(String name, boolean debug) throws IOException {
            if (debug) {
                is = System.in;
            } else {
                is = new FileInputStream(name);
            }
            br = new BufferedReader(new InputStreamReader(is), 32768);
            st = null;
        }


        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int ni() {
            return Integer.parseInt(next());
        }

        public long nl() {
            return Long.parseLong(next());
        }

        public double nd() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return str;
        }
    }

    static class FastWriter {
        public PrintWriter pw;

        public FastWriter(String name, boolean debug) throws IOException {
            if (debug) {
                pw = new PrintWriter(System.out);
            } else {
                pw = new PrintWriter(new BufferedWriter(new FileWriter(new File(name))));
            }
        }

        public void println(Object text) {
            pw.println(text);
        }

        public void print(Object text) {
            pw.print(text);
        }

        public void close() {
            pw.close();
        }

        public void flush() {
            pw.flush();
        }
    }

}


