35 10 s 128 MB

In the year 2051, several Mars expeditions have explored different areas of the red planet and produced maps of these areas. Now, the BaSA (Baltic Space Agency) has an ambitious plan: they would like to produce a map of the whole planet. In order to calculate the necessary effort, they need to know the total size of the area for which maps already exist. It is your task to write a program that calculates this area.

The input contains several test cases. The first line of whole input will contain a single integer

Each test case starts with a line containing a single integer N (1 ≤ N ≤

For each test case, write a single which contains one integer A, the total explored area (i.e. the area of the union of all rectangles).

## Sample Input | ## Sample Output |
---|---|

2 2 10 10 20 20 15 15 25 30 1 0 0 1 1 | 225 1 |

Even though there is an O(N lgN) algorithm, but a O(N^{2}) solution will be enough for this problem.