Hình học giải tích là môn học thú vị đối với Toto. Hôm nay Toto được thầy giáo giao cho bài tập cho n điểm trên mặt phẳng có tọa độ lần lượt là \(A_1(x_1,y_1), A_2(x_2,y_2), ... A_n(x_n,y_n)\) và cho 2 chỉ số u và v \((1<=u<v<=n)\) hãy tìm độ dài đường gấp khúc đi qua các điểm trên mặt phẳng \(A_u -> A_{u+1} -> ... -> A_v \). Mặc dù cố gắng nhưng số lượng điểm quá nhiều khiến Toto bối rối, bạn hãy giúp Toto lập trình giải bài toán này nhé

Input

Dòng đầu tiên là số điểm trên mặt phẳng \((1<= n <= 2*10^5)\)

Tiếp theo n dòng mỗi dòng chứa hai số thực có trị tuyệt đối nhỏ hơn \(10^4\) là tương ứng là tọa độ của n điểm

Dòng tiếp theo là số nguyên dương m là số đường gấp khúc phải tính độ dài \((1<= m <=10^5)\)

Tiếp theo là m dòng mỗi dòng có hai chỉ số \(u, v\) là điểm đầu và điểm cuối của đường gấp khúc cần tính \((1<=u<v<=n)\)

Ouput

Gồm m số thực tương ứng với độ dài m đường gấp khúc cần tính mỗi số thực được lấy chính xác 3 chữ số sau dấu chấm thập phân và mỗi số in trên một dòng

Ví dụ

Input

6
0 0
5 0
5 4
9 8
9 -2 
13 -2
4
1 3
2 5
1 6
4 6

Output

9.000
19.657
28.657
14.000