import sys

# Constants
EMPTY = '.'
BLACK = 'b'
WHITE = 'w'
BLACK_KING = 'B'
WHITE_KING = 'W'

# Board dimensions
ROWS = 8
COLS = 8

# Directions: (dr, dc) for moves
# For men: forward directions depend on player
# For kings: all four diagonals
DIRECTIONS = [(-1, -1), (-1, 1), (1, -1), (1, 1)]

def create_board():
    """Initialize an 8x8 board with pieces in starting positions."""
    board = [[EMPTY] * COLS for _ in range(ROWS)]
    # Black pieces on rows 5,6,7 (ranks 3,2,1)
    for row in [5, 6, 7]:
        for col in range(COLS):
            if (row + col) % 2 == 1:  # dark square
                board[row][col] = BLACK
    # White pieces on rows 0,1,2 (ranks 8,7,6)
    for row in [0, 1, 2]:
        for col in range(COLS):
            if (row + col) % 2 == 1:
                board[row][col] = WHITE
    return board

def print_board(board):
    """Print the board with algebraic notation labels."""
    print("  a b c d e f g h")
    for row in range(ROWS):
        rank = ROWS - row
        print(rank, end=' ')
        for col in range(COLS):
            print(board[row][col], end=' ')
        print(rank)
    print("  a b c d e f g h")

def is_dark_square(row, col):
    """Return True if the square is dark (playable)."""
    return (row + col) % 2 == 1

def in_bounds(row, col):
    """Return True if coordinates are within the board."""
    return 0 <= row < ROWS and 0 <= col < COLS

def parse_move(move_str):
    """Parse a move string like 'b6 c5' into (from_row, from_col, to_row, to_col).
    Returns None if format is invalid."""
    parts = move_str.strip().split()
    if len(parts) != 2:
        return None
    try:
        from_sq = parts[0]
        to_sq = parts[1]
        if len(from_sq) != 2 or len(to_sq) != 2:
            return None
        from_file = from_sq[0]
        from_rank = int(from_sq[1])
        to_file = to_sq[0]
        to_rank = int(to_sq[1])
        if not ('a' <= from_file <= 'h' and 'a' <= to_file <= 'h'):
            return None
        if not (1 <= from_rank <= 8 and 1 <= to_rank <= 8):
            return None
        from_col = ord(from_file) - ord('a')
        from_row = ROWS - from_rank
        to_col = ord(to_file) - ord('a')
        to_row = ROWS - to_rank
        return (from_row, from_col, to_row, to_col)
    except (ValueError, IndexError):
        return None

def get_piece(board, row, col):
    """Return the piece at (row, col) or EMPTY."""
    return board[row][col]

def is_opponent(piece, player):
    """Return True if piece is an opponent of player."""
    if piece == EMPTY:
        return False
    if player == BLACK:
        return piece in (WHITE, WHITE_KING)
    else:  # player == WHITE
        return piece in (BLACK, BLACK_KING)

def is_own(piece, player):
    """Return True if piece belongs to player."""
    if piece == EMPTY:
        return False
    if player == BLACK:
        return piece in (BLACK, BLACK_KING)
    else:
        return piece in (WHITE, WHITE_KING)

def is_king(piece):
    """Return True if piece is a king."""
    return piece in (BLACK_KING, WHITE_KING)

def get_forward_directions(player):
    """Return list of (dr, dc) for forward moves for a man of given player."""
    if player == BLACK:
        return [(1, -1), (1, 1)]  # black moves down (increasing row)
    else:  # WHITE
        return [(-1, -1), (-1, 1)]  # white moves up (decreasing row)

def get_all_directions():
    """Return all four diagonal directions."""
    return DIRECTIONS

def get_legal_moves(board, player):
    """Return a list of ((from_row, from_col), (to_row, to_col)) for all legal moves of player."""
    moves = []
    for row in range(ROWS):
        for col in range(COLS):
            piece = board[row][col]
            if not is_own(piece, player):
                continue
            # Determine possible directions
            if is_king(piece):
                directions = get_all_directions()
            else:
                directions = get_forward_directions(player)
            # Simple moves (one step)
            for dr, dc in directions:
                nr, nc = row + dr, col + dc
                if in_bounds(nr, nc) and is_dark_square(nr, nc) and board[nr][nc] == EMPTY:
                    moves.append(((row, col), (nr, nc)))
            # Captures (jump over opponent)
            for dr, dc in directions:
                mid_r, mid_c = row + dr, col + dc
                if not in_bounds(mid_r, mid_c) or not is_dark_square(mid_r, mid_c):
                    continue
                mid_piece = board[mid_r][mid_c]
                if not is_opponent(mid_piece, player):
                    continue
                land_r, land_c = row + 2*dr, col + 2*dc
                if in_bounds(land_r, land_c) and is_dark_square(land_r, land_c) and board[land_r][land_c] == EMPTY:
                    moves.append(((row, col), (land_r, land_c)))
    return moves

def has_legal_moves(board, player):
    """Return True if player has at least one legal move."""
    return len(get_legal_moves(board, player)) > 0

def execute_move(board, from_pos, to_pos):
    """Execute a move on the board. Returns True if a capture occurred."""
    fr, fc = from_pos
    tr, tc = to_pos
    piece = board[fr][fc]
    # Move piece
    board[tr][tc] = piece
    board[fr][fc] = EMPTY
    # Check for capture: if the move is a jump (distance 2)
    capture = False
    if abs(tr - fr) == 2:
        # Remove the jumped piece
        mid_r = (fr + tr) // 2
        mid_c = (fc + tc) // 2
        board[mid_r][mid_c] = EMPTY
        capture = True
    # Promotion
    if piece == BLACK and tr == 0:  # black reaches rank 8 (row 0)
        board[tr][tc] = BLACK_KING
    elif piece == WHITE and tr == 7:  # white reaches rank 1 (row 7)
        board[tr][tc] = WHITE_KING
    return capture

def count_pieces(board, player):
    """Count total pieces (men and kings) of a player."""
    count = 0
    for row in range(ROWS):
        for col in range(COLS):
            piece = board[row][col]
            if is_own(piece, player):
                count += 1
    return count

def main():
    board = create_board()
    current_player = BLACK  # black moves first
    while True:
        print_board(board)
        # Check if current player has any legal moves
        if not has_legal_moves(board, current_player):
            # Game over
            winner = WHITE if current_player == BLACK else BLACK
            print(f"Player {winner.upper()} wins! (No legal moves for {current_player.upper()})")
            break
        # Check if opponent has pieces (should be redundant but safe)
        opponent = WHITE if current_player == BLACK else BLACK
        if count_pieces(board, opponent) == 0:
            print(f"Player {current_player.upper()} wins! (Opponent has no pieces)")
            break
        # Prompt for move
        while True:
            move_str = input(f"Player {current_player.upper()}, enter your move (e.g., b6 c5): ")
            parsed = parse_move(move_str)
            if parsed is None:
                print("Invalid format. Use algebraic notation like 'b6 c5'.")
                continue
            fr, fc, tr, tc = parsed
            # Check that from square has own piece
            if not is_own(board[fr][fc], current_player):
                print("You don't have a piece there.")
                continue
            # Check that to square is empty and dark
            if not is_dark_square(tr, tc):
                print("Target square is not a playable dark square.")
                continue
            if board[tr][tc] != EMPTY:
                print("Target square is not empty.")
                continue
            # Check if the move is in the list of legal moves
            legal_moves = get_legal_moves(board, current_player)
            if ((fr, fc), (tr, tc)) not in legal_moves:
                print("That move is not legal.")
                continue
            # Execute move
            execute_move(board, (fr, fc), (tr, tc))
            break
        # Switch player
        current_player = opponent

if __name__ == "__main__":
    main()