Manga Operations and Prefix Matching

In this problem, you are given an initially empty string representing a comic strip. The comic uses special operations to add text in a compressed format and to revert to a previous state. The string is constructed using a series of operations. There are two types of operations:

• Operation 1: 1 x c — Append x copies of the character c to the end of the current string. It is guaranteed that the string is either empty or its last character is not c.
• Operation 2: 2 x — Revert the current string to its state immediately after the x-th operation. If x equals 0, the string becomes empty. It is guaranteed that x is less than the current operation number.

After each operation, you must compute the answer based on the current string. For every prefix A of the string, define L as the length of the longest proper prefix B of A which is also a suffix of A (if no such non-empty prefix exists, L is 0). In other words, L is the length of the longest border of the prefix A. The answer for the current string is the sum of L over all prefixes of the string, modulo 998244353.

For example, consider the string "bbaaabba". Its prefixes have the following L values:

• "b" → 0
• "bb" → 1
• "bba" → 0
• "bbaa" → 0
• "bbaaa" → 0
• "bbaaab" → 1
• "bbaaabb" → 2
• "bbaaabba" → 3

The sum is 0+1+0+0+0+1+2+3 = 7.

You are given n operations. After processing each operation, output the answer (i.e. the sum of all L values for every prefix of the current string) modulo 998244353.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵ or as specified by the input constraints), the number of operations.

Each of the next n lines describes an operation. An operation is given by one of the following two formats:

• 1 x c — Append x copies of character c to the end of the current string. (It is guaranteed that the string is empty or its last character is not c.)
• 2 x — Revert the current string to the state immediately after the x-th operation. (If x is 0, the string becomes empty. It is guaranteed that x is less than the current number of operations.)

outputFormat

After each operation, output a single line containing one integer: the sum of the longest border lengths (the L values) for every prefix of the current string, taken modulo 998244353.

sample

3
1 2 a
1 3 b
2 1

1
1
1