J. Insert Force
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of size $$$n$$$ consisting of non-negative integers. At first, your score is $$$0$$$.

You can perform the following operation:

  • Choose an index $$$i$$$ $$$(1 \leq i \lt |a|)$$$, increase your score by $$$(a_i + a_{i+1})$$$.
  • Then, insert $$$(a_i + a_{i+1})$$$ between $$$a_i$$$ and $$$a_{i+1}$$$. Note that after inserting, the size of the array is increased by $$$1$$$.

You need to answer $$$q$$$ independent queries. For the $$$i$$$-th query, given a number $$$x_i$$$, you should find the maximum score you can obtain after performing exactly $$$x_i$$$ operations. Since the answer may be large, output the answer modulo $$$998\,244\,353$$$.

Input

The first line contains an integer $$$t$$$ $$$(1 \le t \le 10^5)$$$, the number of test cases.

For each test case,the input consists of four lines:

  • The first line contains an integer $$$n$$$ $$$(2 \leq n \leq 2 \cdot 10^5)$$$, representing the size of the array.
  • The second line contains $$$n$$$ space-separated integers $$$a_1,a_2,\ldots ,a_n$$$ $$$(0 \le a_i \le 2 \cdot 10^5)$$$.
  • The third line contains an integer $$$q$$$ $$$(1 \leq q \le 2 \cdot 10^5)$$$, representing the number of queries.
  • The fourth line contains $$$q$$$ space-separated integers $$$x_1,x_2,\ldots ,x_q$$$ $$$(1 \le x_i \le 2 \cdot 10^5)$$$.

It is guaranteed that the sum of $$$n$$$ and $$$q$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output $$$q$$$ space-separated integers in a single line, representing the maximum score after performing $$$x_i$$$ operations, modulo $$$998\,244\,353$$$.

Example
Input
2
4
8 7 2 12
2
1 2
6
100000 0 99882 191 99699 487
4
15 4 12 200000
Output
15 40
258200160 1100098 60800104 385867226
Note

In the first test case,

  • If you do exactly $$$1$$$ operation, the optimal scheme is $$$[8,7,2,12] \rightarrow [8,\underline{15},7,2,12]$$$.
  • If you do exactly $$$2$$$ operations, the optimal scheme is $$$[8,7,2,12] \rightarrow [8,7,2,\underline{14},12]\rightarrow [8,7,2,14,\underline{26},12]$$$.