Sandwich Preparation

Interview

Time limit2sMemory limit1024 MB

Summary

Given four axis-aligned rectangles on a grid, find the area of their union so overlapping cells are counted once.

Level: Easy2 of 10
Topics: Implementation, Brute force
Solved: No attempts yet

Problem

Pasha is very fond of making sandwiches. His signature sandwich, the Coupe, is made from four main ingredients: a top slice of bread, a slice of cheese, a slice of ham, and a bottom slice of bread. All ingredients are rectangular. One day he wanted to make the sandwich quickly, so he tossed the ingredients into the air, hoping they would fall and stack themselves in the right order. However, the ingredients landed on the table in a random way.

Pasha is also a big fan of tic-tac-toe, so the tablecloth on his table looks like a checkered plane. After quickly drawing a coordinate grid on the table, Pasha worked out which ingredient landed on which cells. It turned out that each ingredient is a rectangle with corners at integer coordinates and sides parallel to the axes.

Pasha wants to know the total area the sandwich covered on the table. Write a program that computes this area.

Input

The input file contains four lines, each with four integers: the coordinates of the lower left corner and the upper right corner of one ingredient. The coordinate grid is set up so that the first coordinate increases from left to right and the second increases from bottom to top. All numbers in the input have absolute value at most 1000.

Output

Print a single integer, the answer to the problem.

Examples2

Example 1
Input
```
2 0 5 2
0 1 3 6
1 3 5 7
4 1 6 5
```
Expected output
```
35
```
Example 2
Input
```
0 0 2 1
0 0 1 2
1 0 2 2
0 1 2 2
```
Expected output
```
4
```