Мінімальна функція#12813

Мінімальна функція

2 seconds
256 megabytes
Hard

Спочатку є функція f(x)=0.

Потрібно виконати операції. Операції мають два типи:

  1. «1 a b». Функція оновиться. f(x)_{new}=f(x)_{old}+|x-a|+b.

  2. «2». Знайдіть та такі, що  — мінімальне. Якщо таких декілька, то знайдіть мінімальне .

Input

Перший рядок містить одне ціле число (1 \leq q \leq 2 \cdot 10^5).

Кожен з наступних рядків описує операцію. У першому типі та (-10^9 \leq a, b \leq 10^9).

Гарантується, що перша операція першого типу.

Output

Для кожного запиту виведіть два цілі числа та .

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading