#include <bits/stdc++.h>
using namespace std;
const long long inf = (long long)1e18;
const long long mod = (long long)1e9 + 7;
const double eps = (double)1e-9;
const double pi = acos(-1.0);
const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};
const int N = 300500;
char s[N];
vector<int> g[N];
multiset<int> vals[N];
int n, q, a[N], subtree[N], t[N << 2];
int sz, nxt[N][26], p[N], pr[N], ver[N], link[N];
inline void add(int id) {
  int v = 0, m = (int)strlen(s + 1);
  for (int i = 1; i <= m; i++) {
    int c = s[i] - 'a';
    if (nxt[v][c] == -1) {
      nxt[v][c] = ++sz;
      p[sz] = v;
      pr[sz] = c;
    }
    v = nxt[v][c];
  }
  ver[id] = v;
  vals[v].insert(0);
}
int getnxt(int v, int c);
int getlink(int v) {
  if (link[v] != -1) return link[v];
  if (!v || !p[v]) return link[v] = 0;
  return link[v] = getnxt(getlink(p[v]), pr[v]);
}
int getnxt(int v, int c) {
  if (nxt[v][c] != -1) return nxt[v][c];
  if (!v) return nxt[v][c] = 0;
  return nxt[v][c] = getnxt(getlink(v), c);
}
void dfs(int v, int pr = -1) {
  subtree[v] = 1;
  for (auto to : g[v]) {
    if (to == pr) continue;
    dfs(to, v);
    subtree[v] += subtree[to];
  }
}
int ptr, ar[N], pos[N], pred[N], up[N];
void hld(int v, int pr = -1) {
  ar[++ptr] = v;
  pos[v] = ptr;
  pred[v] = pr;
  for (auto to : g[v]) {
    if (to == pr) continue;
    if (subtree[to] + subtree[to] >= subtree[v]) {
      up[to] = up[v];
      hld(to, v);
    }
  }
  for (auto to : g[v]) {
    if (to == pr) continue;
    if (subtree[to] + subtree[to] < subtree[v]) {
      up[to] = to;
      hld(to, v);
    }
  }
}
void build(int v, int l, int r) {
  if (l == r) {
    t[v] = (vals[ar[r]].empty() ? -1 : *vals[ar[r]].rbegin());
    return;
  }
  int mid = (l + r) >> 1;
  build(v << 1, l, mid);
  build(v << 1 | 1, mid + 1, r);
  t[v] = max(t[v << 1], t[v << 1 | 1]);
}
void upd(int v, int l, int r, int pos) {
  if (l == r) {
    t[v] = (vals[ar[r]].empty() ? -1 : *vals[ar[r]].rbegin());
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid)
    upd(v << 1, l, mid, pos);
  else
    upd(v << 1 | 1, mid + 1, r, pos);
  t[v] = max(t[v << 1], t[v << 1 | 1]);
}
int get(int v, int l, int r, int lx, int rx) {
  if (rx < l || r < lx) return -1;
  if (lx <= l && r <= rx) return t[v];
  int mid = (l + r) >> 1;
  return max(get(v << 1, l, mid, lx, rx), get(v << 1 | 1, mid + 1, r, lx, rx));
}
inline void setUpd(int v, int was, int now) {
  vals[v].erase(vals[v].find(was));
  vals[v].insert(now);
}
inline int hldGet(int v) {
  int res = get(1, 1, ptr, pos[up[v]], pos[v]);
  v = pred[up[v]];
  while (v != -1) {
    res = max(res, get(1, 1, ptr, pos[up[v]], pos[v]));
    v = pred[up[v]];
  }
  return res;
}
int main() {
  memset(nxt, -1, sizeof(nxt));
  memset(link, -1, sizeof(link));
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; i++) {
    scanf("%s", s + 1);
    add(i);
  }
  for (int i = 1; i <= sz; i++) g[getlink(i)].push_back(i);
  dfs(0);
  hld(0);
  build(1, 1, ptr);
  while (q--) {
    int tp;
    scanf("%d", &tp);
    if (tp == 1) {
      int id, val;
      scanf("%d %d", &id, &val);
      setUpd(ver[id], a[id], val);
      upd(1, 1, ptr, pos[ver[id]]);
      a[id] = val;
    } else {
      scanf("%s", s + 1);
      int v = 0, m = (int)strlen(s + 1), res = -1;
      for (int i = 1; i <= m; i++) {
        v = getnxt(v, s[i] - 'a');
        res = max(res, hldGet(v));
      }
      printf("%d\n", res);
    }
  }
  return 0;
}
