Digit Root Subarray Query

Given a sequence of integers \(A_1, A_2, \dots, A_n\), the digit root of a number is defined as the process of summing its digits repeatedly until a single-digit number is obtained. For example, the digit root of 64357 is computed as follows:

\(6+4+3+5+7 = 25, \; 2+5 = 7\). Therefore, the digit root of 64357 is 7.

Similarly, define the digit root of an interval as the digit root of the sum of all numbers within that interval.

You are given a sequence \(A_1, A_2, \dots, A_n\) and you need to answer several queries. Each query gives an interval \([L, R]\). For each query, consider every continuous subarray \(A_i, A_{i+1}, \dots, A_j\) where \(L \le i \le j \le R\) and compute its digit root. Then, among all these subarrays, determine the largest 5 distinct digit roots. If there are fewer than 5 distinct digit roots, fill the remaining positions with \(-1\).

Note: All formulas should be formatted in LaTeX.

inputFormat

The first line contains two integers \(n\) and \(q\) \( (1 \leq n, q \leq 10^3)\) representing the number of elements in the sequence and the number of queries.

The second line contains \(n\) integers \(A_1, A_2, \dots, A_n\) separated by spaces.

Each of the next \(q\) lines contains two integers \(L\) and \(R\) \(1 \le L \le R \le n\), representing a query interval.

outputFormat

For each query, output a single line with 5 space‐separated integers representing the largest 5 distinct digit roots (in descending order) among all continuous subarrays in the interval \([L, R]\). If there are less than 5 distinct values, output \(-1\) for the missing positions.

sample

5 2
6 4 3 5 7
1 5
2 4

9 8 7 6 5
8 7 5 4 3