Description

Three students play poker during a break from learning programming (numbered $1,2,3$). Each person starts with $n$ cards. There are $m$ different ranks in total. Any number of identical cards can be played together as a group.

At the beginning, the first player plays, and they must play the smallest card in their hand. After that, players take turns in the order $1,2,3,1,2,3\ldots$. Each player plays a group of cards that is larger than the group played by the previous player, choosing the smallest group they can play. If they cannot play, they pass.

The comparison rule between groups is as follows: a group with more cards is larger than a group with fewer cards; if the number of cards is the same, then the group with the larger rank is larger. For example, $(1,1,1)>(3,3)>(2,2)>(4)>(1)$.

If, in a round, the other two players are both unable to play, then the next round starts again from the player who played the last group. Whoever plays all of their cards first wins. Determine who will win in the end, and output the winner’s number.

For all testdata, $n,m\leq 50$.

Input Format

The input has $4$ lines.

Line $1$ contains two positive integers $n,m$.

Lines $2$ to $4$ each contain $n$ numbers, describing the cards each person initially has.

Output Format

The output has $1$ line with $1$ positive integer, which is the winner’s number.

10 3
1 3 3 1 3 3 1 2 3 3 
3 2 1 2 2 3 3 1 1 2 
2 2 1 2 3 1 2 3 3 1 

3

Hint

How the sample is played:

Round 1:
[1]: 1 3 3 1 3 3 1 2 3 3, plays [1]
[2]: 3 2 1 2 2 3 3 1 1 2, plays [2]
[3]: 2 2 1 2 3 1 2 3 3 1, plays [3]
[1]: 3 3 1 3 3 1 2 3 3, plays [1,1]
[2]: 3 1 2 2 3 3 1 1 2, plays [2,2]
[3]: 2 2 1 2 1 2 3 3 1, plays [3,3]
[1]: 3 3 3 3 2 3 3, plays [3,3,3]
[2]: 3 1 3 3 1 1 2, cannot play
[3]: 2 2 1 2 1 2 1, plays [2,2,2,2]
[1]: 3 2 3 3, cannot play
[2]: 3 1 3 3 1 1 2, cannot play


Round 2:
[3]: 1 1 1, plays [1]
[1]: 3 2 3 3, plays [2]
[2]: 1 3 3 1 1 2, plays [3]
[3]: 1 1, plays [1,1] <- wins

Translated by ChatGPT 5