from typing import List, Optional # Returns (safe sheep, caught sheep) def process_lunch_time(sheep: List[List[int]], steps: List[int], L: int) -> tuple[List[int], Optional[int]]: right_side = [] chase = None chase_distance = None chase_runs_right = False for i, me in enumerate(sheep): location = 0 for num, (hour, size) in zip(steps, enumerate(me)): location += num * (hour + 1) * size if location > L: location = L D = min(L - location, location) runs_right = location >= L // 2 can_catch = L < 4 * D if runs_right: right_side.append(i) if not can_catch: continue # Incorrectly chasing the closest, breaking ties by chasing right-running sheep if chase is None or (D > chase_distance or (D == chase_distance and runs_right and not chase_runs_right)): chase = i chase_distance = D chase_runs_right = runs_right if chase is not None and chase in right_side: right_side.remove(chase) return right_side, chase n, m, L = map(int, input().split()) sheep = [list(map(int, input().split())) for _ in range(n)] steps = [0] * 11 for _ in range(m): X = int(input()) if 1 <= X <= 11: steps[X - 1] += 1 continue right_side, caught = process_lunch_time(sheep, steps, L) print(" ".join(str(x + 1) for x in right_side) if len(right_side) > 0 else "None") print(caught + 1 if caught is not None else "None") steps = [0] * 11 for idx in right_side + ([caught] if caught is not None else []): sheep[idx] = [0] * 11 # Will forever be stuck on the left.