/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
文字列 S があり、初め S= 1 です。
以下の形式のクエリが Q 個与えられるので順に処理してください。
1 x: S の末尾に数字 x を追加する2: S の先頭の数字を削除する3: S を十進数表記の数とみなした値を 998244353 で割った余りを出力する
制約
- 1 \leq Q \leq 6 \times 10^5
- 1 番目の形式のクエリについて、x \in \{1,2,3,4,5,6,7,8,9\}
- 2 番目の形式のクエリは S が 2 文字以上の時にのみ与えられる
- 3 番目の形式のクエリが 1 個以上存在する
入力
入力は以下の形式で標準入力から与えられる。
Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q
ただし \mathrm{query}_i は i 番目のクエリを表し、以下のいずれかの形式である。
1 x
2
3
出力
3 番目の形式のクエリの個数を q として、q 行出力せよ。i (1 \leq i \leq q) 行目には i 番目の 3 番目の形式のクエリに対する出力をせよ。
入力例 1
3 3 1 2 3
出力例 1
1 12
1 番目のクエリにおいて、S は 1 なので ( 1 を 998244353 で割った余りに等しい) 1 を出力します。
2 番目のクエリにおいて、S は 12 になります。
3 番目のクエリにおいて、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 で割った余りであることに注意してください。
Score : 400 points
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.