#include <bits/stdc++.h>
using namespace std;
int read() {
  int s = 0, w = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
  return s * w;
}
struct Edge {
  int to, next;
} a[900010 << 1];
int h[900010], cnt, d[900010], dfn[900010], low[900010], dfx, bc[900010],
    top[900010], son[900010], sz[900010];
void add(int x, int y) { a[++cnt] = (Edge){y, h[x]}, h[x] = cnt; }
int ch[900010][26], tot, n, m, al[900010], rk[900010];
int ins(char* S) {
  int x = 0;
  for (int i = 0; S[i]; i++)
    x = (ch[x][S[i] - 'a'] ? ch[x][S[i] - 'a'] : ch[x][S[i] - 'a'] = ++tot);
  return x;
}
void byd() {
  queue<int> Q;
  for (int i = 0; i < 26; i++)
    if (ch[0][i]) Q.push(ch[0][i]);
  while (!Q.empty()) {
    int x = Q.front();
    Q.pop(), add(al[x], x);
    for (int i = 0; i < 26; i++)
      if (!ch[x][i])
        ch[x][i] = ch[al[x]][i];
      else
        al[ch[x][i]] = ch[al[x]][i], Q.push(ch[x][i]);
  }
}
void Dfs(int x) {
  d[x] = d[al[x]] + 1, sz[x] = 1;
  for (int i = h[x]; i; i = a[i].next)
    Dfs(a[i].to), sz[x] += sz[a[i].to],
        (sz[a[i].to] > sz[son[x]] || !son[x]) ? son[x] = a[i].to : 0;
}
void DFS(int x, int tp) {
  bc[dfn[x] = ++dfx] = x, top[x] = tp;
  if (son[x]) DFS(son[x], tp);
  for (int i = h[x]; i; i = a[i].next)
    if (a[i].to ^ son[x]) DFS(a[i].to, a[i].to);
  low[x] = dfx;
}
int s[900010 << 2];
multiset<int> st[900010];
int ASK(int k, int l, int r, int L, int R) {
  if (L > r || l > R) return -1;
  if (L <= l && r <= R) return s[k];
  int mid = l + r >> 1;
  return max(ASK(k << 1, l, mid, L, R), ASK(k << 1 | 1, mid + 1, r, L, R));
}
void BYD(int k, int l, int r) {
  if (l == r)
    return s[k] = (st[bc[l]].empty() ? -1 : *(--st[bc[l]].end())), void(0);
  int mid = l + r >> 1;
  BYD(k << 1, l, mid), BYD(k << 1 | 1, mid + 1, r),
      s[k] = max(s[k << 1], s[k << 1 | 1]);
}
void INS(int k, int l, int r, int p) {
  if (l == r)
    return s[k] = (st[bc[l]].empty() ? -1 : *(--st[bc[l]].end())), void(0);
  int mid = l + r >> 1;
  p > mid ? INS(k << 1 | 1, mid + 1, r, p) : INS(k << 1, l, mid, p),
      s[k] = max(s[k << 1], s[k << 1 | 1]);
}
int SP_ASK(int x, int y) {
  int ans = -1;
  while (top[x] ^ top[y])
    if (d[top[x]] < d[top[y]])
      ans = max(ans, ASK(1, 1, dfx, dfn[top[y]], dfn[y])), y = al[top[y]];
    else
      ans = max(ans, ASK(1, 1, dfx, dfn[top[x]], dfn[x])), x = al[top[x]];
  return max(ans, ASK(1, 1, dfx, min(dfn[x], dfn[y]), max(dfn[x], dfn[y])));
}
int Mapping(char* S) {
  int x = 0, ans = -1;
  for (int i = 0; S[i]; i++)
    x = ch[x][S[i] - 'a'], ans = max(ans, SP_ASK(0, x));
  return ans;
}
char S[900010];
int vl[900010];
signed main() {
  int x, y;
  n = read(), m = read();
  for (int i = 1; i <= n; i++) scanf("%s", S), st[rk[i] = ins(S)].insert(0);
  byd(), Dfs(0), DFS(0, 0), BYD(1, 1, dfx);
  while (m--)
    if (read() == 2)
      scanf("%s", S), cout << Mapping(S) << '\n';
    else
      x = read(), st[rk[x]].erase(st[rk[x]].find(vl[x])),
      st[rk[x]].insert(vl[x] = read()), INS(1, 1, dfx, dfn[rk[x]]);
  return 0;
}
