Pentru o listă de numere naturale vom numi reprezentant al listei numărul care apare de cele mai multe ori în aceasta. În caz de egalitate (adică mai multe valori cu număr maxim de apariții) reprezentantul este suma acestor valori.

Cerința

Se dă o listă inițial vidă cu două tipuri de operații codificate în felul următor:

• 1 x – adăugăm un element nou cu valoarea x la sfârșitul listei și ne întrebăm ce valoare are reprezentantul după această modificare;
• 2 x – eliminăm primul element cu valoarea x din listă, ne întrebăm care este reprezentantul listei după eliminare și punem la loc elementul pe poziția lui.

Date de intrare

Pe prima linie a fișierului de intrare operatii.in se află numărul natural N de operații. Următoarele N linii conțin câte o pereche de numere naturale, separate prin spațiu, care descriu operația de efectuat: tipul operației (1 sau 2) și valoarea lui x.

Date de ieșire

Fișierul de ieșire operatii.out va conține răspunsurile la întrebările din cele N operații pe linii separate.

Restricții și precizări

• 1 ≤ N ≤ 200.000
• 0 ≤ x ≤ 200.000 pentru ambele tipuri de operații
• ordinea efectuării operațiilor este cea din fișierul de intrare
• pentru operația de tipul 2 se garantează că lista are cel puțin două elemente și că are cel puțin un element egal cu x
• Pentru 20 de puncte, 1 ≤ N ≤ 1000 și avem doar operații de tipul 1
• Pentru 23 de puncte, 1 ≤ N ≤ 1000 și avem ambele tipuri de operații
• Pentru 12 puncte, 1000 < N ≤ 200.000 și avem doar operații de tipul 1
• Pentru 45 de puncte, fără alte restricții

Exemplu:

operatii.in

6
1 10
1 20
1 20
1 10
2 20
2 10

operatii.out

10
30
20
30
10
20

Explicație

Avem 6 operații.
După prima operație lista va fi formată dintr-un singur element, 10, reprezentantul este 10.
După a doua operație lista va fi 10, 20, avem două elemente cu număr maxim de apariții, reprezentantul va fi 10 + 20 = 30.
După a treia operație, în lista 10, 20, 20 reprezentantul va fi 20.
După a patra operație, lista are elementele 10, 20, 20, 10, reprezentantul va fi 10 + 20 = 30 (fiecare valoare va fi adunată la sumă o singură dată).
La a cincea operație, dacă ștergem primul 20, lista va fi 10, 20, 10 care îl are ca reprezentant pe 10. După ce îl punem la loc, lista va fi din nou 10, 20, 20, 10.
La a șasea operație, dacă ștergem primul 10, lista va fi 20, 20, 10 care îl are ca reprezentant pe 20. După ce îl punem la loc, lista va fi din nou 10, 20, 20, 10.