Background

Celestials open the blue heavens, and the silver realm loses the dusk.

Problem Description

The stars in the night sky form a sequence $a$. The $i$-th number in the sequence represents the brightness of the $i$-th star.

Now, as the favored one of the stars, you have two ways to operate on the stars.

• Operation 1: The input format is $\texttt{1 l r x y}$, which means changing the brightness of all stars in $[l,r]$ whose brightness is $x$ to $y$.

• Operation 2: The input format is $\texttt{2 l r}$, which means outputting the value of $\prod\limits_{i = l}^{r} C_{\sum_{j = l}^{i}a_j}^{a_i}\ \bmod 998244353$.

Input Format

The first line contains two integers $n,q$, representing the length of the sequence and the number of operations.

The second line contains $n$ integers, representing the initial values of the sequence.

The next $q$ lines each contain one operation, with the format given above.

Output Format

For each operation of type $2$, output the required value.

3 3
2 3 5
2 1 3
1 1 3 2 4
2 1 2

2520
35

5 5
4 6 7 8 9
1 2 4 9 8
1 3 5 8 9
2 3 5
2 1 3
2 1 2

412013881
4084080
210

Hint

Sample Explanation #1

It can be obtained by directly computing according to the statement.

For $100\%$ of the testdata, $1 \le n,q,a_i \le 10^5$. Also, $1 \le l,r\le n;1 \le x,y\le 10^5$.

At any time, $\sum a$ will not exceed $10^7$.

Translated by ChatGPT 5