동적 수열 구간 아핀 변환 구간 합

$N$개의 정수로 이루어진 수열 $a_0, a_1, ..., a_{N - 1}$이 주어진다.

다음 유형의 쿼리 $Q$개를 순서대로 처리한다:

• 0 $i$ $x$ :
  • $i < |a|$이면, $a_i$의 바로 앞에 $x$를 삽입한다.
  • $i = |a|$이면, $a_{|a| - 1}$의 뒤에 $x$를 삽입한다.
• 1 $i$ : $a_i$를 제거한다(남은 원소들은 이어 붙인다).
• 2 $l$ $r$ : $a_l, a_{l + 1}, a_{l + 2}, \dots, a_{r - 1}$을 뒤집는다.
• 3 $l$ $r$ $b$ $c$ : 각 $i = l, l + 1, l + 2, \dots, {r - 1}$에 대해, $a_i \gets b \times a_i + c$로 갱신한다.
• 4 $l$ $r$ : $\sum_{i = l}^{r - 1} a_i \bmod 998244353$을 출력한다.

제약 조건

• $1 \le N, Q \le 500000$
• $0 \le a_i \lt 998244353$
• 형식 0 $i$ $x$에 대해:
  • $0 \le i \le ($해당 시점의 $|a|)$
  • $0 \le x \lt 998244353$
• 형식 1 $i$에 대해:
  • $0 \le i \lt ($해당 시점의 $|a|)$
• 형식 2 $l$ $r$에 대해:
  • $0 \le l \lt r \le ($해당 시점의 $|a|)$
• 형식 3 $l$ $r$ $b$ $c$에 대해:
  • $0 \le l \lt r \le ($해당 시점의 $|a|)$
  • $0 \le b \lt 998244353$
  • $0 \le c \lt 998244353$
• 형식 4 $l$ $r$에 대해:
  • $0 \le l \lt r \le ($해당 시점의 $|a|)$

$N$ $Q$
$a_0$ $a_1$ ... $a_{N - 1}$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$

4 $l$ $r$ : $\sum_{i = l}^{r - 1} a_i \bmod 998244353$을 출력한다.