Gitt $n$ vertikale linjer, der den $i$-te linjen er $x = a_i$, og også $m$ horisontale linjer, der den $i$-te linjen er $y = b_i$. Det koster $t_i$ tidsenheter å bevege seg $1$ lengdeenhet langs den $i$-te vertikale linjen, og det koster $t_0$ tidsenheter å bevege seg $1$ lengdeenhet langs en hvilken som helst horisontal linje.

La $f(i, j)$ være den minimale tiden som trengs for å komme seg fra $(0, 0)$ til $(a_i, b_j)$ ved å bevege seg kun langs de vertikale og horisontale linjene. Du må svare på $q$ spørringer, der hver spørring er representert som fire heltall $l, r, d, u$, og du må beregne

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

Siden svarene kan være store, skriv dem ut modulo $998\,244\,353$.

Inndata

Det er flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 10^4$), som angir antallet testtilfeller. For hvert testtilfelle:

Den første linjen inneholder tre heltall $n, m, q$ ($1 \le n, m, q \le 2 \times 10^5$), som angir antallet vertikale linjer, horisontale linjer og spørringer.

Den andre linjen inneholder $n$ heltall $a_1, a_2, \dots, a_n$ ($0 = a_1 < a_2 < \dots < a_n \le 10^9$), som angir $x$-koordinatene til de vertikale linjene.

Den tredje linjen inneholder $m$ heltall $b_1, b_2, \dots, b_m$ ($0 = b_1 < b_2 < \dots < b_m \le 10^9$), som angir $y$-koordinatene til de horisontale linjene.

Den fjerde linjen inneholder $n$ heltall $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 10^9$), der $t_i$ angir tiden som trengs for å bevege seg $1$ lengdeenhet langs den $i$-te vertikale linjen.

Den femte linjen inneholder ett heltall $t_0$ ($1 \le t_0 \le 10^9$), som angir tiden som trengs for å bevege seg $1$ lengdeenhet langs en hvilken som helst horisontal linje.

For de følgende $q$ linjene inneholder den $i$-te linjen fire heltall $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$), som angir den $i$-te spørringen.

Det er garantert at summen av $n$, summen av $m$ og summen av $q$ over alle testtilfeller ikke overstiger $2 \times 10^5$.

Utdata

For hvert testtilfelle, skriv ut én linje som inneholder $q$ heltall, der det $i$-te heltallet er svaret på den $i$-te spørringen modulo $998\,244\,353$.

Eksempel

Eksempelinndata 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

Eksempelutdata 1

43 21 0