#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const int mod = 1e9 + 7;
const int N = 3e5 + 10;
const int inf = 1e9;
int n, m;
char s[N];
int d[N], b[N];
vector<int> g[N];
struct SegmentTree {
  int tr[N << 2], n;
  int top[N], sz[N], f[N], d[N], son[N], dfn[N], id[N], val[N], tot;
  void bd(int l, int r, int p) {
    if (l == r) return tr[p] = val[id[l]], void();
    int mid = l + r >> 1;
    bd(l, mid, p << 1);
    bd(mid + 1, r, p << 1 | 1);
    tr[p] = max(tr[p << 1], tr[p << 1 | 1]);
  }
  void up(int x, int l, int r, int p, int k) {
    if (l == r) return tr[p] = k, void();
    int mid = l + r >> 1;
    if (x <= mid)
      up(x, l, mid, p << 1, k);
    else
      up(x, mid + 1, r, p << 1 | 1, k);
    tr[p] = max(tr[p << 1], tr[p << 1 | 1]);
  }
  int qy(int dl, int dr, int l, int r, int p) {
    if (l == dl && r == dr) return tr[p];
    int mid = l + r >> 1;
    if (dr <= mid)
      return qy(dl, dr, l, mid, p << 1);
    else if (dl > mid)
      return qy(dl, dr, mid + 1, r, p << 1 | 1);
    else
      return max(qy(dl, mid, l, mid, p << 1),
                 qy(mid + 1, dr, mid + 1, r, p << 1 | 1));
  }
  void dfs(int u) {
    d[u] = d[f[u]] + 1;
    sz[u] = 1;
    for (int x : g[u]) {
      f[x] = u;
      dfs(x);
      sz[u] += sz[x];
      if (sz[x] > sz[son[u]]) son[u] = x;
    }
  }
  void dfs1(int u, int t) {
    top[u] = t;
    dfn[u] = ++tot;
    id[tot] = u;
    if (son[u]) dfs1(son[u], t);
    for (int x : g[u]) {
      if (x == son[u]) continue;
      dfs1(x, x);
    }
  }
  void up(int i, int k) { up(dfn[i], 1, n, 1, k); }
  int qy(int x, int y) {
    int ret = -1;
    while (top[x] != top[y]) {
      if (d[top[x]] < d[top[y]]) swap(x, y);
      ret = max(ret, qy(dfn[top[x]], dfn[x], 1, n, 1));
      x = f[top[x]];
    }
    if (d[x] < d[y]) swap(x, y);
    return max(ret, qy(dfn[y], dfn[x], 1, n, 1));
  }
  void init(int _n) {
    n = _n;
    dfs(1);
    dfs1(1, 1);
    bd(1, n, 1);
  }
} seg;
struct ACtree {
  int son[N][26], fail[N], top[N], tot;
  multiset<int> cnt[N];
  int newnode() {
    for (int i = 0; i < 26; i++) son[tot][i] = 0;
    cnt[tot++].clear();
    return tot - 1;
  }
  void init() {
    tot = 0;
    newnode();
  }
  void ins(int x, char s[]) {
    int rt = 0, m = strlen(s);
    for (int i = 0; i < m; i++) {
      if (!son[rt][s[i] - 'a']) son[rt][s[i] - 'a'] = newnode();
      rt = son[rt][s[i] - 'a'];
    }
    cnt[rt].insert(0);
    b[x] = rt;
  }
  void gao() {
    queue<int> q;
    for (int i = 0; i < 26; i++)
      if (son[0][i]) fail[son[0][i]] = 0, q.push(son[0][i]);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      if (!cnt[fail[u]].empty())
        top[u] = fail[u];
      else
        top[u] = top[fail[u]];
      g[fail[u] + 1].push_back(u + 1);
      for (int i = 0; i < 26; i++) {
        if (son[u][i]) {
          fail[son[u][i]] = son[fail[u]][i];
          q.push(son[u][i]);
        } else
          son[u][i] = son[fail[u]][i];
      }
    }
    for (int i = 0; i < tot; i++)
      if (!cnt[i].empty()) {
        seg.val[i + 1] = 0;
      } else
        seg.val[i + 1] = -1;
    seg.init(tot);
  }
  void change(int i, int x) {
    cnt[b[i]].erase(cnt[b[i]].lower_bound(d[i]));
    d[i] = x;
    cnt[b[i]].insert(x);
    auto it = cnt[b[i]].end();
    --it;
    seg.up(b[i] + 1, *it);
  }
  int qy(char s[]) {
    int rt = 0, m = strlen(s), ans = -1;
    for (int i = 0; i < m; i++) {
      rt = son[rt][s[i] - 'a'];
      ans = max(ans, seg.qy(rt + 1, 1));
    }
    return ans;
  }
} AC;
int main() {
  scanf("%d%d", &n, &m);
  AC.init();
  for (int i = 1; i <= n; i++) {
    scanf("%s", s);
    AC.ins(i, s);
  }
  AC.gao();
  while (m--) {
    int op, i, x;
    scanf("%d", &op);
    if (op == 1) {
      scanf("%d%d", &i, &x);
      AC.change(i, x);
    } else {
      scanf("%s", s);
      printf("%d\n", AC.qy(s));
    }
  }
  return 0;
}
