eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Плохой сигнал

Плохой сигнал

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Организуется важная встреча ООН в городе. Любое уважающее себя шпионское агентство попытается подслушать делегации, чтобы получить некоторое преимущество в переговорах. Они делают это путем установки скрытых микрофонов вокруг мест встречи. Эти микрофоны постоянно ловят звуковые волны и передают их по радио.

На самом деле жесткая конкуренция между шпионскими агентствами окутала весь город скрытыми микрофонами. Причем так, что радиоволны мешали друг другу, что часто даже не позволяло извлечь нужный сигнал из беспорядка радиоволн - в зависимости от Вашего положения и близости к различным передатчикам.

Извлечь сигнал i можно только если:

где

  • - сила принимаемого сигнала от микрофона i,

  • s_i - сила сигнала, посылаемого от микрофона i,

  • P_i - местоположение микрофона i,

  • P_listen - местоположение, откуда Вы снимаете сигналы,

  • |P_i-P_j| - Евклидово расстояние между точками P_i и P_j

  • B - уровень фонового шума.

Входные данные

Первая строка содержит количество тестов, не большее 100. Каждый тест содержит:

  • строку с числом n (0 n 100000) - количество установленных микрофонов.

  • строку со значением B (0 B 1000000) - уровнем фонового шума.

  • строку с целыми числами x и y - координаты точки Plisten, с которой снимаются сигналы.

  • n строк с тремя целыми числами x_i, y_i и s_i (0 < s_{i }1000000): координаты x и y местоположения P_i микрофона i и силу его сигнала.

Все координаты лежат в промежутке [0, 10000]. Все места P_i отличаются от P_listen. Тесты подобраны так, что малые округления действительных чисел не влияют на результат.

Выходные данные

Для каждого теста вывести:

  • одно целое число в отдельной строке: индекс (начиная с единицы) микрофона, сигнал с которого можно получить, или строку "NOISE" если такого микрофона не существует.

Пример

Входные данные #1
3
4
10
100 100
90 90 20000
110 90 50
90 110 1000
110 110 50
4
100
100 100
90 90 20000
110 90 50
90 110 1000
110 110 50
2
0
0 10
0 0 1000
0 8 1
Выходные данные #1
1
NOISE
1
Источник 2013 Benelux Algorithm Programming Contest (BAPC), Preliminaries, Сентябрь 28, Задача B