E. Запросы про префикс функцию
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана строка $$$s$$$, состоящая из строчных латинских букв.

К ней приходят $$$q$$$ запросов: дана другая строка $$$t$$$, состоящая из строчных латинских букв; проделайте следующие шаги:

  1. склеить $$$s$$$ и $$$t$$$;
  2. посчитать префикс-функцию полученной строки $$$s+t$$$;
  3. выведите значения префикс-функции на позициях $$$|s|+1, |s|+2, \dots, |s|+|t|$$$ ($$$|s|$$$ и $$$|t|$$$ — это длины строк $$$s$$$ и $$$t$$$, соответственно);
  4. вернуть строку обратно к $$$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$$$ ($$$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