13. Красота требует жертв

Есть набор из $n$ вещей, у которых есть определенные характеристики. Для каждой вещи помимо характеристик известен факт ее наличия в магазине, а также цена $c$. У вас есть $k$ бурлей на покупку вполне конкретной вещи, но может оказаться так, что ее нет в наличии или она вам не по карману. Найдите 5 кандидатов, имеющихся в наличии и подходящих по стоимости, при этом наиболее похожих на нужную вещь. Похожесть между вещами $u$ и $v$ определим как Евклидово расстояние между ними.

Вам будет задано $q$ запросов вида $i$, $k$, где $i$ $-$ это номер нужной вам вещи, а $k$ $-$ количество бурлей в ваших карманах. Если нужная вам вещь подходит по стоимости и есть в наличии, выведите ее номер, в противном случае выведите ровно 5 кандидатов, подходящих под условие задачи.

Гарантируется, что всегда есть хотя бы 5 вещей, подходящих под требуемые условия.

Открытый файл с описанием вещей содержит следующие данные. В первой строчке задается $n$, $10 \leq n \leq 10^4$ $-$ количество вещей в магазине. Далее идут $n$ строк с описаниями вещей вида $p$, $c$, $f_1,f_2,...,f_{10}$, где $p \in \{0,1\}$ $-$ признак наличия вещи в магазине, $1\leq c\leq 10^5$ --- стоимость вещи, $f_1,f_2,...,f_{10}$ $-$ определенные характеристики вещи, $-100 < f_i < 100$.

В отдельном файле с примерами запросов и ответов на них содержатся строки вида $i$, $k$, $a_1,a_2,a_3,a_4,a_5$ либо $i$, $k$, $a$ в зависимости от того, подходит ли под условие запрашиваемая вещь. Здесь $0\leq i\leq n-1$, $1\leq k \leq 10^5$, $0\leq a, a_{1..5}\leq n-1$. Эти данные нужны для проверки вашего решения.

В закрытом файле, на котором будет тестироваться ваша программа, в первой строчке задаются два числа $n$, $10 \leq n \leq 10^4$ и $q, 1 \leq q \leq 10^3$, разделенные пробелами, где $n$ $-$ количество вещей в магазине, а $q$ $-$ количество запросов. Далее идут $n$ строк с описаниями вещей вида $p,c,f_1,f_2,...,f_{10}$, где $p \in \{0,1\}$ $-$ признак наличия вещи в магазине, $1\leq c\leq 10^5$ $-$ стоимость вещи, $f_1,f_2,...,f_{10}$ $-$ определенные характеристики вещи, $-100 < f_i < 100$. После чего идут $q$ строк вида $i$, $k$, $0\leq i\leq n-1$, $1\leq k \leq 10^5$.

Ваша программа должна вывести ответы на $q$ запросов: в первой строке выведите количество найденных вещей $k$ ($k \in \{1,5\}$), во второй строке необходимо вывести либо индекс вещи, если она в наличии и её стоимость меньше либо равна сумме, имеющейся у вас, либо ровно пять индексов подходящих под это условие вещей, разделённых пробелами. Порядок вещей в списке может быть любым.

Для удобства индексы вещей нумеруются с нуля. В случае, когда больше пяти вещей подходят под условие, вы можете вывести любые пять из них.

В результате работы ваша программа должна предложить такие объекты, что среднее Евклидово расстояние от них до исходной вещи не должно превышать ответ жюри более чем в два раза для каждого запроса.

https://disk.yandex.ru/d/g9VIKdbAneh6Fw - ссылка на файл с открытыми примерами данных.

https://disk.yandex.ru/d/vabElRMn4VDFZg - ссылка на файл с открытыми примерами запросов и ответов.