Sau nhiều năm tổ chức trò chơi và thấy Bessie liên tục đứng nhất, Farmer John nhận ra đây không thể là ngẫu nhiên. Ông kết luận rằng chiến thắng hẳn được mã hóa trong DNA của Bessie và bắt đầu tìm gen «chiến thắng» này.

Ông thiết kế quy trình tìm các ứng viên cho gen đó. Bộ gen của Bessie là xâu $S$ dài $N$, với $1 \leq N \leq 3000$. Ông chọn cặp $(K,L)$ có $1 \leq L \leq K \leq N$, nghĩa là gen ứng viên dài $L$ được tìm trong một xâu con lớn hơn dài $K$. Ông lấy mọi xâu con dài $K$ của $S$, mỗi xâu gọi là một $k$-mer. Với mỗi $k$-mer, ông xét mọi xâu con dài $L$, chọn xâu nhỏ nhất theo thứ tự từ điển làm gen ứng viên (chọn xâu bên trái nhất nếu hòa), rồi thêm vị trí bắt đầu $p_i$ của xâu đó trong $S$, đánh số từ $0$, vào tập $P$.

Vì chưa chọn $K$ và $L$, ông muốn biết số ứng viên cho mỗi cặp $(K,L)$.

Với mỗi $v$ trong $1\dots N$, hãy giúp ông xác định số cặp $(K,L)$ có $|P|=v$.

Dữ liệu vào

$N$ là độ dài xâu và $S$ là xâu đã cho. Bảo đảm mọi ký tự đều viết hoa, $s_i \in A-Z$, vì di truyền học của bò tiến bộ hơn con người rất nhiều.

Dữ liệu ra

Với mỗi $v$ trong $1\dots N$, in số cặp $(K,L)$ có $|P|=v$, mỗi số trên một dòng riêng.

Ví dụ

Dữ liệu vào 1

8
AGTCAACG

Dữ liệu ra 1

11
10
5
4
2
2
1
1

Ghi chú

Trong test này, dòng ra thứ ba là 5 vì có đúng 5 cặp $K$ và $L$ tạo ra ba gen «chiến thắng» ứng viên. Các ứng viên như sau ($p_i$ đánh số từ $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]

Để thấy (4,2) tạo ra kết quả này, lấy tất cả $4$-mer:

AGTC
GTCA
TCAA
CAAC
AACG

Với mỗi $4$-mer, tìm xâu con dài 2 nhỏ nhất theo thứ tự từ điển:

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

Thêm vị trí của các xâu con này trong xâu ban đầu vào tập $P$, thu được $P = [0,3,4]$.

Mặt khác, cặp $(4,1)$ chỉ tạo ra tổng cộng $2$ gen «chiến thắng» ứng viên. Nếu lấy tất cả $4$-mer và tìm xâu con dài $1$ nhỏ nhất theo thứ tự từ điển (dùng A, A' và A* để phân biệt các A khác nhau), ta được:

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

Dù A' và A* đều nhỏ nhất theo thứ tự từ điển trong 3 trường hợp cuối, xâu con bên trái nhất được ưu tiên, nên chỉ A' được tính là ứng viên trong tất cả các trường hợp này. Do đó $P = [0,4]$.

Nhiệm vụ con

• Các đầu vào 2-4: $N \leq 100$
• Các đầu vào 5-7: $N \leq 500$
• Các đầu vào 8-16: không có ràng buộc bổ sung.

Tác giả bài toán: Suhas Nagar