class Checkers:
    def __init__(self):
        self.board = [['.' for _ in range(8)] for _ in range(8)]
        self.setup_board()
        self.current_player = 'b'  # black starts
        self.game_over = False
        self.winner = None

    def setup_board(self):
        for row in range(3):
            for col in range(8):
                if (row + col) % 2 == 1:
                    self.board[row][col] = 'b'
        for row in range(5, 8):
            for col in range(8):
                if (row + col) % 2 == 1:
                    self.board[row][col] = 'r'

    def print_board(self):
        print("  a b c d e f g h")
        for i, row in enumerate(self.board):
            print(f"{8-i} ", end="")
            for piece in row:
                print(piece, end=" ")
            print()
        print()

    def parse_move(self, move_str):
        if len(move_str) != 5 or move_str[2] != ' ':
            return None
        from_col, from_row = move_str[0], move_str[1]
        to_col, to_row = move_str[3], move_str[4]
        if not (from_col.islower() and from_row.isdigit() and to_col.islower() and to_row.isdigit()):
            return None
        from_col = ord(from_col) - ord('a')
        from_row = 8 - int(from_row)
        to_col = ord(to_col) - ord('a')
        to_row = 8 - int(to_row)
        if not (0 <= from_col < 8 and 0 <= from_row < 8 and 0 <= to_col < 8 and 0 <= to_row < 8):
            return None
        return (from_row, from_col, to_row, to_col)

    def is_valid_move(self, move):
        from_row, from_col, to_row, to_col = move
        piece = self.board[from_row][from_col]
        if piece == '.':
            return False
        if (piece.islower() and piece != self.current_player) or (piece.isupper() and piece.lower() != self.current_player):
            return False
        if self.board[to_row][to_col] != '.':
            return False
        row_diff = to_row - from_row
        col_diff = abs(to_col - from_col)
        if col_diff != 1:
            return False
        if piece.islower():
            if piece == 'b' and row_diff != 1:
                return False
            if piece == 'r' and row_diff != -1:
                return False
        else:  # king
            if abs(row_diff) != 1:
                return False
        return True

    def is_valid_capture(self, move):
        from_row, from_col, to_row, to_col = move
        piece = self.board[from_row][from_col]
        if piece == '.':
            return False
        if (piece.islower() and piece != self.current_player) or (piece.isupper() and piece.lower() != self.current_player):
            return False
        if self.board[to_row][to_col] != '.':
            return False
        row_diff = to_row - from_row
        col_diff = to_col - from_col
        if abs(row_diff) != 2 or abs(col_diff) != 2:
            return False
        mid_row = (from_row + to_row) // 2
        mid_col = (from_col + to_col) // 2
        mid_piece = self.board[mid_row][mid_col]
        if mid_piece == '.' or (mid_piece.islower() and mid_piece == self.current_player) or (mid_piece.isupper() and mid_piece.lower() == self.current_player):
            return False
        if piece.islower():
            if piece == 'b' and row_diff != 2:
                return False
            if piece == 'r' and row_diff != -2:
                return False
        return True

    def make_move(self, move):
        from_row, from_col, to_row, to_col = move
        piece = self.board[from_row][from_col]
        self.board[from_row][from_col] = '.'
        self.board[to_row][to_col] = piece
        if abs(to_row - from_row) == 2:  # capture
            mid_row = (from_row + to_row) // 2
            mid_col = (from_col + to_col) // 2
            self.board[mid_row][mid_col] = '.'
        if (piece == 'b' and to_row == 0) or (piece == 'r' and to_row == 7):
            self.board[to_row][to_col] = piece.upper()
        self.current_player = 'r' if self.current_player == 'b' else 'b'

    def has_legal_moves(self, player):
        for row in range(8):
            for col in range(8):
                piece = self.board[row][col]
                if piece == '.':
                    continue
                if (piece.islower() and piece != player) or (piece.isupper() and piece.lower() != player):
                    continue
                # check regular moves
                for dr, dc in [(-1, -1), (-1, 1), (1, -1), (1, 1)]:
                    nr, nc = row + dr, col + dc
                    if 0 <= nr < 8 and 0 <= nc < 8 and self.board[nr][nc] == '.':
                        if piece.islower():
                            if (piece == 'b' and dr == 1) or (piece == 'r' and dr == -1):
                                return True
                        else:  # king
                            return True
                # check captures
                for dr, dc in [(-2, -2), (-2, 2), (2, -2), (2, 2)]:
                    nr, nc = row + dr, col + dc
                    if 0 <= nr < 8 and 0 <= nc < 8 and self.board[nr][nc] == '.':
                        mid_r, mid_c = row + dr//2, col + dc//2
                        mid_piece = self.board[mid_r][mid_c]
                        if mid_piece != '.' and ((mid_piece.islower() and mid_piece != player) or (mid_piece.isupper() and mid_piece.lower() != player)):
                            if piece.islower():
                                if (piece == 'b' and dr == 2) or (piece == 'r' and dr == -2):
                                    return True
                            else:  # king
                                return True
        return False

    def count_pieces(self, player):
        count = 0
        for row in range(8):
            for col in range(8):
                piece = self.board[row][col]
                if piece == '.':
                    continue
                if (piece.islower() and piece == player) or (piece.isupper() and piece.lower() == player):
                    count += 1
        return count

    def check_game_over(self):
        if not self.has_legal_moves('b'):
            self.game_over = True
            self.winner = 'r'
            return True
        if not self.has_legal_moves('r'):
            self.game_over = True
            self.winner = 'b'
            return True
        if self.count_pieces('b') == 0:
            self.game_over = True
            self.winner = 'r'
            return True
        if self.count_pieces('r') == 0:
            self.game_over = True
            self.winner = 'b'
            return True
        return False

    def play(self):
        print("Welcome to Checkers!")
        print("Enter moves in algebraic notation (e.g., b6 c5 or b6 d4 for capture).")
        print("Black (b) starts, Red (r) follows. Kings are uppercase (B, R).")
        print()
        while not self.game_over:
            self.print_board()
            print(f"{self.current_player.upper()}'s turn")
            move_str = input("Enter your move (from to): ").strip()
            move = self.parse_move(move_str)
            if move is None:
                print("Invalid move format. Use format like 'b6 c5' or 'b6 d4'.")
                continue
            if self.is_valid_capture(move):
                self.make_move(move)
            elif self.is_valid_move(move):
                self.make_move(move)
            else:
                print("Illegal move. Try again.")
                continue
            if self.check_game_over():
                break
        self.print_board()
        if self.winner == 'b':
            print("Black wins!")
        elif self.winner == 'r':
            print("Red wins!")
        else:
            print("Game over.")

if __name__ == "__main__":
    game = Checkers()
    game.play()