CF1437G Death DBMS

为了简单起见，我们假设“死亡笔记本”是一本只要写上名字就能杀人的笔记本。 用它杀人很容易，但要记录那些你还没杀但仍打算杀的人却相当困难。你决定制作一个“死亡数据库管理系统”——一个可以轻松访问可能的受害者数据库的计算机程序。下面让我向你描述一下它。 让我们来定义一个受害者：受害者有一个仅由小写字母组成的名字（不一定唯一）和一个整数表示嫌疑值。 在程序开始时，用户将 $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 \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$ 仅由小写字母组成。 - 保证第二种查询至少有一个。