Minimum Operations to Equalize Numbers in Different Bases

Consider a sequence ( A ) of ( n ) non‐negative integers. In a given base ( B ), an operation on a number ( x ) is defined as one of the two following actions:

1. Replace ( x ) with ( \lfloor x/B \rfloor ).
2. Replace ( x ) with ( x \times B + t ), where ( t ) is an arbitrary digit, i.e. ( 0 \le t \le B-1 ).

These operations essentially allow you to modify the base ( B ) representation of ( x ) by either deleting its last digit or appending an arbitrary digit at the end.

You are given ( m ) independent queries. Each query is described by three integers ( l ), ( r ), and ( B ). For the subarray ( A[l \ldots r] ), determine the minimum total number of operations required to make all the numbers equal if in each operation you can modify exactly one number.

A key observation is that the minimum number of operations needed to convert a number ( x ) to a number ( y ) is determined by their base ( B ) representations. Let ( |\mathit{rep}_B(x)| ) denote the length of the base ( B ) representation of ( x ) (note that the representation of 0 is ( \texttt{"0"} )) and let ( LCP(\mathit{rep}_B(x), \mathit{rep}_B(y)) ) be the length of the longest common prefix (digit‐wise) of these representations. Then the cost to convert ( x ) into ( y ) is given by:

[ \text{cost}(x,y) = |\mathit{rep}_B(x)| + |\mathit{rep}_B(y)| - 2\cdot LCP(\mathit{rep}_B(x), \mathit{rep}_B(y)). ]

Since operations are applied individually, the optimal strategy to equalize all numbers in ( A[l \ldots r] ) is to choose a target number ( y ) whose base ( B ) representation is the longest common prefix among the base ( B ) representations of all numbers in the subarray. More precisely, let

[ L_0 = \text{LCP}(\mathit{rep}_B(A[l]), \mathit{rep}_B(A[l+1]), \ldots, \mathit{rep}_B(A[r])). ]

Then the minimum total number of operations required is

[ \sum_{i=l}^{r} |\mathit{rep}_B(A[i])| - (r-l+1) \times L_0. ]

Your task is to answer all queries.

inputFormat

The input consists of multiple lines. The first line contains two integers ( n ) and ( m ) indicating the number of elements in the sequence and the number of queries, respectively. The second line contains ( n ) non-negative integers representing the sequence ( A ). Each of the next ( m ) lines contains three integers ( l ), ( r ), and ( B ) representing a query.

outputFormat

For each query, output a single integer — the minimum total number of operations required to make all numbers in ( A[l \ldots r] ) equal, according to the allowed operations.

sample

3 2
1 2 3
1 3 10
1 2 2

3
1

</p>