Маршрутизатор с параметрами пути в стиле ServeMux

Напишите маршрутизатор с шаблонами в стиле ServeMux Go 1.22 (правила упрощены и заданы ниже точно).

Шаблон: [МЕТОД ]путь. Путь начинается с / и делится на сегменты по /. Сегмент {имя} совпадает с любым непустым сегментом запроса. Если путь шаблона заканчивается на /, это префиксный шаблон: он совпадает с запросом, у которого сегментов строго больше, чем у шаблона без последнего пустого, и первые совпадают (/static/ подходит для /static/ и /static/a/b, но не для /static; шаблон / подходит для любого пути). Иначе число сегментов должно совпасть.

Выбор:

1. Шаблоны, совпавшие по пути. Если таких нет: 404.
2. Из них подходящие по методу: шаблон без метода подходит к любому, GET подходит и к HEAD. Если таких нет: 405.
3. Лучший по ключам: больше литеральных сегментов; точный лучше префиксного; с методом лучше, чем без; раньше в списке.

Ввод: n, затем n строк имя шаблон; q, затем q запросов МЕТОД путь (n ≤ 200, q ≤ 1200).

Вывод: на каждый запрос имя обработчика и параметры имя=значение в порядке шаблона через пробел, либо 404 или 405.

Пример

4
list GET /items
show GET /items/{id}
new GET /items/new
root /
5
GET /items/7
GET /items/new
POST /items/7
GET /items
DELETE /x/y

show id=7
new
root
list
root