找规律害人害己。
设 \(f(k,x)\) 表示操作 \(k\) 次之后第 \(x\) 个左括号的位置，知道 \(f(k,x)\) 之后可以简单二分出答案。
首先考虑 \(f\) 的递推式，左括号的位置改变有两种情况。((->(X 和 ()->)(，对应过来就是 \(f(k+1,x)=\min(f(k,x)+1,f(k,x+1)-1)\)，考虑用 \(f(0,y)\) 表示出 \(f(k,x)\)，有：
\[f(k,x)=\min_{x\le y\le x+k} f(0,y)+k-2(y-x)
\]
设 \(m\) 为左括号个数，如果 \(k\) 较小，则直接处理出 \(f(0,[0,2m))\)，每次 rmq 找最小值即可。
考虑 \(k\) 比较大的情况，跨掉一个串之后的 \(f\) 变化是很有规律的。容易发现 \(f(0,j+m)=f(0,j)+n\)，而贡献到 \(f(k,x)\) 时他们的贡献会相差 \(2m\)，所以我们对于 \(n-2m\) 分类讨论，如果 \(n-2m>0\)，则尽量选靠左的 \(m\) 个，否则尽量选靠右的 \(m\) 个，依然可以通过简单 rmq 解决。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
inline int read() {
register int s = 0, f = 1; register char ch = getchar();
while (!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while (isdigit(ch)) s = (s * 10) + (ch & 15), ch = getchar();
return s * f;
}
inline void otp(int x) {
(x >= 10) ? otp(x / 10), putchar((x % 10) ^ 48) : putchar(x ^ 48);
}
int n, q, mn[N << 1][20], top = 0;
char ch[N];
inline int f(int k, int x) {
int l, r;
if (2 * top <= n) l = x, r = min(l + k, l + top - 1);
else r = x + k, l = max(x, r - top + 1);
int p = (l % top + top) % top + 1;
int t = __lg(r - l + 1), B = (l >= 0) ? l / top : (l + 1) / top - 1;
return min(mn[p][t], mn[p + (r - l + 1) - (1 << t)][t]) + (n - 2 * top) * B + k + 2 * x;
}
inline int query(int k, int x) {
int l = -1e9, r = 1e9, mid, res;
while (l <= r) {
mid = l + r >> 1;
if (f(k, mid) <= x) l = (res = mid) + 1;
else r = mid - 1;
} return res;
}
int main() {
int T; T = read();
while (T--) {
scanf("%s", ch); q = read();
n = strlen(ch);
top = 0;
for (int i = 0; i < n; ++i)
if (ch[i] == '(') mn[++top][0] = i;
for (int i = top + 1; i <= top * 2; ++i) mn[i][0] = mn[i - top][0] + n;
for (int i = 1; i <= top * 2; ++i) mn[i][0] -= 2 * (i - 1);
for (int i = 1; i < 20; ++i)
for (int j = 1; j + (1 << i) <= top * 2; ++j)
mn[j][i] = min(mn[j][i - 1], mn[j + (1 << i - 1)][i - 1]);
while (q--) {
int k, l, r; k = read(); l = read(); r = read();
otp(top ? query(k, r) - query(k, l - 1) : 0);
putchar('\n');
}
} return 0;
}