Pattern

Time limit1sMemory limit128 MB

Summary

Count unit squares with max(x,y) odd inside a large rectangle using a closed-form counting formula instead of brute force.

Level: Medium6 of 10
Topics: Math, Combinatorics, Implementation
Solved: No attempts yet

Problem

The first quadrant is divided into unit square grid cells. For the unit square whose lower-left corner is the integer point (x, y), the square is dark if max(x, y) is odd, and it is not dark if max(x, y) is even.

Given the lower-left and upper-right corners of a rectangle, count the number of dark unit squares completely contained in that rectangle.

Input

The first line contains four integers X1 Y1 X2 Y2, separated by spaces. (0 <= X1 < X2 <= 1,000,000, 0 <= Y1 < Y2 <= 1,000,000)

The rectangle contains exactly the unit squares with X1 <= x < X2 and Y1 <= y < Y2.

Output

Print the number of dark unit squares contained in the given rectangle.

Examples3

Example 1
Input
```
2 3 7 6
```
Expected output
```
8
```
Example 2
Input
```
0 4 2 104
```
Expected output
```
100
```
Example 3
Input
```
4 1 7 50
```
Expected output
```
72
```