On place sur un plan, une par une et dans l’ordre, $N$ feuilles rectangulaires de papier, chacune d’une couleur différente. 

Aucune feuille n’est placée de biais. Autrement dit, tous les côtés des feuilles sont parallèles ou perpendiculaires entre eux. 

La figure 1 montre les feuilles 1, 2 et 3 placées dans cet ordre.

Si l’on ajoute la feuille 4 comme sur la figure 2, la feuille 3 est entièrement recouverte et devient invisible. 

Les feuilles 1 et 2 sont partiellement recouvertes, tandis que la feuille 4 est entièrement visible.

Écrivez un programme qui détermine l’aire visible de chaque feuille lorsque les $N$ feuilles sont placées dans l’ordre aux positions données.

Entrée

La première ligne de l’entrée contient un entier $N$ ($1 \le N \le 100$), le nombre de feuilles. Les $N$ lignes suivantes décrivent les feuilles dans l’ordre, une par ligne.

Le plan est une grille ayant au plus $1001$ cases horizontalement et $1001$ verticalement. 

Chaque case est un carré de largeur $1$, de hauteur $1$ et d’aire $1$. 

Pour faciliter l’explication, considérons une grille de $6$ cases horizontalement et $6$ verticalement. La valeur $(a, b)$ inscrite dans chaque case en est l’identifiant. 

La case en bas à gauche est $(0, 0)$ et celle en haut à droite est $(5, 5)$.

La position d’une feuille est représentée par quatre entiers indiquant l’identifiant de sa case en bas à gauche, sa largeur et sa hauteur. 

Par exemple, la feuille grise de la figure a sa case inférieure gauche en $(1, 4)$, une largeur de $3$ et une hauteur de $2$ ; elle est donc représentée par `1 4 3 2`. 

Aucune feuille ne dépasse les limites de la grille. 

Contraintes 

Sous-tâche 1 : $11$ points sur $100$ ; $N = 1$. 

Sous-tâche 2 : $12$ points sur $100$ ; $N \le 10$, et chaque feuille a une largeur de $1$ et une hauteur de $1$. La grille comporte $101$ cases horizontalement et $101$ verticalement. 

Sous-tâche 3 : $30$ points sur $100$ ; $N \le 10$, et la grille comporte $101$ cases horizontalement et $101$ verticalement. 

Sous-tâche 4 : $47$ points sur $100$ ; aucune contrainte supplémentaire par rapport aux contraintes initiales.

Sortie

Après avoir placé les $N$ feuilles sur le plan dans l’ordre de l’entrée, affichez l’aire visible de chaque feuille dans ce même ordre, à raison d’un entier par ligne.

Si une feuille est invisible, affichez l’entier $0$.

Exemples

Entrée 1

2
0 0 10 10
2 2 6 6

Sortie 1

64
36

Entrée 2

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

Sortie 2

81
25
60

Entrée 3

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

Sortie 3

62
24
0
120