Реплікація. Частина 1

Обмеження: 2 сек., 512 МіБ

Реплікація — процес створення двох дочірніх молекул ДНК на основі батьківської молекули. Реплікацію ДНК здійснює складний комплекс, що складається з 15-20 різних білків-ферментів. Для реплікації віруси постійно ділять свою ДНК, тим самим скорочуючи її.

Також кожен вірус має генетичне дерево.

Генетичне дерево — це двійкове дерево, яке задовольняє властивість: якщо ген \(b\) є вузлом-нащадком гена \(a\), то довжина гена \(a\) більша або рівна за довжину гена \(b\).

При видаленні кореневого гена з дерева вірус замінює його останнім геном в ієрархії, видаляє і проводить операцію заміщення. Останнім в ієрархії є крайній справа ген найнижчого рівня дерева.

Заміщення — процес обміну в дереві короткого гена з більш довгим за умови, що більш короткий ген вище в ієрархії. Батьківський коротший ген обмінюється із синівським довшим (якщо є два синівські гени, які довші за батьківський, то обмін відбувається з довшим із них). Операції заміщення відбуваються доти, поки вся ієрархія не задовольнятиме властивість генетичного дерева.

При додаванні гена він додається останнім в ієрархії і також відбувається операція заміщення. Якщо нижній рівень дерева повний, то новий ген додається на новий найнижчий рівень.

Ваше завдання — емулювати поведінку генотипу вірусу.

Формально генетичне дерево — це двійкова купа, потрібно емулювати операції з нею.

Спочатку існує лише один кореневий ген. Задано запити на додавання гена й видалення кореневої вершини генетичного дерева.

Після кожного запиту виведіть кількість операцій заміщення, виконаних у процесі операції, а також нове значення (розмір гена) кореня дерева.

Вхідні дані

У першому рядку задано два цілих числа \(n\) і \(p\) — кількість запитів та розмір початкового гена.

Кожен із наступних \(n\) рядків містять один із запитів

• \(\texttt{+}\ a_i\) — додати ген розміром \(a_i\),

• - — видалити кореневий ген.

Вихідні дані

Для кожної операції в окремому рядку виведіть два числа через пробіл — кількість заміщень, а також розмір кореневого гена після виконання операції.

Обмеження

\(1 \le n \le 10^5\),

\(1 \le a_i < p \le 10^9\),

у цій задачі гарантується, що кожен наступний доданий ген буде коротшим за попередній,

усі значення довжин генів унікальні,

дерево ніколи не стане пустим.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 43 + 23 + 15 - + 4 -	0 43 0 43 1 23 0 23 1 15