Background

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

Problem Description

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.

Input Format

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 Format

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

5 5
7 6 5 8 9
1 3 2
2 5 2
4 4 6
3 5 4
1 5 3

5
8
0
5 
10

8 4
10 14 7 11 19 13 7 18 
1 7 4
3 8 2
1 4 4
1 4 2

15
18
8
11

Hint

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