Fermierul Ion are idee originala: sa infiinteze pe teritoriul fermei sale
gradina zoologica "Madame Tussaud". Si fiindca deja are o colectie
impresionanta de animale de ceara, in marime naturala, raspandite pe teritoriul
fermei sale acest lucru nu e foarte dificil.
In acest scop a luat harta fermei sale, pe care este fixat un sistem de coordonate
si pe care sunt marcate pozitiile animalelor pe teritoriul fermei. Fiecare animal
este plasat pe teritoriul fermei într-un punct de coordonate întregi
si nu poate fi mutat fara a-l deteriora.
Gradina zoologica pe care o proiecteaza Ion va avea forma unui dreptunghi având
laturile paralele cu axele de coordonate si Ion ar dori ca aceasta sa contina
cat mai multe animale.
Înainte de a începe constructia, fermierul face un studiu, pentru
a gasi pozitia optima de amplasare a gradinii zoologice. Pentru aceasta, el
si-a ales câteva pozitii unde ar putea sa construiasca gradina zoologica.
Pentru fiecare dintre ele, ar dori sa stie câte animale dintre cele N
pe care le are se afla în interiorul gradinii (sau pe marginile acesteia).
Cerinta
Scrieti un program care sa determine pentru fiecare amplasare
posibila a gradinii zoologice numarul de animale care s-ar afla in interiorul
acesteia (sau pe margini).
Date de intrare
Prima linie a fisierului de intrare zoo.in
contine numarul întreg N,
reprezentând numarul de animale. Fiecare dintre urmatoarele N
linii contine coordonatele x
si y ale unui animal,
separate prin spatiu. Urmatoarea linie contine numarul întreg M,
reprezentând numarul posibilitatilor de amplasare a gradinii zoologice.
Pe fiecare dintre urmatoarele M
linii se afla patru numere întregi separate prin spatii: x1
y1 x2 y2 unde (x1,y1)
reprezinta coordonatele coltului stânga-jos al gradinii zoologice, iar
(x2,y2) reprezinta coordonatele
coltului dreapta-sus.
Date de iesire
În fisierul zoo.out
veti afisa, pentru fiecare posibilitate de amplasare a gradinii zoologice, numarul
de animale aflate în interiorul sau pe marginile acesteia.
Restrictii
1 <= N <= 16 000
1 <= M <= 100 000
Coordonatele fiecarui animal si ale colturilor fiecarui dreptunghi sunt
numere întregi din intervalul [-2
000 000 000 , 2 000 000 000].
Pot exista mai multe animale în acelasi punct.
x1<x2 si y1<y2
pentru fiecare dreptunghi descris în fisierul de intrare