Problem Description

There are $n$ distinct boxes in a row. Initially, the $i$-th box contains $a_i$ items, and the total number of items is $S = \sum_{i = 1}^{n} a_i$. For a non-negative integer array $(b_1, b_2, \ldots, b_n)$ satisfying $\sum_{i = 1}^{n} b_i = S$, consider the following problem:

You want the $i$-th box to contain exactly $b_i$ items. To achieve this, you may perform the following operation any number of times: for two adjacent boxes, move exactly one item from one box to the other. The cost of performing one operation on boxes $i$ and $i + 1$ ($1 \le i < n$) is $w_i$. Note: moving one item from box $\bm{i}$ to box $\bm{i + 1}$ and moving one item from box $\bm{i + 1}$ to box $\bm{i}$ both cost $\bm{w_i}$. You must ensure that during the operations, no box ever has a negative number of items.

Under the above setting, define the minimum cost to reach a state where the $i$-th box contains exactly $b_i$ items from the initial state as $\operatorname{val}(b_1, b_2, \ldots, b_n)$. You need to compute, over all non-negative integer arrays $(b_1, b_2, \ldots, b_n)$ satisfying $\sum_{i = 1}^{n} b_i = S$, the sum of $\operatorname{val}(b_1, b_2, \ldots, b_n)$. Output the answer modulo $998244353$.

Input Format

This problem has multiple test cases. The first line contains a positive integer $T$, the number of test cases.

For each test case, the input consists of three lines. The first line contains a positive integer $n$, the number of boxes. The second line contains $n$ non-negative integers $a_1, a_2, \ldots, a_n$ describing the initial state. The third line contains $n - 1$ non-negative integers $w_1, w_2, \ldots, w_{n - 1}$ describing the cost of moving items.

Output Format

For each test case, output one integer per line: the sum, over all non-negative integer arrays satisfying $\sum_{i = 1}^{n} b_i = S$, of the minimum cost to reach the target state, modulo $998244353$.

2
2
2 3
65472
5
1 3 2 1 1
2 3 3 3

589248
8589

Hint

[Sample Explanation #1]

For the first test case, there are six cases to consider. The pairs $(b_1, b_2)$ are $(0, 5), (1, 4), (2, 3), (3, 2), (4, 1), (5, 0)$.

In the first case, at least $2$ moves are needed, and the minimum cost is $65472 \times 2 = 130944$.

In the second case, at least $1$ move is needed, and the minimum cost is $65472$.

In the third case, no operation is needed, and the minimum cost is $0$.

In the fourth case, at least $1$ move is needed, and the minimum cost is $65472$.

In the fifth case, at least $2$ moves are needed, and the minimum cost is $65472 \times 2 = 130944$.

In the last case, at least $3$ moves are needed, and the minimum cost is $65472 \times 3 = 196416$.

Therefore, the sum of minimum costs is $130944 + 65472 + 0 + 65472 + 130944 + 196416 = 589248$.

[Sample #2]

See box/box2.in and box/box2.ans in the attachment.

This sample satisfies the constraints of test points $5 \sim 8$.

[Sample #3]

See box/box3.in and box/box3.ans in the attachment.

This sample satisfies the constraints of test points $9 \sim 12$.

[Sample #4]

See box/box4.in and box/box4.ans in the attachment.

This sample satisfies the constraints of test points $13 \sim 14$.

[Sample #5]

See box/box5.in and box/box5.ans in the attachment.

This sample satisfies the constraints of test points $15 \sim 16$.

[Sample #6]

See box/box6.in and box/box6.ans in the attachment.

This sample satisfies the constraints of test points $17 \sim 18$.

[Constraints]

It is guaranteed that for every test point and every test case: $2 \le n \le 5 \times {10}^5$, $1 \le S \le 2 \times {10}^6$, $a_i \ge 0$, and $0 \le w_i < 998244353$.

Special Property A: For any $1 \le i < n$, $w_i = 1$.
Special Property B: For any $1 \le i < n - 20$, $a_i = 0$.
Special Property C: There are at most $20$ indices $i \in [1, n]$ such that $a_i \ne 0$.

[Hint]

Some test points have a large input size. To optimize runtime, it is recommended to use a faster input method.

Translated by ChatGPT 5