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