AT_utpc2025_g Greatest Bracket Sequence

本题的设定与 [F 问题](https://atcoder.jp/contests/utpc2025/tasks/utpc2025_f)相同。 给定一个仅由 `(` 和 `)` 组成、长度为 $N$ 的字符串 $S$。 请你回答 $Q$ 个询问。对于第 $i$ 个询问，会给出两个整数 $L_i, R_i$，请解决以下问题。 > 考虑 $S$ 的第 $L_i$ 个字符到第 $R_i$ 个字符所形成的子字符串 $X$。 > > 选择一个正整数 $k$，再从 $X$ 重复连接 $k$ 次得到的字符串中，选择一个子串 $Y$。这里要求 $Y$ 必须是一个「正确括号序列」。$Y$ 可以为空串。 > > 判定 $Y$ 的长度的最大可能值是否存在，如果存在请输出最大值。 「正确括号序列」指的是，可以通过若干次（可为 $0$ 次）删除子串 `()` 变成空字符串的字符串。

输入通过标准输入给出，格式如下： > $N\ Q\ S\ L_1\ R_1\ L_2\ R_2\ \vdots\ L_Q\ R_Q$

请输出 $Q$ 行。第 $i$ 行对于第 $i$ 个询问，如果 $Y$ 的最大可能长度存在，则输出该最大值，否则输出 `-1`。

### 样例解释 1 对于第 $1$ 个询问，$X = )($。对于任意正整数 $k$，从 $X$ 重复 $k$ 次得到的字符串中，去掉开头和结尾的字符所得到的长度为 $2k-2$ 的子串都是正确括号序列，因此 $Y$ 的最大长度不存在上限。 对于第 $2$ 个询问，$X = ()(( $。可以证明 $Y$ 的长度最大可能为 $2$。 对于第 $3$ 个询问，$X = ( ($。最大可能长度为 $0$。注意 $Y$ 可以为空字符串。 ### 数据范围 - $N, Q, L_i, R_i$ 均为整数 - $1 \leq N \leq 2 \times 10^5$ - $1 \leq Q \leq 2 \times 10^5$ - $S$ 为仅由 `(` 和 `)` 组成的长度为 $N$ 的字符串 - $1 \leq L_i \leq R_i \leq N$ 由 ChatGPT 5 翻译