In the year 2202, humanity mastered subspace navigation technology.

When subspace navigation is activated, the spaceship carves out a subspace tunnel in the universe. You can think of this as the region in the plane bounded by the two lines $y = 0$ and $y = y_0$ ($y_0 > 0$) (and extending to infinity). The starting and ending points of the spaceship are at infinity on the negative and positive $x$-axis, respectively (approximately, you can consider the start and end points of the subspace navigation to be $s = (-10^{18}, 0)$ and $t = (10^{18}, 0)$).

However, just as the universe is not uniform but filled with planets and black holes, there are many "singularities" in the subspace tunnel. Each singularity is located at some coordinate $(x, y)$, where $x \in [0, 10^6]$ and $y \in [0, y_0]$. For a spaceship flying through this, getting close to them is dangerous. Therefore, an intelligent flight control system should plan a route from the start to the end such that the spaceship is sufficiently far from these singularities at all times—that is, the distance to the nearest singularity at any moment is maximized. Of course, your route cannot exceed the boundaries of the subspace tunnel. Formally, given $n, y_0$ and $n$ singularities in the subspace tunnel with IDs from $1$ to $n$, denoted by $\{p_i = (x_i, y_i)\}_{i=1}^n$, you are required to find:

$$\sup \left\{ \inf_{t \in [0, 1]} \min_{i=1}^n d(\varphi(t), p_i) \mid \varphi : [0, 1] \to \mathbb{R} \times [0, y_0] \in [C^0(\mathbb{R})]^2, \text{s.t. } \varphi(0) = s, \varphi(1) = t \right\} (*)$$

where $d : \mathbb{R}^2 \times \mathbb{R}^2 \to \mathbb{R}$ is the Euclidean distance in the plane:

$$d((x_1, y_1), (x_2, y_2)) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$$

In addition, the distribution of singularities in the subspace tunnel is not stable; sometimes new singularities are scanned, and sometimes old ones disappear. Specifically, the flight control system receives two types of events, totaling $m$ events:

• Type 1: 1 x y, indicating that the spaceship has scanned a new singularity at $(x, y)$, with an ID equal to the maximum ID of all singularities that have ever existed (including those that have already disappeared) plus $1$.
• Type 2: 2 id, indicating that the singularity with ID id has disappeared. It is guaranteed that the singularity with ID id exists and has not disappeared yet.

To remain competitive in the interstellar market, a powerful flight control system should recompute the value of $(*)$ after each event.

Input

Read data from standard input. The first line contains three positive integers $n, m, y_0$. The next $n$ lines, where the $i$-th line ($i \in [1, n]$) contains two integers $(x_i, y_i)$, represent a singularity with ID $i$. The next $m$ lines, each in the form 1 x y or 2 id, represent an event.

Output

Output to standard output. Output $m + 1$ lines. The first line outputs a non-negative real number representing the answer before any events occur. The next $m$ lines each contain a non-negative real number representing the answer after each event.

Your answer is considered correct if and only if the relative or absolute error between your output and the standard answer does not exceed $10^{-6}$. That is, if your output and the standard answer are $a, b > 0$ respectively, the answer is considered correct if and only if $\frac{|a-b|}{\max\{|a|, |b|, 1\}} \leq 10^{-6}$.

Examples

Input 1

1 1 1
2 0 0
3 1 1

Output 1

1
0.70710678118654752440084436210485

Subtasks

For all data, it is guaranteed that: $1 \leq n, m \leq 3000$, $1 \leq y_0 \leq 10^6$, $x \in [0, 10^6]$, $y \in [0, y_0]$. It is guaranteed that in Type 2 events, the singularity with ID id exists and has not disappeared.