P5287 [HNOI2019] JOJO

JoJo's Bizarre Adventure is a very popular manga. The main character in the manga often likes to shout many consecutive “Ora” or “Muda”.

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$.

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.

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

#### Sample Explanation | Operation | Current string | Answer | | :----------: | :----------: | :----------: | | $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 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