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

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

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

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

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

Input

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

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

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

Output

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

Examples