Diferențe pentru problema/extraterestri între reviziile #11 si #12

== include(page="template/taskheader" task_id="extraterestri") ==

O invazie de $N$ farfurii zburătoare (denumite uzual OZN) dă bătăi de cap autorităților. În fiecare astfel de OZN se află extratereștri care au ca misiune distrugerea planetei noastre. Radarul care a detectat invazia are un ecran similar cu planul [$XOY$]. Fiecare OZN este reprezentat pe ecran printr-un segment de dreaptă.
Pentru anihilarea OZN-urilor, autoritățile dispun de $K$ arme laser. Armele sunt poziționate pe sol (ilustrat pe ecranul radarului prin axa [$OX$]). Fiecare armă emite o rază laser, ilustrată pe ecran printr-o paralelă cu axa [$OY$]. Dacă o rază laser intersectează segmentul de pe ecranul radarului corespunzător unui OZN, raza va omorî toți extratereștrii aflați în OZN-ul respectiv.

O invazie de *N* farfurii zburătoare (denumite uzual OZN) dă bătăi de cap autorităților. În fiecare astfel de OZN se află extratereștri care au ca misiune distrugerea planetei noastre. Radarul care a detectat invazia are un ecran similar cu planul [$XOY$]. Fiecare OZN este reprezentat pe ecran printr-un segment de dreaptă.
 
Pentru anihilarea OZN-urilor, autoritățile dispun de *K* arme laser. Armele sunt poziționate pe sol (ilustrat pe ecranul radarului prin axa [$OX$]). Fiecare armă emite o rază laser, ilustrată pe ecran printr-o paralelă cu axa [$OY$]. Dacă o rază laser intersectează segmentul de pe ecranul radarului corespunzător unui OZN, raza va omorî toți extratereștrii aflați în OZN-ul respectiv.
 

Din păcate, în preajmă se află doar un militar specializat în arme laser, așa că autoritățile doresc să știe exact ce armă trebuie să folosească acesta pentru a distruge cât mai mulți extratereștri.
h2. Cerință

h2. Date de intrare

Fișierul de intrare $extraterestri.in$ conține pe prima linie două numere naturale separate prin spațiu $N$ $K$ reprezentând numărul de OZN-uri și respectiv numărul de arme laser. Pe următoarele $N$ linii sunt descrise cele $N$ OZN-uri, câte unul pe linie. Un OZN este descris prin $5$ numere naturale separate prin câte un spațiu $x1$ $y1$ $x2$ $y2$ [$nr$], reprezentând în ordine coordonatele capetelor segmentului corespunzător $(x1, y1)$, $(x2, y2)$, iar $nr$ – numărul de extratereștri din el. Pe ultima linie se găsesc $K$ numere naturale $a1 a2 a3 ... aK$, separate prin câte un spațiu, reprezentând coordonatele pe axa $OX$ (abscisele) unde sunt amplasate armele laser.

Fișierul de intrare $extraterestri.in$ conține pe prima linie două numere naturale separate prin spațiu *N* *K* reprezentând numărul de OZN-uri și respectiv numărul de arme laser. Pe următoarele *N* linii sunt descrise cele *N* OZN-uri, câte unul pe linie. Un OZN este descris prin $5$ numere naturale separate prin câte un spațiu *x1* *y1* *x2* *y2* *nr*, reprezentând în ordine coordonatele capetelor segmentului corespunzător $([*x1*], [*y1*])$, $([*x2*], [*y2*])$, iar *nr* – numărul de extratereștri din el. Pe ultima linie se găsesc *K* numere naturale *a1 a2 a3 ... aK*, separate prin câte un spațiu, reprezentând coordonatele pe axa $OX$ (abscisele) unde sunt amplasate armele laser.

h2. Date de ieșire

Fișierul de ieșire $extraterestri.out$ va conține $K$ linii. Pe linia $i$ va fi scris numărul total de extratereștri care pot fi distruși cu arma [$i$], considerând armele numerotate în ordinea în care acestea apar în fișierul de intrare.

Fișierul de ieșire $extraterestri.out$ va conține *K* linii. Pe linia *i* va fi scris numărul total de extratereștri care pot fi distruși cu arma *i*, considerând armele numerotate în ordinea în care acestea apar în fișierul de intrare.

h2. Restricții

* $1 ≤ N ≤ 20 000$
* $1 ≤ K ≤ 20 000$
* $1 ≤ orice coordonată din fișierul de intrare ≤ 2 000 000$
* $1 ≤ nr ≤ 100$, pentru orice OZN
* $x1 < x2$, pentru orice OZN

* 1 ≤ *N* ≤ 20 000
* 1 ≤ *K* ≤ 20 000
* 1 ≤ orice coordonată din fișierul de intrare ≤ 2 000 000
* 1 ≤ *nr* ≤ 100$, pentru orice OZN
* *x1* < *x2*, pentru orice OZN

* Pe ecranul radarului segmentele ce descriu navele se pot intersecta.
* Dacă raza laser trece prin unul dintre capetele unui OZN atunci acesta este distrus.

* Pentru $50%$ dintre testele de intrare $1 ≤ N*K ≤ 10 000 000$

* Pentru $50%$ dintre testele de intrare 1 ≤ [*N*]*[*K*] ≤ 10 000 000

h2. Exemplu