Đoạn nén tốt nhất (Best Compressible Segment)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho xâu $S$ gồm $N$ chữ cái Latin in hoa. Các vị trí trong $S$ được đánh số từ $1$ đến $N$.

Với một xâu con liên tiếp $T$, chia $T$ thành các đoạn liên tiếp cực đại gồm các ký tự giống nhau. Số đoạn nhận được cũng chính là số cặp ký tự-số lượng khi nén $T$ theo quy tắc của bài Nén xâu.

Một xâu con được gọi là nén tốt nếu số đoạn của nó không vượt quá $K$.

Cần chọn một xâu con nén tốt có độ dài lớn nhất. Nếu có nhiều xâu con cùng có độ dài lớn nhất, chọn xâu có vị trí bắt đầu $L$ nhỏ nhất.

Hãy tìm độ dài lớn nhất và hai chỉ số $L,R$ của xâu con được chọn.

Input

• Dòng 1 chứa hai số nguyên $N$ và $K$.
• Dòng 2 chứa xâu $S$ có đúng $N$ ký tự, chỉ gồm A..Z.

Output

In ba số nguyên theo thứ tự: độ dài lớn nhất, $L$, $R$.

Subtask

• Subtask 1 (30 điểm): $N\le2000$.
• Subtask 2 (30 điểm): $K=1$.
• Subtask 3 (40 điểm): không có ràng buộc bổ sung.
• Trong mọi Subtask: $1\le K\le N\le10^6$.

Ví dụ

Input

13 2
AAABBCCCCDDAA

Output

6 4 9

Giải thích

Các đoạn liên tiếp của xâu là AAA, BB, CCCC, DD, AA.

Hai xâu con dài nhất có không quá $2$ đoạn là $S[4..9]=$ BBCCCC và $S[6..11]=$ CCCCDD. Cả hai đều có độ dài $6$.

Do hai phương án có cùng độ dài, ta chọn phương án có vị trí bắt đầu nhỏ hơn là $L=4$. Khi đó $R=9$, nên chương trình in 6 4 9.