Crossroads
平面上有 n 条竖直直线 x=ai 和 m 条水平直线 y=bj。
沿第 i 条竖直直线移动一个单位距离,需要 ti 单位时间;沿任意水平直线移动一个单位距离,需要 t0 单位时间。可以沿直线向任意方向移动,并在交点转向。
记 f(i,j) 为从 (0,0) 出发,只沿这些直线移动,到达 (ai,bj) 的最短时间。
有 q 次询问,每次给出 l,r,d,u,求
$$\sum_{i=l}^{r}\sum_{j=d}^{u}f(i,j)\pmod{998244353}.$$
输入格式
第一行整数 T。每组数据包含:
- 第一行三个整数 n,m,q;
- 第二行 n 个整数 a1,…,an;
- 第三行 m 个整数 b1,…,bm;
- 第四行 n 个整数 t1,…,tn;
- 第五行整数 t0;
- 接下来 q 行,每行四个整数 l,r,d,u。
输出格式
每组输出一行 q 个整数,按询问顺序输出答案。
数据范围
- 1≤T≤104;
- 1≤n,m,q≤2×105;
- 0=a1<a2<⋯<an≤109;
- 0=b1<b2<⋯<bm≤109;
- 1≤t0,ti≤109;
- 1≤l≤r≤n,1≤d≤u≤m;
- 所有数据的 n 之和、m 之和、q 之和分别不超过 2×105。
样例 1
输入:
1
3 2 3
0 2 10
0 3
100 2 1
1
1 3 1 2
2 3 2 2
1 1 1 1
输出:
43 21 0