\(d_l\) 桁の（10 進法での）数字列 \(s_l\) と \(d_r\) 桁の数字列 \(s_r\) をこの順に連結させて得られるのは、\(d_l+d_r\) 桁の数字列 \(s_l \cdot 10^{d_r} + s_r\) となります。

そこで、\(\N^2\) 上の二項演算を \((s_l, b_l) \circ (s_r, b_r) = (s_l\cdot b_r + s_r, b_l\cdot b_r)\) で定義します（上記の \(10^d\) を \(b\) と置き直しています）。単位元は \((0, 10^0)\) です。

また、数字一つのみからなる列 \(x\) は \((x, 10^1)\) に相当します。 加えて、ここでは \(998244353\) で割ったあまりとして計算します。

よって、クエリを先読みして追加される数字列を順に並べ、セグ木を用いて（追加・削除に応じて区間を伸縮させて）区間 \(\circ\)-fold を求めることで \(O(Q\log(Q))\) 時間で求めることができます。

なお、queue の演算（push・pop）と queue に入っている要素全体のモノイド積をならし定数時間で行うデータ構造も存在し、（先読みなしで）\(O(Q)\) 時間で解くこともできます。

two-stack queue と呼ばれるデータ構造の応用によって実現されます。（two-stack deque を用いることで deque 演算にも対応できます。）競プロ界隈では SWAG (Sliding Window Aggregation) などと呼ばれることが多そうですが、学術界隈における言い回しとは若干範囲が異なるかもしれません。

参考記事として、https://qiita.com/Shirotsume/items/4a2837b5895ef9a7aeb1 などがありそうです。

また、上記の演算 \(\circ\colon \N^2\to\N^2\) は、（適当な \(b\) や適切な法を用いるものとして）rolling hash の演算と見なすこともでき、いろいろと応用が考えられそうです。

例題：

• https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0355
• https://atcoder.jp/contests/abl/tasks/abl_e