#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const int N = 1e6;
const int mod = 1e9 + 7;
const int K = 26;
struct AhoCorasick {
  struct Vertex {
    vector<int> nxt;
    vector<int> go;
    char ch;
    int par;
    int suf;
    int output;
    multiset<int> store;
    Vertex(int p = 0, char c = '$') : par(p), ch(c) {
      nxt.resize(K, -1);
      go.resize(K, -1);
    }
  };
  vector<Vertex> Trie;
  int size;
  char low;
  AhoCorasick(char low = 'a') : low(low) {
    Trie.emplace_back();
    size = 1;
  }
  int add_string(string s) {
    int node = 0;
    for (char c : s) {
      if (Trie[node].nxt[c - low] == -1) {
        Trie.emplace_back(node, c);
        Trie[node].nxt[c - low] = size++;
      }
      node = Trie[node].nxt[c - low];
    }
    Trie[node].store.insert(0);
    return node;
  }
  void build() {
    queue<int> q({0});
    while (q.size()) {
      int node = q.front();
      q.pop();
      int p = Trie[node].par;
      int c = Trie[node].ch - low;
      if (p == 0) {
        Trie[node].suf = p;
        Trie[node].output = p;
      } else {
        while (p != 0 && Trie[Trie[p].suf].nxt[c] == -1) {
          p = Trie[p].suf;
        }
        if (Trie[Trie[p].suf].nxt[c] == -1) {
          Trie[node].suf = 0;
          Trie[node].output = 0;
        } else {
          Trie[node].suf = Trie[Trie[p].suf].nxt[c];
        }
      }
      if (Trie[Trie[node].suf].store.size()) {
        Trie[node].output = Trie[node].suf;
      } else {
        Trie[node].output = Trie[Trie[node].suf].output;
      }
      for (int i = 0; i < K; i++) {
        if (Trie[node].nxt[i] != -1) q.push(Trie[node].nxt[i]);
      }
    }
  }
  int get(int node, int c) {
    if (Trie[node].go[c] != -1) return Trie[node].go[c];
    while (node != 0 && Trie[node].nxt[c] == -1) {
      node = Trie[node].suf;
    }
    if (Trie[node].nxt[c] == -1) {
      Trie[node].go[c] = 0;
    } else {
      Trie[node].go[c] = Trie[node].nxt[c];
    }
    return Trie[node].go[c];
  }
};
void solve() {
  AhoCorasick ac;
  int n, m;
  cin >> n >> m;
  string s;
  vector<int> val(n), nval(n);
  for (int i = 0; i < n; i++) {
    cin >> s;
    nval[i] = ac.add_string(s);
  }
  ac.build();
  int t, ind, x;
  while (m--) {
    cin >> t;
    if (t == 2) {
      int ans = -1;
      cin >> s;
      int node = 0;
      set<int> gone, take;
      for (char c : s) {
        int nn = ac.get(node, c - 'a');
        take.insert(nn);
        node = nn;
      }
      for (int nn : take) {
        while (gone.find(nn) == gone.end()) {
          if (ac.Trie[nn].store.size())
            ans = max(ans, *ac.Trie[nn].store.rbegin());
          gone.insert(nn);
          nn = ac.Trie[nn].output;
        }
      }
      cout << ans << "\n";
    } else {
      cin >> ind >> x;
      ind--;
      ac.Trie[nval[ind]].store.erase(ac.Trie[nval[ind]].store.find(val[ind]));
      val[ind] = x;
      ac.Trie[nval[ind]].store.insert(val[ind]);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  std::cout << std::fixed << std::setprecision(20);
  ;
  int t = 1;
  while (t--) {
    solve();
  }
}
