Congruent Numbers

Interview

Time limit2sMemory limit512 MB

Summary

Given the two legs of a right triangle as fractions p1/q1 and p2/q2, print 1 if the triangle's area is an integer, otherwise 0.

Level: Easy2 of 10
Topics: Math, Number theory, Implementation
Solved: No attempts yet

Problem

A congruent number is an integer that is the area of some right triangle whose sides all have rational length. In this problem you only look at the two legs of the right triangle, not the hypotenuse.

A rational number is a fraction $p/q$ where the numerator $p$ and the denominator $q$ are both integers. If $q = 1$ , then $p/1$ is an integer, so every integer is a rational number.

You are given the rational lengths of the two legs of a right triangle. Determine whether the area of that triangle is a congruent number. In this problem the hypotenuse does not have to be rational.

Input

The input consists of a single test case. Your program may be run several times on different inputs.

The first line contains four integers $p_1$ , $q_1$ , $p_2$ , $q_2$ ( $1 \le p_1, q_1, p_2, q_2 \le 100000$ ). The numbers $p_1/q_1$ and $p_2/q_2$ are the lengths of the two legs of the right triangle.

Output

Print $1$ on a single line if the area of the triangle is an integer, and $0$ otherwise. A rational area is not enough; it has to be an integer.

Examples4

Example 1
Input
```
3 1 4 1
```
Expected output
```
1
```
Example 2
Input
```
15 1 28 3
```
Expected output
```
1
```
Example 3
Input
```
1 2 3 4
```
Expected output
```
0
```
Example 4
Input
```
1 1 10 1
```
Expected output
```
1
```