Виталя и Рома

Рома и Виталя придумали следующую игру: на скорость прибавлять и вычитать из числа степени двойки, а после каждой операции считать число единиц в двоичной записи этого числа. Кто быстрее и правильнее, тот и победил.

Вам предстоит помочь им: написать программу, с помощью которой они могли бы проверить свои расчеты. Правила игры следующие:

1. В начале игры число P равно нулю.
2. За всю игру совершается N операций.
3. Каждая операция – прибавление к числу P или вычитание из числа P числа 2^S.
4. После выполнения каждой операции необходимо вывести число единиц в двоичной записи числа P.

Гарантируется, что ни в какой момент времени число P не может оказаться отрицательным.

Входные данные

Первая строка входного файла INPUT.TXT содержит целое число N (1 ≤ N ≤ 10⁵) – количество операций. На следующих N строках заданы операции, где каждая операция задается одной из двух строк: «add S» или «sub S», где S (0 ≤ S ≤ 10⁵) – целое число.

Операция «add S» означает, что к числу P нужно прибавить 2^S.

Операция «sub S» означает, что из числа P нужно вычесть 2^S.

Выходные данные

Для каждого из N запросов в выходной файл OUTPUT.TXT в отдельной строке выведите количество единиц в двоичной записи числа P после выполнения данной операции.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]