Foma and Entertaining Mathematics

Time limit2sMemory limit1024 MB

Summary

Given a, b, c, d, find the unique x in {1, 2, 3} with a^x + b^x + c^x = d, or print -1 if there is no such x or more than one.

Level: Easy1 of 10
Topics: Implementation, Brute force
Solved: No attempts yet

Statement

This morning Foma searched the whole school for Tanya but could not find her. So he started going into the classrooms one by one.

In the math classroom, Foma found some scribbles on the board: $a^x+b^x+c^x=d \land x \in \{1, 2, 3\}$ . Usach was called in right away. He began by explaining that $\land$ is logical AND and $\in$ means membership in a set. Valya then started to explain what could be done with this, but as soon as Foma realized that $a$ , $b$ , $c$ and $d$ could be replaced by any numbers, he asked Valya for the root of the resulting equation.

Valya does not like talking to Oleg Evgenievich more than necessary, so he asks you for help. Write a program that, given $a$ , $b$ , $c$ and $d$ , finds the root of the equation.

Input

The single line of the input file contains four numbers $a$ , $b$ , $c$ and $d$ ( $-500 \le a, b, c \le 500$ ; $-10^9 \le d \le 10^9$ ), the parameters of the equation.

Output

Print one number $x$ , the root of the equation, on a single line of the output file. If the root cannot be determined uniquely, print -1.

Examples4

Example 1
Input
```
1 1 1 3
```
Expected output
```
-1
```
Example 2
Input
```
1 2 3 6
```
Expected output
```
1
```
Example 3
Input
```
1 2 3 7
```
Expected output
```
-1
```
Example 4
Input
```
1 -1 -2 6
```
Expected output
```
2
```