Đi từ trường về nhà sau một ngày học căng thẳng, Ivica đã sẵn sàng giải lao bằng trò chơi điện tử "Khỉ & chuối".
Trong trò chơi, chú khỉ ở trong một khu rừng mà trên mỗi điểm có toạ độ nguyên đề có một cái cây và mỗi cái cây đều nằm trên một điểm có toạ độ nguyên. Ban đầu, chú khỉ ở vị trí (~X_{m}~, ~Y_{m}~) và hướng mặt về (~X_{m}~, ~Y_{m}~ +1). Ivica điều khiển chú khỉ bằng các phím ~0~.. ~7~. Khi Ivica ấn phím thứ ~K~, khỉ quay mặt sang trái ~45~ độ ~K~ lần và nhảy đến cái câu đầu tiên mà nó nhìn thấy (sau khi đã quay mặt).
Trò chơi kết thúc sau khi ấn ~N~ phím. Sau đó, điểm được tính dựa trên khoảng cách giữa khỉ và cây chuối (khoảng cách Euclide). Khoảng cách càng gần, điểm càng cao. Sau khi kết thúc trò chơi, Ivica muốn biết rằng cậu có thể đạt kết quả như thế nào nếu chỉ thay đổi nhiều nhất một phím. Bạn hãy giải bài toán này.
Input
- Dòng ~1~: gồm ~4~ số ~X_{m}~, ~Y_{m}~, ~X_{b}~, ~Y_{b}~ (~0 \le X_{m}~, ~Y_{m}~, ~X_{b}~, ~Y_{b} \le 1\,000\,000~) là toạ độ ban đầu của khỉ và toạ độ của cây chuối.
- Dòng ~2~: Gồm số nguyên ~N~ (~1 \leq N \leq 100\,000~), số lần bấm phím
- Dòng ~3~: Xâu gồm ~N~ kí tự trong khoảng '0'.. '7', là các phím mà Ivica đã bấm (theo thứ tự)
Output
- Gồm một dòng duy nhất chứa khoảng các mà Ivica có thể đạt được nếu thay đổi nhiều nhất một lần bấm phím. Kết quả của bạn được coi là chính xác nếu sai khác không quá 0.01 so với kết quả của ban tổ chức
Sample Input 1
0 0 2 3
5
15102
Sample Output 1
0.000000
Sample Input 2
5 5 10 5
3
000
Sample Output 2
2.000000
Sample Input 3
0 0 10 10
9
700003000
Sample Output 3
1.414214
Comments