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

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

Перед розв’язанням цієї задачі прочитайте умову попередньої частини.

Для збільшення тривалості існування віруси використовують коревалюацію — процес, при якому вірус додає до свого генотипу довільний ген (необов’язково менший за попередній)

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

Вхідні дані

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

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

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

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

Вихідні дані

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

Обмеження

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

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

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

Приклади