Description

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$.

Input Format

• 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 Format

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$.

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

8 7 6 4 2
7 4 2 -1 -1
9 8 7 6 4

Hint

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