102983: [Atcoder]ABC298 D - Writing a Numeral

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

问题描述

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

• 1 x : 在$S$的末尾添加一个数字$x$。
• 2 : 删除$S$的开头的数字。
• 3 : 打印以$S$表示的十进制数对$998244353$取模的结果。

约束

• $1 \leq Q \leq 6 \times 10^5$
• 对于第一个格式中的每个查询，$x \in \{1,2,3,4,5,6,7,8,9\}$。
• 只有当$S$的长度为$2$或更大时，才会给出第二个格式的查询。
• 至少有一个第三个格式的查询。

输入

输入按照以下格式从标准输入给出：

$Q$
$\mathrm{query}_1$
$\vdots$
$\mathrm{query}_Q$

其中，$\mathrm{query}_i$表示第$i$个查询，格式如下之一：

$1$ $x$

$2$

$3$

输出

打印$q$行，其中$q$是第三个格式的查询的数量。第$i$行 $(1 \leq i \leq q)$ 应对应第三个格式的第$i$个查询。

样例输入 1

3
3
1 2
3

样例输出 1

1
12

在第一个查询中，$S$是1，因此您应该打印对$998244353$取模的$1$，即$1$。

在第二个查询中，$S$变为12。

在第三个查询中，$S$是12，因此您应该打印对$998244353$取模的$12$，即$12$。

样例输入 2

3
1 5
2
3

样例输出 2

5

样例输入 3

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

样例输出 3

0

确保打印对$998244353$取模的数