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

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