JoJo's Bizarre Adventure is a very popular manga. The protagonist often likes to shout "Ora" or "Muda" many times in a row.

To prevent too much text from obscuring the manga's content, the new manga will use $x$ Ora or $x$ Muda to represent $x$ occurrences of "Ora" or "Muda".

To simplify the content, we now use letters to represent the spoken words. We use numbers and letters to represent a string, for example: $2\ a\ 3\ b$ represents the string aabbb.

Initially, the manga contains no text. You need to perform $n$ operations in sequence. There are only two types of operations:

• Type 1: 1 x c adds $x$ occurrences of $c$ to the current manga (this means appending $x$ characters of $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$.)
• Type 2: 2 x restores the manga to the state it was in after the $x$-th operation (this means restoring the string to the state after the $x$-th operation; if $x=0$, the string becomes empty). (For example, if the current string is bbaabbb and the string after the 4th operation was bb, then 2 4 will change bbaabbb to bb. It is guaranteed that $x$ is less than the current operation count.)

As everyone knows, Jotaro Kujo is very intelligent. Now that Dio has been defeated, he has started to consider some problems regarding his manga:

For every prefix $A$ of a string, there exists a longest proper prefix $B$ that matches a suffix of $A$. Let the length of this longest prefix $B$ be $L$. When $L=0$, it means $B$ is an empty string.

After each operation, you need to calculate the sum of $L$ for all prefixes of the current string, modulo $998244353$, and output the result to tell Jotaro Kujo so he can compare it with the answer calculated by his Star Platinum.

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

Input

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

The next $n$ lines each contain an operation, formatted as described in the problem statement, for example: 1 x c 2 x

The input data is guaranteed to be valid.

Output

The output should contain $n$ lines, where the $i$-th line contains an integer representing the answer for the string after the $i$-th operation.

Examples

Input 1

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

Output 1

1
1
4
7
1
6
13
6
1
14
14

Note

Explanation of the example: 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$

Constraints

• $20\%$ of the data satisfies $n \le 300$ and $x \le 300$ for each type 1 operation.
• Another $30\%$ of the data satisfies $n \le 100000$ and $x=1$ for each type 1 operation.
• Another $30\%$ of the data satisfies $n \le 100000$ and contains no type 2 operations.
• $100\%$ of the data satisfies $n \le 100000$ and $x \le 10000$ for each type 1 operation.