1437G - Death DBMS
I'm feeling extremely amused by the power of Aho-Corasick lately, so I will describe two solutions of this problem with it. Feel free to point out how cool you are solving the task with hashes or some suffix structure but Aho solutions will still be cooler. I also want to mention I'm quite proud of the name I came up with for that task :)

First, let's assume that the words in the dictionary are unique.

Build an Aho-Corasick automaton on the dictionary. Then build the tree of its suffix links.

For the first solution you can use the fact that there are not a lot of words in the dictionary that can end in each position. To be exact, at most one word per unique word length. Thus, that's bounded by the square root of the total length.

For that reason you can iterate over all the words that end in all positions of the queries in O(qn−−√). How to do that fast? For each vertex of the automaton precalculate the closest vertex up the suffix link tree that's a terminal. Feed the query word into the automaton and from each vertex you stay at just jump up the tree until you reach the root. Take the maximum value over all the visited terminals.

The second solution actually involves an extra data structure on top of that. No, it's not HLD. You are boring for using it.

Let's abuse the fact that you are allowed to solve the problem fully offline. For each word you can save the list of pairs (time, value) of the times the value of the word changed. For each vertex of the automaton you can save all the times that vertex has been queried from.

Now traverse the tree with dfs. When you enter the vertex, you want to apply all the updates that are saved for the words that are terminals here. What are the updates? From the list we obtained for a word you can generate such triples (l,r,x) that this word had value x from query l to query r. Don't forget the 0 value from 0 to the first update to this word. Then ask all the queries. Then go to children. When you exit the vertex, you want all the updates to be gone. Well, there is a trick for these kinds of operations, it's called rollbacks.

Maintain a segment tree over the query times, the i-th leaf should store the maximum value during the i-th query. The update operation updates the range with the new possible maximum. How to avoid using lazy propagation with such updates? Well, on point query you can collect all the values from the segtree nodes you visit on your way down. That way you don't have to push the updates all the way to the leaves. Not that it matters that much but the number of values to be saved for future rollbacks is decreased dramatically.

That solution works in O((n+q)logq).

#include <bits/stdc++.h>
using namespace std;

const int N = 300000 + 1;
const int A = 26;

struct aho_corasick {

  multiset<int> sus[N];
  int target[N];

  int to[N][A];
  int link[N];
  int sz = 1;

  int update(const string& s) {
    int cur = 0;
    for (int c : s) {
      c -= 'a';
      if (to[cur][c] == 0) {
        to[cur][c] = sz;
        ++sz;
      }
      cur = to[cur][c];
    }
    sus[cur].insert(0);
    target[cur] = 0;
    return cur;
  }

  void push() {
    queue<int> que;
    que.push(0);

    while (!que.empty()) {
      int u = que.front();
      que.pop();
      for (int i = 0; i < A; ++i) {
        if (to[u][i] != 0) {
          link[to[u][i]] = (u == 0) ? 0 : to[link[u]][i];
          que.push(to[u][i]);
        } else {
          to[u][i] = to[link[u]][i];
        }
      }
    }
  }

} aho;

int where[N];
int value[N];
int memo[N];
vector<int> done;

int get(int u) {
  if (u == 0) {
    return -1;
  } else if (memo[u] != -1) {
    return memo[u];
  } else {
    memo[u] = max(aho.target[u], get(aho.link[u]));
    if (memo[u] == -1) {
      memo[u] = -2;
    }
    done.push_back(u);
    return memo[u];
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, q;
  cin >> n >> q;

  memset(aho.target, -1, sizeof aho.target);
  for (int i = 0; i < n; ++i) {
    string s;
    cin >> s;
    where[i] = aho.update(s);
  }
  aho.push();
  memset(memo, -1, sizeof memo);

  while (q--) {
    int type;
    cin >> type;

    if (type == 1) {
      int i, x;
      cin >> i >> x;
      multiset<int> &s = aho.sus[where[--i]];
      s.erase(s.find(value[i]));
      value[i] = x;
      s.insert(value[i]);
      aho.target[where[i]] = *(--s.end());
      for (auto i : done) {
        memo[i] = -1;
      }
      done.clear();
    } else {
      string s;
      cin >> s;

      int cur = 0;
      int max_sus = -1;
      for (auto i : s) {
        cur = aho.to[cur][i - 'a'];
        max_sus = max(max_sus, get(cur));
      }
      cout << max_sus << "\n";
    }
  }
}


/**
 * Description: Aho-Corasick for fixed alphabet. For each prefix,
    * stores link to max length suffix which is also a prefix.
 * Time: O(N\sum)
 * Source: https://ideone.com/0cMjZJ
    * https://codeforces.com/contest/710/problem/F
    * https://codeforces.com/contest/1207/problem/G
 */

int loc[MX], cur[MX];

struct ACfixed { // fixed alphabet
    static const int ASZ = 26;
    struct node { array<int,ASZ> to; int link; int termLink; vi term; multiset<int> vals; };
    vector<node> d = {{}};
    int add(str s, int ind) { // add word
        int v = 0;
        trav(C,s) {
            int c = C-'a';
            if (!d[v].to[c]) d[v].to[c] = sz(d), d.eb();
            v = d[v].to[c];
        }
        d[v].term.pb(ind);
        d[v].vals.ins(0);
        loc[ind] = v;
        // dbg("HAHA",ind,v,d[v].vals);
        return v;
    }
    void init() { // generate links
        d[0].link = -1;
        queue<int> q; q.push(0);
        while (sz(q)) {
            int v = q.ft; q.pop();
            F0R(c,ASZ) {
                int u = d[v].to[c]; if (!u) continue;
                d[u].link = d[v].link == -1 ? 0 : d[d[v].link].to[c];
                q.push(u);
            }
            if (v) F0R(c,ASZ) if (!d[v].to[c])
                d[v].to[c] = d[d[v].link].to[c];
            if (sz(d[v].vals)) {
                d[v].termLink = v;
            } else if (d[v].link == -1) {
                d[v].termLink = -1;
            } else {
                d[v].termLink = d[d[v].link].termLink;
            }
        }
    }
};

ACfixed A;
int N,M;

int get(int x) {
    int res = -1;
    while (x != -1) {
        x = A.d[x].termLink;
        if (x == -1) break;
        ckmax(res,*A.d[x].vals.rbegin());
        x = A.d[x].link;
    }
    return res;
}

int main() {
    setIO(); re(N,M);
    F0R(i,N) {
        str s; re(s);
        A.add(s,i);
    }
    A.init();
    F0R(i,M) {
        int t; re(t);
        if (t == 1) {
            int ind, x; re(ind,x); ind --;
            // dbg("OH",ind,loc[ind],A.d[loc[ind]].vals,cur[ind]);
            erase(A.d[loc[ind]].vals,cur[ind]);
            // dbg("MID",A.d[loc[ind]].vals);
            cur[ind] = x;
            A.d[loc[ind]].vals.ins(cur[ind]);
            // dbg("AFTER",A.d[loc[ind]].vals);
        } else {
            str q; re(q);
            int x = 0, ans = -1;
            trav(c,q) {
                x = A.d[x].to[c-'a'];
                ckmax(ans,get(x));
            }
            ps(ans);
        }
    }
    // you should actually read the stuff at the bottom
}