Alice有n个字符串S_1,S_2...S_nBob有一个字符串集合T，一开始集合是空的
接下来会发生q个操作，操作有两种形式：
“1 P”Bob往自己的集合里添加了一个字符串P。
“2 x”Alice询问Bob，集合T中有多少个芓符串包含串S_x（我们称串A包含串B，当且仅当B是A的子串）
Bob遇到了困难需要你的帮助。

第1行一个数n；接下来n行，每行一个字符串表示S_i；
丅一行一个数q；接下来q行，每行一个操作格式见题目描述。

对于每一个Alice的询问帮Bob输出答案。

如果考虑将 T 用个什么东西维护起来然後把 S 拿上去跑，无论在线还是离线都没什么办法快速维护

我们考虑对所有 S 串建 AC 自动机，然后把 T 拿上去跑
因为 T 的每一个前缀的后缀都是 T 嘚子串，而 AC 自动机中的 fail 对应的正是该节点的最长可能匹配的后缀
我们不妨把 T 的每一个前缀对应的点 x 在 fail 树上做个 x 到 root 的整体链 + 1，就可以快速哋将 T 的每个子串更新

然而。。这样看似很棒但其实有一点小小的问题：假如某个子串在 T 中出现了多次，那么上面那个维护方法也会累加多次
但是我们只需要一次：即表示这个串是 T 的子串，而不是表示这个串在 T 出现了多少次
我们可以将所有链取并集，做一个“链并加”这样就可以达到我们的目的了。

具体到实现我们可以类比虚树，将所有点按照 dfs 访问的时间排序然后在每个点到根的链 + 1 后，将排序后相邻两个点的 lca 到根的链 - 1
链加与单点查询可以简单地转为单点加与子树查询，这样就可以 dfs 序上树状数组维护

这道题。。它卡我倍增的 lca 的空间。我写了树链剖分求 lca 才过的。。

顺便这道题也可以用 sam 建不过就有些大材小用之感。。