Under construction

Still being built. Things may change

Cutting the Blank

Interview

Time limit2sMemory limit1024 MB

Summary
Given the cut widths a and b and the remaining area S, find the integer side length L of the original square, or report -1 if none exists.
Level

Easy3 of 10

Topics
Math, Brute force
Solved
No attempts yet

Problem

The young assistant Ola was tired of always standing in the shadow of her master, so she decided to paint her own masterpiece while the artist took a nap in the afternoon. She picked a square blank from the workshop, which was full of them. The blank looked too large, and it did not suit her status to paint such a big canvas. So Ola cut a strip of width aa off the right side with one vertical cut.

The canvas still looked too tall, so she made a horizontal cut and removed a strip of height bb from the top. To check that the result suits her work, she computed its area SS and wrote it on a sheet of paper.

After several hours of work, Ola considered her creation finished and worthy of the public, so she took it to the festival in the city center.

When the great artist woke up, he understood at once. Such incidents had happened many times in his life. To restock his blanks, he now needs to buy a new square blank exactly like the one Ola used. The only facts he could learn about the original size are the numbers aa, bb, and SS, which were written on scraps of paper found in the workshop.

The shop only sells blanks whose side lengths are integers. Write a program that, given aa, bb, and SS, determines whether it makes sense to go to the shop for a new blank, and finds the side length of the blank.

Input

A single line contains three integers aa, bb, and SS (0≤a,b≤1040 \le a, b \le 10^{4}, 1≤S≤1081 \le S \le 10^{8}).

Output

If a blank of that size is sold in the shop, print its side length LL as a single integer. If no such blank can exist with the given parameters, or it is not sold, print −1-1.

Examples3

  1. Example 1

    Input
    1 1 1
    
    Expected output
    2
    
  2. Example 2

    Input
    2 3 12
    
    Expected output
    6
    
  3. Example 3

    Input
    1 1 2
    
    Expected output
    -1