Gefnar eru $n$ lóðréttar línur, þar sem $i$-ta línan er $x = a_i$, og einnig $m$ láréttar línur, þar sem $i$-ta línan er $y = b_i$. Það kostar $t_i$ tímaeiningar að færast um $1$ lengdareiningu eftir $i$-tu lóðréttu línunni, og það kostar $t_0$ tímaeiningar að færast um $1$ lengdareiningu eftir hvaða láréttu línu sem er.

Látum $f(i, j)$ vera lágmarkstímann sem þarf til að komast frá $(0, 0)$ til $(a_i, b_j)$ með því að ferðast eingöngu eftir lóðréttu og láréttu línunum. Þú þarft að svara $q$ fyrirspurnum, þar sem hver fyrirspurn er táknuð með fjórum heiltölum $l, r, d, u$, og þú þarft að reikna

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

Þar sem svörin geta verið stór skaltu prenta þau modulo $998\,244\,353$.

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur heiltölu $T$ ($1 \le T \le 10^4$), sem gefur til kynna fjölda prófunartilvika. Fyrir hvert prófunartilvik:

Fyrsta línan inniheldur þrjár heiltölur $n, m, q$ ($1 \le n, m, q \le 2 \times 10^5$), sem gefa til kynna fjölda lóðréttra lína, láréttra lína og fyrirspurna.

Önnur línan inniheldur $n$ heiltölur $a_1, a_2, \dots, a_n$ ($0 = a_1 < a_2 < \dots < a_n \le 10^9$), sem gefa til kynna $x$-hnit lóðréttu línanna.

Þriðja línan inniheldur $m$ heiltölur $b_1, b_2, \dots, b_m$ ($0 = b_1 < b_2 < \dots < b_m \le 10^9$), sem gefa til kynna $y$-hnit láréttu línanna.

Fjórða línan inniheldur $n$ heiltölur $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 10^9$), þar sem $t_i$ gefur til kynna tímann sem þarf til að færast um $1$ lengdareiningu eftir $i$-tu lóðréttu línunni.

Fimmta línan inniheldur eina heiltölu $t_0$ ($1 \le t_0 \le 10^9$), sem gefur til kynna tímann sem þarf til að færast um $1$ lengdareiningu eftir hvaða láréttu línu sem er.

Í næstu $q$ línum inniheldur $i$-ta línan fjórar heiltölur $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$), sem gefa til kynna $i$-tu fyrirspurnina.

Það er tryggt að summa $n$, summa $m$ og summa $q$ yfir öll prófunartilvik fari ekki yfir $2 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur $q$ heiltölur, þar sem $i$-ta heiltalan er svarið við $i$-tu fyrirspurninni modulo $998\,244\,353$.

Dæmi

Dæmi um inntak 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

Dæmi um úttak 1

43 21 0