덱 전체 합성 연산

처음에 비어 있는 일차 함수의 수열 $f = ()$이 있다. $Q$개의 쿼리를 처리한다.

• 0 $a$ $b$: 일차 함수 $\lambda x. ax + b$을 수열 $f$의 맨 앞에 추가한다.
• 1 $a$ $b$: 일차 함수 $\lambda x. ax + b$을 수열 $f$의 맨 뒤에 추가한다.
• 2: 수열 $f$의 맨 앞에 있는 일차 함수를 제거한다.
• 3: 수열 $f$의 맨 뒤에 있는 일차 함수를 제거한다.
• 4 $x$: $f = (f_{l}, \dots, f_{r - 1})$이라 하고, $f _ {r - 1}(f _ {r - 2}(\dots (f _ l(x)) \dots)) \bmod 998244353$을 출력한다. $f = ()$이면 $x$을 출력한다.

제약 조건

• $1 \leq Q \leq 500,000$
• $1 \leq a \lt 998244353$
• $0 \leq b, x \lt 998244353$
• 쿼리 $2$ 또는 쿼리 $3$가 주어질 때 수열 $f$은 비어 있지 않다.

$Q$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$

4 $x$: $f = (f_{l}, \dots, f_{r - 1})$이라 하고, $f _ {r - 1}(f _ {r - 2}(\dots (f _ l(x)) \dots)) \bmod 998244353$을 출력한다. $f = ()$이면 $x$을 출력한다.