Givet $n$ vertikala linjer, där den $i$:te linjen är $x = a_i$, samt $m$ horisontella linjer, där den $i$:te linjen är $y = b_i$, kostar det $t_i$ tidsenheter att förflytta sig $1$ längdenhet längs den $i$:te vertikala linjen, och det kostar $t_0$ tidsenheter att förflytta sig $1$ längdenhet längs vilken horisontell linje som helst.

Låt $f(i, j)$ vara den minsta tid som krävs för att ta sig från $(0, 0)$ till $(a_i, b_j)$ genom att endast röra sig längs de vertikala och horisontella linjerna. Du ska besvara $q$ frågor, där varje fråga representeras av fyra heltal $l, r, d, u$, och du ska beräkna

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

Eftersom svaren kan vara stora, skriv ut dem modulo $998\,244\,353$.

Indata

Det finns flera testfall. Den första raden i indata innehåller ett heltal $T$ ($1 \le T \le 10^4$), som anger antalet testfall. För varje testfall:

Den första raden innehåller tre heltal $n, m, q$ ($1 \le n, m, q \le 2 \times 10^5$), som anger antalet vertikala linjer, horisontella linjer och frågor.

Den andra raden innehåller $n$ heltal $a_1, a_2, \dots, a_n$ ($0 = a_1 < a_2 < \dots < a_n \le 10^9$), som anger de vertikala linjernas $x$-koordinater.

Den tredje raden innehåller $m$ heltal $b_1, b_2, \dots, b_m$ ($0 = b_1 < b_2 < \dots < b_m \le 10^9$), som anger de horisontella linjernas $y$-koordinater.

Den fjärde raden innehåller $n$ heltal $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 10^9$), där $t_i$ anger tiden som krävs för att förflytta sig $1$ längdenhet längs den $i$:te vertikala linjen.

Den femte raden innehåller ett heltal $t_0$ ($1 \le t_0 \le 10^9$), som anger tiden som krävs för att förflytta sig $1$ längdenhet längs vilken horisontell linje som helst.

För de följande $q$ raderna innehåller den $i$:te raden fyra heltal $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 anger den $i$:te frågan.

Det garanteras att summan av $n$, summan av $m$ och summan av $q$ över alla testfall inte överstiger $2 \times 10^5$.

Utdata

För varje testfall, skriv ut en rad som innehåller $q$ heltal, där det $i$:te heltalet är svaret på den $i$:te frågan modulo $998\,244\,353$.

Exempel

Exempelindata 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

Exempelutdata 1

43 21 0