题目描述

有 $n$ 个不同的盒子排成一排。在初始状态下，第 $i$ 个盒子放有 $a_i$ 个货物，总货物数量为 $S = \sum_{i = 1}^{n} a_i$。对于非负整数数组 $(b_1, b_2, \ldots, b_n)$ 满足 $\sum_{i = 1}^{n} b_i = S$，考察以下问题：

你想让第 $i$ 个盒子中拥有恰好 $b_i$ 个货物，为此你可以做如下操作若干次：对两个相邻的盒子，把其中一个盒子的恰好一个货物移动至另一个。对 $i, i + 1$（$1 \le i < n$）号盒子做一次操作的代价为 $w_i$。注意：将 $\boldsymbol{i}$ 号盒子的一个货物移动到 $\boldsymbol{i + 1}$ 号盒子和将 $\boldsymbol{i + 1}$ 号盒子的一个货物移动到 $\boldsymbol{i}$ 号盒子的代价都是 $\boldsymbol{w_i}$。你需要保证在操作中不存在盒子中的货物数量是负数。

在以上问题下，定义从初始状态达到第 $i$ 个盒子拥有恰好 $b_i$ 个货物的状态的最小代价为 $\operatorname{val}(b_1, b_2, \ldots, b_n)$，你需要求出对所有满足 $\sum_{i = 1}^{n} b_i = S$ 的非负整数数组 $(b_1, b_2, \ldots, b_n)$，$\operatorname{val}(b_1, b_2, \ldots, b_n)$ 的和。输出这个答案对 $998244353$ 取模后的结果。

输入格式

本题有多组测试数据。输入的第一行包含一个正整数 $T$，表示测试数据组数。

对于每组数据，输入共三行。第一行一个正整数 $n$ 表示盒子的个数，第二行 $n$ 个正整数 $a_1, a_2, \ldots, a_n$ 描述初始状态，第三行 $n - 1$ 个正整数 $w_1, w_2, \ldots, w_{n - 1}$ 描述移动货物的代价。

输出格式

对于每组测试数据输出一行一个整数，表示对于所有满足 $\sum_{i = 1}^{n} b_i = S$ 的非负整数数组，达到目标的代价的最小值之和模 $998244353$ 的结果。

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

589248
8589

样例 2

见附加文件中 [box2.in](file:box2.in) 和 [box2.ans](file:box2.ans)。

这个样例满足测试点 $5 \sim 8$ 的限制。

样例 3

见附加文件中 [box3.in](file:box3.in) 和 [box3.ans](file:box3.ans)。

这个样例满足测试点 $9 \sim 12$ 的限制。

样例 4

见附加文件中 [box4.in](file:box4.in) 和 [box4.ans](file:box4.ans)。

这个样例满足测试点 $13 \sim 14$ 的限制。

样例 5

见附加文件中 [box5.in](file:box5.in) 和 [box5.ans](file:box5.ans)。

这个样例满足测试点 $15 \sim 16$ 的限制。

样例 6

见附加文件中 [box6.in](file:box6.in) 和 [box6.ans](file:box6.ans)。

这个样例满足测试点 $17 \sim 18$ 的限制。

数据范围

保证对于任何测试点的任何一组数据，有 $2 \le n \le 5 \times {10}^5$，$1 \le S \le 2 \times {10}^6$，$a_i \ge 0$，$0 \le w_i < 998244353$。

测试点编号	$T \le$	$n \le$	$S \le$	特殊性质
$1$	$1000$	$5$		A
$2$
$3$	$5$	$9$		无
$4$
$5$	$10$	$2000$	$2000$
$6$
$7$
$8$
$9$			$2 \times {10}^5$
$10$
$11$
$12$
$13$	$2$	$2 \times {10}^5$		B
$14$
$15$				AC
$16$
$17$				无
$18$
$19$	$5$	$5 \times {10}^5$	$2 \times {10}^6$
$20$

特殊性质 A：对于任意 $1 \le i < n$，$w_i = 1$。
特殊性质 B：对于任意 $1 \le i < n - 20$，$a_i = 0$。
特殊性质 C：最多只有 $20$ 个 $i \in [1, n]$ 满足 $a_i \ne 0$。

提示

本题有读入量较大的测试点，为了优化程序运行的时间，我们建议你采用较为快速的读入方式。