Little Lark has a great collection of of toys. Although she has plenty of toys she only likes to play with one at a time. She decides which toy to play with by placing all the toys in a circle around her, numbering them $0$ to $T-1$. She then spins around in the clockwise direction and removes every $K$th toy until one remains. This means that the first toy that she removes is numbered $K-1$. If any toys are moved during this ritual Lark will start crying and then rearrange the toys in the circle in the original order.

Today Lark wants her father to join her while playing with the toys. Her father has of course a favorite toy among Lark’s selection of toys and would of course like that specific toy to be chosen. At which position should he place his favorite toy to make sure that is the toy they end up playing with?


The input is a single line consisting of $2$ integers $T$ and $K$ indicating the number of toys Lark has and the skip length she takes while selecting the next toy to discard.


Output a line with the a single integer, the position the father needs to place his favorite toy for it to be selected. Lark will start counting at position $0$.


  • $1 \leq T \leq 10\, 000\, 000$

  • $1 \leq K \leq 1\, 000\, 000$

  • $K \leq T$

Sample Input 1 Sample Output 1
5 2
Sample Input 2 Sample Output 2
25 18
CPU Time limit 2 seconds
Memory limit 1024 MB
Difficulty 4.2medium
Statistics Show
Source IDI Open 2017
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in