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