#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";
}
}
}