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):
class LazySegmentTree:


    __slots__ = ["n", "original_size", "log", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]


    def __init__(self, length_or_list, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
        self.me = monoid_identity
        self.oe = operator_identity
        self.fmm = func_monoid_monoid
        self.fmo = func_monoid_operator
        self.foo = func_operator_operator

        if isinstance(length_or_list, int):
            self.original_size = length_or_list
            self.log = (self.original_size - 1).bit_length()
            self.n = 1 << self.log
            self.data = [self.me] * (self.n * 2)
            self.lazy = [self.oe] * (self.n * 2)
        elif isinstance(length_or_list, list):
            self.original_size = len(length_or_list)
            self.log = (self.original_size - 1).bit_length()
            self.n = 1 << self.log
            self.data = [self.me] * self.n + length_or_list + [self.me] * (self.n - self.original_size)
            for i in range(self.n-1, 0, -1):
                self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])
            self.lazy = [self.oe] * (self.n * 2)
        else:
            raise TypeError(f"The argument 'length_or_list' must be an integer or a list, not {type(length_or_list).__name__}")
            

    def replace(self, index, value):
        if index < -self.original_size or self.original_size <= index:
            raise IndexError("LazySegmentTree index out of range")
        if index < 0:
            index += self.original_size

        index += self.n

        
        for shift in range(self.log, 0, -1):
            i = index >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        
        self.data[index] = value
        self.lazy[index] = self.oe

        
        i = index
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe


    def __getitem__(self, index):
        if index < -self.original_size or self.original_size <= index:
            raise IndexError("LazySegmentTree index out of range")
        if index < 0:
            index += self.original_size

        index += self.n

        
        for shift in range(self.log, 0, -1):
            i = index >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        
        

        return self.data[index]


    def effect(self, l, r, operator):
        if l < 0:
            l += self.original_size
        if r < 0:
            r += self.original_size
        if not 0 <= l <= r <= self.original_size:
            raise IndexError("LazySegmentTree index out of range")

        if l == r:
            return

        l += self.n
        r += self.n

        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2
        
        
        for shift in range(self.log, 0, -1):
            i = l >> shift
            if i << shift != l:
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
            i = r >> shift
            if i << shift != r:
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe

        
        while l < r:
            if l % 2:
                self.lazy[l] = self.foo(self.lazy[l], operator)
                l += 1
            if r % 2:
                r -= 1
                self.lazy[r] = self.foo(self.lazy[r], operator)
            l //= 2
            r //= 2

        
        i = l0
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe
        i = r0
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe
            
        
    def folded(self, l, r):
        if l < 0:
            l += self.original_size
        if r < 0:
            r += self.original_size
        if not 0 <= l <= r <= self.original_size:
            raise IndexError("LazySegmentTree index out of range")

        l += self.n
        r += self.n

        
        for shift in range(self.log, 0, -1):
            i = l >> shift
            if i << shift != l:
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
            i = r >> shift
            if i << shift != r:
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe

        
        left_folded = self.me
        right_folded = self.me
        while l < r:
            if l % 2:
                left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
            l //= 2
            r //= 2
        return self.fmm(left_folded, right_folded)


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

def yosupo():
    
    
    import sys
    input = sys.stdin.buffer.readline

    def fmm(m1, m2):
        m = m1 + m2
        return (((m >> 32) % MOD) << 32) + (m & mask32)
    
    def fmo(m1, o1):
        val = m1 >> 32
        cnt = m1 & mask32
        b = o1 >> 32
        c = o1 & mask32
        return (((b * val + c * cnt) % MOD) << 32) + cnt

    def foo(o1, o2):
        b1 = o1 >> 32
        c1 = o1 & mask32
        b2 = o2 >> 32
        c2 = o2 & mask32
        b = b1 * b2 % MOD
        c = (c1 * b2 + c2) % MOD
        return (b << 32) + c

    N, Q = map(int, input().split())
    monoid_data = [(A << 32) + 1 for A in map(int, input().split())]
    lst = LazySegmentTree(monoid_data, 1, 1 << 32, fmm, fmo, foo)
    for _ in range(Q):
        q, *k = map(int, input().split())
        if q == 0:
            o = (k[2] << 32) + k[3]
            lst.effect(k[0], k[1], o)
        else:
            print(lst.folded(k[0], k[1]) >> 32)

def atc2():
    
    

    import sys
    input = sys.stdin.buffer.readline

    N, Q = map(int, input().split())
    monoid_data = [(0, 1, 0) if A == b'1' else (1, 0, 0) for A in input().split()]

    def fmm(m1, m2):
        return (m1[0] + m2[0], m1[1] + m2[1], m1[2] + m2[2] + m1[1] * m2[0])

    def fmo(m1, o1):
        if o1:
            return (m1[1], m1[0], m1[0] * m1[1] - m1[2])
        else:
            return m1 

    def foo(o1, o2):
        return o1 ^ o2

    lst = LazySegmentTree(monoid_data, (0, 0, 0), 0, fmm, fmo, foo)
    ans = []
    for _ in range(Q):
        T, L, R = map(int, input().split())
        if T == 1:
            lst.effect(L-1, R, 1)
        else:
            ans.append(lst.folded(L-1, R)[2])
    print('\n'.join(map(str, ans)))

if __name__ == "__main__":
    yosupo()

Solution (Python):
import sys
input = sys.stdin.buffer.readline


class LazySegmentTree:
    def __init__(self, n, unitX, unitA, X_f, A_f, XA_map):
        self.n = n
        self.unitX = unitX
        self.unitA = unitA
        self.X_f = X_f  
        self.A_f = A_f  
        self.XA_map = XA_map  
        self.X = [unitX] * (n + n)
        self.A = [unitA] * (n + n)

    def __getitem__(self, i):
        i += self.n
        self._propagate_above(i)
        return self.X[i]

    def __setitem__(self, i, x):
        i += self.n
        self._propagate_above(i)
        self.X[i] = x
        self._calc_above(i)

    def build(self, array):
        for i, val in enumerate(array, self.n):
            self.X[i] = val
        for i in range(self.n - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def _calc_above(self, i):
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def _propagate_above(self, i):
        k = i >> 1
        H = k.bit_length() - 1
        for h in range(H, -1, -1):
            i = k >> h
            if self.A[i] == self.unitA:
                continue
            self.X[i << 1] = self.XA_map(self.X[i << 1], self.A[i])
            self.X[i << 1 | 1] = self.XA_map(self.X[i << 1 | 1], self.A[i])
            self.A[i << 1] = self.A_f(self.A[i << 1], self.A[i])
            self.A[i << 1 | 1] = self.A_f(self.A[i << 1 | 1], self.A[i])
            self.A[i] = self.unitA

    def fold(self, l, r):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self._propagate_above(l0)
        self._propagate_above(r0)
        xl = self.unitX
        xr = self.unitX
        while l < r:
            if l & 1:
                xl = self.X_f(xl, self.X[l])
                l += 1
            if r & 1:
                r -= 1
                xr = self.X_f(self.X[r], xr)
            l >>= 1
            r >>= 1
        return self.X_f(xl, xr)

    def apply(self, i, a):
        i += self.n
        self._propagate_above(i)
        self.X[i] = self.XA_map(self.X[i], a)
        self.A[i] = self.A_f(self.A[i], a)
        self._calc_above(i)

    def apply_range(self, l, r, a):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self._propagate_above(l0)
        self._propagate_above(r0)
        while l < r:
            if l & 1:
                self.X[l] = self.XA_map(self.X[l], a)
                self.A[l] = self.A_f(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.X[r] = self.XA_map(self.X[r], a)
                self.A[r] = self.A_f(self.A[r], a)
            l >>= 1
            r >>= 1
        self._calc_above(l0)
        self._calc_above(r0)


n, q = map(int, input().split())
a = list(map(int, input().split()))
queries = [list(map(int, input().split())) for i in range(q)]
MOD = 998244353

"""
unitX = (0, 0)
unitA = (1, 0)
X_f = lambda x1, x2: ((x1[0] + x2[0]) % MOD, (x1[1] + x2[1]) % MOD)
XA_map = lambda x, a: ((x[0] * a[0] + x[1] * a[1]) % MOD, x[1])
A_f = lambda a1, a2: ((a2[0] * a1[0]) % MOD, (a2[0] * a1[1] + a2[1]) % MOD)
"""

unitX = 0
unitA = MOD
def X_f(x1, x2):
    x10, x11 = divmod(x1, MOD)
    x20, x21 = divmod(x2, MOD)
    return ((x10 + x20) % MOD) * MOD + (x11 + x21) % MOD

def XA_map(x, a):
    x0, x1 = divmod(x, MOD)
    a0, a1 = divmod(a, MOD)
    return ((x0 * a0 + x1 * a1) % MOD) * MOD + x1

def A_f(a1, a2):
    a10, a11 = divmod(a1, MOD)
    a20, a21 = divmod(a2, MOD)
    return ((a20 * a10) % MOD) * MOD + (a20 * a11 + a21) % MOD


lst = LazySegmentTree(n, unitX, unitA, X_f, A_f, XA_map)
lst.build([val * MOD + 1 for val in a])

ans = []
for flag, *query in queries:
    if flag == 0:
        l, r, b, c = query
        if l + 1 == r:
            lst.apply(l, b * MOD + c)
        else:
            lst.apply_range(l, r, b * MOD + c)
    else:
        l, r = query
        if l + 1 == r:
            ans.append(lst[l] // MOD)
        else:
            ans.append(lst.fold(l, r) // MOD)

print("\n".join(map(str, ans)))