Dadas $n$ líneas verticales, donde la $i$-ésima línea es $x = a_i$, y también $m$ líneas horizontales, donde la $i$-ésima línea es $y = b_i$, cuesta $t_i$ unidades de tiempo moverse $1$ unidad de distancia a lo largo de la $i$-ésima línea vertical, y cuesta $t_0$ unidades de tiempo moverse $1$ unidad de distancia a lo largo de cualquier línea horizontal.

Sea $f(i, j)$ el tiempo mínimo necesario para ir de $(0, 0)$ a $(a_i, b_j)$ moviéndose únicamente a lo largo de las líneas verticales y horizontales. Debes responder $q$ consultas, donde cada consulta se representa mediante cuatro enteros $l, r, d, u$, y debes calcular

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

Como las respuestas pueden ser grandes, imprímelas módulo $998\,244\,353$.

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 10^4$), que indica el número de casos de prueba. Para cada caso de prueba:

La primera línea contiene tres enteros $n, m, q$ ($1 \le n, m, q \le 2 \times 10^5$), que indican las cantidades de líneas verticales, líneas horizontales y consultas.

La segunda línea contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($0 = a_1 < a_2 < \dots < a_n \le 10^9$), que indican las coordenadas $x$ de las líneas verticales.

La tercera línea contiene $m$ enteros $b_1, b_2, \dots, b_m$ ($0 = b_1 < b_2 < \dots < b_m \le 10^9$), que indican las coordenadas $y$ de las líneas horizontales.

La cuarta línea contiene $n$ enteros $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 10^9$), donde $t_i$ indica el tiempo necesario para moverse $1$ unidad de distancia a lo largo de la $i$-ésima línea vertical.

La quinta línea contiene un entero $t_0$ ($1 \le t_0 \le 10^9$), que indica el tiempo necesario para moverse $1$ unidad de distancia a lo largo de cualquier línea horizontal.

En las siguientes $q$ líneas, la $i$-ésima línea contiene cuatro enteros $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$), que indican la $i$-ésima consulta.

Se garantiza que la suma de $n$, la suma de $m$ y la suma de $q$ en todos los casos de prueba no superan $2 \times 10^5$.

Salida

Para cada caso de prueba, imprime una línea con $q$ enteros, donde el $i$-ésimo entero es la respuesta a la $i$-ésima consulta módulo $998\,244\,353$.

Ejemplo

Entrada de ejemplo 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

Salida de ejemplo 1

43 21 0