U372866 [2023年码谷提高组模拟赛1016] D. 反复横跳

给定 $m$ 个字符串 $S_1,S_2,\cdots,S_m$，令 $n = \sum_{i\in[1,m]}|S_i|$，以及一个序列 $a_1,a_2,\cdots,a_n$。 你需要维护一个关于任意字符串的 $f$ 函数，初始时 $f$ 值全为 $0$。 进行 $q$ 次操作，每次操作有以下两种： 1. 给定 $x$，对于任意 $S_k$，若其等于 $S_x$ 的一个后缀 $S_x[i,|S_x|]$，则令 $f(S_k)$ 加上 $a_i$（本质相同的 $S_k$ 只加一次）； 2. 给定 $x$ ，询问 $f(S_x)$。 其中，$S[l,r]$ 表示将 $S$ 从左往右数第 $l$ 到第 $r$ 个字符顺次连接得到的字符串。

第一行，三个正整数 $n,m,q$。 第二行，$n$ 个正整数 $a_1,a_2,\cdots,a_n$。 以下 $m$ 行，其中第 $i$ 行一个字符串 $S_i$。 以下 $q$ 行，每行两个整数 $\text{op},x$。若 $\text{op} = 1$ 则表示执行第一种操作，否则表示执行第二种操作。

对于每个第二种操作，输出一行一个非负整数表示答案。

对于 $30\%$ 的数据，$n,m,q\le10^3$； 对于 $100\%$ 的数据，$1\le n,m,q\le10^5$，$1\le a_i\le10^9$，$1\le x\le m$，字符串中仅包含小写字母。 #### 样例解释 第一次操作后，$f(S_1)=1,f(S_2)=2,f(S_3)=3$； 第三次操作后，$f(S_1)=1,f(S_2)=3,f(S_3)=5$。