T221410 走迷宫 Fascinating Labyrinth

小 C 来到了一个很奇怪的迷宫。这个迷宫由许多个房间构成，第 $i$ 个房间的墙壁上写着一个字符串 $s_i$。每个房间内还有两个按钮，上面分别写着 `人` 和 `赢`。每一个房间内还有一颗初始价值为 $1$ 的钻石。 他观察迷宫后发现，$s_i$ 的并是迷宫负责人给他的 $n$ 个字符串的所有前缀的并（包含空字符串），而且 $s_i$ 互不相同。 但是小 C 被困在了迷宫里，于是他开始按下面前的两个按钮： - 若小 C 当前位于 $x$ 号房间，按下了写着 `人` 的按钮，那么他将会被传送到一个满足 $s_y$ 是 $s_x$ 的最长的后缀且 $y\not=x$ 的房间 $y$。注意，如果没有满足条件的房间，那么 `人` 按钮失效。 - 若小 C 当前位于 $x$ 号房间，按下了写着 `赢` 的按钮，那么他将会被传送到一个满足 $s_x$ 是 $s_y$ 的最长的后缀且 $y\not=x$ 的房间 $y$，如果有多个满足条件的房间，小 C 可以任意选择一个进行传送。注意，如果没有满足条件的房间，那么 `赢` 按钮失效。 小 C 初始在墙壁上写着空字符串的房间，在到达某个房间后，小 C 可以选择收集一次或者不收集这个房间内的钻石。但如果他收集了编号为 $u$ 的房间里的钻石，那么他是不能收集可以通过按下 $u$ 号房间内的按钮直接到达的所有房间的钻石的，否则他会被从天而降的激光射穿（（（ 但是这个迷宫的负责人，IOI AKer @[cxy2022](https://www.luogu.com.cn/user/203008) & @[bilibilitdasc](https://www.luogu.com.cn/user/483824) 喜欢刁难小 C，他们会执行 $m$ 次操作，每次操作都会更改一个房间里钻石的价值。修改完后小 C 会被传送回墙壁上什么也没写的房间，等待他的小 Z 想知道每次修改操作执行之后，小 C 最多可以获得总价值为多少的钻石。 由于 IOI AKer @[cxy2022](https://www.luogu.com.cn/user/203008) & @[bilibilitdasc](https://www.luogu.com.cn/user/483824) 太强了，所以他们拥有时空穿梭能力，每个操作都是基于之前的某个迷宫版本进行的，每次操作都会新建一个迷宫版本。 由于小 Z 十分着急想要见到小 C，你只有 $1s$ 的时间求出所有问题的答案。

第一行一个整数 $n$。 接下来 $n$ 行，每行一个字符串 $str$，表示迷宫负责人给小 C 的字符串。 接下来一行一个整数 $m$，表示修改操作的次数。 接下来 $m$ 行，每行两个整数 $id_i,y_i$ 和一个字符串 $x_i$，表示基于第 $id_i$ 个版本，墙上写着字符串 $x_i$ 的房间里的钻石价值被修改成了 $y_i$。注意若 $x_i$ 为 $\texttt{*}$，那么表示墙上写着空字符串的房间里的钻石价值被修改成了 $y_i$。

$m$ 行，每行一个正整数表示答案。

**【样例 1 解释】** 一共有 $17$ 个房间，它们墙上写的字符串分别是：$\texttt{*},\texttt{e},\texttt{ef},\texttt{efo},\texttt{efoi},\texttt{n},\texttt{nd},\texttt{o},\texttt{oi},\texttt{r},\texttt{ro},\texttt{rou},\texttt{roun},\texttt{round},\texttt{u},\texttt{un},\texttt{und}$ 。（$\texttt{*}$ 表示空字符串） 每个房间能到达的房间如下： | 房间墙上写的字符串 | 能到达的房间墙上写的字符串 | | :-----------: | :-----------: | $\texttt{*}$ | $\texttt{nd},\texttt{n},\texttt{u},\texttt{r},\texttt{oi},\texttt{o},\texttt{ef},\texttt{e}$ | | $\texttt{e}$ | $\texttt{*}$ | | $\texttt{ef}$ | $\texttt{*}$ | | $\texttt{efo}$ | $\texttt{o}$ | | $\texttt{efoi}$ | $\texttt{oi}$ | | $\texttt{o}$ | $\texttt{ro},\texttt{*},\texttt{efo}$ | | $\texttt{oi}$ | $\texttt{*},\texttt{efoi}$ | | $\texttt{r}$ | $\texttt{*}$ | | $\texttt{ro}$ | $\texttt{o}$ | | $\texttt{rou}$ | $\texttt{u}$ | | $\texttt{roun}$ | $\texttt{un}$ | | $\texttt{round}$ | $\texttt{und}$ | | $\texttt{u}$ | $\texttt{*},\texttt{rou}$ | | $\texttt{un}$ | $\texttt{n},\texttt{roun}$ | | $\texttt{und}$ | $\texttt{nd},\texttt{round}$ | | $\texttt{n}$ | $\texttt{*},\texttt{un}$ | | $\texttt{nd}$ | $\texttt{*},\texttt{und}$ | 第一次修改是基于第 $0$ 个版本的，修改墙上写着字符串 $\texttt{e}$ 的房间里钻石的价值为 $10$，那么修改完后的价值如下： | 房间墙上写的字符串 | $\texttt{*}$ | $\texttt{e}$ | $\texttt{ef}$ | $\texttt{efo}$ | $\texttt{efoi}$ | $\texttt{n}$ | $\texttt{nd}$ | $\texttt{o}$ | $\texttt{oi}$ | $\texttt{r}$ | $\texttt{ro}$ | $\texttt{rou}$ | $\texttt{roun}$ | $\texttt{round}$ | $\texttt{u}$ | $\texttt{un}$ | $\texttt{und}$ | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | **对应的价值** | 1 | 10 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 小 C 从墙上写着空字符串的房间出发，依次收集墙上写着字符串 $\texttt{e},\texttt{ef},\texttt{ro},\texttt{efo},\texttt{efoi},\texttt{r},\texttt{rou},\texttt{n},\texttt{roun},\texttt{nd},\texttt{round}$ 的房间里的钻石，可以获得总价值 $10+1+1+1+1+1+1+1+1+1+1=20$ 的钻石。 第二次修改则是基于第 $1$ 个版本的，修改墙上写着字符串 $\texttt{n}$ 的房间里的钻石价值为 $10$，那么修改完后的价值如下： | 房间墙上写的字符串 | $\texttt{*}$ | $\texttt{e}$ | $\texttt{ef}$ | $\texttt{efo}$ | $\texttt{efoi}$ | $\texttt{n}$ | $\texttt{nd}$ | $\texttt{o}$ | $\texttt{oi}$ | $\texttt{r}$ | $\texttt{ro}$ | $\texttt{rou}$ | $\texttt{roun}$ | $\texttt{round}$ | $\texttt{u}$ | $\texttt{un}$ | $\texttt{und}$ | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | **对应的价值** | 1 | 10 | 1 | 1 | 1 | 10 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 小 C 从墙上写着空字符串的房间出发，依次收集墙上写着字符串 $\texttt{e},\texttt{ef},\texttt{ro},\texttt{efo},\texttt{efoi},\texttt{r},\texttt{rou},\texttt{n},\texttt{roun},\texttt{nd},\texttt{round}$ 的房间里的钻石，可以获得总价值 $10+1+1+1+1+1+1+10+1+1+1=29$ 的钻石。 第三、第四、第五次修改分别是基于第 $0$、$2$、$3$ 个版本的，修改完后小 C 可以获得的最大价值分别是 $20$、$38$、$29$。 **【数据范围】** **本题采取捆绑测试。** | 子任务编号 | 分值 | 特殊性质 | | :----------: | :----------: | :----------: | | $1$ | $20$ | $n,m\le 10$，$\left\vert str\right\vert,\left\vert x_i\right\vert\le10$ | | $2$ | $80$ | 无 | 对于 $100\%$ 的数据，$1\le n\le 10^3$，$1\le m\le 4\cdot10^4$，$1\le|str|,|x_i|\le 50$，$id_i