#include<bits/stdc++.h>
using std::cin;
using std::cout;
using db = double;
using ll = long long;
using u64 = unsigned long long;
const int mod = 998244353;
const int N = 1 << 19;
int pow(int a, int b, int ans = 1) {
	for(;b;b >>= 1, a = (u64) a * a % mod) if(b & 1) {
		ans = (u64) ans * a % mod;
	}
	return ans;
}
int wn[N], rev[N];
int lim, invlim;
void init(int len) {
	lim = 2 << std::__lg(len - 1);
	invlim = mod - (mod - 1) / lim;
	for(static int i = 1;i < lim;i += i) {
		wn[i] = 1;
		const int w = pow(3, mod / i / 2);
		for(int j = 1;j < i;++j) {
			wn[i + j] = (u64) wn[i + j - 1] * w % mod;
		}
	}
	for(int i = 1;i < lim;++i) {
		rev[i] = rev[i >> 1] >> 1 | (i % 2u * lim / 2);
	}
}

void DFT(int * a) {
	static u64 t[N];
	for(int i = 0;i < lim;++i) t[i]=  a[rev[i]];
	for(int i = 1;i < lim;i += i) {
		for(int j = 0;j < lim;j += i + i) {
			for(int k = 0;k < i;++k) {
				const u64 x = t[i + j + k] * wn[i + k] % mod;
				t[i + j + k] = t[k + j] + mod - x, t[k + j] += x;
			}
		}
	}
	for(int i = 0;i < lim;++i) a[i]=  t[i] % mod;
}
void IDFT(int * a ){
	DFT(a), std::reverse( a + 1, a + lim);
	for(int i = 0;i < lim;++i) a[i] = (u64) a[i] * invlim % mod;
}
int n, q;
int v[N], vv[N];

int x[N], b[N];
int preb[N];
int prev[N];

int A;
int B;

int S;

void sub(int & x, int y) {
	x -= y, x += x >> 31 & mod;
}
void add(int & x, int y) {
	x += y;
	if(x >= mod) x -= mod;
}
void build() {
	memset(b, 0, lim << 2);
	for(int i = 0;i < n;++i) {
		int need = A + x[i];
		b[(n * 4u - need) % n] += 1;
	}
	DFT(b);
	for(int i = 0;i < lim;++i) {
		b[i] = (u64) b[i] * vv[i] % mod;
	}
	IDFT(b);
	for(int i = n;i < n + n;++i) {
		add(b[i - n], b[i]);
		b[i] = 0;
	}
	for(int i = n;i < n + n;++i) {
		b[i] = b[i - n];
	}
	for(int i = 0;i < n + n;++i) {
		preb[i] = b[i];
	}
	for(int i = n + n - 1;i >= 0;--i) {
		add(preb[i], preb[i + 1]);
	}

}
int main() {
#ifdef zqj
	freopen("$.in", "r", stdin);
#endif
	std::ios::sync_with_stdio(false), cin.tie(0);

	cin >> n >> q;
	if(n % 2) {
		for(int i = 0;i <= q;++i) {
			puts("0");
		}
		return 0;
	}
	if(n % 4 == 2) {
		A = (n + 2) / 4;
		B = n / 2;
	} else {
		A = n / 4 + 1;
		B = n / 2 - 1;
	}
	for(int i = 0;i < n;++i) {
		cin >> v[i];
		vv[i] = v[i];
	}
	for(int i = 0;i < n;++i) {
		x[i] = i;
	}
	for(int i = 0;i < n * 2;++i) prev[i] = v[i % n];
	for(int i = n * 2 - 1;i >= 0;--i) add(prev[i], prev[i + 1]);
	init(n + n);
	DFT(vv);
	build();
	std::vector<int> ins, del;
	auto calc = [&]() {
		int move = (n - S) % n;
		int ans = preb[move] - preb[move + B];
		ans = (ans + mod) % mod;
		for(int x : ins) {
			int p = A - S + x;
			if(p < 0) p += n;
			if(p >= n) p -= n;
			add(ans, prev[p]);
			sub(ans, prev[p + B]);
		}
		for(int x : del) {
			int p = A - S + x;
			if(p < 0) p += n;
			if(p >= n) p -= n;
			sub(ans, prev[p]);
			add(ans, prev[p + B]);
		}
		return ans;
	};
	cout << calc() << '\n';
	const int B = 1000;
	for(int i = 0;i < q;++i) {
		int op, q, k;
		cin >> op;
		if(op == 1) {
			cin >> k;
			S = (S - k + n) % n;
		} else {
			cin >> q >> k;
			q = (q + S) % n;
			del.push_back(x[q]);
			x[q] = (x[q] - k + n) % n;
			ins.push_back(x[q]);
		}
		if(del.size() >= B) {
			build();
			del = ins = {};
		}
		cout << calc() << '\n';
	}
	

}