CF1437G Death DBMS

## 题目背景 （下面有简化描述，不想看长背景就直接去下面） (与题意无关)简单来说，“死亡笔记”是一个能把名字被写在笔记上的人杀死的笔记。 用这个笔记杀人很容易，但没法用它记录你计划杀死但尚未杀死的人（写上人名就直接杀了）。所以你决定开发一个“死亡数据管理系统”-一个能方便地提供潜在受害者信息的系统。下面为你描述这个系统。 一个受害者由两个信息描述：仅由小写英文字母组成的姓名（不保证唯一）和受怀疑程度。 最开始，系统的使用者输入n个受害者的姓名，他们的受怀疑程度最初都为0。 然后使用者会进行两种操作： - 1 i x 将第i个受害者的受怀疑程度改为x - 2 q 给出一个字符串q，询问所有姓名是q的子串的受害者的受怀疑程度的最大值 **注意**，这个系统不负责杀人，因此在整个过程中受害者都是固定的 ## 简化描述 给出$n,m$，然后给出n个字符串，每个字符串都有一个权值，最初权值都为0 然后有m个操作，操作有两种类型 - 1 i x 将第i个字符串的权值修改为x - 2 q 给出一个字符串q，求所有**是q的子串**的字符串的**权值的最大值**

第一行给出$n,m$，分别是受害者数量和操作数量 接下来n行每行一个字符串s，表示第i个受害者的姓名，保证为小写英文字母

对于每个操作2，如果不存在姓名是询问串q的子串的受害者，则输出'-1'，否则输出权值的最大值，每个**操作**的输出**占一行**

$1\le n,m\le 3\times10^5$ $\sum length(s_i)\le3\times 10^5$，即输入的受害者姓名串s的长度和不超过$3\times10^5$ 操作1中$1\le i\le n \space,\space 0\le x \le 10^9$ 操作2中$\sum length(q)\le3\times 10^5$，即询问串长度和不超过$3\times 10^5$