B. Balanced Splitting
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The author of this task dislikes long stories in task statements, so he is making the task statement of this task as concise as possible!

Given a 01-string $$$S$$$ of length $$$N$$$, you have to process $$$Q$$$ queries on it.

For the $$$i^{th}$$$ query, you are given $$$L_i$$$ and $$$R_i$$$, and you have to find any pair $$$(a, b)$$$ such that $$$L_i \le a \le b \le R_i$$$ and $$$S[a .. b]$$$ contains exactly half of the number of 0s and half of the number of 1s in $$$S[L_i .. R_i]$$$. If no such pair exist, output -1.

Input

The input consists of $$$Q+2$$$ lines.

The first line of the input consists of 2 integers $$$N$$$, $$$Q$$$ ($$$1 \le N, Q \le 10^5$$$), the length of the 01-string, and the number of queries respectively.

The second line of the input consists of the 01-string $$$S$$$ of length $$$N$$$.

The $$$i^{th}$$$ of the remaining $$$Q$$$ lines each consist of two integers $$$L_i, R_i$$$ ($$$1 \le L_i \le R_i \le N$$$), the range of the query.

Output

Output $$$Q$$$ lines, one for each query.

If a pair $$$(a, b)$$$ exists, output $$$a$$$ and $$$b$$$ on the same line, separated by a space. If there are multiple solutions, output any.

If no such pair exists, output -1 on the line.

Example
Input
9 5
000101101
2 3
3 6
2 9
1 4
1 6
Output
3 3
4 5
5 8
-1
3 5
Note

$$$S[x..y]$$$ denotes the substring of $$$S$$$ from the $$$x$$$-th position to the $$$y$$$-th position inclusively. That is, $$$S[x..y] = S_xS_{x+1}S_{x+2}\dots S_{y-1}S_{y}$$$.