Wiretap Device

Time limit1sMemory limit128 MB

Summary

Find the one device whose received power exceeds six times the background noise plus every other device's power, or print NOISE.

Level: Easy3 of 10
Topics: Math, Array
Solved: No attempts yet

Problem

A meeting of programming contest organizers is held in Amsterdam this week. Seongjin, the president of the National Union of University Programming Contest Clubs, wants to eavesdrop on it. He hid wiretap devices near the meeting room. Each device records without stopping and sends what it picks up over radio.

Seongjin handed receivers to union members and spread them across several places. Radio signals interfere with one another, so there can be places where nothing is heard at all. Given the position of one member holding a receiver, write a program that finds the wiretap device that person can hear.

The device audible at a position is the $i$ -th device that satisfies the following inequality.

$r_i > 6 \left( B + \sum_{j \ne i} r_j \right)$

$r_i = \dfrac{s_i}{\left| P_i - P_{\mathrm{listen}} \right|^2}$ is the received signal power of the $i$ -th device.
$s_i$ is the strength of the signal sent by the $i$ -th device.
$P_i$ is the position of the $i$ -th device.
$P_{\mathrm{listen}}$ is the position of the person holding the receiver.
$\left| P_i - P_j \right|$ is the Euclidean distance between $P_i$ and $P_j$ .
$B$ is the background noise level.

Input

The first line contains the number of test cases. This value does not exceed 100.

The first line of each test case contains the number of wiretap devices $n$ ( $0 \le n \le 100{,}000$ ). The second line contains the background noise level $B$ ( $0 \le B \le 1{,}000{,}000$ ). The third line contains the x coordinate $x$ and the y coordinate $y$ of the person holding the receiver. Each of the next $n$ lines contains the position $x_i$ , $y_i$ of the $i$ -th device and its signal strength $s_i$ ( $0 \le s_i \le 1{,}000{,}000$ ).

Every coordinate lies in the interval $[0, 10000]$ . Every device position $P_i$ differs from the receiver position $P_{\mathrm{listen}}$ . No input is given in which floating point error changes the answer.

Output

For each test case, print the number of the audible wiretap device on its own line. If no device can be heard, print NOISE.

Device numbers start at 1. Two devices can never satisfy the inequality at the same time, so the answer is unique.

Examples1

Example 1

Input

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

Expected output

1
NOISE
1