#include <bits/stdc++.h>
using namespace std;
struct triePont {
  int os = -1, os2 = -1, c;
  int t[26] = {};
  bool veg = false;
  triePont() {
    for (int i = 0; i < 26; i++) t[i] = -1;
  }
};
struct segment_tree {
  vector<multiset<int>> v;
  int maxn;
  segment_tree() {}
  segment_tree(int n) {
    maxn = n;
    v.assign(4 * n + 4, multiset<int>());
  }
  void csere(int x, int c, int elozo) {
    if (elozo != -1) {
      auto it = v[x].find(elozo);
      v[x].erase(it);
    }
    v[x].insert(c);
  }
  void upd(int s, int e, int c, int elozo, int x, int l, int r) {
    if (e <= l || r <= s) return;
    if (s <= l && r <= e) {
      csere(x, c, elozo);
      return;
    }
    upd(s, e, c, elozo, 2 * x + 1, l, (l + r) / 2);
    upd(s, e, c, elozo, 2 * x + 2, (l + r) / 2, r);
    return;
  }
  int ert(int ind, int akt, int x, int l, int r) {
    int aktErt = (v[x].size() > 0 ? max(akt, *v[x].rbegin()) : akt);
    if (l + 1 == r) return aktErt;
    int m = (l + r) / 2;
    if (ind < m) return ert(ind, aktErt, 2 * x + 1, l, m);
    return ert(ind, aktErt, 2 * x + 2, m, r);
  }
  void update(int l, int r, int c, int elozo) {
    upd(l, r, c, elozo, 0, 0, maxn);
    return;
  }
  int ertek(int ind) { return ert(ind, 0, 0, 0, maxn); }
};
vector<triePont> trie;
vector<vector<int>> g;
vector<int> alatt, hely;
vector<int> vegek;
void Add(string &s) {
  int x = 0;
  for (char &c : s) {
    int y = c - 'a';
    if (trie[x].t[y] == -1) {
      trie.push_back(triePont());
      trie[(int)trie.size() - 1].os = x;
      trie[(int)trie.size() - 1].c = y;
      trie[x].t[y] = (int)trie.size() - 1;
    }
    x = trie[x].t[y];
  }
  trie[x].veg = true;
  vegek.push_back(x);
  return;
}
void AhoCorasic() {
  g.resize(trie.size());
  alatt.resize(trie.size());
  hely.resize(trie.size());
  queue<int> q;
  q.push(0);
  while (q.size()) {
    int x = q.front();
    q.pop();
    if (x != 0) {
      trie[x].os2 = trie[trie[x].os].os2;
      if (trie[x].os2 != -1)
        trie[x].os2 = trie[trie[x].os2].t[trie[x].c];
      else
        trie[x].os2 = 0;
      g[trie[x].os2].push_back(x);
      trie[x].veg = trie[x].veg | trie[trie[x].os2].veg;
    }
    for (int i = 0; i < 26; i++) {
      if (trie[x].t[i] != -1)
        q.push(trie[x].t[i]);
      else if (x != 0)
        trie[x].t[i] = trie[trie[x].os2].t[i];
      else
        trie[x].t[i] = 0;
    }
  }
  return;
}
int ido = 0;
int Bejar(int akt) {
  alatt[akt] = 0;
  for (int x : g[akt]) alatt[akt] += Bejar(x);
  hely[akt] = ido++;
  return alatt[akt] + 1;
}
segment_tree st;
void PontUpdate(int x, int c, int elozo) {
  st.update(hely[x] - alatt[x], hely[x] + 1, c, elozo);
  return;
}
int Megold(string &s) {
  int x = 0, ret = 0;
  bool van = false;
  for (char c : s) {
    x = trie[x].t[c - 'a'];
    van = van | trie[x].veg;
    ret = max(ret, st.ertek(hely[x]));
  }
  if (!van) return -1;
  return ret;
}
int main() {
  cin.sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  trie.push_back(triePont());
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    Add(s);
  }
  AhoCorasic();
  Bejar(0);
  st = segment_tree(g.size());
  vector<int> elozo(n, -1);
  for (int i = 0; i < m; i++) {
    int a;
    cin >> a;
    if (a == 1) {
      int b, c;
      cin >> b >> c;
      PontUpdate(vegek[b - 1], c, elozo[b - 1]);
      elozo[b - 1] = c;
    } else {
      string s;
      cin >> s;
      cout << Megold(s) << "\n";
    }
  }
  return 0;
}
