import sys

class Checkers:
    def __init__(self):
        # Board: 'b' = black man, 'B' = black king, 'w' = white man, 'W' = white king, '.' = empty
        # Black moves 'down' (increasing row), White moves 'up' (decreasing row)
        self.board = [['.' for _ in range(8)] for _ in range(8)]
        self.turn = 'w'  # White starts
        self.setup_board()

    def setup_board(self):
        for r in range(8):
            for c in range(8):
                if (r + c) % 2 == 1:
                    if r < 3:
                        self.board[r][c] = 'b'
                    elif r > 4:
                        self.board[r][c] = 'w'

    def print_board(self):
        print("\n  a b c d e f g h")
        for r in range(8):
            row_str = f"{r+1} " + " ".join(self.board[r])
            print(row_str)
        print(f"\nTurn: {'White' if self.turn == 'w' else 'Black'}")

    def parse_coord(self, coord):
        # Convert 'b6' to (row, col)
        try:
            col = ord(coord[0]) - ord('a')
            row = int(coord[1:]) - 1
            if 0 <= col < 8 and 0 <= row < 8:
                return row, col
        except:
            pass
        return None

    def get_all_legal_moves(self, player):
        jumps = []
        slides = []
        
        for r in range(8):
            for c in range(8):
                piece = self.board[r][c]
                if piece.lower() != player:
                    continue
                
                is_king = piece.isupper()
                # Directions: (row_delta, col_delta)
                dirs = []
                if player == 'w' or is_king: dirs.append((-1, -1)); dirs.append((-1, 1))
                if player == 'b' or is_king: dirs.append((1, -1)); dirs.append((1, 1))

                for dr, dc in dirs:
                    # Check for jump
                    nr, nc = r + dr, c + dc
                    jr, jc = r + 2*dr, c + 2*dc
                    if 0 <= jr < 8 and 0 <= jc < 8:
                        mid_piece = self.board[nr][nc]
                        if mid_piece != '.' and mid_piece.lower() != player and self.board[jr][jc] == '.':
                            jumps.append(((r, c), (jr, jc), (nr, nc)))
                    
                    # Check for slide
                    if 0 <= nr < 8 and 0 <= nc < 8:
                        if self.board[nr][nc] == '.':
                            slides.append(((r, c), (nr, nc), None))
        
        # In checkers, if a jump is available, it must be taken
        return jumps if jumps else slides

    def move_piece(self, start, end, captured):
        r1, c1 = start
        r2, c2 = end
        piece = self.board[r1][c1]
        
        # Move piece
        self.board[r2][c2] = piece
        self.board[r1][c1] = '.'
        
        # Remove captured piece
        if captured:
            cr, cc = captured
            self.board[cr][cc] = '.'
            
        # Promotion
        if piece == 'w' and r2 == 0:
            self.board[r2][c2] = 'W'
        elif piece == 'b' and r2 == 7:
            self.board[r2][c2] = 'B'

    def play(self):
        while True:
            self.print_board()
            legal_moves = self.get_all_legal_moves(self.turn)
            
            if not legal_moves:
                winner = 'Black' if self.turn == 'w' else 'White'
                print(f"No moves left for {self.turn}. {winner} wins!")
                break
            
            try:
                user_input = input("Enter move (from to, e.g. b6 c5): ").split()
                if len(user_input) != 2:
                    print("Invalid input format.")
                    continue
                
                start = self.parse_coord(user_input[0])
                end = self.parse_coord(user_input[1])
                
                if not start or not end:
                    print("Invalid coordinates.")
                    continue
                
                # Check if move is in legal_moves
                move_found = None
                for s, e, c in legal_moves:
                    if s == start and e == end:
                        move_found = (s, e, c)
                        break
                
                if move_found:
                    self.move_piece(move_found[0], move_found[1], move_found[2])
                    # Handle multi-jump
                    if move_found[2]: # It was a jump
                        # Check if the same piece can jump again
                        r2, c2 = move_found[1]
                        # Temporarily switch turn to check for further jumps for the same piece
                        further_jumps = []
                        # We only check jumps for the piece that just moved
                        piece = self.board[r2][c2]
                        is_king = piece.isupper()
                        dirs = []
                        if self.turn == 'w' or is_king: dirs.append((-1, -1)); dirs.append((-1, 1))
                        if self.turn == 'b' or is_king: dirs.append((1, -1)); dirs.append((1, 1))
                        for dr, dc in dirs:
                            nr, nc = r2 + dr, c2 + dc
                            jr, jc = r2 + 2*dr, c2 + 2*dc
                            if 0 <= jr < 8 and 0 <= jc < 8:
                                mid = self.board[nr][nc]
                                if mid != '.' and mid.lower() != self.turn and self.board[jr][jc] == '.':
                                    further_jumps.append(((r2, c2), (jr, jc), (nr, nc)))
                        
                        if further_jumps:
                            print("Multi-jump available!")
                            # Force the player to continue jumping with the same piece
                            while further_jumps:
                                self.print_board()
                                next_input = input("Continue jump (to coord, e.g. d4): ").split()
                                if len(next_input) != 1:
                                    print("Invalid input.")
                                    continue
                                end_coord = self.parse_coord(next_input[0])
                                if not end_coord:
                                    print("Invalid coordinates.")
                                    continue
                                
                                jump_found = None
                                for s, e, c in further_jumps:
                                    if e == end_coord:
                                        jump_found = (s, e, c)
                                        break
                                
                                if jump_found:
                                    self.move_piece(jump_found[0], jump_found[1], jump_found[2])
                                    # Update further_jumps
                                    further_jumps = []
                                    r3, c3 = jump_found[1]
                                    piece = self.board[r3][c3]
                                    is_king = piece.isupper()
                                    dirs = []
                                    if self.turn == 'w' or is_king: dirs.append((-1, -1)); dirs.append((-1, 1))
                                    if self.turn == 'b' or is_king: dirs.append((1, -1)); dirs.append((1, 1))
                                    for dr, dc in dirs:
                                        nr, nc = r3 + dr, c3 + dc
                                        jr, jc = r3 + 2*dr, c3 + 2*dc
                                        if 0 <= jr < 8 and 0 <= jc < 8:
                                            mid = self.board[nr][nc]
                                            if mid != '.' and mid.lower() != self.turn and self.board[jr][jc] == '.':
                                                further_jumps.append(((r3, c3), (jr, jc), (nr, nc)))
                                else:
                                    print("Invalid jump.")
                                else:
                                    break
                            
                    self.turn = 'b' if self.turn == 'w' else 'w'
                else:
                    print("Illegal move.")
            except Exception as e:
                print(f"Error: {e}")

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