#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
int n, Q;
int ans[N], tp[N];
const int M = 15000005;
struct Tree {
  int ls[M], rs[M], tg[M], nd, la = 0;
  Tree() { memset(tg, -1, sizeof(tg)); }
  void change(int &nk, int k, int l, int r, int x, int y, int v) {
    if (k <= nd) {
      nk = ++nd;
      tg[nk] = tg[k];
      ls[nk] = ls[k];
      rs[nk] = rs[k];
    } else
      nk = k;
    if (x <= l && r <= y) return tg[nk] = max(tg[nk], v), void(0);
    int mid = (l + r) / 2;
    if (x <= mid) change(ls[nk], ls[k], l, mid, x, y, v);
    if (y > mid) change(rs[nk], rs[k], mid + 1, r, x, y, v);
  }
  int ask(int k, int l, int r, int p) {
    if (!k) return -1;
    if (l == r) return tg[k];
    int mid = (l + r) / 2;
    if (p <= mid) return max(ask(ls[k], l, mid, p), tg[k]);
    return max(ask(rs[k], mid + 1, r, p), tg[k]);
  }
} TR;
struct AC_automaton {
  int ch[N][26], pos[N];
  int q[N], fa[N], nd = 1;
  vector<pair<int, int> > op[N];
  vector<int> opp[N];
  vector<int> e[N];
  vector<int> vQ[N];
  char s[N];
  void build() {
    for (int i = (int)(1); i <= (int)(n); i++) {
      scanf("%s", s + 1);
      int x = 1;
      for (int j = 1; s[j]; j++) {
        if (!ch[x][s[j] - 'a']) ch[x][s[j] - 'a'] = ++nd;
        x = ch[x][s[j] - 'a'];
      }
      opp[x].push_back(i);
      op[i].push_back(pair<int, int>(0, 0));
    }
    int h = 0, t = 0;
    for (int i = (int)(0); i <= (int)(25); i++)
      if (!ch[1][i])
        ch[1][i] = 1;
      else {
        fa[ch[1][i]] = 1;
        q[++t] = ch[1][i];
      }
    while (h != t) {
      int x = q[++h];
      for (int i = (int)(0); i <= (int)(25); i++)
        if (!ch[x][i])
          ch[x][i] = ch[fa[x]][i];
        else {
          fa[ch[x][i]] = ch[fa[x]][i];
          q[++t] = ch[x][i];
        }
    }
    for (int i = (int)(2); i <= (int)(nd); i++) e[fa[i]].push_back(i);
  }
  void insertC(int x, int y, int i) { op[x].push_back(pair<int, int>(y, i)); }
  int sum = 0;
  void insertQ(int id) {
    scanf("%s", s + 1);
    int l = strlen(s + 1);
    assert((sum += l) <= 300000);
    int x = 1;
    for (int i = 1; i <= l; ++i) {
      x = ch[x][s[i] - 'a'];
      vQ[x].push_back(id);
    }
  }
  void dfs(int x, int rt) {
    TR.la = TR.nd;
    for (auto p : opp[x])
      for (int i = 0; i < op[p].size(); i++) {
        int l = op[p][i].second;
        int r = (i == op[p].size() - 1 ? Q : op[p][i + 1].second - 1);
        TR.change(rt, rt, 0, Q, l, r, op[p][i].first);
      }
    int tmp = TR.nd;
    for (auto i : vQ[x]) ans[i] = max(ans[i], TR.ask(rt, 0, Q, i));
    for (auto i : e[x]) {
      dfs(i, rt);
      TR.nd = tmp;
    }
  }
  void solve() { dfs(1, 0); }
} AC;
int main() {
  scanf("%d%d", &n, &Q);
  AC.build();
  for (int i = (int)(1); i <= (int)(Q); i++) {
    ans[i] = -1;
    scanf("%d", &tp[i]);
    if (tp[i] == 1) {
      int x, y;
      scanf("%d%d", &x, &y);
      AC.insertC(x, y, i);
    } else
      AC.insertQ(i);
  }
  AC.solve();
  for (int i = (int)(1); i <= (int)(Q); i++)
    if (tp[i] == 2) printf("%d\n", ans[i]);
}
