【题目描述】

如同人与人之间一样，前缀和前缀之间也有着很大的不同呢。

落尘兴致一来，观察起了一堆小写字符串的前缀（可以是字符串本身）。令这 𝑛 个字符串的前缀构成的不可重集合（不含空串）为 𝑆，规定其中的每个前缀 𝑆 都有一个绝 对价值 $𝐹_𝑆$。同时规定两个前缀$𝑆_1$ 和 $𝑆_2$ 之间的相对差异价值为 |𝑆1|+|𝑆2|−2|lcp(𝑆1,𝑆2)|，其中 |𝑆| 表示串 𝑆 的长度，lcp(𝑆1,𝑆2) 为这两个串的最长公共前缀。

对于所有的前缀 𝑠 满足 𝑠 的任意前缀 𝑡 有$𝐹_𝑡≥𝐹_𝑠$。

落尘认为这些前缀之间在差异较大时会造成贡献。设以 $𝑆_2$ 为前缀的最长的字符串为 𝑥，规定$𝑆_1$能对$𝑆_2$ 造成贡献当且仅当它们之间的相对差异价值 𝑣 满足 𝑣>|𝑥|，同时绝对价值满足 $𝐹_{S1}≥𝐹_{S2}$。注意，前缀之间的贡献是在不可重集合中进行的，两个相等的前缀之间不造成贡献，也不对其他前缀多次造成贡献。

现在落尘对于每一个前缀想要求出一个答案。设前缀 𝑎 能对某些前缀造成贡献，把这些被造成贡献前缀的集合记作 𝑆。你要找到一个最小的前缀集合 𝑇，使得在 𝑆 中的每一个串，𝑇 中存在一个串是它的前缀。并且，不在 𝑆 中的任何一个缀，𝑇 中任何一个串不是它的前缀。然后 𝑎 的答案便是这个前缀集合 𝑇 中的元素个数。

你要对每个字符串的每个前缀输出它的答案。

【输入格式】

第一行一个整数 𝑛

接下来 𝑛 次读入，每次读入先是一个数 type，表示串的读入类型。

若 type =0 则表明这是一个初始串，接下来读入一个小写字母组成的字符串 𝑥，意义如题，然后读入 |𝑥| 个整数表示这个串每个前缀的 $𝐹_𝑆$

若 type =1 则表明这是一个拼接串，接下来读入一个整数 id，表示这个串的前缀与第 id 个串 $𝑥_{id}$一样（保证第 id 个串已经出现过），且接下来的读入是接着这个长为 $|𝑥_{id}|$的前缀进行拼接。接下来读入一个小写字母组成的字符串 𝑥，拼接后得到本次读入的字符串，然后读入 |𝑥| 个整数表示这个串拼接部分位置每个前缀的 $𝐹_𝑆$。拼接串的答案 只需要输出拼接部分对应答案即可。

注意如果一个前缀在读入过程出现多次，则其 $𝐹_𝑆$ 取第一次出现的。 【输出格式】

共 𝑛 行，每一行共 |𝑥| 个整数表示这个字符串每个前缀的答案（拼接串只要输出拼接部分）

3
0
a
5
1
1
bc
4 1
0
cd
4 2

1
1 0
1 1

【样例1解释】

第一个串为初始串，得到 a。

第二个串从第一个串末尾开始拼接，得到 abc。

第三个串为初始串，得到 cd。

对于第一个串：

前缀a对前缀cd造成贡献，则取 𝑇={cd}。

对于第二个串：

只考虑拼接部分答案：

前缀ab对前缀c,cd造成贡献，则取 𝑇={𝑐}。

前缀abc不对任何前缀贡献。

对于第三个串：

前缀c对前缀abc造成贡献，则取 𝑇={abc}。

前缀cd对前缀abc造成贡献，则取 𝑇={abc}。

数据规模与约定

对于 100% 的数据，$∑|𝑥|≤5×10^5，𝐹_𝑆 ≤5×10^5$。 请选手注意算法的常数问题，以免超时。