Bajtazar 经营着一家益智游戏商店。其中一个游戏包含一个由 $n$ 个小写英文字母组成的字符串。这个游戏的挑战在于将字符串切割成若干片段，使得每个片段都是一个回文串的重排。

如果字符串 $s$ 可以通过重新排列字母得到字符串 $t$，则称 $s$ 是 $t$ 的重排（anagram）。 如果一个字符串从左往右读和从右往左读完全相同，则称其为回文串。 例如，字符串 abba 是一个回文串，它的重排包括 aabb、abab、abba、baab、baba 和 bbaa。字符串 radar 也是一个回文串，它的重排包括 drara 和 radra 等。

Bajtazar 希望切割后得到的片段中，最短的那个片段尽可能长。你的任务是确定这个最短片段的最大可能长度，并给出一个达到该长度的切割方案。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 200\,000$)。第二行包含一个由 $n$ 个小写英文字母（a, b, ..., z）组成的字符串，描述了 Bajtazar 的谜题。

输出格式

第一行输出一个正整数 $d$，表示满足题目条件的情况下，最短片段的最大长度。 第二行输出一个整数 $m$ ($1 \le m \le n$)，表示在该长度下的切割方案中片段的数量。接下来的 $m$ 行，每行包含一对整数 $\ell_i, r_i$ ($1 \le \ell_i \le r_i \le n$)，用空格分隔，表示包含从第 $\ell_i$ 个字符到第 $r_i$ 个字符（包含边界）的片段。输出的数值应满足 $r_i + 1 = \ell_{i+1}$（对于 $1 \le i < m$），且 $\ell_1 = 1$ 以及 $r_m = n$。

你可以假设输入的字符串一定可以被切割成回文串的重排。如果存在多种切割方案使得最短片段的长度最大，输出其中任意一种即可。

样例

输入格式 1

10
dababeaecc

输出格式 1

5
2
1 5
6 10

说明

片段 dabab 和 eaecc 分别是回文串 badab 和 ceaec 的重排。

评分

测试集分为以下子任务。每个子任务的测试用例由一个或多个独立的测试组组成。

如果你的程序仅正确输出了第一行（即满足题目条件的最短片段的最大长度），将获得该测试点 50% 的分数。在这种情况下，对输出的其余行内容没有限制（只要不超过输出限制即可）。