Скоро в городе откроет свои кафе знаменитая сеть закусочных. Чтобы жителям города было проще найти ближайшее заведение, менеджеры сети решили выпустить мобильное приложение. Разработку этого приложения доверили самому известному и талантливому программисту — Максу, конечно же.
Всего в городе открываются $$$N$$$ закусочных, пронумерованных от 1 до $$$N$$$. $$$i$$$-я закусочная расположена в точке $$$(X_i; Y_i)$$$ и имеет рейтинг $$$R_i$$$.
Приложение должно по информации о том, где находится человек, определять закусочные, расположенные неподалёку от него — то есть такие, расстояние до которых (по прямой) не превышает $$$D$$$. Из этих закусочных нужно выбрать ту, которая имеет наивысший рейтинг, а если таких несколько — ближайшую. Если наилучших закусочных всё ещё несколько, следует выбрать ту, номер которой меньше.
Помогите приложению Макса найти наилучшую закусочную для каждого клиента.
Выходные данные
Выведите $$$M$$$ строк, каждая из которых содержит одно целое число — номер наилучшей закусочной, расположенной неподалёку от клиента, отправившего соответствующий запрос.
Если неподалёку от клиента нет закусочных, выведите в соответствующей строке -1.