解题思路

• 观察：每次把一个 1 加到序列末尾；若有 k 个相邻且相等为 x，就合并为一个 x+1。这个过程与“k 进制加一并进位”完全一致： 将序列中“值为 x 的元素个数”记为 cnt[x]，始终有

  $$\sum_{x\ge1} cnt[x]\cdot k^{x-1}=n$$

  （一次合并把 k 个 x 变成一个 x+1，两边权重都等于 k\cdot k^{x-1}=k^x）。

题目内容

首先，你有一个为空的序列，接下来会进行 $n$ 次操作：

每次操作：将一个单独的数字 $1$ 放入序列末尾；

如果序列中出现 $k$ 个相邻的元素都等于 $x$ ，则这 $k$ 个元素会合并成一个元素，值为 $x+1$ ；

合并后可能会触发新的合并操作，直到序列中不存在可合并区间为止。

定义最终序列中的元素依次拼接成一个十进制数，作为答案输出。

输入描述

在一行上输入两个整数 $n,k(1≦n≦10^{18};2≦k≦2×10^5)$ ，分别表示操作总次数，合并阈值。

输出描述

在一行上输出一个整数，表示最终序列中所有元素从左到右拼接形成的十进制数。

样例1

输入

5 2

输出

3 1

说明

在这个样例中，操作如下：

• 第一次，序列由 { } 变为 { $1$ }；

• 第二次，序列由 {$1$} 变为 {$1,1$}，随后两个相邻的 $1$ 合并成 {$2$}；

• 第三次，序列由 {$2$} 变为 {$2,1$};

• 第四次，序列由 {$2,1$} 变为 {$2,1,1$}，先合并 {$1,1$}→$2$ 得 {$2,2$}，再合并 $2,2→3$ 得 {$3$ };

• 第五次：序列由 {$3$} 变为 {$3,1$}。