import math
from concurrent.futures import ThreadPoolExecutor
from dataclasses import dataclass, replace
from pathlib import Path

from PIL import Image, ImageDraw

from .assets import save_temp_png
from .settings import BuildConfig, PAGES_DIR, PrintItem, ROOT, mm_to_px, worker_count


@dataclass
class CardPage:
    items: list[PrintItem | None]
    spaced: bool = False
    extras: list[tuple[PrintItem, tuple[int, int, int, int], int]] | None = None


def grid_capacity(config: BuildConfig) -> tuple[int, int]:
    page_w = mm_to_px(config.paper_mm[0], config.dpi)
    page_h = mm_to_px(config.paper_mm[1], config.dpi)
    margin = mm_to_px(config.margin_mm, config.dpi)
    card_w = mm_to_px(config.card_mm[0], config.dpi)
    card_h = mm_to_px(config.card_mm[1], config.dpi)
    oriented_w = card_h
    oriented_h = card_w
    cols = max(1, (page_w - 2 * margin) // oriented_w)
    rows = max(1, (page_h - 2 * margin) // oriented_h)
    return int(cols), int(rows)


def balanced_columns(items: list[PrintItem], column_count: int) -> list[list[PrintItem]]:
    if column_count <= 0 or not items:
        return []
    columns: list[list[PrintItem]] = [[] for _ in range(column_count)]
    for index, item in enumerate(items):
        columns[index % len(columns)].append(item)
    return columns


def column_height(column: list[PrintItem | None]) -> int:
    for index in range(len(column) - 1, -1, -1):
        if column[index] is not None:
            return index + 1
    return 0


def column_type(column: list[PrintItem | None]) -> str | None:
    for item in column:
        if item is not None:
            return item.image_type
    return None


def optimize_mixed_columns(columns: list[list[PrintItem | None]], rows: int) -> list[list[PrintItem | None]]:
    columns = [list(column) for column in columns]
    while True:
        heights = [column_height(column) for column in columns]
        if not heights:
            return columns
        current_max = max(heights)
        best_move = None
        best_height = current_max
        for donor_index, donor in enumerate(columns):
            donor_type = column_type(donor)
            donor_height = heights[donor_index]
            if donor_type is None or donor_height <= 1 or donor_height < current_max:
                continue
            moved_item = donor[donor_height - 1]
            if moved_item is None:
                continue
            for receiver_index, receiver in enumerate(columns):
                if receiver_index == donor_index:
                    continue
                receiver_type = column_type(receiver)
                receiver_height = heights[receiver_index]
                if receiver_type is None or receiver_type == donor_type:
                    continue
                insert_index = receiver_height + 1
                if insert_index >= rows:
                    continue
                candidate_heights = list(heights)
                candidate_heights[donor_index] = donor_height - 1
                candidate_heights[receiver_index] = insert_index + 1
                candidate_max = max(candidate_heights)
                if candidate_max < best_height:
                    best_height = candidate_max
                    best_move = (donor_index, receiver_index, donor_height - 1, insert_index, moved_item)
        if best_move is None:
            return columns
        donor_index, receiver_index, donor_slot, receiver_slot, moved_item = best_move
        columns[donor_index][donor_slot] = None
        while len(columns[receiver_index]) <= receiver_slot:
            columns[receiver_index].append(None)
        columns[receiver_index][receiver_slot] = moved_item


def page_from_columns(columns: list[list[PrintItem | None]], cols_per_page: int, rows: int) -> list[PrintItem | None]:
    page: list[PrintItem | None] = [None] * (cols_per_page * rows)
    for col_index, column in enumerate(columns[:cols_per_page]):
        for row_index, item in enumerate(column[:rows]):
            if item is not None:
                page[row_index * cols_per_page + col_index] = item
    return page


def full_pages_then_remainder(items: list[PrintItem], cols: int, rows: int) -> tuple[list[CardPage], list[PrintItem]]:
    per_page = cols * rows
    pages: list[CardPage] = []
    full_count = len(items) // per_page
    for page_index in range(full_count):
        start = page_index * per_page
        pages.append(CardPage(list(items[start : start + per_page])))
    return pages, items[full_count * per_page :]


def best_mixed_column_counts(front_count: int, back_count: int, cols: int, rows: int) -> tuple[int, int]:
    best_score: tuple[int, int, int] | None = None
    best_counts = (0, 0)
    for front_cols in range(cols + 1):
        back_cols = cols - front_cols
        if front_count and front_cols == 0:
            continue
        if back_count and back_cols == 0:
            continue
        if not front_count and front_cols:
            continue
        if not back_count and back_cols:
            continue
        front_placed = min(front_count, front_cols * rows) if front_cols else 0
        back_placed = min(back_count, back_cols * rows) if back_cols else 0
        if front_placed + back_placed <= 0:
            continue
        front_h = math.ceil(front_placed / front_cols) if front_cols else 0
        back_h = math.ceil(back_placed / back_cols) if back_cols else 0
        used_cols = (front_cols if front_placed else 0) + (back_cols if back_placed else 0)
        score = (front_placed + back_placed, -max(front_h, back_h), -used_cols)
        if best_score is None or score > best_score:
            best_score = score
            best_counts = (front_cols if front_placed else 0, back_cols if back_placed else 0)
    return best_counts


def pack_remainder_pages(front_items: list[PrintItem], back_items: list[PrintItem], cols: int, rows: int) -> list[CardPage]:
    pages: list[CardPage] = []
    fronts = list(front_items)
    backs = list(back_items)
    while fronts or backs:
        front_cols, back_cols = best_mixed_column_counts(len(fronts), len(backs), cols, rows)
        if front_cols + back_cols <= 0:
            break
        front_take = min(len(fronts), front_cols * rows)
        back_take = min(len(backs), back_cols * rows)
        page_columns = balanced_columns(fronts[:front_take], front_cols) + balanced_columns(backs[:back_take], back_cols)
        page_columns = optimize_mixed_columns(page_columns, rows)
        pages.append(CardPage(page_from_columns(page_columns, cols, rows)))
        fronts = fronts[front_take:]
        backs = backs[back_take:]
    return pages


def pack_cropped_standard_group(group_items: list[PrintItem], cols: int, rows: int) -> list[CardPage]:
    fronts = sorted((item for item in group_items if item.image_type != "back"), key=item_order_key)
    backs = sorted((item for item in group_items if item.image_type == "back"), key=item_order_key)
    front_pages, front_remainder = full_pages_then_remainder(fronts, cols, rows)
    back_pages, back_remainder = full_pages_then_remainder(backs, cols, rows)
    return front_pages + back_pages + pack_remainder_pages(front_remainder, back_remainder, cols, rows)


def is_character_item(item: PrintItem) -> bool:
    return item.group.startswith("character:")


def character_edge_compatible(rotation: int, side: str) -> bool:
    if rotation == 90:
        edge_by_side = {"left": "top", "right": "bottom", "top": "right", "bottom": "left"}
    else:
        edge_by_side = {"left": "bottom", "right": "top", "top": "left", "bottom": "right"}
    return edge_by_side[side] in {"top", "right"}


def item_edge_compatible(item: PrintItem, side: str, cols: int, index: int) -> bool:
    if not is_character_item(item):
        return True
    rotation = item.layout_rotation if item.layout_rotation is not None else (-90 if index % cols else 90)
    return character_edge_compatible(rotation, side)


def character_duplicate_key(item: PrintItem) -> str:
    return item.sort_label or item.label.lower()


def character_bottom_left_corner(index: int, rotation: int, cols: int) -> tuple[int, int]:
    row, col = divmod(index, cols)
    if rotation == 90:
        return row + 1, col + 1
    return row, col


def character_item_bottom_left_corner(item: PrintItem, index: int, cols: int) -> tuple[int, int]:
    rotation = item.layout_rotation if item.layout_rotation is not None else (-90 if index % cols else 90)
    return character_bottom_left_corner(index, rotation, cols)


def slot_corners(index: int, cols: int) -> set[tuple[int, int]]:
    row, col = divmod(index, cols)
    return {(row, col), (row, col + 1), (row + 1, col), (row + 1, col + 1)}


def character_bottom_left_corner_allowed(
    page: list[PrintItem | None],
    index: int,
    item: PrintItem,
    cols: int,
) -> bool:
    item_corners = slot_corners(index, cols)
    item_is_character = is_character_item(item)
    item_bl = character_item_bottom_left_corner(item, index, cols) if item_is_character else None
    item_key = character_duplicate_key(item) if item_is_character else None

    for placed_index, placed in enumerate(page):
        if placed is None:
            continue

        placed_corners = slot_corners(placed_index, cols)
        placed_is_character = is_character_item(placed)
        placed_bl = character_item_bottom_left_corner(placed, placed_index, cols) if placed_is_character else None
        placed_key = character_duplicate_key(placed) if placed_is_character else None

        if item_is_character and item_bl in placed_corners:
            if not (placed_is_character and placed_bl == item_bl and placed_key == item_key):
                return False

        if placed_is_character and placed_bl in item_corners:
            if not (item_is_character and item_bl == placed_bl and item_key == placed_key):
                return False

    return True


def neighboring_slots(index: int, cols: int, total: int) -> list[tuple[int, str, str]]:
    neighbors: list[tuple[int, str, str]] = []
    if index % cols:
        neighbors.append((index - 1, "left", "right"))
    if index % cols != cols - 1 and index + 1 < total:
        neighbors.append((index + 1, "right", "left"))
    if index >= cols:
        neighbors.append((index - cols, "top", "bottom"))
    if index + cols < total:
        neighbors.append((index + cols, "bottom", "top"))
    return neighbors


def can_place_item(page: list[PrintItem | None], index: int, item: PrintItem, cols: int) -> bool:
    if not character_bottom_left_corner_allowed(page, index, item, cols):
        return False

    for neighbor_index, item_side, neighbor_side in neighboring_slots(index, cols, len(page)):
        neighbor = page[neighbor_index]
        if neighbor is None:
            continue
        if not item_edge_compatible(item, item_side, cols, index):
            return False
        if not item_edge_compatible(neighbor, neighbor_side, cols, neighbor_index):
            return False
    return True


def character_pairs(items: list[PrintItem]) -> tuple[list[tuple[PrintItem, PrintItem]], list[PrintItem]]:
    by_key: dict[str, list[PrintItem]] = {}
    for item in items:
        by_key.setdefault(character_duplicate_key(item), []).append(item)

    pairs: list[tuple[PrintItem, PrintItem]] = []
    leftovers: list[PrintItem] = []
    for key in sorted(by_key):
        group = by_key[key]
        for i in range(0, len(group) - 1, 2):
            pairs.append((group[i], group[i + 1]))
        if len(group) % 2:
            leftovers.append(group[-1])
    return pairs, leftovers


def shared_character_corner_slots(page: list[PrintItem | None], cols: int) -> list[tuple[int, int]]:
    slots: list[tuple[int, int]] = []
    for nw_index, item in enumerate(page):
        if item is not None or nw_index % cols == cols - 1:
            continue
        se_index = nw_index + cols + 1
        if se_index >= len(page) or page[se_index] is not None:
            continue
        slots.append((nw_index, se_index))
    return slots


def fill_single_characters(
    page: list[PrintItem | None],
    character_items: list[PrintItem],
    cols: int,
) -> tuple[list[PrintItem | None], list[PrintItem]]:
    empty_indices = [index for index, item in enumerate(page) if item is None]
    best_page = list(page)
    best_count = 0

    def dfs(slot_pos: int, char_pos: int) -> None:
        nonlocal best_count, best_page
        if char_pos > best_count:
            best_count = char_pos
            best_page = list(page)
        if char_pos == len(character_items) or slot_pos == len(empty_indices):
            return
        if char_pos + (len(empty_indices) - slot_pos) <= best_count:
            return

        index = empty_indices[slot_pos]
        for rotation in (90, -90):
            item = replace(character_items[char_pos], layout_rotation=rotation)
            if can_place_item(page, index, item, cols):
                page[index] = item
                dfs(slot_pos + 1, char_pos + 1)
                page[index] = None
        dfs(slot_pos + 1, char_pos)

    dfs(0, 0)
    return best_page, character_items[best_count:]


def fill_page_with_characters(
    page: list[PrintItem | None],
    character_items: list[PrintItem],
    cols: int,
) -> tuple[list[PrintItem | None], list[PrintItem]]:
    pairs, leftovers = character_pairs(character_items)
    if not pairs:
        return fill_single_characters(page, character_items, cols)

    best_page = list(page)
    best_remaining = list(character_items)
    best_score = (-1, -1)

    def dfs(pair_pos: int, placed_pairs: int, unplaced: list[PrintItem]) -> None:
        nonlocal best_page, best_remaining, best_score
        remaining_pairs = len(pairs) - pair_pos
        max_possible_total = len(character_items)
        if max_possible_total < best_score[0]:
            return
        if max_possible_total == best_score[0] and placed_pairs + remaining_pairs <= best_score[1]:
            return

        if pair_pos == len(pairs):
            remaining_for_single_fill = sorted(leftovers + unplaced, key=item_order_key)
            candidate_page, candidate_remaining = fill_single_characters(list(page), remaining_for_single_fill, cols)
            total_placed = len(character_items) - len(candidate_remaining)
            score = (total_placed, placed_pairs)
            if score > best_score:
                best_score = score
                best_page = candidate_page
                best_remaining = candidate_remaining
            return

        first, second = pairs[pair_pos]
        for nw_index, se_index in shared_character_corner_slots(page, cols):
            nw_item = replace(first, layout_rotation=90)
            se_item = replace(second, layout_rotation=-90)
            if not can_place_item(page, nw_index, nw_item, cols):
                continue
            page[nw_index] = nw_item
            if can_place_item(page, se_index, se_item, cols):
                page[se_index] = se_item
                dfs(pair_pos + 1, placed_pairs + 1, unplaced)
                page[se_index] = None
            page[nw_index] = None

        dfs(pair_pos + 1, placed_pairs, unplaced + [first, second])

    dfs(0, 0, [])
    return best_page, best_remaining


def fill_bottom_rows_with_spaced_characters(
    pages: list[CardPage],
    character_items: list[PrintItem],
    config: BuildConfig,
) -> list[PrintItem]:
    if not character_items:
        return character_items

    cols, rows = grid_capacity(config)
    page_w = mm_to_px(config.paper_mm[0], config.dpi)
    page_h = mm_to_px(config.paper_mm[1], config.dpi)
    margin = mm_to_px(config.margin_mm, config.dpi)
    gap = mm_to_px(5.0, config.dpi)
    card_w = mm_to_px(config.card_mm[0], config.dpi)
    card_h = mm_to_px(config.card_mm[1], config.dpi)
    oriented_w, oriented_h = card_h, card_w
    y0 = margin
    remaining = list(character_items)

    for page in pages:
        if not remaining or page.spaced:
            continue
        first_empty_row = rows
        for row in range(rows - 1, -1, -1):
            row_items = page.items[row * cols : (row + 1) * cols]
            if any(item is not None for item in row_items):
                break
            first_empty_row = row
        empty_rows = rows - first_empty_row
        if empty_rows <= 0:
            continue

        area_left = margin
        area_top = y0 + first_empty_row * oriented_h
        area_w = page_w - 2 * margin
        area_h = page_h - margin - area_top
        if first_empty_row > 0:
            area_top += gap
            area_h -= gap
        layout_options = []
        for item_w, item_h, rotation in ((oriented_w, oriented_h, 90), (card_w, card_h, 0)):
            fit_cols = max(1, (area_w + gap) // (item_w + gap))
            fit_rows = max(0, (area_h + gap) // (item_h + gap))
            layout_options.append((fit_cols * fit_rows, fit_cols, fit_rows, item_w, item_h, rotation))
        capacity_slots, fit_cols, fit_rows, item_w, item_h, rotation = max(layout_options)
        capacity = min(len(remaining), capacity_slots)
        if capacity <= 0:
            continue

        place_x0 = area_left
        place_y0 = area_top
        extras = list(page.extras or [])
        for index in range(capacity):
            row, col = divmod(index, fit_cols)
            left = place_x0 + col * (item_w + gap)
            top = place_y0 + row * (item_h + gap)
            extras.append((remaining[index], (left, top, left + item_w, top + item_h), rotation))
        page.extras = extras
        remaining = remaining[capacity:]

    return fill_free_space_with_spaced_characters(pages, remaining, config)


def rects_conflict(rect: tuple[int, int, int, int], occupied: list[tuple[int, int, int, int]], gap: int) -> bool:
    left, top, right, bottom = rect
    for other_left, other_top, other_right, other_bottom in occupied:
        if left < other_right + gap and right > other_left - gap and top < other_bottom + gap and bottom > other_top - gap:
            return True
    return False


def row_band_compatible(rect: tuple[int, int, int, int], occupied: list[tuple[int, int, int, int]]) -> bool:
    left, top, right, bottom = rect
    width = right - left
    height = bottom - top
    for other_left, other_top, other_right, other_bottom in occupied:
        if top >= other_bottom or bottom <= other_top:
            continue
        if top != other_top or bottom != other_bottom:
            return False
        if width != other_right - other_left or height != other_bottom - other_top:
            return False
    return True


def pack_spaced_items_in_free_space(
    occupied: list[tuple[int, int, int, int]],
    items: list[PrintItem],
    config: BuildConfig,
) -> list[tuple[PrintItem, tuple[int, int, int, int], int]]:
    if not items:
        return []

    page_w = mm_to_px(config.paper_mm[0], config.dpi)
    page_h = mm_to_px(config.paper_mm[1], config.dpi)
    margin = mm_to_px(config.margin_mm, config.dpi)
    gap = mm_to_px(5.0, config.dpi)
    card_w = mm_to_px(config.card_mm[0], config.dpi)
    card_h = mm_to_px(config.card_mm[1], config.dpi)
    oriented_w, oriented_h = card_h, card_w
    orientations = ((oriented_w, oriented_h, 90), (card_w, card_h, 0))
    best: list[tuple[int, tuple[int, int, int, int], int]] = []
    seen: set[tuple[int, tuple[tuple[int, int, int, int], ...]]] = set()

    def normalized(rects: list[tuple[int, int, int, int]]) -> tuple[tuple[int, int, int, int], ...]:
        return tuple(sorted(rects))

    def candidates(rects: list[tuple[int, int, int, int]]) -> list[tuple[int, int, int, int, int]]:
        xs = {margin}
        ys = {margin}
        for left, top, right, bottom in rects:
            for item_w, item_h, _ in orientations:
                xs.add(right + gap)
                xs.add(left - gap - item_w)
                ys.add(bottom + gap)
                ys.add(top - gap - item_h)

        out: list[tuple[int, int, int, int, int]] = []
        for item_w, item_h, rotation in orientations:
            for top in sorted(ys):
                if top < margin or top + item_h > page_h - margin:
                    continue
                for left in sorted(xs):
                    if left < margin or left + item_w > page_w - margin:
                        continue
                    rect = (left, top, left + item_w, top + item_h)
                    if row_band_compatible(rect, rects) and not rects_conflict(rect, rects, gap):
                        out.append((*rect, rotation))
        return sorted(out, key=lambda value: (value[1], value[0], value[4]))

    def dfs(rects: list[tuple[int, int, int, int]], placements: list[tuple[tuple[int, int, int, int], int]]) -> bool:
        nonlocal best
        if len(placements) > len(best):
            best = list(placements)
            if len(best) == len(items):
                return True

        state = (len(placements), normalized(rects))
        if state in seen:
            return False
        seen.add(state)

        for left, top, right, bottom, rotation in candidates(rects):
            rect = (left, top, right, bottom)
            if dfs(rects + [rect], placements + [(rect, rotation)]):
                return True
        return False

    dfs(list(occupied), [])
    return [(items[index], rect, rotation) for index, (rect, rotation) in enumerate(best)]


def item_print_size(item: PrintItem, config: BuildConfig) -> tuple[int, int]:
    if item.path.exists():
        with Image.open(item.path) as img:
            return img.size
    return mm_to_px(config.card_mm[0], config.dpi), mm_to_px(config.card_mm[1], config.dpi)


def item_orientations(item: PrintItem, config: BuildConfig) -> list[tuple[int, int, int]]:
    width, height = item_print_size(item, config)
    if item.layout_rotation is not None:
        rotation = item.layout_rotation
        return [(height, width, rotation)] if abs(rotation) % 180 else [(width, height, rotation)]
    if width == height:
        return [(width, height, 0)]
    return [(width, height, 0), (height, width, 90)]


def loose_items_can_touch(items: list[PrintItem]) -> bool:
    if not items:
        return False
    if any(is_character_item(item) or item.group == "board" for item in items):
        return False
    groups = {item.group for item in items}
    image_types = {item.image_type for item in items}
    return len(groups) == 1 and len(image_types) == 1


def compatible_standard_items(left: PrintItem, right: PrintItem) -> bool:
    return (
        not is_character_item(left)
        and not is_character_item(right)
        and left.group != "board"
        and right.group != "board"
        and left.group == right.group
        and left.image_type == right.image_type
    )


def normalize_connected_standard_rotations(
    placements: list[tuple[PrintItem, tuple[int, int, int, int], int]],
) -> list[tuple[PrintItem, tuple[int, int, int, int], int]]:
    if not placements:
        return placements

    normalized = list(placements)
    by_band: dict[tuple[int, int], list[int]] = {}
    for index, (_, rect, _) in enumerate(normalized):
        by_band.setdefault((rect[1], rect[3]), []).append(index)

    for indices in by_band.values():
        indices.sort(key=lambda index: normalized[index][1][0])
        run: list[int] = []

        def flush() -> None:
            if len(run) < 2:
                return
            _, first_rect, _ = normalized[run[0]]
            landscape = first_rect[2] - first_rect[0] > first_rect[3] - first_rect[1]
            if not landscape:
                for run_index in run:
                    item, rect, _ = normalized[run_index]
                    normalized[run_index] = (item, rect, 0)
                return
            for offset, run_index in enumerate(run):
                item, rect, _ = normalized[run_index]
                normalized[run_index] = (item, rect, 90 if offset % 2 == 0 else -90)

        for index in indices:
            if not run:
                run = [index]
                continue
            previous_index = run[-1]
            previous_item, previous_rect, _ = normalized[previous_index]
            item, rect, _ = normalized[index]
            touches = previous_rect[2] == rect[0]
            if touches and compatible_standard_items(previous_item, item):
                run.append(index)
            else:
                flush()
                run = [index]
        flush()

    return normalized


def pack_loose_items_in_free_space(
    occupied: list[tuple[int, int, int, int]],
    items: list[PrintItem],
    config: BuildConfig,
) -> list[tuple[PrintItem, tuple[int, int, int, int], int]]:
    if not items:
        return []

    page_w = mm_to_px(config.paper_mm[0], config.dpi)
    page_h = mm_to_px(config.paper_mm[1], config.dpi)
    margin = mm_to_px(config.margin_mm, config.dpi)
    gap = mm_to_px(5.0, config.dpi)
    internal_gap = 0 if loose_items_can_touch(items) else gap
    orientations = [item_orientations(item, config) for item in items]
    placed_start = len(occupied)

    def gap_to_rect(rect_index: int) -> int:
        return internal_gap if rect_index >= placed_start else gap

    def rect_conflicts(rect: tuple[int, int, int, int], rects: list[tuple[int, int, int, int]]) -> bool:
        left, top, right, bottom = rect
        for index, other in enumerate(rects):
            other_left, other_top, other_right, other_bottom = other
            other_gap = gap_to_rect(index)
            if left < other_right + other_gap and right > other_left - other_gap and top < other_bottom + other_gap and bottom > other_top - other_gap:
                return True
        return False

    def candidates(rects: list[tuple[int, int, int, int]], item_index: int) -> list[tuple[int, int, int, int, int]]:
        xs = {margin}
        ys = {margin}
        for rect_index, (left, top, right, bottom) in enumerate(rects):
            rect_gap = gap_to_rect(rect_index)
            for item_w, item_h, _ in orientations[item_index]:
                xs.add(right + rect_gap)
                xs.add(left - rect_gap - item_w)
                ys.add(bottom + rect_gap)
                ys.add(top - rect_gap - item_h)

        out: list[tuple[int, int, int, int, int]] = []
        for item_w, item_h, rotation in orientations[item_index]:
            for top in sorted(ys):
                if top < margin or top + item_h > page_h - margin:
                    continue
                for left in sorted(xs):
                    if left < margin or left + item_w > page_w - margin:
                        continue
                    rect = (left, top, left + item_w, top + item_h)
                    if row_band_compatible(rect, rects) and not rect_conflicts(rect, rects):
                        out.append((*rect, rotation))
        return sorted(out, key=lambda value: (value[1], value[0], value[4]))

    rects = list(occupied)
    placements: list[tuple[PrintItem, tuple[int, int, int, int], int]] = []
    for index, item in enumerate(items):
        candidate_rects = candidates(rects, index)
        if not candidate_rects:
            continue
        left, top, right, bottom, rotation = candidate_rects[0]
        rect = (left, top, right, bottom)
        rects.append(rect)
        placements.append((item, rect, rotation))
    return normalize_connected_standard_rotations(placements)


def standard_grid_rects(page: CardPage, config: BuildConfig) -> list[tuple[int, int, int, int]]:
    cols, _ = grid_capacity(config)
    margin = mm_to_px(config.margin_mm, config.dpi)
    card_w = mm_to_px(config.card_mm[0], config.dpi)
    card_h = mm_to_px(config.card_mm[1], config.dpi)
    oriented_w, oriented_h = card_h, card_w
    x0 = margin
    y0 = margin
    rects: list[tuple[int, int, int, int]] = []
    for index, item in enumerate(page.items):
        if item is None:
            continue
        row, col = divmod(index, cols)
        left = x0 + col * oriented_w
        top = y0 + row * oriented_h
        rects.append((left, top, left + oriented_w, top + oriented_h))
    rects.extend(rect for _, rect, _ in (page.extras or []))
    return rects


def page_loose_items(page: CardPage) -> list[PrintItem]:
    return [item for item in page.items if item is not None] + [item for item, _, _ in (page.extras or [])]


def place_loose_items_on_pages(
    pages: list[CardPage],
    loose_items: list[PrintItem],
    config: BuildConfig,
) -> list[PrintItem]:
    remaining = list(loose_items)
    for page in pages:
        if not remaining or page.spaced:
            continue
        occupied = standard_grid_rects(page, config)
        if loose_items_can_touch(remaining):
            placements = pack_loose_items_in_free_space(occupied, remaining, config)
        elif all(item_print_size(item, config) == (mm_to_px(config.card_mm[0], config.dpi), mm_to_px(config.card_mm[1], config.dpi)) for item in remaining):
            placements = pack_spaced_items_in_free_space(occupied, remaining, config)
        else:
            placements = pack_loose_items_in_free_space(occupied, remaining, config)
        if not placements:
            continue
        page.extras = list(page.extras or []) + placements
        for placed_item, _, _ in placements:
            remaining.remove(placed_item)
    return remaining


def sparse_standard_upright_row(
    standard_items: list[PrintItem],
    config: BuildConfig,
) -> list[tuple[PrintItem, tuple[int, int, int, int], int]] | None:
    if not standard_items:
        return None
    groups = {item.group for item in standard_items}
    if len(groups) != 1:
        return None

    page_w = mm_to_px(config.paper_mm[0], config.dpi)
    margin = mm_to_px(config.margin_mm, config.dpi)
    gap = mm_to_px(5.0, config.dpi)
    card_w = mm_to_px(config.card_mm[0], config.dpi)
    card_h = mm_to_px(config.card_mm[1], config.dpi)
    ordered: list[PrintItem] = []
    for image_type in ("front", "back"):
        ordered.extend(item for item in standard_items if item.image_type == image_type)
    if len(ordered) != len(standard_items):
        return None

    row_w = len(ordered) * card_w
    if any(item.image_type != ordered[0].image_type for item in ordered):
        row_w += gap
    if row_w > page_w - 2 * margin:
        return None

    placements: list[tuple[PrintItem, tuple[int, int, int, int], int]] = []
    x = margin
    previous_type: str | None = None
    for item in ordered:
        if previous_type is not None and item.image_type != previous_type:
            x += gap
        rect = (x, margin, x + card_w, margin + card_h)
        placements.append((item, rect, 0))
        x += card_w
        previous_type = item.image_type
    return placements


def pack_landscape_card_rows_below(
    occupied: list[tuple[int, int, int, int]],
    items: list[PrintItem],
    config: BuildConfig,
    internal_gap: int | None = None,
) -> list[tuple[PrintItem, tuple[int, int, int, int], int]]:
    if not items:
        return []

    page_w = mm_to_px(config.paper_mm[0], config.dpi)
    page_h = mm_to_px(config.paper_mm[1], config.dpi)
    margin = mm_to_px(config.margin_mm, config.dpi)
    gap = mm_to_px(5.0, config.dpi)
    row_gap = gap if occupied else 0
    item_gap = gap if internal_gap is None else internal_gap
    card_w = mm_to_px(config.card_mm[0], config.dpi)
    card_h = mm_to_px(config.card_mm[1], config.dpi)
    item_w, item_h = card_h, card_w
    usable_w = page_w - 2 * margin
    cols = max(1, (usable_w + item_gap) // (item_w + item_gap))
    top = max((rect[3] for rect in occupied), default=margin) + row_gap
    placements: list[tuple[PrintItem, tuple[int, int, int, int], int]] = []

    for index, item in enumerate(items):
        row, col = divmod(index, cols)
        left = margin + col * (item_w + item_gap)
        y = top + row * (item_h + gap)
        rect = (left, y, left + item_w, y + item_h)
        if rect[3] > page_h - margin:
            break
        rotation = 90 if col % 2 == 0 else -90
        placements.append((item, rect, rotation))
    return normalize_connected_standard_rotations(placements)


def reflow_sparse_standard_page_for_trailing(
    page: CardPage,
    trailing: list[PrintItem],
    config: BuildConfig,
) -> tuple[CardPage, list[PrintItem]] | None:
    if page.spaced or not page.extras:
        return None
    cols, _ = grid_capacity(config)
    standard_items = [item for item in page.items if item is not None and not is_character_item(item)]
    if not standard_items or len(standard_items) > 2 * cols:
        return None
    if any(is_character_item(item) or item.group == "board" for item in trailing):
        return None

    top_row = sparse_standard_upright_row(standard_items, config)
    if top_row is None:
        return None

    extras = [item for item, _, _ in (page.extras or [])]
    occupied = [rect for _, rect, _ in top_row]
    if extras and all(is_character_item(item) for item in extras):
        extra_placements = pack_landscape_card_rows_below(occupied, extras, config)
    else:
        extra_placements = pack_spaced_items_in_free_space(occupied, extras, config)
    if len(extra_placements) != len(extras):
        return None

    occupied.extend(rect for _, rect, _ in extra_placements)
    trailing_placements = pack_landscape_card_rows_below(occupied, trailing, config, mm_to_px(5.0, config.dpi))
    placed_trailing = [item for item, _, _ in trailing_placements]
    remaining = list(trailing)
    for item in placed_trailing:
        remaining.remove(item)
    if len(remaining) == len(trailing):
        return None

    _, rows = grid_capacity(config)
    blank_items = [None] * (cols * rows)
    return CardPage(blank_items, False, top_row + extra_placements + trailing_placements), remaining


def absorb_remaining_by_deferring_small_extras(
    pages: list[CardPage],
    remaining_items: list[PrintItem],
    config: BuildConfig,
) -> tuple[list[CardPage], list[PrintItem], list[PrintItem]] | None:
    if not remaining_items or any(is_character_item(item) for item in remaining_items):
        return None

    trial_pages = clone_pages(pages)
    remaining = list(remaining_items)
    deferred: list[PrintItem] = []
    changed = False

    for page in trial_pages:
        if not remaining or page.spaced or not page.extras:
            continue
        displaced = [item for item, _, _ in page.extras]
        if len(displaced) > 2:
            continue

        empty_page = CardPage(list(page.items), page.spaced, None)
        placements = pack_loose_items_in_free_space(standard_grid_rects(empty_page, config), remaining, config)
        if len(placements) <= len(displaced):
            continue

        page.extras = placements
        for placed_item, _, _ in placements:
            remaining.remove(placed_item)
        deferred.extend(displaced)
        changed = True

    if not changed:
        return None
    return trial_pages, remaining, deferred


def reflow_sparse_pages_for_trailing(
    pages: list[CardPage],
    trailing: list[PrintItem],
    config: BuildConfig,
) -> tuple[list[CardPage], list[PrintItem]] | None:
    for page_index, page in enumerate(pages):
        result = reflow_sparse_standard_page_for_trailing(page, trailing, config)
        if result is None:
            continue
        new_page, remaining = result
        trial_pages = clone_pages(pages)
        trial_pages[page_index] = new_page
        return trial_pages, remaining
    return None


def compact_trailing_pages(pages: list[CardPage], config: BuildConfig) -> tuple[list[CardPage], list[PrintItem]]:
    pages = clone_pages(pages)
    deferred: list[PrintItem] = []
    while len(pages) > 1:
        trailing = page_loose_items(pages[-1])
        if not trailing:
            pages.pop()
            continue

        trial_pages = clone_pages(pages[:-1])
        remaining = place_loose_items_on_pages(trial_pages, trailing, config)
        if remaining:
            reflowed = reflow_sparse_pages_for_trailing(pages[:-1], trailing, config)
            if reflowed is not None:
                trial_pages, remaining = reflowed
                if remaining:
                    absorbed = absorb_remaining_by_deferring_small_extras(trial_pages, remaining, config)
                    if absorbed is not None:
                        trial_pages, remaining, newly_deferred = absorbed
                        deferred.extend(newly_deferred)
                if not remaining:
                    pages = trial_pages
                    break
                if len(remaining) < len(trailing):
                    pages = trial_pages
                    deferred.extend(remaining)
                    break
            swapped = absorb_trailing_by_evicting_extras(pages[:-1], trailing, config)
            if swapped is None:
                swapped = absorb_trailing_by_evicting_extras_and_standards(pages[:-1], trailing, config)
            if swapped is None:
                deferred_swap = absorb_trailing_by_deferring_extras(pages[:-1], trailing, config)
                if deferred_swap is not None:
                    swapped, newly_deferred = deferred_swap
                    deferred.extend(newly_deferred)
            if swapped is None:
                if len(remaining) < len(trailing):
                    pages = trial_pages
                    deferred.extend(remaining)
                break
            pages = swapped
            break
        else:
            pages = trial_pages
            break
    return pages, deferred


def absorb_trailing_by_evicting_extras(
    base_pages: list[CardPage],
    trailing: list[PrintItem],
    config: BuildConfig,
) -> list[CardPage] | None:
    if not trailing or any(is_character_item(item) for item in trailing):
        return None

    for target_index, page in enumerate(base_pages):
        if page.spaced or not page.extras or len(page.extras) > 2:
            continue
        trial_pages = clone_pages(base_pages)
        target = trial_pages[target_index]
        displaced = [item for item, _, _ in (target.extras or [])]
        target.extras = None
        trial_pages[target_index], remaining_trailing = add_standard_items_to_empty_slots_with_remaining(target, trailing, config)
        if remaining_trailing:
            continue
        remaining_displaced = place_loose_items_on_pages(trial_pages, displaced, config)
        if not remaining_displaced:
            return trial_pages

    return None


def absorb_trailing_by_evicting_extras_and_standards(
    base_pages: list[CardPage],
    trailing: list[PrintItem],
    config: BuildConfig,
) -> list[CardPage] | None:
    if not trailing or any(is_character_item(item) for item in trailing):
        return None

    for target_index, page in enumerate(base_pages):
        if page.spaced or not page.extras or len(page.extras) > 2:
            continue

        displaced = [item for item, _, _ in (page.extras or [])]
        target_without_extras = CardPage(list(page.items), page.spaced, None)
        target_with_trailing, remaining_trailing = add_standard_items_to_empty_slots_with_remaining(target_without_extras, trailing, config)
        if remaining_trailing:
            continue

        empty_slots = sum(1 for item in target_with_trailing.items if item is None)
        if empty_slots <= 0:
            continue

        for donor_index, donor in enumerate(base_pages):
            if donor_index == target_index or donor.spaced or donor.extras:
                continue
            donor_standard_count = sum(1 for item in donor.items if item is not None and not is_character_item(item))
            for move_count in range(min(empty_slots, donor_standard_count), 0, -1):
                donor_trial, moved = remove_last_standard_items(donor, move_count)
                if len(moved) != move_count:
                    continue
                target_filled, remaining_moved = add_standard_items_to_empty_slots_with_remaining(target_with_trailing, moved, config)
                if remaining_moved:
                    continue

                trial_pages = clone_pages(base_pages)
                trial_pages[target_index] = target_filled
                trial_pages[donor_index] = donor_trial
                remaining_displaced = place_loose_items_on_pages(trial_pages, displaced, config)
                if not remaining_displaced:
                    return trial_pages

    return None


def absorb_trailing_by_deferring_extras(
    base_pages: list[CardPage],
    trailing: list[PrintItem],
    config: BuildConfig,
) -> tuple[list[CardPage], list[PrintItem]] | None:
    if not trailing or any(is_character_item(item) for item in trailing):
        return None

    for target_index, page in enumerate(base_pages):
        if page.spaced or not page.extras or len(page.extras) > 2:
            continue

        trial_pages = clone_pages(base_pages)
        target = trial_pages[target_index]
        displaced = [item for item, _, _ in (target.extras or [])]
        target.extras = None
        placements = pack_loose_items_in_free_space(standard_grid_rects(target, config), trailing, config)
        if len(placements) != len(trailing):
            continue
        target.extras = placements
        return trial_pages, displaced

    return None


def standard_move_is_compatible(receiver: CardPage, moved: list[PrintItem], config: BuildConfig) -> bool:
    if not moved:
        return False
    if not config.crop_black_borders:
        return True
    cols, _ = grid_capacity(config)
    items = list(receiver.items)
    moved_index = 0
    for index, existing in enumerate(items):
        if existing is not None or moved_index >= len(moved):
            continue
        item = moved[moved_index]
        if not standard_slot_accepts_item(items, index, item, cols, config):
            return False
        items[index] = item
        moved_index += 1
    return moved_index == len(moved)


def remove_last_standard_items(page: CardPage, count: int) -> tuple[CardPage, list[PrintItem]]:
    items = list(page.items)
    moved_with_indices: list[tuple[int, PrintItem]] = []
    for index in range(len(items) - 1, -1, -1):
        item = items[index]
        if item is None or is_character_item(item):
            continue
        moved_with_indices.append((index, item))
        items[index] = None
        if len(moved_with_indices) == count:
            break
    moved_with_indices.reverse()
    return CardPage(items, page.spaced, list(page.extras or [])), [item for _, item in moved_with_indices]


def add_standard_items_to_empty_slots_with_remaining(
    page: CardPage,
    moved: list[PrintItem],
    config: BuildConfig,
) -> tuple[CardPage, list[PrintItem]]:
    cols, _ = grid_capacity(config)
    items = list(page.items)
    remaining = list(moved)
    for index, item in enumerate(items):
        if item is None and remaining:
            moved_item = remaining[0]
            if standard_slot_accepts_item(items, index, moved_item, cols, config):
                items[index] = moved_item
                remaining.pop(0)
    return CardPage(items, page.spaced, None), remaining


def add_standard_items_to_empty_slots(page: CardPage, moved: list[PrintItem], config: BuildConfig) -> CardPage:
    return add_standard_items_to_empty_slots_with_remaining(page, moved, config)[0]


def standard_slot_accepts_item(
    items: list[PrintItem | None],
    index: int,
    item: PrintItem,
    cols: int,
    config: BuildConfig,
) -> bool:
    if not config.crop_black_borders:
        return True
    groups = {placed.group for placed in items if placed is not None and not is_character_item(placed)}
    if groups and groups != {item.group}:
        return False
    total = len(items)
    for neighbor_index in (index - cols, index + cols):
        if neighbor_index < 0 or neighbor_index >= total:
            continue
        neighbor = items[neighbor_index]
        if neighbor is None or is_character_item(neighbor):
            continue
        if neighbor.group != item.group or neighbor.image_type != item.image_type:
            return False
    return True


def distribute_standard_overflow(
    pages: list[CardPage],
    overflow: list[PrintItem],
    config: BuildConfig,
) -> None:
    cols, rows = grid_capacity(config)
    per_page = cols * rows
    remaining = list(overflow)

    for page_index, page in enumerate(pages):
        if not remaining or page.extras:
            continue
        items = list(page.items)
        changed = False
        for slot_index, existing in enumerate(items):
            if existing is not None:
                continue
            for item_index, item in enumerate(remaining):
                if standard_slot_accepts_item(items, slot_index, item, cols, config):
                    items[slot_index] = item
                    del remaining[item_index]
                    changed = True
                    break
            if not remaining:
                break
        if changed:
            pages[page_index] = CardPage(items, page.spaced, page.extras)

    while remaining:
        page_items: list[PrintItem | None] = [None] * per_page
        next_remaining: list[PrintItem] = []
        page_group = remaining[0].group if config.crop_black_borders else None
        for item in remaining:
            if page_group is not None and item.group != page_group:
                next_remaining.append(item)
                continue
            placed = False
            for slot_index, existing in enumerate(page_items):
                if existing is None and standard_slot_accepts_item(page_items, slot_index, item, cols, config):
                    page_items[slot_index] = item
                    placed = True
                    break
            if not placed:
                next_remaining.append(item)
        pages.append(CardPage(page_items))
        remaining = next_remaining


def reserve_character_rows_by_evicting_standard(
    pages: list[CardPage],
    character_items: list[PrintItem],
    config: BuildConfig,
) -> list[PrintItem]:
    cols, rows = grid_capacity(config)
    if cols < 2 or rows < 2 or len(character_items) < 2:
        return character_items

    remaining = list(character_items)
    overflow: list[PrintItem] = []
    for page_index, page in enumerate(pages):
        if len(remaining) < 2 or page.spaced or page.extras:
            continue
        standard_count = sum(1 for item in page.items if item is not None and not is_character_item(item))
        if standard_count != cols * rows:
            continue
        trial_page, moved = remove_last_standard_items(page, cols)
        if len(moved) != cols:
            continue
        placed = pack_spaced_items_in_free_space(standard_grid_rects(trial_page, config), remaining[:2], config)
        if len(placed) != 2:
            continue
        pages[page_index] = CardPage(trial_page.items, trial_page.spaced, placed)
        overflow.extend(moved)
        remaining = remaining[2:]

    if overflow:
        distribute_standard_overflow(pages, overflow, config)
    return remaining


def place_characters_in_tight_grid_corners(
    pages: list[CardPage],
    character_items: list[PrintItem],
    config: BuildConfig,
) -> list[PrintItem]:
    cols, rows = grid_capacity(config)
    if cols < 2 or rows < 2 or not character_items:
        return character_items

    corner_slots = [(0, -90), (cols * rows - 1, 90)]
    remaining = list(character_items)
    overflow: list[PrintItem] = []

    for page in pages:
        if not remaining or page.spaced or page.extras:
            continue

        items = list(page.items)
        for slot_index, rotation in corner_slots:
            if not remaining:
                break
            current = items[slot_index]
            if current is not None and is_character_item(current):
                continue

            item = replace(remaining[0], layout_rotation=rotation)
            trial = list(items)
            trial[slot_index] = None
            if not can_place_item(trial, slot_index, item, cols):
                continue

            if current is not None:
                overflow.append(current)
            items[slot_index] = item
            remaining = remaining[1:]

        page.items = items

    if overflow:
        distribute_standard_overflow(pages, overflow, config)
    return remaining


def swap_standard_space_for_characters(
    pages: list[CardPage],
    character_items: list[PrintItem],
    config: BuildConfig,
) -> list[PrintItem]:
    remaining = list(character_items)
    if not remaining:
        return remaining

    while remaining:
        best = None
        best_score = 0

        for receiver_index, receiver in enumerate(pages):
            receiver_extras = list(receiver.extras or [])
            if not receiver_extras:
                continue
            empty_slots = [index for index, item in enumerate(receiver.items) if item is None]
            if not empty_slots:
                continue

            for donor_index, donor in enumerate(pages):
                if donor_index == receiver_index or donor.extras:
                    continue
                donor_standard_count = sum(1 for item in donor.items if item is not None and not is_character_item(item))
                max_move = min(len(empty_slots), donor_standard_count)
                for move_count in range(max_move, 0, -1):
                    donor_trial, moved = remove_last_standard_items(donor, move_count)
                    if len(moved) != move_count or not standard_move_is_compatible(receiver, moved, config):
                        continue

                    receiver_trial = add_standard_items_to_empty_slots(receiver, moved, config)
                    char_pool = [item for item, _, _ in receiver_extras] + remaining
                    placed = pack_spaced_items_in_free_space(standard_grid_rects(donor_trial, config), char_pool, config)
                    net_gain = len(placed) - len(receiver_extras)
                    if net_gain > best_score:
                        best_score = net_gain
                        best = (receiver_index, donor_index, receiver_trial, donor_trial, placed, char_pool)
                    if best_score >= len(remaining):
                        break
                if best_score >= len(remaining):
                    break
            if best_score >= len(remaining):
                break

        if best is None:
            return remaining

        receiver_index, donor_index, receiver_trial, donor_trial, placed, char_pool = best
        pages[receiver_index] = receiver_trial
        donor_trial.extras = placed
        pages[donor_index] = donor_trial
        remaining = char_pool[len(placed) :]

    return remaining


def normalize_standard_order(pages: list[CardPage], config: BuildConfig) -> None:
    standard_items = [
        item
        for page in pages
        for item in page.items
        if item is not None and not is_character_item(item)
    ]
    if not standard_items:
        return

    if config.crop_black_borders:
        standard_items = sorted(standard_items, key=lambda item: (group_order_key(item.group), item_order_key(item)))
    else:
        standard_items = sorted(standard_items, key=noncropped_standard_item_order_key)

    if config.crop_black_borders:
        buckets: dict[tuple[str, str], list[PrintItem]] = {}
        for item in standard_items:
            buckets.setdefault((item.group, item.image_type), []).append(item)

        for page in pages:
            items = list(page.items)
            for index, item in enumerate(items):
                if item is None or is_character_item(item):
                    continue
                key = (item.group, item.image_type)
                items[index] = buckets[key].pop(0) if buckets.get(key) else item
            page.items = items
        return

    gap = mm_to_px(5.0, config.dpi)
    slot_rects = standard_page_slot_rects(config)
    slots: list[tuple[CardPage, int]] = []
    for page in pages:
        if page.spaced:
            continue
        extra_rects = [rect for _, rect, _ in (page.extras or [])]
        for index, item in enumerate(page.items):
            if item is not None and is_character_item(item):
                continue
            if index >= len(slot_rects):
                continue
            if extra_rects and rects_conflict(slot_rects[index], extra_rects, gap):
                continue
            slots.append((page, index))

    item_iter = iter(standard_items)
    filled: set[tuple[int, int]] = set()
    for page, index in slots:
        try:
            item = next(item_iter)
        except StopIteration:
            break
        page.items[index] = item
        filled.add((id(page), index))

    for page in pages:
        for index, item in enumerate(page.items):
            if item is not None and not is_character_item(item) and (id(page), index) not in filled:
                page.items[index] = None


def standard_page_slot_rects(config: BuildConfig) -> list[tuple[int, int, int, int]]:
    cols, rows = grid_capacity(config)
    margin = mm_to_px(config.margin_mm, config.dpi)
    card_w = mm_to_px(config.card_mm[0], config.dpi)
    card_h = mm_to_px(config.card_mm[1], config.dpi)
    oriented_w, oriented_h = card_h, card_w
    x0 = margin
    y0 = margin
    rects: list[tuple[int, int, int, int]] = []
    for index in range(cols * rows):
        row, col = divmod(index, cols)
        left = x0 + col * oriented_w
        top = y0 + row * oriented_h
        rects.append((left, top, left + oriented_w, top + oriented_h))
    return rects


def fill_free_space_with_spaced_characters(
    pages: list[CardPage],
    character_items: list[PrintItem],
    config: BuildConfig,
) -> list[PrintItem]:
    if not character_items:
        return character_items

    cols, _ = grid_capacity(config)
    margin = mm_to_px(config.margin_mm, config.dpi)
    card_h = mm_to_px(config.card_mm[1], config.dpi)
    card_w = mm_to_px(config.card_mm[0], config.dpi)
    oriented_w, oriented_h = card_h, card_w
    x0 = margin
    y0 = margin
    remaining = list(character_items)

    for page in pages:
        if not remaining or page.spaced:
            continue
        occupied: list[tuple[int, int, int, int]] = []
        for index, item in enumerate(page.items):
            if item is None:
                continue
            row, col = divmod(index, cols)
            left = x0 + col * oriented_w
            top = y0 + row * oriented_h
            occupied.append((left, top, left + oriented_w, top + oriented_h))
        occupied.extend(rect for _, rect, _ in (page.extras or []))

        placed = pack_spaced_items_in_free_space(occupied, remaining, config)
        if placed:
            page.extras = list(page.extras or []) + placed
            remaining = remaining[len(placed):]

    return remaining


def grouped_card_pages(items: list[PrintItem], config: BuildConfig) -> list[CardPage]:
    cols, rows = grid_capacity(config)
    per_page = cols * rows
    pages: list[CardPage] = []
    standard_items = [item for item in items if not item.group.startswith("character:")]
    character_items = sorted((item for item in items if item.group.startswith("character:")), key=item_order_key)
    if config.crop_black_borders:
        groups = sorted({item.group for item in standard_items}, key=group_order_key)
        for group in groups:
            group_items = [item for item in standard_items if item.group == group]
            pages.extend(pack_cropped_standard_group(group_items, cols, rows))
        existing_first = fill_cropped_character_pages(pages, character_items, config, reserve_first=False)
        reserve_first = fill_cropped_character_pages(pages, character_items, config, reserve_first=True)
        pages = min((existing_first, reserve_first), key=grouped_character_page_score)
    else:
        group_items = sorted(standard_items, key=noncropped_standard_item_order_key)
        for i in range(0, len(group_items), per_page):
            page = group_items[i : i + per_page]
            if i + per_page >= len(group_items):
                page = page + [None] * (per_page - len(page))
            pages.append(CardPage(page))
        existing_first = fill_noncropped_character_pages(pages, character_items, config, reserve_first=False, tight_grid_first=False)
        reserve_first = fill_noncropped_character_pages(pages, character_items, config, reserve_first=True, tight_grid_first=False)
        tight_grid_first = fill_noncropped_character_pages(pages, character_items, config, reserve_first=False, tight_grid_first=True)
        pages = min((existing_first, reserve_first, tight_grid_first), key=character_page_score)
    return pages


def pack_spaced_character_pages(items: list[PrintItem], config: BuildConfig) -> list[CardPage]:
    margin = mm_to_px(config.margin_mm, config.dpi)
    card_w = mm_to_px(config.card_mm[0], config.dpi)
    card_h = mm_to_px(config.card_mm[1], config.dpi)
    remaining = list(items)
    pages: list[CardPage] = []

    while remaining:
        extras = pack_spaced_items_in_free_space([], remaining, config)
        placed_count = len(extras)

        if placed_count == 0:
            item = remaining[0]
            left = margin
            top = margin
            extras.append((item, (left, top, left + card_w, top + card_h), 0))
            placed_count = 1

        pages.append(CardPage([], True, extras))
        remaining = remaining[placed_count:]

    return pages


def group_order_key(group: str) -> tuple[int, str]:
    base_order = {"encounter": 0, "office": 1, "basement": 2}
    if group in base_order:
        return base_order[group], group
    if group.startswith("character:"):
        return 3, group
    return 99, group


def item_order_key(item: PrintItem) -> tuple[int, str, str, str]:
    if item.image_type == "back":
        phase = 2
    elif item.is_starter:
        phase = 0
    else:
        phase = 1
    return phase, item.sort_label or item.label.lower(), item.image_type, str(item.path)


def noncropped_standard_item_order_key(item: PrintItem) -> tuple[int, str, str, str]:
    if item.image_type == "back":
        phase = {"encounter": 5, "office": 6, "basement": 7}.get(item.group, 99)
    elif item.group == "encounter":
        phase = 0
    elif item.group == "office" and item.is_starter:
        phase = 1
    elif item.group == "office":
        phase = 2
    elif item.group == "basement" and item.is_starter:
        phase = 3
    elif item.group == "basement":
        phase = 4
    else:
        phase = 99
    return phase, item.sort_label or item.label.lower(), item.image_type, str(item.path)


def clone_pages(pages: list[CardPage]) -> list[CardPage]:
    return [CardPage(list(page.items), page.spaced, list(page.extras or []) if page.extras else None) for page in pages]


def character_page_score(pages: list[CardPage]) -> tuple[int, int, int, int]:
    character_indices: list[int] = []
    character_only_pages = 0
    extra_character_count = 0
    for page_index, page in enumerate(pages):
        page_items = [item for item in page.items if item is not None]
        extra_items = [item for item, _, _ in (page.extras or [])]
        page_items.extend(extra_items)
        has_character = any(is_character_item(item) for item in page_items)
        has_standard = any(not is_character_item(item) for item in page_items)
        if has_character:
            character_indices.append(page_index)
        if has_character and not has_standard:
            character_only_pages += 1
        extra_character_count += sum(1 for item in extra_items if is_character_item(item))
    last_character_page = max(character_indices) if character_indices else -1
    return len(pages), last_character_page, character_only_pages, extra_character_count


def grouped_character_page_score(pages: list[CardPage]) -> tuple[int, int, int, int, int]:
    character_indices: list[int] = []
    character_only_pages = 0
    extra_character_count = 0
    for page_index, page in enumerate(pages):
        page_items = [item for item in page.items if item is not None]
        extra_items = [item for item, _, _ in (page.extras or [])]
        page_items.extend(extra_items)
        has_character = any(is_character_item(item) for item in page_items)
        has_standard = any(not is_character_item(item) for item in page_items)
        if has_character:
            character_indices.append(page_index)
        if has_character and not has_standard:
            character_only_pages += 1
        extra_character_count += sum(1 for item in extra_items if is_character_item(item))
    last_character_page = max(character_indices) if character_indices else -1
    return len(pages), len(character_indices), character_only_pages, extra_character_count, last_character_page


def fill_cropped_character_pages(
    base_pages: list[CardPage],
    character_items: list[PrintItem],
    config: BuildConfig,
    reserve_first: bool,
) -> list[CardPage]:
    pages = clone_pages(base_pages)
    remaining = list(character_items)

    if reserve_first:
        remaining = reserve_character_rows_by_evicting_standard(pages, remaining, config)
    remaining = fill_bottom_rows_with_spaced_characters(pages, remaining, config)
    remaining = swap_standard_space_for_characters(pages, remaining, config)
    if not reserve_first:
        remaining = reserve_character_rows_by_evicting_standard(pages, remaining, config)
        remaining = fill_bottom_rows_with_spaced_characters(pages, remaining, config)
        remaining = swap_standard_space_for_characters(pages, remaining, config)

    normalize_standard_order(pages, config)
    if remaining:
        pages.extend(pack_spaced_character_pages(remaining, config))
    return pages


def fill_noncropped_character_pages(
    base_pages: list[CardPage],
    character_items: list[PrintItem],
    config: BuildConfig,
    reserve_first: bool,
    tight_grid_first: bool,
) -> list[CardPage]:
    cols, _ = grid_capacity(config)
    pages = clone_pages(base_pages)
    remaining = list(character_items)

    if tight_grid_first:
        remaining = place_characters_in_tight_grid_corners(pages, remaining, config)

    if reserve_first:
        remaining = reserve_character_rows_by_evicting_standard(pages, remaining, config)

    if remaining and pages:
        last_page = pages[-1]
        if not last_page.spaced:
            filled_page, filled_remaining = fill_page_with_characters(list(last_page.items), remaining, cols)
            if not filled_remaining:
                pages[-1] = CardPage(filled_page)
                remaining = []

    remaining = fill_free_space_with_spaced_characters(pages, remaining, config)
    remaining = swap_standard_space_for_characters(pages, remaining, config)

    if not reserve_first:
        remaining = reserve_character_rows_by_evicting_standard(pages, remaining, config)
        remaining = fill_free_space_with_spaced_characters(pages, remaining, config)
        remaining = swap_standard_space_for_characters(pages, remaining, config)

    normalize_standard_order(pages, config)
    if remaining:
        pages.extend(pack_spaced_character_pages(remaining, config))
    return pages


def draw_crop_lines(page: Image.Image, rect: tuple[int, int, int, int]) -> None:
    draw = ImageDraw.Draw(page)
    left, top, right, bottom = rect
    draw.line((left, 0, left, page.height), fill=(0, 0, 0), width=1)
    draw.line((right, 0, right, page.height), fill=(0, 0, 0), width=1)
    draw.line((0, top, page.width, top), fill=(0, 0, 0), width=1)
    draw.line((0, bottom, page.width, bottom), fill=(0, 0, 0), width=1)


def load_page_image(cache: dict[Path, Image.Image], path: Path) -> Image.Image:
    if path not in cache:
        cache[path] = Image.open(path).convert("RGB")
    return cache[path]


def rotated(img: Image.Image, degrees: int) -> Image.Image:
    return img.rotate(degrees, expand=True) if degrees else img


def paste_print_placements(page: Image.Image, placements: list[tuple[PrintItem, tuple[int, int, int, int], int]]) -> None:
    image_cache: dict[Path, Image.Image] = {}

    for _, rect, _ in placements:
        draw_crop_lines(page, rect)

    for item, rect, rotation in placements:
        face = load_page_image(image_cache, item.path)
        bleed = load_page_image(image_cache, item.bleed_path) if item.bleed_path is not None else face
        bleed = rotated(bleed, rotation)
        cx = (rect[0] + rect[2]) // 2
        cy = (rect[1] + rect[3]) // 2
        page.paste(bleed, (cx - bleed.width // 2, cy - bleed.height // 2))

    for item, rect, rotation in placements:
        face = rotated(load_page_image(image_cache, item.path), rotation)
        size = (rect[2] - rect[0], rect[3] - rect[1])
        if face.size != size:
            face = face.resize(size, Image.Resampling.LANCZOS)
        page.paste(face, (rect[0], rect[1]))


def split_trailing_character_only_pages(pages: list[CardPage]) -> tuple[list[CardPage], list[PrintItem]]:
    deferred: list[PrintItem] = []
    kept = list(pages)
    while kept:
        page = kept[-1]
        extras = page.extras or []
        if page.items or not extras or any(not is_character_item(item) for item, _, _ in extras):
            break
        deferred = [item for item, _, _ in extras] + deferred
        kept.pop()
    return kept, deferred


def render_card_pages(
    items: list[PrintItem],
    config: BuildConfig,
    start_index: int,
    board_items: list[PrintItem] | None = None,
) -> tuple[int, list[PrintItem], list[PrintItem]]:
    pages = grouped_card_pages(items, config)
    pages, compact_deferred_items = compact_trailing_pages(pages, config)
    remaining_board_items = place_loose_items_on_pages(pages, list(board_items or []), config)
    pages, deferred_character_items = split_trailing_character_only_pages(pages)
    deferred_character_items = compact_deferred_items + deferred_character_items
    page_w = mm_to_px(config.paper_mm[0], config.dpi)
    page_h = mm_to_px(config.paper_mm[1], config.dpi)
    margin = mm_to_px(config.margin_mm, config.dpi)
    card_w = mm_to_px(config.card_mm[0], config.dpi)
    card_h = mm_to_px(config.card_mm[1], config.dpi)
    oriented_w, oriented_h = card_h, card_w
    cols, _ = grid_capacity(config)

    def render_one_card_page(page_offset_and_plan: tuple[int, CardPage]) -> tuple[Path, int]:
        page_offset, page_plan = page_offset_and_plan
        page_items = page_plan.items
        spaced = page_plan.spaced
        extras = page_plan.extras or []
        page = Image.new("RGB", (page_w, page_h), "white")

        gap = mm_to_px(5.0, config.dpi) if spaced else 0
        if spaced:
            page_cols = max(1, (page_w - 2 * margin + gap) // (oriented_w + gap))
        else:
            page_cols = cols
        x0 = margin
        y0 = margin
        placements: list[tuple[PrintItem | None, tuple[int, int, int, int], int]] = []
        for idx, item in enumerate(page_items):
            row = idx // page_cols
            col = idx % page_cols
            left = x0 + col * (oriented_w + gap)
            top = y0 + row * (oriented_h + gap)
            rotate = item.layout_rotation if item is not None and item.layout_rotation is not None else (-90 if col % 2 else 90)
            placements.append((item, (left, top, left + oriented_w, top + oriented_h), rotate))

        drawable = [(item, rect, rotate) for item, rect, rotate in placements if item is not None] + extras
        paste_print_placements(page, drawable)

        out = PAGES_DIR / f"page_{start_index + page_offset:03d}.png"
        out.parent.mkdir(parents=True, exist_ok=True)
        save_temp_png(page, out, config.dpi)
        return out, sum(1 for item in page_items if item is not None) + len(extras)

    if pages:
        with ThreadPoolExecutor(max_workers=worker_count(len(pages))) as executor:
            for out, count in executor.map(render_one_card_page, enumerate(pages)):
                print(f"Wrote {out.relative_to(ROOT)} ({count} card images)")
    return start_index + len(pages), deferred_character_items, remaining_board_items


def plan_board_rows(items: list[PrintItem], config: BuildConfig) -> list[list[tuple[PrintItem, bool]]]:
    page_w = mm_to_px(config.paper_mm[0], config.dpi)
    page_h = mm_to_px(config.paper_mm[1], config.dpi)
    margin = mm_to_px(config.margin_mm, config.dpi)
    gap = mm_to_px(5.0, config.dpi)
    usable_w = page_w - 2 * margin
    usable_h = page_h - 2 * margin

    pages: list[list[tuple[PrintItem, bool]]] = []
    current: list[tuple[PrintItem, bool]] = []
    row_w = row_h = used_h = 0

    for item in items:
        with Image.open(item.path) as img:
            options = [(False, img.width, img.height), (True, img.height, img.width)]
        rotate, bw, bh = min((o for o in options if o[1] <= usable_w), key=lambda o: o[2], default=options[0])
        needed_w = bw if row_w == 0 else row_w + gap + bw
        if row_w and needed_w > usable_w:
            used_h += row_h + (gap if used_h else 0)
            row_w = row_h = 0
        if used_h and used_h + bh > usable_h:
            pages.append(current)
            current = []
            used_h = row_w = row_h = 0
        current.append((item, rotate))
        row_w = bw if row_w == 0 else row_w + gap + bw
        row_h = max(row_h, bh)
    if current:
        pages.append(current)
    return pages


def render_board_pages(
    items: list[PrintItem],
    config: BuildConfig,
    start_index: int,
    character_items: list[PrintItem] | None = None,
) -> int:
    if not items and not character_items:
        return start_index
    pages = plan_board_rows(items, config)
    page_w = mm_to_px(config.paper_mm[0], config.dpi)
    page_h = mm_to_px(config.paper_mm[1], config.dpi)
    margin = mm_to_px(config.margin_mm, config.dpi)
    gap = mm_to_px(5.0, config.dpi)
    usable_w = page_w - 2 * margin
    remaining_characters = list(character_items or [])

    def plan_board_placements(page_items: list[tuple[PrintItem, bool]]) -> tuple[list[tuple[PrintItem, tuple[int, int, int, int], int]], list[tuple[PrintItem, tuple[int, int, int, int], int]]]:
        rows: list[list[tuple[PrintItem, bool, int, int]]] = []
        row: list[tuple[PrintItem, bool, int, int]] = []
        row_w = row_h = 0
        for item, rotate in page_items:
            with Image.open(item.path) as img:
                bw, bh = (img.height, img.width) if rotate else (img.width, img.height)
            if row and row_w + gap + bw > usable_w:
                rows.append(row)
                row = []
                row_w = row_h = 0
            row.append((item, rotate, bw, bh))
            row_w = bw if row_w == 0 else row_w + gap + bw
            row_h = max(row_h, bh)
        if row:
            rows.append(row)

        y = margin
        board_placements: list[tuple[PrintItem, tuple[int, int, int, int], int]] = []
        for row in rows:
            row_h = max(bh for _, _, _, bh in row)
            x = margin
            for item, rotate, bw, bh in row:
                top = y + (row_h - bh) // 2
                rect = (x, top, x + bw, top + bh)
                board_placements.append((item, rect, 90 if rotate else 0))
                x += bw + gap
            y += row_h + gap

        occupied = [rect for _, rect, _ in board_placements]
        standard_items = [item for item in remaining_characters if not is_character_item(item)]
        character_items = [item for item in remaining_characters if is_character_item(item)]
        standard_placements = pack_loose_items_in_free_space(occupied, standard_items, config)
        occupied.extend(rect for _, rect, _ in standard_placements)
        character_placements = pack_spaced_items_in_free_space(occupied, character_items, config)
        return board_placements, standard_placements + character_placements

    planned_pages = []
    for page_items in pages:
        board_placements, char_placements = plan_board_placements(page_items)
        if char_placements:
            for placed_item, _, _ in char_placements:
                remaining_characters.remove(placed_item)
        planned_pages.append((board_placements, char_placements))

    for page in pack_spaced_character_pages(remaining_characters, config):
        planned_pages.append(([], list(page.extras or [])))
    remaining_characters = []

    def render_one_board_page(page_offset_and_plan) -> tuple[Path, int]:
        page_offset, (board_placements, char_placements) = page_offset_and_plan
        page = Image.new("RGB", (page_w, page_h), "white")

        placements = board_placements + char_placements
        paste_print_placements(page, placements)

        out = PAGES_DIR / f"page_{start_index + page_offset:03d}.png"
        out.parent.mkdir(parents=True, exist_ok=True)
        save_temp_png(page, out, config.dpi)
        return out, len(placements)

    if planned_pages:
        with ThreadPoolExecutor(max_workers=worker_count(len(planned_pages))) as executor:
            for out, count in executor.map(render_one_board_page, enumerate(planned_pages)):
                noun = "images" if count != 1 else "image"
                print(f"Wrote {out.relative_to(ROOT)} ({count} {noun})")
    return start_index + len(planned_pages)
