Given $n$ vertical lines, where the $i$-th line is $x = a_i$, and also $m$ horizontal lines, where the $i$-th line is $y = b_i$, it costs $t_i$ units of time to move $1$ unit of distance along the $i$-th vertical line, and it costs $t_0$ units of time to move $1$ unit of distance along any horizontal line.

Let $f(i, j)$ be the minimum time needed to get from $(0, 0)$ to $(a_i, b_j)$ by moving only along the vertical and horizontal lines. You need to answer $q$ queries, where each query is represented as four integers $l, r, d, u$, and you need to calculate

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

Since the answers may be large, output them modulo $998\,244\,353$.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^4$), indicating the number of test cases. For each test case:

The first line contains three integers $n, m, q$ ($1 \le n, m, q \le 2 \times 10^5$), indicating the numbers of vertical lines, horizontal lines, and queries.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 = a_1 < a_2 < \dots < a_n \le 10^9$), indicating the $x$-coordinates of the vertical lines.

The third line contains $m$ integers $b_1, b_2, \dots, b_m$ ($0 = b_1 < b_2 < \dots < b_m \le 10^9$), indicating the $y$-coordinates of the horizontal lines.

The fourth line contains $n$ integers $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 10^9$), where $t_i$ indicates the time needed to move $1$ unit of distance along the $i$-th vertical line.

The fifth line contains one integer $t_0$ ($1 \le t_0 \le 10^9$), indicating the time needed to move $1$ unit of distance along any horizontal line.

For the following $q$ lines, the $i$-th line contains four integers $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$), indicating the $i$-th query.

It is guaranteed that the sum of $n$, the sum of $m$, and the sum of $q$ over all test cases do not exceed $2 \times 10^5$.

Output

For each test case, output one line containing $q$ integers, where the $i$-th integer is the answer to the $i$-th query modulo $998\,244\,353$.

Example

Sample Input 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

Sample Output 1

43 21 0