#include <bits/stdc++.h>
using namespace std;
template <class T>
using v2d = vector<vector<T> >;
template <class T>
bool uin(T &a, T b) {
  return a > b ? (a = b, true) : false;
}
template <class T>
bool uax(T &a, T b) {
  return a < b ? (a = b, true) : false;
}
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
const int maxN = 3e5 + 10;
const int maxS = 3e5 + 10;
int n, m, idx, a[maxN], id[maxN];
struct Node {
  int nxt[26], par, link, nleaf;
  char ch;
  multiset<int> values;
  Node() : link(-1), nleaf(-1), values() { fill(nxt, nxt + 26, -1); }
} trie[maxS];
int add_string(string &s) {
  int cur = 0;
  for (auto &c : s) {
    char d = c - 'a';
    if (trie[cur].nxt[d] == -1) {
      trie[cur].nxt[d] = ++idx;
      trie[idx].par = cur;
      trie[idx].ch = d;
    }
    cur = trie[cur].nxt[d];
  }
  trie[cur].values.insert(0);
  trie[cur].nleaf = cur;
  return cur;
}
int go(int, char);
int get_link(int cur) {
  if (trie[cur].link == -1) {
    if (cur == 0 || trie[cur].par == 0) {
      trie[cur].link = 0;
    } else {
      trie[cur].link = go(get_link(trie[cur].par), trie[cur].ch);
    }
  }
  return trie[cur].link;
}
int go(int cur, char ch) {
  if (trie[cur].nxt[ch] == -1) {
    trie[cur].nxt[ch] = (cur == 0 ? 0 : go(get_link(cur), ch));
  }
  return trie[cur].nxt[ch];
}
int get_leaf(int cur) {
  if (cur == 0) {
    return 0;
  }
  if (trie[cur].nleaf == -1) {
    trie[cur].nleaf = get_leaf(get_link(cur));
  }
  return trie[cur].nleaf;
}
void solve() {
  cin >> n >> m;
  for (int i = 1; i <= (int)(n); ++i) {
    string s;
    cin >> s;
    id[i] = add_string(s);
  }
  while (m--) {
    int type;
    cin >> type;
    if (type == 1) {
      int i, x;
      cin >> i >> x;
      multiset<int> &st = trie[id[i]].values;
      st.erase(st.find(a[i]));
      st.insert(x);
      a[i] = x;
    } else {
      string q;
      cin >> q;
      int cur = 0, ans = -1;
      for (auto &c : q) {
        cur = go(cur, c - 'a');
        int pos = get_leaf(cur);
        while (pos != 0) {
          uax(ans, *trie[pos].values.rbegin());
          pos = get_leaf(get_link(pos));
        }
      }
      cout << ans << "\n";
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int T = 1;
  while (T--) {
    solve();
  }
  return 0;
}
