War, the Card Game

War is a card game for two players that needs no skill at all, which makes it perfect for a computer to play. Each player has a deck: a list of card values from 2 to 14 (an ace is 14), where the first card in the list is the top of the deck. Each round goes like this:

• Both players put their top card face up on the table. The higher card wins the round.
• If the two cards are equal, there is a war: each player puts their next 3 cards face down on the table, then 1 more face up, and the new face-up cards are compared. If those are equal too, another war follows, and so on.
• If a war starts while a player has fewer than 4 cards left in their deck, the game ends at once: the player with fewer cards in their deck loses, and if both have the same number, nobody wins.
• The winner of the round takes every card on the table and puts them at the bottom of their deck: first all the cards they put down themselves, in the order they put them down, then the other player's cards, in the order those were put down.
• A player with no cards left after a round has lost the game.

Some games would go on forever, so if nobody has won after max_rounds rounds, the game stops there with nobody winning. Write war(deck1, deck2, max_rounds) that returns a tuple (winner, rounds): winner is 1 or 2 for the player who won the game, or 0 if nobody won, and rounds is the number of rounds played, including the one that ended the game.

Examples

war([5], [3], 10)                          # returns (1, 1)
war([2, 9], [8, 3], 10)                    # returns (1, 4)
war([7, 2, 3, 4, 5], [7, 9, 9, 9, 6], 10)  # returns (2, 1)

In the second game, player 2 wins round 1 (8 beats 2) and their deck becomes [3, 8, 2]. Player 1 then wins three rounds in a row: 9 beats 3, 9 beats 8 and 3 beats 2, and player 2 has no cards left. In the third game the two 7s start a war: 5 against 6, so player 2 takes all ten cards in the first round.

Constraints

• Each deck has 1 to 52 cards; 1 <= max_rounds <= 100,000.