题目描述

给定一个仅包含小写字母和括号的字符串 $S$，保证括号可以两两匹配。

给出 $Q$ 组询问，每组询问给出一个小写字母 $c_i$ 和一个数 $x_i$，询问 $S$ 中有多少对匹配的括号之间有不少于 $x_i$ 个 $c_i$。

输入格式

输入的第一行包含一个字符串 $S$。

第二行包含一个整数 $Q$。

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

输出格式

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

((a)()((b)((c))))
3
a 2
b 1
c 1

0
3
4

提示

评测用例规模与约定

• 对于 $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$ 的长度。