#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 5;
const int INF = 0x3f3f3f3f;
struct Trie {
  int ch[MAXN][26], f[MAXN], val[MAXN], v[MAXN], top[MAXN], ed[MAXN];
  multiset<int> vals[MAXN];
  int sz, rt;
  int newnode() { return sz++; }
  void init() {
    sz = 0;
    memset(val, -1, sizeof val);
    val[rt = newnode()] = 0;
  }
  void insert(char *s, int id) {
    int p = rt, c;
    for (int i = 0; s[i]; i++) {
      c = s[i] - 'a';
      if (!ch[p][c]) ch[p][c] = newnode();
      p = ch[p][c];
    }
    val[p] = 0;
    vals[p].insert(0);
    ed[id] = p;
  }
  void build() {
    queue<int> q;
    for (int c = 0; c < 26; c++) {
      if (ch[rt][c])
        f[ch[rt][c]] = rt, q.push(ch[rt][c]);
      else
        ch[rt][c] = rt;
    }
    while (q.size()) {
      int p = q.front();
      q.pop();
      top[p] = val[f[p]] >= 0 ? f[p] : top[f[p]];
      for (int c = 0; c < 26; c++) {
        if (ch[p][c])
          f[ch[p][c]] = ch[f[p]][c], q.push(ch[p][c]);
        else
          ch[p][c] = ch[f[p]][c];
      }
    }
  }
  void modify(int i, int x) {
    int p = ed[i];
    vals[p].erase(vals[p].find(v[i]));
    v[i] = x;
    vals[p].insert(x);
    val[p] = *vals[p].rbegin();
  }
  int query(char *s) {
    int p = rt, res = -1;
    for (int i = 0; s[i]; i++) {
      p = ch[p][s[i] - 'a'];
      for (int q = p; q != rt; q = top[q]) res = max(res, val[q]);
    }
    return res;
  }
} T;
int n, m, op, id, x;
char s[MAXN];
inline void run() {
  cin >> n >> m, T.init();
  for (int i = 1; i <= n; i++) cin >> s, T.insert(s, i);
  T.build();
  while (m--) {
    cin >> op;
    if (op == 1) {
      cin >> id >> x;
      T.modify(id, x);
    } else {
      cin >> s;
      cout << (T.query(s)) << '\n';
    }
  }
}
int main() {
  run();
  return 0;
}
