#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const long long INF = 1e18;
const double eps = 1e-10;
const double pi = acos(-1);
mt19937 mrand(chrono::high_resolution_clock::now().time_since_epoch().count());
template <class T>
inline void upmin(T &x, T y) {
  x = x > y ? y : x;
}
template <class T>
inline void upmax(T &x, T y) {
  x = x < y ? y : x;
}
const int maxn = 6e5 + 233;
vector<int> G[maxn * 2];
struct SAM {
  int len[maxn * 2];
  int f[maxn * 2];
  int cnt[maxn * 2];
  int ch[maxn * 2][26];
  int sz;
  int last;
  void init() {
    last = sz = 1;
    f[1] = len[1] = 0;
    memset(ch[1], 0, sizeof(ch[1]));
  }
  void add(int c) {
    if (ch[last][c] && len[ch[last][c]] == len[last] + 1) {
      last = ch[last][c];
      return;
    }
    bool ok = 0;
    int x = ++sz;
    len[x] = len[last] + 1;
    int p;
    for (p = last; p && !ch[p][c]; p = f[p]) ch[p][c] = x;
    if (!p)
      f[x] = 1, cnt[1]++;
    else {
      int q = ch[p][c];
      if (len[x] == len[p] + 1) ok = 1;
      if (len[p] + 1 == len[q])
        f[x] = q, cnt[q]++;
      else {
        int nq = ++sz;
        len[nq] = len[p] + 1;
        f[nq] = f[q];
        memcpy(ch[nq], ch[q], sizeof(ch[q]));
        for (; p && ch[p][c] == q; p = f[p]) ch[p][c] = nq;
        f[q] = f[x] = nq;
        cnt[nq] += 2;
        if (ok)
          last = nq;
        else
          last = x;
        return;
      }
    }
    last = x;
  }
  void build() {
    for (int i = 2; i <= sz; i++) G[f[i]].emplace_back(i);
  }
} sam;
int f[maxn * 2], son[maxn * 2], d[maxn * 2], sz[maxn * 2], top[maxn * 2],
    in[maxn * 2], rk[maxn * 2], out[maxn * 2];
int idx;
void dfs1(int u, int fa) {
  f[u] = fa;
  d[u] = d[fa] + 1;
  sz[u] = 1;
  for (auto &v : G[u]) {
    if (v == fa) continue;
    dfs1(v, u);
    sz[u] += sz[v];
    if (sz[v] > sz[son[u]]) son[u] = v;
  }
}
void dfs2(int u, int t) {
  top[u] = t;
  in[u] = ++idx;
  rk[idx] = u;
  if (son[u]) dfs2(son[u], t);
  for (auto &v : G[u]) {
    if (v == f[u] || v == son[u]) continue;
    dfs2(v, v);
  }
  out[u] = idx;
}
template <class T>
struct Segment_Tree {
  multiset<int> s[maxn * 2];
  int mx[maxn << 3];
  void up(int o) { mx[o] = max(mx[o << 1], mx[o << 1 | 1]); }
  void build(int o, int l, int r) {
    if (l == r) {
      mx[o] = -1;
      s[l].insert(1);
      return;
    }
    int mid = l + r >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
    up(o);
  }
  void upd(int o, int tl, int tr, int l, int r, int v, bool ok) {
    if (tr < l || r < tl) return;
    if (l <= tl && tr <= r) {
      if (ok) {
        s[l].insert(-v);
        mx[o] = -(*s[l].begin());
      } else
        s[l].erase(s[l].find(-v));
      return;
    }
    int mid = (tl + tr) >> 1;
    upd(o << 1, tl, mid, l, r, v, ok);
    upd(o << 1 | 1, mid + 1, tr, l, r, v, ok);
    up(o);
  }
  int qmax(int o, int tl, int tr, int l, int r) {
    if (tr < l || r < tl) return -inf;
    if (l <= tl && tr <= r) return mx[o];
    int mid = (tl + tr) >> 1;
    return max(qmax(o << 1, tl, mid, l, r),
               qmax(o << 1 | 1, mid + 1, tr, l, r));
  }
};
Segment_Tree<int> tr;
string s[maxn], t[maxn];
int op[maxn], id[maxn], val[maxn];
int n, m;
int pos[maxn];
int now[maxn];
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(10);
  cin >> n >> m;
  sam.init();
  for (int i = 1; i <= n; i++) {
    sam.last = 1;
    cin >> s[i];
    for (int j = 0; j < s[i].size(); j++) {
      sam.add(s[i][j] - 'a');
    }
    pos[i] = sam.last;
  }
  for (int i = 1; i <= m; i++) {
    cin >> op[i];
    if (op[i] == 1)
      cin >> id[i] >> val[i];
    else {
      cin >> t[i];
      sam.last = 1;
      for (int j = 0; j < t[i].size(); j++) {
        sam.add(t[i][j] - 'a');
      }
    }
  }
  sam.build();
  dfs1(1, 0);
  dfs2(1, 1);
  tr.build(1, 1, idx);
  for (int i = 1; i <= n; i++) {
    tr.upd(1, 1, sam.sz, in[pos[i]], in[pos[i]], 0, 1);
    now[i] = 0;
  }
  for (int i = 1; i <= m; i++) {
    if (op[i] == 1) {
      tr.upd(1, 1, idx, in[pos[id[i]]], in[pos[id[i]]], now[id[i]], 0);
      now[id[i]] = val[i];
      tr.upd(1, 1, idx, in[pos[id[i]]], in[pos[id[i]]], now[id[i]], 1);
    } else {
      int res = -1;
      int p = 1;
      for (int j = 0; j < t[i].size(); j++) {
        int c = t[i][j] - 'a';
        p = sam.ch[p][c];
        int np = p;
        while (top[np] != top[1]) {
          upmax(res, tr.qmax(1, 1, idx, in[top[np]], in[np]));
          np = f[top[np]];
        }
        upmax(res, tr.qmax(1, 1, idx, in[1], in[np]));
      }
      cout << res << '\n';
    }
  }
  return 0;
}
