TWOSUMQUERY - Two Sum Query

You will be given an array A of size N and also given Q queries. In each query you will be given a number K. You have to print two number S1 and S2. Where S1 is the sum of all the elements that are strictly less than K, and S2 is the sum of all the elements that are strictly greater than K.

Input

Input starts with an integer T (1 <= T <= 20), denoting the number of test cases. Each test case starts with two integers N (1 <= N <= 105) and Q (1 <= Q <= 105). N denotes the number of elements in the array and Q is the number of queries. The next line contain N integers A0, A1, A2, ..., AN-1 (0 <= Ai <= 109). Then the next line contains Q integers K (0 <= K <= 109). For each K you have to print S1and S2.

Output

For each test case print "Case X:" (without quotes) where X is the running test case number. Then next Q lines consist of S1 and S2 for every given K in the current test case. Where S1 is the sum of all the elements that are strictly less than K, and S2 is the sum of all the elements that are strictly greater than K.

Sample

Input
2
10 5
5 1 0 8 1 13 34 21 3 2
1 2 3 4 35
7 2
6 24 120 1 720 2 1
1 23

Output
Case 1:
0 86
2 84
4 81
7 81
88 0
Case 2:
0 872
10 864

Added by:Nesar
Date:2019-10-02
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C-CLANG C NCSHARP CSHARP C++ 4.3.2 CPP CPP14 JAVA JULIA PYTHON PYPY PYPY3 PYTHON3
Resource:Fresh problem

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.