P5561 [Celeste-B] Mirror Magic

> ... > 呼吸。 > 你能站起来，Madeline > 想想羽毛。你能拯救 Theo

镜之神庙是一座有魔力的神庙，在这里你能一窥自己心灵的真相。 Theo 被困在了一面镜子里。当 Madeline 尝试去拯救 Theo 时，神庙里的"生物"们给她出了一道难题，这道难题是这样的： 神庙的"生物"们准备了 $n$ 串草莓，这些草莓的长度之和 $=r$。 $2\ k$，表示删除第 $k$ 次操作插入的草莓串，保证第 $k$ 次操作为插入并且此时第 $k$ 次操作插入的草莓串在集合中。 "生物"们认为和谐的味道才是美味的。在执行任意一次操作之后，"生物"们想要知道当前集合中所有草莓串的美味度(即 $LCP$ - 最长公共前缀)。（若集合为空，则美味度 $0$，若集合中只有一个草莓串，则美味度为草莓串的长度） 为了方便表达，我们把每一种草莓表示为一个**小写英文字母**。 多年以后，Madeline 又来到了镜之神庙，想要回忆多年前自己的登山旅途，可是她已经不记得自己当年是怎么解决那道谜题的了，你能帮帮她找到谜题的答案吗？

第一行一个正整数 $n$，表示草莓串的个数。 接下来 $n$ 行一行一个**只包含小写字母**的字符串，表示原来的 $n$ 个草莓串。 接下来一行一个正整数 $q$，表示操作个数。 接下来 $q$ 行一行一个操作。

输出 $q$ 行，对应每次操作之后集合中草莓串的美味度($LCP$ - 最长公共前缀).

样例解释： 第一次操作后，集合为 $\{"abccccd"\}$,$LCP=7$ 第二次操作后，集合为 $\{"abccccd","abccddc"\}$,$LCP=4$ 第三次操作后，集合为 $\{"abccccd","abccddc","acbbcad"\}$,$LCP=1$ 第四次删除了第三次插入的串，故 $LCP=4$ 第五次删除了第二次插入的串，故 $LCP=7$ 令 $len$ 等于 $n$ 个串的长度之和。总有 $len \leq 10^6$ Subtask $1$($10$ Pts), $n \leq 5, q = 10$ Subtask $2$($30$ Pts), $n \leq 10^6, q = 10^6$, 保证每次插入的是串的一个前缀 Subtask $3$($10$ Pts), $n \leq 10^6, q = 10^5$, 不含 $2$ 操作, **保证询问为随机生成** Subtask $4$($50$ Pts), $n \leq 10^6, q = 10^6$ 提示：你可以根据 $q$ 判断 Subtask 编号