시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 116 44 42 40.777%

문제

이번주에 알고스팟 회의가 암스테르담에서 열린다. 전국 대학생 프로그래밍 대회 동아리 연합(이하 전대프연) 회장 성진이는 알고스팟 회의를 도청하려고 한다. 성진이는 도청장치를 회의 장소 근처에 숨겨놓았다. 도청장치는 계속해서 녹음하며, 무선 전파를 이용해서 전송한다.

성진이는 전대프연 회원들에게 도청장치의 수신기를 나누어주었고, 여러 장소에 흩어 보냈다. 전파는 서로 간섭을 일으킨다. 따라서, 전혀 듣지 못하는 장소가 있을 수 있다. 수신기를 가진 한 회원의 위치가 주어졌을 때, 그 사람이 들을 수 있는 도청장치를 구하는 프로그램을 작성하시오.

어떤 장소에서 들을 수 있는 도청장치는 다음과 같은 식을 만족하는 \(i\)번째 도청장치이다.

\[r_i > 6(B+\sum_{j \ne i} {r_j})\]

  • \(r_i = \frac{s_i} {\left| P_i - P_{listen} \right| ^2}\)는 \(i\)번째 도청장치의 신호 수신 세기이다.
  • \(s_i\)는 \(i\)번째 도청장치가 보낸 신호의 세기이다.
  • \(P_i\)는 \(i\)번째 도청장치의 위치이다.
  • \(P_{listen}\)는 수신기를 들고있는 사람의 위치이다.
  • \(\left| P_i - P_{j} \right|\) \(P_i\)와 \(P_j\) 사이의 유클리드 거리이다.
  • \(B\)는 백그라운드 노이즈의 레벨이다.

입력

첫째 줄에 테스트 케이스의 수가 주어지며, 100을 넘지 않는다. 각 테스트 케이스의 첫째 줄에는 도청장치의 수 \(n\) (0 ≤ \(n\) ≤ 100,000)이 주어진다. 둘째 줄에는 백그라운드 노이즈의 레벨 \(B\) (0 ≤ \(B\) ≤ 1,000,000)가 주어진다. 셋째 줄에는 수신기를 들고있는 사람의 위치 x좌표와 y좌표 \(x\)와 \(y\)가 주어진다. 다음 \(n\)개 줄에는 \(i\)번째 도청장치의 위치 \(x_i\), \(y_i\)와 신호의 세기 \(s_i\)가 주어진다. (0 ≤ \(s_i\) ≤ 1,000,000)

모든 좌표는 구간 [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
NOISE
1

힌트