Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

The Best Gift Ever

By TarifEzaz · Limits 3s, 512 MB

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 AA and BB of size NN and MM respectively. Each array can be considered as a collection of elements and AA and BB 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 ii, jj, kk and ll, where 1ijN1 \le i \le j \le N and 1klM1 \le k \le l \le M and give them an integer number GG as gift in return. Let's call each of these 4-tuple (ii, jj, kk, ll) a query. The integer GG can be calculated in the following manner:

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

Now, given two arrays AA and BB, 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 TT (1T101 \le T \le 10), the number of testcases. Each testcase starts with two integers NN and MM (1N,M1051 \le N, M \le 10^5), the sizes of the two arrays AA and BB respectively. The next line has NN integers AiA^i (1Ai1041 \le A^i \le 10^4), where each integer indicates the ithi^{th} element of the array AA. The following line contains MM integers BjB_j (1Bj1041 \le B_j \le 10^4). Each BjB_j indicates the jthj^{th} element of array BB. The next line contains an integer QQ (1Q1051 \le Q \le 10^5). Each of the next QQ lines contain four integers ii , jj , kk and ll.

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 GG on a line by itself. Please see the sample cases for exact formatting.

Sample

InputOutput
1
2 3
1 2
1 2 3
1
1 2 1 3
Case 1:
18

Discussion

Statistics


73% Solution Ratio

NAbdullaEarliest, Dec '16

MR.Jukerburg11Fastest, 0.2s

Shipon_diuLightest, 18 MB

mdvirusShortest, 453B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.