AT_pakencamp_2024_day3_1_g Bracket Sequence Queries

给定一个仅由 `(` 和 `)` 构成的字符串 $S$。 另外，还给定 $Q$ 个查询。对于第 $i$ 个查询，给定一组正整数 $(s_i,t_i)$，请解答下列问题： - 有一个被赋值为 $s_i$ 的变量 $x$，以及一个长度为 $0$ 的序列 $h$。你可以进行以下操作次数任意（包括 $0$ 次）： - 向 $h$ 中添加 $x$，之后进行以下两种操作之一： - 用 $x+1$ 替换 $x$。 - 可以任选一个 $y$，使得 $S$ 的第 $x+1$ 到第 $y$ 个字符组成的字符串为一个合法括号序列，然后用 $y$ 替换 $x$。该操作仅当 $x\leq |S|-1$ 时才能进行。 - 操作结束时，若 $x=t_i$，问最终可能得到的 $h$ 的种类数，对 $998244353$ 取模后输出。 什么是合法括号序列？合法括号序列是指通过重复 $0$ 次或多次删除子串 `()`，最终可以变为空串的字符串。

输入通过标准输入按照以下格式给出： > $S$ $Q$ $s_1$ $t_1$ $s_2$ $t_2$ $\vdots$ $s_Q$ $t_Q$

输出 $Q$ 行。 第 $i$ 行输出第 $i$ 个查询的答案。

### 样例解释 1 关于第 1 个查询，可能作为最终 $h$ 的有以下 6 种情况： - $(0)$ - $(0,1,5)$ - $(0,1,3,5)$ - $(0,1,3,4,5)$ - $(0,1,2,3,5)$ - $(0,1,2,3,4,5)$ ### 数据范围 - $S$ 是由 `(` 和 `)` 构成的、长度 $1$ 到 $200000$ 的字符串。 - $1\leq Q\leq 200000$ - $0\leq s_i\lt t_i\leq |S|$ $(1\leq i\leq Q)$ - $Q,s_i,t_i$ 均为整数。 由 ChatGPT 5 翻译