English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/majmun

Đ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í (Xm, Ym) và hướng mặt về (Xm,Ym +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ố Xm, Ym, Xb, Yb (0<= Xm, Ym, Xb, Yb<=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<=N<=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

Example

Input:
0 0 2 3
5
15102

Output:
0.000000

Input:
5 5 10 5
3
000

Output:
2.000000

Input:
0 0 10 10
9
700003000

Output:
1.414214

---