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():
    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 propagate(self,v):
        ope = self.lazy[v]
        if ope == self.operate_unit:
            return
        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)

    def propagate_above(self,i):
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            self.propagate(v)

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

    def update(self,l,r,x):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        self.propagate_above(l0)
        self.propagate_above(r0)
        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
        self.remerge_above(l0)
        self.remerge_above(r0)

    def query(self,l,r):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        self.propagate_above(l0)
        self.propagate_above(r0)
        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

    def bisect_l(self,l,r,x):
        l += 1<<self.n
        r += 1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        self.propagate_above(l0)
        self.propagate_above(r0)
        Lmin = -1
        Rmin = -1
        while l<r:
            if l & 1:
                if self.data[l][0] <= x and Lmin==-1:
                    Lmin = l
                l += 1
            if r & 1:
                if self.data[r-1][0] <=x:
                    Rmin = r-1
            l >>= 1
            r >>= 1

        res = -1
        if Lmin != -1:
            pos = Lmin
            while pos<self.num:
                self.propagate(pos)
                if self.data[2 * pos][0] <=x:
                    pos = 2 * pos
                else:
                    pos = 2 * pos +1
            res =  pos-self.num
        if Rmin != -1:
            pos = Rmin
            while pos<self.num:
                self.propagate(pos)
                if self.data[2 * pos][0] <=x:
                    pos = 2 * pos
                else:
                    pos = 2 * pos +1
            if res==-1:
                res = pos-self.num
            else:
                res = min(res,pos-self.num)

        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))