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$.