Sim-4-1 | perle

This was the problem page during the contest. Access the current page here.
Time limit: 0.5s Memory limit: 256MB Input: Output:

La ora de arte a Academiei Eden, Anya are de construit un șirag de perle. Inițial, profesorul Henderson îi dă Anyei două
numere, QQ și KK. Apoi, profesorul îi dă QQ instrucțuni Anyei, de următoarele tipuri:

  • Adăugare: Anya trebuie să adauge o perlă cu prețul xx în capătul din dreapta al șiragului.
  • Ștergere: Anya trebuie să scoată perla aflată în capătul din dreapta al șiragului, și să spună ce preț a avut aceasta.
  • Ștergere specială: Anya trebuie să scoată (printr-un procedeu de spargere ce implică un ciocan) a KK-a cea mai puțin valoroasă perlă din șirag, și să spună ce preț a avut aceasta. O perlă AA este considerată mai valoroasă decât o altă perlă BB dacă AA are un preț mai mare ca BB, sau dacă A are același preț ca BB, dar a fost adăugată în șirag la un moment de timp ulterior adăugării perlei B în șirag.

Dacă Anya nu poate efectua o operație de ștergere (pentru că șiragul este gol), sau de ștergere specială (pentru că nu există cel puțin KK perle în șirag), se consideră că operația nu poate fi efectuată, iar Anya nu scoate nicio perlă din șirag.

La final, Anya trebuie să prezinte în fața clasei șiragul de perle obținut în urma efectuării celor QQ operații.

Date de intrare

Pe prima linie se află 22 numere naturale QQ și KK, separate printr-un spațiu, cu semnificația din enunț.
Pe următoarele QQ linii se află cele QQ operații pe care Anya trebuie să le efectueze, codificate astfel:

  • 1 x1 \ x: adăugarea unei perle cu prețul xx;
  • 22: ștergere;
  • 33: ștergere specială.

Date de ieșire

Afișați, în ordine, pentru fiecare operație de ștergere sau ștergere specială, câte o linie conținând un număr xx reprezentând prețul perlei scoase din șirag în urma operației respective. În cazul în care operația nu poate fi efectuată, valoarea lui xx va fi 1−1.
Pe ultima linie afișați, în ordine, de la stânga la dreapta, prețurile perlelor din șiragul obținut după efectuarea celor QQ operații.

Restricții și precizări

  • 1Q,K500 0001 \leq Q, K \leq 500 \ 000
  • Prețurile perlelor adăugate sunt numere naturale pozitive mai mici sau egale decât 1 000 000 0001 \ 000 \ 000 \ 000.
  • Se garantează că șiragul obținut după efectuarea celor QQ operații conține cel puțin o perlă.
    # Punctaj Restricții
    1 8 1Q1 0001 \leq Q \leq 1 \ 000 și toate perlele adăugate în șirag au prețuri distincte.
    2 4 1Q1 0001 \leq Q \leq 1 \ 000
    3 12 K=1K = 1, și toate perlele adăugate în șirag au prețuri distincte.
    4 8 K=1K = 1
    5 20 Nu există operații de tip 22 (ștergere), și toate perlele adăugate în șirag au prețuri distincte.
    6 15 Nu există operații de tip 22 (ștergere).
    7 19 Toate perlele adăugate în șirag au prețuri distincte.
    8 14 Fără restricții suplimentare

Exemplu

stdin

10 2
1 2
1 3
1 5
1 2
1 4
2
1 1
3
2
1 6

stdout

4
2
1
3 5 2 6

Explicație

După primele 55 operații, toate de adăugare, șiragul are forma 2 3 5 2 42 \ 3 \ 5 \ 2 \ 4.
Operația 66 este o operație de ștergere, iar perla eliminată are prețul 44. Șiragul are acum forma 2 3 5 22 \ 3 \ 5 \ 2.
Operația 77 este o operație de adăugare, iar șiragul capătă forma 2 3 5 2 12 \ 3 \ 5 \ 2 \ 1.
Operația 88 este o operație de ștergere specială, iar perla eliminată are prețul 22. Fiindcă prima perlă cu preț 22 era a doua cea mai puțin valoroasă și a fost eliminată, șiragul are acum forma 3 5 2 13 \ 5 \ 2 \ 1.
Operația 99 este o operație de ștergere, iar perla eliminată are prețul 11. Șiragul are acum forma 3 5 23 \ 5 \ 2.
Operația 1010 este o operație de adăugare, iar șiragul capătă forma 3 5 2 63 \ 5 \ 2 \ 6, pe care o și afișăm.

Log in or sign up to be able to send submissions!