Waiting for the Dog

Luka bought a new golden collar for his dog and entered a park. At the entrance, Luka and the dog were at the same point A = (Ax, Ay). Luka let the dog go and then walked to the exit B = (Bx, By) along a fastest possible route.

Treat the park as a two-dimensional plane, and represent both Luka and the dog as points. They can move in the four cardinal directions. While moving, their speed is exactly 1 m/s. They may turn at any time, so in one second one could move 0.37 m upward and 0.63 m to the right.

Luka walked without stopping on a fastest route until he reached the exit. The dog may stop sometimes, and it caught up with Luka at the same point B exactly T seconds after Luka reached the exit. At that moment Luka noticed that the dog no longer had the collar.

The park contains several rectangular gardens. Neither Luka nor the dog may enter the interior of a garden, but they may move along its boundary. No two gardens touch each other.

Find the total area of all positions where the dog could have lost the collar.

The first line contains the number of gardens N. (0 <= N <= 100)

The second line contains the entrance coordinates Ax Ay. (0 <= Ax, Ay <= 10000)

The third line contains the exit coordinates Bx By. (0 <= Bx, By <= 10000) The exit is different from the entrance.

Each of the next N lines contains four integers X1 Y1 X2 Y2 describing one garden. (0 <= X1 < X2 <= 10000, 0 <= Y1 < Y2 <= 10000) The point (X1, Y1) is the lower-left corner and (X2, Y2) is the upper-right corner. No garden contains the entrance or the exit.

The last line contains the time T that Luka waited for the dog at the exit. (0 <= T <= 10000)

Print the total area of all positions where the dog could have lost the collar.

An absolute or relative error of at most 0.01 is accepted.