Gegeben sind $n$ vertikale Geraden, wobei die $i$-te Gerade $x = a_i$ ist, sowie $m$ horizontale Geraden, wobei die $i$-te Gerade $y = b_i$ ist. Es kostet $t_i$ Zeiteinheiten, sich um $1$ Längeneinheit entlang der $i$-ten vertikalen Gerade zu bewegen, und es kostet $t_0$ Zeiteinheiten, sich um $1$ Längeneinheit entlang einer beliebigen horizontalen Gerade zu bewegen.

Sei $f(i, j)$ die minimale Zeit, die benötigt wird, um von $(0, 0)$ nach $(a_i, b_j)$ zu gelangen, indem man sich nur entlang der vertikalen und horizontalen Geraden bewegt. Sie müssen $q$ Anfragen beantworten, wobei jede Anfrage durch vier ganze Zahlen $l, r, d, u$ dargestellt wird, und Sie müssen Folgendes berechnen:

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

Da die Antworten groß sein können, geben Sie diese modulo $998\,244\,353$ aus.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 10^4$), die die Anzahl der Testfälle angibt. Für jeden Testfall gilt:

Die erste Zeile enthält drei ganze Zahlen $n, m, q$ ($1 \le n, m, q \le 2 \times 10^5$), die die Anzahl der vertikalen Geraden, der horizontalen Geraden und der Anfragen angeben.

Die zweite Zeile enthält $n$ ganze Zahlen $a_1, a_2, \dots, a_n$ ($0 = a_1 < a_2 < \dots < a_n \le 10^9$), die die $x$-Koordinaten der vertikalen Geraden angeben.

Die dritte Zeile enthält $m$ ganze Zahlen $b_1, b_2, \dots, b_m$ ($0 = b_1 < b_2 < \dots < b_m \le 10^9$), die die $y$-Koordinaten der horizontalen Geraden angeben.

Die vierte Zeile enthält $n$ ganze Zahlen $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 10^9$), wobei $t_i$ die Zeit angibt, die benötigt wird, um sich um $1$ Längeneinheit entlang der $i$-ten vertikalen Gerade zu bewegen.

Die fünfte Zeile enthält eine ganze Zahl $t_0$ ($1 \le t_0 \le 10^9$), die die Zeit angibt, die benötigt wird, um sich um $1$ Längeneinheit entlang einer beliebigen horizontalen Gerade zu bewegen.

In den folgenden $q$ Zeilen enthält die $i$-te Zeile vier ganze Zahlen $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$), die die $i$-te Anfrage beschreiben.

Es wird garantiert, dass die Summe von $n$, die Summe von $m$ und die Summe von $q$ über alle Testfälle hinweg $2 \times 10^5$ nicht überschreiten.

Ausgabe

Geben Sie für jeden Testfall eine Zeile mit $q$ ganzen Zahlen aus, wobei die $i$-te ganze Zahl die Antwort auf die $i$-te Anfrage modulo $998\,244\,353$ ist.

Beispiel

Beispieleingabe 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

Beispielausgabe 1

43 21 0