#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f, mod = 1e9 + 7, N = 3e5 + 10;
template <typename T>
inline void rd_(T &x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= f;
}
int n, m, tr[N][26], tot, f[N], id[N], v[N], t[N << 2];
char ch[N];
priority_queue<pair<int, int> > q[N];
vector<int> g[N];
void insert_(char *ch, int tim) {
  int pos = 0;
  for (int i = 1; ch[i]; i++) {
    if (!tr[pos][ch[i] - 'a']) tr[pos][ch[i] - 'a'] = ++tot;
    pos = tr[pos][ch[i] - 'a'];
  }
  id[tim] = pos;
}
int son[N], siz[N], st[N], cnt = -1, top[N];
void update_(int o, int l, int r, int x, int k) {
  if (l == r) {
    t[o] = k;
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    update_(o << 1, l, mid, x, k);
  else
    update_(o << 1 | 1, mid + 1, r, x, k);
  t[o] = max(t[o << 1], t[o << 1 | 1]);
}
int query_(int o, int l, int r, int x, int y) {
  if (x <= l && r <= y) return t[o];
  int res = -1, mid = (l + r) >> 1;
  if (x <= mid) res = max(res, query_(o << 1, l, mid, x, y));
  if (mid < y) res = max(res, query_(o << 1 | 1, mid + 1, r, x, y));
  return res;
}
int cal_(int u, int res = -1) {
  while (top[u])
    res = max(res, query_(1, 0, tot, st[top[u]], st[u])), u = f[top[u]];
  return max(res, query_(1, 0, tot, st[0], st[u]));
}
void solve_(char *ch) {
  int pos = 0, ans = -1;
  for (int i = 1; ch[i]; i++) {
    pos = tr[pos][ch[i] - 'a'];
    ans = max(ans, cal_(pos));
  }
  printf("%d\n", ans);
}
void dfs1_(int u) {
  siz[u] = 1, son[u] = tot + 1;
  for (int v, i = 0; i < (int)g[u].size(); i++) {
    v = g[u][i];
    dfs1_(v), siz[u] += siz[v];
    if (siz[son[u]] < siz[v]) son[u] = v;
  }
}
void dfs2_(int u, int topf) {
  top[u] = topf, st[u] = ++cnt;
  if (son[u] != tot + 1) dfs2_(son[u], topf);
  for (int v, i = 0; i < (int)g[u].size(); i++) {
    v = g[u][i];
    if (son[u] != v) dfs2_(v, v);
  }
}
void build_() {
  queue<int> q;
  for (int i = (0); i <= (25); i++)
    if (tr[0][i]) q.push(tr[0][i]), g[0].push_back(tr[0][i]);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = (0); i <= (25); i++) {
      int v = tr[u][i];
      if (v)
        f[v] = tr[f[u]][i], q.push(v), g[f[v]].push_back(v);
      else
        tr[u][i] = tr[f[u]][i];
    }
  }
  dfs1_(0);
  dfs2_(0, 0);
  memset(t, -1, sizeof(t));
  for (int i = (1); i <= (n); i++) update_(1, 0, tot, st[id[i]], 0);
}
int main() {
  rd_(n), rd_(m);
  for (int i = (1); i <= (n); i++) {
    scanf("%s", ch + 1);
    insert_(ch, i);
    q[id[i]].push(pair<int, int>(0, i));
  }
  build_();
  for (int op, x, k, i = 1; i <= m; i++) {
    rd_(op);
    if (op == 1) {
      rd_(x), rd_(k), v[x] = k;
      q[id[x]].push(pair<int, int>(k, x));
      while (v[q[id[x]].top().second] != q[id[x]].top().first) q[id[x]].pop();
      update_(1, 0, tot, st[id[x]], q[id[x]].top().first);
    } else {
      scanf("%s", ch + 1);
      solve_(ch);
    }
  }
  return 0;
}
