在工厂(Lihmuf Sorting)工作后,Lihmuf 想和他的好朋友 Pak Chanek 玩游戏。有 $$$N$$$ 个盒子,编号从 $$$1$$$ 到 $$$N$$$。第 $$$i$$$ 个盒子包含 $$$i$$$ 个球。 Pak Chanek 和 Lihmuf 将使用这些盒子玩游戏。
将会有 $$$N$$$ 回合,编号从 $$$1$$$ 到 $$$N$$$。在每一回合中,Pak Chanek 选择一个盒子并从该盒子中取出所有球,然后 Lihmuf 对他选择的一个盒子做同样的事情(有可能两个选择的盒子是相同的)。
给定一个整数$$$M$$$。在游戏开始之前,Lihmuf 必须选择一个满足 $$$1 \leq K \leq M$$$ 的整数 $$$K$$$。已知在第 $$$j$$$ 个回合中,Pak Chanek 将选择第 $$$j$$$ 个盒子,而 Lihmuf 将选择第 $$$y$$$ 个盒子,其中 $$$y=((j \times K - 1) \bmod N) + 1$$$。帮助 Lihmuf 选择正确的 $$$K$$$ 值,以便他获得尽可能多的球!如果 $$$K$$$ 的可能值有多个,导致球总数最多,请找到 $$$K$$$ 的最小此类值。
请记住,每个框都可以选择多次,但第一次选择框后,该框就会变空。
输入
唯一的一行包含两个整数 $$$N$$$ 和 $$$M$$$ ($$$1 \leq N \leq 10^9$$$; $$$1 \leq M \leq 2000$$$) — 盒子的数量和 $$$K$$$ 值的最大限制。
输出
一个整数,表示 $$$K$$$ 的值,这将使 Lihmuf 获得尽可能多的球。如果 $$$K$$$ 的可能值有多个,导致球总数最多,请找到 $$$K$$$ 的最小此类值。
示例
输入 #1
3 1
输出 #1
1
输入 #2
5 4
输出 #2
3
注意
在第一个例子中,如果 Lihmuf 选择 $$$K=1$$$,游戏将如下进行:
1. Pak Chanek 选择 $$$1$$$-st 盒子并获得 $$$1$$$ 球,然后 Lihmuf 选择 $$$1$$$-st 盒子并获得 $$$0$$$ 球。
2. Pak Chanek 选择 $$$2$$$-nd 盒子并获得 $$$2$$$ 球,然后 Lihmuf 选择 $$$2$$$-nd 盒子并获得 $$$0$$$ 球。
3. Pak Chanek 选择 $$$3$$$-rd 盒子并获得 $$$3$$$ 球,然后 Lihmuf 选择 $$$3$$$-rd 盒子并获得 $$$0$$$ 球。
Lihmuf 总共获得 $$$0+0+0=0$$$ 球。
Lihmuf 可以获得的最大球总数为 $$$0$$$,因为他只能选择 $$$K=1$$$。因此,$$$K=1$$$ 是导致最多球总数的 $$$K$$$ 的最小可能值。
在第二个例子中,如果 Lihmuf 选择 $$$K=3$$$,游戏将如下进行:
1. Pak Chanek 选择 $$$1$$$-st 盒子并获得 $$$1$$$ 球,然后 Lihmuf 选择 $$$3$$$-rd 盒子并获得 $$$3$$$ 球。
2. Pak Chanek 选择 $$$2$$$-nd 盒子并获得 $$$2$$$ 球,然后 Lihmuf 选择 $$$1$$$-st 盒子并获得 $$$0$$$ 球。
3. Pak Chanek 选择第 $$$3$$$ 个盒子并获得 $$$0$$$ 球,然后 Lihmuf 选择第 $$$4$$$ 个盒子并获得 $$$4$$$ 球。
4. Pak Chanek 选择第 $$$4$$$ 个盒子并获得 $$$0$$$ 球,然后 Lihmuf 选择第 $$$2$$$ 个盒子并获得 $$$0$$$ 球。
5. Pak Chanek 选择第 $$$5$$$ 个盒子并获得 $$$5$$$ 球,然后 Lihmuf 选择第 $$$5$$$ 个盒子并获得 $$$0$$$ 球。
Lihmuf 总共获得 $$$3+0+4+0+0=7$$$ 球。
可以得出,$$$7$$$ 是 Lihmuf 可以获得的最大总球数。导致 $$$7$$$ 球总数的 $$$K$$$ 的可能值为 $$$3$$$ 和 $$$4$$$。因此,$$$K=3$$$ 是$$$K$$$ 产生最多球总数的最小可能值。