#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int maxm = 6e5 + 10;
const int inf = 0x3f3f3f3f;
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c,
                                       qu[55];
int f, qr;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char x) {
  *oS++ = x;
  if (oS == oT) flush();
}
template <typename A>
inline bool read(A &x) {
  for (f = 1, c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-')
      f = -1;
    else if (c == EOF)
      return 0;
  for (x = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    x = x * 10 + (c & 15);
  x *= f;
  return 1;
}
inline bool read(char &x) {
  while ((x = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                           (iS == iT ? EOF : *iS++))
                        : *iS++)) == ' ' ||
         x == '\n' || x == '\r')
    ;
  return x != EOF;
}
inline bool read(char *x) {
  while ((*x = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                            (iS == iT ? EOF : *iS++))
                         : *iS++)) == '\n' ||
         *x == ' ' || *x == '\r')
    ;
  if (*x == EOF) return 0;
  while (!(*x == '\n' || *x == ' ' || *x == '\r' || *x == EOF))
    *(++x) = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                          (iS == iT ? EOF : *iS++))
                       : *iS++);
  *x = 0;
  return 1;
}
template <typename A, typename... B>
inline bool read(A &x, B &...y) {
  return read(x) && read(y...);
}
template <typename A>
inline bool write(A x) {
  if (!x) putc('0');
  if (x < 0) putc('-'), x = -x;
  while (x) qu[++qr] = x % 10 + '0', x /= 10;
  while (qr) putc(qu[qr--]);
  return 0;
}
inline bool write(char x) {
  putc(x);
  return 0;
}
inline bool write(const char *x) {
  while (*x) {
    putc(*x);
    ++x;
  }
  return 0;
}
inline bool write(char *x) {
  while (*x) {
    putc(*x);
    ++x;
  }
  return 0;
}
template <typename A, typename... B>
inline bool write(A x, B... y) {
  return write(x) || write(y...);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io ::putc;
using io ::read;
using io ::write;
string str[maxm];
char s[maxm];
int pt[maxm], trie[maxm][27], flag[maxm], a[maxm], fail[maxm], last[maxm];
int cnt;
multiset<int> st[maxm];
vector<int> v;
void insert(int x) {
  int rt = 0;
  int len = strlen(s + 1);
  for (int i = 1; i <= len; i++) {
    int nxt = s[i] - 'a';
    if (!trie[rt][nxt]) trie[rt][nxt] = ++cnt;
    rt = trie[rt][nxt];
  }
  flag[rt] = 1;
  st[rt].insert(0);
  pt[x] = rt;
}
void getfail() {
  queue<int> q;
  for (int i = 0; i < 26; i++) {
    if (trie[0][i]) {
      fail[trie[0][i]] = 0;
      q.push(trie[0][i]);
    }
  }
  while (!q.empty()) {
    int now = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      if (trie[now][i]) {
        fail[trie[now][i]] = trie[fail[now]][i];
        last[trie[now][i]] = flag[fail[trie[now][i]]]
                                 ? fail[trie[now][i]]
                                 : last[fail[trie[now][i]]];
        q.push(trie[now][i]);
      } else
        trie[now][i] = trie[fail[now]][i];
    }
  }
}
int query() {
  int now = 0, ans = -1;
  int len = strlen(s + 1);
  for (int i = 1; i <= len; i++) {
    now = trie[now][s[i] - 'a'];
    int id = flag[now] ? now : last[now];
    while (id && flag[id] != -1) {
      ans = max(ans, *st[id].rbegin());
      flag[id] = -1;
      v.push_back(id);
      id = last[id];
    }
  }
  for (int id : v) flag[id] = 1;
  v.clear();
  return ans;
}
int main() {
  int n, m;
  read(n, m);
  for (int i = 1; i <= n; i++) {
    read(s + 1);
    insert(i);
  }
  getfail();
  while (m--) {
    int op;
    read(op);
    if (op == 1) {
      int id, x;
      read(id, x);
      st[pt[id]].erase(st[pt[id]].lower_bound(a[id]));
      a[id] = x;
      st[pt[id]].insert(x);
    }
    if (op == 2) {
      read(s + 1);
      printf("%d\n", query());
    }
  }
  return 0;
}
