#include <bits/stdc++.h>
using namespace std;
namespace Aho {
const int N = 3e5 + 7;
const int K = 26;
int nxt[N][K];
int go[N][K];
int link[N];
bool leaf[N];
int val[N];
int par[N];
char ch[N];
int ex[N];
int sz;
void init() {
  memset(nxt, -1, sizeof nxt);
  memset(go, -1, sizeof go);
  memset(link, -1, sizeof link);
  memset(leaf, 0, sizeof leaf);
  memset(ex, -1, sizeof ex);
  memset(val, -1, sizeof val);
  sz = 0;
}
int addString(const string &s) {
  int cur = 0;
  for (char c : s) {
    int cc = c - 'a';
    if (nxt[cur][cc] == -1) {
      nxt[cur][cc] = ++sz;
      ch[sz] = c;
      par[sz] = cur;
    }
    cur = nxt[cur][cc];
  }
  val[cur] = 0;
  leaf[cur] = 1;
  return cur;
}
int Go(int v, char ch);
int getlink(int v) {
  if (link[v] != -1) return link[v];
  if (v == 0 || par[v] == 0)
    return link[v] = 0;
  else
    return link[v] = Go(getlink(par[v]), ch[v]);
}
int Go(int v, char c) {
  int cc = c - 'a';
  if (go[v][cc] != -1) return go[v][cc];
  if (nxt[v][cc] != -1)
    return go[v][cc] = nxt[v][cc];
  else
    return go[v][cc] = (v ? Go(getlink(v), c) : 0);
}
int exitlink(int v) {
  if (ex[v] != -1) return ex[v];
  int nxt = getlink(v);
  if (nxt == 0 || leaf[nxt]) return ex[v] = nxt;
  return ex[v] = exitlink(nxt);
}
int match(string s) {
  int cur = 0;
  int ans = -1;
  for (auto c : s) {
    cur = Go(cur, c);
    int e = (leaf[cur] ? cur : exitlink(cur));
    while (e) {
      ans = max(ans, val[e]);
      e = exitlink(e);
    }
    ans = max(ans, val[cur]);
  }
  return ans;
}
}  // namespace Aho
const int N = 3e5 + 7;
int id[N], asol[N];
multiset<int> ms[N];
int vv[N];
int main() {
  Aho::init();
  int n, q;
  cin >> n >> q;
  map<string, int> mp;
  int iid = 0;
  for (int i = 1; i <= n; i++) {
    string s;
    cin >> s;
    if (mp.count(s) == 0) mp[s] = ++iid;
    int ii = mp[s];
    id[ii] = Aho::addString(s);
    vv[i] = 0;
    asol[i] = ii;
    ms[ii].insert(0);
  }
  while (q--) {
    int tp;
    cin >> tp;
    if (tp == 1) {
      int idx, val;
      cin >> idx >> val;
      int ii = asol[idx];
      ms[ii].erase(ms[ii].find(vv[idx]));
      vv[idx] = val;
      ms[ii].insert(vv[idx]);
      Aho::val[id[ii]] = *ms[ii].rbegin();
    } else {
      string s;
      cin >> s;
      cout << Aho::match(s) << "\n";
    }
  }
}
