Under construction

Still being built. Things may change

Fence Construction

Time limit0.1sMemory limit1024 MB

Summary
Given N rectangles added one at a time, print the perimeter of the bounding rectangle of all buildings so far after each addition.
Level

Easy1 of 10

Topics
Implementation, Math
Solved
No attempts yet

Problem

Puang village builds a fence around the outskirts of the village to protect it from the threat of poor grades (학점). Each building is a rectangle on a 2D plane, with lower-left corner (ai,bi)(a_i, b_i) and upper-right corner (ci,di)(c_i, d_i). Puang village has world-class construction skills, so buildings may overlap. The fence is the smallest rectangle that encloses every building in the village, and its sides must be parallel to the x-axis or the y-axis. The cost of the fence is its perimeter.

By the village's iron rule that fences must be sturdy, each time a building is added, the existing fence is torn down and a new one is installed. The village starts with no buildings and constructs NN buildings one at a time. After each building is built, print the cost of the fence construction.

Input

The first line contains the number of buildings NN to construct. Each of the next NN lines contains four integers aia_i, bib_i, cic_i, and did_i, separated by spaces, which describe the ii-th building to be constructed.

Output

Print NN lines. The ii-th line contains the fence construction cost after the ii-th building is built.

Constraints

  • 1≤N≤101 \le N \le 10
  • −10≤ai<ci≤10-10 \le a_i < c_i \le 10
  • −10≤bi<di≤10-10 \le b_i < d_i \le 10
  • 1≤i≤N1 \le i \le N
  • All given coordinates are integers.

Examples2

  1. Example 1

    Input
    4
1 1 3 3
2 2 4 4
2 2 3 3
1 1 4 4
    Expected output
    8
12
12
12

  2. Example 2

    Input
    2
0 0 2 2
0 0 1 4
    Expected output
    8
12