题目背景

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

题目描述

定义数 $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$。