#include <bits/stdc++.h>

using namespace std;

const int MxN = int(3e5)+10;
int n, m, to[MxN][26], term[MxN], link[MxN], dic[MxN], sus[MxN], sz = 1; 
int v[MxN], an[MxN];
multiset<int> vals[MxN];

void add_word(string s, int j) {
    int cur = 0;
    for (auto c : s) {
        if (!to[cur][c - 'a']) {
            to[cur][c - 'a'] = sz++;
        }
        cur = to[cur][c - 'a'];
    }
    term[cur] = cur;
    v[j] = cur;
    sus[j] = 0;
    vals[cur].insert(0);
}

void push_links() {
    int q[sz];
    q[0] = 0;
    int st = 0;
    int fi = 1;
    while (st < fi) {
        int V = q[st++];
        int U = link[V];
        if (term[U]) dic[V] = U;
        else dic[V] = dic[U];
        for (int i = 0; i < 26; i++) {
            if (to[V][i]) {
                link[to[V][i]] = V ? to[U][i] : 0;
                q[fi++] = to[V][i];
            } else {
                to[V][i] = to[U][i];
            }
        }
    }
}

int search(string s) {
    int ans = -1;
    int cur = 0;
    for (auto c : s) {
        cur = to[cur][c - 'a'];
        for (int p = cur; p != 0; p = dic[p]) {
            if (term[p])
                ans = max(an[p], ans);
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        add_word(s, i+1);
    }
    push_links();
    for (int i = 0; i < m; i++) {
        int a;
        cin >> a;
        if (a == 1) {
            int b, c;
            cin >> b >> c;
            vals[v[b]].erase(vals[v[b]].find(sus[b]));
            sus[b] = c;
            vals[v[b]].insert(c);
            auto y = vals[v[b]].end();
            y--;
            an[v[b]] = (*y); 
        }
        if (a == 2) {
            string s;
            cin >> s;
            cout << search(s) << "\n";
        }
    }
}