As in this problem, if you are asked to find the remainder by \(998244353\), it is good idea to find the remainder automatically using a struct called modint. AtCoder Library provides such a struct. We use it with the following alias declaration (as described in the official document).

using mint = modint998244353;

For a string \(S\) consisting of digits, one can find the remainder by \(998244353\) when it is regarded as a decimal representation of a value as follows:

1. Initialize a variable \(ans\) with \(0\).
2. For each \(i=1,2,\ldots,|S|\), replace \(ans\) with \(10 \times ans + S_i\) (where \(S_i\) is the \(i\)-th digit of \(S\) from the beginning).

However, this costs \(|S|\) steps, so running this every time a query of the third kind is given costs a total of \(\mathrm{O}(Q^2)\) time, which exceeds the execution time limit.

Instead, we always maintain \(ans\), and apply a differential update for each query of the first and second kinds. For the first kind, we can replace \(ans\) with \(10 \times ans + x\). For the second kind, we can subtract (leading digit) \(\times 10^{|S|-1}\) from \(ans\) and then remove the leading digit. Note the following two points:

• Removing an element from a string or a vector costs steps proportional to its size, so we need to use another structure like a deque.
• Finding \(10^{|S|-1}\) every time may cost \(\mathrm{O}(Q^2)\) time, for example if you process \(3 \times 10^5\) queries of the first kind and then \(3 \times 10^5\) queries of the third kind. You can avoid this by precalculating \(10^i\) for \(i=0,1,2,\ldots\), or using the fast exponentiation algorithm. (The pow function in ACL (AtCoder Library)’s modint uses the fast exponentiation, so we use it in the following sample code.)

Sample code (C++)

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace atcoder;
using mint = modint998244353;
using namespace std;

int main() {
	
	int Q;
	cin>>Q;
    
	deque<int> S(1,1);
	mint ans = 1;
	
	for(int i=0;i<Q;i++){
		int t;
		cin>>t;
		if(t==1){
			int x;
			cin>>x;
			S.push_back(x);
			ans = ans*10 + x;
		}
		if(t==2){
			ans -= mint(10).pow(S.size()-1) * S.front();
			S.pop_front();
		}
		if(t==3){
			cout<<ans.val()<<endl;
		}
	}
	
	return 0;
}