Three-Player Card Game Showdown

Three students with identifiers \(1, 2, 3\) are playing a card game during their programming break. Initially, each player is dealt \(n\) cards and the cards come in \(m\) different types (with values in the range \(1\) to \(m\), where \(n, m \le 50\)). In this game, a player may play a group of identical cards at once. The strength of a move (i.e. a group of cards) is determined first by the number of cards played and then by the card value. In other words, a group \((k, a)\) (meaning \(k\) cards of value \(a\)) is considered stronger than \((l, b)\) if either \(k > l\) or \(k = l\) and \(a > b\). For example, using latex ordering we have:

[ (3,1) > (2,3) > (2,2) > (1,4) > (1,1) ]

The game is played as follows:

1. Player 1 starts the game by playing the smallest move available from his hand. (Since playing a single card is always an option, the smallest move is to play one card of the smallest value in his hand.)
2. Then, the players take turns in the order \(1, 2, 3, 1, 2, 3, \dots\). On each turn, a player must play a move that is strictly stronger than the move played by the previous player. If a player has several valid moves, they must choose the one which is minimal among those valid moves (again, the moves are compared by first comparing the count, then the card value).
3. If a player cannot play any valid move, they must pass.
4. If in a round the other two players consecutively cannot beat the last played move, the round ends. The player who played the last valid move then starts a new round by playing the smallest move available from his hand.
5. The game ends as soon as one of the players has no cards remaining. That player is declared the winner.

Given the initial hands of the three players, determine the identifier of the winning player.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of cards per player and the number of card types respectively (\(n, m \le 50\)).

Then follow three lines. The \(i\)-th line contains \(n\) integers representing the values of the cards in player \(i\)'s hand. Each card value is an integer in the range \(1\) to \(m\).

outputFormat

Output a single integer representing the identifier of the winning player (either 1, 2, or 3).

sample

1 5
1
2
3

3