H. Gaslighting
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Waymo and Brian are discussing the winter 2023 seasonsals a string $$$s$$$ and will have $$$q$$$ different conversations. In some conversation, Brian will start talking about $$$s_{l \dots r}$$$, but Waymo will attempt to gaslight him into thinking he was talking about $$$s_{l' \dots r'}$$$ where $$$s_{l \dots r}$$$ and $$$s_{l' \dots r'}$$$ differ by exactly 1 element. Waymo loves to gaslight but he doesn't know the string well enough, so he asks you to construct an $$$l'$$$ and $$$r'$$$ for each $$$l \ r$$$ Brian talks about. Note that $$$r' - l' + 1 = r - l + 1$$$.

Note that two strings $$$a$$$ and $$$b$$$ of the same length differ by exactly $$$1$$$ element if and only if there exists some index $$$i$$$ such that $$$a_i \neq b_i$$$ and for all $$$j \neq i$$$, $$$a_j = b_j$$$.

Input

The first line of input contains two integers $$$n$$$ and $$$q$$$ denoting the length of the string and the number of conversations $$$(1 \leq n \leq 7000, 1 \leq q \leq 10^6)$$$.

The second line of input contains the string $$$s$$$ of length $$$n$$$ and consists only of lowercase English letters.

The following $$$q$$$ lines each contain two integers $$$l$$$ and $$$r$$$, denoting the substring Waymo and Brian are talking about $$$(1 \leq l \leq r \leq n)$$$.

—

Tests in subtasks are numbered from $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$.

Tests $$$1 - 3$$$ satisfy $$$n, q \leq 100$$$.

Tests $$$4 - 7$$$ satisfy $$$n \leq 2000$$$.

Tests $$$8 - 10$$$ satisfy $$$q = n, l = 1$$$.

The remaining tests do not satisfy any additional constraints.

Output

For each of the $$$q$$$ conversations, output a line containing two integers $$$l' \ r'$$$ denoting some valid answer as defined in the statement or $$$0$$$ $$$0$$$ if no such $$$l'$$$ and $$$r'$$$ exist. In the case that multiple valid $$$l'$$$ and $$$r'$$$ exist, output any of them.

Example
Input
7 6
abaacba
1 2
1 3
1 4
2 5
2 3
7 7
Output
4 5
5 7
0 0
0 0
3 4
5 5
Note

$$$s_{1 \dots 2} = ab$$$ and $$$s_{4 \dots 5} = ac$$$ differ by exactly $$$1$$$ element.

$$$s_{1 \dots 3} = aba$$$ and $$$s_{5 \dots 7} = cba$$$ differ by exactly $$$1$$$ element.

There exists no valid $$$l'$$$ and $$$r'$$$ that denote a substring that differs from $$$s_{1 \dots 4} = abaa$$$ by exactly $$$1$$$ element.

—

Problem Idea: 3366

Problem Preparation: 3366

Occurrences: Novice 12, Advanced 8