AtCoder Library Practice Contest - Range Affine Range Sum

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

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
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 monoid_func(s, t):
	(sv, sn) = (s >> 32, s % (1 << 32))
	(tv, tn) = (t >> 32, t % (1 << 32))
	return ((sv + tv) % MOD << 32) + sn + tn

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

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

def main():
	monoid_identity = 0
	operator_identity = 1 << 32
	(N, Q) = LI()
	A = [(ai << 32) + 1 for ai in 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 << 32) + c)
		else:
			(_, l, r) = q
			print(LST.fold(l, r) >> 32)
main()


class SegmentTreeLazy:

	def __init__(self, arr, ti, ei, func, op, merge):
		self.h = (len(arr) - 1).bit_length()
		self.n = 2 ** self.h
		self.func = func
		self.op = op
		self.merge = merge
		self.ti = ti
		self.ei = ei
		self.val = [ti for _ in range(2 * self.n)]
		for i in range(len(arr)):
			self.val[self.n + i] = arr[i]
		for i in range(1, self.n)[::-1]:
			self.val[i] = self.func(self.val[2 * i], self.val[2 * i + 1])
		self.laz = [ei for _ in range(2 * self.n)]

	def reflect(self, k):
		if self.laz[k] == self.ei:
			return self.val[k]
		return self.op(self.val[k], self.laz[k])

	def propagate(self, k):
		if self.laz[k] == self.ei:
			return
		self.laz[2 * k] = self.merge(self.laz[2 * k], self.laz[k])
		self.laz[2 * k + 1] = self.merge(self.laz[2 * k + 1], self.laz[k])
		self.val[k] = self.reflect(k)
		self.laz[k] = self.ei

	def thrust(self, k):
		for i in range(1, self.h + 1)[::-1]:
			self.propagate(k >> i)

	def recalc(self, k):
		while k:
			k >>= 1
			self.val[k] = self.func(self.reflect(2 * k), self.reflect(2 * k + 1))

	def update(self, lt, rt, x):
		lt += self.n
		rt += self.n
		vl = lt
		vr = rt
		self.thrust(lt)
		self.thrust(rt - 1)
		while rt - lt > 0:
			if lt & 1:
				self.laz[lt] = self.merge(self.laz[lt], x)
				lt += 1
			if rt & 1:
				rt -= 1
				self.laz[rt] = self.merge(self.laz[rt], x)
			lt >>= 1
			rt >>= 1
		self.recalc(vl)
		self.recalc(vr - 1)

	def query(self, lt, rt):
		lt += self.n
		rt += self.n
		self.thrust(lt)
		self.thrust(rt - 1)
		vl = vr = self.ti
		while rt - lt > 0:
			if lt & 1:
				vl = self.func(vl, self.reflect(lt))
				lt += 1
			if rt & 1:
				rt -= 1
				vr = self.func(self.reflect(rt), vr)
			lt >>= 1
			rt >>= 1
		return self.func(vl, vr)
import sys
input = sys.stdin.buffer.readline
MOD = 998244353
(N, Q) = map(int, input().split())
arr = [a * MOD + 1 for a in map(int, input().split())]
ti = 0
ei = MOD

def func(a, b):
	(a1, a2) = divmod(a, MOD)
	(b1, b2) = divmod(b, MOD)
	c1 = (a1 + b1) % MOD
	c2 = (a2 + b2) % MOD
	return c1 * MOD + c2

def op(a, x):
	(a1, a2) = divmod(a, MOD)
	(x1, x2) = divmod(x, MOD)
	c1 = (a1 * x1 + a2 * x2) % MOD
	c2 = a2
	return c1 * MOD + c2

def merge(x, y):
	(x1, x2) = divmod(x, MOD)
	(y1, y2) = divmod(y, MOD)
	z1 = x1 * y1 % MOD
	z2 = (x2 * y1 + y2) % MOD
	return z1 * MOD + z2
st = SegmentTreeLazy(arr, ti, ei, func, op, merge)
res = list()
for _ in range(Q):
	(q, *p) = map(int, input().split())
	if q == 0:
		(l, r, b, c) = p
		st.update(l, r, b * MOD + c)
	else:
		(l, r) = p
		res.append(st.query(l, r) // MOD)
print('\n'.join(map(str, res)))


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


class LazySegmentTree:

	def __init__(self, n, op, e, mapping, composition, id):
		self.n = n
		self.op = op
		self.e = e
		self.mapping = mapping
		self.composition = composition
		self.id = id
		self.log = (n - 1).bit_length()
		self.size = 1 << self.log
		self.d = [e] * (2 * self.size)
		self.lz = [id] * self.size

	def update(self, k):
		self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

	def all_apply(self, k, f):
		self.d[k] = self.mapping(f, self.d[k])
		if k < self.size:
			self.lz[k] = self.composition(f, self.lz[k])

	def push(self, k):
		self.all_apply(2 * k, self.lz[k])
		self.all_apply(2 * k + 1, self.lz[k])
		self.lz[k] = self.id

	def build(self, arr):
		assert len(arr) == self.n
		for i in range(self.n):
			self.d[self.size + i] = arr[i]
		for i in range(1, self.size)[::-1]:
			self.update(i)

	def set(self, p, x):
		assert 0 <= p < self.n
		p += self.size
		for i in range(1, self.log + 1)[::-1]:
			self.push(p >> i)
		self.d[p] = x
		for i in range(1, self.log + 1):
			self.update(p >> i)

	def get(self, p):
		assert 0 <= p < self.n
		p += self.size
		for i in range(1, self.log + 1):
			self.push(p >> i)
		return self.d[p]

	def prod(self, l, r):
		assert 0 <= l <= r <= self.n
		if l == r:
			return self.e
		l += self.size
		r += self.size
		for i in range(1, self.log + 1)[::-1]:
			if l >> i << i != l:
				self.push(l >> i)
			if r >> i << i != r:
				self.push(r >> i)
		sml = smr = self.e
		while l < r:
			if l & 1:
				sml = self.op(sml, self.d[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.d[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def all_prod(self):
		return self.d[1]

	def apply(self, p, f):
		assert 0 <= p < self.n
		p += self.size
		for i in range(1, self.log + 1)[::-1]:
			self.push(p >> i)
		self.d[p] = self.mapping(f, self.d[p])
		for i in range(1, self.log + 1):
			self.update(p >> i)

	def range_apply(self, l, r, f):
		assert 0 <= l <= r <= self.n
		if l == r:
			return
		l += self.size
		r += self.size
		for i in range(1, self.log + 1)[::-1]:
			if l >> i << i != l:
				self.push(l >> i)
			if r >> i << i != r:
				self.push(r - 1 >> i)
		l2 = l
		r2 = 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 = l2
		r = 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)

	def max_right(self, l, g):
		if l == self.n:
			return self.n
		l += self.size
		for i in range(1, self.log + 1)[::-1]:
			self.push(l >> i)
		sm = self.e
		while True:
			while l % 2 == 0:
				l >>= 1
			if not g(self.op(sm, self.d[l])):
				while l < self.size:
					self.push(l)
					l = 2 * l
					if g(self.op(sm, self.d[l])):
						sm = self.op(sm, self.d[l])
						l += 1
				return l - self.size
			sm = self.op(sm, self.d[l])
			l += 1
			if l & -l == l:
				return self.n

	def min_left(self, r, g):
		if r == 0:
			return 0
		r += self.size
		for i in range(1, self.log + 1)[::-1]:
			self.push(r - 1 >> i)
		sm = self.e
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not g(self.op(self.d[r], sm)):
				while r < self.size:
					self.push(r)
					r = 2 * r + 1
					if g(self.op(self.d[r], sm)):
						sm = self.op(self.d[r], sm)
						r -= 1
				return r + 1 - self.size
			sm = self.op(self.d[r], sm)
			if r & -r == r:
				return 0
import sys
input = sys.stdin.buffer.readline
MOD = 998244353
(N, Q) = map(int, input().split())
A = [a * MOD + 1 for a in map(int, input().split())]

def op(a, b):
	(a1, a2) = divmod(a, MOD)
	(b1, b2) = divmod(b, MOD)
	c1 = (a1 + b1) % MOD
	c2 = (a2 + b2) % MOD
	return c1 * MOD + c2

def mapping(x, a):
	(x1, x2) = divmod(x, MOD)
	(a1, a2) = divmod(a, MOD)
	c1 = (a1 * x1 + a2 * x2) % MOD
	c2 = a2
	return c1 * MOD + c2

def composition(x, y):
	(x1, x2) = divmod(x, MOD)
	(y1, y2) = divmod(y, MOD)
	z1 = x1 * y1 % MOD
	z2 = (x1 * y2 + x2) % MOD
	return z1 * MOD + z2
lst = LazySegmentTree(N, op, 0, mapping, composition, MOD)
lst.build(A)
res = []
for _ in range(Q):
	q = tuple(map(int, input().split()))
	if q[0] == 0:
		(_, l, r, b, c) = q
		lst.range_apply(l, r, b * MOD + c)
	else:
		(_, l, r) = q
		res.append(lst.prod(l, r) // MOD)
print('\n'.join(map(str, res)))


mod = 998244353

class lazy_segtree(object):

	def __init__(self, n_or_vec):
		if isinstance(n_or_vec, int):
			self.n = n_or_vec
			v = [self.e()] * n_or_vec
		elif isinstance(n_or_vec, list) or isinstance(n_or_vec, tuple):
			self.n = len(n_or_vec)
			v = n_or_vec
		self.log = (self.n - 1).bit_length()
		self.size = 1 << self.log
		self.d = [self.e()] * (2 * self.size)
		self.lz = [self.identity()] * self.size
		for (i, vi) in enumerate(v):
			self.d[self.size + i] = vi
		for i in reversed(range(1, self.size)):
			self.update(i)

	def update(self, k):
		self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

	def all_apply(self, k, f):
		self.d[k] = self.mapping(f, self.d[k])
		if k < self.size:
			self.lz[k] = self.composition(f, self.lz[k])

	def push(self, k):
		self.all_apply(2 * k, self.lz[k])
		self.all_apply(2 * k + 1, self.lz[k])
		self.lz[k] = self.identity()

	def set_x(self, p, x):
		p += self.size
		for i in reversed(range(1, self.log + 1)):
			self.push(p >> i)
		self.d[p] = x
		for i in range(1, self.log + 1):
			self.update(p >> i)

	def get(self, p):
		p += self.size
		for i in reversed(range(1, self.log + 1)):
			self.push(p >> i)
		return self.d[p]

	def show(self):
		print('show array')
		for i in range(self.n):
			print(self.get(i), end=' ')
		print('\n')

	def prod(self, l, r):
		if l == r:
			return self.e()
		l += self.size
		r += self.size
		for i in reversed(range(1, self.log + 1)):
			if l >> i << i != l:
				self.push(l >> i)
			if r >> i << i != r:
				self.push(r >> i)
		sml = self.e()
		smr = self.e()
		while l < r:
			if l & 1:
				sml = self.op(sml, self.d[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.d[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def all_prod(self):
		return self.d[1]

	def apply(self, p, f):
		p += self.size
		for i in reversed(range(1, self.log + 1)):
			self.push(p >> i)
		self.d[p] = self.mapping(f, self.d[p])
		for i in range(1, self.log + 1):
			self.update(p >> i)

	def range_apply(self, l, r, f):
		if l == r:
			return
		l += self.size
		r += self.size
		for i in reversed(range(1, self.log + 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)

	def max_right(self, l, g, target):
		if l == self.n:
			return self.n
		l += self.size
		for i in reversed(range(1, self.log + 1)):
			self.push(l >> i)
		sm = self.e()
		while True:
			while l % 2 == 0:
				l >>= 1
			if not g(self.op(sm, self.d[l]), target):
				while l < self.size:
					self.push(l)
					l = 2 * l
					if g(self.op(sm, self.d[l]), target):
						sm = self.op(sm, self.d[l])
						l += 1
				return l - self.size
			sm = self.op(sm, self.d[l])
			l += 1
			if l & -l == l:
				break
		return self.n

	def min_left(self, r, g, target):
		if r == 0:
			return 0
		r += self.size
		for i in reversed(range(1, self.log + 1)):
			self.push(r - 1 >> i)
		sm = self.e()
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not g(self.op(self.d[r], sm), target):
				while r < self.size:
					self.push(r)
					r = 2 * r + 1
					if g(self.op(self.d[r], sm), target):
						sm = self.op(self.d[r], sm)
						r -= 1
				return r + 1 - self.size
			sm = self.op(self.d[r], sm)
			if r & -r == r:
				break
		return 0

	def op(self, L, R):
		(La, Lsize) = L
		(Ra, Rsize) = R
		return ((La + Ra) % mod, Lsize + Rsize)

	def e(self):
		return (0, 0)

	def identity(self):
		return (1, 0)

	def mapping(self, L, R):
		(La, Lb) = L
		(Ra, Rsize) = R
		return ((La * Ra + Lb * Rsize) % mod, Rsize)

	def composition(self, L, R):
		(La, Lb) = L
		(Ra, Rb) = R
		return (La * Ra % mod, (Rb * La + Lb) % mod)
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
(N, Q) = map(int, input().split())
A = [(a, 1) for a in map(int, input().split())]
lazyseg = lazy_segtree(A)
for _ in range(Q):
	(t, *arg) = map(int, input().split())
	if t == 0:
		(l, r, c, d) = arg
		lazyseg.range_apply(l, r, (c, d))
	else:
		(l, r) = arg
		print(lazyseg.prod(l, r)[0])


import sys

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return list(map(int, input().split()))

def main():
	MOD = 998244353

	class Lazy_segtree:

		def __init__(self, op, e, mapping, composition, id, v):
			if type(v) is int:
				v = [e()] * v
			self._n = len(v)
			self.log = self.ceil_pow2(self._n)
			self.size = 1 << self.log
			self.d = [e()] * (2 * self.size)
			self.lz = [id()] * self.size
			self.e = e
			self.op = op
			self.mapping = mapping
			self.composition = composition
			self.id = id
			for i in range(self._n):
				self.d[self.size + i] = v[i]
			for i in range(self.size - 1, 0, -1):
				self.update(i)

		def set(self, p, x):
			p += self.size
			for i in range(self.log, 0, -1):
				self.push(p >> i)
			self.d[p] = x
			for i in range(1, self.log + 1):
				self.update(p >> i)

		def get(self, p):
			p += self.size
			for i in range(self.log, 0, -1):
				self.push(p >> i)
			return self.d[p]

		def prod(self, l, r):
			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.d[l])
					l += 1
				if r & 1:
					r -= 1
					smr = self.op(self.d[r], smr)
				l >>= 1
				r >>= 1
			return self.op(sml, smr)

		def all_prod(self):
			return self.d[1]

		def apply(self, p, f):
			p += self.size
			for i in range(self.log, 0, -1):
				self.push(p >> i)
			self.d[p] = self.mapping(f, self.d[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.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)
			(l2, r2) = (l, r)
			while l < r:
				if l & 1:
					sml = self.all_apply(l, f)
					l += 1
				if r & 1:
					r -= 1
					smr = 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)

		def max_right(self, l, g):
			if l == self._n:
				return _n
			l += self.size
			for i in range(self.log, 0, -1):
				self.push(l >> i)
			sm = self.e()
			while True:
				while l % 2 == 0:
					l >>= 1
				if not g(self.op(sm, self.d[l])):
					while l < self.size:
						self.push(l)
						l = 2 * l
						if g(self.op(sm, self.d[l])):
							sm = self.op(sm, self.d[l])
							l += 1
					return l - self.size
				sm = self.op(sm, self.d[l])
				l += 1
				if l & -l == l:
					break
			return self._n

		def min_left(self, r, g):
			if r == 0:
				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 % 2:
					r >>= 1
				if not g(self.op(self.d[r], sm)):
					while r < self.size:
						self.push(r)
						r = 2 * r + 1
						if g(self.op(self.d[r], sm)):
							sm = self.op(self.d[r], sm)
							r -= 1
					return r + 1 - self.size
				sm = self.op(self.d[r], sm)
				if r & -r == r:
					break
			return 0

		def update(self, k):
			self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

		def all_apply(self, k, f):
			self.d[k] = self.mapping(f, self.d[k])
			if k < self.size:
				self.lz[k] = self.composition(f, self.lz[k])

		def push(self, k):
			self.all_apply(2 * k, self.lz[k])
			self.all_apply(2 * k + 1, self.lz[k])
			self.lz[k] = self.id()

		def ceil_pow2(self, n):
			x = 0
			while 1 << x < n:
				x += 1
			return x

	def e():
		return 0

	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

	def id():
		return 1 << 32
	(N, Q) = MI()
	a = LI()
	for i in range(N):
		a[i] = (a[i] << 32) + 1
	seg = Lazy_segtree(op, e, mapping, composition, id, a)
	for _ in range(Q):
		q = LI()
		if q[0] == 0:
			(_, l, r, b, c) = q
			seg.apply(l, r, (b << 32) + c)
		else:
			(_, l, r) = q
			ans = seg.prod(l, r) >> 32
			print(ans % MOD)
main()


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

class LazySegmentTree:
	__slots__ = ['n', 'data', 'lazy', 'me', 'oe', 'fmm', 'fmo', 'foo']

	def __init__(self, monoid_data, 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
		self.n = len(monoid_data)
		self.data = monoid_data * 2
		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)

	def replace(self, index, value):
		index += self.n
		for shift in range(index.bit_length() - 1, 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 effect(self, l, r, operator):
		l += self.n
		r += self.n
		indices = []
		l0 = l // (l & -l) // 2
		r0 = (r // (r & -r) - 1) // 2
		while r0 > l0:
			indices.append(r0)
			r0 //= 2
		while l0 > r0:
			indices.append(l0)
			l0 //= 2
		while l0 and l0 != r0:
			indices.append(r0)
			r0 //= 2
			if l0 == r0:
				break
			indices.append(l0)
			l0 //= 2
		while r0:
			indices.append(r0)
			r0 //= 2
		for i in reversed(indices):
			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
		for i in indices:
			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):
		l += self.n
		r += self.n
		indices = []
		l0 = l // (l & -l) // 2
		r0 = (r // (r & -r) - 1) // 2
		while r0 > l0:
			indices.append(r0)
			r0 //= 2
		while l0 > r0:
			indices.append(l0)
			l0 //= 2
		while l0 and l0 != r0:
			indices.append(r0)
			r0 //= 2
			if l0 == r0:
				break
			indices.append(l0)
			l0 //= 2
		while r0:
			indices.append(r0)
			r0 //= 2
		for i in reversed(indices):
			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)

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

	def fmm(m1, m2):
		m = m1 + m2
		return ((m >> 32) % MOD << 32) + (m & mask)

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

	def foo(o1, o2):
		b1 = o1 >> 32
		c1 = o1 & mask
		b2 = o2 >> 32
		c2 = o2 & mask
		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 test():
	import random

	def madd(a, b):
		return (a + b) % MOD

	def mmul(a, b):
		return a * b % MOD
	lst = LazySegmentTree([0] * 10, 0, 1, madd, mmul, mmul)
	ls = [0] * 10
	for _ in range(10000000):
		if random.randint(0, 1):
			l = random.randint(0, 9)
			r = random.randint(l + 1, 10)
			e = random.randint(1, 782)
			lst.effect(l, r, e)
			for i in range(l, r):
				ls[i] *= e
				ls[i] %= MOD
		else:
			l = random.randint(0, 9)
			r = random.randint(l + 1, 10)
			if lst.folded(l, r) != sum(ls[l:r]):
				print(ls)
				print(l, r)
				print(lst.folded(l, r))
main()


class LazySegmentTree:
	__slots__ = ['merge', 'merge_unit', 'operate', 'merge_operate', 'operate_unit', 'n', 'data', 'lazy']

	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.data = [merge_unit for i in range(1 << self.n + 1)]
		self.lazy = [operate_unit for i in range(1 << self.n + 1)]
		if init:
			for i in range(n):
				self.data[2 ** self.n + i] = init[i]
			for i in range(2 ** self.n - 1, 0, -1):
				self.data[i] = self.merge(self.data[2 * i], self.data[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[v << 1] = self.operate(self.data[v << 1], ope)
		self.data[(v << 1) + 1] = self.operate(self.data[(v << 1) + 1], ope)
		self.lazy[v << 1] = self.merge_operate(self.lazy[v << 1], ope)
		self.lazy[(v << 1) + 1] = self.merge_operate(self.lazy[(v << 1) + 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:
			c = self.merge(self.data[i], self.data[i ^ 1])
			i >>= 1
			self.data[i] = self.operate(c, 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.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.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 >> 32
import sys
input = sys.stdin.buffer.readline
mod = 998244353
mask = 2 ** 32 - 1

def merge(x, y):
	s = ((x >> 32) + (y >> 32)) % mod
	num = (x & mask) + (y & mask)
	return (s << 32) + num
merge_unit = 0

def operate(x, ope):
	(s, num) = (x >> 32, x & mask)
	(b, c) = (ope >> 32, ope & mask)
	s = (b * s + c * num) % mod
	return (s << 32) + num

def merge_operate(x, y):
	(b1, c1) = (x >> 32, x & mask)
	(b2, c2) = (y >> 32, y & mask)
	return (b1 * b2 % mod << 32) + (b2 * c1 + c2) % mod
operate_unit = 1 << 32
(N, Q) = map(int, input().split())
a = list(map(int, input().split()))
a = [(a[i] << 32) + 1 for i in range(N)]
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 << 32) + c)
	else:
		(gomi, l, r) = query
		print(LST.query(l, r))


import sys
sys.setrecursionlimit(10 ** 7)

def MI():
	return map(int, sys.stdin.readline().rstrip().split())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

class LazySegTree:

	def __init__(self, N, X_func, A_func, operate, X_unit, A_unit):
		self.N = N
		self.X_func = X_func
		self.A_func = A_func
		self.operate = operate
		self.X_unit = X_unit
		self.A_unit = A_unit
		self.X = [self.X_unit] * (2 * self.N)
		self.A = [self.A_unit] * (2 * self.N)
		self.size = [0] * (2 * self.N)

	def build(self, init_value):
		for i in range(self.N):
			self.X[self.N + i] = init_value[i]
			self.size[self.N + i] = 1
		for i in range(self.N - 1, 0, -1):
			self.X[i] = self.X_func(self.X[i << 1], self.X[i << 1 | 1])
			self.size[i] = self.size[i << 1] + self.size[i << 1 | 1]

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

	def eval_at(self, i):
		return self.operate(self.X[i], self.A[i], self.size[i])

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

	def propagate_at(self, i):
		self.X[i] = self.operate(self.X[i], self.A[i], self.size[i])
		self.A[i << 1] = self.A_func(self.A[i << 1], self.A[i])
		self.A[i << 1 | 1] = self.A_func(self.A[i << 1 | 1], self.A[i])
		self.A[i] = self.A_unit

	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.X_unit
		vR = self.X_unit
		while L < R:
			if L & 1:
				vL = self.X_func(vL, self.eval_at(L))
				L += 1
			if R & 1:
				R -= 1
				vR = self.X_func(self.eval_at(R), vR)
			L >>= 1
			R >>= 1
		return self.X_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.A[L] = self.A_func(self.A[L], x)
				L += 1
			if R & 1:
				R -= 1
				self.A[R] = self.A_func(self.A[R], x)
			L >>= 1
			R >>= 1
		self.eval_above(L0)
		self.eval_above(R0)
mod = 998244353

def X_func(x, y):
	return (x + y) % mod

def A_func(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
X_unit = 0
A_unit = (1, 0)
(N, Q) = MI()
LST = LazySegTree(N, X_func, A_func, operate, X_unit, A_unit)
A = LI()
LST.build(A)
for i in range(Q):
	X = LI()
	if X[0] == 0:
		(l, r, b, c) = X[1:]
		LST.operate_range(l, r, (b, c))
	else:
		(l, r) = X[1:]
		print(LST.fold(l, r))


class LazySegmentTree:

	def __init__(self, op, e, mapping, composition, ie, init_array):
		self.op = op
		self.e = e
		self.mapping = mapping
		self.composition = composition
		self.ie = ie
		l = len(init_array)

		def ceil_pow2(n):
			x = 0
			while 1 << x < n:
				x += 1
			return x
		self.log = ceil_pow2(l)
		self.size = 1 << self.log
		self.d = [e() for _ in range(2 * self.size)]
		self.lz = [ie() for _ in range(self.size)]
		for (i, a) in enumerate(init_array):
			self.d[i + self.size] = a
		for i in range(self.size - 1, 0, -1):
			self.__update(i)

	def set(self, p, x):
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		self.d[p] = x
		for i in range(1, self.log + 1):
			self.__update(p >> i)

	def __getitem__(self, p):
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		return self.d[p]

	def prod(self, l, r):
		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 = self.e()
		smr = self.e()
		while l < r:
			if l & 1:
				sml = self.op(sml, self.d[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.d[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def apply(self, l, r, f):
		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)
		l2 = l
		r2 = 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 = l2
		r = 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)

	def __update(self, k):
		self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

	def __all_apply(self, k, f):
		self.d[k] = self.mapping(f, self.d[k])
		if k < self.size:
			self.lz[k] = self.composition(f, self.lz[k])

	def __push(self, k):
		self.__all_apply(2 * k, self.lz[k])
		self.__all_apply(2 * k + 1, self.lz[k])
		self.lz[k] = self.ie()

def atcoder_practice_k():
	import sys
	input = sys.stdin.buffer.readline
	(N, Q) = map(int, input().split())
	A = list(map(lambda x: (int(x) << 32) + 1, input().split()))
	MOD = 998244353

	def e():
		return 0

	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

	def ie():
		return 1 << 32
	st = LazySegmentTree(op, e, mapping, composition, ie, A)
	for _ in range(Q):
		(k, *q) = map(int, input().split())
		if k == 0:
			(l, r, b, c) = q
			st.apply(l, r, (b << 32) + c)
		else:
			(l, r) = q
			a = st.prod(l, r)
			print(a >> 32)
atcoder_practice_k()


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')

class LazySegmentTree:

	def __init__(self, n, a=None):
		num = 1
		while num <= n:
			num *= 2
		self.num = num
		self.seg = [ninf] * (2 * self.num - 1)
		self.lazy = [f0] * (2 * self.num - 1)
		self.ls = [0] * (2 * self.num - 1)
		self.rs = [0] * (2 * self.num - 1)
		self.ls[0] = 0
		self.rs[0] = self.num
		for i in range(self.num - 1):
			self.ls[2 * i + 1] = self.ls[i]
			self.rs[2 * i + 1] = (self.ls[i] + self.rs[i]) // 2
			self.ls[2 * i + 2] = (self.ls[i] + self.rs[i]) // 2
			self.rs[2 * i + 2] = self.rs[i]
		if a is not None:
			assert len(a) == n
			for i in range(n):
				self.seg[num - 1 + i] = a[i]
			for k in range(num - 2, -1, -1):
				self.seg[k] = op(self.seg[2 * k + 1], self.seg[2 * k + 2])

	def eval(self, k):
		if self.lazy[k] == f0:
			return
		if k < self.num - 1:
			self.lazy[k * 2 + 1] = composition(self.lazy[k], self.lazy[k * 2 + 1])
			self.lazy[k * 2 + 2] = composition(self.lazy[k], self.lazy[k * 2 + 2])
		self.seg[k] = mapping(self.lazy[k], self.seg[k])
		self.lazy[k] = f0

	def eval_all(self):
		for i in range(2 * self.num - 1):
			self.eval(i)

	def update(self, a, b, x=None, f=None):
		if f is None:
			f = lambda y: x
		k = 0
		q = [k]
		while q:
			k = q.pop()
			(l, r) = (self.ls[k], self.rs[k])
			if k >= 0:
				self.eval(k)
				if r <= a or b <= l:
					continue
				elif a <= l and r <= b:
					self.lazy[k] = composition(f, self.lazy[k])
					self.eval(k)
				else:
					q.append(~k)
					q.append(2 * k + 1)
					q.append(2 * k + 2)
			else:
				k = ~k
				self.seg[k] = op(self.seg[2 * k + 1], self.seg[2 * k + 2])

	def query(self, a, b):
		k = 0
		l = 0
		r = self.num
		q = [k]
		ans = ninf
		while q:
			k = q.pop()
			(l, r) = (self.ls[k], self.rs[k])
			self.eval(k)
			if r <= a or b <= l:
				continue
			elif a <= l and r <= b:
				ans = op(ans, self.seg[k])
			else:
				q.append(2 * k + 2)
				q.append(2 * k + 1)
		return ans
(n, q) = list(map(int, input().split()))
a = list(map(int, input().split()))
M = 998244353
ninf = 0
f0 = 1 << 32

def op(x, y):
	(x0, x1) = (x >> 32, x % (1 << 32))
	(y0, y1) = (y >> 32, y % (1 << 32))
	return ((x0 + y0) % M << 32) + x1 + y1

def mapping(f, x):
	(x0, x1) = (x >> 32, x % (1 << 32))
	(f0, f1) = (f >> 32, f % (1 << 32))
	return ((f0 * x0 + f1 * x1) % M << 32) + x1

def composition(f, g):
	(g0, g1) = (g >> 32, g % (1 << 32))
	(f0, f1) = (f >> 32, f % (1 << 32))
	return (f0 * g0 % M << 32) + (g1 * f0 + f1) % M
sg = LazySegmentTree(n, [(item << 32) + 1 for item in a])
ans = []
for _ in range(q):
	t = tuple(map(int, input().split()))
	if t[0] == 0:
		(_, l, r, b, c) = t
		sg.update(l, r, f=(b << 32) + c)
	else:
		(_, s, t) = t
		ans.append(sg.query(s, t) >> 32)
write('\n'.join(map(str, ans)))


mod = 998244353
mask = 2 ** 32
ide_ele = 0
lazy_ele = mask

def segfunc(a, b):
	(a1, a2) = divmod(a, mask)
	(b1, b2) = divmod(b, mask)
	c1 = (a1 + b1) % mod
	c2 = a2 + b2
	return c1 * mask + c2

def op(a, x):
	(a1, a2) = divmod(a, mask)
	(x1, x2) = divmod(x, mask)
	c1 = (a1 * x1 + a2 * x2) % mod
	c2 = a2
	return c1 * mask + c2

def merge(x, y):
	(x1, x2) = divmod(x, mask)
	(y1, y2) = divmod(y, mask)
	z1 = x1 * y1 % mod
	z2 = (x2 * y1 + y2) % mod
	return z1 * mask + z2

class lazysegmenttree:

	def __init__(self, init_val, func=segfunc, ie=ide_ele, le=lazy_ele, op=op, merge=merge):
		n = len(init_val)
		self.func = func
		self.op = op
		self.merge = merge
		self.ie = ie
		self.le = le
		self.h = (n - 1).bit_length()
		self.num = 1 << self.h
		self.tree = [ie] * self.num * 2
		self.lazy = [le] * self.num * 2
		for i in range(n):
			self.tree[i + self.num] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = func(self.tree[2 * i], self.tree[2 * i + 1])

	def reflect(self, k):
		if self.lazy[k] == self.le:
			return self.tree[k]
		return self.op(self.tree[k], self.lazy[k])

	def propagate(self, k):
		if self.lazy[k] == self.le:
			return
		self.lazy[2 * k] = self.merge(self.lazy[2 * k], self.lazy[k])
		self.lazy[2 * k + 1] = self.merge(self.lazy[2 * k + 1], self.lazy[k])
		self.tree[k] = self.reflect(k)
		self.lazy[k] = self.le

	def thrust(self, k):
		for i in range(1, self.h + 1)[::-1]:
			self.propagate(k >> i)

	def recalc(self, k):
		while k:
			k >>= 1
			self.tree[k] = self.func(self.reflect(2 * k), self.reflect(2 * k + 1))

	def update(self, left_0, right_0, value):
		l = left_0 + self.num
		r = right_0 + self.num + 1
		vl = l
		vr = r
		x = value
		self.thrust(l)
		self.thrust(r - 1)
		while r - l > 0:
			if l & 1:
				self.lazy[l] = self.merge(self.lazy[l], x)
				l += 1
			if r & 1:
				r -= 1
				self.lazy[r] = self.merge(self.lazy[r], x)
			l >>= 1
			r >>= 1
		self.recalc(vl)
		self.recalc(vr - 1)

	def query(self, left_0, right_0):
		l = left_0 + self.num
		r = right_0 + self.num + 1
		self.thrust(l)
		self.thrust(r - 1)
		vl = vr = self.ie
		while r - l > 0:
			if l & 1:
				vl = self.func(vl, self.reflect(l))
				l += 1
			if r & 1:
				r -= 1
				vr = self.func(self.reflect(r), vr)
			l >>= 1
			r >>= 1
		return self.func(vl, vr) // mask
(n, q) = map(int, input().split())
a = [i * mask + 1 for i in map(int, input().split())]
st = lazysegmenttree(a)
ans = []
for _ in range(q):
	(q, *p) = map(int, input().split())
	if q:
		(l, r) = p
		ans += [st.query(l, r - 1)]
	else:
		(l, r, b, c) = p
		st.update(l, r - 1, b * mask + c)
print(*ans, sep='\n')


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


from typing import Callable, List, TypeVar
S = TypeVar('S')
F = TypeVar('F')

class LazySegmentTree:
	__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:
		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:
		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:
		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:
		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 self.tree[1]

	def apply(self, k: int, f: F) -> None:
		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:
		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:
		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:
		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():
	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)))
range_affine_range_sum()


class LazySegmentTree:

	def __init__(self, n, op, e, mapping, composition, id):
		self.n = n
		self.op = op
		self.e = e
		self.mapping = mapping
		self.composition = composition
		self.id = id
		self.log = (n - 1).bit_length()
		self.size = 1 << self.log
		self.d = [e] * (2 * self.size)
		self.lz = [id] * self.size

	def update(self, k):
		self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

	def all_apply(self, k, f):
		self.d[k] = self.mapping(f, self.d[k])
		if k < self.size:
			self.lz[k] = self.composition(f, self.lz[k])

	def push(self, k):
		self.all_apply(2 * k, self.lz[k])
		self.all_apply(2 * k + 1, self.lz[k])
		self.lz[k] = self.id

	def build(self, arr):
		for i in range(self.n):
			self.d[self.size + i] = arr[i]
		for i in range(1, self.size)[::-1]:
			self.update(i)

	def set(self, p, x):
		p += self.size
		for i in range(1, self.log + 1)[::-1]:
			self.push(p >> i)
		self.d[p] = x
		for i in range(1, self.log + 1):
			self.update(p >> i)

	def get(self, p):
		p += self.size
		for i in range(1, self.log + 1):
			self.push(p >> i)
		return self.d[p]

	def prod(self, l, r):
		if l == r:
			return self.e
		l += self.size
		r += self.size
		for i in range(1, self.log + 1)[::-1]:
			if l >> i << i != l:
				self.push(l >> i)
			if r >> i << i != r:
				self.push(r >> i)
		sml = smr = self.e
		while l < r:
			if l & 1:
				sml = self.op(sml, self.d[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.d[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def all_prod(self):
		return self.d[1]

	def apply(self, p, f):
		p += self.size
		for i in range(1, self.log + 1)[::-1]:
			self.push(p >> i)
		self.d[p] = self.mapping(f, self.d[p])
		for i in range(1, self.log + 1):
			self.update(p >> i)

	def range_apply(self, l, r, f):
		if l == r:
			return
		l += self.size
		r += self.size
		for i in range(1, self.log + 1)[::-1]:
			if l >> i << i != l:
				self.push(l >> i)
			if r >> i << i != r:
				self.push(r - 1 >> i)
		l2 = l
		r2 = 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 = l2
		r = 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)

	def max_right(self, l, g):
		if l == self.n:
			return self.n
		l += self.size
		for i in range(1, self.log + 1)[::-1]:
			self.push(l >> i)
		sm = self.e
		while True:
			while l % 2 == 0:
				l >>= 1
			if not g(self.op(sm, self.d[l])):
				while l < self.size:
					self.push(l)
					l = 2 * l
					if g(self.op(sm, self.d[l])):
						sm = self.op(sm, self.d[l])
						l += 1
				return l - self.size
			sm = self.op(sm, self.d[l])
			l += 1
			if l & -l == l:
				return self.n

	def min_left(self, r, g):
		if r == 0:
			return 0
		r += self.size
		for i in range(1, self.log + 1)[::-1]:
			self.push(r - 1 >> i)
		sm = self.e
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not g(self.op(self.d[r], sm)):
				while r < self.size:
					self.push(r)
					r = 2 * r + 1
					if g(self.op(self.d[r], sm)):
						sm = self.op(self.d[r], sm)
						r -= 1
				return r + 1 - self.size
			sm = self.op(self.d[r], sm)
			if r & -r == r:
				return 0
(N, Q) = map(int, input().split())
A = [(a << 32) + 1 for a in map(int, input().split())]
mod = 998244353

def op(a, b):
	(a1, a2) = (a >> 32, a % (1 << 32))
	(b1, b2) = (b >> 32, b % (1 << 32))
	c1 = (a1 + b1) % mod
	c2 = (a2 + b2) % mod
	return (c1 << 32) + c2

def mapping(x, a):
	(x1, x2) = (x >> 32, x % (1 << 32))
	(a1, a2) = (a >> 32, a % (1 << 32))
	c1 = (a1 * x1 + a2 * x2) % mod
	c2 = a2
	return (c1 << 32) + c2

def composition(x, y):
	(x1, x2) = (x >> 32, x % (1 << 32))
	(y1, y2) = (y >> 32, y % (1 << 32))
	z1 = x1 * y1 % mod
	z2 = (x1 * y2 + x2) % mod
	return (z1 << 32) + z2
seg = LazySegmentTree(N, op, 0, mapping, composition, 1 << 32)
seg.build(A)
for i in range(Q):
	(*q,) = map(int, input().split())
	if q[0] == 0:
		(_, l, r, b, c) = q
		seg.range_apply(l, r, (b << 32) + c)
	else:
		(_, l, r) = q
		print(seg.prod(l, r) >> 32)


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

class LazySegmentTree:
	__slots__ = ['n', 'data', 'lazy', 'me', 'oe', 'fmm', 'fmo', 'foo']

	def __init__(self, monoid_data, 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
		self.n = len(monoid_data)
		self.data = monoid_data * 2
		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)

	def replace(self, index, value):
		index += self.n
		for shift in range(index.bit_length() - 1, 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 effect(self, l, r, operator):
		l += self.n
		r += self.n
		l0 = l
		r0 = r
		while l0 % 2 == 0:
			l0 //= 2
		while r0 % 2 == 0:
			r0 //= 2
		r0 -= 1
		for shift in range(l0.bit_length() - 1, 0, -1):
			i = l0 >> 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
		for shift in range(r0.bit_length() - 1, 0, -1):
			i = r0 >> 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
		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):
		l += self.n
		r += self.n
		l0 = l
		r0 = r
		while l0 % 2 == 0:
			l0 //= 2
		while r0 % 2 == 0:
			r0 //= 2
		r0 -= 1
		for shift in range(l0.bit_length() - 1, 0, -1):
			i = l0 >> 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
		for shift in range(r0.bit_length() - 1, 0, -1):
			i = r0 >> 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
		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)

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


mod = 998244353
eps = 10 ** (-9)

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

	def op(a, b):
		return (a + b) % mod
	e = 0
	mask = 2 ** 32 - 1

	def mapping(a, x, seg_len):
		b = x >> 32
		c = x & mask
		return (a * b % mod + c * seg_len % mod) % mod

	def composition(x, y):
		b1 = x >> 32
		c1 = x & mask
		b2 = y >> 32
		c2 = y & mask
		return (b1 * b2 % mod << 32) + (b2 * c1 % mod + c2) % mod
	id = 1 << 32

	class LazySegTree:

		def __init__(self, A, op=op, e=e, mapping=mapping, composition=composition, id=id, initialize=True):
			self.N = len(A)
			self.LV = (self.N - 1).bit_length()
			self.N0 = 1 << self.LV
			self.op = op
			self.e = e
			self.mapping = mapping
			self.composition = composition
			self.id = id
			if initialize:
				self.data = [self.e] * self.N0 + A + [self.e] * (self.N0 - self.N)
				for i in range(self.N0 - 1, 0, -1):
					self.data[i] = op(self.data[i * 2], self.data[i * 2 + 1])
			else:
				self.data = [self.e] * (self.N0 * 2)
			self.lazy = [id] * (self.N0 * 2)

		def _ascend(self, i):
			for _ in range(i.bit_length() - 1):
				i >>= 1
				self.data[i] = self.op(self.data[i * 2], self.data[i * 2 + 1])

		def _descend(self, idx):
			lv = idx.bit_length()
			for j in range(lv - 1, 0, -1):
				i = idx >> j
				x = self.lazy[i]
				if x == self.id:
					continue
				self.lazy[i * 2] = self.composition(self.lazy[i * 2], x)
				self.lazy[i * 2 + 1] = self.composition(self.lazy[i * 2 + 1], x)
				self.lazy[i] = self.id
				self.data[i * 2] = self.mapping(self.data[i * 2], x, 1 << self.LV + j - lv)
				self.data[i * 2 + 1] = self.mapping(self.data[i * 2 + 1], x, 1 << self.LV + j - lv)

		def apply(self, l, r, x):
			l += self.N0 - 1
			r += self.N0 - 1
			self._descend(l // (l & -l))
			self._descend(r // (r & -r) - 1)
			l_ori = l
			r_ori = r
			seg_len = 1
			while l < r:
				if l & 1:
					self.data[l] = self.mapping(self.data[l], x, seg_len)
					self.lazy[l] = self.composition(self.lazy[l], x)
					l += 1
				if r & 1:
					r -= 1
					self.data[r] = self.mapping(self.data[r], x, seg_len)
					self.lazy[r] = self.composition(self.lazy[r], x)
				l >>= 1
				r >>= 1
				seg_len <<= 1
			self._ascend(l_ori // (l_ori & -l_ori))
			self._ascend(r_ori // (r_ori & -r_ori) - 1)

		def query(self, l, r):
			l += self.N0 - 1
			r += self.N0 - 1
			self._descend(l // (l & -l))
			self._descend(r // (r & -r) - 1)
			ret = self.e
			while l < r:
				if l & 1:
					ret = self.op(ret, self.data[l])
					l += 1
				if r & 1:
					ret = self.op(self.data[r - 1], ret)
					r -= 1
				l >>= 1
				r >>= 1
			return ret
	(N, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	ST = LazySegTree(A)
	for _ in range(Q):
		q = list(map(int, input().split()))
		if q[0] == 0:
			(l, r, b, c) = q[1:]
			l += 1
			r += 1
			ST.apply(l, r, (b << 32) + c)
		else:
			(l, r) = q[1:]
			l += 1
			r += 1
			print(ST.query(l, r))
main()


import sys
input = lambda : sys.stdin.readline().rstrip()

class SegmentTree:

	def __init__(self, n, p, unit, f, g, h):
		num = 2 ** (n - 1).bit_length()
		seg = [unit] * (num * 2)
		self.lazy = [None] * (num * 2)
		for i in range(n):
			seg[num + i] = p[i]
		for i in range(num - 1, 0, -1):
			seg[i] = f(seg[i << 1], seg[(i << 1) + 1])
		self.num = num
		self.seg = seg
		self.unit = unit
		self.flag = False
		self.f = f
		self.g = g
		self.h = h

	def gindex(self, l, r):
		l += self.num
		r += self.num
		lm = l // (l & -l) >> 1
		rm = r // (r & -r) >> 1
		mm = max(lm, rm)
		r -= 1
		while l < r:
			if r <= rm:
				yield r
			if l <= lm:
				yield l
			l >>= 1
			r >>= 1
		while l:
			if l <= mm:
				yield l
			l >>= 1

	def propagates(self, ids):
		num = self.num
		g = self.g
		h = self.h
		for i in reversed(ids):
			if self.lazy[i] is None:
				continue
			if i << 1 < num:
				self.lazy[i << 1] = h(self.lazy[i << 1], self.lazy[i])
				self.lazy[(i << 1) + 1] = h(self.lazy[(i << 1) + 1], self.lazy[i])
			self.seg[i << 1] = g(self.seg[i << 1], self.lazy[i])
			self.seg[(i << 1) + 1] = g(self.seg[(i << 1) + 1], self.lazy[i])
			self.lazy[i] = None

	def query(self, l, r):
		f = self.f
		if self.flag:
			(*ids,) = self.gindex(l, r)
			self.propagates(ids)
		ansl = ansr = self.unit
		l += self.num
		r += self.num - 1
		if l == r:
			return self.seg[l]
		while l < r:
			if l & 1:
				ansl = f(ansl, self.seg[l])
				l += 1
			if r & 1 == 0:
				ansr = f(self.seg[r], ansr)
				r -= 1
			l >>= 1
			r >>= 1
		if l == r:
			ansl = f(ansl, self.seg[l])
		return f(ansl, ansr)

	def update1(self, i, x):
		if self.flag:
			(*ids,) = self.gindex(i, i + 1)
			self.propagates(ids)
		i += self.num
		f = self.f
		self.seg[i] = x
		while i:
			i >>= 1
			self.seg[i] = f(self.seg[i << 1], self.seg[(i << 1) + 1])

	def update2(self, l, r, x):
		self.flag = True
		(*ids,) = self.gindex(l, r)
		self.propagates(ids)
		num = self.num
		f = self.f
		g = self.g
		h = self.h
		l += num
		r += num - 1
		if l == r:
			self.seg[l] = g(self.seg[l], x)
			for i in ids:
				self.seg[i] = f(self.seg[i << 1], self.seg[(i << 1) + 1])
			return
		while l < r:
			if l & 1:
				if l < num:
					self.lazy[l] = h(self.lazy[l], x)
				self.seg[l] = g(self.seg[l], x)
				l += 1
			if r & 1 == 0:
				if r < num:
					self.lazy[r] = h(self.lazy[r], x)
				self.seg[r] = g(self.seg[r], x)
				r -= 1
			l >>= 1
			r >>= 1
		if l == r:
			self.lazy[l] = h(self.lazy[l], x)
			self.seg[l] = g(self.seg[l], x)
		for i in ids:
			self.seg[i] = f(self.seg[i << 1], self.seg[(i << 1) + 1])

	def update(self, i, x):
		if type(i) is int:
			self.update1(i, x)
		else:
			self.update2(i[0], i[1], x)
mod = 998244353
d = 10 ** 9
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
aa = [d * i + 1 for i in a]

def f(a, b):
	(a1, a2) = divmod(a, d)
	(b1, b2) = divmod(b, d)
	c1 = (a1 + b1) % mod
	c2 = (a2 + b2) % mod
	return c1 * d + c2

def g(a, x):
	(a1, a2) = divmod(a, d)
	(x1, x2) = divmod(x, d)
	c1 = (a1 * x1 + a2 * x2) % mod
	c2 = a2
	return c1 * d + c2

def h(x, y):
	if x is None:
		return y
	(x1, x2) = divmod(x, d)
	(y1, y2) = divmod(y, d)
	z1 = x1 * y1 % mod
	z2 = (x2 * y1 + y2) % mod
	return z1 * d + z2
seg = SegmentTree(n, aa, 0, f, g, h)
for _ in range(q):
	que = list(map(int, input().split()))
	if len(que) == 5:
		(_, l, r, b, c) = que
		seg.update((l, r), b * d + c)
	else:
		(_, l, r) = que
		print(seg.query(l, r) // d)


import sys
input = lambda : sys.stdin.readline().rstrip()

class LazySegmentTree:

	def __init__(self, init, unitX, unitA, f, g, h):
		self.f = f
		self.g = g
		self.h = h
		self.unitX = unitX
		self.unitA = unitA
		self.f = f
		if type(init) == int:
			self.n = init
			self.X = [unitX] * (self.n * 2)
			self.size = [1] * (self.n * 2)
		else:
			self.n = len(init)
			self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
			self.size = [0] * self.n + [1] * len(init) + [0] * (self.n - len(init))
			for i in range(self.n - 1, 0, -1):
				self.X[i] = self.f(self.X[i * 2], self.X[i * 2 | 1])
		for i in range(self.n - 1, 0, -1):
			self.size[i] = self.size[i * 2] + self.size[i * 2 | 1]
		self.A = [unitA] * (self.n * 2)

	def update(self, i, x):
		i += self.n
		self.X[i] = x
		i >>= 1
		while i:
			self.X[i] = self.f(self.X[i * 2], self.X[i * 2 | 1])
			i >>= 1

	def calc(self, i):
		return self.g(self.X[i], self.A[i], self.size[i])

	def calc_above(self, i):
		i >>= 1
		while i:
			self.X[i] = self.f(self.calc(i * 2), self.calc(i * 2 | 1))
			i >>= 1

	def propagate(self, i):
		self.X[i] = self.g(self.X[i], self.A[i], self.size[i])
		self.A[i * 2] = self.h(self.A[i * 2], self.A[i])
		self.A[i * 2 | 1] = self.h(self.A[i * 2 | 1], self.A[i])
		self.A[i] = self.unitA

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

	def propagate_all(self):
		for i in range(1, self.n):
			self.propagate(i)

	def getrange(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)
		al = self.unitX
		ar = self.unitX
		while l < r:
			if l & 1:
				al = self.f(al, self.calc(l))
				l += 1
			if r & 1:
				r -= 1
				ar = self.f(self.calc(r), ar)
			l >>= 1
			r >>= 1
		return self.f(al, ar)

	def getvalue(self, i):
		i += self.n
		self.propagate_above(i)
		return self.calc(i)

	def operate_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.A[l] = self.h(self.A[l], a)
				l += 1
			if r & 1:
				r -= 1
				self.A[r] = self.h(self.A[r], a)
			l >>= 1
			r >>= 1
		self.calc_above(l0)
		self.calc_above(r0)

	def max_right(self, l, z):
		if l >= self.n:
			return self.n
		l += self.n
		s = self.unitX
		while 1:
			while l % 2 == 0:
				l >>= 1
			if not z(self.f(s, self.calc(l))):
				while l < self.n:
					l *= 2
					if z(self.f(s, self.calc(l))):
						s = self.f(s, self.calc(l))
						l += 1
				return l - self.n
			s = self.f(s, self.calc(l))
			l += 1
			if l & -l == l:
				break
		return self.n

	def min_left(self, r, z):
		if r <= 0:
			return 0
		r += self.n
		s = self.unitX
		while 1:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not z(self.f(self.calc(r), s)):
				while r < self.n:
					r = r * 2 + 1
					if z(self.f(self.calc(r), s)):
						s = self.f(self.calc(r), s)
						r -= 1
				return r + 1 - self.n
			s = self.f(self.calc(r), s)
			if r & -r == r:
				break
		return 0
P = 998244353
mm = 4294967295
f = lambda x, y: (x + y) % P

def g(x, a, s):
	(a1, a2) = (a >> 32, a & mm)
	return (a1 * x + a2 * s) % P

def h(a, b):
	(a1, a2) = (a >> 32, a & mm)
	(b1, b2) = (b >> 32, b & mm)
	return (a1 * b1 % P << 32) + (a2 * b1 + b2) % P
unitX = 0
unitA = 1 << 32
(N, Q) = map(int, input().split())
A = [int(a) for a in input().split()]
st = LazySegmentTree(A, unitX, unitA, f, g, h)
for _ in range(Q):
	q = [int(a) for a in input().split()]
	if q[0] == 0:
		(l, r, b, c) = q[1:]
		st.operate_range(l, r, (b << 32) + c)
	else:
		(l, r) = q[1:]
		print(st.getrange(l, r))


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')
		if l == r:
			return self.me
		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)

	def max_right(self, l, f):
		if l < -self.original_size or self.original_size < l:
			raise IndexError('LazySegmentTree index out of range')
		if l < 0:
			l += self.original_size
		assert f(self.me)
		if l == self.original_size:
			return self.original_size
		l += self.n
		for shift in range(self.log, 0, -1):
			i = l >> 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
		left_folded = self.me
		while True:
			while l % 2 == 0:
				l //= 2
			if not f(self.fmm(left_folded, self.data[l])):
				while l < self.n:
					i = 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
					l *= 2
					if f(self.fmm(left_folded, self.data[l])):
						left_folded = self.fmm(left_folded, self.data[l])
						l += 1
				return l - self.n
			left_folded = self.fmm(left_folded, self.data[l])
			l += 1
			if l == l & -l:
				break
		return self.original_size

	def min_left(self, r, f):
		if r < -self.original_size or self.original_size < r:
			raise IndexError('LazySegmentTree index out of range')
		if r < 0:
			r += self.original_size
		assert f(self.me)
		if r == 0:
			return 0
		r += self.n
		for shift in range(self.log, 0, -1):
			i = r >> 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
		right_folded = self.me
		while True:
			r -= 1
			while r > 1 and r % 2:
				r //= 2
			if not f(self.fmm(self.data[r], right_folded)):
				while r < self.n:
					i = 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
					r = 2 * r + 1
					if f(self.fmm(self.data[r], right_folded)):
						right_folded = self.fmm(self.data[r], right_folded)
						r -= 1
				return r + 1 - self.n
			right_folded = self.fmm(self.data[r], right_folded)
			if r == r & -r:
				break
		return 0
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)
	ans = []
	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:
			ans.append(lst.folded(k[0], k[1]) >> 32)
	print('\n'.join(map(str, ans)))

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


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


class LazySegmentTree:
	__slots__ = ['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.data[2 * v], ope)
			self.data[2 * v + 1] = self.operate(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.data[2 * v], ope)
			self.data[2 * v + 1] = self.operate(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.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.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.merge(self.data[2 * l0], self.data[2 * l0 + 1]), self.lazy[l0])
		while r0:
			r0 >>= 1
			self.data[r0] = self.operate(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.data[2 * v], ope)
			self.data[2 * v + 1] = self.operate(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.data[2 * v], ope)
			self.data[2 * v + 1] = self.operate(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 >> 20
import sys
input = sys.stdin.buffer.readline
mod = 998244353
mask = 2 ** 20 - 1

def merge(x, y):
	s = ((x >> 20) + (y >> 20)) % mod
	num = (x & mask) + (y & mask)
	return (s << 20) + num
merge_unit = 0

def operate(x, ope):
	(s, num) = (x >> 20, x & mask)
	s = (ope[0] * s + ope[1] * num) % mod
	return (s << 20) + num
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()))
a = [(a[i] << 20) + 1 for i in range(N)]
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))


import sys
input = lambda : sys.stdin.readline().rstrip()

class LazySegmentTree:

	def __init__(self, n, p, x_unit, m_unit, f, g, h):
		self.n = n
		self.seg = p * 2
		self.x_unit = x_unit
		self.m_unit = m_unit
		self.f = f
		self.g = g
		self.h = h
		for i in range(self.n - 1, 0, -1):
			self.seg[i] = self.f(self.seg[i << 1], self.seg[(i << 1) + 1])
		self.lazy = [m_unit] * (self.n * 2)

	def update(self, l, r, x):
		l += self.n
		r += self.n
		ll = l // (l & -l)
		rr = r // (r & -r) - 1
		for shift in range(ll.bit_length() - 1, 0, -1):
			i = ll >> shift
			self.lazy[i << 1] = self.h(self.lazy[i << 1], self.lazy[i])
			self.lazy[(i << 1) + 1] = self.h(self.lazy[(i << 1) + 1], self.lazy[i])
			self.seg[i] = self.g(self.seg[i], self.lazy[i])
			self.lazy[i] = self.m_unit
		for shift in range(rr.bit_length() - 1, 0, -1):
			i = rr >> shift
			self.lazy[i << 1] = self.h(self.lazy[i << 1], self.lazy[i])
			self.lazy[(i << 1) + 1] = self.h(self.lazy[(i << 1) + 1], self.lazy[i])
			self.seg[i] = self.g(self.seg[i], self.lazy[i])
			self.lazy[i] = self.m_unit
		while l < r:
			if l & 1:
				self.lazy[l] = self.h(self.lazy[l], x)
				l += 1
			if r & 1:
				r -= 1
				self.lazy[r] = self.h(self.lazy[r], x)
			l >>= 1
			r >>= 1
		while ll > 1:
			ll >>= 1
			self.seg[ll] = self.f(self.g(self.seg[ll << 1], self.lazy[ll << 1]), self.g(self.seg[(ll << 1) + 1], self.lazy[(ll << 1) + 1]))
			self.lazy[ll] = self.m_unit
		while rr > 1:
			rr >>= 1
			self.seg[rr] = self.f(self.g(self.seg[rr << 1], self.lazy[rr << 1]), self.g(self.seg[(rr << 1) + 1], self.lazy[(rr << 1) + 1]))
			self.lazy[rr] = self.m_unit

	def query(self, l, r):
		l += self.n
		r += self.n
		ll = l // (l & -l)
		rr = r // (r & -r) - 1
		for shift in range(ll.bit_length() - 1, 0, -1):
			i = ll >> shift
			self.lazy[i << 1] = self.h(self.lazy[i << 1], self.lazy[i])
			self.lazy[(i << 1) + 1] = self.h(self.lazy[(i << 1) + 1], self.lazy[i])
			self.seg[i] = self.g(self.seg[i], self.lazy[i])
			self.lazy[i] = self.m_unit
		for shift in range(rr.bit_length() - 1, 0, -1):
			i = rr >> shift
			self.lazy[i << 1] = self.h(self.lazy[i << 1], self.lazy[i])
			self.lazy[(i << 1) + 1] = self.h(self.lazy[(i << 1) + 1], self.lazy[i])
			self.seg[i] = self.g(self.seg[i], self.lazy[i])
			self.lazy[i] = self.m_unit
		ans_l = ans_r = self.x_unit
		while l < r:
			if l & 1:
				ans_l = self.f(ans_l, self.g(self.seg[l], self.lazy[l]))
				l += 1
			if r & 1:
				r -= 1
				ans_r = self.f(self.g(self.seg[r], self.lazy[r]), ans_r)
			l >>= 1
			r >>= 1
		return self.f(ans_l, ans_r)
mod = 998244353
mask = (1 << 32) - 1
(n, q) = map(int, input().split())
a = [(i << 32) + 1 for i in map(int, input().split())]

def f(a, b):
	m = a + b
	return ((m >> 32) % mod << 32) + (m & mask)

def g(a, x):
	a1 = a >> 32
	a2 = a & mask
	x1 = x >> 32
	x2 = x & mask
	return ((a1 * x1 + a2 * x2) % mod << 32) + a2

def h(x, y):
	x1 = x >> 32
	x2 = x & mask
	y1 = y >> 32
	y2 = y & mask
	a = x1 * y1 % mod
	b = (x2 * y1 + y2) % mod
	return (a << 32) + b
seg = LazySegmentTree(n, a, 0, 1 << 32, f, g, h)
for _ in range(q):
	(f, *query) = map(int, input().split())
	if f == 0:
		(l, r, b, c) = query
		seg.update(l, r, (b << 32) + c)
	else:
		(l, r) = query
		print(seg.query(l, r) >> 32)


import sys
readline = sys.stdin.readline

class Lazysegtree:

	def __init__(self, A, fx, ex, fm, initialize=True):
		self.N = len(A)
		self.N0 = 2 ** (self.N - 1).bit_length()
		self.ex = ex
		self.lazy = [None] * (2 * self.N0)
		if initialize:
			self.data = [self.ex] * self.N0 + A + [self.ex] * (self.N0 - self.N)
			for i in range(self.N0 - 1, -1, -1):
				self.data[i] = self.fx(self.data[2 * i], self.data[2 * i + 1])
		else:
			self.data = [self.ex] * (2 * self.N0)

	def fx(self, x, y):
		return (x + y) % MOD

	def fm(self, o, p):
		o1 = o >> 32
		return (o1 * (p >> 32) % MOD << 32) + (o1 * (p & mask) + (o & mask)) % MOD

	def fa(self, ope, idx):
		k = idx.bit_length()
		return ((ope >> 32) * self.data[idx] + (self.N0 >> k - 1) * (ope & mask)) % MOD

	def __repr__(self):
		s = 'data'
		l = 'lazy'
		cnt = 1
		for i in range(self.N0.bit_length()):
			s = '\n'.join((s, ' '.join(map(str, self.data[cnt:cnt + (1 << i)]))))
			l = '\n'.join((l, ' '.join(map(str, self.lazy[cnt:cnt + (1 << i)]))))
			cnt += 1 << i
		return '\n'.join((s, l))

	def _ascend(self, k):
		k = k >> 1
		c = k.bit_length()
		for j in range(c):
			idx = k >> j
			self.data[idx] = self.fx(self.data[2 * idx], self.data[2 * idx + 1])

	def _descend(self, k):
		k = k >> 1
		idx = 1
		c = k.bit_length()
		for j in range(1, c + 1):
			idx = k >> c - j
			if self.lazy[idx] is None:
				continue
			self.data[2 * idx] = self.fa(self.lazy[idx], 2 * idx)
			self.data[2 * idx + 1] = self.fa(self.lazy[idx], 2 * idx + 1)
			if self.lazy[2 * idx] is not None:
				self.lazy[2 * idx] = self.fm(self.lazy[idx], self.lazy[2 * idx])
			else:
				self.lazy[2 * idx] = self.lazy[idx]
			if self.lazy[2 * idx + 1] is not None:
				self.lazy[2 * idx + 1] = self.fm(self.lazy[idx], self.lazy[2 * idx + 1])
			else:
				self.lazy[2 * idx + 1] = self.lazy[idx]
			self.lazy[idx] = None

	def query(self, l, r):
		L = l + self.N0
		R = r + self.N0
		self._descend(L // (L & -L))
		self._descend(R // (R & -R) - 1)
		sl = self.ex
		sr = self.ex
		while L < R:
			if R & 1:
				R -= 1
				sr = self.fx(self.data[R], sr)
			if L & 1:
				sl = self.fx(sl, self.data[L])
				L += 1
			L >>= 1
			R >>= 1
		return self.fx(sl, sr)

	def operate(self, l, r, x):
		L = l + self.N0
		R = r + self.N0
		Li = L // (L & -L)
		Ri = R // (R & -R)
		self._descend(Li)
		self._descend(Ri - 1)
		while L < R:
			if R & 1:
				R -= 1
				self.data[R] = self.fa(x, R)
				if self.lazy[R] is None:
					self.lazy[R] = x
				else:
					self.lazy[R] = self.fm(x, self.lazy[R])
			if L & 1:
				self.data[L] = self.fa(x, L)
				if self.lazy[L] is None:
					self.lazy[L] = x
				else:
					self.lazy[L] = self.fm(x, self.lazy[L])
				L += 1
			L >>= 1
			R >>= 1
		self._ascend(Li)
		self._ascend(Ri - 1)
MOD = 998244353
mask = (1 << 32) - 1
(N, Q) = map(int, readline().split())
A = list(map(int, readline().split()))
T = Lazysegtree(A, None, 0, None, initialize=True)
Ans = []
for _ in range(Q):
	(t, *s) = readline().split()
	if t == '0':
		(l, r, b, c) = map(int, s)
		T.operate(l, r, (b << 32) + c)
	else:
		(l, r) = map(int, s)
		Ans.append(T.query(l, r))
print('\n'.join(map(str, Ans)))


import sys
input = sys.stdin.buffer.readline
mod = 998244353
INF = float('inf')
sec = pow(2, mod - 2, mod)

def getlist():
	return list(map(int, input().split()))

class lazySegTree(object):

	def __init__(self, N):
		self.N = N
		self.LV = (N - 1).bit_length()
		self.N0 = 2 ** self.LV
		self.data = [0] * (2 * self.N0)
		self.lazybeta = [1] * (2 * self.N0)
		self.lazy = [0] * (2 * self.N0)

	def initialize(self, A):
		for i in range(self.N):
			self.data[self.N0 - 1 + i] = A[i]
		for i in range(self.N0 - 2, -1, -1):
			self.data[i] = (self.data[2 * i + 1] + self.data[2 * i + 2]) % mod

	def gindex(self, l, r):
		L = l + self.N0 >> 1
		R = r + self.N0 >> 1
		lc = 0 if l & 1 else (L & -L).bit_length()
		rc = 0 if r & 1 else (R & -R).bit_length()
		for i in range(self.LV):
			if rc <= i:
				yield R
			if L < R and lc <= i:
				yield L
			L >>= 1
			R >>= 1

	def propagates(self, *ids):
		for i in reversed(ids):
			w = self.lazybeta[i - 1]
			v = self.lazy[i - 1]
			if w == 1 and (not v):
				continue
			val = v * sec % mod
			self.lazybeta[2 * i - 1] = self.lazybeta[2 * i - 1] * w % mod
			self.lazybeta[2 * i] = self.lazybeta[2 * i] * w % mod
			self.lazy[2 * i - 1] = (self.lazy[2 * i - 1] * w + val) % mod
			self.lazy[2 * i] = (self.lazy[2 * i] * w + val) % mod
			self.data[2 * i - 1] = (self.data[2 * i - 1] * w + val) % mod
			self.data[2 * i] = (self.data[2 * i] * w + val) % mod
			self.lazybeta[i - 1] = 1
			self.lazy[i - 1] = 0

	def update(self, l, r, b, c):
		(*ids,) = self.gindex(l, r + 1)
		self.propagates(*ids)
		L = self.N0 + l
		R = self.N0 + r + 1
		v = c
		w = b
		while L < R:
			if R & 1:
				R -= 1
				self.lazybeta[R - 1] = self.lazybeta[R - 1] * w % mod
				self.lazy[R - 1] = (w * self.lazy[R - 1] + v) % mod
				self.data[R - 1] = (self.data[R - 1] * w + v) % mod
			if L & 1:
				self.lazybeta[L - 1] = self.lazybeta[L - 1] * w % mod
				self.lazy[L - 1] = (w * self.lazy[L - 1] + v) % mod
				self.data[L - 1] = (self.data[L - 1] * w + v) % mod
				L += 1
			L >>= 1
			R >>= 1
			v <<= 1
		for i in ids:
			self.data[i - 1] = (self.data[2 * i - 1] + self.data[2 * i]) % mod

	def query(self, l, r):
		self.propagates(*self.gindex(l, r + 1))
		L = self.N0 + l
		R = self.N0 + r + 1
		s = 0
		while L < R:
			if R & 1:
				R -= 1
				s += self.data[R - 1]
			if L & 1:
				s += self.data[L - 1]
				L += 1
			L >>= 1
			R >>= 1
			s %= mod
		return s

def main():
	(N, Q) = getlist()
	A = getlist()
	lSeg = lazySegTree(N)
	lSeg.initialize(A)
	for _ in range(Q):
		q = getlist()
		if q[0] == 0:
			(null, l, r, b, c) = q
			lSeg.update(l, r - 1, b, c)
		else:
			(null, l, r) = q
			res = lSeg.query(l, r - 1)
			print(res)
main()


class convolution:

	def __init__(self, a: list, b: list, mod: int):
		(self.a, self.b) = (a, b)
		(self.n, self.m) = (len(a), len(b))
		self.MOD = mod
		self.g = primitive_root_constexpr(self.MOD)

	def convolution(self) -> list:
		(n, m) = (self.n, self.m)
		(a, b) = (self.a, self.b)
		if not n or not m:
			return []
		if min(n, m) <= 60:
			if n < m:
				(n, m) = (m, n)
				(a, b) = (b, a)
			ans = [0] * (n + m - 1)
			for i in range(n):
				for j in range(m):
					ans[i + j] += a[i] * b[j] % self.MOD
					ans[i + j] %= self.MOD
			return ans
		z = 1 << ceil_pow2(n + m - 1)
		a = self.resize(a, z)
		a = self.butterfly(a)
		b = self.resize(b, z)
		b = self.butterfly(b)
		for i in range(z):
			a[i] = a[i] * b[i] % self.MOD
		a = self.butterfly_inv(a)
		a = a[:n + m - 1]
		iz = self.inv(z)
		a = [x * iz % self.MOD for x in a]
		return a

	def butterfly(self, a: list) -> list:
		n = len(a)
		h = ceil_pow2(n)
		first = True
		sum_e = [0] * 30
		m = self.MOD
		if first:
			first = False
			(es, ies) = ([0] * 30, [0] * 30)
			cnt2 = bsf(m - 1)
			e = self.mypow(self.g, m - 1 >> cnt2)
			ie = self.inv(e)
			for i in range(cnt2, 1, -1):
				es[i - 2] = e
				ies[i - 2] = ie
				e = e * e % m
				ie = ie * ie % m
			now = 1
			for i in range(cnt2 - 2):
				sum_e[i] = es[i] * now % m
				now = now * ies[i] % m
		for ph in range(1, h + 1):
			w = 1 << ph - 1
			p = 1 << h - ph
			now = 1
			for s in range(w):
				offset = s << h - ph + 1
				for i in range(p):
					l = a[i + offset] % m
					r = a[i + offset + p] * now % m
					a[i + offset] = (l + r) % m
					a[i + offset + p] = (l - r) % m
				now = now * sum_e[bsf(~s)] % m
		return a

	def butterfly_inv(self, a: list) -> list:
		n = len(a)
		h = ceil_pow2(n)
		first = True
		sum_ie = [0] * 30
		m = self.MOD
		if first:
			first = False
			(es, ies) = ([0] * 30, [0] * 30)
			cnt2 = bsf(m - 1)
			e = self.mypow(self.g, m - 1 >> cnt2)
			ie = self.inv(e)
			for i in range(cnt2, 1, -1):
				es[i - 2] = e
				ies[i - 2] = ie
				e = e * e % m
				ie = ie * ie % m
			now = 1
			for i in range(cnt2 - 2):
				sum_ie[i] = ies[i] * now % m
				now = es[i] * now % m
		for ph in range(h, 0, -1):
			w = 1 << ph - 1
			p = 1 << h - ph
			inow = 1
			for s in range(w):
				offset = s << h - ph + 1
				for i in range(p):
					l = a[i + offset] % m
					r = a[i + offset + p] % m
					a[i + offset] = (l + r) % m
					a[i + offset + p] = (m + l - r) * inow % m
				inow = sum_ie[bsf(~s)] * inow % m
		return a

	@staticmethod
	def resize(array: list, sz: int) -> list:
		new_array = array + [0] * (sz - len(array))
		return new_array

	def inv(self, x: int):
		if is_prime_constexpr(self.MOD):
			assert x
			return self.mypow(x, self.MOD - 2)
		else:
			eg = inv_gcd(x)
			assert eg[0] == 1
			return eg[1]

	def mypow(self, x: int, n: int) -> int:
		assert 0 <= n
		r = 1
		m = self.MOD
		while n:
			if n & 1:
				r = r * x % m
			x = x * x % m
			n >>= 1
		return r

class dsu:

	def __init__(self, n: int):
		self._n = n
		self.parent_or_size = [-1] * self._n

	def merge(self, a: int, b: int) -> int:
		assert 0 <= a and a < self._n
		assert 0 <= b and a < self._n
		x = self.leader(a)
		y = self.leader(b)
		if x == y:
			return x
		if -self.parent_or_size[x] < -self.parent_or_size[y]:
			(x, y) = (y, x)
		self.parent_or_size[x] += self.parent_or_size[y]
		self.parent_or_size[y] = x
		return x

	def same(self, a: int, b: int) -> bool:
		assert 0 <= a and a < self._n
		assert 0 <= b and a < self._n
		return self.leader(a) == self.leader(b)

	def leader(self, a: int) -> int:
		assert 0 <= a and a < self._n
		if self.parent_or_size[a] < 0:
			return a
		self.parent_or_size[a] = self.leader(self.parent_or_size[a])
		return self.parent_or_size[a]

	def size(self, a: int) -> int:
		assert 0 <= a and a < self._n
		return -self.parent_or_size[self.leader(a)]

	def groups(self):
		leader_buf = [0] * self._n
		group_size = [0] * self._n
		for i in range(self._n):
			leader_buf[i] = self.leader(i)
			group_size[leader_buf[i]] += 1
		result = [[] for _ in range(self._n)]
		for i in range(self._n):
			result[leader_buf[i]].append(i)
		result = [v for v in result if v]
		return result

class fenwick_tree:

	def __init__(self, n):
		self._n = n
		self.data = [0] * n

	def add(self, p: int, x: int):
		assert 0 <= p and p <= self._n
		p += 1
		while p <= self._n:
			self.data[p - 1] += x
			p += p & -p

	def sum(self, l: int, r: int) -> int:
		assert 0 <= l and l <= r and (r <= self._n)
		return self.__sum(r) - self.__sum(l)

	def __sum(self, r: int) -> int:
		s = 0
		while r > 0:
			s += self.data[r - 1]
			r -= r & -r
		return s

def ceil_pow2(n: int) -> int:
	x = 0
	while 1 << x < n:
		x += 1
	return x

def bsf(n: int) -> int:
	return (n & -n).bit_length() - 1

def safe_mod(x: int, m: int) -> int:
	x %= m
	if x < 0:
		x += m
	return x

class barrett:

	def __init__(self, m: int):
		self._m = m
		self.im = -1 // (m + 1)

	def umod(self):
		return self._m

	def mul(self, a: int, b: int) -> int:
		z = a
		z *= b
		x = z * im >> 64
		v = z - x * self._m
		if self._m <= v:
			v += self._m
		return v

def pow_mod_constexpr(x: int, n: int, m: int) -> int:
	if m == 1:
		return 0
	_m = m
	r = 1
	y = safe_mod(x, m)
	while n:
		if n & 1:
			r = r * y % _m
		y = y * y % _m
		n >>= 1
	return r

def is_prime_constexpr(n: int) -> bool:
	if n <= 1:
		return False
	if n == 2 or n == 7 or n == 61:
		return True
	if n % 2 == 0:
		return False
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for a in [2, 7, 61]:
		t = d
		y = pow_mod_constexpr(a, t, n)
		while t != n - 1 and y != 1 and (y != n - 1):
			y = y * y % n
			t <<= 1
		if y != n - 1 and t % 2 == 0:
			return False
	return True

def inv_gcd(self, a: int, b: int) -> tuple:
	a = safe_mod(a, b)
	if a == 0:
		return (b, 0)
	s = b
	t = a
	m0 = 0
	m1 = 1
	while t:
		u = s // t
		s -= t * u
		m0 -= m1 * u
		tmp = s
		s = t
		t = tmp
		tmp = m0
		m0 = m1
		m1 = tmp
	if m0 < 0:
		m0 += b // s
	return (s, m0)

def primitive_root_constexpr(m: int) -> int:
	if m == 2:
		return 1
	if m == 167772161:
		return 3
	if m == 469762049:
		return 3
	if m == 754974721:
		return 11
	if m == 998244353:
		return 3
	divs = [0] * 20
	divs[0] = 2
	cnt = 1
	x = (m - 1) // 2
	while x % 2 == 0:
		x //= 2
	i = 3
	while i * i <= x:
		if x % i == 0:
			divs[cnt] = i
			cnt += 1
			while x % i == 0:
				x //= i
		i += 2
	if x > 1:
		divs[cnt] = x
		cnt += 1
	g = 2
	while True:
		ok = True
		for i in range(cnt):
			if pow_mod_constexpr(g, (m - 1) // div[i], m) == 1:
				ok = False
				break
		if ok:
			return g
		g += 1

class simple_queue:

	def __init__(self):
		self.payload = []
		self.pos = 0

	def size(self):
		return len(self.payload) - self.pos

	def empty(self):
		return self.pos == len(self.payload)

	def push(self, t: int):
		self.payload.append(t)

	def front(self):
		return self.payload[self.pos]

	def clear(self):
		self.payload.clear()
		pos = 0

	def pop(self):
		self.pos += 1

	def pop_front(self):
		self.pos += 1
		return self.payload[~-self.pos]

class csr:

	def __init__(self, n: int, edges: list):
		from copy import deepcopy
		self.start = [0] * (n + 1)
		self.elist = [[] for _ in range(len(edges))]
		for e in edges:
			self.start[e[0] + 1] += 1
		for i in range(1, n + 1):
			self.start[i] += self.start[i - 1]
		counter = deepcopy(self.start)
		for e in edges:
			self.elist[counter[e[0]]] = e[1]
			counter[e[0]] += 1

class scc_graph:
	edges = []

	def __init__(self, n: int):
		self._n = n
		self.now_ord = 0
		self.group_num = 0

	def num_vertices(self):
		return self._n

	def add_edge(self, _from: int, _to: int):
		self.edges.append((_from, [_to]))

	def scc_ids(self):
		g = csr(self._n, self.edges)
		visited = []
		low = [0] * self._n
		ord = [-1] * self._n
		ids = [0] * self._n

		def dfs(s, v: int):
			low[v] = ord[v] = self.now_ord
			self.now_ord += 1
			visited.append(v)
			for i in range(g.start[v], g.start[v + 1]):
				to = g.elist[i][0]
				if ord[to] == -1:
					s(s, to)
					low[v] = min(low[v], low[to])
				else:
					low[v] = min(low[v], ord[to])
			if low[v] == ord[v]:
				while True:
					u = visited.pop()
					ord[u] = self._n
					ids[u] = self.group_num
					if u == v:
						break
				self.group_num += 1
		for i in range(self._n):
			if ord[i] == -1:
				dfs(dfs, i)
		for i in range(self._n):
			ids[i] = self.group_num - 1 - ids[i]
		return (self.group_num, ids)

	def scc(self):
		ids = self.scc_ids()
		group_num = ids[0]
		counts = [0] * group_num
		for x in ids[1]:
			counts[x] += 1
		groups = [[] for _ in range(group_num)]
		for i in range(self._n):
			groups[ids[1][i]].append(i)
		return groups

class lazy_segtree:

	def __init__(self, op, e, mapping, composition, id, v: list):
		self.op = op
		self.e = e
		self.mapping = mapping
		self.composition = composition
		self.id = id
		self._n = len(v)
		self.log = ceil_pow2(self._n)
		self.size = 1 << self.log
		self.lz = [self.id()] * self.size
		self.d = [self.e()] * (2 * self.size)
		for i in range(self._n):
			self.d[self.size + i] = v[i]
		for i in range(self.size - 1, 0, -1):
			self.__update(i)

	def set_(self, p: int, x: int):
		assert 0 <= p and p < self._n
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		self.d[p] = x
		for i in range(1, self.log + 1):
			self.__update(p >> 1)

	def get(self, p: int):
		assert 0 <= p and p < self._n
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		return self.d[p]

	def prod(self, l: int, r: int):
		assert 0 <= l and l <= r and (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.d[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.d[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def all_prod(self):
		return self.d[1]

	def apply(self, p: int, f):
		assert 0 <= p and p < self._n
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		self.d[p] = self.mapping(f, self.d[p])
		for i in range(1, self.log + 1):
			self.__update(p >> 1)

	def apply(self, l: int, r: int, f):
		assert 0 <= l and l <= r and (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)
		(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 >> i)

	def max_right(self, l: int, g):
		assert 0 <= l and l <= self._n
		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 l % 2 == 0:
				l >>= 1
			if not g(self.op(sm, self.d[l])):
				while l < self.size:
					self.__push(l)
					l = 2 * l
					if g(self.op(sm, self.d[l])):
						sm = self.op(sm, self.d[l])
						l += 1
				return l - self.size
			sm = self.op(sm, self.d[l])
			l += 1
			if l & -l == l:
				break
		return self._n

	def min_left(self, r: int, g):
		assert 0 <= r and r <= self._n
		if r == 0:
			return 0
		r += self.size
		for i in range(self.log, 0, -1):
			self.__push(r >> i)
		sm = self.e()
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not g(self.op(self.d[r], sm)):
				while r < self.size:
					self.__push(r)
					r = 2 * r + 1
					if g(self.op(self.d[r], sm)):
						sm = self.op(self.d[r], sm)
						r -= 1
				return r + 1 - self.size
			sm = self.op(self.d[r], sm)
			if r & -r == r:
				break
		return 0

	def __update(self, k: int):
		self.d[k] = self.op(self.d[k * 2], self.d[k * 2 + 1])

	def __all_apply(self, k: int, f):
		self.d[k] = self.mapping(f, self.d[k])
		if k < self.size:
			self.lz[k] = self.composition(f, self.lz[k])

	def __push(self, k: int):
		self.__all_apply(2 * k, self.lz[k])
		self.__all_apply(2 * k + 1, self.lz[k])
		self.lz[k] = self.id()

def pow_mod(x: int, n: int, m: int) -> int:
	assert 0 <= n and 1 <= m
	if m == 1:
		return 0
	bt = barrett(m)
	r = 1
	y = safe_mod(x, m)
	while n:
		if n & 1:
			r = bt.mul(r, y)
		y = bt.mul(y, y)
		n >>= 1
	return n

def inv_mod(x: int, m: int) -> int:
	assert 1 <= m
	z = inv_gcd(x, m)
	assert z[0] == 1
	return z[1]

def crt(r: list, m: list) -> tuple:
	assert len(r) == len(m)
	n = len(r)
	r0 = 0
	m0 = 1
	for i in range(n):
		assert 1 <= m[i]
		r1 = safe_mod(r[i], m[i])
		m1 = m[i]
		if m0 < m1:
			(r0, r1) = (r1, r0)
			(m0, m1) = (m1, m0)
		if m0 % m1 == 0:
			if r0 % m1 != r1:
				return (0, 0)
			continue
		(g, im) = inv_gcd(m0, m1)
		u1 = m1 // g
		if (r1 - r0) % g:
			return (0, 0)
		x = (r1 - r0) // g % u1 * im % u1
		r0 += x * m0
		m0 *= u1
		if r0 < 0:
			r0 += m0
	return (r0, m0)

def floor_sum(n: int, m: int, a: int, b: int) -> int:
	ans = 0
	if a >= m:
		ans += (n - 1) * n * (a // m) // 2
		a %= m
	if b >= m:
		ans += n * (b // m)
		bb %= m
	y_max = (a * n + b) // m
	x_max = y_max * m - b
	if y_max == 0:
		return ans
	ans += (n - (x_max + a - 1) // a) * y_max
	ans += floor_sum(y_max, a, m, (a - x_max % a) % a)
	return ans

class mf_graph:
	numeric_limits_max = 10 ** 18

	def __init__(self, n: int):
		self._n = n
		self.g = [[] for _ in range(self._n)]
		self.pos = []

	def add_edge(self, _from: int, _to: int, cap: int) -> int:
		assert 0 <= _from and _from < self._n
		assert 0 <= _to and _to < self._n
		assert 0 <= cap
		m = len(self.pos)
		self.pos.append((_from, len(self.g[_from])))
		self.g[_from].append(self._edge(_to, len(self.g[_to]), cap))
		self.g[_to].append(self._edge(_from, len(self.g[_from]) - 1, 0))
		return m

	class edge:

		def __init__(s, _from: int, _to: int, cap: int, flow: int):
			s._from = _from
			s._to = _to
			s.cap = cap
			s.flow = flow

	def get_edge(self, i: int) -> edge:
		m = len(self.pos)
		assert 0 <= i and i < m
		_e = self.g[self.pos[i][0]][self.pos[i][1]]
		_re = self.g[_e.to][_e.rev]
		return self.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap)

	def edges(self) -> list:
		m = len(self.pos)
		result = [self.get_edge(i) for i in range(m)]
		return result

	def change_edge(self, i: int, new_cap: int, new_flow: int):
		m = len(self.pos)
		assert 0 <= i and i < m
		assert 0 <= new_flow and new_flow <= new_cap
		_e = self.g[self.pos[i][0]][self.pos[i][1]]
		_re = self.g[_e.to][_e.rev]
		_e.cap = new_cap - new_flow
		_re.cap = new_flow

	def flow(self, s: int, t: int):
		return self.flow_(s, t, self.numeric_limits_max)

	def flow_(self, s: int, t: int, flow_limit: int) -> int:
		assert 0 <= s and s < self._n
		assert 0 <= t and t < self._n
		level = [0] * self._n
		it = [0] * self._n

		def bfs():
			for i in range(self._n):
				level[i] = -1
			level[s] = 0
			que = deque([s])
			while que:
				v = que.popleft()
				for e in self.g[v]:
					if e.cap == 0 or level[e.to] >= 0:
						continue
					level[e.to] = level[v] + 1
					if e.to == t:
						return
					que.append(e.to)

		def dfs(self_, v: int, up: int) -> int:
			if v == s:
				return up
			res = 0
			level_v = level[v]
			for i in range(it[v], len(self.g[v])):
				it[v] = i
				e = self.g[v][i]
				if level_v <= level[e.to] or self.g[e.to][e.rev].cap == 0:
					continue
				d = self_(self_, e.to, min(up - res, self.g[e.to][e.rev].cap))
				if d <= 0:
					continue
				self.g[v][i].cap += d
				self.g[e.to][e.rev].cap -= d
				res += d
				if res == up:
					break
			return res
		flow = 0
		while flow < flow_limit:
			bfs()
			if level[t] == -1:
				break
			for i in range(self._n):
				it[i] = 0
			while flow < flow_limit:
				f = dfs(dfs, t, flow_limit - flow)
				if not f:
					break
				flow += f
		return flow

	def min_cut(self, s: int) -> list:
		visited = [False] * self._n
		que = deque([s])
		while que:
			p = que.popleft()
			visited[p] = True
			for e in self.g[p]:
				if e.cap and (not visited[e.to]):
					visited[e.to] = True
					que.append(e.to)
		return visited

	class _edge:

		def __init__(s, to: int, rev: int, cap: int):
			s.to = to
			s.rev = rev
			s.cap = cap

class mcf_graph:
	numeric_limits_max = 10 ** 18

	def __init__(self, n: int):
		self._n = n
		self.g = [[] for _ in range(n)]
		self.pos = []

	def add_edge(self, _from: int, _to: int, cap: int, cost: int) -> int:
		assert 0 <= _from and _from < self._n
		assert 0 <= _to and _to < self._n
		m = len(self.pos)
		self.pos.append((_from, len(self.g[_from])))
		self.g[_from].append(self._edge(_to, len(self.g[_to]), cap, cost))
		self.g[_to].append(self._edge(_from, len(self.g[_from]) - 1, 0, -cost))
		return m

	class edge:

		def __init__(s, _from: int, _to: int, cap: int, flow: int, cost: int):
			s._from = _from
			s._to = _to
			s.cap = cap
			s.flow = flow
			s.cost = cost

	def get_edge(self, i: int) -> edge:
		m = len(self.pos)
		assert 0 <= i and i < m
		_e = self.g[self.pos[i][0]][self.pos[i][1]]
		_re = self.g[_e.to][_e.rev]
		return self.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap, _e.cost)

	def edges(self) -> list:
		m = len(self.pos)
		result = [self.get_edge(i) for i in range(m)]
		return result

	def flow(self, s: int, t: int) -> edge:
		return self.flow_(s, t, self.numeric_limits_max)

	def flow_(self, s: int, t: int, flow_limit: int) -> edge:
		return self.__slope(s, t, flow_limit)[-1]

	def slope(self, s: int, t: int) -> list:
		return self.slope_(s, t, self.numeric_limits_max)

	def slope_(self, s: int, t: int, flow_limit: int) -> list:
		return self.__slope(s, t, flow_limit)

	def __slope(self, s: int, t: int, flow_limit: int) -> list:
		assert 0 <= s and s < self._n
		assert 0 <= t and t < self._n
		assert s != t
		dual = [0] * self._n
		dist = [0] * self._n
		(pv, pe) = ([-1] * self._n, [-1] * self._n)
		vis = [False] * self._n

		def dual_ref():
			for i in range(self._n):
				dist[i] = self.numeric_limits_max
				pv[i] = -1
				pe[i] = -1
				vis[i] = False

			class Q:

				def __init__(s, key: int, to: int):
					s.key = key
					s.to = to

				def __lt__(s, r):
					return s.key < r.key
			que = []
			dist[s] = 0
			heappush(que, Q(0, s))
			while que:
				v = heappop(que).to
				if vis[v]:
					continue
				vis[v] = True
				if v == t:
					break
				for i in range(len(self.g[v])):
					e = self.g[v][i]
					if vis[e.to] or not e.cap:
						continue
					cost = e.cost - dual[e.to] + dual[v]
					if dist[e.to] - dist[v] > cost:
						dist[e.to] = dist[v] + cost
						pv[e.to] = v
						pe[e.to] = i
						heappush(que, Q(dist[e.to], e.to))
			if not vis[t]:
				return False
			for v in range(self._n):
				if not vis[v]:
					continue
				dual[v] -= dist[t] - dist[v]
			return True
		flow = 0
		cost = 0
		prev_cost = -1
		result = []
		result.append((flow, cost))
		while flow < flow_limit:
			if not dual_ref():
				break
			c = flow_limit - flow
			v = t
			while v != s:
				c = min(c, self.g[pv[v]][pe[v]].cap)
				v = pv[v]
			v = t
			while v != s:
				e = self.g[pv[v]][pe[v]]
				e.cap -= c
				self.g[v][e.rev].cap += c
				v = pv[v]
			d = -dual[s]
			flow += c
			cost += c * d
			if prev_cost == d:
				result.pop()
			result.append((flow, cost))
			prev_cost = cost
		return result

	class _edge:

		def __init__(s, to: int, rev: int, cap: int, cost: int):
			s.to = to
			s.rev = rev
			s.cap = cap
			s.cost = cost

class Mint:
	modint1000000007 = 1000000007
	modint998244353 = 998244353

	def __init__(self, v: int=0):
		self.m = self.modint1000000007
		self.x = v % self.__umod()

	def inv(self):
		if is_prime_constexpr(self.__umod()):
			assert self.x
			return self.pow_(self.__umod() - 2)
		else:
			eg = inv_gcd(self.x, self.m)
			assert eg[0] == 1
			return eg[2]

	def __str__(self):
		return str(self.x)

	def __le__(self, other):
		return self.x <= Mint.__get_val(other)

	def __lt__(self, other):
		return self.x < Mint.__get_val(other)

	def __ge__(self, other):
		return self.x >= Mint.__get_val(other)

	def __gt(self, other):
		return self.x > Mint.__get_val(other)

	def __eq__(self, other):
		return self.x == Mint.__get_val(other)

	def __iadd__(self, other):
		self.x += Mint.__get_val(other)
		if self.x >= self.__umod():
			self.x -= self.__umod()
		return self

	def __add__(self, other):
		_v = Mint(self.x)
		_v += other
		return _v

	def __isub__(self, other):
		self.x -= Mint.__get_val(other)
		if self.x >= self.__umod():
			self.x += self.__umod()
		return self

	def __sub__(self, other):
		_v = Mint(self.x)
		_v -= other
		return _v

	def __rsub__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v -= self
		return _v

	def __imul__(self, other):
		self.x = self.x * Mint.__get_val(other) % self.__umod()
		return self

	def __mul__(self, other):
		_v = Mint(self.x)
		_v *= other
		return _v

	def __itruediv__(self, other):
		self.x = self.x / Mint.__get_val(other) % self.__umod()
		return self

	def __truediv__(self, other):
		_v = Mint(self.x)
		_v /= other
		return _v

	def __rtruediv__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v /= self
		return _v

	def __ifloordiv__(self, other):
		other = other if isinstance(other, Mint) else Mint(other)
		self *= other.inv()
		return self

	def __floordiv__(self, other):
		_v = Mint(self.x)
		_v //= other
		return _v

	def __rfloordiv__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v //= self
		return _v

	def __pow__(self, other):
		_v = Mint(pow(self.x, Mint.__get_val(other), self.__umod()))
		return _v

	def __rpow__(self, other):
		_v = Mint(pow(Mint.__get_val(other), self.x, self.__umod()))
		return _v

	def __imod__(self, other):
		self.x %= Mint.__get_val(other)
		return self

	def __mod__(self, other):
		_v = Mint(self.x)
		_v %= other
		return _v

	def __rmod__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v %= self
		return _v

	def __ilshift__(self, other):
		self.x <<= Mint.__get_val(other)
		return self

	def __irshift__(self, other):
		self.x >>= Mint.__get_val(other)
		return self

	def __lshift__(self, other):
		_v = Mint(self.x)
		_v <<= other
		return _v

	def __rshift__(self, other):
		_v = Mint(self.x)
		_v >>= other
		return _v

	def __rlshift__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v <<= self
		return _v

	def __rrshift__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v >>= self
		return _v
	__repr__ = __str__
	__radd__ = __add__
	__rmul__ = __mul__

	def __umod(self):
		return self.m

	@staticmethod
	def __get_val(val):
		return val.x if isinstance(val, Mint) else val

	def pow_(self, n: int):
		assert 0 <= n
		x = Mint(self.x)
		r = 1
		while n:
			if n & 1:
				r *= x
			x *= x
			n >>= 1
		return r

	def val(self):
		return self.x

	def mod(self):
		return self.m

	def raw(self, v):
		x = Mint()
		x.x = v
		return x

class scc_graph_sub:

	def __init__(self, n):
		self.internal = scc_graph(n)

	def add_edge(self, _from, _to):
		n = self.internal.num_vertices()
		assert 0 <= _from and _from < n
		assert 0 <= _to and _to < n
		self.internal.add_edge(_from, _to)

	def scc(self):
		return self.internal.scc()

class segtree:

	def __init__(self, op, e, v: list):
		self._n = len(v)
		self.log = ceil_pow2(self._n)
		self.size = 1 << self.log
		self.op = op
		self.e = e
		self.d = [self.e()] * (self.size * 2)
		for i in range(self._n):
			self.d[self.size + i] = v[i]
		for i in range(self.size - 1, 0, -1):
			self.__update(i)

	def set_(self, p: int, x: int):
		assert 0 <= p and p < self._n
		p += self.size
		self.d[p] = x
		for i in range(1, self.log + 1):
			self.__update(p >> i)

	def get(self, p: int):
		assert 0 <= p and p < self._n
		return self.d[p + self.size]

	def prod(self, l: int, r: int):
		assert 0 <= l and l <= r and (r <= self._n)
		l += self.size
		r += self.size
		(sml, smr) = (self.e(), self.e())
		while l < r:
			if l & 1:
				sml = self.op(sml, self.d[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.d[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def all_prod(self):
		return self.d[1]

	def max_right(self, l: int, f):
		assert 0 <= l and l <= self._n
		assert f(self.e())
		if l == self._n:
			return self._n
		l += self.size
		sm = self.e()
		while True:
			while l % 2 == 0:
				l >>= 1
			if not f(self.op(sm, self.d[l])):
				while l < self.size:
					l = 2 * l
					if f(self.op(sm, self.d[l])):
						sm = self.op(sm, self.d[l])
						l += 1
				return l - self.size
			sm = self.op(sm, self.d[l])
			l += 1
			if l & -l == l:
				break
		return self._n

	def min_left(self, r: int, f):
		assert 0 <= r and r <= self._n
		assert f(self.e())
		if r == 0:
			return 0
		r += self.size
		sm = self.e()
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not f(self.op(self.d[r], sm)):
				while r < self.size:
					r = 2 * r + 1
					if f(self.op(self.d[r], sm)):
						sm = self.op(self.d[r], sm)
						r -= 1
				return r + 1 - self.size
			sm = self.op(self.d[r], sm)
			if r & -r == r:
				break
		return 0

	def __update(self, k: int):
		self.d[k] = self.op(self.d[k * 2], self.d[k * 2 + 1])

def sa_native(s: list):
	from functools import cmp_to_key

	def mycmp(r, l):
		if l == r:
			return -1
		while l < n and r < n:
			if s[l] != s[r]:
				return 1 if s[l] < s[r] else -1
			l += 1
			r += 1
		return 1 if l == n else -1
	n = len(s)
	sa = [i for i in range(n)]
	sa.sort(key=cmp_to_key(mycmp))
	return sa

def sa_doubling(s: list):
	from functools import cmp_to_key

	def mycmp(y, x):
		if rnk[x] != rnk[y]:
			return 1 if rnk[x] < rnk[y] else -1
		rx = rnk[x + k] if x + k < n else -1
		ry = rnk[y + k] if y + k < n else -1
		return 1 if rx < ry else -1
	n = len(s)
	sa = [i for i in range(n)]
	rnk = s
	tmp = [0] * n
	k = 1
	while k < n:
		sa.sort(key=cmp_to_key(mycmp))
		tmp[sa[0]] = 0
		for i in range(1, n):
			tmp[sa[i]] = tmp[sa[i - 1]]
			if mycmp(sa[i], sa[i - 1]) == 1:
				tmp[sa[i]] += 1
		(tmp, rnk) = (rnk, tmp)
		k *= 2
	return sa

def sa_is(s: list, upper: int):
	THRESHOLD_NATIVE = 10
	THRESHOLD_DOUBLING = 40
	n = len(s)
	if n == 0:
		return []
	if n == 1:
		return [0]
	if n == 2:
		if s[0] < s[1]:
			return [0, 1]
		else:
			return [1, 0]
	if n < THRESHOLD_NATIVE:
		return sa_native(s)
	if n < THRESHOLD_DOUBLING:
		return sa_doubling(s)
	sa = [0] * n
	ls = [False] * n
	for i in range(n - 2, -1, -1):
		ls[i] = ls[i + 1] if s[i] == s[i + 1] else s[i] < s[i + 1]
	sum_l = [0] * (upper + 1)
	sum_s = [0] * (upper + 1)
	for i in range(n):
		if not ls[i]:
			sum_s[s[i]] += 1
		else:
			sum_l[s[i] + 1] += 1
	for i in range(upper + 1):
		sum_s[i] += sum_l[i]
		if i < upper:
			sum_l[i + 1] += sum_s[i]

	def induce(lms: list):
		from copy import copy
		for i in range(n):
			sa[i] = -1
		buf = [0] * (upper + 1)
		buf = copy(sum_s)
		for d in lms:
			if d == n:
				continue
			sa[buf[s[d]]] = d
			buf[s[d]] += 1
		buf = copy(sum_l)
		sa[buf[s[n - 1]]] = n - 1
		buf[s[n - 1]] += 1
		for i in range(n):
			v = sa[i]
			if v >= 1 and (not ls[v - 1]):
				sa[buf[s[v - 1]]] = v - 1
				buf[s[v - 1]] += 1
		buf = copy(sum_l)
		for i in range(n - 1, -1, -1):
			v = sa[i]
			if v >= 1 and ls[v - 1]:
				buf[s[v - 1] + 1] -= 1
				sa[buf[s[v - 1] + 1]] = v - 1
	lms_map = [-1] * (n + 1)
	m = 0
	for i in range(1, n):
		if not ls[i - 1] and ls[i]:
			lms_map[i] = m
			m += 1
	lms = [i for i in range(1, n) if not ls[i - 1] and ls[i]]
	induce(lms)
	if m:
		sorted_lms = [v for v in sa if lms_map[v] != -1]
		rec_s = [0] * m
		rec_upper = 0
		rec_s[lms_map[sorted_lms[0]]] = 0
		for i in range(1, m):
			l = sorted_lms[i - 1]
			r = sorted_lms[i]
			end_l = lms[lms_map[l] + 1] if lms_map[l] + 1 < m else n
			end_r = lms[lms_map[r] + 1] if lms_map[r] + 1 < m else n
			same = True
			if end_l - l != end_r - r:
				same = False
			else:
				while l < end_l:
					if s[l] != s[r]:
						break
					l += 1
					r += 1
				if l == n or s[l] != s[r]:
					same = False
			if not same:
				rec_upper += 1
			rec_s[lms_map[sorted_lms[i]]] = rec_upper
		rec_sa = sa_is(rec_s, rec_upper)
		for i in range(m):
			sorted_lms[i] = lms[rec_sa[i]]
		induce(sorted_lms)
	return sa

def suffix_array(s: list, upper: int):
	assert 0 <= upper
	for d in s:
		assert 0 <= d and d <= upper
	sa = sa_is(s, upper)
	return sa

def suffix_array2(s: list):
	from functools import cmp_to_key
	n = len(s)
	idx = [i for i in range(n)]
	idx.sort(key=cmp_to_key(lambda l, r: s[l] < s[r]))
	s2 = [0] * n
	now = 0
	for i in range(n):
		if i and s[idx[i - 1]] != s[idx[i]]:
			now += 1
		s2[idx[i]] = now
	return sa_is(s2, now)

def suffix_array3(s: str):
	n = len(s)
	s2 = list(map(ord, s))
	return sa_is(s2, 255)

def lcp_array(s: list, sa: list):
	n = len(s)
	assert n >= 1
	rnk = [0] * n
	for i in range(n):
		rnk[sa[i]] = i
	lcp = [0] * (n - 1)
	h = 0
	for i in range(n):
		if h > 0:
			h -= 1
		if rnk[i] == 0:
			continue
		j = sa[rnk[i] - 1]
		while j + h < n and i + h < n:
			if s[j + h] != s[i + h]:
				break
			h += 1
		lcp[rnk[i] - 1] = h
	return lcp

def lcp_array2(s: str, sa: list):
	n = len(s)
	s2 = list(map(ord, s))
	return lcp_array(s2, sa)

def z_algorithm(s: list):
	n = len(s)
	if n == 0:
		return []
	z = [-1] * n
	z[0] = 0
	j = 0
	for i in range(1, n):
		k = z[i] = 0 if j + z[j] <= i else min(j + z[j] - i, z[i - j])
		while i + k < n and s[k] == s[i + k]:
			k += 1
		z[i] = k
		if j + z[j] < i + z[i]:
			j = i
	z[0] = n
	return z

def z_algorithm2(s: str):
	n = len(s)
	s2 = list(map(ord, s))
	return z_algorithm(s2)

class two_sat:

	def __init__(self, n: int):
		self._n = n
		self.scc = scc_graph(2 * n)
		self._answer = [False] * n

	def add_clause(self, i: int, f: bool, j: int, g: bool):
		assert 0 <= i and i < self._n
		assert 0 <= j and j < self._n
		self.scc.add_edge(2 * i + (not f), 2 * j + g)
		self.scc.add_edge(2 * j + (not g), 2 * i + f)

	def satisfiable(self) -> bool:
		_id = self.scc.scc_ids()[1]
		for i in range(self._n):
			if _id[2 * i] == _id[2 * i + 1]:
				return False
			self._answer[i] = _id[2 * i] < _id[2 * i + 1]
		return True

	def answer(self):
		return self._answer
import sys
sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.141592653589793

def read_str():
	return sys.stdin.readline().strip()

def read_int():
	return int(sys.stdin.readline().strip())

def read_ints():
	return map(int, sys.stdin.readline().strip().split())

def read_ints2(x):
	return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())

def read_str_list():
	return list(sys.stdin.readline().strip().split())

def read_int_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def GCD(a: int, b: int) -> int:
	return b if a % b == 0 else GCD(b, a % b)

def LCM(a: int, b: int) -> int:
	return a * b // GCD(a, b)

def Main_A():
	(n, q) = read_ints()
	d = dsu(n)
	for _ in range(q):
		(t, u, v) = read_ints()
		if t == 0:
			d.merge(u, v)
		else:
			print(int(d.same(u, v)))

def Main_B():
	(n, q) = read_ints()
	a = read_int_list()
	fw = fenwick_tree(n)
	for (i, x) in enumerate(a):
		fw.add(i, x)
	for _ in range(q):
		query = read_int_list()
		if query[0] == 0:
			fw.add(query[1], query[2])
		else:
			print(fw.sum(query[1], query[2]))

def Main_C():
	for _ in range(read_int()):
		(n, m, a, b) = read_ints()
		print(floor_sum(n, m, a, b))

def Main_D():
	(n, m) = read_ints()
	grid = [list(read_str()) for _ in range(n)]
	mf = mf_graph(n * m + 2)
	start = n * m
	end = start + 1
	dir = [(1, 0), (0, 1)]
	for y in range(n):
		for x in range(m):
			if (y + x) % 2 == 0:
				mf.add_edge(start, m * y + x, 1)
			else:
				mf.add_edge(m * y + x, end, 1)
			if grid[y][x] == '.':
				for (dy, dx) in dir:
					ny = y + dy
					nx = x + dx
					if ny < n and nx < m and (grid[ny][nx] == '.'):
						(f, t) = (y * m + x, ny * m + nx)
						if (y + x) % 2:
							(f, t) = (t, f)
						mf.add_edge(f, t, 1)
	ans = mf.flow(start, end)
	for y in range(n):
		for x in range(m):
			for e in mf.g[y * m + x]:
				(to, rev, cap) = (e.to, e.rev, e.cap)
				(ny, nx) = divmod(to, m)
				if (y + x) % 2 == 0 and cap == 0 and (to != start) and (to != end) and (y * m + x != start) and (y * m + x != end):
					if y + 1 == ny:
						grid[y][x] = 'v'
						grid[ny][nx] = '^'
					elif y == ny + 1:
						grid[y][x] = '^'
						grid[ny][nx] = 'v'
					elif x + 1 == nx:
						grid[y][x] = '>'
						grid[ny][nx] = '<'
					elif x == nx + 1:
						grid[y][x] = '<'
						grid[ny][nx] = '>'
	print(ans)
	print(*[''.join(ret) for ret in grid], sep='\n')

def Main_E():
	(n, k) = read_ints()
	a = [read_int_list() for _ in range(n)]
	mcf = mcf_graph(n * 2 + 2)
	s = n * 2
	t = n * 2 + 1
	for i in range(n):
		mcf.add_edge(s, i, k, 0)
		mcf.add_edge(i + n, t, k, 0)
	mcf.add_edge(s, t, n * k, INF)
	for i in range(n):
		for j in range(n):
			mcf.add_edge(i, n + j, 1, INF - a[i][j])
	result = mcf.flow_(s, t, n * k)
	print(n * k * INF - result[1])
	grid = [['.'] * n for _ in range(n)]
	edges = mcf.edges()
	for e in edges:
		if e._from == s or e._to == t or e.flow == 0:
			continue
		grid[e._from][e._to - n] = 'X'
	print(*[''.join(g) for g in grid], sep='\n')

def Main_F():
	MOD = 998244353
	(n, m) = read_ints()
	a = read_int_list()
	b = read_int_list()
	a = [x % MOD for x in a]
	b = [x % MOD for x in b]
	cnv = convolution(a, b, MOD)
	ans = cnv.convolution()
	print(*ans)

def Main_G():
	sys.setrecursionlimit(10 ** 6)
	(n, m) = read_ints()
	scc = scc_graph(n)
	for _ in range(m):
		(a, b) = read_ints()
		scc.add_edge(a, b)
	ans = scc.scc()
	print(len(ans))
	for v in ans:
		print(len(v), ' '.join(map(str, v[::-1])))

def Main_H():
	(n, d) = read_ints()
	xy = [read_int_list() for _ in range(n)]
	tw = two_sat(n)
	for i in range(n):
		for j in range(i + 1, n):
			for x in range(2):
				if abs(xy[i][0] - xy[j][0]) < d:
					tw.add_clause(i, False, j, False)
				if abs(xy[i][0] - xy[j][1]) < d:
					tw.add_clause(i, False, j, True)
				if abs(xy[i][1] - xy[j][0]) < d:
					tw.add_clause(i, True, j, False)
				if abs(xy[i][1] - xy[j][1]) < d:
					tw.add_clause(i, True, j, True)
	if not tw.satisfiable():
		print('No')
		exit()
	print('Yes')
	ans = tw.answer()
	for (i, flag) in enumerate(ans):
		print(xy[i][0] if flag else xy[i][1])

def Main_I():
	s = read_str()
	sa = suffix_array3(s)
	ans = len(s) * (len(s) + 1) // 2
	for x in lcp_array2(s, sa):
		ans -= x
	print(ans)

def Main_J():

	def op(l, r):
		return max(l, r)

	def e():
		return -1

	def f(n):
		return n < r
	(n, q) = read_ints()
	a = read_int_list()
	seg = segtree(op, e, a)
	query = [read_ints() for _ in range(q)]
	for i in range(q):
		(t, l, r) = query[i]
		if t == 1:
			seg.set_(~-l, r)
		elif t == 2:
			print(seg.prod(~-l, r))
		else:
			print(seg.max_right(~-l, f) + 1)

def Main_K():
	p = 998244353

	def op(l, r):
		(l1, l2) = (l >> 32, l % (1 << 32))
		(r1, r2) = (r >> 32, r % (1 << 32))
		return ((l1 + r1) % p << 32) + l2 + r2

	def e():
		return 0

	def mapping(l, r):
		(l1, l2) = (l >> 32, l % (1 << 32))
		(r1, r2) = (r >> 32, r % (1 << 32))
		return ((l1 * r1 + l2 * r2) % p << 32) + r2

	def composition(l, r):
		(l1, l2) = (l >> 32, l % (1 << 32))
		(r1, r2) = (r >> 32, r % (1 << 32))
		return (l1 * r1 % p << 32) + (l1 * r2 + l2) % p

	def id():
		return 1 << 32
	(n, q) = read_ints()
	A = read_int_list()
	A = [(x << 32) + 1 for x in A]
	seg = lazy_segtree(op, e, mapping, composition, id, A)
	ans = []
	for _ in range(q):
		query = read_int_list()
		if query[0] == 0:
			(l, r, b, c) = query[1:]
			seg.apply(l, r, (b << 32) + c)
		else:
			(l, r) = query[1:]
			print(seg.prod(l, r) >> 32)

def Main_L():

	def op(l: tuple, r: tuple):
		return (l[0] + r[0], l[1] + r[1], l[2] + r[2] + l[1] * r[0])

	def e():
		return (0, 0, 0)

	def mapping(l: bool, r: tuple):
		if not l:
			return r
		return (r[1], r[0], r[1] * r[0] - r[2])

	def composition(l: bool, r: bool):
		return l ^ r

	def id():
		return False
	(n, q) = read_ints()
	A = read_int_list()
	query = [read_ints() for _ in range(q)]
	a = [(1, 0, 0) if i == 0 else (0, 1, 0) for i in A]
	seg = lazy_segtree(op, e, mapping, composition, id, a)
	for (t, l, r) in query:
		if t == 1:
			seg.apply(~-l, r, True)
		else:
			print(seg.prod(~-l, r)[2])
Main_K()


import sys
sys.setrecursionlimit(10 ** 6)
INF = 10 ** 9 + 1
MOD = 998244353

def set_depth(depth):
	global DEPTH, SEGTREE_SIZE, NONLEAF_SIZE
	DEPTH = depth
	SEGTREE_SIZE = 1 << DEPTH
	NONLEAF_SIZE = 1 << DEPTH - 1

def set_width(width):
	set_depth((width - 1).bit_length() + 1)

def get_size(pos):
	ret = pos.bit_length()
	return 1 << DEPTH - ret

def up(pos):
	pos += SEGTREE_SIZE // 2
	return pos // (pos & -pos)

def up_propagate(table, pos, binop):
	while pos > 1:
		pos >>= 1
		table[pos] = binop(table[pos * 2], table[pos * 2 + 1])

def full_up(table, binop):
	for i in range(NONLEAF_SIZE - 1, 0, -1):
		table[i] = binop(table[2 * i], table[2 * i + 1])

def force_down_propagate(action_table, value_table, pos, action_composite, action_force, action_unity):
	max_level = pos.bit_length() - 1
	size = NONLEAF_SIZE
	for level in range(max_level):
		size //= 2
		i = pos >> max_level - level
		action = action_table[i]
		if action != action_unity:
			action_table[i * 2] = action_composite(action, action_table[i * 2])
			action_table[i * 2 + 1] = action_composite(action, action_table[i * 2 + 1])
			action_table[i] = action_unity
			value_table[i * 2] = action_force(action, value_table[i * 2], size)
			value_table[i * 2 + 1] = action_force(action, value_table[i * 2 + 1], size)

def force_range_update(value_table, action_table, left, right, action, action_force, action_composite, action_unity):
	left += NONLEAF_SIZE
	right += NONLEAF_SIZE
	while left < right:
		if left & 1:
			value_table[left] = action_force(action, value_table[left], get_size(left))
			action_table[left] = action_composite(action, action_table[left])
			left += 1
		if right & 1:
			right -= 1
			value_table[right] = action_force(action, value_table[right], get_size(right))
			action_table[right] = action_composite(action, action_table[right])
		left //= 2
		right //= 2

def range_reduce(table, left, right, binop, unity):
	ret_left = unity
	ret_right = unity
	left += NONLEAF_SIZE
	right += NONLEAF_SIZE
	while left < right:
		if left & 1:
			ret_left = binop(ret_left, table[left])
			left += 1
		if right & 1:
			right -= 1
			ret_right = binop(table[right], ret_right)
		left //= 2
		right //= 2
	return binop(ret_left, ret_right)

def lazy_range_update(action_table, value_table, start, end, action, action_composite, action_force, action_unity, value_binop):
	L = up(start)
	R = up(end)
	force_down_propagate(action_table, value_table, L, action_composite, action_force, action_unity)
	force_down_propagate(action_table, value_table, R, action_composite, action_force, action_unity)
	force_range_update(value_table, action_table, start, end, action, action_force, action_composite, action_unity)
	up_propagate(value_table, L, value_binop)
	up_propagate(value_table, R, value_binop)

def lazy_range_reduce(action_table, value_table, start, end, action_composite, action_force, action_unity, value_binop, value_unity):
	force_down_propagate(action_table, value_table, up(start), action_composite, action_force, action_unity)
	force_down_propagate(action_table, value_table, up(end), action_composite, action_force, action_unity)
	return range_reduce(value_table, start, end, value_binop, value_unity)

def debug(*x):
	print(*x, file=sys.stderr)

def main():
	(N, Q) = map(int, input().split())
	AS = list(map(int, input().split()))
	set_width(N + 1)
	value_unity = 0
	value_table = [value_unity] * SEGTREE_SIZE
	value_table[NONLEAF_SIZE:NONLEAF_SIZE + len(AS)] = AS
	action_unity = None
	action_table = [action_unity] * SEGTREE_SIZE

	def action_force(action, value, size):
		if action == action_unity:
			return value
		b = action >> 32
		c = action - (b << 32)
		return (value * b + c * size) % MOD

	def action_composite(new_action, old_action):
		if new_action == action_unity:
			return old_action
		if old_action == action_unity:
			return new_action
		b1 = old_action >> 32
		c1 = old_action - (b1 << 32)
		b2 = new_action >> 32
		c2 = new_action - (b2 << 32)
		b = b1 * b2 % MOD
		c = (b2 * c1 + c2) % MOD
		return (b << 32) + c

	def value_binop(a, b):
		return (a + b) % MOD
	full_up(value_table, value_binop)
	for _q in range(Q):
		(q, *args) = map(int, input().split())
		if q == 0:
			(l, r, b, c) = args
			lazy_range_update(action_table, value_table, l, r, (b << 32) + c, action_composite, action_force, action_unity, value_binop)
		else:
			(l, r) = args
			print(lazy_range_reduce(action_table, value_table, l, r, action_composite, action_force, action_unity, value_binop, value_unity))
T1 = '\n5 7\n1 2 3 4 5\n1 0 5\n0 2 4 100 101\n1 0 3\n0 1 3 102 103\n1 2 5\n0 2 5 104 105\n1 0 5\n'
TEST_T1 = '\n>>> as_input(T1)\n>>> main()\n15\n404\n41511\n4317767\n'

def _test():
	import doctest
	doctest.testmod()
	g = globals()
	for k in sorted(g):
		if k.startswith('TEST_'):
			doctest.run_docstring_examples(g[k], g, name=k)

def as_input(s):
	import io
	f = io.StringIO(s.strip())
	g = globals()
	g['input'] = lambda : bytes(f.readline(), 'ascii')
	g['read'] = lambda : bytes(f.read(), 'ascii')
input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
if sys.argv[-1] == '-t':
	print('testing')
	_test()
	sys.exit()
main()


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)

	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

	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)


from typing import Callable, List, TypeVar
S = TypeVar('S')
F = TypeVar('F')

class LazySegmentTree:
	__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:
		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:
		assert 0 <= k < self._n
		k += self._size
		for i in range(self._log, 0, -1):
			self._push(k >> i)
		self.tree[k] = x
		for i in range(1, self._log + 1):
			self._update(k >> i)

	def get(self, k: int) -> S:
		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:
		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 self.tree[1]

	def apply(self, k: int, f: F) -> None:
		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:
		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)
mod = 998244353

def op(l, r):
	(l1, l2) = (l >> 32, l % (1 << 32))
	(r1, r2) = (r >> 32, r % (1 << 32))
	return ((l1 + r1) % mod << 32) + l2 + r2

def mapping(f, x):
	(f1, f2) = (f >> 32, f % (1 << 32))
	(x1, x2) = (x >> 32, x % (1 << 32))
	return ((f1 * x1 + f2 * x2) % mod << 32) + x2

def composition(l, r):
	(l1, l2) = (l >> 32, l % (1 << 32))
	(r1, r2) = (r >> 32, r % (1 << 32))
	return (l1 * r1 % mod << 32) + (r2 * l1 + l2) % mod
(N, Q) = map(int, input().split())
a = list(map(int, input().split()))
lst = LazySegmentTree([(v << 32) + 1 for v in a], 0, op, 1 << 32, mapping, composition)
for i in range(Q):
	(q, *p) = map(int, input().split())
	if q == 0:
		lst.apply_range(p[0], p[1], (p[2] << 32) + p[3])
	else:
		print(lst.prod(*p) >> 32)


import sys
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.141592653589793
p = 998244353

def read_str():
	return sys.stdin.readline().strip()

def read_int():
	return int(sys.stdin.readline().strip())

def read_ints():
	return map(int, sys.stdin.readline().strip().split())

def read_ints2(x):
	return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())

def read_str_list():
	return list(sys.stdin.readline().strip().split())

def read_int_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def GCD(a: int, b: int) -> int:
	return b if a % b == 0 else GCD(b, a % b)

def LCM(a: int, b: int) -> int:
	return a * b // GCD(a, b)

class lazy_segtree:

	def __init__(self, op, e, mapping, composition, id, v: list):
		self.op = op
		self.e = e
		self.mapping = mapping
		self.composition = composition
		self.id = id
		self._n = len(v)
		self.log = self.__ceil_pow2(self._n)
		self.size = 1 << self.log
		self.lz = [self.id()] * self.size
		self.d = [self.e()] * (2 * self.size)
		for i in range(self._n):
			self.d[self.size + i] = v[i]
		for i in range(self.size - 1, 0, -1):
			self.__update(i)

	def set_(self, p: int, x: int):
		assert 0 <= p and p < self._n
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		self.d[p] = x
		for i in range(1, self.log + 1):
			self.__update(p >> 1)

	def get(self, p: int):
		assert 0 <= p and p < self._n
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		return self.d[p]

	def prod(self, l: int, r: int):
		assert 0 <= l and l <= r and (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.d[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.d[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def all_prod(self):
		return self.d[1]

	def apply(self, p: int, f):
		assert 0 <= p and p < self._n
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		self.d[p] = self.mapping(f, self.d[p])
		for i in range(1, self.log + 1):
			self.__update(p >> 1)

	def apply(self, l: int, r: int, f):
		assert 0 <= l and l <= r and (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)
		(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 >> i)

	def max_right(self, l: int, g):
		assert 0 <= l and l <= self._n
		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 l % 2 == 0:
				l >>= 1
			if not g(self.op(sm, self.d[l])):
				while l < self.size:
					self.__push(l)
					l = 2 * l
					if g(self.op(sm, self.d[l])):
						sm = self.op(sm, self.d[l])
						l += 1
				return l - self.size
			sm = self.op(sm, self.d[l])
			l += 1
			if l & -l != l:
				break
		return self._n

	def min_left(self, r: int, g):
		assert 0 <= r and r <= self._n
		if r == 0:
			return 0
		r += self.size
		for i in range(self.log, 0, -1):
			self.__push(r >> i)
		sm = self.e()
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not g(self.op(self.d[r], sm)):
				while r < self.size:
					self.__push(r)
					r = 2 * r + 1
					if g(self.op(self.d[r], sm)):
						sm = self.op(self.d[r], sm)
						r += 1
				return r + 1 - self.size
			sm = self.op(self.d[r], sm)
			if r & -r != r:
				break
		return 0

	def __update(self, k: int):
		self.d[k] = self.op(self.d[k * 2], self.d[k * 2 + 1])

	def __all_apply(self, k: int, f):
		self.d[k] = self.mapping(f, self.d[k])
		if k < self.size:
			self.lz[k] = self.composition(f, self.lz[k])

	def __push(self, k: int):
		self.__all_apply(2 * k, self.lz[k])
		self.__all_apply(2 * k + 1, self.lz[k])
		self.lz[k] = self.id()

	def __ceil_pow2(self, n: int) -> int:
		x = 0
		while 1 << x < n:
			x += 1
		return x

def op(l, r):
	(l1, l2) = (l >> 32, l % (1 << 32))
	(r1, r2) = (r >> 32, r % (1 << 32))
	return ((l1 + r1) % p << 32) + l2 + r2

def e():
	return 0

def mapping(l, r):
	(l1, l2) = (l >> 32, l % (1 << 32))
	(r1, r2) = (r >> 32, r % (1 << 32))
	return ((l1 * r1 + l2 * r2) % p << 32) + r2

def composition(l, r):
	(l1, l2) = (l >> 32, l % (1 << 32))
	(r1, r2) = (r >> 32, r % (1 << 32))
	return (l1 * r1 % p << 32) + (l1 * r2 + l2) % p

def id():
	return 1 << 32

def Main():
	(n, q) = read_ints()
	A = read_int_list()
	A = [(x << 32) + 1 for x in A]
	seg = lazy_segtree(op, e, mapping, composition, id, A)
	ans = []
	for _ in range(q):
		query = read_int_list()
		if query[0] == 0:
			(l, r, b, c) = query[1:]
			seg.apply(l, r, (b << 32) + c)
		else:
			(l, r) = query[1:]
			print(seg.prod(l, r) >> 32)
Main()