8844: [yosupo] Data Structure - Deque 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 beginning of the sequence $f$.
- 1 $a$ $b$: Add a linear function $\lambda x. ax + b$ to the end of the sequence $f$.
- 2: Remove the linear function at the beginning of the sequence $f$.
- 3: Remove the linear function at the end of the sequence $f$.
- 4 $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 beginning of the sequence $f$.
- 1 $a$ $b$: Add a linear function $\lambda x. ax + b$ to the end of the sequence $f$.
- 2: Remove the linear function at the beginning of the sequence $f$.
- 3: Remove the linear function at the end of the sequence $f$.
- 4 $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 $2$ or query $3$ comes.
$1 \leq a \lt 998244353$
$0 \leq b, x \lt 998244353$
The sequence $f$ is not empty when query $2$ or query $3$ comes.
Sample 1 Input
6
1 4 5
4 3
0 2 1
4 2
3
4 3
Sample 1 Output
17
25
7
Sample 2 Input
1
4 1333
Sample 2 Output
1333