$n$ 本の垂直線（$i$ 番目の直線は $x = a_i$）と、$m$ 本の水平線（$i$ 番目の直線は $y = b_i$）が与えられます。$i$ 番目の垂直線に沿って距離 $1$ だけ移動するには $t_i$ 単位時間がかかり、任意の水平線に沿って距離 $1$ だけ移動するには $t_0$ 単位時間がかかります。

垂直線と水平線のみに沿って $(0, 0)$ から $(a_i, b_j)$ へ移動するのに必要な最小時間を $f(i, j)$ とします。$q$ 個のクエリに答えてください。各クエリは 4 つの整数 $l, r, d, u$ で表され、次の値を計算する必要があります：

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

答えは非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りを出力してください。

入力

入力は複数のテストケースからなります。入力の 1 行目には、テストケースの数を表す整数 $T$ ($1 \le T \le 10^4$) が与えられます。各テストケースについて：

1 行目には、垂直線の本数、水平線の本数、クエリの数を表す 3 つの整数 $n, m, q$ ($1 \le n, m, q \le 2 \times 10^5$) が与えられます。

2 行目には、垂直線の $x$ 座標を表す $n$ 個の整数 $a_1, a_2, \dots, a_n$ ($0 = a_1 < a_2 < \dots < a_n \le 10^9$) が与えられます。

3 行目には、水平線の $y$ 座標を表す $m$ 個の整数 $b_1, b_2, \dots, b_m$ ($0 = b_1 < b_2 < \dots < b_m \le 10^9$) が与えられます。

4 行目には $n$ 個の整数 $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 10^9$) が与えられます。ここで $t_i$ は $i$ 番目の垂直線に沿って距離 $1$ だけ移動するのに必要な時間を表します。

5 行目には、任意の水平線に沿って距離 $1$ だけ移動するのに必要な時間を表す 1 つの整数 $t_0$ ($1 \le t_0 \le 10^9$) が与えられます。

続く $q$ 行のうち $i$ 行目には、$i$ 番目のクエリを表す 4 つの整数 $l_i, r_i, d_i, u_i$ ($1 \le l_i \le r_i \le n, 1 \le d_i \le u_i \le m$) が与えられます。

すべてのテストケースにおける $n$ の総和、$m$ の総和、および $q$ の総和がいずれも $2 \times 10^5$ を超えないことが保証されます。

出力

各テストケースについて、$q$ 個の整数を 1 行に出力してください。ここで $i$ 番目の整数は、$i$ 番目のクエリに対する答えを $998\,244\,353$ で割った余りです。

入出力例

入力例 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

出力例 1

43 21 0