#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
vector<int> G[maxn];
int id[maxn];
struct SEG {
  int ma[maxn << 2];
  SEG() { memset(ma, -1, sizeof ma); }
  void update(int rt, int pos, int l, int r, int val) {
    if (l == r) {
      ma[rt] = val;
      return;
    }
    int m = (l + r) >> 1;
    if (m >= pos)
      update(rt << 1, pos, l, m, val);
    else
      update(rt << 1 | 1, pos, m + 1, r, val);
    ma[rt] = max(ma[rt << 1], ma[rt << 1 | 1]);
  }
  int query(int rt, int L, int R, int l, int r) {
    if (L <= l && r <= R) return ma[rt];
    int m = (l + r) >> 1;
    int ret = -1;
    if (m >= L) ret = max(ret, query(rt << 1, L, R, l, m));
    if (m < R) ret = max(ret, query(rt << 1 | 1, L, R, m + 1, r));
    return ret;
  }
} seg;
struct TREE {
  int dfn[maxn], siz[maxn], son[maxn], top[maxn], fa[maxn], o = 0;
  void dfs(int rt, int p) {
    fa[rt] = p;
    siz[rt] = 0;
    son[rt] = -1;
    for (int x : G[rt]) {
      if (x == p) continue;
      dfs(x, rt);
      siz[rt] += siz[x] + 1;
      if (son[rt] == -1 || siz[son[rt]] < siz[x]) son[rt] = x;
    }
  }
  void dfs2(int rt, int p, int tp) {
    dfn[rt] = ++o;
    top[rt] = tp;
    if (son[rt] != -1) dfs2(son[rt], rt, tp);
    for (int x : G[rt]) {
      if (x == p || x == son[rt]) continue;
      dfs2(x, rt, x);
    }
  }
  int query(int rt) {
    int ret = -1;
    while (rt != -1) {
      int tp = top[rt];
      ret = max(ret, seg.query(1, dfn[tp], dfn[rt], 1, maxn - 1));
      rt = fa[tp];
    }
    return ret;
  }
} tree;
multiset<int> S[maxn];
struct ACAM {
  int nxt[maxn][26], fail[maxn], o = 0;
  void insert(char* s, int x) {
    int rt = 0;
    for (int i = 0; s[i]; i++) {
      int c = s[i] - 'a';
      if (!nxt[rt][c]) nxt[rt][c] = ++o;
      rt = nxt[rt][c];
    }
    id[x] = rt;
  }
  void build() {
    queue<int> Q;
    for (int i = 0; i < 26; i++)
      if (nxt[0][i]) {
        G[0].push_back(nxt[0][i]);
        Q.push(nxt[0][i]);
      }
    while (!Q.empty()) {
      int x = Q.front();
      Q.pop();
      for (int i = 0; i < 26; i++) {
        if (nxt[x][i]) {
          fail[nxt[x][i]] = nxt[fail[x]][i];
          Q.push(nxt[x][i]);
          G[nxt[fail[x]][i]].push_back(nxt[x][i]);
        } else
          nxt[x][i] = nxt[fail[x]][i];
      }
    }
  }
  int query(char* s) {
    int rt = 0;
    int ret = -1;
    for (int i = 0; s[i]; i++) {
      rt = nxt[rt][s[i] - 'a'];
      int tmp = tree.query(rt);
      ret = max(ret, tmp);
    }
    return ret;
  }
} ac;
char s[maxn];
int raw[maxn];
int main(void) {
  int n, q;
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; i++) {
    scanf("%s", s);
    ac.insert(s, i);
  }
  ac.build();
  tree.dfs(0, -1);
  tree.dfs2(0, -1, 0);
  for (int i = 1; i <= n; i++) {
    int rt = id[i];
    S[rt].insert(0);
    seg.update(1, tree.dfn[rt], 1, maxn - 1, 0);
  }
  while (q--) {
    int op;
    scanf("%d", &op);
    if (op == 1) {
      int pos, val;
      scanf("%d%d", &pos, &val);
      int rt = id[pos];
      S[rt].erase(S[rt].find(raw[pos]));
      raw[pos] = val;
      S[rt].insert(val);
      seg.update(1, tree.dfn[rt], 1, maxn - 1, *S[rt].rbegin());
    } else {
      scanf("%s", s);
      int ans = ac.query(s);
      printf("%d\n", ans);
    }
  }
}
