The Best Gift Ever

In the world of computing, giving gifts like arrays are completely acceptable. Instead of exchanging cards or flowers, friends here exchange prime numbers with each other. Some even walk in two-dimensional grids, rather than a quick walk in the park. Today, not for the first time, you are going to visit this unusually exceptional world.

As usual, you are greeted in the "world of computing" with two arrays $A$ and $B$ of size $N$ and $M$ respectively. Each array can be considered as a collection of elements and $A$ and $B$ are no exceptions. These two arrays contain integers in them. Delighted by this gift, you have decided to give something back to the inhabitants of this crazy world. But their test of gifts, as you have already figured, is quite extraordinary. They would only accept a gift, if the gift is related to those two given arrays.

Wondering about how a gift can be related with two arrays, you have suddenly come up with this great idea! You will ask each inhabitants 4 integers $i$, $j$, $k$ and $l$, where $1 \le i \le j \le N$ and $1 \le k \le l \le M$ and give them an integer number $G$ as gift in return. Let's call each of these 4-tuple ($i$, $j$, $k$, $l$) a query. The integer $G$ can be calculated in the following manner:

$G = \sum_{x=i}^{j} \sum_{y=k}^{l} A_x * B_y$

Now, given two arrays $A$ and $B$, and a list of queries, you need to figure out what numbers are you going to give to the inhabitants as gifts.

Input

The first line contains an integer $T$ ($1 \le T \le 10$), the number of testcases. Each testcase starts with two integers $N$ and $M$ ($1 \le N, M \le 10^5$), the sizes of the two arrays $A$ and $B$ respectively. The next line has $N$ integers $A^i$ ($1 \le A^i \le 10^4$), where each integer indicates the $i$-th element of the array $A$. The following line contains $M$ integers $B_j$ ($1 \le B_j \le 10^4$). Each $B_j$ indicates the $j$-th element of array $B$. The next line contains an integer $Q$ ($1 \le Q \le 10^5$). Each of the next $Q$ lines contain four integers $i$, $j$, $k$ and $l$.

Output

For each test case, first print the case number on a line by itself. After that, for each query, please print the resulting number $G$ on a line by itself.

Sample

1
2 3
1 2
1 2 3
1
1 2 1 3

Case 1:
18