C. Duplication
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have an array $$$a$$$ that has an initial length of $$$n$$$. Process the following queries:

  • 1 x: Append $$$x$$$ to the end of the array.
  • 2: Delete the last element of the array.
  • 3: Reverse the array.
  • 4: Clone the array and append the clone to the end of the array.
  • 5: Query the sum of all elements in the array, modulo $$$998244353$$$.
Input

The first line consists of an integer $$$n$$$ $$$(1 \le n \le 5 \cdot 10^5)$$$, the initial size of the array.

The second line consists of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(0 \le a_i \le 10^9)$$$, the initial array.

The third line consists of an integer $$$q$$$ $$$(1 \le q \le 5 \cdot 10^5)$$$, the number of queries.

The next $$$q$$$ lines contain the queries as described above, subject to the following constraints:

  • In queries of Type $$$1$$$, $$$0 \le x \le 10^9$$$.
  • In queries of Type $$$2$$$, the array is not currently empty.
  • It is guaranteed that there is at least one query of Type $$$5$$$.

—

Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Test $$$1$$$ has no queries of Types $$$1$$$, $$$2$$$, $$$3$$$, or $$$4$$$.

Tests $$$2-4$$$ have no queries of Type $$$4$$$.

Tests $$$5-7$$$ satisfy $$$n, q \le 10$$$.

Tests $$$8-9$$$ have no queries of Types $$$1$$$, $$$2$$$, or $$$3$$$.

Tests $$$10-11$$$ have no queries of Type $$$2$$$.

Tests $$$12-15$$$ have no queries of Type $$$3$$$.

Tests $$$16-20$$$ satisfy no additional constraints.

Output

For each query of Type $$$5$$$, output one integer — the sum of all elements in the array, modulo $$$998244353$$$.

Example
Input
5
1 3 2 4 5
5
4
2
3
1 3
5
Output
28
Note

Consider the sample test.

After query $$$\texttt{4}$$$, the array becomes $$$\{1, 3, 2, 4, 5, 1, 3, 2, 4, 5\}$$$.

After query $$$\texttt{2}$$$, the array becomes $$$\{1, 3, 2, 4, 5, 1, 3, 2, 4\}$$$.

After query $$$\texttt{3}$$$, the array becomes $$$\{4, 2, 3, 1, 5, 4, 2, 3, 1\}$$$.

After query $$$\texttt{1 3}$$$, the array becomes $$$\{4, 2, 3, 1, 5, 4, 2, 3, 1, 3\}$$$.

To answer query $$$\texttt{5}$$$, compute the sum $$$4 + 2 + 3 + 1 + 5 + 4 + 2 + 3 + 1 + 3 = 28$$$.