Даны $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