Un oso vive en el origen \((0, 0)\) de un plano infinito y necesita poder llegar caminando a algún punto a distancia euclidiana exactamente \(D\) del origen.

Llegan \(N\) predicciones en orden; cada una es una recta infinita que, desde ese momento, el oso ya no puede cruzar. Ninguna recta pasa por el origen. Encuentra la primera predicción después de la cual ningún punto a distancia \(D\) es alcanzable desde el origen (sin cruzar las rectas vigentes).

Entrada

La primera línea tiene un entero \(N\) \((1 \le N \le 2 \cdot 10^5)\) y un número racional \(D\) con a lo más cinco decimales \((1 \le D \le 10^6)\).

Cada una de las siguientes \(N\) líneas tiene cuatro enteros \(X_1\), \(Y_1\), \(X_2\), \(Y_2\) \((-10^6 \le X_1, Y_1, X_2, Y_2 \le 10^6)\) con \((X_1, Y_1) \ne (X_2, Y_2)\): la recta que pasa por esos dos puntos. Las predicciones se numeran de \(1\) a \(N\) en ese orden.

Salida

Una línea con el número de la primera predicción tras la cual el oso ya no alcanza ningún punto a distancia \(D\), o el carácter * si eso nunca pasa. Se garantiza que cambiar \(D\) en \(\pm 10^{-5}\) no altera la respuesta.

Ejemplo 1

Entrada

5 4.321
-2 -1 3 -2
1 6 3 -2
1 6 -2 -1
-3 4 3 3
-2 1 5 4

Salida

4

Ejemplo 2

Entrada

5 2
1 0 1 1
-1 0 -1 -1
3 1 1 3
1 3 3 1
0 4 4 0

Salida

*

Regional Latinoamericana 2023 del ICPC, problema H («Health in Hazard»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.