Under construction

Still being built. Things may change

Positive Con Sequences

Interview

Time limit1sMemory limit256 MB

Summary
Fill the missing entry of each four-term sequence with a number from 1 to 10000 that makes it arithmetic or geometric, or output -1.
Level

Easy3 of 10

Topics
Math, Brute force
Solved
No attempts yet

Problem

Your younger sister is preparing for a mathematics exam, and she keeps meeting problems that ask her to fill in the missing term of a number sequence. Almost every sequence of that style is either arithmetic or geometric. An arithmetic sequence adds a fixed integer to the previous term to form the next one, and a geometric sequence multiplies the previous term by a fixed integer.

Write a program that computes the missing term so she can check her answers.

Input

The input consists of one or more datasets.

Each dataset is one line holding 4 integers separated by spaces that describe a sequence. Exactly one of them is -1, which marks the position of the missing term. The other three are integers between 1 and 10,000 inclusive, and once the -1 position is ignored they are given in non-decreasing order.

The end of the input is a line containing four values of -1.

Output

Print one line for each dataset.

If an integer between 1 and 10,000 inclusive can be placed at the missing position so that the whole sequence becomes arithmetic or geometric, print that integer.

If no such integer exists, print -1.

Examples2

  1. Example 1

    Input
    1 2 -1 4
2 4 8 -1
7 8 -1 21
5 -1 11 14
-1 2 4 6
-1 -1 -1 -1
    Expected output
    3
16
-1
8
-1

  2. Example 2

    Input
    -1 3 9 27
1 1 -1 1
9997 9998 9999 -1
-1 -1 -1 -1
    Expected output
    1
1
10000