#include <bits/stdc++.h>
using namespace std;
const int B = 26;
const int N = 3e5 + 10;
const int M = N * B;
const char O = 'a';
namespace acaho {
int ch[N][B], link[N], nc;
int root = 0;
int vis[N];
int endpos[N], val[N], ec;
int np (void) {
nc ++;
fill(ch[nc], ch[nc] + B, 0);
link[nc] = 0;
val[nc] = -1;
return nc;
}
void insert (char * s) {
int p = root;
for (int i = 0, o; s[i]; i ++) {
if (!ch[p][o = s[i] - O]) ch[p][o] = np();
p = ch[p][o];
}
val[p] = 0;
endpos[++ ec] = p;
}
void build (void) {
queue<int> q;
for (int o = 0; o < B; o ++) if (ch[root][o])
q.push(ch[root][o]);
while (!q.empty()) {
int p = q.front(); q.pop();
for (int o = 0; o < B; o ++) {
if (ch[p][o]) {
link[ch[p][o]] = ch[link[p]][o];
q.push(ch[p][o]);
} else {
ch[p][o] = ch[link[p]][o];
}
}
}
}
void clear (void) { nc = -1; root = np(); }
};
using namespace acaho;
char s[N];
int value[N]; multiset<int> vs[N];
int main (void) {
clear();
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++) {
scanf("%s", s);
insert(s);
vs[endpos[i]].insert(0);
}
build();
int len = 0;
for (int i = 1, opt, x, y; i <= m; i ++) {
scanf("%d", &opt);
if (opt == 1) {
scanf("%d%d", &x, &y);
vs[endpos[x]].erase(vs[endpos[x]].find(value[x]));
vs[endpos[x]].insert(value[x] = y);
val[endpos[x]] = *(--vs[endpos[x]].end());
} else {
scanf("%s", s);
int ans = -1, p = 0;
len += strlen(s);
for (int j = 0; s[j]; j ++) {
p = ch[p][s[j] - 'a'];
for (int q = p; vis[q] != i && q; q = link[q]) {
ans = max(ans, val[q]);
vis[q] = i;
}
}
printf("%d\n", ans);
}
}
}