Hi CF! I find problem sqrt decomposition. Sorry my english isn't well.

Roma and Vitala came up with the following game: add and subtract from the number of power two, and after each operation count the number of units in the binary number of this number. Who is faster and more correct, he won.

You have to help them: write a program with which they could check their calculations. The rules of the game are:

At the beginning of the game, the number P is zero. For the entire game, N operations are performed. Each operation is the addition to the number P or subtraction from the number P of the number 2S. After performing each operation, it is necessary to output the number of units in the binary representation of P. It is guaranteed that at any time the number P can not be negative.

Input

The first line of the input file INPUT.TXT contains an integer N (1 ≤ N ≤ 10⁵) — the number of operations. The following N lines specify operations where each operation is specified by one of two lines: "add S" or "sub S", where S (0 ≤ S ≤ 10⁵) is an integer.

The "add S" operation means that 2 ^S must be added to the P number.

The operation "sub S" means that the number P should subtract 2 ^S.

Output

For each of the N requests to the output file OUTPUT.TXT on a separate line, output the number of units in the binary record of the number P after performing this operation.

test

4 add 2 add 8 sub 3 sub 0 output: 1 2 6 7