SHTANU - Tanushera And His Car

no tags 

Tanusera is a famous programmer. Recently he has bought a new car. He loves to play with problems, you know. So, he has decided to make a new problem. He has developed a software & installed it in his car. This software measures the distance passed by the car from time 1 to time N and shows the distance passed by it in every second. You'll be given the data which the software represents. After that Tanusera will ask you Q queries. In each query, he will give you time t1 and time t2. You have to calculate the distance passed by his car from t1 to t2.

Input

Input starts with an integer T, denoting the number of test cases. In each case, there will be two integers N and Q where N denotes the amount of times the software has been performed and Q denotes the number of queries. The next line will contain N integers, ith integer is the distance passed by the car in ith time. Then there will be Q lines. In each line, there will be two integers t1 and t2.

 

Constraints

1 <= T <= 3 
1 <= N <= 1000000 
0 <= i
th integer <= 1000000 
1 <= Q <= 1000000 
1 <= t1 <= t2 <= N 

Output

For each case, print the case number and the distance passed by the car from time t1 to time t2 for every query in single line. See the samples for further clarification.

Example

Input:
3
3 5 4 0 0 5 9 2 1 2 1 1 3 5 5 5 3 3 2 0 8 2 3 1 3 2 2 1 1 5 1 1 Output: Case 1: 0 0 16 2 Case 2: 8 10 0 Case 3: 5

[ Original setter of this problem is Risal Shahriar Shefin, RUET ]


hide comments
nadstratosfer: 2018-06-09 22:35:55

I don't understand the motivation to lobby for demoting the problem to tutorial. The way SPOJ is currently organized, it's a cemetery of problems; barely anyone ever looks at these. Sometimes it just hurts when I dig up extremely useful and fun problem there that has like 20 solvers in 10 years. On the other hand, easy classicals get a lot of solvers and noone will fasttrack his rank through such problems in a long term. This problem is based on an important concept and is decently set allowing some experiments also in slower languages. Doesn't deserve to be shitcanned at least until the hierarchy/scoring system is updated IMHO.

Jitesh: 2018-06-09 10:22:41

Move it to tutorial, please.


Added by:Avik Sarkar
Date:2018-05-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:RUET Beginner Battle -1