Annetaan $n$ pystysuoraa suoraa, missä $i$:s suora on $x = a_i$, sekä $m$ vaakasuoraa suoraa, missä $i$:s suora on $y = b_i$. Liikkuminen $1$ pituusyksikön verran $i$:ttä pystysuoraa suoraa pitkin vie $t_i$ aikayksikköä, ja liikkuminen $1$ pituusyksikön verran mitä tahansa vaakasuoraa suoraa pitkin vie $t_0$ aikayksikköä.

Olkoon $f(i, j)$ pienin tarvittava aika päästä pisteestä $(0, 0)$ pisteeseen $(a_i, b_j)$ liikkumalla vain pystysuoria ja vaakasuoria suoria pitkin. Sinun tulee vastata $q$ kyselyyn, missä jokainen kysely esitetään neljänä kokonaislukuna $l, r, d, u$, ja sinun tulee laskea

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

Koska vastaukset voivat olla suuria, tulosta ne modulo $998\,244\,353$.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^4$), joka ilmaisee testitapausten lukumäärän. Jokaiselle testitapaukselle:

Ensimmäinen rivi sisältää kolme kokonaislukua $n, m, q$ ($1 \le n, m, q \le 2 \times 10^5$), jotka ilmaisevat pystysuorien suorien, vaakasuorien suorien ja kyselyiden lukumäärät.

Toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \dots, a_n$ ($0 = a_1 < a_2 < \dots < a_n \le 10^9$), jotka ilmaisevat pystysuorien suorien $x$-koordinaatit.

Kolmas rivi sisältää $m$ kokonaislukua $b_1, b_2, \dots, b_m$ ($0 = b_1 < b_2 < \dots < b_m \le 10^9$), jotka ilmaisevat vaakasuorien suorien $y$-koordinaatit.

Neljäs rivi sisältää $n$ kokonaislukua $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 10^9$), missä $t_i$ ilmaisee ajan, joka tarvitaan $1$ pituusyksikön liikkumiseen $i$:ttä pystysuoraa suoraa pitkin.

Viides rivi sisältää yhden kokonaisluvun $t_0$ ($1 \le t_0 \le 10^9$), joka ilmaisee ajan, joka tarvitaan $1$ pituusyksikön liikkumiseen mitä tahansa vaakasuoraa suoraa pitkin.

Seuraavilla $q$ rivillä $i$:s rivi sisältää neljä kokonaislukua $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$), jotka ilmaisevat $i$:nnen kyselyn.

On taattu, että lukujen $n$ summa, lukujen $m$ summa ja lukujen $q$ summa yli kaikkien testitapausten eivät ylitä arvoa $2 \times 10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi rivi, joka sisältää $q$ kokonaislukua, missä $i$:s kokonaisluku on vastaus $i$:nteen kyselyyn modulo $998\,244\,353$.

Esimerkki

Esimerkkisyöte 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

Esimerkkituloste 1

43 21 0