#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
    while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
const int MAX_N = 550000;
const int MAX_K = 51;
const int p = 19260817;
const int mod = 998244353;
int n, m, q, a[MAX_N], pre[MAX_N], nxt[MAX_N], cnt[MAX_N], f[MAX_K * 2 + 10];
ULL g[MAX_K * 2 + 10], bin[MAX_K * 2];
const int MOD = (1 << 24) - 1;
struct Hash
{
    struct edge
    {
        ULL x;
        int cnt, nxt;
    } e[21000000];
    int fir[MOD + 1], cnt_e;
    void add(ULL x, int d)
    {
        int u = (x & MOD);
        for (int i = fir[u]; i; i = e[i].nxt)
            if (e[i].x == x)
            {
                e[i].cnt += d;
                return ;
            }
        e[++cnt_e] = (edge) { x, d, fir[u] }; fir[u] = cnt_e;
    }
    int query(ULL x)
    {
        int u = (x & MOD);
        for (int i = fir[u]; i; i = e[i].nxt)
            if (e[i].x == x)
                return e[i].cnt;
        return 0;
    }
} hash;
void merge()
{
    int x = read(), y = read();
    memset(f, 0, sizeof f);
    int L = MAX_K, R = L - 1;
    for (int i = x; i && L > 1; i = pre[i])
        f[--L] = a[i];
    for (int i = y; i && R + 1 < MAX_K * 2; i = nxt[i])
        f[++R] = a[i];
    for (int i = 1; i <= R; i++)
        g[i] = g[i - 1] * p + f[i];
    for (int i = L; i < MAX_K; i++)
        for (int j = MAX_K; j <= min(R, i + 49); j++)
            hash.add(g[j] - g[i - 1] * bin[j - i + 1], 1);
    nxt[x] = y, pre[y] = x;
}
void split()
{
    int x = read(), y = nxt[x];
    memset(f, 0, sizeof f);
    int L = MAX_K, R = L - 1;
    for (int i = x; i && L > 1; i = pre[i])
        f[--L] = a[i];
    for (int i = y; i && R + 1 < MAX_K * 2; i = nxt[i])
        f[++R] = a[i];
    for (int i = 1; i <= R; i++)
        g[i] = g[i - 1] * p + f[i];
    for (int i = L; i < MAX_K; i++)
        for (int j = MAX_K; j <= min(R, i + 49); j++)
            hash.add(g[j] - g[i - 1] * bin[j - i + 1], -1);
    nxt[x] = pre[y] = 0;
}
char s[11000000];
int query()
{
    scanf("%s", s + 1);
    int k = read(), ans = 1, n = strlen(s + 1);
    ULL val = 0;
    if (k == 1)
        for (int i = 1; i <= n; i++)
            ans = ((LL)ans * cnt[s[i]]) % mod;
    else for (int i = 1; i <= n; i++)
    {
        val = val * p + s[i];
        if (i > k) val -= bin[k] * s[i - k];
        if (i >= k) ans = ((LL)ans * hash.query(val)) % mod;
    }
    return ans;
}
int main()
{
    int n = read(), q = read();
    bin[0] = 1;
    for (int i = 1; i < MAX_K; i++) bin[i] = bin[i - 1] * p;
    for (int i = 1; i <= n; i++) cnt[a[i] = read() + '0'] ++;
    while (q --)
    {
        int opt = read();
        if (opt == 1) merge();
        else if (opt == 2) split();
        else printf("%d\n", query());
    }
    return 0;
}