#include <bits/stdc++.h>
using namespace std;
function<void(void)> ____ = []() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
};
const int MAXN = 3e5 + 7;
struct AhoCorasick {
  int tot, ch[MAXN][26], fail[MAXN];
  int newnode() {
    tot++;
    memset(ch[tot], 0, sizeof(ch[tot]));
    return tot;
  }
  AhoCorasick() {
    tot = -1;
    newnode();
  }
  int insert(char *s) {
    int u = 0;
    for (int i = 0; s[i]; i++) {
      int c = s[i] - 'a';
      if (!ch[u][c]) ch[u][c] = newnode();
      u = ch[u][c];
    }
    return u;
  }
  vector<int> G[MAXN];
  void buildFail() {
    queue<int> que;
    for (int c = 0; c < 26; c++) {
      int v = ch[0][c];
      if (!v) continue;
      que.push(v);
      fail[v] = 0;
    }
    while (!que.empty()) {
      int u = que.front();
      que.pop();
      for (int c = 0; c < 26; c++) {
        if (!ch[u][c]) {
          ch[u][c] = ch[fail[u]][c];
          continue;
        }
        que.push(ch[u][c]);
        int v = fail[u];
        while (v and !ch[v][c]) v = fail[v];
        fail[ch[u][c]] = ch[v][c];
      }
    }
    for (int i = 1; i <= tot; i++) G[fail[i]].push_back(i);
  }
} aho;
struct SegmentTree {
  int l[MAXN << 2], r[MAXN << 2], maxx[MAXN << 2];
  void build(int L, int R, int rt = 1) {
    l[rt] = L;
    r[rt] = R;
    maxx[rt] = -1;
    if (L + 1 == R) return;
    int mid = (L + R) >> 1;
    build(L, mid, rt << 1);
    build(mid, R, rt << 1 | 1);
  }
  void modify(int pos, int x, int rt = 1) {
    if (l[rt] + 1 == r[rt]) {
      maxx[rt] = x;
      return;
    }
    int mid = (l[rt] + r[rt]) >> 1;
    if (pos < mid)
      modify(pos, x, rt << 1);
    else
      modify(pos, x, rt << 1 | 1);
    maxx[rt] = max(maxx[rt << 1], maxx[rt << 1 | 1]);
  }
  int qmax(int L, int R, int rt = 1) {
    if (L >= r[rt] or l[rt] >= R) return -1;
    if (L <= l[rt] and r[rt] <= R) return maxx[rt];
    return max(qmax(L, R, rt << 1), qmax(L, R, rt << 1 | 1));
  }
} seg;
int idx, dfn[MAXN], top[MAXN], sz[MAXN], son[MAXN], dep[MAXN], par[MAXN];
void firstDfs(int u, int d, int fa) {
  sz[u] = 1;
  dep[u] = d;
  par[u] = fa;
  for (int v : aho.G[u]) {
    firstDfs(v, d + 1, u);
    if (!son[u] or sz[v] > sz[son[u]]) son[u] = v;
  }
}
void secondDfs(int u, int tp) {
  top[u] = tp;
  dfn[u] = ++idx;
  if (son[u]) secondDfs(son[u], tp);
  for (int v : aho.G[u]) {
    if (v == son[u]) continue;
    secondDfs(v, v);
  }
}
int n, m, trienode[MAXN];
set<pair<int, int> > S[MAXN];
char buf[MAXN];
int getmax(int u, int v = 0) {
  int ret = -1;
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) swap(u, v);
    ret = max(ret, seg.qmax(dfn[top[u]], dfn[u] + 1));
    u = par[top[u]];
  }
  if (dep[u] > dep[v]) swap(u, v);
  return max(ret, seg.qmax(dfn[u], dfn[v] + 1));
}
int w[MAXN];
void solve() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%s", buf);
    trienode[i] = aho.insert(buf);
  }
  aho.buildFail();
  firstDfs(0, 0, 0);
  secondDfs(0, 0);
  seg.build(1, MAXN);
  for (int i = 1; i <= n; i++) {
    S[dfn[trienode[i]]].insert(make_pair(0, i));
    seg.modify(dfn[trienode[i]], 0);
    w[i] = 0;
  }
  for (int kase = 1; kase <= m; kase++) {
    int op;
    scanf("%d", &op);
    if (op == 1) {
      int id, x;
      scanf("%d %d", &id, &x);
      S[dfn[trienode[id]]].erase(make_pair(w[id], id));
      w[id] = x;
      S[dfn[trienode[id]]].insert(make_pair(w[id], id));
      seg.modify(dfn[trienode[id]], S[dfn[trienode[id]]].rbegin()->first);
    } else {
      scanf("%s", buf);
      int u = 0, ret = -1;
      for (int i = 0; buf[i]; i++) {
        int c = buf[i] - 'a';
        u = aho.ch[u][c];
        ret = max(ret, getmax(u));
      }
      cout << ret << endl;
    }
  }
}
int main() {
  solve();
  return 0;
}
