class Player(object):
    def __init__(self, cardString):
        # Splits the deck string into a list
        self.deckList = [int(n) for n in cardString.split()]
        self.collection = []
    
    def draw(self):
        # Returns the first card of the deck while also removing it
        return self.deckList.pop(0)
    
    def addToCollection(self, cardStack):
        # Collection is a form of staging a deck until we're ready to add it to the bottom of the deck
        self.collection.extend(cardStack)

    def collect(self):
        self.deckList.extend(self.collection)
        self.collection = []
        
    def cardsRemaining(self):
        return len(self.deckList)
    
    # Used to grab the next 1-4 cards when performing a war
    def split(self, amount):
        deckCopy = self.deckList
        self.deckList = deckCopy[amount:]
        
        return deckCopy[:amount]

def main(deckOne, deckTwo):
    playerOne = Player(deckOne)
    playerTwo = Player(deckTwo)
    
    while (True):
        battle(playerOne, playerTwo)
        
        if (playerOne.cardsRemaining() == 0 and playerTwo.cardsRemaining() == 0):
            print('0')
            break
        elif(playerOne.cardsRemaining() == 0):
            print('2')
            break
        elif(playerTwo.cardsRemaining() == 0):
            print('1')
            break
    
def battle(playerOne, playerTwo):
    victor = None
    
    if (playerOne.deckList[0] > playerTwo.deckList[0]):
        playerOne.addToCollection([playerOne.draw(), playerTwo.draw()])
        victor = playerOne
    elif(playerTwo.deckList[0] > playerOne.deckList[0]):
        playerTwo.addToCollection([playerTwo.draw(), playerOne.draw()])
        victor = playerTwo
    else:
        # Upon a tie, we draw the two cards we were comparing and hold onto them for the time being
        # We then start a war 
        tieDeck = [playerOne.draw(), playerTwo.draw()]
        victor = war(playerOne, playerTwo)
        
        # If there wasn't a victor in the war, we simply return
        if (victor == None):
            return
        
        # If there is a victor, we add to the cards we were sitting onto to the victor
        victor.addToCollection(tieDeck)
    
    # Moves the victor's collection of cards to the bottom of their deck
    victor.collect()
    
def war(playerOne, playerTwo):
    index = None

    # We iterate to see how many cards can we pull from both deck, once we find the amount, we break 
    for x in range(4,0,-1):
        if (playerOne.cardsRemaining() >= x and playerTwo.cardsRemaining() >= x):
            index = x
            break;
    
    
    # If index wasn't defined, that means that either one or both of the players don't have enough cards
    if (index == None):
        # If both don't have enough, we return None to signify no victor
        if (playerOne.cardsRemaining() == 0 and playerTwo.cardsRemaining() == 0):
            return None
        # Otherwise we return the winner
        return playerTwo if (playerOne.cardsRemaining() == 0) else playerOne
    
    # We split the most cards we can from each deck and sit on them for now
    playerOneSplit = playerOne.split(index)
    playerTwoSplit = playerTwo.split(index)
    
    # We assign the cards we'll be checking for the war
    playerOneDrawnCard = playerOneSplit[len(playerOneSplit) - 1]
    playerTwoDrawnCard = playerTwoSplit[len(playerTwoSplit) - 1]
 
    victor = None
 
    # If the new face up cards still result in a tie, we recursively start a new war
    if (playerOneDrawnCard == playerTwoDrawnCard):
        victor = war(playerOne, playerTwo)
    else:
        # Otherwise, we decide the victor
        victor = playerOne if playerOneDrawnCard > playerTwoDrawnCard else playerTwo
    
    # If we recursively retrieve a None as the victor, we continue the return 
    if (victor == None):
        return None
    elif (victor == playerOne):
        playerOne.addToCollection(playerOneSplit + playerTwoSplit)
    else:
        playerTwo.addToCollection(playerTwoSplit + playerOneSplit)
    
    return victor

if __name__ == "__main__":
    # Challlenge 1
    deckOne = "5 1 13 10 11 3 2 10 4 12 5 11 10 5 7 6 6 11 9 6 3 13 6 1 8 1"
    deckTwo = "9 12 8 3 11 10 1 4 2 4 7 9 13 8 2 13 7 4 2 8 9 12 3 12 7 5"
    print("\nChallenge One")
    print("-------------")
    main(deckOne, deckTwo)
    
    print("\nChallenge Two")
    print("-------------")
    # Challlenge 2
    deckOne = "3 11 6 12 2 13 5 7 10 3 10 4 12 11 1 13 12 2 1 7 10 6 12 5 8 1"
    deckTwo = "9 10 7 9 5 2 6 1 11 11 7 9 3 4 8 3 4 8 8 4 6 9 13 2 13 5"
    main(deckOne, deckTwo)
    
    print("\nChallenge Three")
    print("-------------")
    # Challlenge 3
    deckOne = "1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13"
    deckTwo = "1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13"
    main(deckOne, deckTwo)