#include <iostream>
#include <cstdio>
using namespace std;

typedef unsigned long long ULL;

const int N = 2e5 + 5, S = 51, O = 1 << 23, T = 1e7 + 5, P = 998244353;

const ULL B = 7;

int n, m, L[N], R[N], a[N], p[N], pos[N];

ULL v[N][S], Pow[S];

char s[T];

int cnt[O];

int head[O], numE;

struct E{
	int next, w;
	ULL v;
} e[N * S * 2];

void inline add(ULL x, int k) {
	int u = x % O;
	for (int i = head[u]; i; i = e[i].next) {
		if (e[i].v == x) {
			e[i].w += k;
			return ;
		}
	}
	e[++numE] = (E) { head[u], k, x };
	head[u] = numE;
}

int inline ask(ULL x) {
	int u = x % O;
	for (int i = head[u]; i; i = e[i].next) {
		if (e[i].v == x) return e[i].w;
	}
	return 0;
}

void inline merge(int x, int y) {
	R[x] = y, L[y] = x;
	for (int i = x, j = 1; j <= 50 && i; j++, i = L[i]) {
		while (p[i] < 50 && R[pos[i]]) {
			pos[i] = R[pos[i]];
			++p[i], v[i][p[i]] = v[i][p[i] - 1] * B + a[pos[i]];
			add(v[i][p[i]], 1);		
		}
	}
}

void inline split(int x) {
	int y = R[x];
	for (int i = x, j = 1; j <= 50 && i; j++, i = L[i]) {
		while (pos[i] != x && pos[i] != i) {
			add(v[i][p[i]], -1);		
			--p[i], pos[i] = L[pos[i]];
		}
	}
	R[x] = 0, L[y] = 0;
}

int main() {
	//freopen("C:/Users/MoRanSky/Downloads/P3823_3.in", "r", stdin);
	Pow[0] = 1;
	for (int i = 1; i < S; i++)
		Pow[i] = Pow[i - 1] * B;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", a + i), p[i] = 1, pos[i] = i;
		v[i][1] = a[i], add(v[i][1], 1);
	}
	while (m--) {
		int op; scanf("%d", &op);
		if (op == 1) {
			int x, y; scanf("%d%d", &x, &y);
			merge(x, y);
		} else if (op == 2) {
			int x; scanf("%d", &x);
			split(x);
		} else {
			int k; scanf("%s%d", s + 1, &k);
			ULL val = 0;
			int res = 1;
			for (int i = 1; s[i]; i++) {
				val = val * B + (s[i] - '0');
				if (i - k >= 1) val = val - Pow[k] * (s[i - k] - '0');
				if (i >= k) res = 1ll * res * ask(val) % P;
			}
			printf("%d\n", res);
		}
	}
	return 0;
}