Cho $n$ đường thẳng đứng, trong đó đường thẳng thứ $i$ là $x = a_i$, và $m$ đường nằm ngang, trong đó đường thẳng thứ $i$ là $y = b_i$. Cần $t_i$ đơn vị thời gian để di chuyển $1$ đơn vị khoảng cách dọc theo đường thẳng đứng thứ $i$, và cần $t_0$ đơn vị thời gian để di chuyển $1$ đơn vị khoảng cách dọc theo bất kỳ đường nằm ngang nào.

Gọi $f(i, j)$ là thời gian tối thiểu cần thiết để đi từ $(0, 0)$ đến $(a_i, b_j)$ bằng cách chỉ di chuyển dọc theo các đường thẳng đứng và đường nằm ngang. Bạn cần trả lời $q$ truy vấn, mỗi truy vấn được biểu diễn bởi bốn số nguyên $l, r, d, u$, và bạn cần tính:

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

Vì đáp án có thể rất lớn, hãy in ra kết quả theo modulo $998\,244\,353$.

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1 \le T \le 10^4$), cho biết số lượng bộ dữ liệu. Với mỗi bộ dữ liệu:

Dòng đầu tiên chứa ba số nguyên $n, m, q$ ($1 \le n, m, q \le 2 \times 10^5$), cho biết số lượng đường thẳng đứng, đường nằm ngang và số truy vấn.

Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($0 = a_1 < a_2 < \dots < a_n \le 10^9$), cho biết tọa độ $x$ của các đường thẳng đứng.

Dòng thứ ba chứa $m$ số nguyên $b_1, b_2, \dots, b_m$ ($0 = b_1 < b_2 < \dots < b_m \le 10^9$), cho biết tọa độ $y$ của các đường nằm ngang.

Dòng thứ tư chứa $n$ số nguyên $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 10^9$), trong đó $t_i$ cho biết thời gian cần thiết để di chuyển $1$ đơn vị khoảng cách dọc theo đường thẳng đứng thứ $i$.

Dòng thứ năm chứa một số nguyên $t_0$ ($1 \le t_0 \le 10^9$), cho biết thời gian cần thiết để di chuyển $1$ đơn vị khoảng cách dọc theo bất kỳ đường nằm ngang nào.

Trong $q$ dòng tiếp theo, dòng thứ $i$ chứa bốn số nguyên $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$), biểu thị truy vấn thứ $i$.

Đảm bảo rằng tổng của $n$, tổng của $m$ và tổng của $q$ trên tất cả các bộ dữ liệu không vượt quá $2 \times 10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa $q$ số nguyên, trong đó số nguyên thứ $i$ là đáp án cho truy vấn thứ $i$ theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

43 21 0