本文共 3611 字，大约阅读时间需要 12 分钟。
C. Perform the Combo
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You want to perform the combo on your opponent in one popular fighting game. The combo is the string ss consisting of nn lowercase Latin letters. To perform the combo, you have to press all buttons in the order they appear in ss. I.e. if s=s="abca" then you have to press 'a', then 'b', 'c' and 'a' again.
You know that you will spend mm wrong tries to perform the combo and during the ii-th try you will make a mistake right after pipi-th button (1≤pi<n1≤pi<n) (i.e. you will press first pipi buttons right and start performing the combo from the beginning). It is guaranteed that during the m+1m+1-th try you press all buttons right and finally perform the combo.
I.e. if s=s="abca", m=2m=2 and p=[1,3]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 tt independent test cases.
Input
The first line of the input contains one integer tt (1≤t≤1041≤t≤104) — the number of test cases.
Then tt test cases follow.
The first line of each test case contains two integers nn and mm (2≤n≤2⋅1052≤n≤2⋅105, 1≤m≤2⋅1051≤m≤2⋅105) — the length of ss and the number of tries correspondingly.
The second line of each test case contains the string ss consisting of nn lowercase Latin letters.
The third line of each test case contains mm integers p1,p2,…,pmp1,p2,…,pm (1≤pi<n1≤pi<n) — the number of characters pressed right during the ii-th try.
It is guaranteed that the sum of nn and the sum of mm both does not exceed 2⋅1052⋅105 (∑n≤2⋅105∑n≤2⋅105, ∑m≤2⋅105∑m≤2⋅105).
It is guaranteed that the answer for each letter does not exceed 2⋅1092⋅109.
Output
For each test case, print the answer — 2626 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
Copy
34 2abca1 310 5codeforces2 8 3 2 926 10qwertyuioplkjhgfdsazxcvbnm20 10 1 2 3 5 10 5 9 4
output
Copy
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 44, 'b' is 22 and 'c' is 22.
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 99, 'd' is 44, 'e' is 55, 'f' is 33, 'o' is 99, 'r' is 33 and 's' is 11.
【题意】
按开关，第i个时出错了，，就要从1开始按，就是1~i都多按了一遍，求最后各个开官按下的次数。
差分，设一个数组f，f[i]表示第i个前面的开关多按了几次，就是个差分数组，不过这个得倒着累加，最后别忘了加上原始数列中各个字母出现的次数。