eolymp
bolt
Try our new interface for solving problems
Problems

Circular Island

Circular Island

Time limit 6 seconds
Memory limit 256 MiB

Andrew has just made a breakthrough in geography: he has found an island that was previously unknown to the civilized world. This island has a shape of perfect circle and it is inhabited by two tribes, Java and Seeplusplus. After a brief contact with the aborigines, Andrew found out that the boundary between the lands of the tribes is a straight line. Moreover, he knows the locations of several Java villages and of several Seeplusplus villages (each is of course located within or on the boundary of the corresponding tribe's land). Now he needs to find out what is the minimal and maximal possible area of Java's land. Help him!

Input data

The first line of the input file contains one integer r — the radius of the island (1 ≤ r ≤ 10^9). The next line contains one integer n (1 ≤ n ≤ 50000) — the number of Java villages. Each of the next n lines contains two integers x and y — the coordinates of Java villages. The next line contains one integer m (1 ≤ m ≤ 50000) — the number of Seeplusplus villages. Each of the next m lines contains two integers x and y — the coordinates of Seeplusplus villages. The center of the island has coordinates (0, 0), each village is within the island and at least r/10 away from the island boundary. No two villages coincide. The input is guaranteed to be valid — there will always be at least one straight line separating the Java villages from the Seeplusplus villages.

Output data

Output two floating-point numbers, separated with a space — the minimal and maximal possible area of the Java land. An area will be considered correct if it is within 10^{-6} relative error of the right answer.

Examples

Input example #1
6
2
3 4
-3 4
1
0 0
Output example #1
12.389928320447162 56.54866776461629
Author Peter Mitrichev
Source Winter School, Kharkov, 2011, Day 8