FMI NO STRESS 13 | Dragonul IPv4

Cerință

După peripeții care ar fi prea multe ca să poată fi povestite, Ernest a ajuns să înfrunte dragonul care nu le dădea pace celor din Fólkvangr. Însă, odată învins dragonul, Ernest a aflat un secret enorm: Dragonul era Sys Admin la multinaționala la care lucra.

El se ocupa de trei tipuri de operații care manipulează o bază de date de intervale de subrețele IPv4 (să se studieze Nota din josul paginii pentru mai multe informații legate de cum se determină subrețelele în funcție de un subnet range):

1. Se dă un subnet range IPv4 de forma a.b.c.d/e (unde a.b.c.d este un prefix și e este o mască). Acesta trebuie adăugat în baza de date.
2. Se dă un subnet range IPv4 de forma a.b.c.d/e, care trebuie eliminat din baza de date (se garantează că există în baza de date).
3. Se dă o adresă IP de forma a.b.c.d. Trebuie să se afișeze Da dacă există un subnet range în baza de date care să conțină adresa IP, altfel Nu.

Ernest este acum nevoit să îl înlocuiască pe dragon, dar nu vrea să facă această muncă pe vecie, astfel încat vă roagă să scrieți un program care se ocupă de aceste operații în locul lui.

Date de intrare

Pe prima linie se află un număr întreg $n$ care reprezintă numărul total de operații.

Următoarele $n$ linii conțin una dintre următoarele operații:

• Pentru operația de tip 1: 1 a.b.c.d/e - adaugă subnetul în baza de date.
• Pentru operația de tip 2: 2 a.b.c.d/e - elimină subnetul din baza de date.
• Pentru operația de tip 3: 3 a.b.c.d - verifică dacă adresa IP se află într-un subnet din baza de date.

Date de ieșire

Pentru fiecare operație de tip 3, se va afișa pe o linie separată Da sau Nu, în funcție de rezultatul verificării.

Restricții și precizări

• $1 \leq n \leq 100\ 000$;
• Subneturile sunt date în format standard IPv4 a.b.c.d/e, unde:
  • $0 \leq a, b, c, d \leq 255$;
  • $1 \leq e \leq 30$ (masca de subrețea);
• Adresele IP din operațiile de tip $3$ sunt în format standard IPv4 a.b.c.d, unde $0 \leq a, b, c, d \leq 255$;
• Se garantează că orice operație de tip $2$ face referire la un subnet deja existent în baza de date;
• Operațiile se efectuează în ordinea în care sunt citite;
• Un subnet se poate găsi de mai multe ori în baza de date. Atunci când are loc o operație de tip $2$, se va șterge o singură apariție a acelui subnet din baza de date;
• Pentru teste în valoare de $19$ puncte, $1 \leq n \leq 5000$;
• Pentru alte teste în valoare de $24$ de puncte, $1 \leq e \leq 5$ (masca de subrețea);
• Pentru alte teste în valoare de $57$ de puncte, nu există restricții suplimentare.

Exemplul 1

stdin

5 
1 192.168.1.0/24 
1 10.0.0.0/8 
3 192.168.1.5 
2 192.168.1.0/24 
3 192.168.1.5

stdout

Da
Nu

Explicație

• Operația 1 192.168.1.0/24 adaugă subnetul 192.168.1.0/24 în baza de date.
• Operația 1 10.0.0.0/8 adaugă subnetul 10.0.0.0/8 în baza de date.
• Operația 3 192.168.1.5 verifică dacă adresa IP 192.168.1.5 este cuprinsă într-un subnet din baza de date. Rezultatul este Da, deoarece 192.168.1.5 aparține subnetului 192.168.1.0/24.
• Operația 2 192.168.1.0/24 elimină subnetul 192.168.1.0/24 din baza de date.
• Operația 3 192.168.1.5 verifică din nou adresa IP 192.168.1.5. Rezultatul este Nu, deoarece subnetul care conținea această adresă a fost eliminat.

Notă

• Șirul de biți echivalent unui IP sau adresei unui subnet se obține concatenând reprezentările binare ale primelor $4$ numere din componență, în ordinea în care apar. De exemplu:
  • $11000000.10101000.00000000.01100100 \leftarrow$ 192.168.0.100
• Se consideră că un IP a.b.c.d aparține unui subnet x.y.z.t/e dacă primii e biți din cele două șiruri de biți sunt egali.
  • $\textbf{11000000.10101000.00000001}.00000101 \leftarrow$ 192.168.1.5
  • $\textbf{11000000.10101000.00000001}.00000000 \leftarrow$ 192.168.1.0/24
  • Deoarece primii $24$ de biți sunt egali în cele două șiruri, atunci IP-ul 192.168.1.5 aparține subnetului 192.168.1.0/24.
• Disclaimer: această explicație este simplificată pentru a fi mai ușor de înțeles. Pentru mai multe detalii, accesați acest link.