As the general elections approach, Rahul thinks of adding pace to the election campaign. Due to time constraints, Sonia advices him to visit only first k nearest cities.

You have been given x and y coordinates of the cities. Find the kth  nearest city.

Input Format

First line of input contains t the number of test cases and k.

For each test case there are 2 types of queries:
first type: 1 x y , x and y are the co-ordinates of the city

Second type: 2 , for each query of second type output the rocket distance of kth nearest city from the position of Rahul

Rocket Distance between two points (x2, y2) and (x1, y1) is defined as (x2 - x1)2 + (y2 – y1)2

The poisiton of Rahul is always ar Origin(0, 0).

Constraints:

1 ≤ k ≤ q ≤ 10⁵

-10⁶ ≤ x, y ≤ 10⁶

Output Format

For each query of type 2, output the Rocket distance of Kth nearest city from Origin.