Score : $400$ points

问题描述

我们有一个字符串 $S$。初始时，$S=$ 1。

按照以下格式顺序处理 $Q$ 个查询操作：

• 1 x：在 $S$ 的末尾追加一个数字 $x$。
• 2：删除 $S$ 开头的数字。
• 3：计算以 $S$ 表示的十进制数对 $998244353$ 取模的结果，并打印该数值。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

We have a string $S$. Initially, $S=$ 1.
Process $Q$ queries in the following formats in order.

• 1 x : Append a digit $x$ at the end of $S$.
• 2 : Delete the digit at the beginning of $S$.
• 3 : Print the number represented by $S$ in decimal, modulo $998244353$.

Constraints

• $1 \leq Q \leq 6 \times 10^5$
• For each query in the first format, $x \in \{1,2,3,4,5,6,7,8,9\}$.
• A query in the second format is given only if $S$ has a length of $2$ or greater.
• There is at least one query in the third format.

Input

The input is given from Standard Input in the following format:

$Q$

$\mathrm{query}_1$

$\vdots$

$\mathrm{query}_Q$

Here, $\mathrm{query}_i$ denotes the $i$-th query, which is in one of the following formats:

$1$ $x$

$2$

$3$

Output

Print $q$ lines, where $q$ is the number of queries in the third format. The $i$-th line $(1 \leq i \leq q)$ should correspond to the $i$-th query in the third format.

Sample Input 1

3
3
1 2
3

Sample Output 1

1
12

In the first query, $S$ is 1, so you should print $1$ modulo $998244353$, that is, $1$.
In the second query, $S$ becomes 12.
In the third query, $S$ is 12, so you should print $12$ modulo $998244353$, that is, $12$.

Sample Input 2

3
1 5
2
3

Sample Output 2

5

Sample Input 3

11
1 9
1 9
1 8
1 2
1 4
1 4
1 3
1 5
1 3
2
3

Sample Output 3

0

Be sure to print numbers modulo $998244353$.

update @ 2024/3/10 12:22:06