题目描述

题目译自 XXII Olimpiada Informatyczna — II etap Trzy Wieże

Bajtazar 经营一家谜题商店，店里一款热门谜题是一个由 $n$ 个小写英文字母组成的字符串。玩家需将这个字符串巧妙切割成若干区间，每区间必须是回文字符串的字母重排，即通过重排字母可形成回文字符串。回文字符串是指从左到右和从右到左读都相同的字符串，例如 $\texttt{abba}$ 是回文字符串，其字母重排包括 $\texttt{aabb}$、$\texttt{abab}$、$\texttt{abba}$、$\texttt{baab}$、$\texttt{baba}$、$\texttt{bbaa}$；$\texttt{radar}$ 也是回文字符串，其字母重排如 $\texttt{drara}$、$\texttt{radra}$。

Bajtazar 希望切割后最短区间的长度尽可能大。你的任务是找出最短区间的最大可能长度，并提供一个实现此长度的切割方案。

输入格式

• 第一行包含一个整数 $n$ $(1 \leq n \leq 200000)$，表示字符串长度。
• 第二行包含一个由 $n$ 个小写英文字母（$\texttt{a}$, $\texttt{b}$, $\ldots$, $\texttt{z}$）组成的字符串，描述 Bajtazar 的谜题。

输出格式

• 第一行包含一个正整数 $d$，表示满足题目条件的切割中最短区间的最大长度。
• 第二行包含一个整数 $m$ $(1 \leq m \leq n)$，表示最短区间长度为 $d$ 的切割中的区间数。
• 接下来的 $m$ 行描述区间，第 $i$ 行包含两个整数 $\ell_i$, $r_i$ $(1 \leq \ell_i \leq r_i \leq n)$，表示包含从第 $\ell_i$ 到第 $r_i$ 位字母（含两端）的区间。需满足：对于 $1 \leq i < m$，$r_i + 1 = \ell_{i+1}$，且 $\ell_1 = 1$，$r_m = n$。

保证输入字符串可切割成回文字符串的字母重排。若存在多个最优切割方案，输出任意一种。

样例

输入

10
dababeaecc

输出

5
2
1 5
6 10

区间 $\texttt{dabab}$ 和 $\texttt{eaecc}$ 是回文字符串的字母重排，分别可重排为 $\texttt{badab}$ 和 $\texttt{ceaec}$（均为回文）。

附加样例

• $n=10$，输入字符串为 $\texttt{ababcbbbac}$，最短区间长度 $d=3$。
• $n=4000$，输入字符串本身是回文字符串的字母重排，最短区间长度 $d=4000$。
• $n=199996$，输入字符串由字母 $\texttt{a}$ 重复 $49999$ 次、$\texttt{b}$ 重复 $49999$ 次，依此类推至 $\texttt{d}$，最短区间长度 $d=49999$。

数据范围与提示

详细子任务附加限制及分值如下表所示。