有 n 个人在争夺一枚金币。

所有人排成一队，然后位于第 1,1+k,1+2k,\dots,1+(⌊n/k⌋−1)k 个的人被淘汰，这里 ⌊n/k⌋ 为 n 除以 k 上取整，上取整操作会将一个小数变成大于或等于它的最小整数，如 ⌊33/5⌋=⌊6.6⌋=7。重复这一操作，直到仅剩一个人。最终剩下的这个人获得这枚金币。

小 Y 是所有人中最聪明的。他想知道，要想最终获得金币，一开始他应该站在第几个位置？

一行包含两个正整数 n 和 k，表示总人数以及淘汰时用到的参数。

输出一行一个整数，表示小 Y 应该处于的初始队列中的位置。

样例输入 4

1919810 114514

样例输出 4

1919805

样例解释

对于样例 1：n=6，起初，队列 =[1,2,3,4,5,6]，因为 k=2，所以位于第 1,3,5 的人被淘汰，队列 =[2,4,6]，然后位于第 1,3 的人被淘汰，队列 =[4]，只剩下一个人，所以小 Y 一开始应该站在 4 号位置。

对于样例 2：n=8，起初，队列 =[1,2,3,4,5,6,7,8]，因为 k=3，所以位于 1,4,7 的人被淘汰，队列 =[2,3,5,6,8]，然后位于 1,4 的人被淘汰，队列 =[2,5,8]，然后位于 1 的人被淘汰，队列 =[5,8]，然后位于 1 的人被淘汰，队列 =[8]，只剩下一个人，所以小 Y 一开始应该站在 8 号位置。

数据范围

本题共有 12 个测试点，每个测试点 10 分。

对于全部测试点：2 \le n,k \le 10^{12}。

对于测试点 1 ：n=k=2。

对于测试点 2-4 ：n,k \le 1000。

对于测试的 5-8 ：k \le 1000000

2025年常州“信息与未来”小学生编程比赛

市赛常州2025数论