题目背景

...

呼吸。

你能站起来，Madeline

想想羽毛。你能拯救 Theo

题目描述

镜之神庙是一座有魔力的神庙，在这里你能一窥自己心灵的真相。

Theo 被困在了一面镜子里。当 Madeline 尝试去拯救 Theo 时，神庙里的"生物"们给她出了一道难题，这道难题是这样的：

神庙的"生物"们准备了 $n$ 串草莓，这些草莓的长度之和 $<= 10^6$，现在它们可以执行这样一些操作：

$1\ x\ l\ r$，表示将编号 $x$ 的草莓串的子草莓串 $[l,r]$ 复制一份，插入当前的草莓集合中，保证草莓串 $x$ 的长度 $>=r$。

$2\ k$，表示删除第 $k$ 次操作插入的草莓串，保证第 $k$ 次操作为插入并且此时第 $k$ 次操作插入的草莓串在集合中。

"生物"们认为和谐的味道才是美味的。在执行任意一次操作之后，"生物"们想要知道当前集合中所有草莓串的美味度(即 $LCP$ - 最长公共前缀)。（若集合为空，则美味度 $0$，若集合中只有一个草莓串，则美味度为草莓串的长度）

为了方便表达，我们把每一种草莓表示为一个小写英文字母。

多年以后，Madeline 又来到了镜之神庙，想要回忆多年前自己的登山旅途，可是她已经不记得自己当年是怎么解决那道谜题的了，你能帮帮她找到谜题的答案吗？

输入格式

第一行一个正整数 $n$，表示草莓串的个数。

接下来 $n$ 行一行一个只包含小写字母的字符串，表示原来的 $n$ 个草莓串。

接下来一行一个正整数 $q$，表示操作个数。

接下来 $q$ 行一行一个操作。

输出格式

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

3
abccccd
abccddc
acbbcad
5
1 1 1 7
1 2 1 7
1 3 1 7
2 3
2 2

7
4
1
4
7

提示

样例解释：

第一次操作后，集合为 $\{"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 编号