class Draughts:
    def __init__(self):
        self.board = self.create_board()
        self.current_player = 'white'
        self.game_over = False
        self.winner = None

    def create_board(self):
        board = [['.' for _ in range(8)] for _ in range(8)]
        # Place black pieces (lowercase)
        for row in range(3):
            for col in range(8):
                if (row + col) % 2 == 1:
                    board[row][col] = 'b'
        # Place white pieces (uppercase)
        for row in range(5, 8):
            for col in range(8):
                if (row + col) % 2 == 1:
                    board[row][col] = 'w'
        return board

    def print_board(self):
        print("  a b c d e f g h")
        for i, row in enumerate(self.board):
            print(8 - i, ' '.join(row), 8 - i)
        print("  a b c d e f g h")

    def parse_position(self, pos):
        if len(pos) != 2:
            return None
        col_char, row_char = pos[0], pos[1]
        if col_char not in 'abcdefgh' or row_char not in '12345678':
            return None
        col = ord(col_char) - ord('a')
        row = 8 - int(row_char)
        return row, col

    def is_valid_position(self, row, col):
        return 0 <= row < 8 and 0 <= col < 8

    def is_player_piece(self, piece):
        if self.current_player == 'white':
            return piece in 'wW'
        else:
            return piece in 'bB'

    def is_enemy_piece(self, piece):
        if self.current_player == 'white':
            return piece in 'bB'
        else:
            return piece in 'wW'

    def is_king(self, piece):
        return piece in 'WB'

    def get_possible_moves(self, row, col):
        piece = self.board[row][col]
        moves = []
        if piece == '.' or not self.is_player_piece(piece):
            return moves

        # Directions: up-left, up-right, down-left, down-right
        directions = []
        if piece == 'w' or self.is_king(piece):  # White moves up
            directions.extend([(-1, -1), (-1, 1)])
        if piece == 'b' or self.is_king(piece):  # Black moves down
            directions.extend([(1, -1), (1, 1)])

        # Check regular moves
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            if self.is_valid_position(new_row, new_col) and self.board[new_row][new_col] == '.':
                moves.append((new_row, new_col))

        # Check captures
        capture_moves = self.get_capture_moves(row, col)
        if capture_moves:
            return capture_moves

        return moves

    def get_capture_moves(self, row, col):
        piece = self.board[row][col]
        captures = []
        if piece == '.' or not self.is_player_piece(piece):
            return captures

        # Directions for capture
        directions = []
        if piece == 'w' or self.is_king(piece):
            directions.extend([(-1, -1), (-1, 1)])
        if piece == 'b' or self.is_king(piece):
            directions.extend([(1, -1), (1, 1)])

        for dr, dc in directions:
            mid_row, mid_col = row + dr, col + dc
            end_row, end_col = row + 2*dr, col + 2*dc
            if (self.is_valid_position(mid_row, mid_col) and 
                self.is_valid_position(end_row, end_col) and
                self.is_enemy_piece(self.board[mid_row][mid_col]) and
                self.board[end_row][end_col] == '.'):
                captures.append((end_row, end_col, mid_row, mid_col))  # end_pos, captured_pos

        return captures

    def has_captures(self):
        for row in range(8):
            for col in range(8):
                piece = self.board[row][col]
                if self.is_player_piece(piece):
                    captures = self.get_capture_moves(row, col)
                    if captures:
                        return True
        return False

    def make_move(self, from_pos, to_pos):
        from_row, from_col = from_pos
        to_row, to_col = to_pos
        piece = self.board[from_row][from_col]
        
        # Check if it's a capture
        captures = self.get_capture_moves(from_row, from_col)
        is_capture = any(c[0] == to_row and c[1] == to_col for c in captures)
        
        # Move the piece
        self.board[to_row][to_col] = piece
        self.board[from_row][from_col] = '.'
        
        # Remove captured piece if it's a capture
        if is_capture:
            for c in captures:
                if c[0] == to_row and c[1] == to_col:
                    self.board[c[2]][c[3]] = '.'
                    break
        
        # Promote to king if reached the end
        if piece == 'w' and to_row == 0:
            self.board[to_row][to_col] = 'W'
        elif piece == 'b' and to_row == 7:
            self.board[to_row][to_col] = 'B'

    def get_all_possible_moves(self):
        moves = []
        must_capture = self.has_captures()
        
        for row in range(8):
            for col in range(8):
                piece = self.board[row][col]
                if self.is_player_piece(piece):
                    if must_capture:
                        captures = self.get_capture_moves(row, col)
                        for c in captures:
                            moves.append(((row, col), (c[0], c[1])))
                    elif not must_capture:
                        regular_moves = self.get_possible_moves(row, col)
                        for move in regular_moves:
                            if len(move) == 2:  # Regular move
                                moves.append(((row, col), move))
        return moves

    def is_game_over(self):
        white_pieces = sum(row.count('w') + row.count('W') for row in self.board)
        black_pieces = sum(row.count('b') + row.count('B') for row in self.board)
        
        if white_pieces == 0:
            self.winner = 'black'
            return True
        if black_pieces == 0:
            self.winner = 'white'
            return True
            
        # Check if current player has any moves
        moves = self.get_all_possible_moves()
        if not moves:
            self.winner = 'black' if self.current_player == 'white' else 'white'
            return True
            
        return False

    def switch_player(self):
        self.current_player = 'black' if self.current_player == 'white' else 'white'

    def play(self):
        while not self.game_over:
            self.print_board()
            print(f"{self.current_player.capitalize()}'s turn")
            
            moves = self.get_all_possible_moves()
            if not moves:
                self.game_over = True
                self.winner = 'black' if self.current_player == 'white' else 'white'
                break
                
            move_str = input("Enter move (e.g., 'b6 c5'): ").strip()
            if not move_str:
                continue
                
            parts = move_str.split()
            if len(parts) != 2:
                print("Invalid input. Please use format 'from to' (e.g., 'b6 c5')")
                continue
                
            from_pos_str, to_pos_str = parts
            from_pos = self.parse_position(from_pos_str)
            to_pos = self.parse_position(to_pos_str)
            
            if not from_pos or not to_pos:
                print("Invalid position. Use algebraic notation (e.g., 'b6 c5')")
                continue
                
            from_row, from_col = from_pos
            to_row, to_col = to_pos
            
            # Check if the piece belongs to current player
            if not self.is_player_piece(self.board[from_row][from_col]):
                print("That's not your piece!")
                continue
                
            # Check if move is valid
            valid_moves = self.get_all_possible_moves()
            move_valid = False
            for move in valid_moves:
                if move[0] == from_pos and move[1] == to_pos:
                    move_valid = True
                    break
                    
            if not move_valid:
                print("Invalid move!")
                continue
                
            # Make the move
            self.make_move(from_pos, to_pos)
            
            # Check for game over
            if self.is_game_over():
                self.game_over = True
                break
                
            # Switch player
            self.switch_player()
            
        # Game over
        self.print_board()
        if self.winner:
            print(f"Game over! {self.winner.capitalize()} wins!")
        else:
            print("Game over! It's a draw!")

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