Dois Tipos de Feitiços

Flúcio está jogando um jogo de computador. Neste jogo, ele luta contra monstros usando feitiços mágicos.

Existem dois tipos de feitiços: o feitiço de fogo de poder $x$ que causa $x$ dano ao monstro e o feitiço de raio de poder $y$ que causa $y$ de dano ao monstro e dobra o dano do próximo feitiço que Flúcio lançar. Cada feitiço pode ser lançado apenas uma vez por batalha, mas Flúcio pode lançá-los em qualquer ordem.

Por exemplo, suponha que Flúcio conheça três feitiços: um feitiço de fogo de poder $5$ , um feitiço de raio de poder $1$ e um feitiço de raio de poder $8$ . Existem $6$ maneiras de escolher a ordem em que ele lança os feitiços:

primeiro, segundo, terceiro. Esta ordem causa $5 + 1 + 2*8 = 22$ de dano;
primeiro, terceiro, segundo. Esta ordem causa $5 + 8 + 2*1 = 15$ de dano;
segundo, primeiro, terceiro. Esta ordem causa $1 + 2*5 + 8 = 19$ de dano;
segundo, terceiro, primeiro. Esta ordem causa $1 + 2*8 + 2*5 = 27$ de dano;
terceiro, primeiro, segundo. Esta ordem causa $8 + 2*5 + 1 = 19$ de dano;
terceiro, segundo, primeiro. Esta ordem causa $8 + 2*1 + 2*5 = 20$ de dano.

Inicialmente, Flúcio conhece $0$ feitiços. Seu conjunto de feitiços muda $n$ vezes, cada vez ele aprende um novo feitiço ou esquece um já conhecido. Após cada mudança, calcule o dano máximo possível que Flúcio pode causar usando os feitiços que ele conhece.

Entrada:

A primeira linha contém um inteiro $n$ - o número de mudanças no conjunto de feitiços.

Cada uma das próximas $n$ linhas contém dois inteiros $tp$ e $d$ - a descrição da mudança. Se $tp_i$ for igual a $0$ , então Flúcio aprende (ou esquece) um feitiço de fogo, caso contrário, ele aprende (ou esquece) um feitiço de raio.

Se $d_i > 0$ , então Flúcio aprende um feitiço de poder $d_i$ . Caso contrário, Flúcio esquece um feitiço com poder $-d_i$ , e é garantido que ele conhecia aquele feitiço antes da mudança.

É garantido que os poderes de todos os feitiços que Flúcio conhece após cada mudança são diferentes (Flúcio nunca conhece dois feitiços com o mesmo poder).

Saída:

Após cada mudança, imprima o dano máximo que Flúcio pode causar com seu conjunto atual de feitiços.

Restrições:

$1 \leq n \leq 2*10^5$ ;
$0 \leq tp_i \leq 1$ ;
$-10^9 \leq d_i \leq 10^9$ ;

Exemplo:

Entrada	Saida
6 1 5 0 10 1 -5 0 5 1 11 0 -10	5 25 10 15 36 21

Para submeter sua solução, use esse link.