Fraction Sum

Interview

Time limit2sMemory limit128 MB

Summary

Add two given fractions and output the sum reduced to lowest terms using GCD.

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

Problem

Given two fractions A/B and C/D whose numerators and denominators are natural numbers, compute their sum and write it as a reduced fraction. A reduced fraction is one whose numerator and denominator have greatest common divisor 1.

Input

The first line contains the numerator and denominator A B of the first fraction. The second line contains the numerator and denominator C D of the second fraction. All four numbers are natural numbers no greater than 30,000.

Output

Print the numerator and denominator of the reduced sum, separated by one space.

Examples1

Example 1
Input
```
2 7
3 5
```
Expected output
```
31 35
```