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.util.*;
import java.io.*;
import java.math.BigInteger;
public class Solution
{
     static class Pair<A,B>{
        A parent;
        B rank;
        Pair(A parent,B rank)
        {
            this.rank=rank;
            this.parent=parent;
        }
    }
//    static int find(Pair pr[],int i)
//    {
//        if(i==pr[i].parent)
//            return i;
//        else
//        {
//            pr[i].parent=find(pr,pr[i].parent);
//            return pr[i].parent;
//        }
//    }
//    static void join(Pair[] pr,int i,int j)
//    {
//        i=find(pr,i);
//        j=find(pr,j);
//        if(i==j)
//            return;
//        if(pr[i].rank>=pr[j].rank)
//        {
//            pr[j].parent=i;
//            pr[i].rank+=pr[j].rank;
//        }
//        else
//        {
//            pr[i].parent = j;
//            pr[j].rank+=pr[i].rank;
//        }
//    }
    static void swap(char ar[],int i,int j)
    {
        char f = ar[i];
        ar[i]=ar[j];
        ar[j]=f;
    }
    static ArrayList<Integer> graph[] ;
    static TreeSet<Long> ts;
    public static void main (String[] args) throws IOException
    {
        StringBuilder sb = new StringBuilder();
        FastReader s1 = new FastReader();
        int t=s1.I();
        while(t--!=0)
        {
             int n=s1.I();
             int m=s1.I();
             String s = s1.next();
             int ar[] = new int[m];
             for(int i=0;i<m;i++)
                 ar[i]=s1.I();
             int ans[] = new int[n+1];
             for(int i=0;i<m;i++)
             {
                 ans[ar[i]]++;
             }
//             for(int I:ans)
//             {
//                 System.out.print(I+" ");
//             }
//             System.out.println("2nd");
             ans[n]++;
             for(int i=n-1;i>=0;i--)
             {
                 ans[i]+=ans[i+1];
             }
//             for(int I:ans)
//             System.out.print(I+" ");
//             System.out.println("exit");
             int temp[] = new int[26];
             for(int i=0;i<n;i++)
             {
                 temp[s.charAt(i)-'a']+=(ans[i+1]);
             }
             for(int i=0;i<26;i++)
                 sb.append(temp[i]+" ");
             sb.append("\n");
        }
        System.out.println(sb);
    }
    static boolean print(int h,int b,int a)
    {
        if(h*h==(a*a+b*b))
            return true;
        return false;
    }
    static long min(long no,long temp)
    {
        if(no<temp)
        {
            return -1;
        }
        long ans=no-temp;
        long max=-1;
        int n = (int)(Math.log(no)/Math.log(2));
        long curr=temp;
        for(int i=n;i>=0;i--)
        {
            long demo=(long)Math.pow(2, i);
            long h=(demo|curr);
            if(h<=no && h>max)
            {
                max=h;
                curr=h;
            }
        }
        return max;
    }
    static int dayofweek(long d, int m, long y) 
{ 
    int t[] = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 }; 
    y -= (m < 3) ? 1 : 0; 
    return (int)( y + y/4 - y/100 + y/400 + t[(m-1)] + d) % 7; 
}
        static String preprocess(String s)
    {
        StringBuilder sb = new StringBuilder();
        sb.append("@#");
        for(int i=0;i<s.length();i++)
        {
            sb.append(s.charAt(i)).append("#");
        }
        sb.append("$");
        return sb.toString();
    }
    static String LPS(String s)
    {
        String snew = preprocess(s);
        int n = snew.length();
//        System.out.println(snew);
        int c = 0,r = 0;
        int maxlen = 0;
        int index=0;
        int len[] = new int[n];
        for(int i=1;i<n-1;i++)
        {
            int mirr = c-(i-c);
            if(i<r)
            {
                len[i]=Math.min(len[mirr],r-i);
            }
      //      System.out.println(i+" ");
            while(snew.charAt(i+len[i])==snew.charAt(i-len[i]))
                len[i]++;
            if(i+len[i]>r)
            {
                c = i;
                r = i+len[i];
            }
//            System.out.println(c+" "+i+" "+snew.charAt(i)+" "+len[i]+" "+maxlen+" "+index);
            if(len[i]>maxlen)
            {
//                System.out.println("inside");
                maxlen = len[i];
                index = i;
            }
        }
        maxlen--;
        int left = (index-maxlen-1)/2;
        int right = left+maxlen;
        return s.substring(left, right);
    }
    static long phi(long n)
    {
        long result=n;
        for(int i=2;i<=Math.sqrt(n);i++)
        {
            if(n%i==0)
            {
                result-=result/i;
            }
            while(n%i==0)
            {
                n=n/i;
            }
        }
        if(n>1)
        {
            result-=(result/n);
        }
        return result;
    }
    static ArrayList<Integer> primeFactor(int n)
    {
        ArrayList<Integer> ans = new ArrayList<>();
        if(n%2==0)
            ans.add(2);
        while (n%2==0)
        {   
            n /= 2;
        }
        for (int i = 3; i <= Math.sqrt(n); i+= 2)
        {
            if(n%i==0)
                ans.add(i);
            while (n%i == 0)
            {
                n /= i;
            }
        }
        if (n > 2)
            ans.add(n);
        return ans;
    }
    static int longestSubSeg(int a[], int n,int k)
    {
        int cnt0 = 0;
        int l = 0;
        int max_len = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == 0)
                cnt0++;
            while (cnt0 > k) {
                if (a[l] == 0)
                    cnt0--;
                l++;
            }
            max_len = Math.max(max_len, i - l + 1);
        }
        
        return max_len;
    }
    static void dfs(int index,boolean ar[])
    {
        ar[index]=true;
        for(int i=0;i<graph[index].size();i++)
        {
            if(!ar[graph[index].get(i)])
            {
                dfs(graph[index].get(i),ar);
            }
        }
    }
    static int binary(int left,int right,int ar[],int no)
    {
        int mid=(left+right)/2;
        if(Math.abs(right-left)<=1)
        {
            if(no>=ar[right])
            {
                return right+1;
            }
            else if(no<ar[left])
            {
                return left;
            }
            else
            {
                return left+1;
            }
        }
        if(ar[mid]>no)
        {
            right=mid-1;
            return binary(left, right, ar, no);
        }
        else{
            left=mid;
            return binary(left, right, ar, no);
        }
    }
    static class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader()
        {
            br = new BufferedReader(new
                             InputStreamReader(System.in));
        }
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int I()
        {
            return Integer.parseInt(next());
        }
        
        long L()
        {
            return Long.parseLong(next());
        }
        
        double D()
        {
            return Double.parseDouble(next());
        }
        
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
    static long gcd(long a,long b)
    {
        if(a%b==0)
            return b;
        return gcd(b,a%b);
    }
    static float power(float x, int y)
    {
        float temp;
        if( y == 0)
            return 1;
        temp = power(x, y/2);
        
        if (y%2 == 0)
            return temp*temp;
        else
        {
            if(y > 0)
                return x * temp * temp;
            else
                return (temp * temp) / x;
        }
    }
    static long pow(long x, long y)
    {
        int p = 1000000007;
        long res = 1;
        x = x % p;
        while (y > 0)
        {
            if((y & 1)==1)
                res = (res * x) % p;
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }
    static ArrayList<Integer> sieveOfEratosthenes(int n)
    {
        ArrayList<Integer> arr=new ArrayList<Integer>();
        boolean prime[] = new boolean[n+1];
        for(int i=2;i<n;i++)
            prime[i] = true;
        
        for(int p = 2; p*p <=n; p++)
        {
            if(prime[p] == true)
            {
                arr.add(p);
                for(int i = p*p; i <= n; i += p)
                    prime[i] = false;
            }
        }
        return arr;
    }
}