写数字

题目描述

我们有一个字符串 $S$。初始时,$S$ 为 1。

按顺序处理以下格式的 $Q$ 个查询。

1 x : 在 $S$ 的末尾追加数字 $x$。

2 : 删除 $S$ 开头的数字。

3 : 输出 $S$ 表示的十进制数对 $998244353$ 取模的结果。

输入格式

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

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

其中,$\mathrm{query}_i$ 表示第 $i$ 个查询,格式为以下三种之一:

$1$ $x$

$2$

$3$

输出格式

设第三类查询共有 $q$ 个,输出 $q$ 行。第 $i$ 行 $(1 \le i \le q)$ 对应第 $i$ 个第三类查询的答案。

样例

3
3
1 2
3

1
12

第一个查询中 $S$ 是 1,应输出 $1$ 对 $998244353$ 取模的结果,即 $1$。

第二个查询后,$S$ 变为 12。

第三个查询中 $S$ 是 12,应输出 $12$ 对 $998244353$ 取模的结果,即 $12$。

3
1 5
2
3

5

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

0

务必输出对 $998244353$ 取模后的结果。

数据范围

• $1 \le Q \le 6 \times 10^5$
• 第一类查询中,$x \in \{1,2,3,4,5,6,7,8,9\}$。
• 第二类查询仅在 $S$ 的长度至少为 $2$ 时给出。
• 至少有一个第三类查询。