#3055. 「HNOI2019」JOJO

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

JOJO 的奇幻冒险是一部非常火的漫画。漫画中的男主角经常喜欢连续喊很多的「欧拉」或者「木大」。

为了防止字太多挡住漫画内容,现在打算在新的漫画中用 x 欧拉或者 x 木大表示有 x 个欧拉或者木大。

为了简化内容我们现在用字母表示喊出的话。

我们用数字和字母来表示一个串,例如:2 a 3 b 表示的串就是 aabbb

一开始漫画中什么话都没有,接下来你需要依次实现 n 个操作,总共只有 2 种操作:

  • 第一种:1 x c:在当前漫画中加入 x c ,表示在当前串末尾加入 x c 字符。保证当前串是空串或者串尾字符不是 c
  • 第二种:2 x:觉得漫画没画好,将漫画还原到第 x 次操作以后的样子,表示将串复原到第 x 次操作后的样子,如果 x=0 则是将串变成空串。如果当前串是 bbaabbb,第 4 次操作后串是 bb,则 2 4 会使 bbaabbb 变成 bb,保证 x 小于当前操作数。

众所周知空条承太郎十分聪明,现在迪奥已经被打败了,他开始考虑自己的漫画中的一些问题:

对于一个串的每个前缀 A ,都有一个最长的比它短的前缀 B 与前缀 A 的一个后缀匹配,设这个最长的前缀 B 的长度为 L L 0 时意味着 B 是一个空串。

每一次操作后,你都需要将当前的串的所有前缀的 L 求和并对 998244353 取模输出告诉空条承太郎,好和他的白金之星算出的答案对比。比如 bbaaabba L 分别是 0, 1, 0, 0, 0, 1, 2, 3 ,所以对于这个串的答案就是 7

输入格式

第一行包括一个正整数 n ,表示操作数量。

接下来 n 行每行包含一个操作,操作格式如题目描述所示,例如:

  • 1 x c
  • 2 x

保证数据合法。

输出格式

仅包含 n 行,第 i 行一个整数,表示 i 个操作之后串的答案。

样例

样例输入

11
1 2 a
1 3 b
1 2 a
1 1 b
2 2
1 3 a
1 2 b
2 6
2 5
1 7 a
1 5 c

样例输出

1
1
4
7
1
6
13
6
1
14
14

样例说明

操作 此时的串 答案(取模后)
1 aa 0+1=1
2 aabbb 0+1+0+0+0=1
3 aabbbaa 0+1+0+0+0+1+2=4
4 aabbbaab 0+1+0+0+0+1+2+3=7
5 aabbb 0+1+0+0+0=1
6 aabbbaaa 0+1+0+0+0+1+2+2=6
7 aabbbaaabb 0+1+0+0+0+1+2+2+3+4=13
8 aabbbaaa 0+1+0+0+0+1+2+2=6
9 aabbb 0+1+0+0+0=1
10 aabbbaaaaaaa 0+1+0+0+0+1+2+2+2+2+2+2=14
11 aabbbaaaaaaaccccc 0+1+0+0+0+1+2+2+2+2+2+2+0+0+0+0+0=14

数据范围与提示

20\% 的数据满足 n\le 300 ,对于每个 1 操作中的 x\le 300

另有 30\% 的数据满足 n\le 10^5 ,且对于每个 1 操作中的 x=1

另有 30\% 的数据满足 n\le 10^5 ,且不含 2 操作;

100\% 的数据满足 n\le 10^5 ,且每个 1 操作中的 x\le 10^4