오랫동안 게임을 열고 Bessie가 계속 1등을 하는 것을 지켜본 Farmer John은 이것이 우연일 수 없다고 생각했다. 그는 Bessie의 DNA에 승리가 들어 있을 것이라 결론짓고 이 «승리» 유전자를 찾으려 한다.

그는 이 유전자의 후보를 찾는 과정을 고안했다. Bessie의 유전체는 길이가 $N$인 문자열 $S$이며 $1 \leq N \leq 3000$이다. $1 \leq L \leq K \leq N$을 만족하는 쌍 $(K,L)$을 고른다. 이는 길이가 $K$인 더 큰 부분 문자열 안에서 길이가 $L$인 승리 유전자 후보를 찾는다는 뜻이다. $S$의 길이 $K$인 모든 부분 문자열을 가져오며, 각각을 $k$-mer라고 부른다. 각 $k$-mer에 대해 길이 $L$인 모든 부분 문자열을 구하고 사전순으로 가장 작은 것을 승리 유전자 후보로 고른다. 동률이면 가장 왼쪽을 고른다. 이후 그 부분 문자열이 $S$에서 시작하는 위치 $p_i$를 $0$부터 세어 집합 $P$에 넣는다.

아직 $K$와 $L$을 고르지 않았으므로 모든 $(K,L)$쌍에 대해 후보의 수를 알고 싶다.

$1\dots N$의 각 $v$에 대해 $|P|=v$인 $(K,L)$쌍의 수를 구하도록 도와주자.

입력

$N$은 문자열의 길이이고 $S$는 주어지는 문자열이다. 소의 유전학은 인간보다 훨씬 발전했으므로 모든 문자는 대문자이며 $s_i \in A-Z$임이 보장된다.

출력

$1\dots N$의 각 $v$에 대해 $|P|=v$인 $(K,L)$쌍의 수를 각각 별도의 줄에 출력한다.

예제

입력 1

8
AGTCAACG

출력 1

11
10
5
4
2
2
1
1

참고

이 테스트 케이스에서 출력의 세 번째 줄은 5이다. 승리 유전자 후보 세 개를 만드는 $K$와 $L$의 쌍이 정확히 5개 있기 때문이다. 후보는 다음과 같다($p_i$는 $0$부터 시작한다).

(4,2) -> P = [0,3,4]
(5,3) -> P = [0,3,4]
(6,4) -> P = [0,3,4]
(6,5) -> P = [0,1,3]
(6,6) -> P = [0,1,2]

(4,2)가 이 결과를 만드는 과정을 보려면 모든 $4$-mer를 가져온다.

AGTC
GTCA
TCAA
CAAC
AACG

각 $4$-mer에서 길이가 2인 사전순 최소 부분 문자열을 찾는다.

AGTC -> AG
GTCA -> CA
TCAA -> AA
CAAC -> AA
AACG -> AA

원래 문자열에서 이 부분 문자열들의 위치를 집합 $P$에 넣으면 $P = [0,3,4]$가 된다.

한편 $(4,1)$쌍에서는 승리 유전자 후보가 총 $2$개뿐이다. 모든 $4$-mer에서 길이가 $1$인 사전순 최소 부분 문자열을 찾으면 다음과 같다. 서로 다른 A를 구분하기 위해 A, A', A*를 사용한다.

AGTC -> A
GTCA' -> A'
TCA'A* -> A'
CA'A*C -> A'
A'A*CG -> A'

마지막 세 경우에는 A'와 A* 모두 사전순 최소이지만 가장 왼쪽 부분 문자열이 우선하므로, 모든 경우에 A'만 후보로 센다. 따라서 $P = [0,4]$이다.

서브태스크

• 입력 2-4: $N \leq 100$
• 입력 5-7: $N \leq 500$
• 입력 8-16: 추가 제한 없음.

문제 출제자: Suhas Nagar