#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
const int inf = 1e9 + 10;
int ed[maxn];
multiset<int> st[maxn];
int val[maxn];
struct seg {
  int t[maxn << 2];
  void build(int now, int l, int r) {
    t[now] = -1;
    if (l == r) return;
    build(now << 1, l, ((l + r) >> 1));
    build(now << 1 | 1, ((l + r) >> 1) + 1, r);
  }
  void update(int now, int l, int r, int pos, int val) {
    if (l == r) {
      t[now] = val;
      return;
    }
    if (pos <= ((l + r) >> 1))
      update(now << 1, l, ((l + r) >> 1), pos, val);
    else
      update(now << 1 | 1, ((l + r) >> 1) + 1, r, pos, val);
    t[now] = max(t[now << 1], t[now << 1 | 1]);
  }
  int quary(int now, int l, int r, int L, int R) {
    if (L > R) return -1;
    if (l == L && R == r) return t[now];
    return max(quary(now << 1, l, ((l + r) >> 1), L, min(((l + r) >> 1), R)),
               quary(now << 1 | 1, ((l + r) >> 1) + 1, r,
                     max(((l + r) >> 1) + 1, L), R));
  }
} T;
struct ACautomaton {
  int ch[maxn][30];
  int fail[maxn];
  int tot = 0;
  int cnt[maxn];
  int in[maxn];
  int ans[maxn];
  void insert(string s, int x) {
    int n = s.length();
    int now = 0;
    for (int i = 0; i < n; i++) {
      if (ch[now][s[i] - 'a'])
        now = ch[now][s[i] - 'a'];
      else {
        ch[now][s[i] - 'a'] = ++tot;
        now = tot;
      }
    }
    cnt[now]++;
    ed[x] = now;
  }
  queue<int> q;
  void getfail() {
    for (int i = 0; i < 26; i++)
      if (ch[0][i]) q.push(ch[0][i]), fail[ch[0][i]] = 0;
    while (!q.empty()) {
      int k = q.front();
      q.pop();
      for (int i = 0; i < 26; i++) {
        if (ch[k][i])
          fail[ch[k][i]] = ch[fail[k]][i], q.push(ch[k][i]);
        else
          ch[k][i] = ch[fail[k]][i];
      }
    }
  }
  std::vector<int> v[maxn];
  int vis[maxn];
  void build_tree() {
    for (int i = tot; i >= 1; i--) {
      v[fail[i]].push_back(i);
    }
  }
  int de[maxn], top[maxn], fa[maxn], son[maxn], size[maxn], id[maxn];
  int p = 0;
  void dfs1(int x, int f) {
    de[x] = de[f] + 1;
    size[x] = 1;
    fa[x] = f;
    for (int i : v[x]) {
      dfs1(i, x);
      size[x] += size[i];
      if (size[i] > size[son[x]]) son[x] = i;
    }
  }
  void dfs2(int x, int to) {
    id[x] = ++p;
    top[x] = to;
    if (son[x]) dfs2(son[x], to);
    for (int i : v[x]) {
      if (i == son[x]) continue;
      dfs2(i, i);
    }
  }
  void build() {
    build_tree();
    dfs1(0, 0);
    dfs2(0, 0);
    T.build(1, 1, p);
  }
  void update(int now, int val) { T.update(1, 1, p, id[now], val); }
  int quary(int now) {
    int ans = -1;
    while (now) {
      ans = max(ans, T.quary(1, 1, p, id[top[now]], id[now]));
      now = fa[top[now]];
    }
    return ans;
  }
  void ask(string s) {
    int len = s.length();
    int ans = -1;
    int now = 0;
    for (int i = 0; i < len; i++) {
      while (now && ch[now][s[i] - 'a'] == 0) now = fail[now];
      if (ch[now][s[i] - 'a']) now = ch[now][s[i] - 'a'];
      if (now) ans = max(ans, quary(now));
    }
    printf("%d\n", ans);
  }
} AC;
string s;
int n, q;
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; i++) cin >> s, AC.insert(s, i);
  AC.getfail();
  AC.build();
  for (int i = 1; i <= n; i++) st[ed[i]].insert(0), AC.update(ed[i], 0);
  for (int i = 1, op; i <= q; i++) {
    scanf("%d", &op);
    int x, y;
    if (op == 1) {
      scanf("%d%d", &x, &y);
      st[ed[x]].erase(st[ed[x]].find(val[x]));
      val[x] = y;
      st[ed[x]].insert(val[x]);
      AC.update(ed[x], (*st[ed[x]].rbegin()));
    } else {
      cin >> s;
      AC.ask(s);
    }
  }
  return 0;
}
