#include <bits/stdc++.h>
using namespace std;
void solve();
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  solve();
}
const int N = 3e5 + 1000;
int n, m, k = 500, val[N], bor[N][26], p[2 * N], gi = 1, cur;
multiset<int> se[N];
vector<int> v;
string s[N], q, w;
char gg(int pos) {
  if (pos < q.size()) return q[pos];
  if (pos == q.size()) return '#';
  return w[pos - q.size() - 1];
}
bool f() {
  p[0] = -1;
  for (int i = 1; i <= q.size() + w.size() + 1; i++) {
    int k = p[i - 1];
    while (k > -1 && gg(k) != gg(i - 1)) {
      k = p[k];
    }
    p[i] = k + 1;
    if (p[i] == q.size()) {
      return true;
    }
  }
  return false;
}
void solve() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    if (s[i].size() <= k) {
      cur = 0;
      for (int j = 0; j < s[i].size(); j++) {
        if (!bor[cur][s[i][j] - 'a']) {
          bor[cur][s[i][j] - 'a'] = gi++;
        }
        cur = bor[cur][s[i][j] - 'a'];
      }
      se[cur].insert(0);
    } else {
      v.push_back(i);
    }
  }
  for (int i = 0; i < m; i++) {
    int type;
    cin >> type;
    if (type == 1) {
      int pos, nval;
      cin >> pos >> nval;
      pos--;
      if (s[pos].size() <= k) {
        cur = 0;
        for (int j = 0; j < s[pos].size(); j++) {
          cur = bor[cur][s[pos][j] - 'a'];
          if (j + 1 == s[pos].size()) {
            if (se[cur].find(val[pos]) != se[cur].end()) {
              se[cur].erase(se[cur].find(val[pos]));
            }
            val[pos] = nval;
            se[cur].insert(val[pos]);
          }
        }
      } else {
        val[pos] = nval;
      }
    } else {
      string e;
      cin >> e;
      int res = -1;
      for (int j = 0; j < e.size(); j++) {
        cur = 0;
        for (int h = j; h < e.size(); h++) {
          if (!bor[cur][e[h] - 'a']) break;
          cur = bor[cur][e[h] - 'a'];
          if (!se[cur].empty()) {
            res = max(res, (*--se[cur].end()));
          }
        }
      }
      if (e.size() > k) {
        w = e;
        for (int j = 0; j < v.size(); j++) {
          q = s[v[j]];
          if (f()) {
            res = max(res, val[v[j]]);
          }
        }
      }
      cout << res << '\n';
    }
  }
}
