위험 속의 건강

얼어붙은 황야에 거대한 빙하를 삼아 사는 북극곰이 있다. 빙하는 2차원 평면으로 나타낸다. 곰의 굴은 $(0, 0)$에 있다. 건강을 유지하려면 곰은 굴에서 깨어날 때마다 굴로부터 정확히 거리 $D$만큼 떨어진 임의의 점까지 걸어간다. 거리는 유클리드 거리로 잰다.

연구진은 앞으로 며칠 동안 지구온난화가 빙하에 미칠 영향을 예측한 보고서를 받았다. 예측은 시간 순서대로 주어진다. 각 예측은 융해 사건을 나타내는 무한한 직선이다. 예측이 실현되면 곰은 그 직선을 더 이상 넘을 수 없다.

처음에는 빙하가 모든 방향으로 무한히 넓어서 곰이 자유롭게 돌아다닐 수 있다. 하지만 빙하가 줄어들어 곰이 더 이상 건강을 유지할 수 없게 될 수도 있다. 굴로부터 정확히 거리 $D$인 점 중에서 곰이 도달할 수 있는 점이 하나도 없게 되는 가장 이른 시점을 구하라.

그림은 첫 번째 테스트 케이스를 나타낸다. 원은 굴로부터 정확히 거리 $D$인 점들의 집합이다. 처음 세 예측(실선)만 고려하면 곰은 아직 원 위의 점에 도달할 수 있다. 네 번째 예측(점선)까지 고려하면 원 위의 어떤 점도 굴에서 도달할 수 없다.

첫 줄에는 정수 $N$($1 \le N \le 2 \times 10^5$)과 소수점 아래 다섯 자리 이하의 유리수 $D$($1 \le D \le 10^6$)가 주어진다. $N$은 예측의 개수이고, $D$는 굴로부터의 거리이다.

이어지는 $N$개의 줄에는 각각 정수 $X_1$, $Y_1$, $X_2$, $Y_2$($-10^6 \le X_1, Y_1, X_2, Y_2 \le 10^6$이고 $(X_1, Y_1) \ne (X_2, Y_2)$)가 주어진다. 이 네 값은 $(X_1, Y_1)$과 $(X_2, Y_2)$를 지나는 무한한 직선을 정한다. 예측이 실현되면 곰은 이 직선을 넘을 수 없다. 예측은 시간 순서대로 주어지며, 1부터 $N$까지 그 순서대로 번호가 매겨진다. 어떤 예측 직선도 굴을 지나지 않는다.

그 예측이 실현된 뒤에 굴로부터 정확히 거리 $D$인 점 중 곰이 도달할 수 있는 점이 하나도 없게 되는 가장 이른 예측의 번호를 한 줄에 출력한다. 그런 상황이 일어나지 않으면 *를 출력한다. 주어진 $D$에서 $\pm 10^{-5}$ 이내로 값이 달라져도 출력은 바뀌지 않는다는 것이 보장된다.