#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 5;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;
const long long llINF = 0x3f3f3f3f3f3f3f3f;
long long make_compiler_happy() { return INF & maxn & mod & llINF; }
long long fpow(long long a, long long b) {
  long long res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
long long inv(long long x) { return fpow(x, mod - 2); }
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
const int maxch = 3e5 + 5;
const int alpha_size = 26;
int n;
int segmax[maxn * 4];
void upd(int o, int l, int r, int x, int v) {
  if (l == r) {
    segmax[o] = v;
    return;
  }
  if (x <= (l + r) / 2)
    upd(o * 2, l, (l + r) / 2, x, v);
  else
    upd(o * 2 + 1, (l + r) / 2 + 1, r, x, v);
  segmax[o] = max(segmax[o * 2], segmax[o * 2 + 1]);
}
int getmax(int o, int l, int r, int ql, int qr) {
  if (r < ql || l > qr) return 0;
  if (ql <= l && r <= qr) return segmax[o];
  return max(getmax(o * 2, l, (l + r) / 2, ql, qr),
             getmax(o * 2 + 1, (l + r) / 2 + 1, r, ql, qr));
}
vector<int> g[maxn];
int cur, rnk[maxn], dep[maxn];
int siz[maxn], fa[maxn], son[maxn];
int in[maxn], out[maxn], top[maxn];
void dfs1(int u, int pa, int d) {
  fa[u] = pa;
  siz[u] = 1;
  dep[u] = d;
  int tson = -1;
  for (auto v : g[u]) {
    if (v == pa) continue;
    dfs1(v, u, d + 1);
    siz[u] += siz[v];
    if (tson == -1 || siz[tson] < siz[v]) tson = v;
  }
  son[u] = tson;
}
void dfs2(int u, int pa, int tp) {
  in[u] = ++cur;
  rnk[cur] = u;
  top[u] = tp;
  if (son[u] != -1) dfs2(son[u], u, tp);
  for (auto v : g[u]) {
    if (v != pa && v != son[u]) dfs2(v, u, v);
  }
  out[u] = cur;
}
void init() {
  dfs1(0, -1, 0);
  cur = 0;
  dfs2(0, -1, 0);
}
struct ACAutomata {
  int ch[maxch][alpha_size];
  int f[maxch];
  int lst[maxch];
  int word[maxch];
  int sz;
  int id(char c) { return c - 'a'; }
  void init() {
    sz = 1;
    g[0].clear();
    memset(ch[0], 0, sizeof(ch[0][0]) * (alpha_size));
  }
  int insert(const string &s, int x) {
    int len = ((int)s.size());
    int now = 0;
    for (int i = 0; i < (len); i++) {
      int c = id(s[i]);
      if (!ch[now][c]) {
        word[sz] = f[sz] = lst[sz] = 0;
        memset(ch[sz], 0, sizeof(ch[sz][0]) * (alpha_size));
        ch[now][c] = sz++;
      }
      now = ch[now][c];
    }
    if (!word[now]) word[now] = x;
    return word[now];
  }
  void getfail() {
    queue<int> q;
    for (int i = 0; i < (alpha_size); i++) {
      int u = ch[0][i];
      if (u) {
        q.push(u);
        lst[u] = f[u] = 0;
        if (word[u]) g[0].push_back(word[u]);
      }
    }
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      int j = f[u];
      for (int i = 0; i < (alpha_size); i++) {
        int v = ch[u][i];
        if (!v) {
          ch[u][i] = ch[f[u]][i];
          continue;
        }
        q.push(v);
        f[v] = ch[j][i];
        lst[v] = word[f[v]] ? f[v] : lst[f[v]];
        if (word[v]) g[word[lst[v]]].push_back(word[v]);
      }
    }
  }
  int match(int x) {
    if (!x) return -1;
    int ans = 0;
    while (x > 0) {
      ((void)0), ((void)0), ((void)0), ((void)0);
      ans = max(ans, getmax(1, 1, cur, in[top[x]], in[x]));
      ((void)0);
      x = fa[top[x]];
    }
    return ans;
  }
  int find(const string &s) {
    int len = ((int)s.size());
    int now = 0;
    int ans = -1;
    for (int i = 0; i < (len); i++) {
      int u = id(s[i]);
      now = ch[now][u];
      int t;
      if (word[now])
        t = match(word[now]);
      else
        t = match(word[lst[now]]);
      ans = max(ans, t);
    }
    return ans;
  }
};
ACAutomata ac;
int mp[maxn];
int val[maxn];
multiset<int> st[maxn];
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int q;
  cin >> n >> q;
  ac.init();
  string s;
  for (int i = 0; i < (n); i++) {
    cin >> s;
    mp[i + 1] = ac.insert(s, i + 1);
  }
  ac.getfail();
  init();
  while (q--) {
    int t;
    cin >> t;
    if (t == 1) {
      int x, v;
      cin >> x >> v;
      auto p = st[mp[x]].find(val[x]);
      if (p != st[mp[x]].end()) st[mp[x]].erase(p);
      val[x] = v;
      x = mp[x];
      st[x].insert(v);
      upd(1, 1, cur, in[x], *--st[x].end());
    } else {
      cin >> s;
      cout << ac.find(s) << '\n';
    }
  }
}
