AT_abc405_g [ABC405G] Range Shuffle Query

長さ $ N $ の数列 $ A = (A_1, A_2, \dots, A_N) $ が与えられます。 $ Q $ 個のクエリが与えられるので処理してください。 クエリでは整数 $ L, R, X $ が与えられるので次の問題を解いてください。 > $ A $ の $ L $ 番目から $ R $ 番目までの要素を取り出してできる数列 $ B=(A_L, A_{L+1}, \dots, A_R) $ があります。 > あなたは以下の一連の操作をちょうど $ 1 $ 回行います。 > > - まず、 $ B $ から値が $ X $ 以上の要素を全て取り除く。 > - 次に、 $ B $ の要素を自由に並べ替える。 > > 操作後の $ B $ としてあり得るものは何通りありますか？答えを $ 998244353 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。ここで $ \mathrm{query}_i $ は $ i $ 番目のクエリを意味する。 > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリは以下の形式で与えられる。 > $ L $ $ R $ $ X $

$ Q $ 行出力せよ。 $ i $ 行目には $ i $ 番目のクエリの答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のクエリについて、操作後の $ B $ としてあり得るものは $ (1,1,2), (1,2,1), (2,1,1) $ の $ 3 $ 通りです。 $ 2 $ 番目のクエリについて、操作後の $ B $ としてあり得るものは空の列 $ () $ の $ 1 $ 通りです。 ### Constraints - $ 1 \leq N \leq 2.5 \times 10^5 $ - $ 1 \leq Q \leq 2.5 \times 10^5 $ - $ 1 \leq A_i \leq N $ - $ 1 \leq L \leq R \leq N $ - $ 1 \leq X \leq N $ - 入力される値は全て整数