#P18080. Crossroads

Crossroads

Crossroads

平面上有 nn 条竖直直线 x=aix=a_i 和 mm 条水平直线 y=bjy=b_j。

沿第 ii 条竖直直线移动一个单位距离,需要 tit_i 单位时间;沿任意水平直线移动一个单位距离,需要 t0t_0 单位时间。可以沿直线向任意方向移动,并在交点转向。

记 f(i,j)f(i,j) 为从 (0,0)(0,0) 出发,只沿这些直线移动,到达 (ai,bj)(a_i,b_j) 的最短时间。

有 qq 次询问,每次给出 l,r,d,ul,r,d,u,求

$$\sum_{i=l}^{r}\sum_{j=d}^{u}f(i,j)\pmod{998244353}.$$

输入格式

第一行整数 TT。每组数据包含:

  • 第一行三个整数 n,m,qn,m,q;
  • 第二行 nn 个整数 a1,…,ana_1,\ldots,a_n;
  • 第三行 mm 个整数 b1,…,bmb_1,\ldots,b_m;
  • 第四行 nn 个整数 t1,…,tnt_1,\ldots,t_n;
  • 第五行整数 t0t_0;
  • 接下来 qq 行,每行四个整数 l,r,d,ul,r,d,u。

输出格式

每组输出一行 qq 个整数,按询问顺序输出答案。

数据范围

  • 1≤T≤1041\le T\le10^4;
  • 1≤n,m,q≤2×1051\le n,m,q\le2\times10^5;
  • 0=a1<a2<⋯<an≤1090=a_1<a_2<\cdots<a_n\le10^9;
  • 0=b1<b2<⋯<bm≤1090=b_1<b_2<\cdots<b_m\le10^9;
  • 1≤t0,ti≤1091\le t_0,t_i\le10^9;
  • 1≤l≤r≤n1\le l\le r\le n,1≤d≤u≤m1\le d\le u\le m;
  • 所有数据的 nn 之和、mm 之和、qq 之和分别不超过 2×1052\times10^5。

样例 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