#P18435. Palindrome

Palindrome

Palindrome

作为一位魔术师和回文串爱好者,你希望通过魔法操作使字符串变成回文串。

一次魔法操作中,可以删除字符串 SS 的一个子串 S[a…b]S[a\ldots b],并将剩余的前后两部分连接起来,消耗 b−a+1b-a+1 单位魔法药剂。

给定一个由 nn 个小写英文字母组成的字符串 strstr,以及 mm 次魔法测试。每次测试给定 l,rl,r,令 S=str[l…r]S=str[l\ldots r]。你最多使用一次魔法操作,求使 SS 变为回文串所需的最少药剂,以及达到该最小消耗的方案数。方案按选择的删除区间区分。

特别地,若 SS 本来就是回文串,直接输出 0 0。

回文串从左向右与从右向左读取相同,例如 aba、ccpcc、qaq;ccpc、qhd 则不是回文串。S[a…b]S[a\ldots b] 指下标从 aa 到 bb 的子串,端点均包含,下标从 11 开始。

输入格式

第一行包含整数 nn 和字符串 strstr(1≤n=∣str∣≤5⋅1051\le n=|str|\le5\cdot10^5),字符串只包含小写英文字母。

第二行一个整数 mm(1≤m≤4⋅1051\le m\le4\cdot10^5),表示测试次数。

接下来 mm 行,每行两个整数 l,rl,r(1≤l≤r≤n1\le l\le r\le n),表示本次令 S=str[l…r]S=str[l\ldots r]。各次测试独立,不修改原字符串。

输出格式

对每次测试输出一行两个整数,依次为最小代价及达到最小代价的方案数,以一个空格分隔。方案数不取模。

原样例 1

5 abcca
3
1 5
3 4
3 5
1 1
0 0
1 1

原样例 2

5 babdb
2
1 4
3 4
1 1
1 2