P7851 「JZOI-2」信号塔

团员们满脑子都是办周年庆，但小僖只想摸鱼。 小僖想看电视，但是发现没信号了，于是他去修理信号塔了。

在一条有 $10^{999}+1$ 个点的直线上，满足直线上相邻两点间的距离相等，每个点上建立都建立了一个信号塔，从左到右编号为 $0\sim 10^{999}$，其中 $0$ 号塔是电视节目发送点。 由于小僖只想看电视，所以这里的信号只会从左往右传输。假设一个信号塔的强度为 $x$，那么它的信号最多能往右传输 $\lfloor\frac{x-1}{k}\rfloor$ 的距离。 现在小僖要给每个信号塔设置一个强度，但由于信号塔太多了，他忙不过来，于是他交给了笨笨机器人来做。 笨笨机器人按照以下方式给每个信号塔设置一个强度。 首先先将 $0$ 号塔的强度设为 $10^{30}$，然后从左到右，从 $1$ 号信号塔开始一直做到 $10^{999}$ 号信号塔。对于每个信号塔，在其左边寻找离它最近的一个信号塔 $a$，满足 $a$ 信号塔的信号可以传送到该信号塔，然后将该信号塔的信号强度赋值为这两个信号塔之间的距离。 这里定义 $i$ 号信号塔和 $j$ 号信号塔之间的距离为 $|i-j|$。 例如当 $k=2$ 的时候 $1\sim5$ 号的信号塔的强度分别为 $1,2,3,1,5$。 但小僖还是不放心笨笨机器人，所以他想知道第 $n$ 个信号塔的强度。

一行，两个正整数 $n,k$。 具体意义见题面。

一行，一个整数，表示编号为 $n$ 信号塔的强度。

对于 $10\%$ 的数据，$1\le n,k\le 2 \times 10^3$。 对于 $30\%$ 的数据，$1\le n\le 1 \times 10^7$。 对于另外 $15\%$ 的数据，$k=1$。 对于另外 $15\%$ 的数据，$k=2$。 对于 $100\%$ 的数据 $1\leq n\leq10^{18},1\leq k\leq10^{6}$。