Дано $n$ вертикальних прямих, де $i$-та пряма задається рівнянням $x = a_i$, а також $m$ горизонтальних прямих, де $i$-та пряма задається рівнянням $y = b_i$. Переміщення на $1$ одиницю відстані вздовж $i$-ї вертикальної прямої займає $t_i$ одиниць часу, а переміщення на $1$ одиницю відстані вздовж будь-якої горизонтальної прямої займає $t_0$ одиниць часу.

Нехай $f(i, j)$ — мінімальний час, необхідний для того, щоб дістатися з $(0, 0)$ до $(a_i, b_j)$, рухаючись лише вздовж вертикальних і горизонтальних прямих. Вам потрібно відповісти на $q$ запитів, де кожен запит задається чотирма цілими числами $l, r, d, u$, і потрібно обчислити

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

Оскільки відповіді можуть бути великими, виведіть їх за модулем $998\,244\,353$.

Вхідні дані

Вхідні дані містять декілька наборів тестових даних. Перший рядок містить ціле число $T$ ($1 \le T \le 10^4$), що позначає кількість наборів тестових даних. Для кожного набору тестових даних:

Перший рядок містить три цілі числа $n, m, q$ ($1 \le n, m, q \le 2 \times 10^5$), що позначають кількість вертикальних прямих, горизонтальних прямих та запитів.

Другий рядок містить $n$ цілих чисел $a_1, a_2, \dots, a_n$ ($0 = a_1 < a_2 < \dots < a_n \le 10^9$), що позначають $x$-координати вертикальних прямих.

Третій рядок містить $m$ цілих чисел $b_1, b_2, \dots, b_m$ ($0 = b_1 < b_2 < \dots < b_m \le 10^9$), що позначають $y$-координати горизонтальних прямих.

Четвертий рядок містить $n$ цілих чисел $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 10^9$), де $t_i$ позначає час, необхідний для переміщення на $1$ одиницю відстані вздовж $i$-ї вертикальної прямої.

П'ятий рядок містить одне ціле число $t_0$ ($1 \le t_0 \le 10^9$), що позначає час, необхідний для переміщення на $1$ одиницю відстані вздовж будь-якої горизонтальної прямої.

У наступних $q$ рядках $i$-й рядок містить чотири цілі числа $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$), що позначають $i$-й запит.

Гарантується, що сума $n$, сума $m$ та сума $q$ за всіма наборами тестових даних не перевищують $2 \times 10^5$.

Вихідні дані

Для кожного набору тестових даних виведіть один рядок, що містить $q$ цілих чисел, де $i$-те ціле число — відповідь на $i$-й запит за модулем $998\,244\,353$.

Приклад

Приклад вводу 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

Приклад виводу 1

43 21 0