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.
2
2 2
yz
1 1
2 2
yz
1 1
 1
11 2
thisisatest
3 5

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 1 

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 1 

 1 0 0 0 1 0 0 3 5 0 0 0 0 0 0 0 0 0 4 5 0 0 0 0 0 0 


// start of CP 3.0
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
//____By:sirjan13____
 
#define int long long
#define ld long double
#define mod 1000000007
#define mod1 mod
#define mod2 100000009
#define show(a) for(int i=0;i<a.size();i++) cout<<a[i & 1]<<" ";
#define fi first
#define se second
#define vi vector<int>
#define vs vector<string>
#define vll vector<ll>
#define pb push_back
#define pi pair<int,int>
#define si set<int>
#define sll set<ll>
#define pll pair<ll, ll>
#define sci(x) scanf("%d",&x)
#define scs(x)  scanf("%s", x)
#define scll(x) scanf("%I64d",&x)
#define all(v) v.begin(),v.end()
#define sot(v) sort(v.begin(), v.end())
#define maxheap priority_queue<int>
#define minheap priority_queue<int,vector<int>,greater<int>>
#define mp make_pair
#define fast_io() cin.sync_with_stdio(false);cout.sync_with_stdio(false);
#define PI 3.1415926535
#define long_zero 0ll
#define long_one 1ll
 
inline int sbt(int x){return __builtin_popcountll(x);}
 
using namespace std;
//using namespace __gnu_pbds;
 
#define TRACE
#ifdef TRACE
#define deb(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        cout << name << " : " << arg1 << std::endl;
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    }
#else
#define deb(...)
#endif
#define N 2013
 
//map<int, int> freq;
bool ok = 1;
int n, pichla, ek, x0, g, bd, m1, m2, curr, place22, place4, nb, maxi, chosen1, chosen2, chosen3, inplace, xs, res2, m, k, K, sabka_baap;
//multiset<pair<int, pi>> events;
// string res;
//int dp[(1 << 21)], v, b[N], a[N], swaps[22][22];
//string s[N];
// int res, h, adc[N];
// string s;
// bool oksd;
//string s[N], ss[N];
//si segments;
vector<pi> adj[N];
//vi buff;
//vi a, b;
//sii conf[2][2];
//map<int, vector<pi>> m[2];
//vector<pair<int, pair<int, pi>>> v[2];
 
vector<int> prefix_function (string s, int n) {
    vi dp(n);
    dp[0] = 0;
    for(int i = 1; i < n; i++) {
        int j = dp[i - 1];
        while(j > 0 && (s[i] != s[j]))
            j = dp[j - 1];
        if(s[i] == s[j]) j++;
        dp[i] = j;
    }
    return dp;
}
 
bool cmp(pair<int, pair<int, pi>> x, pair<int, pair<int, pi>> y) {
    return x.se.fi < y.se.fi;
}
 
inline int mul(int a, int b, int m = mod) { return ((a % mod) * (b % mod)) % m; }
inline int add(int a, int b, int m = mod) { return ((a % mod) + (b % mod)) % m; }
inline int sub(int a, int b, int m = mod) { return (a - b + m) % m; }
 
int fastpow(int a, int b) {
    int res = 1;
    while(b > 0) {
        if(b & 1) res = mul(res, a);
        a = mul(a, a);
        b >>= 1;
    }
    return res;
}
 
int modinv(int a) {
    return fastpow(a, mod - 2);
}
 
 
int tmp;//, a[N], b[N];
//char vis[N][N];
string s;
int res, open;
int dx[][2] = {{1, 1}, {-1, -1}, {-1, 1}, {1, -1}};
//int diag1[N], diag2[N];
//pi maxi_ij;
//int vis[N][N], dp[N], pos[N];
// int maxi;
// int res;
int d;
// string a, b;
// int x[27], y[27];
//int a[N][N];
//vector<pair<int, vi>> v;
int a[N], p[N];
 
 
 
int32_t main() {
    fast_io()
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    int t;
    cin >> t;
    while(t--) {
        cin >> n >> m;
        cin >> s;
        s = "%" + s;
        map<char, int> res;
        vi suff(n + 1, 0);
        for(int i = 1; i <= m; i++) {
            int x;
            cin >> x;
            suff[x] = 1;
        }
        for(int i = n - 1; i >= 1; i--) {
            suff[i] += suff[i + 1];
        }
        for(int i = 1; i <= n; i++) {
            res[s[i]] += (1 + suff[i]);
        }
        for(char i = 'a'; i <= 'z'; i++) {
            cout << res[i] << ' ';
        }
        cout << endl;
    }
    return 0;
}