Codeforces Round #643 (Div. 2) : C. Count Triangles : Solution in python

C. Count Triangles

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Like any unknown mathematician, Yuri has favourite numbers: A

, B, C, and D, where A≤B≤C≤D. Yuri also likes triangles and once he thought: how many non-degenerate triangles with integer sides x, y, and z exist, such that A≤x≤B≤y≤C≤z≤D

holds?

Yuri is preparing problems for a new contest now, so he is very busy. That's why he asked you to calculate the number of triangles with described property.

The triangle is called non-degenerate if and only if its vertices are not collinear.

Input

The first line contains four integers: A

, B, C and D (1≤A≤B≤C≤D≤5⋅105

) — Yuri's favourite numbers.

Output

Print the number of non-degenerate triangles with integer sides x

, y, and z such that the inequality A≤x≤B≤y≤C≤z≤D

holds.

Examples

Input

Copy

1 2 3 4

Output

Copy

4

Input

Copy

1 2 2 5

Output

Copy

3

Input

Copy

500000 500000 500000 500000

Output

Copy

1

Note

In the first example Yuri can make up triangles with sides (1,3,3)

, (2,2,3), (2,3,3) and (2,3,4)

.

In the second example Yuri can make up triangles with sides (1,2,2)

, (2,2,2) and (2,2,3)

.

In the third example Yuri can make up only one equilateral triangle with sides equal to 5⋅105

.

Solution in Python :

l = [int(i) for i in input().split()]

length = len(l)
count = 0
for a in range(l[0] , l[1]+1) :
    for b in range(l[1],l[2]+1) :
        for c in range(l[2] ,l[3]+1) :
                 if a+b > c and b+c > a and c+a > b :
                    count += 1
print(count)