Best Compressible Segment

Version: Phuoc Hung OJ Extended

Problem Statement

You are given a string $S$ of $N$ uppercase Latin letters. Positions are numbered from $1$ to $N$.

For any contiguous substring $T$, split it into maximal consecutive runs of equal characters. The number of runs is also the number of letter-count pairs in its run-length encoding.

A substring is called good for compression if it contains at most $K$ runs.

Choose a good substring with maximum length. If several substrings have the same maximum length, choose the one with the smallest starting position $L$.

Find the maximum length and the endpoints $L,R$ of the chosen substring.

Input

• Line 1 contains integers $N$ and $K$.
• Line 2 contains $S$ with exactly $N$ characters, all from A..Z.

Output

Print three integers: the maximum length, $L$, and $R$, in this order.

Subtasks

• Subtask 1 (30 points): $N\le2000$.
• Subtask 2 (30 points): $K=1$.
• Subtask 3 (40 points): no additional restriction.
• In every subtask: $1\le K\le N\le10^6$.

Examples

Input

13 2
AAABBCCCCDDAA

Output

6 4 9

Explanation

The runs are AAA, BB, CCCC, DD, and AA.

Two longest substrings with at most $2$ runs are $S[4..9]=$ BBCCCC and $S[6..11]=$ CCCCDD. Both have length $6$. The first one starts earlier, so $L=4$ and $R=9$. Therefore the output is 6 4 9.