Range Affine Range Sum

Source: AtCoder

Version: Phuoc Hung OJ Extended

Problem Statement

Apply affine maps $x\mapsto bx+c$ on half-open ranges and query range sums modulo $998244353$.

Input

The first line contains $N,Q$ and the next line $a_0,\ldots,a_{N-1}$. Queries are:

• 0 l r b c: for $l\le i<r$, set $a_i\leftarrow b a_i+c$ modulo $998244353$.
• 1 l r: print $\sum_{i=l}^{r-1}a_i$ modulo $998244353$.

Output

Print one line for every type 1 query.

Subtasks

• 20 points: $N,Q\le50$.
• 30 points: $N,Q\le5000$.
• 50 points: $N,Q\le5\cdot10^5$, $0\le a_i,c<998244353$, $1\le b<998244353$.

Examples

Input

5 7
1 2 3 4 5
1 0 5
0 2 4 100 101
1 0 3
0 1 3 102 103
1 2 5
0 2 5 104 105
1 0 5

Output

15
404
41511
4317767

Explanation

The first answer is 15. Each update applies an affine function in chronological order, with arithmetic modulo $998244353$. The later answers are 404, 41511, and 4317767.