리슐리외의 사열

리슐리외 추기경이 오늘 근위병들을 정렬하기로 했다. 연병장에는 $n$개의 대열이 있다. 대열의 각 근위병은 어떤 색의 제복을 입고 있다. 제복 색은 총 26가지이며, 각 색은 라틴 알파벳의 한 글자로 나타낸다.

각 대열은 문자열 $s_i$로 주어진다. 문자열의 시작이 대열의 앞, 문자열의 끝이 대열의 뒤이다.

추기경은 여러 번의 시범 행진을 계획했다. 리슐리외는 행진을 구성할 때 문자열 $t$를 사용한다. 행진은 모두 $k$번 열리며, 다음과 같이 진행된다. $j$번째 행진에서 리슐리외는 $t$에서 길이가 $j$인 부분 문자열 하나를 지우고, 남은 문자열을 $t_j$라고 적는다. 그다음 접두사가 $t_j$와 같은 모든 대열을 고르고, 이 대열들이 $j$번째 행진에 참여한다.

첫 줄에 소문자 라틴 알파벳으로 이루어진 문자열 $t$가 주어진다 ($1 \le |t| \le 10^5$).

둘째 줄에 두 자연수 $n$, $k$가 주어진다 ($1 \le n \le 10^5$, $1 \le k < |t|$). $n$은 대열의 수, $k$는 행진의 수이다.

이어지는 $n$개의 줄에 각 대열의 문자열 $s_i$가 주어진다. 빈 문자열이 아니며 소문자 라틴 알파벳으로 이루어져 있다.

모든 $s_i$의 길이 합은 $10^5$을 넘지 않는다.

한 줄에 $k$개의 정수를 출력한다. $j$번째 수는 $j$번째 행진에 참여할 수 있는 대열의 최대 개수이다.