Fișierul intrare/ieșire	extraterestri1.in, extraterestri1.out	Sursă	Cerc informatică Vianu
Autor	Cristian Frâncu | Dana Lica	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.1 sec	Limită de memorie	1280 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Extraterestri1 (clasa a 8-a)

Notă: această problemă are exact același enunț ca problema extraterestri. Ceea ce s-a modificat este memoria, care a fost mult limitată.

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.

Cerință

Ajutați autoritățile să determine numărul de extratereștri care pot fi anihilați cu fiecare armă din dotare.

Date de intrare

Fișierul de intrare extraterestri1.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.

Date de ieșire

Fișierul de ieșire extraterestri1.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.

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
• 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

Exemplu

extraterestri1.in	extraterestri1.out	Explicații
5 3 1 1 3 2 2 2 3 4 1 3 6 5 8 5 8 5 1 7 1 6 6 2 7 4 1 3 7 5	5 15 6	Arma care emite din punctul (3,0) doboară farfuriile reprezentate de segmentele (1,1)(3,2) și (2,3)(4,1) distrugând în total 5 extratereștri. Arma care emite din punctul (7,0) doboară farfuriile reprezentate de segmentele (5,1)(7,1), (6,2)(7,4) și (6,5)(8,5) distrugând în total 15 extratereștri. Arma care emite din punctul (5,0) doboară farfuria reprezentată de segmentul (5,1)(7,1) și distruge 6 extratereștri.