Death DBMS

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

为了简单起见，我们假设“死亡笔记本”是一本只要写上名字就能杀人的笔记本。

用它杀人很容易，但要记录那些你还没杀但仍打算杀的人却相当困难。你决定制作一个“死亡数据库管理系统”——一个可以轻松访问可能的受害者数据库的计算机程序。下面让我向你描述一下它。

让我们来定义一个受害者：受害者有一个仅由小写字母组成的名字（不一定唯一）和一个整数表示嫌疑值。

在程序开始时，用户将 $n$ 个受害者名字输入数据库，每个嫌疑值初始设置为 $0$。

随后，用户将进行两种查询：

• $1$ $i$ $x$，将第 $i$ 个受害者的嫌疑值设置为 $x$；
• $2$ $q$，求出姓名为 $q$ 的连续子串的受害者的最大嫌疑值。

提醒一下，这个程序并不杀人，它只是帮助搜索可以写在笔记本上的名字。因此，在整个查询过程中，数据库中的受害者名单不会发生变化。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示受害者人数和查询次数。

接下来的 $n$ 行，每行包含一个字符串 $s_i$，表示第 $i$ 个受害者的姓名。

接下来的 $m$ 行，每行都有一个查询：

• $1$ $i$ $x$，将第 $i$ 个受害者的嫌疑值设置为 $x$；
• $2$ $q$，求出姓名为 $q$ 的连续子串的受害者的最大嫌疑值。

输出格式

对于每个第二种查询，输出一个整数。

如果没有受害者的姓名是 $q$ 的连续子串，则输出 $-1$。否则，输出受害者姓名为 $q$ 的连续子串的最大嫌疑值。

样例输入 1

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

样例输出 1

-1
0
943
135832
943

样例输入 2

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

样例输出 2

0
4
4
-1
18
18
12
11

数据范围

• $1 \le n, m \le 3 \cdot 10^5$。
• 对于第一种查询：$1 \le i \le n$，$0 \le x \le 10^9$。
• 字符串 $s_i$ 的总长度不超过 $3 \cdot 10^5$，字符串 $q$ 的总长度不超过 $3 \cdot 10^5$。
• 保证每个受害者的姓名和第二种查询的字符串 $q$ 仅由小写字母组成。
• 保证第二种查询至少有一个。