您想在一款流行的格斗游戏中对对手进行连击。该组合是由 $$$n$$$ 小写拉丁字母组成的字符串 $$$s$$$。要执行组合,您必须按照 $$$s$$$ 中出现的顺序按下所有按钮。 IE。如果 $$$s=$$$"abca" 那么你必须再次按“a”,然后按“b”、“c”和“a”。
你知道你会花费 $$$m$$$ 错误尝试执行组合,并且在第 $$$i$$$ 次尝试期间,你会在第 $$$p_i$$$ 个按钮之后犯错误 ($$$1 \le p_i < n$$$) (即,你将向右按下第一个 $$$p_i$$$ 按钮并从头开始执行组合)。保证在第 $$$m+1$$$ 次尝试中按下所有按钮并最终执行组合。
即如果 $$$s=$$$"abca", $$$m=2$$$ 和 $$$p = [1, 3]$$$ 那么按下按钮的顺序将是 'a' (这里你犯了一个错误并从头开始执行组合), 'a', 'b', 'c', (这里你犯了一个错误并从头开始执行组合),'a' (注意此时你不会执行组合因为错误),'b','c','a'。
您的任务是计算每个按钮(字母)按下的次数。
您必须回答 $$$t$$$ 独立测试用例。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
然后是 $$$t$$$ 测试用例。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — $$$s$$$ 的长度和相应的尝试次数。
每个测试用例的第二行包含字符串 $$$s$$$,由 $$$n$$$ 小写拉丁字母组成。
每个测试用例的第三行包含 $$$m$$$ 整数 $$$p_1, p_2, \dots, p_m$$$ ($$$1 \le p_i < n$$$) — 在第 $$$i$$$ 次尝试期间向右按下的字符数。
保证$$$n$$$之和与$$$m$$$之和不超过$$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$, $$$\sum m \le 2 \cdot 10^5$$$)。
保证每个字母的答案不超过$$$2 \cdot 10^9$$$。
输出
对于每个测试用例,打印答案 - $$$26$$$ 整数:按下按钮“a”的次数,按下按钮“b”的次数,$$$\dots$$$,按下按钮“z”的次数。
示例
输入 #1
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
输出 #1
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
注意
第一个测试用例在问题陈述中进行了描述。错误的尝试是“a”、“abc”,最后的尝试是“abca”。按“a”的次数为 $$$4$$$,按“b”的次数为 $$$2$$$,按“c”的次数为 $$$2$$$。
在第二个测试用例中,有五个错误的尝试:“co”、“codeforc”、“cod”、“co”、“codeforce”,最后的尝试是“codeforces”。按“c”的次数为 $$$9$$$,“d”为 $$$4$$$,“e”为 $$$5$$$,“f”为 $$$3$$$,“o”为 $$$9$$$,“r”为 $$$3$$$,“s”为 $$$1$$$。