#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double DINF = 1e18;
const int N = 3e5 + 5;
int tot, son[N][26], fail[N], q[N];
int aid[N];
int Val1[N];
multiset<int> Val2[N];
int n;
char s[N];
void Insert(int p) {
  for (int l = strlen(s), x = 0, i = 0, w; i < l; ++i) {
    if (!son[x][w = s[i] - 'a']) son[x][w] = ++tot;
    x = son[x][w];
    if (i == l - 1) {
      aid[p] = x;
      Val1[p] = 0;
      Val2[x].insert(0);
    }
  }
}
void Update(int p, int V) {
  int x = aid[p];
  Val2[x].erase(Val2[x].find(Val1[p]));
  Val1[p] = V;
  Val2[x].insert(V);
}
void make() {
  int h = 1, t = 0, i, j, x;
  fail[0] = -1;
  for (int i = 0; i < 26; ++i)
    if (son[0][i]) q[++t] = son[0][i];
  while (h <= t)
    for (x = q[h++], i = 0; i < 26; ++i)
      if (son[x][i]) {
        fail[son[x][i]] = son[fail[x]][i];
        q[++t] = son[x][i];
      } else {
        son[x][i] = son[fail[x]][i];
      }
}
bool vis[N];
int val2[N];
int getVal2(int x) {
  if (vis[x]) return val2[x];
  if (x == 0) {
    vis[x] = 1;
    val2[x] = -1;
    return val2[x];
  }
  vis[x] = 1;
  val2[x] = -1;
  if (Val2[x].size()) val2[x] = *Val2[x].rbegin();
  val2[x] = max(val2[x], getVal2(fail[x]));
  return val2[x];
}
void cleanVal2(int x) {
  if (!vis[x]) return;
  if (x == 0) {
    vis[x] = 0;
    return;
  }
  vis[x] = 0;
  cleanVal2(fail[x]);
  return;
}
int find() {
  int maxres = -1;
  for (int l = strlen(s), x = 0, i = 0, w, j; i < l; ++i) {
    x = son[x][w = s[i] - 'a'];
    maxres = max(maxres, getVal2(x));
  }
  for (int l = strlen(s), x = 0, i = 0, w, j; i < l; ++i) {
    x = son[x][w = s[i] - 'a'];
    cleanVal2(x);
  }
  return maxres;
}
void solve() {
  int q;
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; ++i) {
    scanf("%s", s);
    Insert(i);
  }
  make();
  while (q--) {
    int op;
    scanf("%d", &op);
    if (op == 1) {
      int i, x;
      scanf("%d%d", &i, &x);
      Update(i, x);
    } else {
      scanf("%s", s);
      printf("%d\n", find());
    }
  }
  return;
}
int main() {
  int T = 1;
  for (int i = 1; i <= T; ++i) {
    solve();
  }
  return 0;
}
