题目背景

小 E 终于在今天收回了被妈妈保管的压岁钱。

作为有远见的收藏家，小 E 知道，如果她从现在开始收集东西，以后就会变得值钱了。

小 E 的世界里有一些纸币。她知道这些纸币未来的价值，但遗憾的是，这些纸币只能从小换到大。如何是好？

题目描述

给定 $n$ 种物品，每种物品 $i$ 价值为 $v_i$，个数为 $c_i$。

定义总价值为 $\sum\limits_{i=1}^nc_iv_i$，你可以进行一些（可能为 $0$）次操作来最大化总价值。

一次操作为：选定一个 $i$ 满足 $c_i \geq x_i$，让 $c_i\gets c_i - x_i$，$c_{i+1}\gets c_{i+1}+ 1$。

输出最大的总价值对 $998,\!244,\!353$ 取模。

注意，你需要最大化总价值，再对 $998,\!244,\!353$ 取模，而不是最大化「总价值对 $998,\!244,\!353$ 取模的值」。

输入格式

本题有多组数据。

第一行一个正整数 $sid$，表示该测试数据所属子任务编号。

第二行一个正整数 $t$，表示数据组数。对于每组数据：

• 输入共四行。
• 第一行，一个正整数 $n$，表示钱的种数。
• 第二行，$n$ 个非负整数分别表示 $v_1, v_2 \dots v_n$。
• 第三行，$n$ 个非负整数分别表示 $c_1, c_2 \dots c_n$。
• 第四行，$n - 1$ 个正整数分别表示 $x_1, x_2 \dots x_{n - 1}$。

输出格式

输出 $t$ 行，每行一个整数，表示物品总价值的最大值。所有答案对 $998244353$ 取模。

0
2
2
1 5
5 1
4
10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

11
172998509

提示

样例解释

对于样例的第一组数据，$v=[1,5]$，$c=[5,1]$，$x=[4]$。可以选定 $i=1$ 进行一次操作，此时 $c=[1,2]$，总价值为 $1\cdot 1+5\cdot 2=11$，可以证明它是最大的。

数据规模与约定

本题采用捆绑测试。

下面是各 Subtask 的特殊性质，斜杠表示该栏无特殊限制。

• 特殊性质 A：$x_i = 10^9$。
• 特殊性质 B：$x_i = 1$。
• 特殊性质 C：所有 $c_i, v_i$ 均在 $[0, 10^5]$ 间均匀随机生成；所有 $x_i$ 均在 $[1, 10^5]$ 间均匀随机生成。

对于所有数据，$1\le t \le 10^5$，$2\le n$，$\sum n\le 2\times 10^5$，$1\le x_i\le 10^9$，$0\le c_i,v_i\le 10^9$。