Problem C
Toys
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?
Input
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
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$.
Limits
-
$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 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
25 18 |
1 |
