On vous donne $n$ droites verticales, où la $i$-ème droite est $x = a_i$, ainsi que $m$ droites horizontales, où la $i$-ème droite est $y = b_i$. Il faut $t_i$ unités de temps pour parcourir $1$ unité de distance le long de la $i$-ème droite verticale, et il faut $t_0$ unités de temps pour parcourir $1$ unité de distance le long de n'importe quelle droite horizontale.

Soit $f(i, j)$ le temps minimum nécessaire pour aller de $(0, 0)$ à $(a_i, b_j)$ en se déplaçant uniquement le long des droites verticales et horizontales. Vous devez répondre à $q$ requêtes, où chaque requête est représentée par quatre entiers $l, r, d, u$, et vous devez calculer

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

Comme les réponses peuvent être grandes, affichez-les modulo $998\,244\,353$.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 10^4$), indiquant le nombre de cas de test. Pour chaque cas de test :

La première ligne contient trois entiers $n, m, q$ ($1 \le n, m, q \le 2 \times 10^5$), indiquant les nombres de droites verticales, de droites horizontales et de requêtes.

La deuxième ligne contient $n$ entiers $a_1, a_2, \dots, a_n$ ($0 = a_1 < a_2 < \dots < a_n \le 10^9$), indiquant les coordonnées $x$ des droites verticales.

La troisième ligne contient $m$ entiers $b_1, b_2, \dots, b_m$ ($0 = b_1 < b_2 < \dots < b_m \le 10^9$), indiquant les coordonnées $y$ des droites horizontales.

La quatrième ligne contient $n$ entiers $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 10^9$), où $t_i$ indique le temps nécessaire pour parcourir $1$ unité de distance le long de la $i$-ème droite verticale.

La cinquième ligne contient un entier $t_0$ ($1 \le t_0 \le 10^9$), indiquant le temps nécessaire pour parcourir $1$ unité de distance le long de n'importe quelle droite horizontale.

Pour les $q$ lignes suivantes, la $i$-ème ligne contient quatre entiers $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$), indiquant la $i$-ème requête.

Il est garanti que la somme des $n$, la somme des $m$ et la somme des $q$ sur tous les cas de test ne dépassent pas $2 \times 10^5$.

Sortie

Pour chaque cas de test, affichez une ligne contenant $q$ entiers, où le $i$-ème entier est la réponse à la $i$-ème requête modulo $998\,244\,353$.

Exemple

Exemple d'entrée 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

Exemple de sortie 1

43 21 0