편집 거리

두 문자열 $A$와 $B$의 편집 거리는, 문자열 $A$를 $B$로 바꾸기 위해 적용해야 하는 편집 작업의 최소 횟수로 정의된다. 가능한 편집 작업은 아래의 $3$가지가 있다:

1. 삽입: 현재 문자열의 임의의 위치에 글자를 하나 삽입한다.
2. 삭제: 현재 문자열의 임의의 위치의 글자를 하나 삭제한다.
3. 변경: 현재 문자열의 임의의 위치의 글자 하나를 다른 글자로 바꾼다.

두 문자열 aba와 abba의 경우, aba의 첫 글자와 두 번째 글자 사이에 b를 삽입하면 abba가 되므로 편집 거리는 $1$이다. 또, 두 문자열 aba와 acaa의 경우, aba의 문자 b를 c로 변경하고, 마지막 문자 a 뒤에 새로운 문자 a를 삽입하면 acaa가 되므로 편집 거리는 $2$가 된다.

임의의 문자열 $A$, $B$에 대해, $A$와 $B$의 편집 거리와 $B$와 $A$의 편집 거리는 같음에 유의하라.

주어진 문자열 $P$와 $T$에 대해서, $T$의 모든 연속이고 길이가 $1$ 이상인 부분문자열과 $P$의 편집 거리들 중, 그 값이 각각 $0, 1, \ldots, K$인 경우의 수를 구하는 프로그램을 작성하라.

입력 형식

첫 줄에 문자열 $T$의 길이 $N$, 문자열 $P$의 길이 $M$, 편집 거리의 제한을 나타내는 정수 $K$가 공백으로 구분되어 주어진다. ($1 \le N \le 100\,000;$ $1 \le M \le 1\,000;$ $0 \le K \le M$; 이 문제는 입력 제한이 일반적이지 않으므로 주의하라; 아래 채점 방식 부분에 추가적인 정보가 있다)

그다음 줄에 길이 $N$의 문자열 $T$가 주어진다.

그다음 줄에 길이 $M$의 문자열 $P$가 주어진다.

주어지는 문자열 $T$와 $P$는 모두 영어 알파벳 소문자로만 구성되어 있다.

출력 형식

첫 줄부터 $K + 1$개의 줄에 걸쳐 정답을 출력한다. $i + 1$번째 줄에는 $P$와의 편집 거리가 정확하게 $i$인 경우의 수를 출력한다.

예제

7 3 1
abbabaa
aba

1
10

예제 설명

편집 거리가 $0$인 경우는 $T$의 $4$번째 글자에서 시작하는 부분문자열 aba $1$개가 있다.

편집 거리가 $1$인 경우는 $T$의 $1$번째 글자에서 시작하는 부분문자열 ab, abb, abba가 있고, $2$번째 글자에서 시작하는 bba, $3$번째 글자에서 시작하는 ba, baba, $4$번째 글자에서 시작하는 ab, abaa, $5$번째 글자에서 시작하는 ba, 마지막으로, $6$번째 글자에서 시작하는 aa가 있어, 모두 $10$개이다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다. 입력 케이스 종류들 중 하나가 다른 모든 종류를 포함하는 경우가 없음에 주의하라.

해설