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:
//#pragma warning(disable:4996)
//#include <Windows.h>
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>
#include <bitset>
//#include <stdio.h>

//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 998244353;
const long long INF = 1e18;
typedef long long LL;
typedef long double LD;
//typedef boost::multiprecision::cpp_int bigint;
typedef pair<LL, LL> PLL;
typedef pair<int, int> PI;
typedef pair<LD, LL> pdl;
typedef pair<LD, LD> pdd;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef unsigned long long ULL;
template<class T>
using pqueue = priority_queue<T, vector<T>, function<bool(T, T)>>;

template<class T>
inline void chmin(T& a, T b) {
	a = min(a, b);
}

template<class T>
inline void chmax(T& a, T b) {
	a = max(a, b);
}

void input();
void solve();

void daminput();
void naive();

void outputinput();

int main() {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	input();
	//daminput();
	solve();
	//naive();
	//outputinput();
	return 0;
}

//////////////////////////////////////////////////
//////////////////////////////////////////////////

int N, Q;
VLL A;
VVLL query;

void input() {
	cin >> N >> Q;
	A.resize(N);
	for (int n = 0; n < N; n++)cin >> A[n];
	query.resize(Q);
	for (int q = 0; q < Q; q++) {
		query[q].resize(5);
		cin >> query[q][0];
		if (query[q][0] == 0) {
			cin >> query[q][1] >> query[q][2]
				>> query[q][3] >> query[q][4];
		}
		else {
			cin >> query[q][1] >> query[q][2];
		}
	}
}

void daminput() {
}

//TT(T,T):=モノイドの乗算
//MT(M,T,LL):=モノイドに対する左作用(第3項は要素数)
//MM(M,M):=左作用の合成
template<class T, class M>
class LazySegtree {
public:
	vector<T> seg;
	vector<M> lazy;   //実、更新の必要性
	typedef function<T(T, T)> TT;
	typedef function<T(M, T, int)> MT;
	typedef function<M(M, M)> MM;
	TT tt;
	MT mt;
	MM mm;
	M Me;
	T Te;
	int snum;   //何回シフトで下段から1に行けるか
	LazySegtree(int N, TT _tt, MT _mtn, MM _mm, T te, M me) {
		int RN = 1;
		snum = 0;
		while (RN < N) {
			RN *= 2;
			snum++;
		}
		Te = te;
		Me = me;
		seg.resize(2 * RN, Te);
		lazy.resize(2 * RN, Me);
		tt = _tt;
		mt = _mtn;
		mm = _mm;
	}
	LazySegtree(vector<T>& vec, TT _tt, MT _mt, MM _mm, T te, M me) {
		int RN = 1;
		snum = 0;
		while (RN < vec.size()) {
			RN *= 2;
			snum++;
		}
		Te = te;
		Me = me;
		seg.resize(2 * RN, Te);
		lazy.resize(2 * RN, Me);
		tt = _tt;
		mt = _mt;
		mm = _mm;
		for (int n = 0; n < vec.size(); n++) seg[RN + n] = vec[n];
		for (int n = RN - 1; n >= 1; n--) {
			seg[n] = tt(seg[2 * n], seg[2 * n + 1]);
		}
	}
	void eval(int k, int l, int r) {
		if (k >= seg.size())return;
		if (lazy[k] == Me)return;
		seg[k] = mt(lazy[k], seg[k], r - l + 1);
		if (k < seg.size() / 2) {
			lazy[2 * k] = mm(lazy[k], lazy[2 * k]);
			lazy[2 * k + 1] = mm(lazy[k], lazy[2 * k + 1]);
		}
		lazy[k] = Me;
	}
	void apply(int a, int b, M m, int k, int l, int r) {
		eval(k, l, r);
		if (r < a || b < l)return;
		if (a <= l && r <= b) {
			lazy[k] = mm(m, lazy[k]);
			eval(k, l, r);
		}
		else {
			apply(a, b, m, 2 * k, l, (l + r) / 2);
			apply(a, b, m, 2 * k + 1, (l + r) / 2 + 1, r);
			seg[k] = tt(seg[2 * k], seg[2 * k + 1]);
		}
	}
	void apply(int a, int b, M m) {
		apply(a, b, m, 1, 0, seg.size() / 2 - 1);
	}
	T get(int a, int b, int k, int l, int r) {
		if (r < a || b < l)return Te;
		eval(k, l, r);
		if (a <= l && r <= b)return seg[k];
		else return tt(get(a, b, 2 * k, l, (l + r) / 2), get(a, b, 2 * k + 1, (l + r) / 2 + 1, r));
	}
	T get(int a, int b) {
		return get(a, b, 1, 0, seg.size() / 2 - 1);
	}
	void set(int n, T t) {
		int RN = seg.size() / 2;
		int l = 0, r = RN - 1;
		for (int t = snum; t > 0; t--) {
			eval((n + RN) >> t, l, r);
			if (((n + RN) >> (t - 1)) & 1) {
				l = ((l + r) >> 1) + 1;
			}
			else {
				r = (l + r) >> 1;
			}
		}
		eval((n + RN), n, n);
		seg[n + RN] = t;
		l = n;
		r = n;
		n += RN;
		while ((n >> 1) > 0) {
			if (n & 1) {
				l = 2 * l - r - 1;
			}
			else {
				r = 2 * r - l + 1;
			}
			n >>= 1;
			eval(n * 2, l, (l + r) >> 1);
			eval(n * 2 + 1, ((l + r) >> 1) + 1, r);
			seg[n] = tt(seg[2 * n], seg[2 * n + 1]);
		}
	}
};

void solve() {
	LazySegtree<LL, PLL> seg(A, [](LL a, LL b) {
		return (a + b) % MOD;
	}, [](PLL m, LL t, int n) {
		LL ans = m.first * t + n * m.second;
		return ans % MOD;
	}, [](PLL m2, PLL m1) {
		LL a = m2.first * m1.first;
		a %= MOD;
		LL b = m2.first * m1.second + m2.second;
		b %= MOD;
		return PLL(a, b);
	}, 0, PLL(1, 0));
	for (int q = 0; q < Q; q++) {
		if (query[q][0] == 0) {
			int l = query[q][1];
			int r = query[q][2];
			int a = query[q][3];
			int b = query[q][4];
			seg.apply(l, r - 1, PLL(a, b));
		}
		else {
			int l = query[q][1];
			int r = query[q][2];
			cout << seg.get(l, r - 1) << "\n";
		}
	}
}

void naive() {
}

void outputinput() {
}