Challenge: Pass the Parcel

Lab Python Intermediate 20 points

Children sit in a circle in the given order. The parcel starts with the first child and is passed; every k-th child to hold it leaves the circle (counting the first holder as 1). Print the children in the order they leave, then Winner: <name>. Use a deque.

Input

Line 1: names. Line 2: k (k ≥ 1).

Output

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

Example

Input

A B C D E
3

Output

C
A
E
B
Winner: D

Sample input available Sample output available

Editor

Python

Hints

Move the front child to the back k - 1 times (or use rotate).

Then popleft() removes the k-th child.

Solution explanation

The deque behaves like the circle: the front is whoever holds the parcel.

Show solution

from collections import deque
circle = deque(input().split())
k = int(input())
while len(circle) > 1:
    circle.rotate(-(k - 1))
    print(circle.popleft())
print("Winner:", circle[0])

Output

Answer