Perform the Combo

一台机器准备要打印一篇文章，有 $m$ 个打印操作 给出操作序列 $p_1,p_2, \dots ,p_m$ 和 长度为 $n$ 的字符串 $s$ 对于每个 $(1 \le i \le m)$，$p_i$ 表示该机器将位置 $1\sim p_i$ 上的所有字母打印了出来 最后，在所有操作做完后，该机器又将整个字符串 $s$ 打印了出来 请求出字母表中每个字母在文章中出现了多少次 ### 输入格式 第一行一个整数 $T$，表示数据的组数 对于每组数据： 第一行两个整数 $n,m$，分别表示字符串长度和操作数 第二行一个长度为 $n$ 的，由小写字母构成的字符串 $s$ 第三行 $m$ 个整数，表示操作序列 $p$ ### 输出格式 $T$ 行，每行 $26$ 个整数，分别表示每个字母出现的次数 每行第一个数表示 $\texttt{a}$ 出现的次数，第二个数表示 $\texttt{b}$ 出现的次数，以此类推 **说明与提示** $1\le T \le 10^4$ $2 \le n \le 2 \cdot 10^5$ $1 \le m \le 2 \cdot 10^5$ $\sum n,\sum m \le 2 \cdot 10^5$ $1 \le p_i <n$ 感谢 @[_Wolverine](https://www.luogu.com.cn/user/120362) 提供的翻译

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.

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 $ .

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'.

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

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

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 $ .