Sistemul poștal de pe planeta Arcadius

Căpitanul Jean-Luc Picard, în călătoriile lui la bordul navei USS Enterprise, a descoperit pe planeta Arcadius, un sistem foarte ciudat de adrese poștale. Pe această planetă, o adresă poștală este un număr întreg pozitiv pe 32 de biți, împărțit în 4 octeți separați prin ‘.’ pentru a permite o reținere foarte ușoară a adreselor poștale. Astfel:

prima adresă poștală este 00000000.00000000.00000000.00000000 (transformat în numere întregi pozitive 0.0.0.0),
ultima adresă asignabilă este 11111111.11111111.11111111.11111111 (transformat în numere întregi positive 255.255.255.255).

Cartiere de pe planeta Arcadius

Toate aceste adrese poștale sunt împărțite în cartiere, pentru o deservire cât mai promptă a locuitorilor planetei. Astfel un cartier de pe planeta Arcadius constă din toate acele case care au primii x biți din adresa poștală comuni.

Partea de cartier pentru o anumită adresă poștală se specifică printr-o mască de cartier. Astfel, de exemplu pentru o mască de cartier /13, înseamnă că primii 13 biți din acele adrese poștale sunt de cartier, iar următorii 19 biți sunt pentru adrese poștale care fac parte din cartier.

Aceste măsți de cartier sunt date prin 2 metode:

O notație prin care se specifică numărul de biți de cartier (De exemplu /13)
O notație zecimală (Notația de mai sus se transformă într-o adresă poștală) (În exemplul nostru /13 =11111111.11111000.00000000.00000000=255.248.0.0)

Masca de cartier este identică pentru toate casele aflate în același cartier.

Adresa cartierului

Fiecare casă se află într-un anumit cartier, determinat de adresa poștală și de masca de cartier pe care o are. Adresa de cartier se calculează astfel:

adresa_cartier=adresa_poștală & masca_de_cartier

De exemplu o casă cu adresa poștală 89.67.45.13 și cu masca de cartier /13 se află în cartierul: 89.64.0.0/13

Am calculat astfel:

89.67.45.13	&
255.248.0.0	=
89.64.0.0	89.64.0.0/13

sau (transformat pe biți)

01011001.01000011.00101101.00001101	&
11111111.11111000.00000000.00000000	=
01011001.01000000.00000000.00000000	89.64.0.0/13

Poștași de pe planeta Arcadius

Poștașii de pe planeta Arcadius au o modalitate diferită de distribuire a coletelor poștale față de cei de pe planeta Pământ. Poștașul este singurul care poate avea mai multe adrese poștale, întrucât deservește mai multe cartiere.

Fiecare poștaș are câte o adreșă poștală din fiecare cartier pe care le deservește. Astfel dacă un poștaș are următoarele adrese poștale

89.45.67.12/24
141.85.37.11/24

Atunci el deservește cartierele:

89.45.67.0/24
141.85.37.0/24

Pentru ca un postaș să distribuie un colet cu o anumită adresă poștală destinație, acea adresă poștală trebuie să facă parte dintr-un cartier pe care poștașul îl deservește.
Procesul de trimitere a coletelor, se realizează după următorii pași :

Se parcurge lista cartierelor de la masca cea mai mare(/32) la masca cea mai mică(/0) și se efectuează următorul test:
```
 adresa_dest_colet & masca_de_cartier_i==adresa_de_cartier_i
```
- masca_de_cartier_i=masca de cartier pentru al i-ulea cartier deservit de poștaș
- adresa_de_cartier_i=adresa de cartier pentru al i-ulea cartier deservit de poștaș
- adresa_dest_colet=adresa destinașie a coletului care trebuie transmis mai departe.

Dacă testul este validat, atunci acel colet va fi livrat în cartierul i.

Astfel, de exemplu pentru cazul de mai sus, dacă

poștașul trebuie să distribuie un colet către adresa poștală 141.85.37.56, atunci el îl va duce în cartierul al doilea.
poștașul trebuie să distribuie un colet către adresa poștală 11.23.45.67, atunci el va arunca coletul, căci adresa destinație nu face parte din nici un cartier pe care îl deservește.

Cerințe

Fiind dat un poștaș cu M cartiere pe care le deservește și N colete, va trebui să specificați pentru fiecare colet în ce cartier se va duce.

Formatul de intrare al datelor

$M$

$A_{1}$

$B_{1}$

$C_{1}$

$D_{1}$

$N_{1}$

…

$A_{M}$

$B_{M}$

$C_{M}$

$D_{M}$

$N_{M}$

$N$

$X_{1}$

$Y_{1}$

$Z_{1}$

$T_{1}$

…

$X_{N}$

$Y_{N}$

$Z_{N}$

$T_{N}$

A_i= primul octet al adresei poștale din cartierul i deservit de poștaș

B_i= al doilea octet al adresei poștale din cartierul i deservit de poștaș

C_i= al treilea octet al adresei poștale din cartierul i deservit de poștaș

D_i= ultimul octet al adresei poștale din cartierul i deservit de poștaș

N_i= masca de cartier pentru cartierul i deservit de poștaș

Adresa poștașului din cartierul i este: A_i.B_i.C_i.D_i/N_i

X_j= primul octet al adresei poștale pentru coletul j

Y_j= al doilea octet al adresei poștale pentru coletul j

Z_j= al treilea octet al adresei poștale pentru coletul j

T_j= ultimul octet al adresei poștale pentru coletul j

Coletul j are adresa poștală destinație X_j.Y_j.Z_j.T_j

Formatul de ieșire al datelor

N linii cu numărul cartierului unde coletul i va fi distribuit sau -1, dacă nu există cartier în care coletul va fi distribuit.

Restricții

0<M<1000
0<N<MAXINT (cel mai mare număr întreg)
0<=A_i,B_i,C_i,D_i,X_j,Y_j,Z_j,T_j<=255
0<=N_i<=32
0<=i<M (numerotarea cartierelor începe de la 0)
0<=j<N (numerotarea coletelor începe de la 0)
Puteți folosi orice algoritm de sortare.

Exemple

Intrare

2
89 45 67 12 24
141 85 37 11 24
2
141 85 37 56
11 23 45 67

Ieșire

1
-1

Poștașul deservește următoarele cartiere:

89.45.67.0/24
141.85.37.0/24

Primul colet se duce în cartierul 141.85.37.0/24, întrucât

141.85.37.56 & 255.255.255.0 ==141.85.37.0

Cel de-al doilea colet va fi aruncat, întrucât nu există nici un cartier care să satisfacă condiția.

Intrare

3
10 23 45 12 24
10 23 45 13 25
10 24 45 12 24
3
10 23 45 196
10 23 46 1
10 23 45 1

Ieșire

0
-1
1

Poștașul deservește următoarele cartiere:

10.23.45.0/24
10.23.45.0/25
10.24.45.0/24

Primul colet se va duce în primul cartier pentru că

10.23.45.196 & 255.255.255.0 ==10.23.45.0

Al doilea colet va fi aruncat.

Al treilea colet se va duce în cartierul 10.23.45.0/25, pentru că are masca de cartier cea mai mare, comparativ cu 10.23.45.0/24.

Autor: Octavian Rânciog

Data: 22.11.2010