#include <bits/stdc++.h>
using namespace std;

const int maxn = 330009;
int nxt[maxn][27], tot, fail[maxn], val[maxn], idx[maxn], v[maxn];
int failpro[maxn];
multiset<int> validx[maxn];
int main() {
#ifdef LOCAL
  freopen(".a.in", "r", stdin);
#endif
  ios_base::sync_with_stdio(false);
  cout.tie(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  val[0] = -1;
  for (int i = 0; i < n; ++i) {
    int rt = 0;
    string s;
    cin >> s;
    for (int j = 0; j < (int)s.size(); ++j) {
      if (!nxt[rt][s[j] - 'a']) {
        nxt[rt][s[j] - 'a'] = ++tot;
        val[tot] = -1;
      }
      rt = nxt[rt][s[j] - 'a'];
    }
    idx[i] = rt;
    validx[rt].insert(0);
    val[rt] = 0;
  }
  vector<int> que;
  for (int i = 0; i < 26; ++i)
    if (nxt[0][i]) que.push_back(nxt[0][i]);
  for (int i = 0; i < (int)que.size(); ++i) {
    int u=que[i];
    failpro[u] = val[fail[u]] >= 0 ? fail[u] : failpro[fail[u]];
    for (int j = 0; j < 26; ++j) {
      if (nxt[que[i]][j]) {
        fail[nxt[que[i]][j]] = nxt[fail[que[i]]][j];
        que.push_back(nxt[que[i]][j]);
      } else {
        nxt[que[i]][j] = nxt[fail[que[i]]][j];
      }
    }
  }
  while (q--) {
    int op;
    cin >> op;
    if (op == 1) {
      int x, y;
      cin >> x >> y;
      --x;
      validx[idx[x]].erase(validx[idx[x]].find(v[x]));
      v[x] = y;
      validx[idx[x]].insert(y);
      val[idx[x]] = *--validx[idx[x]].end();
    } else {
      string t;
      cin >> t;
      int rt = 0, res = -1;
      for (int i = 0; i < (int)t.size(); ++i) {
        rt = nxt[rt][t[i] - 'a'];
        for (int j = rt; j; j = failpro[j]) res = max(res, val[j]);
      }
      cout << res << "\n";
    }
  }
  return 0;
}