Путь к файлу по правилам PSR-4

Даны правила PSR-4: префикс пространства имён (заканчивается на \) и каталог. Для каждого полного имени класса найдите путь к файлу: выберите правило с самым длинным подходящим префиксом, отрежьте префикс, оставшиеся \ замените на /, добавьте .php и каталог (ровно один / между каталогом и остатком). Ведущий \ у имени класса игнорируется. Если префикс не подошёл или после него ничего не осталось, выведите not found.

Ввод: m правил, затем q имён классов (q ≤ 2·10⁴).

Пример

3
App\ src/
App\Tests\ tests/
Vendor\Lib\ vendor/lib/src/
4
App\Billing\Invoice
App\Tests\InvoiceTest
\Vendor\Lib\Http\Client
Other\Thing

src/Billing/Invoice.php
tests/InvoiceTest.php
vendor/lib/src/Http/Client.php
not found