题目描述

题目译自 XXXII Olimpiada Informatyczna – II etap Podział na anagramy

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

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

附加样例

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

数据范围与提示

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