P3962 [TJOI2013] Digital Root

The digital root of a number is defined as repeatedly summing its digits until the result is less than 10. For example, the digital root of 64357 is 7, because $6 + 4 + 3 + 5 + 7 = 25$, and $2 + 5 = 7$. The digital root of an interval is defined as the digital root of the sum of all numbers in that interval. Given a sequence $A_1, A_2, A_3, \ldots, A_n$, you need to answer several queries. For each query, you are given an interval $[l, r]$. Among all contiguous subintervals within $[l, r]$, find the top 5 distinct digital roots. If there are fewer than 5, fill the remaining positions with $-1$.

- The first line contains an integer $N$, the length of the sequence. - The second line contains $N$ integers $A_i$ ($0 \le A_i < 10^9$). - The third line contains an integer $Q$, the number of queries. - Each of the next $Q$ lines contains two integers $l, r$ ($1 \le l \le r \le N$), denoting a query interval.

Output $Q$ lines. For each query interval, output the top 5 distinct digital roots of all its contiguous subintervals in descending order, space-separated. If there are fewer than 5, pad with $-1$.

### Sample Explanation For the first query interval $[1, 3]$, its contiguous subintervals are $[1, 1]$, $[2, 2]$, $[3, 3]$, $[1, 2]$, $[2, 3]$, $[1, 3]$. Their corresponding digital roots are $2, 6, 7, 8, 4, 6$. Therefore, the top 5 are $8, 7, 6, 4, 2$. ### Constraints - 30% of the testdata: $N \le 1000$, $Q \le 1000$. - 100% of the testdata: $N \le 100000$, $Q \le 100000$. Translated by ChatGPT 5