There are $n$ distinct boxes arranged 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 any array of non-negative integers $(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 can perform the following operation any number of times: choose two adjacent boxes and 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: The cost to move one item from box $i$ to box $i + 1$ is the same as moving one item from box $i + 1$ to box $i$, which is $w_i$. You must ensure that the number of items in any box never becomes negative during the operations.

Under the above problem, define $\operatorname{val}(b_1, b_2, \ldots, b_n)$ as the minimum cost to reach the state where the $i$-th box has exactly $b_i$ items from the initial state. You need to calculate the sum of $\operatorname{val}(b_1, b_2, \ldots, b_n)$ over all arrays of non-negative integers $(b_1, b_2, \ldots, b_n)$ such that $\sum_{i = 1}^{n} b_i = S$. Output the result modulo $998244353$.

Input

This problem contains multiple test cases.

The first line contains a positive integer $T$, representing 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 costs of moving items.

Output

For each test case, output a single integer representing the sum of the minimum costs for all arrays $(b_1, b_2, \ldots, b_n)$ satisfying $\sum_{i = 1}^{n} b_i = S$, modulo $998244353$.

Examples

Input 1

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

Output 1

589248
8589

Note 1

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

For the first scenario, at least $2$ moves are required, with a minimum cost of $65472 \times 2 = 130944$.

For the second scenario, at least $1$ move is required, with a minimum cost of $65472$.

For the third scenario, no operations are needed, with a minimum cost of $0$.

For the fourth scenario, at least $1$ move is required, with a minimum cost of $65472$.

For the fifth scenario, at least $2$ moves are required, with a minimum cost of $65472 \times 2 = 130944$.

For the last scenario, at least $3$ moves are required, with a minimum cost of $65472 \times 3 = 196416$.

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

Examples 2-6

See the provided files. These examples satisfy the constraints for test cases $5 \sim 16$.

Subtasks

It is guaranteed that for any 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 all $1 \le i < n$, $w_i = 1$.
• Special Property B: For all $1 \le i < n - 20$, $a_i = 0$.
• Special Property C: At most $20$ indices $i \in [1, n]$ satisfy $a_i \ne 0$.

Note

This problem has test cases with large input sizes. To optimize execution time, we recommend using fast I/O methods.