Problem J
Exploding Kittens
Today your friends are playing a game of Exploding Kittens. On a player’s turn, she must perform the following actions in order:
-
Draw a single card from the top of the deck.
-
If the drawn card is an “Exploding Kitten”, she must leave the game unless she has a “Defuse” card in her hand, in which case she must discard both the “Exploding Kitten” card and the “Defuse” card, so that these two cards will never be drawn again in the same game. Otherwise, she can choose to do nothing.
-
If she has more than five cards in his hand, she must discard cards until he has no more than five cards.
Players alternate turns in a single round, and the relative orders in which players take turns must be identical between rounds. When a player leaves the game, the relative draw order of other players will stay the same. The last player left in the game is the winner, and the game will stop at that point.
You don’t want to watch the game because there’s no skill involved, but you still would like to know the result. You somehow know the location of all “Exploding Kittens” and “Defuse” cards in the deck. Assuming everyone starts with an empty hand and plays optimally (i.e. discard “Defuse” cards only when absolutely necessary), who will win the game?
Input
The first line consists of three integers $N$, the number of players in the game, $E$, the number of “Exploding Kitten” cards, and $D$, the number of “Defuse” cards. Note that $2\leq N\leq 1\, 000$ and $2\leq D, E\leq 10\, 000$.
The next line of the input contains $E$ integers $e_ i$ ($0\leq e_ i\leq 2\cdot 10^9$). This represents the number of cards between a “Exploding Kitten” card and the top card of the deck.
The final line of the input contains $D$ integers $d_ i$ ($0\leq d_ i\leq 2\cdot 10^9$). This represents the number of cards between a “Defuse” card and the top of the deck.
It is guaranteed that all “Exploding Kittens” and “Defuse” cards given in the input are located at distinct locations within the deck.
Output
If there is a winner, print the ID of the winner, defined as the number of players who took their turn before the winner on the first round. Otherwise, print $-1$.
Sample Input 1 | Sample Output 1 |
---|---|
2 4 3 3 4 5 7 1 2 10 |
0 |
Sample Input 2 | Sample Output 2 |
---|---|
3 5 2 1 4 7 9 11 2 3 |
2 |
Sample Input 3 | Sample Output 3 |
---|---|
3 3 2 1 4 7 2 3 |
-1 |