ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1331. Vladislava

Time limit: 1.0 second
Memory limit: 64 MB
— We call this satellite Vladya. As you know Vladislava has one more satellite, artificial as well, and also extra-terrestrial. It is smaller. We call it Slava, you get it? The planet is called Vladislava and it is natural to call its satellites Vladya and Slava, isn’t it?
— Yes, of course,— said Gorbovsky. He was familiar with this beautiful argumentation. He heard it for the third time. — You suggested it very wittily, August. Vladya and Slava — Vladislava. Splendid!
— You call these satellites respectively Y-one and Y-two on the Earth,— continued Bader,— Vladya and Slava. But we, we call them other way. We call them Vladya and Slava.
He looked at Valkenstein strictly. Valkenstein worked his jaws. As far as he knew “we” ment Bader himself and only Bader.
N artifacts of extra-terrestrial civilizations were found on the planet Vladislava.
The scientific spacecraft settled on the planet’s orbit and launched automatic probes, which found out that a storm-boat will be able to touch down only in one of M points on the planet’s surface because of the rough relief. Inasmuch as the transportation on the planet’s surface takes much time, it is reasonable to find the nearest landing place for each artifact.

Input

The first line contains integers N and M (1 ≤ N, M ≤ 5000) — amounts of artifacts and landing grounds respectively. Then there is positive real R ≤ 1000 — that is the planet radius. Each of the following M lines consists of latitude Wi and longitude Li of one of the landing grounds, Wi, Li are real numbers, |Wi| ≤ 90, |Li| ≤ 180. The next N lines contain artifacts coordinates — latitude wi and longitude li — real numbers, |wi| ≤ 90, |li| ≤ 180. All real numbers are rounded to 6 digits after decimal point.

Output

You are to output exactly N lines. ith line should contain the distance between the ith artifact and the nearest landing ground within two digits after a decimal point.

Samples

inputoutput
1 2
1
0 0
1 1
0 0
0.00
2 1
1
0 0
0 90
0 45
1.57
0.79
Problem Author: Alexander Bikbaev
Problem Source: The 10th Collegiate Programming Contest of the High School Pupils of the Sverdlovsk Region (October 16, 2004)