Description

To prevent too many words from blocking the manga content, the new manga plans to use $x$ Ora or $x$ Muda to represent that there are $x$ occurrences of Ora or Muda.

To simplify the content, we now use letters to represent the shouted words.

We use numbers and letters to represent a string. For example, 2 a 3 b represents the string $aabbb$.

At the beginning, there is no text in the manga. Next, you need to perform $n$ operations in order. There are only $2$ types of operations in total:

• The first type: 1 x c adds $x$ copies of $c$ to the current manga, meaning appending $x$ characters $c$ to the end of the current string. It is guaranteed that the current string is empty, or the last character of the string is not $c$.
• The second type: 2 x thinks the manga was not drawn well and restores it to the state after the $x$-th operation, meaning restoring the string to the state after the $x$-th operation. If $x=0$, the string becomes the empty string.

If the current string is $bbaabbb$, and after the $4$-th operation the string is $bb$, then 2 4 will change $bbaabbb$ into $bb$. It is guaranteed that $x$ is less than the current operation index.

As everyone knows, Jotaro Kujo is very smart. Now that Dio has been defeated, he starts thinking about some problems in his manga:

For each prefix $A$ of a string, there is a longest prefix $B$ that is shorter than it and matches a suffix of prefix $A$. Let the length of this longest prefix $B$ be $L$. When $L$ is $0$, it means $B$ is an empty string.

After each operation, you need to compute the sum of $L$ over all prefixes of the current string, take it modulo $998244353$, and output it to tell Jotaro Kujo, so that he can compare it with the answer computed by his Star Platinum.

For example, for $bbaaabba$, the values of $L$ are $0, 1, 0, 0, 0, 1, 2, 3$, so the answer for this string is $7$.

Input Format

The first line contains a positive integer $n$, representing the number of operations.

The next $n$ lines each contain one operation. The operation formats are as described in the statement, for example:

• 1 x c
• 2 x

It is guaranteed that the input is valid.

Output Format

The output contains exactly $n$ lines. The $i$-th line contains one integer, representing the answer after the first $i$ operations.

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

Hint

Sample Explanation

Constraints

$20\%$ of the testdata satisfies $n\leq 300$ and for each operation of type $1$, $x\leq 300$.

Another $30\%$ of the testdata satisfies $n\leq 10 ^ 5$ and for each operation of type $1$, $x=1$.

Another $30\%$ of the testdata satisfies $n\leq 10 ^ 5$ and contains no operation of type $2$.

$100\%$ of the testdata satisfies $n\leq 10 ^ 5$ and for each operation of type $1$, $x\leq 10 ^ 4$.

Translated by ChatGPT 5