Ai devenit de curând angajat al unei renumite firme IT şi ai primit spre rezolvare următoarea problemă:

Să se realizeze o structură de date ce permite efectuarea eficientă a următoarelor două operaţii:
1 cheie valoare 
inserează perechea (cheie, valoare) în structura de date.
2                  
se determină valoarea cheii accesată cel mai demult şi se elimină această valoare; în cazul în care există mai multe valori asociate cheii respective, se elimină valoarea inserată cel mai demult, iar când există o singură valoare, aceasta se elimină împreună cu cheia.

Accesarea unui element se realizează la ambele operaţii.

Cerinţă

Scrieţi un program care să implementeze structura de date.

Date de intrare

Fişierul de intrare oldest.in va conţine pe prima linie un număr natural N, reprezentând numărul de operaţii ce vor fi efectuate. Pe următoarele N linii se vor afla operaţiile cerute, câte o operaţie pe o linie. Linia care descrie o operaţie va conţine fie 3 valori separate prin spaţii pentru primul tip de operaţie sub forma 1 cheie valoare, fie valoarea 2, pentru al doilea tip de operaţie.

Date de ieşire

Fişierul de ieşire oldest.out va conţine în ordinea din fişierul de intrare, valorile determinate la operaţiile de tip 2, câte una pe fiecare linie.

Restricţii

• 1 ≤ N ≤ 100 000
• Cheile si valorile sunt din intervalul [0, 1 000 000 000]
• Se garantează că la fiecare operaţie de tip 2 există cel puţin un element în structura de date.

Exemplu

oldest.in	oldest.out
8 1 1 4 1 2 3 1 1 2 2 2 1 1 6 2 2	3 4 2 6

stud. Mircea Dima

Universitatea Bucureşti

blasterzm@gmail.com