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.
import java.io.*;
import java.util.*;
import java.text.*;
import java.lang.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.regex.*;
public class Myclass{
         public static Queue a[]=new Queue[300001];
         static int n,m;
         static boolean chk(int i,int j) {
        	 return (i>=0 && i<n && j>=0 && j<m);
         }
         public static void main(String[] args) 
        {
            InputReader in = new InputReader(System.in);
            PrintWriter pw = new PrintWriter(System.out);
            for(int i=0;i<10;i++) {
            	a[i]=new LinkedList<query>();
            }        
            n=in.nextInt();
            m=in.nextInt();
            int sz=in.nextInt();
            long p[]=new long [sz+1];
            for(int i=1;i<=sz;i++)
            	p[i]=in.nextLong();
            char s[][]=new char[n][m];
            int[][] val=new int[n][m];
            for(int i=0;i<n;i++)
            	s[i]=in.nextLine().toCharArray();
            for(int i=0;i<n;i++) {
            	for(int j=0;j<m;j++) {
            		if(s[i][j]-'0'<=9 && s[i][j]-'0'>=1) {
            			a[s[i][j]-'0'].add(new query(i,j,0));
            			val[i][j]=s[i][j]-'0';
            		}
            	}
            }
            int upto[]=new int[sz+1];
            while(true) {
            for(int k=1;k<=sz;k++) {
            	while(true && !a[k].isEmpty()) {
            		query q=(query) a[k].peek();
            		if(q.z>=upto[k]+p[k]) {
            			break;
            		}
            		q=(query) a[k].poll();
            		int i=q.x;
            		int j=q.y;
            		if(chk(i-1,j) && s[i-1][j]!='#' && val[i-1][j]==0) {
            			val[i-1][j]=k;
            			a[k].add(new query(i-1,j,q.z+1));
            		}
            		if(chk(i+1,j) && s[i+1][j]!='#' && val[i+1][j]==0) {
            			val[i+1][j]=k;
            			a[k].add(new query(i+1,j,q.z+1));
            		}
            		if(chk(i,j-1) && s[i][j-1]!='#' && val[i][j-1]==0) {
            			val[i][j-1]=k;
            			a[k].add(new query(i,j-1,q.z+1));
            		}
            		if(chk(i,j+1) && s[i][j+1]!='#' && val[i][j+1]==0) {
            			val[i][j+1]=k;
            			a[k].add(new query(i,j+1,q.z+1));
            		}
            	}
            	upto[k]+=p[k];
            }
            boolean fi=true;
            for(int i=0;i<=sz;i++) {
            	if(a[i].size()>0)
            		fi=false;
            }
            if(fi)
            	break;
            }
           
            int cnt[]=new int[sz+1];
            for(int i=0;i<n;i++) {
            	for(int j=0;j<m;j++) {
            		cnt[val[i][j]]++;
            	}
            }
            for(int i=1;i<=sz;i++)
            	pw.print(cnt[i]+" ");
            pw.flush();
            pw.close();
        
        
        }
         
		private static void debug(Object... o) {
			System.out.println(Arrays.deepToString(o));
		}
        static class InputReader 
        {
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;
 
        public InputReader(InputStream stream) 
        { 
            this.stream = stream;
        }
        public int snext() 
        {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) 
            {
                curChar = 0;
                try 
                {
                    snumChars = stream.read(buf);
                } 
                
                catch (IOException e) 
                {
                    throw new InputMismatchException();
                }
                
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
 
        public int nextInt() 
        {
            int c = snext();
            while (isSpaceChar(c)) 
            {
                c = snext();
            }
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = snext();
            }
            int res = 0;
            do 
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public long nextLong()
        {
            int c = snext();
            while (isSpaceChar(c)) 
            {
                c = snext();
            }
            int sgn = 1;
            if (c == '-') 
            {
                sgn = -1;
                c = snext();
            }
            long res = 0;
            do 
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public int[] nextIntArray(int n) 
        {
            int a[] = new int[n];
            for (int i = 0; i < n; i++) 
            {
                a[i] = nextInt();
            }
            return a;
        }
        static class tri implements Comparable<tri> {
            int p, c, l;
 
            tri(int p, int c, int l) {
                this.p = p;
                this.c = c;
                this.l = l;
            }
 
            public int compareTo(tri o) {
                return Integer.compare(l, o.l);
            }
        }
 
        public String readString()
        {
            int c = snext();
            while (isSpaceChar(c)) 
            {
                c = snext();
            }
            StringBuilder res = new StringBuilder();
            do 
            {
                res.appendCodePoint(c);
                c = snext();
            } while (!isSpaceChar(c));
            return res.toString();
        }
 
        public String nextLine() 
        {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            StringBuilder res = new StringBuilder();
            do 
            {
                res.appendCodePoint(c);
                c = snext();
            } while (!isEndOfLine(c));
            return res.toString();
        }
 
        public boolean isSpaceChar(int c) 
        {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
 
        private boolean isEndOfLine(int c) 
        {
            return c == '\n' || c == '\r' || c == -1;
        }
 
        public interface SpaceCharFilter
        {
            public boolean isSpaceChar(int ch);
        }
    }
        public static long mod = 1000000007;
        public static int d;
        public static int p;
        public static int q;
        
        public static int[] suffle(int[] a,Random gen)
        {
            int n = a.length;
            for(int i=0;i<n;i++)
            {
                int ind = gen.nextInt(n-i)+i;
                int temp = a[ind];
                a[ind] = a[i];
                a[i] = temp;
            }
            return a;
        }
        
        public static void swap(int a, int b){
            int temp = a;
            a = b;
            b = temp;
        }
        
       /* public static long primeFactorization(long n)
        {
             HashSet<Integer> a =new HashSet<Integer>();
        	long cnt=0;
            for(int i=2;i*i<=n;i++)
            {
                while(a%i==0)
                {
                    a.add(i);
                    a/=i;
                }
            }
            if(a!=1)
            	cnt++;
                //a.add(n);
            return cnt;
        }*/
        
        public static void sieve(boolean[] isPrime,int n)
        {
            for(int i=1;i<n;i++)
                isPrime[i] = true;
            
            isPrime[0] = false;
            isPrime[1] = false;
            
            for(int i=2;i*i<n;i++)
            {
                if(isPrime[i] == true)
                {
                    for(int j=(2*i);j<n;j+=i)
                        isPrime[j] = false;
                }
            }
        }
        
        public static int GCD(int a,int b)
        {
            if(b==0)
                return a;
            else
                return GCD(b,a%b);
        }
        
        public static long GCD(long a,long b)
        {
            if(b==0)
                return a;
            else
                return GCD(b,a%b);
        }
        
        public static void extendedEuclid(int A,int B)
        {
            if(B==0)
            {
                d = A;
                p = 1 ;
                q = 0;
            }
            else
            {
                extendedEuclid(B, A%B);
                int temp = p;
                p = q;
                q = temp - (A/B)*q;
            }
        }
        
        public static long LCM(long a,long b)
        {
            return (a*b)/GCD(a,b);
        }
        
        public static int LCM(int a,int b)
        {
            return (a*b)/GCD(a,b);
        }
        
        public static int binaryExponentiation(int x,int n)
        {
            int result=1;
            while(n>0)
            {
                if(n % 2 ==1)
                    result=result * x;
                x=x*x;
                n=n/2;
            }
            return result;
        }
        
        public static long binaryExponentiation(long x,long n)
        {
            long result=1;
            while(n>0)
            {
                if(n % 2 ==1)
                    result=result * x;
                x=x*x;
                n=n/2;
            }
            return result;
        }
        
        public static int modularExponentiation(int x,int n,int M)
        {
            int result=1;
            while(n>0)
            {
                if(n % 2 ==1)
                    result=(result * x)%M;
                x=(x%M*x)%M;
                n=n/2;
            }
            return result;
        }
        
        public static long modularExponentiation(long x,long n,long M)
        {
            long result=1;
            while(n>0)
            {
                if(n % 2 ==1)
                    result=(result%M * x%M)%M;
                x=(x%M * x%M)%M;
                n=n/2;
            }
            return result;
        }
        
        public static long modInverse(int A,int M)
        {
            return modularExponentiation(A,M-2,M);
        }
        
        public static long modInverse(long A,long M)
        {
            return modularExponentiation(A,M-2,M);
        }
        
        public static boolean isPrime(int n)
        {
            
            if (n <= 1)  return false;
            if (n <= 3)  return true;
            
            if (n%2 == 0 || n%3 == 0) 
                return false;
         
            for (int i=5; i*i<=n; i=i+6)
            {
                if (n%i == 0 || n%(i+2) == 0)
                   return false;
            }
            
            return true;
        }
        
         public static long[] shuffle(long[] a, Random gen){ 
                for(int i = 0, n = a.length;i < n;i++){ 
                    int ind = gen.nextInt(n-i)+i; 
                    long d = a[i]; 
                    a[i] = a[ind]; 
                    a[ind] = d; 
                } 
                return a; 
            }
        static class pair implements Comparable<pair>
        {
            Long x;
            Integer y;
            pair(long z,int sum)
            {
                this.x=z;
                this.y=sum;
            }
 

 
 
 
 
 
        public int compareTo(pair o) {
                int result = x.compareTo(o.x);
                if(result==0)
                    result = y.compareTo(o.y);
                
            return result;
            }  
            
            public String toString()
            {
                return x+" "+y;
            }
            
            public boolean equals(Object o)
            {
                if (o instanceof pair)
                {
                    pair p = (pair)o;
                    return p.x == x && p.y == y ;
                }
                return false;
            }
            
            public int hashCode()
            {
                return new Long(x).hashCode()*31 + new Long(y).hashCode();
            }
        }
       
 
      
}
class query {
	Integer x;
	Integer y,z;
	query(int x,int y,int z){
		this.x=x;
		this.y=y;
		this.z=z;
	}
	 public String toString()
     {
         return x+" "+y+" "+z;
     }
}