Challenge: Pass the Parcel

Lab C++ Intermediate 20 points

Children sit in a circle in the given order. Every k-th child to hold the parcel leaves (the first holder counts as 1). Print the children as they leave, then Winner: <name>. Use a deque.

Input

Line 1: n k. Line 2: n names.

Output

One name per line as they leave, then the winner.

Example

Input

5 3
A B C D E

Output

C
A
E
B
Winner: D

Sample input available Sample output available

Editor

C++

Hints

Move the front to the back k - 1 times.

Then the front child leaves.

Solution explanation

The deque is the circle: its front is whoever holds the parcel.

Show solution

#include <deque>
#include <iostream>
#include <string>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    deque<string> d(n);
    for (auto& s : d) cin >> s;
    while (d.size() > 1) {
        for (int i = 0; i < k - 1; i++) {
            d.push_back(d.front());
            d.pop_front();
        }
        cout << d.front() << endl;
        d.pop_front();
    }
    cout << "Winner: " << d.front() << endl;
    return 0;
}

Output

Answer