{"raw_statement":[{"iden":"background","content":"与其编写苍白无力的背景，不如出更有质量的题。"},{"iden":"statement","content":"定义数 $x$ 在 $B$ 进制下的一次操作为以下两种操作中的任意一种：\n\n- 令 $x \\rightarrow \\lfloor \\dfrac{x}{B} \\rfloor$。\n\n- 令 $x \\rightarrow x \\times B + t $。其中 $t \\in [0,B-1]$。\n\n现给定长度为 $n$ 的序列 $A$。$m$ 次询问，每次询问形如：\n\n- `l r B` 表示询问将序列 $A$ 中下标在 $[l,r]$ 之内的数在 $B$ 进制下操作，至少多少次才能将所有数变为相同（注：每次操作是对**一个数**进行操作）。\n\n**询问间相互独立，即操作不会真的进行。**\n\n"},{"iden":"input","content":"第一个两个整数，分别表示 $n,m$。\n\n第二行一行 $n$ 个数，表示序列 $A$。\n\n接下来 $m$ 行，每行三个数，分别表示这次询问的 $l,r,B$。"},{"iden":"output","content":"输出共 $m$ 行，其中第 $i$ 行表示第 $i$ 次询问的答案。"},{"iden":"note","content":"### 样例解释\n\n对于样例一，五次询问分别将区间内所有数变为 $3$、$4$、$8$、$4$、$6$ 是一种最优操作。\n\n------------\n\n### 数据范围 \n\n**「本题采用捆绑测试」**\n\n- $\\operatorname{Subtask} 1(10\\%)$：$n,m \\leq 1000$。\n\n- $\\operatorname{Subtask} 2(20\\%)$：保证所有询问 $B=2$。\n\n- $\\operatorname{Subtask} 3(40\\%)$：$n,m \\leq 3 \\times 10^4$。\n\n- $\\operatorname{Subtask} 4(30\\%)$：无特殊限制。\n\n对于 $100\\%$ 的数据：$1 \\leq n,m \\leq 10^5$，$2 \\leq A_i,B \\leq 10^8$。\n"}],"translated_statement":null,"sample_group":[["5 5\n7 6 5 8 9\n1 3 2\n2 5 2\n4 4 6\n3 5 4\n1 5 3","5\n8\n0\n5 \n10"],["8 4\n10 14 7 11 19 13 7 18 \n1 7 4\n3 8 2\n1 4 4\n1 4 2\n","15\n18\n8\n11\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}