平面上に、互いに色の異なる長方形の色紙 $N$ 枚を 1 枚ずつ順番に置きます。 

色紙を斜めに置くことはありません。つまり、どの色紙の辺も互いに平行または垂直です。 

図 1 は、1 番、2 番、3 番の色紙をこの順に置いた状態を示しています。

ここに図 2 のように 4 番の色紙をさらに置くと、3 番の色紙は完全に覆われて見えなくなります。 

また、1 番と 2 番の色紙は一部が覆われて見え、4 番の色紙は全体が見えます。

$N$ 枚の色紙を指定された位置に順番に置いたとき、各色紙の見える部分の面積を求めるプログラムを作成してください。

入力

入力の 1 行目に、色紙の枚数を表す整数 $N$（$1 \le N \le 100$）が与えられます。続く $N$ 行には、各色紙について 1 行ずつ順番に情報が与えられます。

色紙を置く平面は、横に最大 $1001$ マス、縦に最大 $1001$ マスの格子です。 

各マスは幅 $1$、高さ $1$、面積 $1$ の正方形です。 

説明のため、横 $6$ マス、縦 $6$ マスの格子を例に考えます。各マスに書かれた値 $(a, b)$ は、そのマスの番号を表します。 

左下端のマスは $(0, 0)$、右上端のマスは $(5, 5)$ です。

色紙の置き方は、左下端のマスの番号と幅、高さを表す 4 つの整数で表現します。 

例えば、上図の灰色の色紙は左下端が $(1, 4)$、幅 $3$、高さ $2$ なので、`1 4 3 2` と表します。 

色紙が格子の外にはみ出すことはありません。 

制約 

小課題 1：$100$ 点中 $11$ 点。$N = 1$。 

小課題 2：$100$ 点中 $12$ 点。$N \le 10$ で、すべての色紙は幅 $1$、高さ $1$ です。平面は横 $101$ マス、縦 $101$ マスの格子です。 

小課題 3：$100$ 点中 $30$ 点。$N \le 10$ で、平面は横 $101$ マス、縦 $101$ マスの格子です。 

小課題 4：$100$ 点中 $47$ 点。元の制約以外に追加の制約はありません。

出力

入力順に $N$ 枚の色紙を平面上に置いた後、各色紙の見える部分の面積を入力順に、1 行に 1 つの整数で出力してください。

見えない色紙については整数 $0$ を出力してください。

入出力例

入力 1

2
0 0 10 10
2 2 6 6

出力 1

64
36

入力 2

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

出力 2

81
25
60

入力 3

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

出力 3

62
24
0
120