Codeforces Round 624 (Div. 3) |
---|
Закончено |
Вы хотите выполнить комбо против своего соперника в одном популярном файтинге. Комбо — это строка $$$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$$$.
Название |
---|