J. The Power of the Sun
time limit per test
2 s
memory limit per test
512 megabytes
input
standard input
output
standard output

Dr. Otto Octavius is a brilliant nuclear physicist working on his life's work: a sustainable fusion power source. He claims to have "the power of the sun, in the palm of his hand" with his new Infinite Factorial Reactor.

The reactor consists of $$$n$$$ fusion cores lined up in a row, indexed from $$$1$$$ to $$$n$$$. Initially, the $$$i$$$-th core holds an energy level of $$$a_i$$$.

Octavius uses his mechanical arms to conduct $$$q$$$ operations. In each operation, he interacts with a specific range of cores $$$[l, r]$$$. The operations are of two types:

  1. Fusion Ignition: Octavius triggers a reaction in the cores from index $$$l$$$ to $$$r$$$. The energy level of every core in this range transforms into its own factorial. Formally, for each $$$i$$$ such that $$$l \le i \le r$$$, the energy level $$$a_i$$$ becomes $$$a_i!$$$ (where $$$0! = 1$$$ and $$$x! = 1 \times 2 \times \dots \times x$$$ for $$$x \ge 1$$$).

  2. Stability Check: Octavius measures the total energy output of the cores from index $$$l$$$ to $$$r$$$. However, the inhibitor chip has a limit and can only display the result modulo $$$998244353$$$. Formally, the reading is $$$\left(\sum_{i=l}^{r} a_i\right) \pmod{998244353}$$$.

Help Dr. Octavius simulate the reactor's behavior and determine the energy readings for all type 2 operations.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 5 \cdot 10^5$$$) — the number of fusion cores and the number of operations.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 5 \cdot 10^5$$$) — the initial energy levels of the cores.

Each of the next $$$q$$$ lines contains three integers $$$type$$$, $$$l$$$, $$$r$$$ ($$$type \in \{1, 2\}$$$, $$$1 \le l \le r \le n$$$) — describing an operation of the corresponding type on the range $$$[l, r]$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$ and the sum of $$$q$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

For each operation of type $$$2$$$, print a single integer — the sum of energy levels in the range modulo $$$998244353$$$.

Example
Input
1
5 4
3 2 4 1 0
2 1 5
1 1 3
2 1 5
2 2 4
Output
10
33
27