#include <bits/stdc++.h>
using namespace std;
struct Aho_Corasick {
  struct Node {
    map<char, int> next, go;
    int link = -1, p = -1;
    char ch = -1;
    vector<int> children;
    bool leaf = false;
    map<int, int, greater<int>> cnt;
    Node(int p = -1, char ch = '$') : p(p), ch(ch) {}
  };
  vector<Node> nodes = vector<Node>(1);
  int add_string(string &s) {
    int v = 0;
    for (char c : s) {
      if (nodes[v].next.count(c) == 0) {
        nodes[v].next[c] = int(nodes.size());
        nodes.push_back({v, c});
      }
      v = nodes[v].next[c];
    }
    nodes[v].leaf = true;
    return v;
  }
  int link(int u) {
    if (u == 0 || nodes[u].p == 0) return 0;
    if (nodes[u].link != -1) return nodes[u].link;
    return nodes[u].link = go(link(nodes[u].p), nodes[u].ch);
  }
  int go(int u, char c) {
    if (nodes[u].go.count(c) != 0) return nodes[u].go[c];
    if (nodes[u].next.count(c) != 0) return nodes[u].go[c] = nodes[u].next[c];
    return nodes[u].go[c] = u == 0 ? 0 : go(link(u), c);
  }
} aho;
struct HLD {
  int N, timer = 0;
  vector<int> sTree;
  vector<int> parent, depth, heavy, head, pos;
  HLD() = default;
  HLD(int n) {
    N = 1 << (32 - __builtin_clz(n - 1));
    sTree = vector<int>(N << 1, -1);
    parent = vector<int>(n);
    heavy = vector<int>(n, -1);
    head = vector<int>(n);
    pos = vector<int>(n);
    dfs(0);
    decompose(0, 0);
  }
  int dfs(int u) {
    int size = 1;
    int heavy_size = 0;
    for (int v : aho.nodes[u].children) {
      parent[v] = u;
      int curr = dfs(v);
      size += curr;
      if (curr > heavy_size) heavy_size = curr, heavy[u] = v;
    }
    return size;
  }
  void decompose(int u, int h) {
    head[u] = h, pos[u] = ++timer;
    if (heavy[u] != -1) decompose(heavy[u], h);
    for (int v : aho.nodes[u].children)
      if (v != heavy[u]) decompose(v, v);
  }
  void update_node(int i, int val) {
    i = pos[i];
    i += N - 1;
    sTree[i] = val;
    while (i > 1) {
      i >>= 1;
      sTree[i] = max(sTree[i << 1], sTree[i << 1 | 1]);
    }
  }
  int get_range(int node, int b, int e, int i, int j) {
    if (i > e || j < b) return -1;
    if (i <= b && e <= j) return sTree[node];
    int mid = b + e >> 1;
    return max(get_range(node << 1, b, mid, i, j),
               get_range(node << 1 | 1, mid + 1, e, i, j));
  }
  int get_max(int l, int r) { return get_range(1, 1, N, l, r); }
  int query(int node) {
    int ans = -1;
    for (; head[node] != 0; node = parent[head[node]])
      ans = max(ans, get_max(pos[head[node]], pos[node]));
    return max(ans, get_max(pos[0], pos[node]));
  }
};
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  vector<tuple<string, int, int>> patterns(n);
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    int node = aho.add_string(s);
    patterns[i] = {s, node, 0};
  }
  int _size = int(aho.nodes.size());
  for (int v = 1; v < int(aho.nodes.size()); v++)
    aho.nodes[aho.link(v)].children.push_back(v);
  HLD hld(_size + 1);
  for (int v = 1; v < _size; v++)
    if (aho.nodes[v].leaf) {
      hld.update_node(v, 0);
      aho.nodes[v].cnt[0]++;
    }
  while (m--) {
    int t;
    cin >> t;
    if (t == 1) {
      int i, x;
      cin >> i >> x;
      int node = get<1>(patterns[i - 1]);
      aho.nodes[node].cnt[get<2>(patterns[i - 1])]--;
      if (aho.nodes[node].cnt[get<2>(patterns[i - 1])] == 0)
        aho.nodes[node].cnt.erase(get<2>(patterns[i - 1]));
      get<2>(patterns[i - 1]) = x;
      aho.nodes[node].cnt[get<2>(patterns[i - 1])]++;
      auto it = aho.nodes[node].cnt.begin();
      hld.update_node(node, it->first);
    } else {
      string q;
      cin >> q;
      int node = 0;
      int ans = -1;
      for (char c : q) {
        node = aho.go(node, c);
        ans = max(ans, hld.query(node));
      }
      cout << ans << '\n';
    }
  }
  return 0;
}
