def normal_nim(s):
    # Here, the last player to move wins (last player to remove last stones)
    initial_xor_sum = 0
    for pile in s:
        initial_xor_sum ^= pile

    # In case the initial state is xor_sum equal to 0, any move player 1 makes will
    # change the xor_sum to not 0. As long as player 2 moves to make the xor_sum
    # back to 0, player 1 can never wins
    if initial_xor_sum == 0:
        return "Player 2"
    else:
        return "Player 1"


# Function to a find a winnable move in a nim-game
def move_to_zero_xor(s):
    xor_sum = 0
    for number in s:
        xor_sum ^= number

    if xor_sum == 0:
        return "XOR of all numbers is already 0"
    # Proof that there is always a move that makes the xor_sum from not 0 to 0
    # Let S be the xor of all numbers but the one I'll change, which is x.
    # S^x = xor_sum
    # S^x' = 0 =>  x' = S => x'^x = xor_sum => x^xor_sum = x'
    # To prove that always exist x' < x, just look for the highest bit in xor_sum
    # look for a number that has that bit as well, x' won't have. This way,
    # I can guarantee there will be a number that works and that x' < x.

    copy_xor_sum = xor_sum
    highest_bit = 0
    while copy_xor_sum > 1:
        copy_xor_sum = copy_xor_sum >> 1
        highest_bit += 1

    base_10 = 1 << highest_bit
    for number in s:
        if (number & base_10) == base_10:
            print(f"Move from number {number} to number {xor_sum ^ number}")


def misere_nim(s):
    # Although less obvious than normal nim, the logic is similar. But there is an edge-case
    # As long your next move will not change all columns to be 1, forcing oponent
    # into xor_sum = 0 is a winning move. If all columns are 1, odd columns is a
    # winning move to your oponent and even columns is winning move to you
    xor_sum = 0
    columns_one = 0
    exist_non_one_column = False
    for number in s:
        if number == 1:
            columns_one += 1
        else:
            exist_non_one_column = True
        xor_sum ^= number

    if exist_non_one_column:
        if xor_sum==0:
            return "Second"
        else:
            return "First"
    else:
        if columns_one%2==0:
            return "First"
        else:
            return "Second"