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 \le 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 \le t \le 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 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 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, \dots, p_m$ ($1 \le 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 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$, $\sum m \le 2 \cdot 10^5$).

It is guaranteed that the answer for each letter does not exceed $2 \cdot 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', $\dots$, 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$.

Difficulty: introductory

Starter code:

Solutions:
from string import ascii_lowercase

t = int(input())

for _ in range(t):
    n, m = [int(x) for x in input().split()]

    s = input()
    count = {x : 0 for x in ascii_lowercase}
    errors = [int(x) for x in input().split()]

    errors = sorted(errors)

    e_idx = 0
    for j, c in enumerate(s):
        while e_idx < m and errors[e_idx] <= j:
            e_idx += 1
        count[c] += (m - e_idx) + 1

    print(*[count[c] for c in ascii_lowercase])


for eps in range(int(input())):
    n, m = map(int, input().split())
    s = input()
    a = list(map(int, input().split()))
    a.sort()
    ans = [0] * 26
    j = 0
    for i in range(n):
        while j < m and i >= a[j]:
            j += 1
        ans[ord(s[i]) - ord("a")] += m - j + 1
    for elem in ans:
        print(elem, end=" ")
    print()

from sys import stdin


def solve():
    n, m = list(map(int, input().split()))
    s = input()
    ml = list(map(int, input().split()))
    ml.append(n)
    ml.sort(reverse=True)
    prev = 0
    ans = [0] * 26
    for i in range(m, -1, -1):
        for j in range(prev, ml[i]):
            ans[ord(s[j]) - ord('a')] += i + 1
        prev = ml[i]
    print(*ans)


for i in range(int(input())):
    solve()


import sys
input = sys.stdin.readline


alph = "abcdefghijklmnopqrstuvwxyz"
to_int = {v: i for i, v in enumerate(alph)}

t = int(input())
for _ in range(t):
    n, m = list(map(int, input().split()))
    s = input()
    p = list(map(int, input().split()))
    num = [[0] * (n + 1) for i in range(26)]
    for i in range(n):
        tmp = to_int[s[i]]
        for j in range(26):
            if tmp == j:
                num[j][i + 1] = num[j][i] + 1
            else:
                num[j][i + 1] = num[j][i]
    ans = [0] * 26
    for i in range(len(ans)):
        for j in p:
            ans[i] += num[i][j]
        ans[i] += num[i][-1]
    print(*ans)

ans = []
empt = [0 for i in range(26)]
s = 'abcdefghijklmnopqrstuvwxyz'
pos = {s[i]: i for i in range(26)}

for t in range(int(input())):
	[n, m] = [int(i) for i in input().split()]
	seq = input()
	err = [(int(i) - 1) for i in input().split()]
	freq = {}
	for i in err:
		if i in freq:
			freq[i] += 1
		else:
			freq[i] = 1

	dp = [0 for i in range(n)]
	dp[n - 1] = 1
	for i in range(n - 2, -1, -1):
		dp[i] = dp[i + 1]
		if i in freq:
			dp[i] += freq[i]
	a = empt + []
	for i in range(n):
		a[pos[seq[i]]] += dp[i]
	ans.append(' '.join([str(i) for i in a]))

print('\n'.join(ans))


t=int(input())
while(t):
        t-=1
        co=[0]*26
        n,m=list(map(int,input().split()))
        reco=[0]*n
        s=input()
        a=list(map(int,input().split()))
        for i in range(m):
                reco[0]+=1
                reco[a[i]]+=-1
        reco[0]+=1
        for i in range(1,n):
                reco[i]=reco[i]+reco[i-1]
        for i in range(n):
                z=ord(s[i])-97
                co[z]+=reco[i]
        print(*co)


t=int(input())
while t:
    n,m=map(int,input().split())
    s=input()
    p=input().split()
    for i in range(m):
        p[i]=int(p[i])
    p.sort()
    ls=[]
    count=0
    for i in range(m):
        if(i==0):
            count+=1
            if(i==m-1):
                ls.append([p[i],count])
        elif(p[i]==p[i-1]):
            count+=1
            if(i==m-1):
                ls.append([p[i],count])
        else:
            ls.append([p[i-1],count])
            count=1
            if(i==m-1):
                ls.append([p[i],count])
    ls.append([n,0])            
    visited=[1 for i in range(n)]
    count=m
    j=0
    for i in range(n):
        if(i<ls[j][0]):
            visited[i]+=count
        else:
            count-=ls[j][1]
            j+=1
            visited[i]+=count
    ans=[0 for i in range(26)]
    for i in range(n):
        ans[ord(s[i])-97]+=visited[i]
    print(*ans)
    t-=1

import string

for _ in range(int(input())):
    n, m = list(map(int, input().split()))
    s = input()
    p = list(map(int, input().split())) + [-1]

    d = {c: [0] for c in string.ascii_lowercase}

    for i in s:
        for c in string.ascii_lowercase:
            d[c].append(d[c][-1])

        d[i][-1] += 1

    ans = {c: 0 for c in string.ascii_lowercase}

    for i in p:
        for c in string.ascii_lowercase:
            ans[c] += d[c][i]

    print(*list(ans.values()))


import sys
input = sys.stdin.readline

t=int(input())

for tests in range(t):
    n,m=list(map(int,input().split()))
    S=input().strip()
    P=list(map(int,input().split()))

    SCORE=[[0]*26 for i in range(n)]

    for i in range(n):
        for j in range(26):
            SCORE[i][j]=SCORE[i-1][j]
            
        SCORE[i][ord(S[i])-97]+=1

    ANS=[0]*26

    for p in P:
        for j in range(26):
            ANS[j]+=SCORE[p-1][j]

    for j in range(26):
        ANS[j]+=SCORE[-1][j]

    print(*ANS)
    

    



import math

def rints():
    return list(map(int,input().split()))


t = int(input())
for _ in range(t):
    n,m = rints()
    s = input()
    p = rints()
    occs = [0] * 26
    
    p.sort()

    ai = 0
    active = [1]*n
    rem = m+1
    for pi in p:
        for i in range(ai,pi):
            active[i] = rem
        rem -= 1
        ai = pi

    for i in range(n):
        c = ord(s[i]) - ord('a')
        occs[c] += active[i]

    print(*occs)



import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n, m = list(map(int, input().split()))
    s = list([ord(x)-97 for x in input().rstrip()])
    p = [n] + sorted(map(int, input().split()), reverse=True)
    ans = [0]*26

    i = 0
    for i in range(n):
        while p and p[-1] == i:
            p.pop()
        ans[s[i]] += len(p)

    print(*ans)