$N$ rechteckige Blätter Buntpapier mit jeweils unterschiedlichen Farben werden nacheinander auf eine Ebene gelegt. 

Kein Blatt wird schräg gelegt. Das heißt, alle Kanten der Blätter sind zueinander entweder parallel oder senkrecht. 

Abbildung 1 zeigt die Blätter 1, 2 und 3, nachdem sie in dieser Reihenfolge gelegt wurden.

Wird wie in Abbildung 2 noch Blatt 4 hinzugefügt, ist Blatt 3 vollständig verdeckt und nicht mehr sichtbar. 

Die Blätter 1 und 2 sind teilweise verdeckt, während Blatt 4 vollständig sichtbar ist.

Schreibe ein Programm, das die sichtbare Fläche jedes Blatts bestimmt, wenn $N$ Blätter der Reihe nach an die gegebenen Positionen gelegt werden.

Eingabe

Die erste Eingabezeile enthält eine ganze Zahl $N$ ($1 \le N \le 100$), die Anzahl der Blätter. Die nächsten $N$ Zeilen beschreiben die Blätter der Reihe nach, jeweils eines pro Zeile.

Die Ebene ist ein Gitter mit höchstens $1001$ Zellen in horizontaler und $1001$ Zellen in vertikaler Richtung. 

Jede Gitterzelle ist ein Quadrat mit Breite $1$, Höhe $1$ und Fläche $1$. 

Zur Veranschaulichung betrachten wir ein Gitter mit $6$ Zellen horizontal und $6$ vertikal. Der Wert $(a, b)$ in jeder Zelle bezeichnet deren Nummer. 

Die Zelle ganz links unten ist $(0, 0)$, die ganz rechts oben ist $(5, 5)$.

Die Lage eines Blatts wird durch vier ganze Zahlen beschrieben, welche die Nummer seiner linken unteren Zelle, seine Breite und seine Höhe angeben. 

Das graue Blatt in der Abbildung hat beispielsweise die linke untere Zelle $(1, 4)$, Breite $3$ und Höhe $2$ und wird daher als `1 4 3 2` dargestellt. 

Kein Blatt ragt über die Gittergrenzen hinaus. 

Beschränkungen 

Teilaufgabe 1: $11$ von $100$ Punkten; $N = 1$. 

Teilaufgabe 2: $12$ von $100$ Punkten; $N \le 10$, und alle Blätter haben Breite $1$ und Höhe $1$. Das Gitter hat $101$ Zellen horizontal und $101$ vertikal. 

Teilaufgabe 3: $30$ von $100$ Punkten; $N \le 10$, und das Gitter hat $101$ Zellen horizontal und $101$ vertikal. 

Teilaufgabe 4: $47$ von $100$ Punkten; keine zusätzlichen Beschränkungen über die ursprünglichen hinaus.

Ausgabe

Nachdem die $N$ Blätter in Eingabereihenfolge auf die Ebene gelegt wurden, gib die sichtbare Fläche jedes Blatts in derselben Reihenfolge aus, als eine ganze Zahl pro Zeile.

Ist ein Blatt nicht sichtbar, gib die ganze Zahl $0$ aus.

Beispiele

Eingabe 1

2
0 0 10 10
2 2 6 6

Ausgabe 1

64
36

Eingabe 2

3
0 2 10 10
7 9 8 4 
8 4 10 6

Ausgabe 2

81
25
60

Eingabe 3

4
0 2 10 10 
7 9 8 4 
8 4 10 6
6 0 12 10

Ausgabe 3

62
24
0
120