题目描述

我们有一个字符串 $S$。最初，$S=$ 1。
按顺序处理 $Q$ 个查询，格式如下所示。

• 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，所以你应该打印 $1$ 对 $998244353$ 取模，即 $1$。
在第二个查询中，$S$ 变为 12。
在第三个查询中，$S$ 是 12，所以你应该打印 $12$ 对 $998244353$ 取模，即 $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$。