411. Hostel Visit
0
Medium
The Dean of MAIT plans to visit the hostels of MAIT. Due to his busy schedule, he will only visit the first "K" nearest hostels. The hostels are located in a 2D plane. Given the coordinates of the hostels, we need to determine the Rocket distance of the Kth nearest hostel from the origin (Dean's place).
Input Format
The first line of input contains Q, the total number of queries, and K.
There are two types of queries:
First type: 1 x y
For queries of the first type, you will receive the coordinates (x, y) of a newly constructed hostel.
Second type: 2
For queries of the second type, you need to output the Rocket distance of the Kth nearest hostel so far.
The Dean will always stay at his place (origin).
It is guaranteed that there will be at least K queries of type 1 before the first query of type 2.
Rocket distance between two points (x2, y2) and (x1, y1) is defined as (x2 - x1)^2 + (y2 - y1)^2.
Output Format
For each query of type 2, output the Rocket distance of the Kth nearest hostel from the origin.
Example
Input
9 3
1 10 10
1 9 9
1 -8 -8
2
1 7 7
2
1 6 6
1 5 5
2
Output
200
162
98
Constraints
1 <= k <= Q <= 10^5
-10^6 <= x , y <= 10^6
-10^6 <= x , y <= 10^6
Loading...
View Submissions
Console