The Game of Drunkard
In the card game "War," a deck is evenly divided between two players. Each player reveals their top card, and the player with the higher card wins both cards, placing them at the bottom of their deck. The player who runs out of cards loses the game.
For simplicity, assume all cards have unique ranks, and the lowest card beats the highest card (i.e., "six beats ace").
When a player wins the round, they place the first player's card at the bottom of their deck first, followed by the second player's card (so the second player's card ends up at the very bottom).
Write a program to simulate the game of "War" and determine the winner. The game uses n cards, with values ranging from 0 to n-1, where a higher card beats a lower one, except that the card with value 0 beats the card n-1.
Input
The program receives three lines of input. The first line contains an even integer n (2 ≤ n ≤ 100000). The second line contains n/2 numbers representing the first player's cards, and the third line contains n/2 numbers representing the second player's cards. Cards are listed from top to bottom, meaning each line starts with the card that will be revealed first. It is guaranteed that each card appears exactly once in the decks.
Output
The program should determine who wins with the given deal and output the word "first" or "second", followed by the number of moves made until the win. If the game does not conclude within 2·10^5 moves, the program should output the word "draw".