Ми маємо мультимножину цілих чисел \(S\), яка спочатку порожня.

Отримавши \(Q\) запитів, обробіть їх по порядку. Кожен запит належить до одного з наступних типів.

• 1 x: вставте x у \(S\).

• 2 x c: Видаліть x із \(S\) m разів, де m = \(\mathrm{min}(c\),(кількість x, що міститься в \(S\))).

• 3 : Вивести (( максимальне значення \(S\))−( мінімальне значення \(S\))). Гарантується, що \(S\) не є порожнім, коли надається цей запит.

Обмеження

• \(1 \leq Q \leq 2\times 10^5\)
• \(0 \leq x \leq 10^9\)
• \(1 \leq c \leq Q\)
• Коли надається запит типу 3, \(S\) не є порожнім.
• Усі значення у вхідних даних є цілими числами.

Формат вхідних даних

Перший рядок містить ціле число \(Q\)

Наступні  \(Q\) рядків містять запити описаних типів.

Формат вихідних даних

У вихідний потік виведіть, в окремому рядку, для кожного запиту типу 3 відповідь.

Примітка

До прикладу 1

• 1-й запит: вставте 3 у S. S тепер {3}.
• 2-й запит: вставити 2 в S. S тепер {2,3}.
• 3-й запит: максимальне значення S = ={2,3} дорівнює 3, а мінімальне значення — 2, тому виведіть 3-2=1.
• 4-й запит: вставити 2 в S. S тепер {2,2,3}.
• 5-й запит: вставити 7 в S. S тепер {2,2,3,7}.
• 6-й запит: максимальне значення S = {2,2,3,7} дорівнює 7, а мінімальне значення — 2, тому виведіть 7-2=5.
• 7-й запит: оскільки в S є дві 2 і {min(2,3)} = 2, видаліть 2 із S двічі. S тепер {3,7}.
• 8-й запит: максимальне значення S = {3,7} дорівнює 7, а мінімальне значення — 3, тому виведіть 7-3=4.

Приклад вхідних даних

8
1 3
1 2
3
1 2
1 7
3
2 2 3
3

Приклад вихідних даних

1
5
4

Приклад вхідних даних

4
1 10000
1 1000
2 100 3
1 10

Приклад вихідних даних