Bajtazar runs a puzzle shop. One of the puzzles involves a string consisting of $n$ lowercase English letters. The challenge in this puzzle is to cut the string into pieces such that each piece is an anagram of a palindrome.

A string $s$ is an anagram of a string $t$ if we can rearrange the letters in $s$ to obtain $t$. A string is a palindrome if it reads the same from left to right as it does from right to left. For example, the string abba is a palindrome, and its anagrams include aabb, abab, abba, baab, baba, and bbaa. The string radar is also a palindrome, and its anagrams include, for example, drara and radra.

Bajtazar would like the shortest of the pieces obtained from the cut to be as long as possible. Your task is to determine the maximum possible length of this shortest piece, and also to find a cut where the shortest piece has this length.

Input

The first line of the input contains an integer $n$ ($1 \le n \le 200\,000$). The second line contains a string consisting of $n$ lowercase English letters (a, b, ..., z) describing Bajtazar's puzzle.

Output

The first line of the output should contain a single positive integer $d$, representing the maximum length of the shortest piece in a cut of the given string that satisfies the condition from the problem statement.

The next line should contain an integer $m$ ($1 \le m \le n$) representing the number of pieces in a cut where the shortest piece has this length. The following $m$ lines should contain descriptions of the consecutive pieces. The $i$-th of these lines should contain a pair of integers $\ell_i, r_i$ ($1 \le \ell_i \le r_i \le n$) separated by a single space, representing a piece containing the letters from the $\ell_i$-th to the $r_i$-th inclusive. The printed values must satisfy $r_i + 1 = \ell_{i+1}$ for $1 \le i < m$, as well as $\ell_1 = 1$ and $r_m = n$.

You may assume that the input string can be cut into anagrams of palindromes. If there is more than one partition where the length of the shortest piece is maximal, you should output any one such partition.

Examples

Input 1

10
dababeaecc

Output 1

5
2
1 5
6 10

Note

The pieces dabab and eaecc are anagrams of palindromes, badab and ceaec respectively.

Scoring

If your program correctly outputs only the first line of the output, i.e., the maximum length of the shortest piece in a cut of the string that satisfies the condition from the problem statement, it will receive 50% of the points for the given test. In such a case, there are no restrictions on the content of the remaining lines of the output (other than not exceeding the output limit).