Рома и Виталя придумали следующую игру: на скорость прибавлять и вычитать из числа степени двойки, а после каждой операции считать число единиц в двоичной записи этого числа. Кто быстрее и правильнее, тот и победил.
Вам предстоит помочь им: написать программу, с помощью которой они могли бы проверить свои расчеты.
Правила игры следующие:
Гарантируется, что в любой момент времени число P не может быть отрицательным.
На первой строке задано целое число N (1 ≤ N ≤ 105) - количество операций.
На следующих N строках заданы операции, где каждая операция задается одной из двух строк: «add S» или «sub S», где S (0 ≤ S ≤ 105) — это целое число.
Операция «add S» означает, что нужно прибавить к числу P двойку в степени S.
Операция «sub S» означает, что нужно вычесть из числа P двойку в степени S.
Для каждого из N запросов выведите на одной строке число — количество единиц в двоичной записи числа P после выполнения данной операции.
2
add 1
sub 1
1
0
4
add 2
add 8
sub 3
sub 0
1
2
6
7
