#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

#define	ls		i << 1

#define	rs		i << 1 | 1

#define	mid		((l + r) >> 1)

#define lson		ls, l, mid

#define	rson		rs, mid + 1, r

typedef long long LL;

const int N   = 1e5 + 10;

const int mod = 99971;

int T;

int a[N], nxt[N], cal[N][49];

int t[N << 2][49], up[N << 2];

int n, m;

void pushup(int i){

	rep(j, 0, 47){

		t[i][j] = t[ls][(j + up[ls] + 48) % 48] + t[rs][(j + up[rs] + 48) % 48];

		t[i][j] %= mod;

	}

}

void build(int i, int l, int r){

	up[i] = 0;

	if (l == r){

		rep(j, 0, 47) t[i][j] = cal[a[l]][j];

		return;

	}

	build(lson);

	build(rson);

	pushup(i);

}

void update(int i, int l, int r, int L, int R){

	if (L <= l && r <= R){

		++up[i];

		up[i] %= 48;

		return;

	}

	if (L <= mid) update(lson, L, R);

	if (R  > mid) update(rson, L, R);

	pushup(i);

}

int query(int i, int l, int r, int L, int R, int cnt){

	if (L <= l && r <= R){

		return t[i][(up[i] + cnt) % 48];

	}

	int ret = 0;

	int now = cnt + up[i];

	if (L <= mid) ret += query(lson, L, R, now);

	if (R  > mid) ret += query(rson, L, R, now);

	ret %= mod;

	return ret;

}	

int main(){

	scanf("%d", &T);

	rep(i, 1, mod - 1) nxt[i] = 1ll * i * i * i % mod;

	rep(i, 1, mod - 1){

		cal[i][0] = i;

		rep(j, 1, 47){

			cal[i][j] = nxt[cal[i][j - 1]];

		}

	}

	while (T--){

		scanf("%d%d", &n, &m);

		rep(i, 1, n){

			scanf("%d", a + i);

			a[i] %= mod;

		}

		build(1, 1, n);

		while (m--){

			int op, l, r;

			scanf("%d%d%d", &op, &l, &r);

			if (op == 1) update(1, 1, n, l, r);

			else printf("%d\n", query(1, 1, n, l, r, 0));

		}

	}

	return 0;

}