Gen Chiến Thắng

Farmer John phân tích bộ gen của Bessie -- một chuỗi $S$ độ dài $N$ ($1\le N\le 3000$) gồm các chữ cái in hoa.

Với mỗi cặp $(K,L)$ thỏa $1\le L\le K\le N$, FJ thực hiện:

1. Lấy tất cả các chuỗi con độ dài $K$ (k-mer) của $S$: $S[0..K-1],S[1..K],\dots ,S[N-K..N-1]$
2. Trong mỗi k-mer, tìm chuỗi con độ dài $L$ nhỏ nhất theo thứ tự từ điển (nếu hòa, lấy vị trí trái nhất)
3. Ghi lại vị trí bắt đầu (0-indexed) trong $S$ của chuỗi con đó vào tập $P$

Với mỗi $v$ từ 1 đến $N$, đếm số cặp $(K,L)$ mà $|P|=v$.

Dữ liệu vào

• Dòng 1: Số nguyên $N$
• Dòng 2: Chuỗi $S$ gồm $N$ chữ cái in hoa

Dữ liệu ra

• $N$ dòng, dòng thứ $v$ là số cặp $(K,L)$ sao cho $|P|=v$.

Ràng buộc

• $1\le N\le 3000$
• Giới hạn bộ nhớ: 512MB
• Test 2-4: $N\le 100$
• Test 5-7: $N\le 500$

Ví dụ