إعداد هذه المسألة مطابق للمسألة F. الاختلافات عن المسألة F تحتها خط.

تُعطى سلسلة نصية $S$ طولها $N$ تتكون فقط من ( و ).

أجب عن $Q$ استعلامات. في الاستعلام $i$، يُعطى العددان الصحيحان $L_i$ و $R_i$. حل المسألة التالية:

ليكن $X$ هو السلسلة الفرعية من $S$ من المحرف $L_i$ إلى المحرف $R_i$. لنتأمل اختيار عدد صحيح موجب $k$ ثم اختيار سلسلة فرعية $Y$ من السلسلة الناتجة عن دمج $k$ نسخ من $X$. هنا، يجب أن تكون $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$، إذا دمجنا $k$ نسخ من $X$ وحذفنا المحرفين الأول والأخير، نحصل على متتالية أقواس منتظمة طولها $2k - 2$. لذلك لا يوجد طول أقصى ممكن للسلسلة $Y$، لذا يجب طباعة -1.
• في الاستعلام الثاني، $X =$ ()((. يمكن إثبات أن الطول الأقصى الممكن للسلسلة $Y$ هو $2$. لذلك، اطبع 2.
• في الاستعلام الثالث، $X =$ ((. الطول الأقصى الممكن للسلسلة $Y$ هو $0$، لذا اطبع 0. لاحظ أن $Y$ يمكن أن تكون سلسلة فارغة.