Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

C. Выполни комбо
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы хотите выполнить комбо против своего соперника в одном популярном файтинге. Комбо — это строка $$$s$$$, состоящая из $$$n$$$ строчных букв латинского алфавита. Чтобы выполнить комбо, вам нужно нажать все кнопки в том порядке, в котором они появляются в $$$s$$$. То есть, если $$$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'.

Пример
Входные данные
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
Примечание

Первый набор входных данных разобран в условии задачи. Неверными попытками являются «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$$$.