Blocked Billboard

Interview

Time limit2sMemory limit512 MB

Summary

Given two non-overlapping billboards and one truck rectangle, compute the total billboard area not covered by the truck.

Level: Easy3 of 10
Topics: Geometry, Implementation, Math, Brute force
Solved: No attempts yet

Problem

During long milking sessions, Bessie the cow likes to stare out of her barn window at two huge rectangular billboards across the street. One advertises "Farmer Alex's Amazingly Appetizing Alfalfa" and the other "Farmer Greg's Great Grain". The pictures of these two cow feed products look much tastier to Bessie than the grass on her own farm.

One day, while Bessie is staring out of the window, a huge rectangular truck parks across the street. The side of the truck carries an advertisement for "Farmer Smith's Superb Steaks", which Bessie does not quite understand. What worries her is that the truck may block the view of her two favorite billboards.

You are given the positions of the two billboards and the position of the truck. Compute the total area of the two billboards that is still visible. The truck may block both billboards, only one of them, or neither of them.

Input

The first line contains four space separated integers $x_1$ $y_1$ $x_2$ $y_2$ , where $(x_1, y_1)$ is the lower left corner and $(x_2, y_2)$ is the upper right corner of the first billboard in Bessie's 2D field of view. The second line gives the lower left and the upper right corner of the second billboard in the same way. The third line gives the lower left and the upper right corner of the truck. Every coordinate is between $-1000$ and $1000$ , and in each rectangle the lower left coordinate is smaller than the upper right coordinate on both axes. The two billboards overlap in an area of $0$ .

Output

Print the total area of the two billboards that is still visible.

Hint

In the first example, an area of $5$ from the first billboard and an area of $12$ from the second billboard remain visible.

Examples2

Example 1
Input
```
1 2 3 5
6 0 10 4
2 1 8 3
```
Expected output
```
17
```

Example 2

Input

0 0 2 2
3 3 5 5
-1000 -1000 -999 -999

Expected output