Josephus Circle

Lab C Advanced 30 points

n people stand in a circle numbered 1..n. Starting from 1, every k-th person is removed. Using a queue (array), print the order of removal.

Input

Two integers n k (n ≤ 50).

Output

One line.

Example

Input

7 3

Output

3 6 2 7 5 1 4

Sample input available Sample output available

Editor

Hints

Move k-1 people from the front to the back, then remove the front person.

Solution explanation

The queue simulates walking around the circle.

Show solution

#include <stdio.h>

int main() {
    int n, k, q[2600], front = 0, back = 0;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        q[back] = i;
        back++;
    }
    int first = 1;
    while (front < back) {
        for (int i = 1; i < k; i++) {
            q[back] = q[front];
            back++;
            front++;
        }
        if (!first) printf(" ");
        printf("%d", q[front]);
        front++;
        first = 0;
    }
    printf("\n");
    return 0;
}

Output

Answer