DSA Homework 3

De la WikiLabs
Jump to navigationJump to search

The Game

Little John is playing a game with his friends. They all sit in a circle and a specified person starts the game by saying his number K. Then the Kth person in the circle, clockwise, is eliminated and the next one says his number and all goes on until there is only one person left.

Help Little John figure out who is winner of the game when knowing how many friends are playing at the beginning and who starts the game.

Requirement

Given a number N of people in the circle and a number K <= N of the person who starts, specify who is the last person left in the game.

Input Data

A file called game.in, containing the number of people N on the first line and the number K representing the person who starts, on the second line.

Output Data

A file called game.out, containing a number specifying the last person left in the game.

Restrictions

1 ≤ K ≤ N ≤ 100000

Examples

Input Output

5

2

3

Explanation

At the start, there are 5 people in the circle: 1 2 3 4 5

1. Person number 2 starts by saying his number, 2. Advancing by that amount will reach person 4, who is eliminated: 1 2 3 5

2. 4 was eliminated, so the next one in the circle, 5 says his number. Advancing 5 positions from 5 will reach person 1, who is eliminated (remember, they are in a circle, so just go from 5 to 1, at the end of the line): 2 3 5

3. The next is 2, so he says his number, that reaches 5, which is eliminated: 2 3

4. Next is 2 again and saying 2 will eliminate himself and so 3 is the last one left: 3