==Include(page="template/taskheader" task_id="geamuri")==
==Include(page="template/taskheader" task_id="geamuri")==
Enervat de atatea probleme de pe InfoArena care nu-i ieseau si de atatea runde de GInfo cu probleme indentice, Geminski isi ia pistolul si pleaca sa impuste niste geamuri. Ajuns la fata locului, constata ca se afla in fata a $N$ geamuri dreptungiulare, fiecare bine delimitat in raport cu sistemul cartezian ortogonal. Geminski are la el $M$ gloante. Cand se decide sa traga un glont, el isi stabileste un punct bine delimitat in raport cu sistemul cartezian ortogonal, dupa care trage! Geminski are totusi unele limitari, astfel ca nu poate trage decat din puncte cu coordonate cuprinse intre $1$ si {$C$}. Fiecare geam ce contine acel punct se va sparge. Geminski vrea ca atunci cand trage cu glontul al {$i$}-lea, sa sparga exact $K{~i~}$ geamuri.
h2. Cerinta
Scrieti un program care sa determine pentru fiecare glont pe care il trage Geminski din cate pozitii il poate trage astfel incat sa sparga exact $K{~i~}$ geamuri.
h2. Date de intrare
Primele doua linii ale fisierului de intrare $geamuri.in$ contin numarele intregi {$C$}, respectiv {$N$}. Urmatoarele $N$ linii contin cate $4$ numere intregi $x{~0~}, y{~0~}, x{~1~}, y{~1~}$ reprezentand coordonatele geamurilor date prin coltul stanga-jos si dreapta-sus ({$1 ≤ x{~0~} ≤ x{~1~} ≤ C, 1 ≤ y{~0~} ≤ y{~1~} ≤ C$}). Urmatoare linie contine numarul intreg {$M$}, iar urmatoarele $M$ linii numerele $K{~i~}$ ({$1 ≤ i ≤ M$}), cate unul pe linie.
h2. Date de iesire
Fisierul de iesire $geamuri.out$ va contine $M$ linii, cu numarul cautat pe fiecare linie.
h2. Restrictii si precizari
* $1 ≤ C ≤ 1024$
* $0 ≤ K{~i~} ≤ N ≤ 50.000$
* $1 ≤ M ≤ 50.000$
* Geamurile se pot suprapune
h2. Exemplu
table(example). |_. geamuri.in |_. geamuri.out |
| 8
3
2 2 5 4
5 3 6 8
4 4 7 6
2
3
2
| 1
7 |
h3. Explicatii
Primul glont poate fi tras doar din $({*5, 4*})$
Al doilea din coordonatele {$({*4, 4*}), ({*5, 3*}), ({*5, 5*}), ({*5, 6*}), ({*6, 4*}), ({*6, 5*}), ({*6, 6*})$}
==Include(page="template/taskfooter" task_id="geamuri")==
==Include(page="template/raw")==
Geamuri
Enervat de atatea probleme de pe InfoArena care nu-i ieseau si de atatea runde de GInfo cu probleme indentice, Geminski isi ia pistolul si pleaca sa impuste niste geamuri. Ajuns la fata locului, constata ca se afla in fata a N geamuri dreptungiulare, fiecare bine delimitat in raport cu sistemul cartezian ortogonal. Geminski are la el M gloante. Cand se decide sa traga un glont, el isi stabileste un punct bine delimitat in raport cu sistemul cartezian ortogonal, dupa care trage! Geminski are totusi une limitari, astfel ca nu poate trage decat din puncte cu coordonate cuprinse intre 1 si C. Fiecare geam ce contine acel punct se va sparge. Geminski vrea ca atunci cand trage cu glontul al i-lea, sa sparga exact K[i] geamuri.
h2. Cerinta
Scrieti un program care sa determine pentru fiecare glont pe care il trage Geminski din cate pozitii il poate trage astfel incat sa sparga exact K[i] geamuri.
Date intrare
Primele doua linii ale fisierului de intrare geamuri.in contin numarele intregi C, respectiv N. Urmatoarele N linii contin cate 4 numere intregi x[0], y[0], x[1], y[1], reprezentand coordonatele geamurilor date prin coltul stanga-jos si dreapta-sus (1 <= x[0] <= x[1] <= C, 1 <= y[0] <= y[1] <= C). Urmatoare linie contine numarul intreg M, iar urmatoarele M linii numerele K[i] (1 <= i <= M), cate unul pe linie.
h2. Date de Iesire
Fisierul de iesire geamuri.out va contine M linii, cu numarul cautat pe fiecare linie.
h2. Restrictii si precizari
S 1 <= C <= 1024
S 0 <= K[i] <= N <= 50.000
S 1 <= M <= 50.000
S Geamurile se pot suprapune
geamuri.in geamuri.out Explicatie
8 1 Primul glont poate fi tras doar din (5, 4), iar al doilea din coordonatele (4, 4), (5, 3), (5, 5), (5, 6), (6, 4), (6, 5), (6, 6).
3 7
2 2 5 4
5 3 6 8
4 4 7 6
2
3
2
==Include(page="template/taskfooter" task_id="geamuri")==
