Problem: You want to perform the combo on your opponent in one popular fighting game. The combo is the string s consisting of n lowercase Latin letters. To perform the combo, you have to press all buttons in the order they appear in s. I.e. if s="abca" then you have to press 'a', then 'b', 'c' and 'a' again.

You know that you will spend m wrong tries to perform the combo and during the i-th try you will make a mistake right after p_i-th button (1 ≤ p_i < n) (i.e. you will press first p_i buttons right and start performing the combo from the beginning). It is guaranteed that during the m+1-th try you press all buttons right and finally perform the combo.

I.e. if s="abca", m=2 and p = [1, 3] then the sequence of pressed buttons will be 'a' (here you're making a mistake and start performing the combo from the beginning), 'a', 'b', 'c', (here you're making a mistake and start performing the combo from the beginning), 'a' (note that at this point you will not perform the combo because of the mistake), 'b', 'c', 'a'.

Your task is to calculate for each button (letter) the number of times you'll press it.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases.

Then t test cases follow.

The first line of each test case contains two integers n and m (2 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ m ≤ 2 ⋅ 10^5) — the length of s and the number of tries correspondingly.

The second line of each test case contains the string s consisting of n lowercase Latin letters.

The third line of each test case contains m integers p_1, p_2, ..., p_m (1 ≤ p_i < n) — the number of characters pressed right during the i-th try.

It is guaranteed that the sum of n and the sum of m both does not exceed 2 ⋅ 10^5 (∑ n ≤ 2 ⋅ 10^5, ∑ m ≤ 2 ⋅ 10^5).

It is guaranteed that the answer for each letter does not exceed 2 ⋅ 10^9.

Output

For each test case, print the answer — 26 integers: the number of times you press the button 'a', the number of times you press the button 'b', ..., the number of times you press the button 'z'.

Example

Input


3
4 2
abca
1 3
10 5
codeforces
2 8 3 2 9
26 10
qwertyuioplkjhgfdsazxcvbnm
20 10 1 2 3 5 10 5 9 4


Output


4 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 9 4 5 3 0 0 0 0 0 0 0 0 9 0 0 3 1 0 0 0 0 0 0 0 
2 1 1 2 9 2 2 2 5 2 2 2 1 1 5 4 11 8 2 7 5 1 10 1 5 2 

Note

The first test case is described in the problem statement. Wrong tries are "a", "abc" and the final try is "abca". The number of times you press 'a' is 4, 'b' is 2 and 'c' is 2.

In the second test case, there are five wrong tries: "co", "codeforc", "cod", "co", "codeforce" and the final try is "codeforces". The number of times you press 'c' is 9, 'd' is 4, 'e' is 5, 'f' is 3, 'o' is 9, 'r' is 3 and 's' is 1.

Solution (in JAVA):

Solution:

import java.io.*;
import java.util.*;
import java.math.*;

public class Main { 
    
    public static void main(String[] args) throws java.lang.Exception { 
        //Reader pm =new Reader(); 
        Scanner pm = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int t = pm.nextInt();
        while(t-- > 0){
            int n = pm.nextInt();
            int m = pm.nextInt();
            Integer[] a = new Integer[m];
            String s = pm.next();
            char[] c = s.toCharArray();
            ArrayList<Integer> al = new ArrayList();
            for(int i=0;i<m;i++)
                a[i] = pm.nextInt();
            Arrays.sort(a);
            int[] arr1 = new int[n];
            int[] arr2 = new int[m];
            for(int i=0;i<n;i++){
                arr1[i] = i+1;
            }
            for(int i=0;i<m;i++){
                arr2[i] = a[i];
            }
            int[] hash2=new int[26];
            if(n == 1){
                hash2[(int)s.charAt(0)-97]++;
                for(int i=0;i<hash2.length;i++)
                    System.out.print(hash2[i]+" ");
                System.out.println();
                continue;
            }
            ArrayList<Integer> out = countEleLessThanOrEqual(arr1, arr2, arr1.length, arr2.length); 
            //System.out.println(out);
            TreeMap<Character,Integer> ts = new TreeMap<>();
            for(int i=0;i<out.size();i++){
                int pl = out.get(i);
                out.set(i,m-pl);
                
                //System.out.println(out);
            }
            for(int i=0;i<out.size();i++){
                int pl2 = out.get(i);
                out.set(i,pl2+1);
            }
            //System.out.println(out);
            for(int i=0;i<n;i++){
                if(ts.get(s.charAt(i)) == null)
                    ts.put(s.charAt(i),out.get(i));
                else{
                    int alr = ts.get(s.charAt(i));
                    ts.put(s.charAt(i),(alr+out.get(i)));
                }
            }
            //System.out.println(ts);
            Set<Character> set = ts.keySet();
            Iterator it = set.iterator();
            int[] hash = new int[26];
            while(it.hasNext()){
                Character cl = (Character)it.next();
                int posT = (int)cl - 97;
                //System.out.print(ts.get(cl)+" ");
                hash[posT] = ts.get(cl);
            }
            for(int i=0;i<hash.length;i++)
                System.out.print(hash[i]+" ");
            System.out.println();
        }
        
    }
    
    static int binary_search(int arr[], int l, int h, int x) { 
		while (l <= h) 
		{ 
			int mid = (l+h) / 2; 
	
			// if 'x' is greater than or equal to arr[mid], 
			// then search in arr[mid+1...h] 
			if (arr[mid] < x) 
				l = mid + 1; 
	
			// else search in arr[l...mid-1]	 
			else
				h = mid - 1;	 
		} 
		
		// required index 
		return h; 
	} 
	
	// method to count for each element in 1st array, 
	// elements less than or equal to it in 2nd array 
	static ArrayList<Integer> countEleLessThanOrEqual(int arr1[], int arr2[], 
								int m, int n) { 
		// sort the 2nd array 
		Arrays.sort(arr2); 
		
		// for each element of 1st array 
		ArrayList<Integer> ret = new ArrayList<>();
		for (int i=0; i<m; i++) { 
			// last index of largest element 
			// smaller than or equal to x 
			int index = binary_search(arr2, 0, n-1, arr1[i]); 
			
			// required count for the element arr1[i] 
			ret.add(index+1);
			//System.out.print((index+1) + " "); 
		} 
		return ret;
	} 
    
    static class Reader { 
        final private int BUFFER_SIZE = 1 << 16; 
        private DataInputStream din; 
        private byte[] buffer; 
        private int bufferPointer, bytesRead; 
  
        public Reader() 
        { 
            din = new DataInputStream(System.in); 
            buffer = new byte[BUFFER_SIZE]; 
            bufferPointer = bytesRead = 0; 
        } 
  
        public Reader(String file_name) throws IOException 
        { 
            din = new DataInputStream(new FileInputStream(file_name)); 
            buffer = new byte[BUFFER_SIZE]; 
            bufferPointer = bytesRead = 0; 
        } 
  
        public String readLine() throws IOException 
        { 
            byte[] buf = new byte[64]; // line length 
            int cnt = 0, c; 
            while ((c = read()) != -1) 
            { 
                if (c == '\n') 
                    break; 
                buf[cnt++] = (byte) c; 
            } 
            return new String(buf, 0, cnt); 
        } 
  
        public int nextInt() throws IOException 
        { 
            int ret = 0; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
            do
            { 
                ret = ret * 10 + c - '0'; 
            }  while ((c = read()) >= '0' && c <= '9'); 
  
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        public long nextLong() throws IOException 
        { 
            long ret = 0; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
            do { 
                ret = ret * 10 + c - '0'; 
            } 
            while ((c = read()) >= '0' && c <= '9'); 
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        public double nextDouble() throws IOException 
        { 
            double ret = 0, div = 1; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
  
            do { 
                ret = ret * 10 + c - '0'; 
            } 
            while ((c = read()) >= '0' && c <= '9'); 
  
            if (c == '.') 
            { 
                while ((c = read()) >= '0' && c <= '9') 
                { 
                    ret += (c - '0') / (div *= 10); 
                } 
            } 
  
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        private void fillBuffer() throws IOException 
        { 
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
            if (bytesRead == -1) 
                buffer[0] = -1; 
        } 
  
        private byte read() throws IOException 
        { 
            if (bufferPointer == bytesRead) 
                fillBuffer(); 
            return buffer[bufferPointer++]; 
        } 
  
        public void close() throws IOException 
        { 
            if (din == null) 
                return; 
            din.close(); 
        } 
    }
}