Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance.

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Example 1:

Input:
1 3
-2 2
1
Output: -2 2

Example 2:

Input:
3 3
5 -1
-2 4
2
Output: 3 3
-2 4

Constraints:

• 1 ≤ k ≤ points.length ≤ 10⁴
• -10⁴ ≤ xi, yi ≤ 10⁴

Input format: First n lines: xi yi (one point per line). Last line: k.

Output format: k closest points, one per line (xi yi).