Напиши на Python 3.12 растеризатор двумерной сцены: один модуль, только стандартная библиотека. Сторонние библиотеки (PIL, numpy и любые другие) использовать нельзя.

## Интерфейс

```python
def render(scene: dict) -> list[list[tuple[int, int, int]]]:
    ...
```

Функция возвращает картинку как список строк сверху вниз. Каждая строка это список пикселей слева направо, каждый пиксель это кортеж `(r, g, b)` из целых чисел от 0 до 255. Элемент `result[j][i]` соответствует пикселю в столбце `i` и строке `j`.

## Сцена

```python
{
  "width": 320, "height": 200,          # размер холста в пикселях
  "background": "#0b1d3a",              # цвет фона
  "shapes": [ {...}, {...} ]            # фигуры, рисуются по порядку, каждая следующая поверх предыдущих
}
```

## Координаты и пиксели

Ось x направлена вправо, ось y вниз. Пиксель `(i, j)` занимает квадрат от `i` до `i+1` по x и от `j` до `j+1` по y. Пиксель закрашивается фигурой, если **центр пикселя** `(i + 0.5, j + 0.5)` лежит внутри фигуры. Сглаживания нет.

## Цвета

Цвет задаётся строкой: `#rgb`, `#rgba`, `#rrggbb` или `#rrggbbaa`, шестнадцатеричные цифры в любом регистре. В коротких формах каждая цифра удваивается (`#a3f` означает `#aa33ff`). Если альфа не указана, она равна 255. У фона альфа игнорируется, фон всегда непрозрачный. Любая другая строка считается ошибкой.

## Фигуры

У каждой фигуры есть поле `type` и поле `fill` (цвет или градиент). Необязательные поля: `opacity` (число от 0 до 1, по умолчанию 1) и `transform` (см. ниже). Все координаты фигуры заданы в её локальной системе.

- `rect`: поля `x`, `y`, `w`, `h`. Точка внутри, если `x <= px < x + w` и `y <= py < y + h`. При `w <= 0` или `h <= 0` фигура пустая.
- `circle`: поля `cx`, `cy`, `r`. Точка внутри, если `(px - cx)² + (py - cy)² <= r²`.
- `ellipse`: поля `cx`, `cy`, `rx`, `ry`. Точка внутри, если `((px - cx) / rx)² + ((py - cy) / ry)² <= 1`. При `rx <= 0` или `ry <= 0` фигура пустая.
- `polygon`: поле `points` (список точек `[x, y]`, не меньше трёх, многоугольник замкнут) и необязательное `fill_rule`: `"nonzero"` (по умолчанию) или `"evenodd"`. Принадлежность точки определяется лучом из неё вправо. Ребро `(x0, y0) → (x1, y1)` пересекает луч, если `y0 <= py < y1` или `y1 <= py < y0`, и при этом `x0 + (py - y0) * (x1 - x0) / (y1 - y0) > px`. Каждое такое ребро добавляет к числу оборотов `+1`, если `y1 > y0`, иначе `-1`. Для `nonzero` точка внутри, если сумма не равна нулю, для `evenodd` точка внутри, если число пересекающих рёбер нечётное.
- `line`: поля `x1`, `y1`, `x2`, `y2`, `width`. Точка внутри, если расстояние от неё до отрезка не больше `width / 2`. Если концы совпадают, получается круг.

## Преобразование

`transform` задаётся шестью числами `[a, b, c, d, e, f]` и переводит локальную точку `(x, y)` в точку холста `(a*x + c*y + e, b*x + d*y + f)`. Чтобы проверить пиксель, его центр переводится обратным преобразованием в локальные координаты, и проверка идёт там. Поэтому круг под масштабом становится эллипсом, а толщина линии масштабируется вместе с ней. Если преобразование вырожденное (`a*d - b*c == 0`), фигура не рисуется. Без `transform` локальные координаты совпадают с координатами холста.

## Градиент

```python
{"type": "linear", "x1": 0, "y1": 0, "x2": 100, "y2": 0, "stops": [[0, "#000"], [0.5, "#f00"], [1, "#fff"]]}
```

Координаты градиента тоже локальные. Для точки `p` параметр `t` равен скалярному произведению `(p - p1)` на `(p2 - p1)`, делённому на `|p2 - p1|²`, и обрезается до отрезка `[0, 1]`. Если `p1` совпадает с `p2`, то `t = 0`. Точки остановки `stops` идут по возрастанию смещения. Если `t` не больше первого смещения, берётся первый цвет. Если не меньше последнего, берётся последний. Иначе берутся соседние остановки с `o_i <= t <= o_{i+1}`, и каждый канал, включая альфу, интерполируется линейно, без округления на этом шаге. Если две соседние остановки стоят в одной точке, берётся цвет второй. Пустой список `stops` считается ошибкой.

## Наложение цветов

Для закрашиваемого пикселя берётся цвет заливки `(r, g, b, a)` в этой точке. Непрозрачность равна `α = a / 255 * opacity`. Каждый канал холста заменяется на `floor(src * α + dst * (1 - α) + 0.5)`, где `dst` это текущее целое значение канала. Результат ограничивается отрезком от 0 до 255.

## Ошибки

Неверный цвет, неизвестный тип фигуры, многоугольник меньше чем из трёх точек и градиент без остановок должны вызывать `ValueError`.

## Производительность

Холст 800×600 с 400 небольшими фигурами и холст 640×480 с несколькими крупными полупрозрачными фигурами и градиентом должны рисоваться не дольше 4 секунд каждый на обычном ПК.

## Формат ответа

Ответь ТОЛЬКО кодом модуля в одном блоке ```python.