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

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

Constraints

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

Input

Input is given from Standard Input in the following format:


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


Output

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

Example

Input

5 7
1 2 3 4 5
1 0 5
0 2 4 100 101
1 0 3
0 1 3 102 103
1 2 5
0 2 5 104 105
1 0 5


Output

15
404
41511
4317767

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define mul(a, b) (a = 1ll * a * b % mod)
#define add(a, b) (a += b, a >= mod ? a -= mod : 0)
using namespace std;

const int mod = 998244353;

struct node {
	int sum, b, c;
	node *son[2];
	node(): b(1), c(0) {}
} *root, pool[1048576 + 10];

int idx;
int n, q;
int a[524288 + 10];
void build(node*, const int&, const int&);
int query(node*, const int&, const int&, const int&, const int&);
void modify(node*, const int&, const int&, const int&, const int&, const int&, const int&);
void update(node*, const int&);

int main() {
	scanf("%d%d", &n, &q);
	for (int i = 0; i < n; ++i)
		scanf("%d", &a[i]);
	n = 1 << 32 - __builtin_clz(n - 1);
	build(root = &pool[idx++], 0, n);
	while (q--) {
		int f, l, r; scanf("%d%d%d", &f, &l, &r);
		if (f)
			printf("%d\n", query(root, l, r, 0, n));
		else {
			int b, c; scanf("%d%d", &b, &c);
			modify(root, l, r, 0, n, b, c);
		}
	}
	return 0;
}

void build(node *p, const int& l, const int& r) {
	if (l + 1 == r)
		p->son[0] = p->son[1] = nullptr,
			p->sum = a[l];
	else {
		const int mid = l + r >> 1;
		build(p->son[0] = &pool[idx++], l, mid);
		build(p->son[1] = &pool[idx++], mid, r);
		p->sum = p->son[1]->sum;
		add(p->sum, p->son[0]->sum);
	}
}

int query(node *p, const int &l, const int &r, const int &L, const int &R) {
	update(p, R - L);
	if (l == L && r == R)
		return p->sum;
	const int mid = L + R >> 1;
	if (r <= mid)
		return query(p->son[0], l, r, L, mid);
	else if (l >= mid)
		return query(p->son[1], l, r, mid, R);
	else {
		int ret = query(p->son[0], l, mid, L, mid);
		add(ret, query(p->son[1], mid, r, mid, R));
		return ret;
	}
}

inline void update(node *p, const int &siz) {
	if (p->b != 1) {
		mul(p->sum, p->b);
		if (siz > 1)
			mul(p->son[0]->b, p->b), mul(p->son[1]->b, p->b),
				mul(p->son[0]->c, p->b), mul(p->son[1]->c, p->b);
		p->b = 1;
	}
	if (p->c != 0) {
		p->sum = (p->sum + 1ll * p->c * siz) % mod;
		if (siz > 1)
			add(p->son[0]->c, p->c), add(p->son[1]->c, p->c);
		p->c = 0;
	}
}

void modify(node *p, const int &l, const int &r, const int &L, const int &R, const int &b, const int &c) {
	update(p, R - L);
	if (l == L && r == R) {
		p->b = b, p->c = c;
		update(p, R - L);
		return;
	}
	const int mid = L + R >> 1;
	if (r <= mid)
		modify(p->son[0], l, r, L, mid, b, c);
	else if (l >= mid)
		modify(p->son[1], l, r, mid, R, b, c);
	else {
		modify(p->son[0], l, mid, L, mid, b, c);
		modify(p->son[1], mid, r, mid, R, b, c);
	}
	update(p->son[0], R - L >> 1); update(p->son[1], R - L >> 1);
	p->sum = p->son[0]->sum + p->son[1]->sum;
	if (p->sum >= mod)
		p->sum -= mod;
}