P9376 "DROI" Round 2 Base and Operations

Instead of writing a weak background, it is better to make a higher-quality problem.

Define one operation on a number $x$ in base $B$ as either of the following: - Set $x \rightarrow \lfloor \dfrac{x}{B} \rfloor$. - Set $x \rightarrow x \times B + t$，where $t \in [0,B-1]$. You are given a sequence $A$ of length $n$. There are $m$ queries, and each query is in the form: - `l r B` means: for the numbers in the sequence $A$ with indices in $[l,r]$, when operating in base $B$, what is the minimum number of operations needed to make all numbers equal (note: each operation is applied to **one number**). **Queries are independent, i.e. the operations are not actually performed.**

The first line contains two integers, which are $n, m$. The second line contains $n$ numbers, representing the sequence $A$. The next $m$ lines each contain three numbers, representing $l, r, B$ for the query.

Output $m$ lines in total. The $i$-th line should contain the answer to the $i$-th query.

### Sample Explanation For sample 1, for the five queries, making all numbers in the interval become $3$, $4$, $8$, $4$, and $6$, respectively, is one optimal way. ------------ ### Constraints **"This problem uses bundled testdata."** - $\operatorname{Subtask} 1(10\%)$: $n,m \leq 1000$. - $\operatorname{Subtask} 2(20\%)$: it is guaranteed that all queries have $B=2$. - $\operatorname{Subtask} 3(40\%)$: $n,m \leq 3 \times 10^4$. - $\operatorname{Subtask} 4(30\%)$: no special restrictions. For $100\%$ of the testdata: $1 \leq n,m \leq 10^5$, $2 \leq A_i,B \leq 10^8$. Translated by ChatGPT 5