题目描述

33DAI 给自己安排了 $n$ 天的出题进度，下标从 $1$ 开始。第 $i$ 天他原本计划出 $a_i$ 道题，但实际出了 $b_i$ 道题。

记第 $i$ 天结束时的余额为 $bal_i$（$bal_0 = 0$），它表示到当天为止的净账：

• $bal_i > 0$：还净欠 $bal_i$ 道题；
• $bal_i < 0$：反而净多出了 $-bal_i$ 道题；
• $bal_i = 0$：刚好两清。

第 $i$ 天一共需要出多少道题，由前一天的余额决定：

• 若 $bal_{i-1} > 0$（前面欠了题），欠的这些题要额外按 $2$ 倍补上，所以这一天一共需要出 $a_i + 2 \times bal_{i-1}$ 道；
• 若 $bal_{i-1} \le 0$（前面不欠题，或多出了题），多出的部分直接算作今天已经出了的题，所以这一天只需要出 $a_i + bal_{i-1}$ 道。

当天结束时，余额等于「实际出的题数」减去「当天一共需要出的题数」：

$$bal_i = \begin{cases} b_i - (a_i + 2 \times bal_{i-1}), & bal_{i-1} > 0 \\[2pt] b_i - (a_i + bal_{i-1}), & bal_{i-1} \le 0 \end{cases}$$

这个余额会一路带到后面的天数里继续参与计算。

注意式子里的 $bal_{i-1}$ 是可以为负的：当 $bal_{i-1} < 0$ 且 $-bal_{i-1} > a_i$ 时，$a_i + bal_{i-1}$ 会小于 $0$，表示这一天一道题都不用出（前面多出的题已经把它盖过去了），此时余额依然按上面的式子计算。

$n$ 天结束后，记 $bal_n$ 的绝对值为 $ans$：若 $bal_n > 0$，$ans$ 就是 33DAI 还欠的题数；若 $bal_n \le 0$，$ans$ 就是最后净多出的题数。请输出 $ans$ 对 $998244353$ 取模的结果。

输入格式

输入的第一行是一个整数 $t$，表示测试用例组数。

接下来依次给出 $t$ 组测试用例，每组测试用例的格式为：

• 第一行一个整数 $n$，表示计划的天数；
• 第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每天原本计划出的题数；
• 第三行 $n$ 个整数 $b_1, b_2, \dots, b_n$，表示每天实际出的题数。

输出格式

对每组测试用例输出一行一个整数，表示该组的 $ans$ 对 $998244353$ 取模的结果。

2
3
5 6 7
3 0 40
3
6 6 6
6 6 6

37
0

样例 1 解释

第 1 组：$a = (5, 6, 7)$，$b = (3, 0, 40)$。

• 第 $1$ 天：$bal_0 = 0$，属于 $bal_0 \le 0$ 的情形，需要出 $5 + 0 = 5$ 道，实际出了 $3$ 道，$bal_1 = 3 - 5 = -2$（净多出 $2$ 道）；
• 第 $2$ 天：$bal_1 = -2 \le 0$，多出的 $2$ 道算作今天出的，需要出 $6 + (-2) = 4$ 道，实际出了 $0$ 道，$bal_2 = 0 - 4 = -4$（净多出 $4$ 道）；
• 第 $3$ 天：$bal_2 = -4 \le 0$，需要出 $7 + (-4) = 3$ 道，实际出了 $40$ 道，$bal_3 = 40 - 3 = 37$。

最终 $bal_3 = 37 > 0$，即还净欠 $37$ 道，$ans = 37$，对 $998244353$ 取模仍是 $37$，输出 37。

第 2 组：这三天每天原本计划出 $6$ 道、实际也出了 $6$ 道，于是一直有 $bal_1 = bal_2 = bal_3 = 0$，$ans = 0$，输出 0。

4
2
5 5
3 0
3
3 0 8
9 0 10
3
4 4 4
10 0 20
2
7 5
0 0

3
14
32
2

样例 2 解释

第 1 组：$a = (5, 5)$，$b = (3, 0)$。

• 第 $1$ 天需要 $5$ 道、出了 $3$ 道，$bal_1 = -2$；
• 第 $2$ 天需要 $5 + (-2) = 3$ 道、出了 $0$ 道，$bal_2 = 0 - 3 = -3$。

最终 $bal_2 = -3 \le 0$，即最后净多出 $3$ 道，$ans = 3$，输出 3。

第 2 组：$a = (3, 0, 8)$，$b = (9, 0, 10)$。

• 第 $1$ 天需要 $3$ 道、出了 $9$ 道，$bal_1 = 9 - 3 = 6$（净欠 $6$ 道）；
• 第 $2$ 天：$bal_1 = 6 > 0$，欠的 $6$ 道要按 $2$ 倍补，需要出 $0 + 2 \times 6 = 12$ 道，实际出了 $0$ 道，$bal_2 = 0 - 12 = -12$；
• 第 $3$ 天：$bal_2 = -12 \le 0$，需要出 $8 + (-12) = -4$ 道，也就是一道都不用出；实际出了 $10$ 道，$bal_3 = 10 - (-4) = 14$。

最终 $bal_3 = 14 > 0$，即还净欠 $14$ 道，$ans = 14$，输出 14。

第 3 组：$a = (4, 4, 4)$，$b = (10, 0, 20)$。

• 第 $1$ 天需要 $4$ 道、出了 $10$ 道，$bal_1 = 6$；
• 第 $2$ 天需要 $4 + 2 \times 6 = 16$ 道、出了 $0$ 道，$bal_2 = -16$；
• 第 $3$ 天需要 $4 + (-16) = -12$ 道（一道都不用出）、出了 $20$ 道，$bal_3 = 20 - (-12) = 32$。

最终 $bal_3 = 32 > 0$，即还净欠 $32$ 道，$ans = 32$，输出 32。

第 4 组：$a = (7, 5)$，$b = (0, 0)$。

• 第 $1$ 天需要 $7$ 道、出了 $0$ 道，$bal_1 = -7$；
• 第 $2$ 天需要 $5 + (-7) = -2$ 道（一道都不用出）、出了 $0$ 道，$bal_2 = 0 - (-2) = 2$。

最终 $bal_2 = 2 > 0$，即还净欠 $2$ 道，$ans = 2$，输出 2。

样例 3

见 owed3.in 与 owed3.ans。

样例 4

见 owed4.in 与 owed4.ans。

样例 5

见 owed5.in 与 owed5.ans。

数据范围

对于所有测试数据，保证：

• $1 \le t \le 500$；
• $1 \le n \le 20$；
• $0 \le a_i \le 10^9$，$0 \le b_i \le 10^9$；
• 所有测试用例的 $n$ 之和不超过 $10^5$。

子任务

本题共 20 个测试点，按测试点计分：

测试点	分值	每个测试点	特殊限制
$1 \sim 6$	$30$	$5$	$n \le 8$ 且 $a_i, b_i \le 1000$
$7 \sim 12$			$n \le 15$ 且 $a_i, b_i \le 10^5$
$13 \sim 20$	$40$		无额外限制

每个测试点单独评分，全部测试点的得分之和即为本题得分。