Plahte

Ο Mirko έπλυνε τα σεντόνια του και πάει να τα κρεμάσει για να στεγνώσουν μπροστά στο σπίτι του. Ωστόσο, δυνατοί άνεμοι τράβηξαν την απλώστρα από το έδαφος, έτσι ο Mirko άπλωσε προσωρινά τα σεντόνια στο γρασίδι.

Το πεδίο με γρασίδι μπορεί να μοντελοποιηθεί από ένα άπειρο τετραγωνικό πλέγμα, όπου κάθε μοναδιαίο τετράγωνο αντιπροσωπεύεται από ένα ζεύγος συντεταγμένων. Τα σεντόνια είναι ορθογώνια στο πλέγμα με πλευρές παράλληλες προς τους άξονες συντεταγμένων. Σεντόνια μπορεί να επικαλύπτονται.

Σε μια προσπάθεια να ξαναβάλει το σκοινί του για άπλωμα, ο Mirko χτύπησε ένα κοντάρι στο έδαφος στις συντεταγμένες ~(0,\,0)~. Ακολούθησε μια εντελώς απροσδόκητη τροπή των γεγονότων. Πετρέλαιο ξεπήδησε από το έδαφος και έκανε τον Mirko να λιποθυμήσει. Ενώ ο Mirko βρισκόταν αναίσθητος, το πετρέλαιο εξαπλωνόταν, λερώνοντας τα σεντόνια του.

Ο χρόνος μετριέται από τη στιγμή που το πετρέλαιο αρχίζει να απλώνεται - τη στιγμή μηδέν καλύπτεται μόνο το τετράγωνο ~(0,\,0)~ με πετρέλαιο. Το πετρέλαιο απλώνεται με ταχύτητα ενός τετραγώνου ανά δευτερόλεπτο και στις οκτώ κατευθύνσεις, όπως φαίνεται στο το παρακάτω σχήμα. Όταν το πετρέλαιο εισέρχεται σε ένα τετράγωνο, λερώνει αυτό το τετράγωνο υφάσματος σε όλα τα σεντόνια που καλύπτουν το τετράγωνο.

Το πεδίο με γρασίδι από το πρώτο παράδειγμα μετά από μηδέν, ένα και δύο δευτερόλεπτα.

Γράψτε ένα πρόγραμμα που, λαμβάνοντας υπόψη ~M~ σημεία στο χρόνο, να υπολογίζει τη συνολική επιφάνεια του λεκιασμένου υφάσματος σε όλα τα σεντόνια για καθένα από τα δεδομένα χρονικά σημεία.

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό ~N~ ~(1 \le N \le 100\,000)~, τον αριθμό των σεντονιών.
Κάθε μία από τις ακόλουθες γραμμές ~N~ περιέχει τέσσερις ακέραιους ~x_1,\,y_1,\,x_2~ και ~y_2~ ~(-1\,000\,000 \le x_1 \le x_2 \le 1\,000\,000)~, ~(-1\,000\,000 \le y_1 \le y_2 \le 1\,000\,000)~. Οι συντεταγμένες ~(x_1,\,y_1)~ και ~(x_2,\,y_2)~ αντιπροσωπεύουν διαγώνια αντίθετες γωνίες ενός σεντονιού (και πάλι, αυτές οι συντεταγμένες είναι μοναδιαία τετράγωνα, όχι σημεία στο επίπεδο). Κανένα από τα σεντόνια αυτά δε θα καλύπτουν το τετράγωνο ~(0,\,0)~.
Η επόμενη γραμμή περιέχει έναν ακέραιο αριθμό ~M (1 \le M \le 100\,000)~, τον αριθμό των σημείων στο χρόνο.
Η επόμενη γραμμή περιέχει ~M~ ακέραιους αριθμούς μεταξύ ~0~ και ~1\,000\,000~, τα χρονικά σημεία. Θα παραδοθούν αυστηρά αύξουσα σειρά.

Έξοδος

Για καθένα από τα χρονικά σημεία, βάλτε σε ξεχωριστή γραμμή τη συνολική επιφάνεια του λεκιασμένου υφάσματος σε όλα τα σεντόνια, με τη σειρά που δίνονται τα χρονικά σημεία στην είσοδο.

Παραδείγματα

input

3
-2 1 1 2
1 0 2 1
-3 -3 -2 0
2
1 2

output

5
15

input

4
5 1 8 4
-8 1 -5 4
-10 2 10 3
6 0 8 10
6
1 2 3 4 7 9

output

0
5
14
18
70
100

input

1
1 1 1000000 1000000
3
100 10000 1000000

output

10000
100000000
1000000000000