class ChessGame:
    def __init__(self):
        self.board = self.create_board()
        self.current_player = 'white'
        self.move_history = []
        self.en_passant_target = None
        self.castling_rights = {'white': {'king_side': True, 'queen_side': True},
                               'black': {'king_side': True, 'queen_side': True}}
        self.game_over = False
        self.result = None

    def create_board(self):
        # Create empty board
        board = [['.' for _ in range(8)] for _ in range(8)]
        
        # Set up pawns
        for col in range(8):
            board[1][col] = 'p'  # Black pawns
            board[6][col] = 'P'  # White pawns
        
        # Set up other pieces
        back_row = ['r', 'n', 'b', 'q', 'k', 'b', 'n', 'r']
        for col, piece in enumerate(back_row):
            board[0][col] = piece  # Black pieces
            board[7][col] = piece.upper()  # White pieces
            
        return board

    def print_board(self):
        print("  a b c d e f g h")
        for i in range(8):
            print(8-i, end=' ')
            for j in range(8):
                piece = self.board[i][j]
                if piece == '.':
                    print('.', end=' ')
                else:
                    print(piece, end=' ')
            print(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 get_piece_color(self, piece):
        if piece == '.':
            return None
        return 'white' if piece.isupper() else 'black'

    def is_valid_move(self, start, end):
        start_row, start_col = start
        end_row, end_col = end
        piece = self.board[start_row][start_col]
        target = self.board[end_row][end_col]
        
        # Check if moving own piece
        if self.get_piece_color(piece) != self.current_player:
            return False
            
        # Check if capturing own piece
        if self.get_piece_color(target) == self.current_player:
            return False
            
        # Piece-specific movement rules
        piece_type = piece.lower()
        delta_row = end_row - start_row
        delta_col = end_col - start_col
        
        # Pawn moves
        if piece_type == 'p':
            direction = -1 if self.current_player == 'white' else 1
            start_row_check = 6 if self.current_player == 'white' else 1
            
            # Forward move
            if delta_col == 0 and target == '.':
                # Single move
                if delta_row == direction:
                    return True
                # Double move from starting position
                if delta_row == 2 * direction and start_row == start_row_check:
                    # Check if path is clear
                    mid_row = start_row + direction
                    if self.board[mid_row][start_col] == '.':
                        return True
            # Capture
            elif abs(delta_col) == 1 and delta_row == direction:
                # Regular capture
                if target != '.' and self.get_piece_color(target) != self.current_player:
                    return True
                # En passant
                if target == '.' and (end_row, end_col) == self.en_passant_target:
                    return True
            return False
            
        # Knight moves
        if piece_type == 'n':
            return (abs(delta_row) == 2 and abs(delta_col) == 1) or \
                   (abs(delta_row) == 1 and abs(delta_col) == 2)
                   
        # Bishop moves
        if piece_type == 'b':
            if abs(delta_row) != abs(delta_col):
                return False
            return self.is_path_clear(start, end)
            
        # Rook moves
        if piece_type == 'r':
            if delta_row != 0 and delta_col != 0:
                return False
            return self.is_path_clear(start, end)
            
        # Queen moves
        if piece_type == 'q':
            if delta_row != 0 and delta_col != 0 and abs(delta_row) != abs(delta_col):
                return False
            return self.is_path_clear(start, end)
            
        # King moves
        if piece_type == 'k':
            # Regular king move
            if abs(delta_row) <= 1 and abs(delta_col) <= 1:
                return True
            # Castling
            if delta_row == 0 and abs(delta_col) == 2 and start_row in [0, 7]:
                # King must not have moved
                if not self.castling_rights[self.current_player]['king_side'] and \
                   not self.castling_rights[self.current_player]['queen_side']:
                    return False
                    
                # Check castling direction
                if delta_col == 2:  # King side
                    if not self.castling_rights[self.current_player]['king_side']:
                        return False
                    # Check squares between king and rook
                    if self.board[start_row][5] != '.' or self.board[start_row][6] != '.':
                        return False
                    # Check if king passes through check
                    if self.is_in_check(self.current_player, (start_row, start_col)) or \
                       self.is_in_check(self.current_player, (start_row, 5)) or \
                       self.is_in_check(self.current_player, (start_row, 6)):
                        return False
                elif delta_col == -2:  # Queen side
                    if not self.castling_rights[self.current_player]['queen_side']:
                        return False
                    # Check squares between king and rook
                    if self.board[start_row][1] != '.' or self.board[start_row][2] != '.' or \
                       self.board[start_row][3] != '.':
                        return False
                    # Check if king passes through check
                    if self.is_in_check(self.current_player, (start_row, start_col)) or \
                       self.is_in_check(self.current_player, (start_row, 2)) or \
                       self.is_in_check(self.current_player, (start_row, 3)):
                        return False
                return True
            return False
            
        return False

    def is_path_clear(self, start, end):
        start_row, start_col = start
        end_row, end_col = end
        delta_row = end_row - start_row
        delta_col = end_col - start_col
        
        step_row = 0 if delta_row == 0 else (1 if delta_row > 0 else -1)
        step_col = 0 if delta_col == 0 else (1 if delta_col > 0 else -1)
        
        steps = max(abs(delta_row), abs(delta_col))
        for i in range(1, steps):
            row = start_row + i * step_row
            col = start_col + i * step_col
            if self.board[row][col] != '.':
                return False
        return True

    def make_move(self, start, end):
        start_row, start_col = start
        end_row, end_col = end
        piece = self.board[start_row][start_col]
        target = self.board[end_row][end_col]
        
        # Save state for undo
        original_state = {
            'board': [row[:] for row in self.board],
            'en_passant_target': self.en_passant_target,
            'castling_rights': dict(self.castling_rights)
        }
        
        # Handle en passant capture
        if piece.lower() == 'p' and (end_row, end_col) == self.en_passant_target:
            # Remove the captured pawn
            capture_row = start_row
            self.board[capture_row][end_col] = '.'
        
        # Move the piece
        self.board[end_row][end_col] = piece
        self.board[start_row][start_col] = '.'
        
        # Handle pawn promotion (auto-promote to queen)
        if piece.lower() == 'p' and end_row in [0, 7]:
            color = 'white' if piece.isupper() else 'black'
            self.board[end_row][end_col] = 'Q' if color == 'white' else 'q'
        
        # Handle castling
        if piece.lower() == 'k' and abs(end_col - start_col) == 2:
            # King side castling
            if end_col - start_col == 2:
                rook_start_col, rook_end_col = 7, 5
            # Queen side castling
            else:
                rook_start_col, rook_end_col = 0, 3
            rook = self.board[end_row][rook_start_col]
            self.board[end_row][rook_end_col] = rook
            self.board[end_row][rook_start_col] = '.'
            
        # Update castling rights
        if piece.lower() == 'k':
            self.castling_rights[self.current_player]['king_side'] = False
            self.castling_rights[self.current_player]['queen_side'] = False
        if piece.lower() == 'r':
            if start_col == 0:  # Queen side rook
                self.castling_rights[self.current_player]['queen_side'] = False
            elif start_col == 7:  # King side rook
                self.castling_rights[self.current_player]['king_side'] = False
                
        # Set en passant target
        self.en_passant_target = None
        if piece.lower() == 'p' and abs(end_row - start_row) == 2:
            self.en_passant_target = ((start_row + end_row) // 2, start_col)
            
        # Check if move leaves king in check
        if self.is_in_check(self.current_player):
            # Undo move
            self.board = original_state['board']
            self.en_passant_target = original_state['en_passant_target']
            self.castling_rights = original_state['castling_rights']
            return False
            
        # Record move
        self.move_history.append((start, end))
        return True

    def is_in_check(self, player, king_pos=None):
        if king_pos is None:
            king_pos = self.find_king(player)
            if king_pos is None:
                return False
                
        king_row, king_col = king_pos
        opponent = 'black' if player == 'white' else 'white'
        
        # Check all opponent pieces to see if any can attack the king
        for row in range(8):
            for col in range(8):
                piece = self.board[row][col]
                if piece != '.' and self.get_piece_color(piece) == opponent:
                    # Temporarily move opponent piece to king position to check if it can attack
                    original_piece = self.board[king_row][king_col]
                    self.board[king_row][king_col] = piece
                    self.board[row][col] = '.'
                    
                    # Check if this piece could attack the king from its current position
                    can_attack = self.is_valid_move_for_check((row, col), (king_row, king_col))
                    
                    # Restore board
                    self.board[row][col] = piece
                    self.board[king_row][king_col] = original_piece
                    
                    if can_attack:
                        return True
        return False

    def is_valid_move_for_check(self, start, end):
        # Simplified version of is_valid_move without checking for check
        start_row, start_col = start
        end_row, end_col = end
        piece = self.board[start_row][start_col]
        target = self.board[end_row][end_col]
        
        # Can't capture own piece
        if self.get_piece_color(target) == self.get_piece_color(piece) and target != '.':
            return False
            
        piece_type = piece.lower()
        delta_row = end_row - start_row
        delta_col = end_col - start_col
        
        # Pawn moves
        if piece_type == 'p':
            direction = -1 if self.get_piece_color(piece) == 'white' else 1
            start_row_check = 6 if self.get_piece_color(piece) == 'white' else 1
            
            # Forward move
            if delta_col == 0 and target == '.':
                if delta_row == direction:
                    return True
                if delta_row == 2 * direction and start_row == start_row_check:
                    mid_row = start_row + direction
                    if self.board[mid_row][start_col] == '.':
                        return True
            # Capture
            elif abs(delta_col) == 1 and delta_row == direction:
                if target != '.':
                    return True
                if (end_row, end_col) == self.en_passant_target:
                    return True
            return False
            
        # Knight moves
        if piece_type == 'n':
            return (abs(delta_row) == 2 and abs(delta_col) == 1) or \
                   (abs(delta_row) == 1 and abs(delta_col) == 2)
                   
        # Bishop moves
        if piece_type == 'b':
            if abs(delta_row) != abs(delta_col):
                return False
            return self.is_path_clear(start, end)
            
        # Rook moves
        if piece_type == 'r':
            if delta_row != 0 and delta_col != 0:
                return False
            return self.is_path_clear(start, end)
            
        # Queen moves
        if piece_type == 'q':
            if delta_row != 0 and delta_col != 0 and abs(delta_row) != abs(delta_col):
                return False
            return self.is_path_clear(start, end)
            
        # King moves
        if piece_type == 'k':
            return abs(delta_row) <= 1 and abs(delta_col) <= 1
            
        return False

    def find_king(self, player):
        king_piece = 'K' if player == 'white' else 'k'
        for row in range(8):
            for col in range(8):
                if self.board[row][col] == king_piece:
                    return (row, col)
        return None

    def has_legal_moves(self, player):
        for start_row in range(8):
            for start_col in range(8):
                piece = self.board[start_row][start_col]
                if piece != '.' and self.get_piece_color(piece) == player:
                    for end_row in range(8):
                        for end_col in range(8):
                            if self.is_valid_move((start_row, start_col), (end_row, end_col)):
                                # Try the move
                                original_board = [row[:] for row in self.board]
                                original_en_passant = self.en_passant_target
                                original_castling = dict(self.castling_rights)
                                
                                if self.make_move((start_row, start_col), (end_row, end_col)):
                                    # Move is legal
                                    self.board = original_board
                                    self.en_passant_target = original_en_passant
                                    self.castling_rights = original_castling
                                    return True
                                else:
                                    # Restore board state
                                    self.board = original_board
                                    self.en_passant_target = original_en_passant
                                    self.castling_rights = original_castling
        return False

    def is_checkmate(self, player):
        return self.is_in_check(player) and not self.has_legal_moves(player)

    def is_stalemate(self, player):
        return not self.is_in_check(player) and not self.has_legal_moves(player)

    def play(self):
        while not self.game_over:
            self.print_board()
            
            # Check for checkmate or stalemate
            if self.is_checkmate(self.current_player):
                winner = 'black' if self.current_player == 'white' else 'white'
                print(f"Checkmate! {winner.capitalize()} wins!")
                self.game_over = True
                break
            elif self.is_stalemate(self.current_player):
                print("Stalemate! Game is a draw.")
                self.game_over = True
                break
                
            # Check for check
            if self.is_in_check(self.current_player):
                print(f"{self.current_player.capitalize()} is in check!")
                
            # Get move
            player_name = "White" if self.current_player == 'white' else "Black"
            move_str = input(f"{player_name}'s move (e.g., 'e2 e4'): ").strip()
            
            if move_str.lower() == 'quit':
                print("Game resigned.")
                self.game_over = True
                break
                
            parts = move_str.split()
            if len(parts) != 2:
                print("Invalid input. Please use format 'e2 e4'.")
                continue
                
            start_pos, end_pos = parts
            start = self.parse_position(start_pos)
            end = self.parse_position(end_pos)
            
            if start is None or end is None:
                print("Invalid position. Use format like 'e2 e4'.")
                continue
                
            if not self.is_valid_move(start, end):
                print("Invalid move.")
                continue
                
            if not self.make_move(start, end):
                print("Move would leave king in check.")
                continue
                
            # Switch players
            self.current_player = 'black' if self.current_player == 'white' else 'white'

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