$N$ rectangular sheets of colored paper, each of a different color, are placed on a plane one at a time in order. 

No sheet is placed at an angle. In other words, any two edges of the sheets are either parallel or perpendicular. 

Figure 1 shows sheets 1, 2, and 3 placed in that order.

If one more sheet, number 4, is placed as shown in Figure 2, sheet 3 becomes completely covered and cannot be seen. 

Sheets 1 and 2 are partially covered, while sheet 4 is entirely visible.

Write a program that finds the visible area of each sheet when $N$ sheets are placed in order at the given positions.

Input

The first input line contains an integer $N$ ($1 \le N \le 100$), the number of sheets. The next $N$ lines describe the sheets in order, one sheet per line.

The plane on which the sheets are placed is a grid with at most $1001$ cells horizontally and $1001$ cells vertically. 

Each grid cell is a square of width $1$, height $1$, and area $1$. 

For convenience, consider an example grid with $6$ cells horizontally and $6$ vertically. The value $(a, b)$ marked in each cell identifies that cell. 

The bottom-left cell is $(0, 0)$, and the top-right cell is $(5, 5)$.

The placement of a sheet is represented by four integers specifying the identifier of its bottom-left cell, its width, and its height. 

For example, the gray sheet in the figure above has bottom-left cell $(1, 4)$, width $3$, and height $2$, so it is represented as `1 4 3 2`. 

No sheet extends outside the grid boundaries. 

Constraints 

Subtask 1: $11$ points out of $100$; $N = 1$. 

Subtask 2: $12$ points out of $100$; $N \le 10$, and every sheet has width $1$ and height $1$. The plane is a grid of $101$ cells horizontally and $101$ vertically. 

Subtask 3: $30$ points out of $100$; $N \le 10$, and the plane is a grid of $101$ cells horizontally and $101$ vertically. 

Subtask 4: $47$ points out of $100$; there are no constraints beyond the original ones.

Output

After placing the $N$ sheets on the plane in input order, print the visible area of each sheet in input order, as one integer per line.

If a sheet is not visible, print the integer $0$.

Examples

Input 1

2
0 0 10 10
2 2 6 6

Output 1

64
36

Input 2

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

Output 2

81
25
60

Input 3

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

Output 3

62
24
0
120