Problem: You are given an array a_0, a_1, ..., a_{N-1} of length N. Process Q queries of the following types.

* `0 l r b c`: For each i = l, l+1, \dots, {r - 1}, set a_i \gets b \times a_i + c.
* `1 l r`: Print \sum_{i = l}^{r - 1} a_i \bmod 998244353.

Constraints

* 1 \leq N, Q \leq 500000
* 0 \leq a_i, c < 998244353
* 1 \leq b < 998244353
* 0 \leq l < r \leq N
* All values in Input are integer.

Input

Input is given from Standard Input in the following format:


N Q
a_0 a_1 ... a_{N - 1}
\textrm{Query}_0
\textrm{Query}_1
:
\textrm{Query}_{Q - 1}


Output

For each query of the latter type, print the answer.

Example

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

Solution (in PYTHON3):

Solution:
class LazySegmentTree():

    __solts__ = ["n","num","merge","merge_unit","operate","merge_operate","operate_unit","data","lazy","count"]

    def __init__(self,n,init,merge,merge_unit,operate,merge_operate,operate_unit):
        self.merge=merge
        self.merge_unit=merge_unit
        self.operate=operate
        self.merge_operate=merge_operate
        self.operate_unit=operate_unit

        self.n=(n-1).bit_length()
        self.num = 1<<self.n
        self.data=[merge_unit for i in range(1<<(self.n+1))]
        self.lazy=[operate_unit for i in range(1<<(self.n+1))]
        self.count = [1]*2*self.num
        if init:
            for i in range(n):
                self.data[2**self.n+i]=init[i]
                self.count[2**self.n+i]=1
            for i in range(2**self.n-1,0,-1):
                self.data[i]=self.merge(self.data[2*i],self.data[2*i+1])
                self.count[i]=self.count[2*i]+self.count[2*i+1]

    def update(self,l,r,x):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1

        i = l0
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            ope = self.lazy[v]
            if ope == self.operate_unit:
                continue
            self.lazy[v]=self.operate_unit
            self.data[2*v]=self.operate(self.count[2*v],self.data[2*v],ope)
            self.data[2*v+1]=self.operate(self.count[2*v+1],self.data[2*v+1],ope)
            self.lazy[2*v]=self.merge_operate(self.lazy[2*v],ope)
            self.lazy[2*v+1]=self.merge_operate(self.lazy[2*v+1],ope)

        i = r0
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            ope = self.lazy[v]
            if ope == self.operate_unit:
                continue
            self.lazy[v]=self.operate_unit
            self.data[2*v]=self.operate(self.count[2*v],self.data[2*v],ope)
            self.data[2*v+1]=self.operate(self.count[2*v+1],self.data[2*v+1],ope)
            self.lazy[2*v]=self.merge_operate(self.lazy[2*v],ope)
            self.lazy[2*v+1]=self.merge_operate(self.lazy[2*v+1],ope)

        while l<r:
            if l&1:
                self.data[l]=self.operate(self.count[l],self.data[l],x)
                self.lazy[l]=self.merge_operate(self.lazy[l],x)
                l+=1
            if r&1:
                self.data[r-1]=self.operate(self.count[r-1],self.data[r-1],x)
                self.lazy[r-1]=self.merge_operate(self.lazy[r-1],x)
            l>>=1
            r>>=1

        while l0:
            l0>>=1
            self.data[l0]=self.operate(self.count[l0],self.merge(self.data[2*l0],self.data[2*l0+1]),self.lazy[l0])

        while r0:
            r0>>=1
            self.data[r0]=self.operate(self.count[r0],self.merge(self.data[2*r0],self.data[2*r0+1]),self.lazy[r0])

    def query(self,l,r):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        i = l0
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            ope = self.lazy[v]
            if ope == self.operate_unit:
                continue
            self.lazy[v]=self.operate_unit
            self.data[2*v]=self.operate(self.count[2*v],self.data[2*v],ope)
            self.data[2*v+1]=self.operate(self.count[2*v+1],self.data[2*v+1],ope)
            self.lazy[2*v]=self.merge_operate(self.lazy[2*v],ope)
            self.lazy[2*v+1]=self.merge_operate(self.lazy[2*v+1],ope)

        i = r0
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            ope = self.lazy[v]
            if ope == self.operate_unit:
                continue
            self.lazy[v]=self.operate_unit
            self.data[2*v]=self.operate(self.count[2*v],self.data[2*v],ope)
            self.data[2*v+1]=self.operate(self.count[2*v+1],self.data[2*v+1],ope)
            self.lazy[2*v]=self.merge_operate(self.lazy[2*v],ope)
            self.lazy[2*v+1]=self.merge_operate(self.lazy[2*v+1],ope)
        res=self.merge_unit
        while l<r:
            if l&1:
                res=self.merge(res,self.data[l])
                l+=1
            if r&1:
                res=self.merge(res,self.data[r-1])
            l>>=1
            r>>=1
        return res

import sys

input = sys.stdin.readline

mod = 998244353

merge = lambda x,y:(x+y) % mod
merge_unit = 0
operate = lambda L,x,y:(y[0]*x+y[1]*L) % mod
merge_operate = lambda x,y:(x[0]*y[0] % mod,(x[1]*y[0]+y[1])%mod)

operate_unit = (1,0)

N,Q = map(int,input().split())
a = list(map(int,input().split()))

LST = LazySegmentTree(N,a,merge,merge_unit,operate,merge_operate,operate_unit)

for _ in range(Q):
    query = list(map(int,input().split()))
    if query[0] == 0:
        gomi,l,r,b,c = query
        LST.update(l,r,(b,c))
    else:
        gomi,l,r = query
        print(LST.query(l,r))