Задана строка \(s\), состоящая из строчных латинских букв.
К ней приходят \(q\) запросов: дана другая строка \(t\), состоящая из строчных латинских букв; проделайте следующие шаги:
- склеить \(s\) и \(t\);
- посчитать префикс-функцию полученной строки \(s+t\);
- выведите значения префикс-функции на позициях \(|s|+1, |s|+2, \dots, |s|+|t|\) (\(|s|\) и \(|t|\) — это длины строк \(s\) и \(t\), соответственно);
- вернуть строку обратно к \(s\).
Префикс-функция строки \(a\) — это последовательность \(p_1, p_2, \dots, p_{|a|}\), где \(p_i\) — это наибольшее значение \(k\) такое, что \(k < i\) и \(a[1..k]=a[i-k+1..i]\) (\(a[l..r]\) обозначает непрерывную подстроку строку \(a\) с позиции \(l\) до позиции \(r\) включительно). Другими словами, это наибольший собственный префикс строки \(a[1..i]\), который равен ее суффиксу такой же длины.
Выходные данные
На каждый запрос выведите значения префикс-функции строки \(s+t\) на позициях \(|s|+1, |s|+2, \dots, |s|+|t|\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
aba
6
caba
aba
bababa
aaaa
b
forces
|
0 1 2 3
1 2 3
2 3 4 5 6 7
1 1 1 1
2
0 0 0 0 0 0
|
|
2
|
aacba
4
aaca
cbbb
aab
ccaca
|
2 2 3 1
0 0 0 0
2 2 0
0 0 1 0 1
|