GARDEN - Golden Garden

Little Jelly is playing in the Golden Garden alone. She is such a pretty girl that the Evil Uncle wants to catch her. The Evil Uncle drives his flying saucer over the Golden Garden and tries to inhale Little Jelly.

It is known that the Golden Garden is a perfect rectangle and the Evil Uncle's flying saucer can inhale her if and only if she is in a circle with a certain radius around the flying saucer.

Your task is to avoid the Evil Uncle catching Little Jelly. First of all, you should find out the common area of the garden and the inhaling circle.

Input

There are multiple test cases in the input file. First line of each test case are three integers x, y and r, For the coordinate of the center of the inhaling circle and its radius.

The second line contains four integers x1, y1, x2 and y2. Which are the coordinate of the Golden Garden. The Golden Garden is such a perfect rectangle so that its sides are parallel to the axis.

All numbers in the input are integers and do not reach 1000 by their absolute values. Sides of the Golden Garden are non-zero.

Output

For each test cases, output only one line with one real number which is the common area of the garden and the circle. Your answer must be accurate up to 0.000001.

Note

There are two input files for this problem. If you get Wrong Answer, click on the "wrong answer" to get more details. For each test file, my judge will give you the id of the test case for which your program gives a wrong response.

Example

Input:
0 0 5
3 3 7 7

Output:
0.547426365104
Warning: enormous input/output data, be careful with certain languages

Added by:Fudan University Problem Setters
Date:2007-12-01
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:Description, standard program & test data by g201513

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.