俾定 $n$ 條垂直線，其中第 $i$ 條線為 $x = a_i$，以及 $m$ 條水平線，其中第 $i$ 條線為 $y = b_i$。沿第 $i$ 條垂直線移動 $1$ 單位距離需要 $t_i$ 單位時間，沿任意水平線移動 $1$ 單位距離需要 $t_0$ 單位時間。

設 $f(i, j)$ 為只沿住呢啲垂直線同水平線由 $(0, 0)$ 到達 $(a_i, b_j)$ 所需嘅最少時間。你需要回答 $q$ 個詢問，每個詢問由四個整數 $l, r, d, u$ 表示，你需要計算：

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

由於答案可能好大，請將答案對 $998\,244\,353$ 取模後輸出。

輸入格式

輸入包含多組測試資料。第一行包含一個整數 $T$ ($1 \le T \le 10^4$)，代表測試資料組數。對於每組測試資料：

第一行包含三個整數 $n, m, q$ ($1 \le n, m, q \le 2 \times 10^5$)，分別代表垂直線嘅數量、水平線嘅數量同詢問次數。

第二行包含 $n$ 個整數 $a_1, a_2, \dots, a_n$ ($0 = a_1 < a_2 < \dots < a_n \le 10^9$)，代表垂直線嘅 $x$ 座標。

第三行包含 $m$ 個整數 $b_1, b_2, \dots, b_m$ ($0 = b_1 < b_2 < \dots < b_m \le 10^9$)，代表水平線嘅 $y$ 座標。

第四行包含 $n$ 個整數 $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 10^9$)，其中 $t_i$ 代表沿第 $i$ 條垂直線移動 $1$ 單位距離所需嘅時間。

第五行包含一個整數 $t_0$ ($1 \le t_0 \le 10^9$)，代表沿任意水平線移動 $1$ 單位距離所需嘅時間。

接住落嚟嘅 $q$ 行，第 $i$ 行包含四個整數 $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$)，代表第 $i$ 個詢問。

保證所有測試資料中 $n$ 嘅總和、$m$ 嘅總和以及 $q$ 嘅總和都唔超過 $2 \times 10^5$。

輸出格式

對於每組測試資料，輸出一行，包含 $q$ 個整數，其中第 $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