Hau có dãy ngoặc độ dài ~n~ và ~q~ truy vấn dạng ~(l, r)~. Với mỗi truy vấn, hãy giúp Hau tìm hai chỉ số ~L, R~ thỏa mãn:

• Dãy con tạo bởi đoạn ~[L, R]~ tạo thành dãy ngoặc đúng

• ~L \le l~ và ~r \le R~

• ~R - L~ nhỏ nhất có thể

Input

Dòng đầu tiên chứa ~2~ số nguyên dương ~n, q~ (~n, q \leq 2 \cdot 10^5~) — độ dài dãy ngoặc và số truy vấn của bài toán.

Dòng thứ hai chứa dãy ngoặc độ dài ~n~. ~q~ dòng tiếp theo, dòng thứ ~i~ gồm ~2~ số ~l, r~ (~1 \leq l \leq r \leq n~) thể hiện truy vấn thứ ~i~.

Output

Gồm ~q~ dòng. Dòng thứ ~i~ trả lời cho truy vấn thứ ~i~ chứa ~2~ chỉ số ~L, R~ biểu diễn dãy tìm được nếu tồn tại đáp án, ngược lại in ~-1~.

Scoring

• Subtask ~1~ (~50~ điểm): ~0 < n \le 1000~.

• Subtask ~2~ (~50~ điểm): không có ràng buộc gì thêm.

Sample Input 1

10 10
))(()()()(
3 7
4 4
6 9
5 7
1 6
1 7
3 8
5 8
7 9
7 10

Sample Output 1

-1
4 5
6 9
4 7
-1
-1
-1
4 9
6 9
-1