Problem Statement

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$.

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.

Input

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

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