In this task your goal is to prey upon caravans.

There are n oases in the desert (for our purposes they are points on the plane). Sometimes caravans go from one oasis to another one. In order to prey upon them, you should predict their paths. But how to do it? The answer was given by Nomad. Caravans' velocity is constant, and they try to minimize maximal period of time outside oases. So, you can conclude, that the optimal path is a polyline. You are given several pairs of oases, and you are to output length of the maximal segment of the optimal path of a caravan which starts its way from the first oasis of the pair and ends in the second one. All oases have distinct locations and there are three oases that do not belong to one line.

First line of the input contains n — amount of oases (). The following n lines describe them. Each line contains two integer numbers — x_i and y_i (). Next line contains one integer number q — amount of caravans (). The next q lines contain start and end oases of caravans — s_i and t_i (1 ≤ s_i, t_i ≤ n).

Output q lengths with relative or absolute error 10^-9 — one number at a line.

sample input	sample output
3 0 0 50 10 150 0 3 1 2 1 3 2 3	50.9901951359 100.4987562112 100.4987562112