Codah ClubTrain. Submit. Improve.
Sign in
English
#00024F

Plahte

Mirko je oprao svoje plahte i uputio se na travnjak ispred svoje kuće objesiti ih kako bi se osušile. Međutim, jaka bura je iščupala jedan od stupova koji razapinju uže na kojem bi se plahte trebale osušiti, pa ih je Mirko privremeno rasprostro na travu. Travnjak možemo predstaviti beskonačnom kvadratnom mrežom, a plahte pravokutnicima koji se nalaze na njoj. Stranice svake plahte paralelne su s koordinatnim osima, a plahte se međusobno mogu preklapati. Mirko je zatim uzeo jedan od stupova i snažno ga zapiknuo u kvadrat zadan koordinatama (0, 0). U tom trenutku dogodilo se nešto neočekivano! Iz zemlje je prsnula nafta, a Mirko se od šoka onesvijestio. Dok Mirko leži u nesvijesti, nafta se širi i prlja njegove plahte. Nafta se širi brzinom od jednog kvadrata u sekundi i to sa svakog već onečišćenog kvadrata u svih osam smjerova kao na slikama dolje. Kada nafta onečisti neki kvadrat, uprlja se taj kvadrat tkanine na svim plahtama koje ga prekrivaju.

Image: dsadsa

Slike prikazuju livadu iz prvog primjera u vremenskim trenucima 0, 1 i 2.
Napišite program koji će za zadane vremenske trenutke odrediti ukupnu površinu uprljane tkanine na plahtama u tim trenucima. Vrijeme mjerimo od trenutka izbijanja nafte.


InputU prvom redu nalazi se prirodni broj N (1 ≤ N ≤ 100 000), broj plahti.U svakom od sljedećih N redova nalaze se po četiri cijela broja x1, y1, x2 i y2 (:1 000 000 ≤ x1 ≤ x2 ≤ 1 000 000), (:1 000 000 ≤ y1≤ y2 ≤ 1 000 000) odvojena s po jednim razmakom. Koordinate (x1,y1) i (x2, y2) predstavljaju dijagonalno suprotne rubne kvadrate zadane plahte. Nijedna plahta neće prekrivati kvadrat s koordinatama (0, 0). U sljedećem redu nalazi se prirodni broj M (1 ≤ M ≤ 100 000), broj vremenskih trenutaka. U sljedećem redu nalazi se M prirodnih brojeva manjih od ili jednakih 1 000 000 odvojenih razmakom. Brojevi predstavljaju trenutke (u sekundama) za koje je potrebno odrediti ukupnu površinu uprljane tkanine. Brojevi će biti navedeni u strogo rastućem redoslijedu.

OutputU M redaka potrebno je ispisati ukupnu površinu uprljane tkanine za zadana trenutke, svaku u zaseban redak, redom kojim su vremena zadana na ulazu.


ulaz
3
-2 1 1 2
1 0 2 1
-3 -3 -2 0
2
1 2
izlaz
5
15

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.