KMO

给定一个长度为 $N$ 的序列 $a=(a_1,a_2,\cdots,a_N)$ 和一个整数 $K$。

如果长度为 $N$ 的序列 $b=(b_1,b_2,\cdots,b_N)$ 满足以下两个条件，就称其为。

• $b_i$ 是非负整数（$1\leq i\leq N$）。
• $\displaystyle\sum_{i=1}^{N}K^{-b_i}\leq1$。

请找出一个使 $\displaystyle\sum_{i=1}^{N}a_i b_i$ 最小的好序列。

输入格式如下：

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

对于每个测试用例，在一行中输出一个最优好序列 $b_1,b_2,\cdots,b_N$，各数之间用空格分隔。

• $1\leq T\leq200\,000$.
• $1\leq N\leq200\,000$.
• $2\le K\le$.