Problem:
 Score : 100 points    Problem Statement 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.        Sample Input 1 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      Sample Output 1 15
404
41511
4317767

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 998244353
INF = float("inf")

sys.setrecursionlimit(1000000)


class LazySegTree():  
    def __init__(self, initial_values, monoid_func, composition, operate, monoid_identity, operator_identity):
        self.N = len(initial_values)
        self.monoid_func = monoid_func
        self.composition = composition
        self.operate = operate
        self.monoid_identity = monoid_identity
        self.operator_identity = operator_identity
        self.data = [self.monoid_identity]*(2*self.N)
        self.lazy = [self.operator_identity]*(2*self.N)
        self.size = [0]*(2*self.N)

        for i, ai in enumerate(initial_values):
            self.data[self.N+i] = ai
            self.size[self.N+i] = 1
        for i in range(self.N-1,0,-1):
            self.data[i] = self.monoid_func(self.data[i << 1], self.data[i << 1 | 1])
            self.size[i] = self.size[i << 1] + self.size[i << 1 | 1]

    def update(self,i,x):  
        i += self.N
        self.data[i] = x
        while i>1:
            i >>= 1
            self.data[i] = self.monoid_func(self.data[i << 1], self.data[i << 1 | 1])

    def eval_at(self,i):  
        return self.operate(self.data[i],self.lazy[i],self.size[i])

    def eval_above(self,i):  
        while i > 1:
            i >>= 1
            self.data[i] = self.monoid_func(self.eval_at(i << 1),self.eval_at(i << 1 | 1))

    def propagate_at(self,i):  
        self.data[i] = self.operate(self.data[i],self.lazy[i],self.size[i])
        self.lazy[i << 1] = self.composition(self.lazy[i << 1],self.lazy[i])
        self.lazy[i << 1 | 1] = self.composition(self.lazy[i << 1 | 1], self.lazy[i])
        self.lazy[i] = self.operator_identity

    def propagate_above(self,i):  
        H = i.bit_length()
        for h in range(H,0,-1):
            self.propagate_at(i >> h)

    def fold(self, L, R):  
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        vL = self.monoid_identity
        vR = self.monoid_identity
        while L < R:
            if L & 1:
                vL = self.monoid_func(vL,self.eval_at(L))
                L += 1
            if R & 1:
                R -= 1
                vR = self.monoid_func(self.eval_at(R),vR)
            L >>= 1
            R >>= 1
        return self.monoid_func(vL,vR)

    
    def apply_range(self,L,R,x):  
        L += self.N
        R += 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.lazy[L] = self.composition(self.lazy[L], x)
                L += 1
            if R & 1:
                R -= 1
                self.lazy[R] = self.composition(self.lazy[R], x)
            L >>= 1
            R >>= 1
        self.eval_above(L0)
        self.eval_above(R0)

def main():
    def monoid_func(x,y):
        return (x+y) % 998244353

    def composition(a,b):
        b0,c0 = a
        b1,c1 = b
        return ((b0*b1) % 998244353,(b1*c0+c1) % 998244353)

    def operate(x,a,r): 
        b,c = a
        return (b*x+c*r) % 998244353

    monoid_identity = 0
    operator_identity = (1,0)

    N, Q = LI()
    A = LI()
    LST = LazySegTree(A, monoid_func, composition, operate, monoid_identity, operator_identity)

    for q in LIR(Q):
        if q[0] == 0:
            _, l, r, b, c = q
            LST.apply_range(l,r,(b,c))
        else:
            _, l, r = q
            print(LST.fold(l,r))

if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 998244353
INF = float("inf")

sys.setrecursionlimit(1000000)


class LazySegTree():  
    def __init__(self, initial_values, monoid_func, composition, operate, monoid_identity, operator_identity):
        self.N = len(initial_values)
        self.monoid_func = monoid_func
        self.composition = composition
        self.operate = operate
        self.monoid_identity = monoid_identity
        self.operator_identity = operator_identity
        self.data = [self.monoid_identity]*(2*self.N)
        self.lazy = [self.operator_identity]*(2*self.N)
        self.size = [0]*(2*self.N)

        for i, ai in enumerate(initial_values):
            self.data[self.N+i] = ai
            self.size[self.N+i] = 1
        for i in range(self.N-1,0,-1):
            self.data[i] = self.monoid_func(self.data[i << 1], self.data[i << 1 | 1])
            self.size[i] = self.size[i << 1] + self.size[i << 1 | 1]

    def update(self,i,x):  
        i += self.N
        self.data[i] = x
        while i>1:
            i >>= 1
            self.data[i] = self.monoid_func(self.data[i << 1], self.data[i << 1 | 1])

    def eval_at(self,i):  
        return self.operate(self.data[i],self.lazy[i],self.size[i])

    def eval_above(self,i):  
        while i > 1:
            i >>= 1
            self.data[i] = self.monoid_func(self.eval_at(i << 1),self.eval_at(i << 1 | 1))

    def propagate_at(self,i):  
        self.data[i] = self.operate(self.data[i],self.lazy[i],self.size[i])
        self.lazy[i << 1] = self.composition(self.lazy[i << 1],self.lazy[i])
        self.lazy[i << 1 | 1] = self.composition(self.lazy[i << 1 | 1], self.lazy[i])
        self.lazy[i] = self.operator_identity

    def propagate_above(self,i):  
        H = i.bit_length()
        for h in range(H,0,-1):
            self.propagate_at(i >> h)

    def fold(self, L, R):  
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        vL = self.monoid_identity
        vR = self.monoid_identity
        while L < R:
            if L & 1:
                vL = self.monoid_func(vL,self.eval_at(L))
                L += 1
            if R & 1:
                R -= 1
                vR = self.monoid_func(self.eval_at(R),vR)
            L >>= 1
            R >>= 1
        return self.monoid_func(vL,vR)

    
    def apply_range(self,L,R,x):  
        L += self.N
        R += 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.lazy[L] = self.composition(self.lazy[L], x)
                L += 1
            if R & 1:
                R -= 1
                self.lazy[R] = self.composition(self.lazy[R], x)
            L >>= 1
            R >>= 1
        self.eval_above(L0)
        self.eval_above(R0)

def main():
    def monoid_func(x,y):
        return (x+y) % 998244353

    def composition(a,b):
        b0,c0 = a
        b1,c1 = b
        return ((b0*b1) % 998244353,(b1*c0+c1) % 998244353)

    def operate(x,a,r): 
        b,c = a
        return (b*x+c*r) % 998244353

    monoid_identity = 0
    operator_identity = (1,0)

    N, Q = LI()
    A = LI()
    LST = LazySegTree(A, monoid_func, composition, operate, monoid_identity, operator_identity)

    for q in LIR(Q):
        if q[0] == 0:
            _, l, r, b, c = q
            LST.apply_range(l,r,(b,c))
        else:
            _, l, r = q
            print(LST.fold(l,r))

if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 998244353
INF = float("inf")

sys.setrecursionlimit(1000000)


class LazySegTree():  
    def __init__(self, initial_values, monoid_func, composition, operate, monoid_identity, operator_identity):
        self.N = len(initial_values)
        self.monoid_func = monoid_func
        self.composition = composition
        self.operate = operate
        self.monoid_identity = monoid_identity
        self.operator_identity = operator_identity
        self.data = [self.monoid_identity]*(2*self.N)
        self.lazy = [self.operator_identity]*(2*self.N)
        self.size = [0]*(2*self.N)

        for i, ai in enumerate(initial_values):
            self.data[self.N+i] = ai
            self.size[self.N+i] = 1
        for i in range(self.N-1,0,-1):
            self.data[i] = self.monoid_func(self.data[i << 1], self.data[i << 1 | 1])
            self.size[i] = self.size[i << 1] + self.size[i << 1 | 1]

    def update(self,i,x):  
        i += self.N
        self.data[i] = x
        while i>1:
            i >>= 1
            self.data[i] = self.monoid_func(self.data[i << 1], self.data[i << 1 | 1])

    def eval_at(self,i):  
        return self.operate(self.data[i],self.lazy[i],self.size[i])

    def eval_above(self,i):  
        while i > 1:
            i >>= 1
            self.data[i] = self.monoid_func(self.eval_at(i << 1),self.eval_at(i << 1 | 1))

    def propagate_at(self,i):  
        self.data[i] = self.operate(self.data[i],self.lazy[i],self.size[i])
        self.lazy[i << 1] = self.composition(self.lazy[i << 1],self.lazy[i])
        self.lazy[i << 1 | 1] = self.composition(self.lazy[i << 1 | 1], self.lazy[i])
        self.lazy[i] = self.operator_identity

    def propagate_above(self,i):  
        H = i.bit_length()
        for h in range(H,0,-1):
            self.propagate_at(i >> h)

    def fold(self, L, R):  
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        vL = self.monoid_identity
        vR = self.monoid_identity
        while L < R:
            if L & 1:
                vL = self.monoid_func(vL,self.eval_at(L))
                L += 1
            if R & 1:
                R -= 1
                vR = self.monoid_func(self.eval_at(R),vR)
            L >>= 1
            R >>= 1
        return self.monoid_func(vL,vR)

    
    def operate_range(self,L,R,x):  
        L += self.N
        R += 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.lazy[L] = self.composition(self.lazy[L], x)
                L += 1
            if R & 1:
                R -= 1
                self.lazy[R] = self.composition(self.lazy[R], x)
            L >>= 1
            R >>= 1
        self.eval_above(L0)
        self.eval_above(R0)

def main():
    def monoid_func(x,y):
        return (x+y) % MOD

    def composition(a,b):
        b0,c0 = a
        b1,c1 = b
        return ((b0*b1) % MOD,(b1*c0+c1) % MOD)

    def operate(x,a,r): 
        b,c = a
        return (b*x+c*r) % MOD

    monoid_identity = 0
    operator_identity = (1,0)

    N, Q = LI()
    A = LI()
    LST = LazySegTree(A, monoid_func, composition, operate, monoid_identity, operator_identity)

    for q in LIR(Q):
        if q[0] == 0:
            _, l, r, b, c = q
            LST.operate_range(l,r,(b,c))
        else:
            _, l, r = q
            print(LST.fold(l,r))

if __name__ == '__main__':
    main()

Solution (Python):
class LazySegmentTree:
    def __init__(self, op_X, e_X, mapping, compose, id_M, N, array=None):
        
        
        self.e_X = e_X; self.op_X = op_X; self.mapping = mapping; self.compose = compose; self.id_M = id_M
        self.N = N
        self.log = (N-1).bit_length()
        self.N0 = 1<<self.log
        self.data = [e_X]*(2*self.N0)
        self.lazy = [id_M]*self.N0
        if array:
            assert N == len(array)
            self.data[self.N0:self.N0+self.N] = array
            for i in range(self.N0-1,0,-1): self.update(i)

    
    def point_set(self, p, x):
        p += self.N0
        for i in range(self.log, 0,-1):
            self.push(p>>i)
        self.data[p] = x
        for i in range(1, self.log + 1):
            self.update(p>>i)
 
    
    def point_get(self, p):
        p += self.N0
        for i in range(self.log, 0, -1):
            self.push(p>>i)
        return self.data[p]
 
    
    def prod(self, l, r):
        if l == r: return self.e_X
        l += self.N0
        r += self.N0
        for i in range(self.log, 0, -1):
            if (l>>i)<<i != l:
                self.push(l>>i)
            if (r>>i)<<i != r:
                self.push(r>>i)

        sml = smr = self.e_X
        while l < r:
            if l & 1: 
                sml = self.op_X(sml, self.data[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op_X(self.data[r], smr)
            l >>= 1
            r >>= 1
        return self.op_X(sml, smr)
 
    
    def all_prod(s): return self.data[1]
 
    
    def apply(self, p, f):
        p += self.N0
        for i in range(self.log, 0, -1):
            self.push(p>>i)
        self.data[p] = self.mapping(f, self.data[p])
        for i in range(1, self.log + 1):
            self.update(p>>i)
 
    
    def apply(self, l, r, f):
        if l == r: return
        l += self.N0
        r += self.N0
        for i in range(self.log, 0, -1):
            if (l>>i)<<i != l:
                self.push(l>>i)
            if (r>>i)<<i != r:
                self.push((r-1)>>i)

        l2, r2 = l, r
        while l < r:
            if l & 1: 
                self.all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.all_apply(r, f)
            l >>= 1
            r >>= 1

        l, r = l2, r2
        for i in range(1, self.log + 1):
            if (l>>i)<<i != l:
                self.update(l>>i)
            if (r>>i)<<i != r:
                self.update((r-1)>>i)
     
    """
    始点 l を固定
    f(x_l*...*x_{r-1}) が True になる最大の r 
    つまり TTTTFFFF となるとき、F となる最小の添え字
    存在しない場合 n が返る
    f(e_M) = True でないと壊れる
    """
    def max_right(self, l, g):
        if l == self.N: return self.N
        l += self.N0
        for i in range(self.log, 0, -1): self.push(l>>i)
        sm = self.e_X
        while True:
            while l&1 == 0:
                l >>= 1
            if not g(self.op_X(sm, self.data[l])):
                while l < self.N0:
                    self.push(l)
                    l *= 2
                    if g(self.op_X(sm, self.data[l])):
                        sm = self.op_X(sm, self.data[l])
                        l += 1
                return l - self.N0
            sm = self.op_X(sm, self.data[l])
            l += 1
            if l&-l == l: break
        return self.N
 
    """
    終点 r を固定
    f(x_l*...*x_{r-1}) が True になる最小の l
    つまり FFFFTTTT となるとき、T となる最小の添え字
    存在しない場合 r が返る
    f(e_M) = True でないと壊れる
    """
    def min_left(self, r, g):
        if r == 0: return 0
        r += self.N0
        for i in range(self.log, 0, -1): self.push((r-1)>>i)
        sm = self.e_X
        while True:
            r -= 1
            while r>1 and r&1:
                r >>= 1
            if not g(self.op_X(self.data[r], sm)):
                while r < self.N0:
                    self.push(r)
                    r = 2*r + 1
                    if g(self.op_X(self.data[r], sm)):
                        sm = self.op_X(self.data[r], sm)
                        r -= 1
                return r + 1 - self.N0
            sm = self.op_X(self.data[r], sm)
            if r&-r == r: break
        return 0
        
    
    def update(self, k):
        self.data[k] = self.op_X(self.data[2*k], self.data[2*k+1])
    
    def all_apply(self, k, f):
        self.data[k] = self.mapping(f, self.data[k])
        if k < self.N0:
            self.lazy[k] = self.compose(f, self.lazy[k])

    def push(self, k): 
        if self.lazy[k] == self.id_M: return
        self.data[2*k  ] = self.mapping(self.lazy[k], self.data[2*k])
        self.data[2*k+1] = self.mapping(self.lazy[k], self.data[2*k+1])
        if 2*k < self.N0:
            self.lazy[2*k]   = self.compose(self.lazy[k], self.lazy[2*k])
            self.lazy[2*k+1] = self.compose(self.lazy[k], self.lazy[2*k+1])
        self.lazy[k] = self.id_M
    
e_X = 0
id_M = 1<<32
def op_X(X,Y):
    return ((((X+Y)>>32)%MOD)<<32) + ((X+Y)&MASK)
def compose(D,C):
    a = C>>32; b = C&MASK
    c = D>>32; d = D&MASK
    return (a*c%MOD<<32) + (c*b + d)%MOD
def mapping(C,X):
    x = X>>32; v = X&MASK
    a = C>>32; b = C&MASK
    return ((x*a + v*b)%MOD<<32) + v


import sys
readline = sys.stdin.readline

MOD = 998244353
MASK = (1<<32)-1

n,q = map(int, readline().split())
a = [(int(i)<<32)+1 for i in input().split()]

seg = LazySegmentTree(op_X, e_X, mapping, compose, id_M, n, array=a)

for _ in range(q):
    *V, = map(int, readline().split())
    if V[0]==0:
        _,l,r,b,c = V
        seg.apply(l,r,(b<<32)+c)
    else:
        _,l,r = V
        print(seg.prod(l,r)>>32)

Solution (Python):
from typing import Callable, List, TypeVar

S = TypeVar("S")
F = TypeVar("F")


class LazySegmentTree:
    """Lazy Segment Tree
    References:
        https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp
    """

    __slots__ = [
        "e",
        "op",
        "id",
        "mapping",
        "composition",
        "_n",
        "_log",
        "_size",
        "tree",
        "lazy",
    ]

    def __init__(
        self,
        a: List[S],
        e: S,
        op: Callable[[S, S], S],
        id_: F,
        mapping: Callable[[F, S], S],
        composition: Callable[[F, F], F],
    ) -> None:
        self.e = e
        self.op = op
        self.id = id_
        self.mapping = mapping
        self.composition = composition

        self._n = len(a)
        self._log = (self._n - 1).bit_length()
        self._size = 1 << self._log

        self.tree = [e] * self._size + a + [e] * (self._size - self._n)
        for i in range(self._size - 1, 0, -1):
            self._update(i)

        self.lazy = [id_] * self._size

    def _update(self, k: int) -> None:
        """Update the value of a[k]."""
        self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])

    def _apply_all(self, k: int, f: F) -> None:
        self.tree[k] = self.mapping(f, self.tree[k])
        if k < self._size:
            self.lazy[k] = self.composition(f, self.lazy[k])

    def _push(self, k: int) -> None:
        self._apply_all(2 * k, self.lazy[k])
        self._apply_all(2 * k + 1, self.lazy[k])
        self.lazy[k] = self.id

    def set(self, k: int, x: S) -> None:
        """Assign x to a[k] in O(log n)."""
        assert 0 <= k < self._n

        k += self._size
        for i in range(self._log, 0, -1):
            self._push(k >> i)
        self.tree[k] = x
        while k:
            k >>= 1
            self._update(k)

    def get(self, k: int) -> S:
        """Return a[k] in O(1)."""
        assert 0 <= k < self._n

        k += self._size
        for i in range(self._log, 0, -1):
            self._push(k >> i)
        return self.tree[k]

    def prod(self, l: int, r: int) -> S:
        """Return op(a[l], ..., a[r - 1]). Return e, if l == r.
        Complexity: O(log n)
        """
        assert 0 <= l <= r <= self._n

        if l == r:
            return self.e

        l += self._size
        r += self._size
        for i in range(self._log, 0, -1):
            if ((l >> i) << i) != l:
                self._push(l >> i)
            if ((r >> i) << i) != r:
                self._push(r >> i)

        sml, smr = self.e, self.e
        while l < r:
            if l & 1:
                sml = self.op(sml, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.tree[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def prod_all(self) -> S:
        """Return op(a[0], ..., a[n - 1]. Return e if n == 0.
        Complexity: O(1)
        """
        return self.tree[1]

    def apply(self, k: int, f: F) -> None:
        """Apply a[p] = op_st(a[p], x) in O(log n)."""
        assert 0 <= k < self._n

        k += self._size
        for i in range(self._log, 0, -1):
            self._push(k >> i)
        self.tree[k] = self.mapping(f, self.tree[k])
        for i in range(1, self._log + 1):
            self._update(k >> i)

    def apply_range(self, l: int, r: int, f: F) -> None:
        """Apply a[i] = op_st(a[i], x) for all i = l..r-1 in O(log n)."""
        assert 0 <= l <= r <= self._n

        if l == r:
            return

        l += self._size
        r += self._size
        for i in range(self._log, 0, -1):
            if ((l >> i) << i) != l:
                self._push(l >> i)
            if ((r >> i) << i) != r:
                self._push((r - 1) >> i)

        l_tmp, r_tmp = l, r
        while l < r:
            if l & 1:
                self._apply_all(l, f)
                l += 1
            if r & 1:
                r -= 1
                self._apply_all(r, f)
            l >>= 1
            r >>= 1
        l, r = l_tmp, r_tmp

        for i in range(1, self._log + 1):
            if ((l >> i) << i) != l:
                self._update(l >> i)
            if ((r >> i) << i) != r:
                self._update((r - 1) >> i)

    def max_right(self, l: int, g: Callable[[S], bool]) -> int:
        """
        Return an index r satisfying both:
            1. r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. r = n or f(op(a[l], a[l + 1], ..., a[r])) = false.

        If f is monotone, this is the maximum r satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= l <= self._n
        assert g(self.e)

        if l == self._n:
            return self._n

        l += self._size
        for i in range(self._log, 0, -1):
            self._push(l >> i)
        sm = self.e

        while True:
            while not l & 1:
                l >>= 1

            if not g(self.op(sm, self.tree[l])):
                while l < self._size:
                    l *= 2
                    if g(self.op(sm, self.tree[l])):
                        sm = self.op(sm, self.tree[l])
                        l += 1
                return l - self._size

            sm = self.op(sm, self.tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self._n

    def min_left(self, r: int, g: Callable[[S], bool]) -> int:
        """
        Return an index l satisfying both:
            1. l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. l = 0 or f(op(a[l - 1], a[l + 1], ..., a[r - 1])) = false.
        If f is monotone, this is the minimum l satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= r <= self._n
        assert g(self.e)

        if not r:
            return 0

        r += self._size
        for i in range(self._log, 0, -1):
            self._push((r - 1) >> i)
        sm = self.e

        while True:
            r -= 1
            while r > 1 and r & 1:
                r >>= 1

            if not g(self.op(self.tree[r], sm)):
                while r < self._size:
                    r = 2 * r + 1
                    if g(self.op(self.tree[r], sm)):
                        sm = self.op(self.tree[r], sm)
                        r -= 1
                return r + 1 - self._size

            sm = self.op(self.tree[r], sm)

            if (r & -r) == r:
                break

        return 0


MOD = 998244353


def range_affine_range_sum():
    """
    https://judge.yosupo.jp/problem/range_affine_range_sum
    https://atcoder.jp/contests/practice2/tasks/practice2_k
    """
    import sys

    readline = sys.stdin.buffer.readline

    N, Q = map(int, readline().split())
    A = [(i << 32) + 1 for i in map(int, readline().split())]

    e = 1
    id_ = 1 << 32

    def op(s, t):
        sv, sn = s >> 32, s % (1 << 32)
        tv, tn = t >> 32, t % (1 << 32)
        return (((sv + tv) % MOD) << 32) + sn + tn

    def mapping(f, a):
        fb, fc = f >> 32, f % (1 << 32)
        av, an = a >> 32, a % (1 << 32)
        return (((fb * av + fc * an) % MOD) << 32) + an

    def composition(f, g):
        fb, fc = f >> 32, f % (1 << 32)
        gb, gc = g >> 32, g % (1 << 32)
        return ((fb * gb % MOD) << 32) + ((gc * fb + fc) % MOD)

    tree = LazySegmentTree(A, e, op, id_, mapping, composition)
    res = []
    for _ in range(Q):
        com, l, r, *bc = map(int, readline().split())
        if com:
            res.append(tree.prod(l, r) >> 32)
        else:
            b, c = bc
            tree.apply_range(l, r, (b << 32) + c)
    print("\n".join(map(str, res)))


if __name__ == "__main__":
    range_affine_range_sum()