บริบทของปัญหานี้เหมือนกับปัญหา F ส่วนที่แตกต่างจากปัญหา F จะถูกขีดเส้นใต้ไว้

กำหนดสตริง $S$ ความยาว $N$ ที่ประกอบด้วย ( และ ) เท่านั้น

จงตอบคำถาม $Q$ ข้อ ในคำถามข้อที่ $i$ คุณจะได้รับจำนวนเต็ม $L_i$ และ $R_i$ จงแก้ปัญหาต่อไปนี้:

ให้ $X$ เป็นสตริงย่อยของ $S$ ตั้งแต่อักขระตัวที่ $L_i$ ถึงอักขระตัวที่ $R_i$ พิจารณาการเลือกจำนวนเต็มบวก $k$ แล้วเลือกสตริงย่อย $Y$ ของสตริงที่ได้จากการนำ $X$ จำนวน $k$ ชุดมาต่อกัน ในที่นี้ $Y$ ต้องเป็นลำดับวงเล็บที่ถูกต้อง ทั้งนี้ $Y$ สามารถเป็นสตริงว่างได้

จงพิจารณาว่ามีความยาวสูงสุดที่เป็นไปได้สำหรับ $Y$ หรือไม่ และหากมี จงหาค่าสูงสุดนั้น

ลำดับวงเล็บที่ถูกต้อง

ลำดับวงเล็บที่ถูกต้องคือสตริงที่สามารถลดรูปให้เป็นสตริงว่างได้โดยการลบสตริงย่อยที่ติดกัน () ซ้ำ ๆ กันศูนย์ครั้งหรือมากกว่า

ข้อมูลนำเข้า

ข้อมูลนำเข้าจะถูกกำหนดให้จากข้อมูลนำเข้ามาตรฐานในรูปแบบต่อไปนี้:

N Q
S
L_1 R_1
L_2 R_2
...
L_Q R_Q

• $N, Q, L_i, R_i$ เป็นจำนวนเต็ม
• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $S$ เป็นสตริงความยาว $N$ ที่ประกอบด้วย ( และ ) เท่านั้น
• $1 \le L_i \le R_i \le N$

ข้อมูลส่งออก

พิมพ์ $Q$ บรรทัด สำหรับบรรทัดที่ $i$ ให้พิมพ์ความยาวสูงสุดที่เป็นไปได้ของ $Y$ สำหรับคำถามข้อที่ $i$ หากมีอยู่จริง และพิมพ์ -1 ในกรณีอื่น

ตัวอย่าง

ข้อมูลนำเข้าตัวอย่าง 1

4 3
()((
2 3
1 4
3 4

ข้อมูลส่งออกตัวอย่าง 1

-1
2
0

หมายเหตุ

• ในคำถามข้อแรก $X =$ )( สำหรับจำนวนเต็มบวก $k$ ใด ๆ หากเรานำ $X$ จำนวน $k$ ชุดมาต่อกันแล้วลบอักขระตัวแรกและตัวสุดท้ายออก เราจะได้ลำดับวงเล็บที่ถูกต้องที่มีความยาว $2k - 2$ ดังนั้นจึงไม่มีความยาวสูงสุดที่เป็นไปได้สำหรับ $Y$ คุณจึงควรพิมพ์ -1
• ในคำถามข้อที่สอง $X =$ ()(( สามารถพิสูจน์ได้ว่าความยาวสูงสุดที่เป็นไปได้ของ $Y$ คือ $2$ ดังนั้นให้พิมพ์ 2
• ในคำถามข้อที่สาม $X =$ (( ความยาวสูงสุดที่เป็นไปได้ของ $Y$ คือ $0$ ดังนั้นให้พิมพ์ 0 สังเกตว่า $Y$ สามารถเป็นสตริงว่างได้