Date $n$ rette verticali, dove la $i$-esima retta è $x = a_i$, e anche $m$ rette orizzontali, dove la $i$-esima retta è $y = b_i$, costa $t_i$ unità di tempo muoversi di $1$ unità di distanza lungo la $i$-esima retta verticale, e costa $t_0$ unità di tempo muoversi di $1$ unità di distanza lungo qualsiasi retta orizzontale.

Sia $f(i, j)$ il tempo minimo necessario per andare da $(0, 0)$ a $(a_i, b_j)$ muovendosi solo lungo le rette verticali e orizzontali. Devi rispondere a $q$ query, dove ciascuna query è rappresentata da quattro interi $l, r, d, u$, e devi calcolare

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

Poiché le risposte possono essere grandi, stampale modulo $998\,244\,353$.

Input

Ci sono più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 10^4$), che indica il numero di casi di test. Per ciascun caso di test:

La prima riga contiene tre interi $n, m, q$ ($1 \le n, m, q \le 2 \times 10^5$), che indicano il numero di rette verticali, rette orizzontali e query.

La seconda riga contiene $n$ interi $a_1, a_2, \dots, a_n$ ($0 = a_1 < a_2 < \dots < a_n \le 10^9$), che indicano le coordinate $x$ delle rette verticali.

La terza riga contiene $m$ interi $b_1, b_2, \dots, b_m$ ($0 = b_1 < b_2 < \dots < b_m \le 10^9$), che indicano le coordinate $y$ delle rette orizzontali.

La quarta riga contiene $n$ interi $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 10^9$), dove $t_i$ indica il tempo necessario per muoversi di $1$ unità di distanza lungo la $i$-esima retta verticale.

La quinta riga contiene un intero $t_0$ ($1 \le t_0 \le 10^9$), che indica il tempo necessario per muoversi di $1$ unità di distanza lungo qualsiasi retta orizzontale.

Per le successive $q$ righe, la $i$-esima riga contiene quattro interi $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$), che indicano la $i$-esima query.

È garantito che la somma di $n$, la somma di $m$ e la somma di $q$ su tutti i casi di test non superano $2 \times 10^5$.

Output

Per ciascun caso di test, stampa una riga contenente $q$ interi, dove l'$i$-esimo intero è la risposta alla $i$-esima query modulo $998\,244\,353$.

Esempio

Input di esempio 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

Output di esempio 1

43 21 0