הרקע של בעיה זו זהה לבעיה 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$ יכולה להיות מחרוזת ריקה.