Маршрутизатор как в ASP.NET Core

Реализуйте упрощённую маршрутизацию. Шаблон состоит из сегментов через /: литерал (сравнивается без учёта регистра, только латиница), параметр {name} (любой сегмент) или {name:int} (только цифры, не больше 9 штук).

Для запроса METHOD /path найдите маршрут, у которого совпадает число сегментов и все сегменты подходят. Среди подходящих по пути выберите маршрут с совпадающим методом и наибольшим числом литеральных сегментов; при равенстве тот, что объявлен раньше.

Вывод для каждого запроса: номер маршрута (с 1) и значения параметров имя=значение через пробел в порядке шаблона. Если путь не подошёл ни к одному маршруту: 404. Если путь подошёл, но метод нигде не совпал: 405.

Ввод: n маршрутов (n ≤ 200), затем q запросов (q ≤ 5000).

Пример

4
GET /users
GET /users/{id:int}
GET /users/me
POST /users
6
GET /users/42
GET /users/me
DELETE /users/1
GET /orders
GET /Users
GET /users/abc

2 id=42
3
405
404
1
404