Вы хотите выполнить комбо против своего соперника в одном популярном файтинге. Комбо — это строка \(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\) независимых наборов входных данных.
Выходные данные
Для каждого набора входных данных выведите ответ на него — \(26\) целых чисел: количество раз, которое вы нажмете кнопку 'a', количество раз, которое вы нажмете кнопку 'b', \(\dots\), количество раз, которое вы нажмете кнопку 'z'.
Примечание
Первый набор входных данных разобран в условии задачи. Неверными попытками являются «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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
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
|