There is an infinite $2 ext{D}$ plane where you are given a $2 ext{D}$ integer array queries, where each queries[i] = [x, y] represents an obstacle placed at the coordinate $(x, y)$. You are also given an integer k.

Initially, there are no obstacles on the plane. For each query, an obstacle is placed at the specified coordinate.

The distance of an obstacle at $(x, y)$ from the origin $(0, 0)$ is defined as its Manhattan distance, which is $|x| + |y|$.

Return an integer array results of length equal to queries.length, where results[i] represents the distance of the $k^{ ext{th}}$ nearest obstacle to the origin after processing the $i^{ ext{th}}$ query. If there are fewer than k obstacles present after a query, results[i] should be $-1$.

Constraints:

• $1 \leq$ queries.length $\leq 2 imes 10^5$

• All queries[i] are unique.

• $-10^9 \leq$ queries[i][0], queries[i][1] $\leq 10^9$

• $1 \leq$ k $\leq 10^5$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.