A base station sits at the origin (0, 0). There are n relay towers at integer coordinates. Select the k towers closest to the base by Euclidean distance. To keep the ordering exact, compare towers by the key (x*x + y*y, x, y) in ascending order; the selected towers are the k with the smallest keys, and you must print them in that same key order.
Two towers may share coordinates; identical towers are interchangeable and produce identical output lines.
Input format
Line 1: two integers n and k.
Next n lines: two integers x and y, one tower per line.
Output format
k lines, each x y, the chosen towers ordered by (x*x + y*y, x, y) ascending.
Constraints
- 1 <= k <= n <= 100000
- -100000 <= x, y <= 100000