#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
struct AC_Automata {
  int root, tree[N][26], tot;
  int fail[N], id[N], vis[N];
  int qu[N], head, tail;
  int newnode() {
    for (int i = 0; i < 26; i++) tree[tot][i] = 0;
    fail[tot] = vis[tot] = 0;
    return tot++;
  }
  void init() {
    tot = 0;
    root = newnode();
  }
  int insert(string s) {
    int cur = root;
    for (int i = 0; s[i]; i++) {
      int tmp = s[i] - 'a';
      if (!tree[cur][tmp]) tree[cur][tmp] = newnode();
      cur = tree[cur][tmp];
    }
    vis[cur] = 1;
    return cur;
  }
  void build() {
    head = 1, tail = 0;
    for (int i = 0; i < 26; i++)
      if (tree[0][i]) qu[++tail] = tree[0][i];
    while (head <= tail) {
      int cur = qu[head++];
      for (int i = 0; i < 26; i++) {
        int tmp = tree[cur][i];
        if (tmp)
          fail[tmp] = tree[fail[cur]][i], qu[++tail] = tmp;
        else
          tree[cur][i] = tree[fail[cur]][i];
      }
    }
    for (int i = 1; i <= tail; i++) vis[qu[i]] |= vis[fail[qu[i]]];
  }
} ac;
struct Segment {
  int a[N];
  struct Tree {
    int l, r, val;
  } tree[N << 2];
  void init(int sz) {
    for (int i = 1; i <= sz; i++) a[i] = 0;
  }
  void build(int pos, int l, int r) {
    tree[pos] = {l, r, a[l]};
    if (l == r) return;
    int mid = l + r >> 1;
    build(pos << 1, l, mid);
    build(pos << 1 | 1, mid + 1, r);
    tree[pos].val = max(tree[pos << 1].val, tree[pos << 1 | 1].val);
  }
  void modify(int pos, int wz, int val) {
    if (tree[pos].l == wz && tree[pos].r == wz) {
      tree[pos].val = val;
      return;
    }
    int mid = tree[pos].l + tree[pos].r >> 1;
    if (wz <= mid) modify(pos << 1, wz, val);
    if (mid < wz) modify(pos << 1 | 1, wz, val);
    tree[pos].val = max(tree[pos << 1].val, tree[pos << 1 | 1].val);
  }
  int query_ma(int pos, int l, int r) {
    if (l <= tree[pos].l && tree[pos].r <= r) return tree[pos].val;
    int mid = tree[pos].l + tree[pos].r >> 1, ma = 0;
    if (l <= mid) ma = max(ma, query_ma(pos << 1, l, r));
    if (mid < r) ma = max(ma, query_ma(pos << 1 | 1, l, r));
    return ma;
  }
} seg;
int main() {
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  ac.init();
  vector<int> pos(n + 1);
  for (int i = 1; i <= n; i++) {
    string s;
    cin >> s;
    pos[i] = ac.insert(s);
  }
  ac.build();
  int sz = ac.tot;
  vector<vector<int>> v(sz);
  for (int i = 1; i < sz; i++) v[ac.fail[i]].emplace_back(i);
  vector<int> deep(sz + 1), siz(sz + 1), fa(sz + 1), son(sz + 1);
  function<void(int, int, int)> dfs1 = [&](int x, int y, int depth) {
    siz[x] = 1;
    deep[x] = depth;
    son[x] = 0;
    for (auto it : v[x]) {
      if (it == y) continue;
      fa[it] = x;
      dfs1(it, x, depth + 1);
      siz[x] += siz[it];
      if ((!son[x]) || siz[it] > siz[son[x]]) son[x] = it;
    }
  };
  dfs1(0, -1, 1);
  int idx = 0;
  vector<int> top(sz + 1), dfn(sz + 1);
  function<void(int, int, int)> dfs2 = [&](int x, int y, int z) {
    top[x] = z;
    dfn[x] = ++idx;
    if (son[x]) dfs2(son[x], x, z);
    for (auto it : v[x]) {
      if (it == y || it == son[x]) continue;
      dfs2(it, x, it);
    }
  };
  dfs2(0, -1, 0);
  seg.init(sz);
  seg.build(1, 1, sz);
  vector<int> pre(n + 1);
  vector<multiset<int>> se(sz + 1);
  for (int i = 1; i <= n; i++) se[dfn[pos[i]]].insert(0);
  while (m--) {
    int op;
    cin >> op;
    if (op == 2) {
      string s;
      cin >> s;
      int cur = 0, ma = 0, ok = 0;
      for (int i = 0; s[i]; i++) {
        cur = ac.tree[cur][s[i] - 'a'];
        auto query = [&](int tmp) {
          int ma = 0;
          while (tmp) {
            ma = max(ma, seg.query_ma(1, dfn[top[tmp]], dfn[tmp]));
            tmp = fa[top[tmp]];
          }
          return ma;
        };
        ma = max(ma, query(cur));
        if (ac.vis[cur]) ok = 1;
      }
      if (!ok)
        cout << -1 << "\n";
      else
        cout << ma << "\n";
    } else {
      int id, x;
      cin >> id >> x;
      int wz = dfn[pos[id]];
      se[wz].erase(se[wz].find(pre[id]));
      se[wz].insert(x);
      pre[id] = x;
      seg.modify(1, wz, *se[wz].rbegin());
    }
  }
  return 0;
}
