804. Hostel Visit

0

Medium

The Dean of MAIT plans to visit the hostels of MAIT, but 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 the input contains Q, the total number of queries, and K. There are two types of queries: First type: 1 x y For a query of the first type, you will receive the coordinates (x, y) of a newly constructed hostel. Second type: 2 For a query 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. The 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