AT_abc405_g [ABC405G] Range Shuffle Query

You are given a length- $ N $ sequence $ A = (A_1, A_2, \dots, A_N) $ . Process $ Q $ queries. Each query gives you integers $ L $ , $ R $ , $ X $ and asks you to solve the following. > Let $ B = (A_L, A_{L+1}, \dots, A_R) $ be the sequence formed by the $ L $ -th through $ R $ -th elements of $ A $ . > Perform the following procedure exactly once: > > - First, remove from $ B $ every element whose value is at least $ X $ . > - Then, rearrange the remaining elements of $ B $ arbitrarily. > > How many distinct sequences $ B $ can result? Find the count modulo $ 998244353 $ .

The input is given from Standard Input in the following format, where $ \mathrm{query}_i $ denotes the $ i $ ‑th query: > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ Each query is given in the following format: > $ L $ $ R $ $ X $

Output $ Q $ lines. The $ i $ -th line should contain the answer to the $ i $ ‑th query.

### Sample Explanation 1 For the first query, there are three possible resulting sequences $ B $ : $ (1,1,2) $ , $ (1,2,1) $ , and $ (2,1,1) $ . For the second query, there is one possible resulting sequence $ B $ : the empty sequence $ () $ . ### Constraints - $ 1 \le N \le 2.5 \times 10^5 $ - $ 1 \le Q \le 2.5 \times 10^5 $ - $ 1 \le A_i \le N $ - $ 1 \le L \le R \le N $ - $ 1 \le X \le N $ - All input values are integers.