1697 - A billionaire

Time Limit: 3s Memory Limit: 128MB

Submissions: 59 Solved: 15


    Fan Hao is the richest person in Team Nebula or even the whole ACM group. Since he spend a lot and cannot memorize the specific number of expense, Fan Hao uses a notebook to write down his cost every hour. To simplify the calculation, we assume every record of expense will not exceed 100. Now Fan Hao wants to know his total expenses from time a to time b, and your task is to write a naive program to calculate it.




    The first line contains a single integer T, referring to the number of test cases.

   Each test case consists of several lines. The first line consists of 2 integers n,q (1<=n,q<=100000)

   Next to it is a line with n integers a(1),a(2),……a(n) (0<=a(i)<=100) – the record of expense in time i.

    Then q lines follows, in the j-th of which there are two integers r,s (1<=r<=s<=n) – you need to calculate the sum from time ai to time bi and output it.




   For each query, first output”Case #i:”where ‘I’ is the number of this case. Then, output the answer separated by a space, e.g. the sum from a(r) to a(s) including both a(r) and a(s).



Sample Input
4 2
1 2 3 4
1 3
2 4
5 3
1 2 3 5 8
3 5
2 3
1 4

Sample Output
Case #1:
6 9
Case #2:
16 5 11


Huge amount of input. Using scanf instead of std::cin to get faster IO.