Digital root

The digital root (also repeated digital sum) of a number is the (single digit) value obtained by an iterative process of summing digits, on each iteration using the result from the previous iteration to compute a digit sum. The process continues until a single-digit number is reached.
For example, the digital root of 65536 is 7, because 6+5+5+3+6=25 and 2+5=7.
The digital root of an interval is digital root of the sum of all numbers in that interval.

Consider a sequence A₁,A₂,A₃……A_n, your task is to answer some queries[l,r]. For each query, tell the biggest five different digital roots among all continuous subintervals of interval[l,r]

In the first line of the input , we have one integer T indicating the number of test cases. (1 <= T <= 10) Then T cases follows. For each test case, the first line is an integer n indicating the length of sequence(1<=n<=100000); following one line containing n integer A_i(0<=A_i<=1000000000); the third line is an integer Q indicating the number of queries(1<=Q<=100000); following Q lines, each line indicating one query [l,r],(1<=l<=r<=n).

For each test case, first you should print "Case #x:" in a line, where x stands for the case number started with 1. Then for each query output a line contains five integer indicating the answers(if the kind of digital root is smaller than five, output -1 to complete). Leave an empty line between test cases.

1
5
101 240 331 4 52
3
1 3
4 5
1 5

Case #1:
8 7 6 4 2
7 4 2 -1 -1
9 8 7 6 4

For the first query, [1,3] has six subintervals: [1,1],[2,2],[3,3],[1,2],[2,3],[1,3]. Interval sums are 101,240,331,341,571,672, correspondence digital roots are 2,6,7
,8,4,6,the most biggest five are 8,7,6,4,2

L7we@UESTC_Alchemist

2012 Multi-University Training Contest 6