import sys

def print_board(board):
    # Print rows from 8 to 1
    for row in range(7, -1, -1):
        row_str = str(row + 1) + " "
        for col in range(8):
            row_str += board[row][col] + " "
        print(row_str)
    print("  a b c d e f g h")

def algebraic_to_coords(square):
    col = ord(square[0]) - ord('a')
    row = 8 - int(square[1])
    return row, col

def get_legal_moves(board, player):
    moves = []
    for row in range(8):
        for col in range(8):
            piece = board[row][col]
            if piece == '.':
                continue
            if player == 'red' and piece in ['r', 'R']:
                if piece == 'r':
                    directions = [(1, -1), (1, 1)]
                else:
                    directions = [(-1, -1), (-1, 1), (1, -1), (1, 1)]
                for dr, dc in directions:
                    new_row, new_col = row + dr, col + dc
                    if 0 <= new_row < 8 and 0 <= new_col < 8:
                        if board[new_row][new_col] == '.':
                            moves.append((row, col, new_row, new_col))
                for dr, dc in directions:
                    mid_row, mid_col = row + dr, col + dc
                    new_row, new_col = row + 2 * dr, col + 2 * dc
                    if 0 <= new_row < 8 and 0 <= new_col < 8:
                        if board[mid_row][mid_col] in ['w', 'W'] and board[new_row][new_col] == '.':
                            moves.append((row, col, new_row, new_col))
            elif player == 'white' and piece in ['w', 'W']:
                if piece == 'w':
                    directions = [(-1, -1), (-1, 1)]
                else:
                    directions = [(-1, -1), (-1, 1), (1, -1), (1, 1)]
                for dr, dc in directions:
                    new_row, new_col = row + dr, col + dc
                    if 0 <= new_row < 8 and 0 <= new_col < 8:
                        if board[new_row][new_col] == '.':
                            moves.append((row, col, new_row, new_col))
                for dr, dc in directions:
                    mid_row, mid_col = row + dr, col + dc
                    new_row, new_col = row + 2 * dr, col + 2 * dc
                    if 0 <= new_row < 8 and 0 <= new_col < 8:
                        if board[mid_row][mid_col] in ['r', 'R'] and board[new_row][new_col] == '.':
                            moves.append((row, col, new_row, new_col))
    return moves

def make_move(board, move, player):
    from_row, from_col, to_row, to_col = move
    piece = board[from_row][from_col]
    board[to_row][to_col] = piece
    board[from_row][from_col] = '.'

    if abs(to_row - from_row) == 2:
        mid_row = (from_row + to_row) // 2
        mid_col = (from_col + to_col) // 2
        board[mid_row][mid_col] = '.'

    if player == 'red' and to_row == 7 and piece == 'r':
        board[to_row][to_col] = 'R'
    elif player == 'white' and to_row == 0 and piece == 'w':
        board[to_row][to_col] = 'W'

def game_over(board):
    red_pieces = 0
    white_pieces = 0
    for row in range(8):
        for col in range(8):
            piece = board[row][col]
            if piece in ['r', 'R']:
                red_pieces += 1
            elif piece in ['w', 'W']:
                white_pieces += 1

    if red_pieces == 0:
        return True, 'white'
    if white_pieces == 0:
        return True, 'red'

    red_moves = get_legal_moves(board, 'red')
    white_moves = get_legal_moves(board, 'white')

    if len(red_moves) == 0:
        return True, 'white'
    if len(white_moves) == 0:
        return True, 'red'

    return False, None

def main():
    board = [['.' for _ in range(8)] for _ in range(8)]
    for row in range(8):
        for col in range(8):
            if (row + col) % 2 == 1:
                if row < 3:
                    board[row][col] = 'r'
                elif row > 4:
                    board[row][col] = 'w'
                else:
                    board[row][col] = '.'
            else:
                board[row][col] = '.'

    current_player = 'red'

    while True:
        print_board(board)
        is_over, winner = game_over(board)
        if is_over:
            if winner == 'red':
                print("Red wins!")
            else:
                print("White wins!")
            break

        legal_moves = get_legal_moves(board, current_player)
        if not legal_moves:
            if current_player == 'red':
                print("White wins! (Red has no moves)")
            else:
                print("Red wins! (White has no moves)")
            break

        if current_player == 'red':
            move_str = input("Red's move (e.g., b6 c5): ").strip()
        else:
            move_str = input("White's move (e.g., b6 c5): ").strip()

        if not move_str:
            continue

        parts = move_str.split()
        if len(parts) != 2:
            print("Invalid move format. Use 'from to', e.g., b6 c5")
            continue

        from_square, to_square = parts

        try:
            from_row, from_col = algebraic_to_coords(from_square)
            to_row, to_col = algebraic_to_coords(to_square)
        except:
            print("Invalid square notation. Use column letter and row number, e.g., b6")
            continue

        piece = board[from_row][from_col]
        if current_player == 'red' and piece not in ['r', 'R']:
            print("No red piece at that square.")
            continue
        if current_player == 'white' and piece not in ['w', 'W']:
            print("No white piece at that square.")
            continue

        move = (from_row, from_col, to_row, to_col)
        if move not in legal_moves:
            print("Illegal move.")
            continue

        make_move(board, move, current_player)

        if current_player == 'red':
            current_player = 'white'
        else:
            current_player = 'red'

if __name__ == "__main__":
    main()