Danych jest $n$ prostych pionowych, gdzie $i$-ta prosta to $x = a_i$, oraz $m$ prostych poziomych, gdzie $i$-ta prosta to $y = b_i$. Przemieszczenie się o $1$ jednostkę odległości wzdłuż $i$-tej prostej pionowej kosztuje $t_i$ jednostek czasu, a przemieszczenie się o $1$ jednostkę odległości wzdłuż dowolnej prostej poziomej kosztuje $t_0$ jednostek czasu.

Niech $f(i, j)$ oznacza minimalny czas potrzebny na dotarcie z $(0, 0)$ do $(a_i, b_j)$ poruszając się wyłącznie wzdłuż prostych pionowych i poziomych. Musisz odpowiedzieć na $q$ zapytań, gdzie każde zapytanie jest reprezentowane przez cztery liczby całkowite $l, r, d, u$, i musisz obliczyć

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

Ponieważ odpowiedzi mogą być duże, wypisz je modulo $998\,244\,353$.

Wejście

Wejście składa się z wielu przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^4$), oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego:

Pierwszy wiersz zawiera trzy liczby całkowite $n, m, q$ ($1 \le n, m, q \le 2 \times 10^5$), oznaczające odpowiednio liczbę prostych pionowych, prostych poziomych oraz zapytań.

Drugi wiersz zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($0 = a_1 < a_2 < \dots < a_n \le 10^9$), oznaczających współrzędne $x$ prostych pionowych.

Trzeci wiersz zawiera $m$ liczb całkowitych $b_1, b_2, \dots, b_m$ ($0 = b_1 < b_2 < \dots < b_m \le 10^9$), oznaczających współrzędne $y$ prostych poziomych.

Czwarty wiersz zawiera $n$ liczb całkowitych $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 10^9$), gdzie $t_i$ oznacza czas potrzebny na przemieszczenie się o $1$ jednostkę odległości wzdłuż $i$-tej prostej pionowej.

Piąty wiersz zawiera jedną liczbę całkowitą $t_0$ ($1 \le t_0 \le 10^9$), oznaczającą czas potrzebny na przemieszczenie się o $1$ jednostkę odległości wzdłuż dowolnej prostej poziomej.

W kolejnych $q$ wierszach, $i$-ty wiersz zawiera cztery liczby całkowite $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$), oznaczające $i$-te zapytanie.

Gwarantowane jest, że suma $n$, suma $m$ oraz suma $q$ po wszystkich przypadkach testowych nie przekraczają $2 \times 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający $q$ liczb całkowitych, gdzie $i$-ta liczba całkowita jest odpowiedzią na $i$-te zapytanie modulo $998\,244\,353$.

Przykład

Przykładowe wejście 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

Przykładowe wyjście 1

43 21 0