#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x) {
  x = 0;
  char ch = getchar();
  bool f = false;
  while (!isdigit(ch)) {
    if (ch == '-') {
      f = true;
    }
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + (ch ^ 48);
    ch = getchar();
  }
  x = f ? -x : x;
  return;
}
template <typename T>
inline void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 ^ 48);
  return;
}
const int N = 3e5 + 5;
char s[N];
int rt = 1, tot = 1, f[N], val[N], ch[N][26];
void Insert(int id) {
  int n = strlen(s), x = rt;
  for (int i = 0; i < n; i++) {
    int k = s[i] - 'a';
    if (!ch[x][k]) ch[x][k] = ++tot;
    x = ch[x][k];
  }
  val[id] = x;
}
queue<int> q;
void Build() {
  q.push(rt);
  for (int i = 0; i < 26; i++) ch[0][i] = rt;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = 0; i < 26; i++)
      if (ch[x][i])
        f[ch[x][i]] = ch[f[x]][i], q.push(ch[x][i]);
      else
        ch[x][i] = ch[f[x]][i];
  }
  return;
}
struct edge {
  int to, ch;
} e[N * 2];
int num, head[N];
inline void add(int x, int y) {
  e[++num] = {y, head[x]};
  head[x] = num;
}
int dfn, p[N], id[N], fa[N], siz[N], dep[N], son[N], top[N];
void dfs1(int x, int t) {
  siz[x] = 1;
  dep[x] = t;
  for (int i = head[x]; i != -1; i = e[i].ch) {
    int to = e[i].to;
    if (dep[to]) continue;
    dfs1(to, t + 1);
    fa[to] = x;
    siz[x] += siz[to];
    if (siz[son[x]] < siz[to]) son[x] = to;
  }
  return;
}
void dfs2(int x, int tp) {
  p[id[x] = ++dfn] = x;
  top[x] = tp;
  if (son[x]) dfs2(son[x], tp);
  for (int i = head[x]; i != -1; i = e[i].ch) {
    int to = e[i].to;
    if (top[to]) continue;
    dfs2(to, to);
  }
  return;
}
struct Segment_Tree {
  int maxv[N * 4];
  inline void pushup(int x) { maxv[x] = max(maxv[x << 1], maxv[x << 1 | 1]); };
  void Build() { memset(maxv, -1, sizeof(maxv)); }
  void Modify(int x, int l, int r, int q, int k) {
    if (l == r) return (void)(maxv[x] = k);
    int mid = l + r >> 1;
    if (q <= mid)
      Modify(x << 1, l, mid, q, k);
    else
      Modify(x << 1 | 1, mid + 1, r, q, k);
    pushup(x);
  }
  int Query(int x, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return maxv[x];
    int ans = -1, mid = l + r >> 1;
    if (ql <= mid) ans = max(ans, Query(x << 1, l, mid, ql, qr));
    if (qr > mid) ans = max(ans, Query(x << 1 | 1, mid + 1, r, ql, qr));
    return ans;
  }
} Tree;
int Query(int x) {
  int ans = -1;
  while (x != 1)
    ans = max(ans, Tree.Query(1, 1, tot, id[top[x]], id[x])), x = fa[top[x]];
  return ans;
}
int w[N];
multiset<int> S[N];
int main() {
  int n, T;
  read(n), read(T);
  for (int i = 1; i <= n; i++) scanf("%s", s), Insert(i);
  Build();
  num = -1;
  memset(head, -1, sizeof(head));
  for (int i = 2; i <= tot; i++) add(f[i], i);
  fa[1] = 1;
  dfs1(1, 1);
  dfs2(1, 1);
  Tree.Build();
  for (int i = 1; i <= n; i++) {
    int tt = val[i];
    S[tt].insert(0);
    Tree.Modify(1, 1, tot, id[tt], 0);
  }
  while (T--) {
    int op;
    read(op);
    if (op == 1) {
      int x, k, t;
      read(x), read(k), t = val[x];
      S[t].erase(S[t].find(w[x]));
      S[t].insert(k);
      w[x] = k;
      Tree.Modify(1, 1, tot, id[t], *S[t].rbegin());
    }
    if (op == 2) {
      scanf("%s", s);
      int len = strlen(s), ans = -1;
      for (int i = 0, x = 1; i < len; i++)
        x = ch[x][s[i] - 'a'], ans = max(ans, Query(x));
      write(ans);
      putchar('\n');
    }
  }
  return 0;
}
