#include <bits/stdc++.h>
using namespace std;
struct segTree {
  vector<int> t;
  int maxN;
  void init(int n) { maxN = n, t.resize(2 * n, -1); }
  void update(int poz, int val) {
    for (t[poz += maxN] = val; poz > 1; poz >>= 1)
      t[poz >> 1] = max(t[poz], t[poz ^ 1]);
  }
  int ask(int l, int r) {
    int ans = -1;
    for (l += maxN, r += maxN; l < r; l >>= 1, r >>= 1) {
      if (l & 1) ans = max(ans, t[l++]);
      if (r & 1) ans = max(ans, t[--r]);
    }
    return ans;
  }
};
struct node {
  int suff = -1, p = -1;
  ;
  int val = -1, cnt = 1;
  vector<int> to, back, v;
  bool leaf = false;
  char c;
  multiset<int> s;
  segTree* t;
  int poz = 0, start = -1, last = 0, need = 0;
  node(int pater, char k) {
    p = pater, c = k;
    to.resize(26, -1);
  }
};
vector<node> trie = {node(-1, '0')};
int add(string s, int x) {
  int curr = 0;
  for (char& c : s) {
    if (trie[curr].to[c - 'a'] == -1) {
      trie[curr].to[c - 'a'] = trie.size();
      trie.push_back(node(curr, c));
    }
    curr = trie[curr].to[c - 'a'];
  }
  trie[curr].leaf = true;
  return curr;
}
int go(int v, char c);
int suff(int v) {
  if (trie[v].suff == -1) {
    if (v == 0 || trie[v].p == 0)
      trie[v].suff = 0;
    else
      trie[v].suff = go(suff(trie[v].p), trie[v].c);
    if (v != 0) trie[trie[v].suff].back.push_back(v);
  }
  return trie[v].suff;
}
int go(int v, char c) {
  if (trie[v].to[c - 'a'] == -1)
    trie[v].to[c - 'a'] = (v == 0 ? 0 : go(suff(v), c));
  return trie[v].to[c - 'a'];
}
void dfs(int curr, int last) {
  if (trie[curr].leaf) trie[last].v.push_back(curr), last = curr;
  trie[curr].last = last;
  for (int& to : trie[curr].back) dfs(to, last);
}
int cnt(int curr) {
  bool problem = false;
  for (int& to : trie[curr].v) {
    trie[curr].cnt += cnt(to);
    trie[curr].need = max(trie[curr].need, trie[to].cnt);
  }
  return trie[curr].cnt;
}
void assign(int v, int start, segTree* t = new segTree(), int d = 0) {
  trie[v].t = t, trie[v].poz = d, trie[v].start = start;
  int need = trie[v].need;
  bool was = false;
  for (int& to : trie[v].v) {
    if (trie[to].cnt == need && !was)
      assign(to, start, t, d + 1), was = true;
    else
      assign(to, v);
  }
  if (!was) t->init(d + 1);
}
void update(int v, int x, int val) {
  trie[v].s.insert(val);
  val = *trie[v].s.rbegin();
  trie[v].t->update(trie[v].poz, val);
  trie[v].val = val;
}
int ask(int v) {
  int ans = -1;
  while (v > 0) {
    if (trie[v].poz != 0)
      ans = max(ans, trie[v].t->ask(0, trie[v].poz + 1));
    else
      ans = max(ans, trie[v].val);
    v = trie[v].start;
  }
  return ans;
}
int main() {
  cin.sync_with_stdio(false);
  cout.sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  vector<int> at(n);
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    at[i] = add(s, i);
  }
  for (int i = 0; i < trie.size(); i++) suff(i);
  dfs(0, 0);
  cnt(0);
  assign(0, -1);
  vector<int> v(n, 0);
  for (int i = 0; i < n; i++) update(at[i], i, 0);
  while (m--) {
    int x;
    cin >> x;
    if (x == 2) {
      string s;
      cin >> s;
      int ans = -1, curr = 0;
      for (char& c : s) {
        curr = go(curr, c);
        ans = max(ans, ask(trie[curr].last));
      }
      cout << ans << "\n";
    } else {
      int p, val;
      cin >> p >> val;
      trie[at[p - 1]].s.erase(trie[at[p - 1]].s.find(v[p - 1]));
      update(at[p - 1], p - 1, val);
      v[p - 1] = val;
    }
  }
}
