8843: [yosupo] Data Structure - Queue Operate All Composite
[Creator : ]
Description
There is an initially empty sequence of linear functions $f = ()$. Process $Q$ queries.
- 0 $a$ $b$: Add a linear function $\lambda x. ax + b$ to the end of the sequence $f$.
- 1: Remove the linear function at the beginning of the sequence $f$.
- 2 $x$: Let $f = (f_{l}, \dots, f_{r - 1})$, output $f _ {r - 1}(f _ {r - 2}(\dots (f _ l(x)) \dots)) \bmod 998244353$. Output $x$ if $f = ()$.
- 0 $a$ $b$: Add a linear function $\lambda x. ax + b$ to the end of the sequence $f$.
- 1: Remove the linear function at the beginning of the sequence $f$.
- 2 $x$: Let $f = (f_{l}, \dots, f_{r - 1})$, output $f _ {r - 1}(f _ {r - 2}(\dots (f _ l(x)) \dots)) \bmod 998244353$. Output $x$ if $f = ()$.
Input
$Q$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$
Constraints
$1 \leq Q \leq 500,000$
$1 \leq a \lt 998244353$
$0 \leq b, x \lt 998244353$
The sequence $f$ is not empty when query $1$ comes.
$1 \leq a \lt 998244353$
$0 \leq b, x \lt 998244353$
The sequence $f$ is not empty when query $1$ comes.
Sample 1 Input
6
0 4 5
2 3
0 2 1
2 2
1
2 3
Sample 1 Output
17
27
7
Sample 2 Input
1
2 1333
Sample 2 Output
1333