Voronoi Diagram#5962
On the plane, you will handle queries of two types:
1\ x_i\ y_i — Add the point (x_i, y_i + dy) to the plane.
2\ x_i\ y_i — Calculate the distance from the point (x_i, y_i + dy) to the nearest point among those added by the first type of queries.
Here, dy = [\text{last\_res}] \bmod 2, where is the result of the most recent query of the second type, and denotes rounding to the nearest integer. Before any second type query is executed, dy = 0. There will be no rounding ambiguities; specifically, the fractional parts of all query results differ from by at least 10^{-7}.
The first line contains a single integer (1 \le Q \le 200\,000) — the number of queries. The next lines each contain three integers: t_i, x_i, and y_i (1 \le t_i \le 2, 0 \le x_i, y_i \le 1\,000\,000) — the type of the query and the coordinates of the point. It is guaranteed that for all 1 \le i \le Q - 1, x_i \le x_{i+1}, and all entered points are distinct, even after accounting for the modification. The first query is always of the first type.
For each query of the second type, output a single floating-point number on a separate line — the distance from the modified input point to the nearest point among those added by type one queries up to that moment. The results must be accurate with an absolute or relative error of 10^{-8}.
Example 1