Death DBMS
Contest: Educational Codeforces Round 97 (Rated for Div. 2)
Difficulty rating: 2600
Tags: data structures, string suffix structures, strings, trees

For the simplicity, let's say that the "Death Note" is a notebook that kills a person when their name is written in it.

It's easy to kill with it, but it's pretty hard to keep track of people you haven't killed and still plan to. You decided to make a "Death Database Management System" — a computer program that provides the easy access to the database of possible victims. Let me describe its specifications to you.

Let's define a victim entity: a victim has a name (not necessarily unique) that consists only of lowercase Latin letters and an integer suspicion value.

At the start of the program the user enters a list of $$$n$$$ victim names into a database, each suspicion value is set to $$$0$$$.

Then the user makes queries of two types:

- $$$1~i~x$$$ — set the suspicion value of the $$$i$$$-th victim to $$$x$$$;
- $$$2~q$$$ — given a string $$$q$$$ find the maximum suspicion value of a victim whose name is a contiguous substring of $$$q$$$.

Just to remind you, this program doesn't kill people, it only helps to search for the names to write down in an actual notebook. Thus, the list of the victims in the database doesn't change throughout the queries.

What are you waiting for? Write that program now!

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$) — the number of victims and the number of queries, respectively.

Each of the next $$$n$$$ lines contains a single string $$$s_i$$$ — the name of the $$$i$$$-th victim. Each name consists only of lowercase Latin letters.

Each of the next $$$m$$$ lines contains a query of one of two types:

- $$$1~i~x$$$ ($$$1 \le i \le n$$$, $$$0 \le x \le 10^9$$$) — change the suspicion value of the $$$i$$$-th victim to $$$x$$$;
- $$$2~q$$$ — given a string $$$q$$$ consisting only of lowercase Latin letters find the maximum suspicion value of a victim whose name is a contiguous substring of $$$q$$$.

There is at least one query of the second type. The total length of the strings $$$s_i$$$ doesn't exceed $$$3 \cdot 10^5$$$. The total length of the strings $$$q$$$ doesn't exceed $$$3 \cdot 10^5$$$.

Output format:
For each query of the second type print an integer value. If there is no victim name that is a contiguous substring of $$$q$$$, then print $$$-1$$$. Otherwise, print the maximum suspicion value of a victim whose name is a contiguous substring of $$$q$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
5 8
kurou
takuo
takeshi
naomi
shingo
2 nakiraomi
2 abanaomicaba
1 3 943
2 takuotakeshishingo
1 5 135832
2 shingotakeshi
1 5 0
2 shingotakeshi

Example output:
-1
0
943
135832
943

Example input:
6 15
a
ab
ba
b
a
ba
2 aa
1 4 4
2 bbb
1 2 1
1 2 18
2 b
2 c
1 6 10
2 aba
2 abbbba
1 2 12
2 bbaaab
1 1 11
1 5 5
2 baa

Example output:
0
4
4
-1
18
18
12
11

Editorial:
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(q \sqrt n)$$$. 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) \log q)$$$.