You have a sequence $v_1, v_2, \dots, v_n$ of length $n$, all initially $0$.

You need to perform $m$ operations:

• Operation 1: Given $l, r, a$, add $a$ to the values of $v_l, v_{l+1}, \dots, v_r$.
• Operation 2: Given $l, r$, choose a non-empty subsequence from $v_l, v_{l+1}, \dots, v_r$. Calculate the sum of the variances of all such possible subsequences, modulo $998244353$.

The variance of a sequence $a_1, a_2, \dots, a_k$ is defined as $\frac{1}{k}\sum_{i=1}^k (a_i-\bar{a})^2$, where $\bar{a}=\frac{1}{k}\sum_{i=1}^k a_i$.

Input

The first line contains two integers $n, m$.

The next $m$ lines each contain four integers $1~l~r~a$ or three integers $2~l~r$, representing the first or second type of operation, respectively. It is guaranteed that $0\leq a< 998244353$.

Output

For each operation of the second type, output one line representing the answer.

Examples

Input 1

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

Output 1

388206138
339680376

Note 1

For the first query of the first test case, the sequence is $\{0, 1, 1\}$. Among all subsequences, only $\{0, 1\}$, $\{0, 1\}$, and $\{0, 1, 1\}$ have non-zero variance, which are $\frac{1}{4}, \frac{1}{4}, \frac{2}{9}$ respectively. The total sum is $\frac{13}{18}$.

Input 2

10 20
1 4 4 520968631
1 4 7 988452236
1 4 9 355405133
2 9 10
2 2 8
1 3 5 400339337
2 3 8
2 6 7
2 4 10
2 7 9
1 3 8 387471594
1 2 4 559944503
2 1 8
1 4 7 108832063
2 5 9
2 4 8
1 3 8 622785003
2 9 10
1 2 7 252591713
1 5 6 666406180

Output 2

570099967
274921471
285269733
0
571283655
970723747
401326984
17519114
844628984
570099967

Subtasks

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078

For $10\%$ of the data, $n\leq 10, m\leq 1000$.

For $20\%$ of the data, $n\leq 16, m\leq 1000$.

For $30\%$ of the data, $n\leq 100, m\leq 10^3$.

For $50\%$ of the data, $n, m\leq 10^3$.

For an additional $10\%$ of the data, $n\leq 10^5$, where all operations of type 1 occur before all operations of type 2.

For $80\%$ of the data, $n, m\leq 10^5$.

For $100\%$ of the data, $1\leq n \leq 5\times 10^6, 1\leq m\leq 10^5$.