Задана строка $$$s$$$, состоящая из строчных латинских букв.
К ней приходят $$$q$$$ запросов: дана другая строка $$$t$$$, состоящая из строчных латинских букв; проделайте следующие шаги:
Префикс-функция строки $$$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$$$ ($$$1 \le |s| \le 10^6$$$), состоящая из строчных латинских букв.
Во второй строке записано одно целое число $$$q$$$ ($$$1 \le q \le 10^5$$$) — количество запросов.
В каждой из следующих $$$q$$$ строк записан запрос: непустая строка $$$t$$$ ($$$1 \le |t| \le 10$$$), состоящая из строчных латинских букв.
На каждый запрос выведите значения префикс-функции строки $$$s+t$$$ на позициях $$$|s|+1, |s|+2, \dots, |s|+|t|$$$.
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
aacba 4 aaca cbbb aab ccaca
2 2 3 1 0 0 0 0 2 2 0 0 0 1 0 1
