29080번 - Парады Ришелье 다국어

Сегодня кардинал Ришелье решил построить своих гвардейцев. На плацу построено $n$ шеренг. Каждый гвардеец в шеренге одет в форму некоторого цвета. Всего существует 26 цветов формы. Каждому типу форму соответствует своя буква латинского алфавита.

Можно считать, что каждая шеренга задается строкой $s_i$, в начале строки находится начало шеренги, в конце строки --- конец шеренги.

Планируется провести несколько показательных парадов. У кардинала Ришелье есть строка $t$, с помощью которой он будет составлять каждый из парадов. Всего будет проведено $k$ парадов следующим образом: для $j$-го парада Ришелье вычеркнет из строки $t$ некоторую подстроку длиной $j$, оставшуюся строку он обозначит $t_j$, затем выберет все шеренги, префикс которых равен $t_j$, и они будут задействованы в $j$-м параде.

От вас требуется для каждого $j$ от $1$ до $k$ найти, какое максимальное количество шеренг можно задействовать в $j$-м параде.

В первой строке находится единственная строка $t$ ($1 \le |t| \le 10^5$), состоящая из строчных латинских букв.

В следующей строке находятся два натуральных числа $n$, $k$ ($1 \le n \le 10^5$, $1 \le k < |t|$) --- количество построенных на плацу шеренг и количество парадов соответсвенно.

В каждой из следующих $n$ строк находится описание шеренги $s_i$ --- непустая строка, состоящая из строчных латинских букв.

Суммарная длина $s_i$ не превосходит $10^5$.

В единственной строке выведите $k$ чисел --- максимальное количество шеренг, участвующих в $j$-м параде.