Не більше половини

Limits: 4 sec., 512 MiB

Зеник і Марічка люблять працювати з проміжками. Сьогодні вони розв’язують наступну задачу.

Нехай задано набір числових проміжків та одне число $x$. Завдання — знайти довжину найдовшого проміжку, який:

• повністю лежить в межах $[0...m]$;

• містить точку $x$ (можливо, на межах);

• довжина його перетину з кожним із заданих проміжків не перевищує половини довжини відповідного проміжку.

Марічка з легкістю розв’язує таку задачу, однак Зеник дещо ускладнив її. Початково, набір проміжків є пустим. Далі потрібно виконати $q$ запитів, кожен з яких може бути одного з двох видів:

1. Додати новий проміжок $[l, r]$ до набору.

2. Видалити з набору проміжок, який був доданий у запиті з номером $p$.

Після кожного запиту потрібно вивести одне число — довжину найдовшого проміжку, описаного вище.

Input

У першому рядку задано три цілих числа $m$, $q$ та $x$.

У наступних $q$ рядках описано запити. Перше число описує тип запиту (1 або 2).

У випадку запиту першого типу, в тому самому рядку задано два цілих числа $l$ та $r$ — межі проміжку, який потрібно додати.

У випадку запиту другого типу, задано одне число $p$ — номер запиту, на якому було додано проміжок, який слід видалити. Гарантовано, що цей проміжок ще не був видалений, а також що після його видалення набір не буде пустим. Запити пронумеровані цілими числами від 1 до $q$ включно.

Зауважте, що в будь-який момент часу може існувати декілька однакових проміжків в наборі.

Output

У $q$ рядках виведіть відповідь на задачу після відповідного запиту. Абсолютна або відносна похибка не повинна перевищувати $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