C. Palindrome
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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.
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.

Examples
Input
5 abcca
3
1 5
3 4
3 5
Output
1 1
0 0
1 1
Input
5 babdb
2
1 4
3 4
Output
1 1
1 2