| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 2 | 0 | 0 | 0.000% |
Сегодня кардинал Ришелье решил построить своих гвардейцев. На плацу построено $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$-м параде.
abcdef 3 3 abcefx abcdfab abcdf
2 2 3
abcab 3 4 aaba aabz ad
0 2 0 3