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 $ を $ x+1 $ で置き換える。 - $ S $ の $ x+1 $ 文字目から $ y $ 文字目までを取り出した文字列が正規括弧列であるような $ y $ を好きに選び、 $ x $ を $ y $ で置き換える。この操作は $ 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 $ 番目のクエリに対する答えを出力せよ。

### Sample Explanation 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) $ ### Constraints - $ 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 $ は整数