M. Gift Wrapping
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
Life is about doing what you want to do! If you keep talking cost this return that, you won't accomplish anything!
— Ruby Hoshino

Or so she thought until she fell into large amounts of debt and now has to wrap gifts for a living.

Ruby has $$$n$$$ ($$$1 \le n \le 10^5$$$) gifts. The $$$i$$$-th gift is represented by a rectangle in $$$2$$$d space having a bottom left vertex of ($$$x_i, y_i$$$) and top right vertex of ($$$x_i', y_i'$$$) ($$$0 \le x_i \lt x_i' \le 10^5$$$, $$$0 \le y_i \lt y_i' \le 10^5$$$). Recently, Aqua has told Ruby to be more organized, so she has already sorted the rectangles by their right side. In other words, $$$x_{i - 1}' \le x_i'$$$ for all $$$i \gt 1$$$.

Ruby wants to use gift wrapping to completely cover her gifts. Each gift wrap is also represented by a rectangle in $$$2$$$d space, and Ruby can choose to create these rectangles however she wants as long as they don't overlap and each gift can only belong to a single gift wrap. Ruby is given a bonus if the amount of gift wrap she uses is small, so she wants to minimize the total area of gift wrap used. In other words, Ruby wants to find the minimum total area of non-intersecting rectangles such that each gift is completely contained by exactly one rectangle.

However, Ruby has always been an overachiever (unlike Akane), so she also wants to find the minimum total area of gift wrap to cover every gift from $$$1 \dots i$$$ for all $$$i$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 3$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ ($$$1 \le n \le 10^5$$$) representing the number of gifts.

The $$$i$$$-th of the next $$$n$$$ lines of each test case contains four integers $$$x_i$$$, $$$y_i$$$, $$$x_i'$$$, and $$$y_i'$$$ ($$$0 \le x_i \lt x_i' \le 10^5$$$, $$$0 \le y_i \lt y_i' \le 10^5$$$, $$$x_{i - 1}' \le x_i'$$$), denoting the coordinates of the gift.

 —

For test cases $$$1$$$ - $$$5$$$, it is guaranteed that $$$n \le 5000$$$.

There are no restrictions on the remaining test cases.

Output

For each test case, output $$$n$$$ lines, the $$$i$$$-th of which denotes the minimum area of gift wrap needed to cover every gift from $$$1 \dots i$$$.

Example
Input
1
5
3 3 4 8
0 0 5 1
4 0 5 5
5 6 8 7
6 2 8 4
Output
5
10
40
43
47
Note

Problem Idea: oursaco

Problem Preparation: oursaco

Occurrences: Advanced 9