P12271 [蓝桥杯 2024 国 Python B] 括号与字母

给定一个仅包含小写字母和括号的字符串 $S$，保证括号可以两两匹配。 给出 $Q$ 组询问，每组询问给出一个小写字母 $c_i$ 和一个数 $x_i$，询问 $S$ 中有多少对匹配的括号之间有不少于 $x_i$ 个 $c_i$。

输入的第一行包含一个字符串 $S$。 第二行包含一个整数 $Q$。 接下来 $Q$ 行，每行包含一个小写字母 $c_i$ 和一个整数 $x_i$ 表示一组询问，用一个空格分隔。

输出 $Q$ 行，每行包含一个整数，依次表示每个询问的答案。

### 评测用例规模与约定 - 对于 $40\%$ 的评测用例，$|S|, Q \leq 5000$； - 对于 $70\%$ 的评测用例，$|S| \leq 100000$； - 对于所有评测用例，$1 \leq |S| \leq 10^6$，$1 \leq Q \leq 100000$，$0 \leq x_i < 10^6$。其中 $|S|$ 表示 $S$ 的长度。