#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 6;
int n;

namespace AC {

int tr[N][26], tot;
int fail[N];
int where[N];
bool vis[N];
multiset<int> e[N];

void insert(char *s, int id) {
  int u = 0;
  for (int i = 1; s[i]; i++) {
    if (!tr[u][s[i] - 'a']) {
      tr[u][s[i] - 'a'] = ++tot;
    }
    u = tr[u][s[i] - 'a'];
  }
  where[id] = u;
  e[u].insert(0);
}

void modify(int id, int old, int v) {
  int u = where[id];
  auto it = e[u].find(old);
  assert(it != e[u].end());
  e[u].erase(it);
  e[u].insert(v);
}

queue<int> q;

void build() {
  for (int i = 0; i < 26; i++) {
    if (tr[0][i]) {
      q.push(tr[0][i]);
    }
  }
  while (q.size()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      if (tr[u][i]) {
        fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
      } else {
        tr[u][i] = tr[fail[u]][i];
      }
    }
  }
}

int query(char *t) {
  int u = 0;
  int res = -1;
  vector<int> tmp;
  for (int i = 1; t[i]; i++) {
    u = tr[u][t[i] - 'a'];
    for (int j = u; j && !vis[j]; j = fail[j]) {
      if (!e[j].empty()) {
        res = max(res, *(e[j].rbegin()));
      }
      // res += e[j];
      vis[j] = 1;
      tmp.push_back(j);
    }
  }
  for (auto j: tmp) {
    vis[j] = 0;
  }
  return res;
}
}  // namespace AC

char s[N];
int value[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%s", s + 1);
    AC::insert(s, i);
  }
  AC::build();
  while (m--) {
    int opt;
    scanf("%d", &opt);
    if (opt == 1) {
      int i, x;
      scanf("%d %d", &i, &x);
      AC::modify(i, value[i], x);
      value[i] = x;
    } else {
      scanf("%s", s + 1);
      cout << AC::query(s) << "\n";
    }
  }
  return 0;
}