Rezolvare PBinfo #2218

Domnul Set vă oferă – ce altceva? – o mulțime de numere naturale A, inițial vidă. Pe mulțimea A se definesc următoarele operații:

• 1 x – introduce valoarea x în A (dacă x este deja în A, atunci operația nu se efectuează)
• 2 x – interogare: care valoare din A este cea mai mică, dar mai mare sau egală cu x (dacă o asemenea valoare nu există, sau dacă A este vidă, se va afișa -1)
• 3 x y – șterge din A toate numerele din intervalul [x, y].

Cerința

Dându-se N operații, trebuie să afișați răspunsul la fiecare operație de tip 2.

Date de intrare

Fișierul de intrare set.in conține pe prima linie N. Pe următoarele N linii sunt date cele N operații.

Date de ieșire

În fișierul de ieșire set.out se vor afișa pe câte o linie răspunsurile la operațiile de tip 2.

Restricții și precizări

• 1 ≤ N ≤ 200 000
• Va exista cel puțin o operație de tip 2
• 0 ≤ x ≤ y ≤ 2 000 000 000

Exemplu:

set.in

15
1 10
1 20
1 30
1 40
1 50
1 60
1 70
1 80
1 90
2 39
2 70
3 30 100
2 30
1 3
2 2

set.out

40
70
-1
3

Explicație

Se introduc mai întâi în A valorile 10, 20, 30, 40, 50, 60, 70, 80, 90. Urmează:
Întrebarea (2, 39): Numărul cel mai mic mai mare sau egal cu 39 este 40.
Întrebarea (2, 70): Numărul cel mai mic mai mare sau egal cu 70 este 70.
Operația (3 30 100): Se șterg numerele din intervalul [30,100], adică se șterg valorile 30, 40, 50, 60, 70, 80, 90.
Întrebarea (2 30): Nu există număr mai mare sau egal cu 30, deci afișăm -1.
Operația (1 3): Se introduce 3 în mulțime.
Întrebarea (2, 2): Numărul cel mai mic mai mare sau egal cu 2 este 3.