1226 : 回文字符串

Description

作为一个魔术师和回文字符串爱好者，你想通过魔法操作使得字符串 \(S\) 变成回文字符串。

在一次魔法操作中，你可以花费 \(r - l + 1\) 单位的魔法药剂作为代价，删除字符串 \(S\) 的一个子串 \(S[l...r]\) 并连接剩余部分得到一个新的字符串。

给定一个由 \(n\) 个小写字母组成的字符串 \(str\)，有 \(m\) 个魔法测试。

对于每一个测试，给定两个整数 \(l,r\)，设 \(S\) 表示为 \(str[l...r]\)。

你应该使用最多一次魔法操作，使得 \(S\) 变成回文字符串，求最小魔法药剂代价，以及最小化代价的方案数。

特别地，如果 \(S\) 已经是一个回文字符串，只需输出 ‘0 0’。

注意：

• 回文字符串是指从左到右和从右到左读起来都相同的字符串。例如，‘aba’, ‘ccpcc’, ‘qaq’ 都是回文字符串, 而 ‘ccpc’, ‘qhd’ 不是回文字符串。

• \(S[l...r]\) 表示 \(S\) 从第 \(l\) 个字符开始到第 \(r\) 个字符结束的子串。

Input

第一行包含一个整数 \(n\) 和一个仅由小写字母组成的字符串 \(str\ (1\le n=|str|\le 5 \times 10^5)\)。

第二行包含一个整数 \(m\ (1\le m \le 4 \times 10^5)\)，表示魔法测试的数量。

接下来 \(m\) 行的每一行包含两个整数 \(l,r\)（\(1\le l\le r\le n\)），表示令 \(S=str[l...r]\) 作为一次魔法测试。

Output

对于每个测试，输出一行，包含两个整数 — 最小代价和实现该代价的方案数，用一个空格分隔。

Sample

5 abcca
3
1 5
3 4
3 5
##CASE##
5 babdb
2
1 4
3 4

1 1
0 0
1 1
##CASE##
1 1
1 2

Hint

Source