Sau những năm tổ chức game show của mình và nhìn Bessie giành lấy giải nhất liên tục, nông dân John nhận ra đây không hề là ngẫu nhiên mà là to Bessie đã được cấy mã gen của kẻ chiến thắng. Để giải nhất không rơi vào tay Bessie thêm nữa, nông dân John đã bắt đầu công cuộc tìm kiếm gen của kẻ chiến thắng.

Nhiệm vụ của bạn là giúp anh nông dân John xác định mã gen ưng ý thông qua các bước sau: Từ xâu \(S\) có độ dài \(N\) (\(1 \leq N \leq 3000\)) là mã gen của Bessie, anh ấy chọn vài cặp số nguyên \((K,L)\) (\(1 \le L \le K \le N\)) mô tả mã gen "chiến thắng" có độ dài \(L\) và có thể thu được từ một xâu con độ dài \(K\) của xâu \(S\). Ta định nghĩa \(k-mer\) là tập hợp gồm các xâu con có độ dài \(K\) của xâu \(S\). Với mỗi phần tử của \(k-mer\), anh ấy viết ra tất cả xâu con có độ dài bằng \(L\) của nó, chọn ra xâu có thứ tự từ điển nhỏ nhất là một ứng cử viên cho mã gen "chiến thắng" (nếu tồn tại nhiều xâu con có thứ tự từ điển nhỏ nhất, chọn xâu có vị trí đầu tiên nhỏ nhất) và thêm vị trí xuất hiện lần đầu của nó trong xâu S \(p_i\) (các vị trí đánh số từ \(0\)) vào trong tập hợp \(P\).

Do quá gấp gáp, anh John vẫn chưa chọn được \(K\) và \(L\) nên anh ấy muốn bạn tìm ra số ứng cử viên cho mỗi cặp \(K\) và \(L\) anh ấy đưa ra.

Với mỗi \(v\) trong đoạn từ 1 đến \(N\), hãy giúp anh ấy tìm số cặp \(K, L\) thoả mãn \(|P| = v\).

Input:

• Dòng đầu tiên chứa \(N\), mô tả độ dài của chuỗi.
• Dòng thứ hai chứa chuỗi \(S\) (\(s_i \in A - Z\) \(\forall i \in [0, n - 1]\)).

Output:

• Đối với mỗi \(v\) từ \(1\) đến \(N\), in ra số lượng cặp \((K, L)\) với \(|P| = v\), mỗi số trên một dòng riêng biệt.

Scoring:

• Subtask 1: \(N \leq 100\)
• Subtask 2: \(N \leq 500\)
• Subtask 3: Không có ràng buộc gì thêm

8
AGTCAACG

11
10
5
4
2
2
1
1