#include <bits/stdc++.h>
using namespace std;
const int AS = 26;
struct vertex {
  int next[AS];
  bool leaf = false;
  multiset<int> st;
  int mx = 0;
  int p = -1;
  int length = 0;
  char pch;
  int link = -1;
  int elink = -1;
  int go[AS];
  vertex(int p = -1, char ch = '$') : p(p), pch(ch) {
    fill(begin(next), end(next), -1);
    fill(begin(go), end(go), -1);
  }
};
vector<vertex> trie(1000000);
int cur_size = 1;
int addString(string const& s) {
  int v = 0;
  for (char ch : s) {
    int c = ch - 'a';
    if (trie[v].next[c] == -1) {
      trie[v].next[c] = cur_size;
      trie[cur_size].p = v;
      trie[cur_size].pch = ch;
      cur_size++;
    }
    v = trie[v].next[c];
  }
  trie[v].length = s.length();
  trie[v].st.insert(0);
  trie[v].leaf = true;
  return v;
}
int go(int v, char ch);
int get_link(int v) {
  if (trie[v].link == -1) {
    if (v == 0 || trie[v].p == 0)
      trie[v].link = 0;
    else
      trie[v].link = go(get_link(trie[v].p), trie[v].pch);
  }
  return trie[v].link;
}
int go(int v, char ch) {
  int c = ch - 'a';
  if (trie[v].go[c] == -1) {
    if (trie[v].next[c] != -1)
      trie[v].go[c] = trie[v].next[c];
    else
      trie[v].go[c] = v == 0 ? 0 : go(get_link(v), ch);
  }
  return trie[v].go[c];
}
int tmp_ar[1000000];
void aho_dfs(int node) {
  int v = node;
  int i, j;
  while (1) {
    if (trie[v].elink == -1) {
      i = 1;
      tmp_ar[0] = v;
      while (v = get_link(v)) {
        if (trie[v].leaf) break;
        if (trie[v].elink != -1) {
          v = trie[v].elink;
          break;
        }
        tmp_ar[i] = v;
        i++;
      }
      for (j = 0; j < i; j++) trie[tmp_ar[j]].elink = v;
    } else {
      v = trie[v].elink;
    }
    if (v == 0) break;
  }
  for (i = 0; i < AS; i++) {
    if (trie[node].next[i] != -1) {
      aho_dfs(trie[node].next[i]);
    }
  }
  return;
}
int data[1000000];
int susp[1000000];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ;
  int n, m, i, id, vid, sus;
  cin >> n >> m;
  string s;
  for (i = 0; i < n; i++) {
    cin >> s;
    data[i] = addString(s);
  }
  aho_dfs(0);
  trie[0].mx = -1;
  for (i = 0; i < m; i++) {
    cin >> id;
    if (id == 2) {
      cin >> s;
      int v = 0;
      int tv;
      int mx = -1;
      for (char ch : s) {
        v = go(v, ch);
        if (trie[v].leaf)
          tv = v;
        else
          tv = trie[v].elink;
        do {
          mx = max(mx, trie[tv].mx);
          tv = trie[tv].elink;
        } while (tv);
      }
      cout << mx << '\n';
    } else {
      cin >> vid >> sus;
      vid--;
      trie[data[vid]].st.erase(trie[data[vid]].st.find(susp[vid]));
      susp[vid] = sus;
      trie[data[vid]].st.insert(sus);
      trie[data[vid]].mx = *(--trie[data[vid]].st.end());
    }
  }
}
