This problem focuses on designing a monoid for function composition. Function composition is also explained in AtCoder Algorithm Lectures, “Designing Monoids for Range Queries,” Chapter 6. Here is a short excerpt:

• Suppose each element \(X_i\) of a sequence corresponds to a function \(F_{X_i}\).
• For a sequence \(X=(X_0, X_1, \dots, X_{n-1})\), write \(F_X\) for the composition of \(F_{X_0}, F_{X_1}, \dots, F_{X_{n-1}}\), and use \(F_X\) as the interval information \(f(X)\).

For the concatenation \(XY\) of sequences \(X, Y\), we have \(F_{XY} = F_Y \circ F_X\). Thus, using function composition as \(\mathrm{op}\) gives \(\mathrm{op}(f(X), f(Y)) = f(XY)\).

Function composition satisfies associativity, \((H \circ G) \circ F = H \circ (G \circ F)\). With the identity function as the identity element, the set of all functions from \(T\) to \(T\) forms a monoid under composition.

The idea is to implement function composition as \(\mathrm{op}\).

Let us consider this problem with this in mind. Define

• \(\mathrm{MOD}(x) = x \bmod 998244353\)
• \(\mathrm{ADD}_a(x) = x + a\)

The problem asks us to compose these \(2\) types of functions up to \(N\) times.

The simplest way to represent the composition is to store its steps \(1\) by \(1\). However, storing \(N\) composition steps and evaluating the result at \(x\) each take \(\mathrm{O}(N)\) time, which exceeds the time limit. We therefore need a better way to store the function.

Observing the behavior of these functions gives the following two facts:

• Consecutive \(\mathrm{ADD}\) functions can be combined.
• If there are at least \(2\) \(\mathrm{MOD}\) functions, there is an equivalent representation with just \(1\).

The first fact follows because “add \(a\)” followed by “add \(b\)” can be combined into “add \(a+b\).” In formulas,

\[ \begin{aligned} &(\mathrm{ADD}_b \circ \mathrm{ADD}_a)(x) \\ &= (x+a) + b \\ &= \mathrm{ADD}_{a+b}(x) \end{aligned} \]

The second fact follows intuitively because all additions before the last modulo operation can be combined. In formulas,

\[ \begin{aligned} &(\mathrm{ADD}_c \circ \mathrm{MOD} \circ \mathrm{ADD}_b \circ \mathrm{MOD} \circ \mathrm{ADD}_a)(x) \\ &= ((((x+a) \bmod {998244353}) + b)\bmod{998244353})+c \\ &= ((x+a+b) \bmod {998244353}) + c \\ &= (\mathrm{ADD}_c \circ \mathrm{MOD} \circ \mathrm{ADD}_{a+b})(x) \end{aligned} \]

Based on these facts, define

\[G_{a,b} = \mathrm{ADD}_b \circ \mathrm{MOD} \circ \mathrm{ADD}_a\]

Then we obtain the following fact:

• Any function formed by composing \(\mathrm{MOD}\) and \(\mathrm{ADD}_a\) multiple times in any order can be written either as \(\mathrm{ADD}_a\) for some integer \(a\), or as \(G_{a,b}\) for some integers \(a,b\).

(Proof) We can represent \(\mathrm{MOD}\) and the identity function \(\mathrm{Id}\) as

\[\mathrm{MOD} = G_{0,0}, \mathrm{Id} = \mathrm{ADD}_0\]

so the functions before composition satisfy the condition. Also, the \(4\) combinations of compositions of \(\mathrm{ADD}\) and \(G\) satisfy

\[\mathrm{ADD}_b \circ \mathrm{ADD}_a = \mathrm{ADD}_{a+b}\]

\[\mathrm{ADD}_c \circ G_{a,b} =G_{a,b+c}\]

\[G_{b,c} \circ \mathrm{ADD}_a =G_{a+b,c}\]

\[G_{c,d} \circ G_{a,b} = G_{a+b+c,d}\]

Thus, the condition continues to hold after each composition. (End of proof)

By storing a function in the form \(\mathrm{ADD}_a\) or \(G_{a,b}\), we can perform both composition and evaluation in \(\mathrm{O}(1)\) time. A concrete implementation is as follows:

struct S {
  long long A, B;
  bool get_mod;
};

S op(S x, S y) {
  if (y.get_mod) return {(x.A + x.B + y.A) % mod, y.B, true};
  if (x.get_mod) return {x.A, x.B + y.A, true};
  return {x.A + y.A, 0, false};
}

S e() { return {0, 0, false}; }

Implementing the ideas explained above solves the problem. The time complexity is \(\mathrm{O}(N + Q \log N)\), which is sufficiently fast.

• Sample implementation, C++