Migrated from Lutece 2617 basic string problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在最开始时你有一个空字符串。

给出 $q$ 个操作，操作分为以下两种：

• 1 x c 在字符串后面加上 $x$ 个小写英文字符 $c$；
• 2 x 把字符串还原到第 $x$ 次操作之后的样子。

在每次操作完之后，对字符串的所有前缀的最大 border 求和。

border 的定义请参阅 KMP。

Input

第一行一个数字 $q$ 代表操作次数。 接下来 $q$ 行按照题面形式给出。

Output

输出 $q$ 行，每行一个数代表答案对 $998244353$ 取模之后的结果。

Samples

10
1 5 s
1 5 u
1 5 g
1 5 a
1 5 s
1 4 u
1 3 g
2 5
1 5 u
1 3 g

10
10
10
10
25
55
55
25
65
101

Constraints

$1\leq q\leq 10^5$。 操作一中的 $x$ 满足 $1\leq x\leq 10^4$。 对于第 $k$ 次询问保证 $x<k$。 保证每一次添加字符 $c$ 时，字符串的末尾字符不是 $c$。

Resources

2021 UESTC ICPC Training for String and Search Algorithm