CCGAMBLE - Cyclic Counting Gamble

Nowadays, gamble is so familiar even though it is prohibited in some countries. There are so many ways to gamble. Every rules of gambling always include the probability to win the game. Here, there is a unique rule of a gamble. This rule is called Cyclic Counting Gamble. This game is played by N players and there is only one winner. Those N players are standing and making a big circle. They are numbered from 1 to N. One player is pointed to be number one. Then, player who is in right side of the player numbered i, become player number i+1 (for 1 ≤ i < N). To decide who is the winner, they will chose one number K, then the following algorithm is used:

  1. Starting from player number one, saying "one" (1).
  2. Then, right side of player who is saying i, will say i+1.
  3. Repeat the second rule until a player saying K.
  4. That player will be considered to be lose, get out from circle and can't play anymore.
  5. Player who is right side of that lose player will say "one" and back to second rule.
  6. Repeat that algorithm until one player left, that player become the only winner.

Now, N players want to join that gamble (N is given). Then, they already chose K. Because N and K is too large, then the game can't finished although one century. Here, you are to find the fastest algorithm to know the winner in less than 0.5 second.

Input

Given N and K in one line separated by a white space.

Output

The only line contain one number represent the winner of that game.

Constraint

1 ≤ N, K ≤ 1018

N ≤ 107 or K ≤ 105

Example

Input:
5 2

Output:
3

Explanation

Sequence of players who are saying:

  • 1 say 1
  • 2 say 2 (lose)
  • 3 say 1
  • 4 say 2 (lose)
  • 5 say 1
  • 1 say 2 (lose)
  • 3 say 1
  • 5 say 2 (lose)

The winner is player with number 3.


Added by:Amnu
Date:2018-04-05
Time limit:0.5s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2018-11-26 07:26:03
Constraint not understood. It is written

1 ≤ N , K ≤ 10^18
N ≤ 10^7 or K ≤ 10^5

Which is the correct constraint?

RE :

1 ≤ N ≤ 10^7 and 1 ≤ K ≤ 10^18
or
1 ≤ N ≤ 10^18 and 1 ≤ K ≤ 10^5

Last edit: 2019-02-16 02:15:01
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.