At most half

Limits: 4 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Zenyk and Marichka love working with intervals. Today they are solving the following problem.

Given a set of numeric intervals and a single number \(x\). The task is to find the length of the longest interval that:

• lies entirely within the bounds \([0...m]\);

• contains the point \(x\) (possibly on the boundaries);

• the length of its intersection with each of the given intervals does not exceed half of the length of the corresponding interval.

Marichka easily solves this problem, but Zenyk complicated it a bit. Initially, the set of intervals is empty. Then \(q\) queries must be processed, each of which can be of one of two types:

1. Add a new interval \([l, r]\) to the set.

2. Remove from the set the interval that was added in the query with number \(p\).

After each query, you need to output a single number — the length of the longest interval described above.

Input

The first line contains three integers \(m\), \(q\), and \(x\).

The next \(q\) lines describe the queries. The first number describes the type of query (1 or 2).

In the case of a query of the first type, the same line contains two integers \(l\) and \(r\) — the bounds of the interval to be added.

In the case of a query of the second type, a single number \(p\) is given — the number of the query in which the interval to be removed was added. It is guaranteed that this interval has not been removed yet, and that after its removal the set will not be empty. Queries are numbered with integers from 1 to \(q\) inclusive.

Note that at any given time, there may be several identical intervals in the set.

Output

In \(q\) lines, output the answer to the problem after the corresponding query. The absolute or relative error must not exceed \(10^{-7}\).

Constraints

\(1 \le m \le 10^6\),

\(0 \le x \le m\),

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

\(0 \le l < r \le m\).

Samples

Input (stdin) сopy	Output (stdout) сopy
10 10 6 1 2 5 1 9 10 1 4 8 1 3 7 1 5 8 2 3 2 5 2 4 1 5 6 2 9	6.5 6.0 3.5 3.5 2.0 2.0 4.5 6.0 4.0 6.0