# pyright: strict from itertools import accumulate, combinations from sys import stdin def offsets(length: int, present: set[int]) -> list[int]: return list(accumulate(1 if i not in present else 0 for i in range(length))) def solve( points: set[tuple[int, int]], x_offsets: list[int], y_offsets: list[int], expansion: int = 2, ) -> int: def offset(p: tuple[int, int]) -> tuple[int, int]: return ( p[0] + x_offsets[p[0]] * (expansion - 1), p[1] + y_offsets[p[1]] * (expansion - 1), ) def manhattan_distance(a: tuple[int, int], b: tuple[int, int]) -> int: return abs(a[0] - b[0]) + abs(a[1] - b[1]) return sum( manhattan_distance(offset(a), offset(b)) for a, b in combinations(points, 2) ) points = {(x, y) for y, l in enumerate(stdin) for x, c in enumerate(l) if c == "#"} x_present, y_present = set(p[0] for p in points), set(p[1] for p in points) width, height = max(x for x in x_present) + 1, max(y for y in y_present) + 1 x_offsets = offsets(width, x_present) y_offsets = offsets(height, y_present) print(solve(points, x_offsets, y_offsets)) print(solve(points, x_offsets, y_offsets, 1000000))