Sometimes seat selection is not as easy. One night, you are first to arrive at your friend's dinner party. Your friend has not finished setting up the n dinner table placeholders that he has made for you and yourfriends. He gives you the n placeholders to place around the round dinner table, and each seat at the table is already numbered 1 through n, increasing clockwise, in a circle. Because your friend likes to playgames, he instructs you to put a placeholder at every mth spot at the table moving clockwise, starting at whichever place you choose and ignoring any spot with a placeholder already. The last placeholder isyours, and you want to sit in the seat numbered n. At which spot should you start putting down placeholders?
For example, given 10 sets and instructions to put a placeholder at every 3rd seat, you want to begin by putting a placeholder at seat 9. The placement order is as follows: 9, 2, 5, 8, 3, 7, 4, 1, 6, 10. (Note that you will place at 9 first, then skip 3.) The last seat, 10, is yours.
For example, given 10 sets and instructions to put a placeholder at every 3rd seat, you want to begin by putting a placeholder at seat 9. The placement order is as follows: 9, 2, 5, 8, 3, 7, 4, 1, 6, 10. (Note that you will place at 9 first, then skip 3.) The last seat, 10, is yours.
Input Format
Line 1: an integer nLine 2: an integer m
Sample Input
10
3
Output Format Line 1: an integer f, the prisoner to shoot first in order to spare the nth prisoner
Sample Output
9You must be logged in to submit a solution.