Josephus Permutation

Interview

Time limit2sMemory limit512 MB

Summary

Remove every Kth person from a circle of N people and print the removal order in angle brackets.

Level: Easy3 of 10
Topics: Queue, Simulation
Solved: No attempts yet

Problem

$N$ people numbered 1 to $N$ sit in a circle, and a positive integer $K$ ( $K \le N$ ) is given. Starting the count at person 1, remove the $K$ th person from the circle. Once a person is removed, count again from 1 at the next person, remove the $K$ th person, and repeat the same process along the circle of the remaining people. The process continues until all $N$ people are removed. The order in which the people are removed is the $(N, K)$ -Josephus permutation. For example, the $(7, 3)$ -Josephus permutation is <3, 6, 2, 7, 5, 1, 4>.

Given $N$ and $K$ , write a program that finds the $(N, K)$ -Josephus permutation.

Input

The first line contains $N$ and $K$ in this order, separated by a space. ( $1 \le K \le N \le 1000$ )

Output

Print the Josephus permutation on one line. Start with the opening angle bracket <, write the numbers in the order they were removed, separate consecutive numbers with a comma and one space, and finish with the closing angle bracket >.

Examples7

Example 1
Input
```
7 3
```
Expected output
```
<3, 6, 2, 7, 5, 1, 4>
```
Example 2
Input
```
1 1
```
Expected output
```
<1>
```
Example 3
Input
```
5 1
```
Expected output
```
<1, 2, 3, 4, 5>
```
Example 4
Input
```
5 5
```
Expected output
```
<5, 1, 3, 4, 2>
```
Example 5
Input
```
2 2
```
Expected output
```
<2, 1>
```
Example 6
Input
```
6 4
```
Expected output
```
<4, 2, 1, 3, 6, 5>
```
Example 7
Input
```
10 2
```
Expected output
```
<2, 4, 6, 8, 10, 3, 7, 1, 9, 5>
```