#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = 1000000007;
const int K = 26;
struct Vertex {
  int next[K];
  bool leaf = false;
  int p = -1, sz, match = -1;
  char pch;
  int suff_link = -1;
  int end_link = -1;
  int go[K];
  Vertex(int p = -1, char ch = '$', int _sz = 0) : p(p), pch(ch) {
    fill(begin(next), end(next), -1);
    fill(begin(go), end(go), -1);
    sz = _sz;
  }
};
vector<Vertex> trie(1);
const int MAXN = 500010;
int no[MAXN];
void add_string(string const& s, int i) {
  int v = 0;
  for (char ch : s) {
    int c = ch - 'a';
    if (trie[v].next[c] == -1) {
      trie[v].next[c] = trie.size();
      trie.emplace_back(v, ch, trie[v].sz + 1);
    }
    v = trie[v].next[c];
  }
  trie[v].leaf = true;
  no[i] = v;
}
int go(int v, char ch);
int get_suff_link(int v) {
  if (trie[v].suff_link == -1) {
    if (v == 0 || trie[v].p == 0)
      trie[v].suff_link = 0;
    else
      trie[v].suff_link = go(get_suff_link(trie[v].p), trie[v].pch);
  }
  return trie[v].suff_link;
}
int get_end_link(int v) {
  if (trie[v].end_link == -1) {
    if (v == 0 || trie[v].p == 0) {
      trie[v].end_link = 0;
    } else {
      int suff_link = get_suff_link(v);
      if (trie[suff_link].leaf)
        trie[v].end_link = suff_link;
      else
        trie[v].end_link = get_end_link(suff_link);
    }
  }
  return trie[v].end_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_suff_link(v), ch);
  }
  return trie[v].go[c];
}
map<int, int> st[MAXN];
int mx[MAXN];
int sz = 0;
int getMax(int v) {
  int ans = -1;
  while (v != 0) {
    ans = max(ans, mx[v]);
    v = get_end_link(v);
  }
  return ans;
}
int solve(string t) {
  int state = 0;
  int ans = -1;
  for (char c : t) {
    state = go(state, c);
    if (trie[state].leaf)
      ans = max(ans, getMax(state));
    else
      ans = max(ans, getMax(get_end_link(state)));
  }
  return ans;
}
int v[MAXN];
void update(int i, int x) {
  st[no[i]][v[i]]--;
  if (st[no[i]][v[i]] == 0) st[no[i]].erase(v[i]);
  st[no[i]][x]++;
  mx[no[i]] = st[no[i]].rbegin()->first;
  v[i] = x;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    add_string(s, i);
  }
  for (int i = 0; i < n; i++) {
    st[no[i]][0]++;
  }
  for (int i = 0; i < m; i++) {
    int op;
    cin >> op;
    if (op == 1) {
      int p, x;
      cin >> p >> x;
      update(p - 1, x);
    } else {
      string s;
      cin >> s;
      cout << solve(s) << '\n';
    }
  }
  return 0;
}
