給定 $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