Alice presented her friend Bob with an array of positive integers, indexed from to . She challenged Bob with many queries of the form "what is the sum of the numbers between these two indexes?" But Bob was able to solve the problem too easily.
Alice took her array and found all non-empty subarrays of it. She found the sum of each subarray, and then sorted those values (in nondecreasing order) to create a new array, indexed from to . For example, for an initial array , Alice would generate the subarrays , and (note that , for example, is NOT a subarray). Then she'd take the sums -- -- and sort them to get a new array of .
Alice has given the initial array to Bob, along with queries of the form "what is the sum of the numbers from index to , inclusive, in the new array?" Now Bob's in trouble! Can you help him out?
输入格式
The first line of the input gives the number of test cases, . test cases follow. Each test case begins with one line with two space-separated integers and , denoting the number of elements in the initial array and the number of Alice's queries. Then, there is one line with space-separated integers, denoting the elements of Alice's initial array. Finally, there are more lines with two space-separated integers each: and , the inclusive index bounds for the i-th query.
输出格式
For each test case, output one line with Case #x:, where is the test case number (starting from ). Then output more lines, each with one integer, representing the answers to the queries (in the order they were asked).
