#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 5;
const int MAXM = 2e6 + 5;
char s[MAXN];
vector<int> v[MAXN];
multiset<int> ss[MAXN];
int trie[MAXN][26], fail[MAXN];
int pos[MAXN], dat[MAXN], siz[MAXN];
int fa[MAXN], dep[MAXN], top[MAXN], dfn[MAXN];
int rev[MAXN], son[MAXN], dfn_cnt, root, tree_cnt, tot;
int ls[MAXM], rs[MAXM], val[MAXM];
inline int read() {
  int x = 0;
  char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
inline void Max(int &x, int y) {
  if (x < y) x = y;
}
inline void insert(char *s, int id) {
  int len = strlen(s + 1), cur = 0;
  for (int i = 1; i <= len; i++) {
    int ch = s[i] - 'a';
    if (!trie[cur][ch]) trie[cur][ch] = ++tot;
    cur = trie[cur][ch];
  }
  pos[id] = cur, ss[cur].insert(dat[id]);
}
inline void build(int x = 0) {
  queue<int> q;
  for (int i = 0; i < 26; i++)
    if (trie[0][i]) q.push(trie[0][i]), v[0].push_back(trie[0][i]);
  while (!q.empty()) {
    x = q.front(), q.pop();
    for (int i = 0; i < 26; i++) {
      int y = trie[x][i];
      if (y) {
        fail[y] = trie[fail[x]][i];
        v[fail[y]].push_back(y), q.push(y);
      } else
        trie[x][i] = trie[fail[x]][i];
    }
  }
}
void dfs_son(int x, int fath) {
  siz[x] = 1;
  fa[x] = fath;
  dep[x] = dep[fath] + 1;
  for (auto y : v[x]) {
    dfs_son(y, x), siz[x] += siz[y];
    if (son[x] || siz[y] > siz[son[x]]) son[x] = y;
  }
}
void dfs_chain(int x, int tp) {
  top[x] = tp;
  rev[dfn[x] = ++dfn_cnt] = x;
  if (son[x]) dfs_chain(son[x], tp);
  for (auto y : v[x]) {
    if (y == son[x]) continue;
    dfs_chain(y, y);
  }
}
inline void pushup(int cur) { val[cur] = max(val[ls[cur]], val[rs[cur]]); }
void build(int l, int r, int &cur) {
  cur = ++tree_cnt;
  if (l == r) {
    val[cur] = *--ss[rev[l]].end();
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, ls[cur]);
  build(mid + 1, r, rs[cur]);
  pushup(cur);
}
void modify(int l, int r, int pos, int to, int cur) {
  if (l == r) return val[cur] = to, void();
  int mid = (l + r) >> 1;
  if (pos <= mid)
    modify(l, mid, pos, to, ls[cur]);
  else
    modify(mid + 1, r, pos, to, rs[cur]);
  pushup(cur);
}
int query(int l, int r, int ql, int qr, int cur) {
  if (ql <= l && qr >= r) return val[cur];
  int mid = (l + r) >> 1;
  if (ql > mid) return query(mid + 1, r, ql, qr, rs[cur]);
  if (qr <= mid) return query(l, mid, ql, qr, ls[cur]);
  return max(query(l, mid, ql, qr, ls[cur]),
             query(mid + 1, r, ql, qr, rs[cur]));
}
inline int query(int x) {
  int ans = -1;
  while (top[x]) {
    Max(ans, query(1, dfn_cnt, dfn[top[x]], dfn[x], root));
    x = fa[top[x]];
  }
  return max(ans, query(1, dfn_cnt, 1, dfn[x], root));
}
inline int query(char *s) {
  int len = strlen(s + 1), cur = 0, ans = -1;
  for (int i = 1; i <= len; i++) {
    int ch = s[i] - 'a';
    cur = trie[cur][ch];
    Max(ans, query(cur));
  }
  return ans;
}
int main() {
  int n = read(), m = read();
  for (int i = 1; i <= n; i++) {
    scanf("%s", s + 1);
    insert(s, i);
  }
  for (int i = 0; i <= tot; i++) ss[i].insert(-1);
  build();
  dfs_son(0, 0);
  dfs_chain(0, 0);
  build(1, dfn_cnt, root);
  while (m--) {
    int opt = read();
    if (opt == 1) {
      int id = read(), x = read();
      ss[pos[id]].erase(ss[pos[id]].find(dat[id]));
      ss[pos[id]].insert(dat[id] = x);
      modify(1, dfn_cnt, dfn[pos[id]], *--ss[pos[id]].end(), root);
    } else {
      scanf("%s", s + 1);
      printf("%d\n", query(s));
    }
  }
  return 0;
}
