Hide

Problem J
Card Counting Club

/problems/cardcountingclub/file/statement/en/img-0001.jpg
Picture by Ron Maijen via Wikimedia Commons, cc by-sa 3.0

During the creation of the Card Counting Club, the club wanted to combine their card counting practice along with the process of choosing player order for their games. They converged on a counting-out game that is played like so:

  1. At the beginning of the game, each player is dealt a hand with the same number of cards as everyone else.

  2. Each player begins the turn by showing the card with the smallest value in their hand to the other players.

  3. The player with the smallest card gets to discard it.

    1. Only one player gets to discard their card, and the ties are broken by choosing the player’s whose name comes first lexicographically (i.e. standard dictionary order).

    2. All players that do not get to discard their card leave a small mark on their card and place it back into their hand. Each mark increases the value of the card by an agreed penalty amount.

  4. When a player runs out of cards, they are counted out.

  5. The game is played until all players are counted out.

Once the game is over, the order of players as they were counted out is used to choose the order in which the club members get to play other games.

Over time, the club grew to 35 people, and the cost of the cards along with the time it takes to play out the game became too much. So, the club turns to you to make a program that will play out the game for them to save both time and the cost of the playing cards.

Input

The first line contains three integers $N, M, P$ $( 2 \leq N \leq 35$, $1 \leq M \leq 17\, 000$, and $1 \leq P \leq 10$) where $N$ is the number of players, $M$ is the hand size of each player, and $P$ is the penalty amount for each mark. The next $N$ lines contain the name of the player followed by $M$ space-separated integers $x_1, x_2, \ldots , x_ N$ ($1 \leq x_ i \leq 200\, 000$ for each $1 \leq i \leq M$) representing the values of the cards in the player’s hand. The values may repeat both within and between hands. Each player’s name will consist only of uppercase letters and will have length between $2$ and $10$.

Output

On a single line, display the list of player names in the order in which they are counted out in regular play of the game. Consecutive names on this line should be separated with a single space.

Sample Input 1 Sample Output 1
3 3 3
BOB 5 2 1
EVE 1 4 3
ALICE 3 4 2
EVE ALICE BOB
Sample Input 2 Sample Output 2
3 1 5
WYNKEN 7
BLYNKEN 7
NOD 7
BLYNKEN NOD WYNKEN

Please log in to submit a solution to this problem

Log in