Задана строка \(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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач