#include <bits/stdc++.h>
using namespace std;
char __buf[1 << 20], *__p1, *__p2;
inline int read() {
  int __x = 0, __f = 1;
  char __c = getchar();
  while (__c < '0' || __c > '9') {
    if (__c == '-') __f = -1;
    __c = getchar();
  }
  while (__c >= '0' && __c <= '9') {
    __x = __x * 10 + __c - '0';
    __c = getchar();
  }
  return __x * __f;
}
char __F[200];
inline void write(int __x) {
  if (__x < 0) {
    putchar('-');
    __x = -__x;
  }
  if (__x >= 10) write(__x / 10);
  putchar(__x % 10 + '0');
}
const int maxn = 3e5 + 5;
struct edge {
  int next, to;
} e[maxn];
struct tree {
  int l, r, sum, mid;
} t[maxn * 4];
char s[maxn];
int tr[maxn][26], fail[maxn], p[maxn], h[maxn], n, m, bj[maxn],
    tot = 1, pos, cnt, f[maxn], d[maxn], siz[maxn], son[maxn], top[maxn],
    zc[maxn], zcnt, a[maxn];
queue<int> q;
multiset<int> st[maxn];
void addedge(int x, int y) {
  e[++cnt].next = h[x];
  e[cnt].to = y;
  h[x] = cnt;
}
void insert(int u) {
  int root = 1, y, len = strlen(s);
  for (register int i = 0; i < len; i++) {
    y = s[i] - 'a';
    if (!tr[root][y]) {
      tr[root][y] = ++tot;
    }
    root = tr[root][y];
  }
  bj[u] = root;
}
void getfail() {
  for (register int i = 0; i < 26; i++) {
    tr[0][i] = 1;
  }
  q.push(1);
  while (!q.empty()) {
    int u = q.front(), fa = fail[u];
    q.pop();
    for (register int i = 0; i < 26; i++) {
      int &j = tr[u][i];
      if (!j) {
        j = tr[fa][i];
        continue;
      }
      fail[j] = tr[fa][i];
      q.push(j);
    }
  }
}
void dfs(int u) {
  siz[u] = 1;
  for (register int i = h[u]; i; i = e[i].next) {
    int j = e[i].to;
    d[j] = d[u] + 1;
    f[j] = u;
    dfs(j);
    siz[u] += siz[j];
    if (!son[u] || siz[j] > siz[son[u]]) {
      son[u] = j;
    }
  }
}
void dfs2(int u, int tp) {
  p[u] = ++pos;
  top[u] = tp;
  if (son[u]) {
    dfs2(son[u], tp);
  } else
    return;
  for (register int i = h[u]; i; i = e[i].next) {
    int j = e[i].to;
    if (j == son[u]) {
      continue;
    }
    dfs2(j, j);
  }
}
int lca(int x, int y) {
  while (top[x] != top[y]) {
    if (d[top[x]] < d[top[y]]) {
      swap(x, y);
    }
    x = f[top[x]];
  }
  if (d[x] > d[y]) {
    swap(x, y);
  }
  return x;
}
void pushup(int id) { t[id].sum = max(t[id << 1].sum, t[id << 1 | 1].sum); }
void build(int id, int l, int r) {
  t[id].l = l, t[id].r = r, t[id].mid = (l + r) / 2;
  t[id].sum = -1;
  if (l == r) {
    return;
  }
  int mid = (l + r) / 2;
  build(id << 1, l, mid);
  build(id << 1 | 1, mid + 1, r);
}
void change(int id, int v, int k, int w) {
  if (t[id].l == t[id].r) {
    int l = t[id].l;
    if (k == -1) {
      st[l].insert(-1);
    }
    multiset<int>::iterator it = st[l].find(k);
    st[l].erase(it);
    st[l].insert(w);
    it = st[l].end();
    it--;
    t[id].sum = *it;
    return;
  }
  if (v <= t[id].mid) change(id << 1, v, k, w);
  if (v > t[id].mid) change(id << 1 | 1, v, k, w);
  pushup(id);
}
int ask(int id, int l, int r) {
  if (t[id].l >= l && t[id].r <= r) {
    return t[id].sum;
  }
  int sum = -1;
  if (l <= t[id].mid) sum = max(sum, ask(id << 1, l, r));
  if (r > t[id].mid) sum = max(sum, ask(id << 1 | 1, l, r));
  return sum;
}
int query(int u, int v) {
  int tmp = -1;
  while (top[u] != top[v]) {
    if (d[top[u]] < d[top[v]]) {
      swap(u, v);
    }
    tmp = max(tmp, ask(1, p[top[u]], p[u]));
    u = f[top[u]];
  }
  if (d[u] > d[v]) {
    swap(u, v);
  }
  return max(tmp, ask(1, p[u], p[v]));
}
bool cmp(int x, int y) { return p[x] < p[y]; }
int main() {
  int op, x, y;
  n = read(), m = read();
  for (register int i = 1; i <= n; i++) {
    scanf("%s", s);
    insert(i);
  }
  getfail();
  for (register int i = 2; i <= tot; i++) {
    addedge(fail[i], i);
  }
  dfs(1);
  dfs2(1, 1);
  build(1, 1, pos);
  for (register int i = 1; i <= n; i++) {
    change(1, p[bj[i]], -1, 0);
  }
  zc[0] = 1;
  while (m--) {
    op = read();
    if (op == 1) {
      x = read(), y = read();
      change(1, p[bj[x]], a[x], y);
      a[x] = y;
      continue;
    }
    scanf("%s", s);
    int u = 1, len = strlen(s), L, sum = -1;
    zcnt = 0;
    for (register int i = 0; i < len; i++) {
      u = tr[u][s[i] - 'a'];
      zc[++zcnt] = u;
    }
    sort(zc + 1, zc + zcnt + 1, cmp);
    for (register int i = 1; i <= zcnt; i++) {
      L = lca(zc[i], zc[i - 1]);
      sum = max(sum, query(zc[i], L));
    }
    write(sum);
    putchar('\n');
  }
  return 0;
}
