Palindrome
Description
As a magician and a palindrome lover, you want to make strings become palindromes through magic operation.
In one magic operation, you can erase $S[l...r]$ of a string $S$ and concatenate the rest of $S$ to get the target string, which costs $r - l + 1$ units of magic potion.
You are given a string $str$, consisting of $n$ lowercase Latin letters, and there are $m$ magic tests.
For each one, you are given two integers $l,r$, denoting $S$ as $str[l...r]$.
You should use at most one magic operation, report the minimal cost of magic potion to make $S$ become palindrome, and the number of ways to achieve the target with the previous minimized cost.
Specifically, if $S$ is already a palindrome, just output '$\text {0 0}$'.
NOTE:
- A palindrome is a string that reads the same from left to right as from right to left. For example, 'aba', 'ccpcc', 'qaq' are palindromes, while 'ccpc' and 'qhd' are not.
- $S[l...r]$ means the substring of $S$ which starts from the $l$-th character and ends with the $r$-th character.
The first line contains an integer $n$ and a string $str\ (1\le n=|str|\le 5 \times 10^5)$ of lowercase English letters.
The second line contains an integer $m\ (1\le m \le 4 \times 10^5)$ representing the number of magic tests.
The following $m$ lines describe the tests.
In each line, there are two integers $l,r$ ($1\le l\le r\le n$), you should take the $str[l...r]$ as the problem.
For each tests, output one line consisting two integers - the minimal cost and the number of ways to achieve it, separated by one space.
Input
The first line contains an integer $n$ and a string $str\ (1\le n=|str|\le 5 \times 10^5)$ of lowercase English letters.
The second line contains an integer $m\ (1\le m \le 4 \times 10^5)$ representing the number of magic tests.
The following $m$ lines describe the tests.
In each line, there are two integers $l,r$ ($1\le l\le r\le n$), you should take the $str[l...r]$ as the problem.
Output
For each tests, output one line consisting two integers - the minimal cost and the number of ways to achieve it, separated by one space.
5 abcca
3
1 5
3 4
3 5
5 babdb
2
1 4
3 4
1 1
0 0
1 1
1 1
1 2