# ----06-18-2024 22:22:59----

# map to (turns to win + 1), or False
winnable_cache = {}

def bestMovePlayer2(N1, N2, K1, K2, p1coins):
    winByLoseRound = (p1coins > 0) and winnable(N1 - p1coins, N2, K1-1, K2)
    winByWinRound = (N2-p1coins-1 >= 0) and winnable(N1-p1coins, N2-p1coins-1, K1, K2-1)
    winByDrawRound = (p1coins > 0) and winnable(N1-p1coins, N2-p1coins, K1, K2)
    if not winByLoseRound and not winByWinRound and not winByDrawRound:
        return False
    bestTurns = 1e60
    if winByLoseRound:
        bestTurns = winByLoseRound + 1
        p2coins = 0
    if winByWinRound and winByWinRound < bestTurns:
        bestTurns = winByWinRound + 1
        p2coins = p1coins + 1
    if winByDrawRound and winByDrawRound < bestTurns:
        bestTurns = winByDrawRound + 1
        p2coins = p1coins
    return bestTurns, p2coins

def bestMovePlayer1(N1, N2, K1, K2):
    bestTurns = 0 # lose in maximum amount of turns
    bestCoins = 0
    for p1coins in range(N1+1):
        result = bestMovePlayer2(N1, N2, K1, K2, p1coins)
        if result == False:
            return False # we win. unplanned for.
        if result[0] > bestTurns:
            bestTurns = result[0]
            bestCoins = p1coins
    return bestTurns, bestCoins

def winnable(N1, N2, K1, K2):
    if (N1, N2, K1, K2) in winnable_cache:
        return winnable_cache[(N1, N2, K1, K2)]
    if K1 == 0:
        winnable_cache[(N1, N2, K1, K2)] = False
        return False
    if K2 == 0:
        winnable_cache[(N1, N2, K1, K2)] = 1
        return 1
    result = bestMovePlayer1(N1, N2, K1, K2)
    if result == False:
        winnable_cache[(N1, N2, K1, K2)] = False
        return False
    turns, coins = result
    winnable_cache[(N1, N2, K1, K2)] = turns
    return turns

def solveProblem(N, K):
    for n in range(1, N+1):
        for k in range(1, K+1):
            winnable(n, n, k, k)
    return winnable(N, N, K, K)

def fillTable(N, K):
    print("N/K", end="\t")
    for k in range(1, K+1):
        print(k, end="\t")
    print()
    for n in range(1, N+1):
        print(n, end="\t")
        for k in range(1, K+1):
            w = winnable(n, n, k, k)
            if w == False:
                print("-1", end="\t")
            else:
                print(w-1, end="\t")
        print()

def playGame(N, K):
    solveProblem(N, K)
    N1, N2, K1, K2 = N, N, K, K
    while True:
        move1 = bestMovePlayer1(N1, N2, K1, K2)
        if move1 == False:
            print("Player 1 wins or draws")
            break
        turns, p1coins = move1
        move2 = bestMovePlayer2(N1, N2, K1, K2, p1coins)
        if move2 == False:
            print("Hmm. This shouldn't happen.")
            break
        turns, p2coins = move2
        print("Player 1 plays", p1coins, "and Player 2 plays", p2coins)
        N1 -= p1coins
        N2 -= p2coins
        if p1coins > p2coins:
            K1 -= 1
        elif p2coins > p1coins:
            K2 -= 1
        print(N1, N2, K1, K2)
        if K1 == 0:
            print("Player 1 wins")
            break
        if K2 == 0:
            print("Player 2 wins")
            break