Candies on the table

Limits: 6 sec., 1024 MiB

This statement was translated automatically from Ukrainian.

After the competition, Zenyk and Marichka were at home, lively discussing problems and eating candies with friends. When they had eaten enough candies and everyone had shared their solutions to today’s Olympiad problems, Marichka came up with another problem.

First, she places \(n\) candies on the table. Marichka places the \(i\)-th candy at the point with coordinates \((x_i, y_i)\).

After that, she performs \(q\) actions. Each action is either placing another candy on the table at coordinates \((x_j, y_j)\), or removing the last added candy. After each action, you need to find the minimum distance between any two candies on the table.

Input

The first line contains two integers \(n\) and \(q\) — the number of candies that Marichka initially places on the table and the number of actions she performs afterwards.

The next \(n\) lines each contain two integers \(x_i\) and \(y_i\) — the coordinates of the \(i\)-th candy.

The next \(q\) lines describe Marichka’s actions. The action of adding a candy to the table is described by the line 1 \(\quad x_j \quad y_j\), and the action of removing the last added candy is described by a single number 0.

Marichka will never remove candies that were initially on the table, nor will she place a candy at an already occupied coordinate.

Output

Output \(q\) real numbers on separate lines — the answer to the problem after each of Marichka’s actions. The answer will be considered correct if its absolute or relative error does not exceed \(10^{-7}\).

Constraints

\(2 \le n \le 10^5\),

\(1 \le q \le 10^5\),

the coordinates of the candies are non-negative and do not exceed \(10^6\).

The problem scoring consists of the following subtasks:

1 point — example from the statement,

9 points — \(n, q \le 10^3\),

15 points — no additional constraints.

You will receive the points for a subtask only if you give the correct answer to all tests in the subtask.

Samples

Input (stdin) сopy	Output (stdout) сopy
3 5 1 3 4 7 8 3 1 9 8 1 6 4 0 1 4 4 1 6 4	5.000000000 2.236067977 5.000000000 3.000000000 2.000000000

Notes

Initially, Marichka places three candies at points with coordinates \((1, 3)\), \((4, 7)\) and \((8, 3)\).

After that, five actions take place.

• Marichka places a candy at the point \((9, 8)\). The distance between points \((1, 3)\) and \((4, 7)\) is \(\sqrt{(4-1)^2+(7-3)^2}=5\). This is the minimum distance among all pairs of candies on the table.

• Marichka places a candy at the point \((6, 4)\). The minimum distance is achieved between the candies at points \((4, 7)\) and \((6, 4)\) and is equal to \(\sqrt{5}\).

• Marichka removes the candy from the point \((6, 4)\). The minimum distance is again achieved between points \((1, 3)\) and \((4, 7)\) and is equal to \(5\).

• Next, she places a candy at the point \((4, 4)\). Now the minimum distance is the distance between points \((4, 4)\) and \((4, 7)\).

• After adding a candy at the point \((6, 4)\) the minimum distance is achieved between points \((4, 4)\) and \((6, 4)\).