Tienes \(n\) puntos del plano con coordenadas enteras (puede haber puntos repetidos) y un entero \(k\). Elige los \(k\) puntos más cercanos al origen \((0, 0)\) según la distancia euclidiana.

Para que la respuesta sea única, ordena todos los puntos por distancia al origen y, a igual distancia, por \(x\) y luego por \(y\): la respuesta son los \(k\) primeros, en ese orden.

Entrada

La primera línea tiene \(n\) y \(k\) \((1 \le k \le n \le 10^5)\). Siguen \(n\) líneas con \(x\) e \(y\) \((|x|, |y| \le 10^4)\).

Salida

\(k\) líneas con las coordenadas de los puntos elegidos, en el orden descrito.

Ejemplo 1

Entrada

2 1
1 3
-2 2

Salida

-2 2

Ejemplo 2

Entrada

3 2
3 3
5 -1
-2 4

Salida

3 3
-2 4

Basado en el problema 973 de LeetCode, K Closest Points to Origin, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.