Posters

An election for algorithm president is coming up. Anyone may run, so the field is crowded and the campaigning is fierce.

The posters are the worst of it. Every candidate has one rectangular poster and pastes it on a wall along the street. The posters come in every size, they bury the wall, and a candidate whose poster gets covered simply pastes another one on top. The election commission finally set a rule.

The $N$ candidates receive distinct numbers from 1 to $N$. Each candidate pastes exactly one poster on the wall, and they paste in order of candidate number. A poster pasted later covers whatever is already on the wall.

The wall is large enough to be treated as the coordinate plane. After all $N$ candidates have pasted their posters, look at the wall from the front and compute, for each candidate, the visible area of that candidate's poster.

The first line contains the number of candidates $N$ ($1 \le N \le 5000$).

Each of the next $N$ lines describes one poster, for candidate 1 through candidate $N$ in that order. A line holds four integers $x_1$, $y_1$, $x_2$, $y_2$, meaning the poster is a rectangle with lower left corner $(x_1, y_1)$ and upper right corner $(x_2, y_2)$, pasted at that position. Here $x_1 < x_2$ and $y_1 < y_2$, and all four coordinates are integers between $-10^9$ and $10^9$, inclusive.

Print $N$ lines. The $i$-th line holds the visible area of candidate $i$'s poster.

The picture below shows the first example.

• Candidate 1: blue poster
• Candidate 2: green poster
• Candidate 3: orange poster
• Candidate 4: yellow poster