「DROI」Round 2 进制与操作

与其编写苍白无力的背景，不如出更有质量的题。

定义数 $x$ 在 $B$ 进制下的一次操作为以下两种操作中的任意一种： - 令 $x \rightarrow \lfloor \dfrac{x}{B} \rfloor$。 - 令 $x \rightarrow x \times B + t $。其中 $t \in [0,B-1]$。 现给定长度为 $n$ 的序列 $A$。$m$ 次询问，每次询问形如： - `l r B` 表示询问将序列 $A$ 中下标在 $[l,r]$ 之内的数在 $B$ 进制下操作，至少多少次才能将所有数变为相同（注：每次操作是对**一个数**进行操作）。 **询问间相互独立，即操作不会真的进行。**

第一个两个整数，分别表示 $n,m$。 第二行一行 $n$ 个数，表示序列 $A$。 接下来 $m$ 行，每行三个数，分别表示这次询问的 $l,r,B$。

输出共 $m$ 行，其中第 $i$ 行表示第 $i$ 次询问的答案。

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

### 样例解释 对于样例一，五次询问分别将区间内所有数变为 $3$、$4$、$8$、$4$、$6$ 是一种最优操作。 ------------ ### 数据范围 **「本题采用捆绑测试」** - $\operatorname{Subtask} 1(10\%)$：$n,m \leq 1000$。 - $\operatorname{Subtask} 2(20\%)$：保证所有询问 $B=2$。 - $\operatorname{Subtask} 3(40\%)$：$n,m \leq 3 \times 10^4$。 - $\operatorname{Subtask} 4(30\%)$：无特殊限制。 对于 $100\%$ 的数据：$1 \leq n,m \leq 10^5$，$2 \leq A_i,B \leq 10^8$。