반역의 원철이

원철이는 사람의 외로움이 어떤 영향을 주는지 관찰하는 ALPS(Algorithm of Lonely Person Simulation) 실험에 피실험자로 참여하고 있다.

실험장은 2차원 정수 격자이다. 원철이는 처음에 (XM, YM)에 있고 위쪽을 바라보고 있다. 관찰자는 원철이에게 N개의 명령을 순서대로 내린다. 명령은 0부터 7까지의 정수 k로 표현된다. 명령 k를 받으면 원철이는 현재 바라보는 방향에서 반시계방향으로 45 * k도 회전한 뒤, 바로 앞의 인접한 정수 격자점으로 한 칸 이동한다.

격자의 (XB, YB)에는 원철이가 가까워지고 싶은 여성이 서 있다. 원철이는 실험이 끝났을 때 자신의 위치와 그 여성의 위치 사이의 거리가 가능한 한 작아지기를 바란다.

원철이는 실험에 쓰일 명령을 미리 알게 되었고, 주어진 명령을 그대로 따르면 오히려 목표와 멀어질 수 있다고 생각했다. 그래서 전체 명령 중 최대 한 번은 원래 명령 대신 0부터 7까지의 다른 명령 하나를 수행할 수 있다. 명령을 바꾸지 않아도 된다.

모든 명령을 수행한 뒤 원철이가 목표 위치에 얼마나 가까워질 수 있는지 구하라.

첫째 줄에 원철이의 시작 좌표와 목표 좌표를 나타내는 정수 XM YM XB YB가 주어진다.

0 <= XM, YM, XB, YB <= 1,000,000

둘째 줄에 실험에 사용되는 명령의 개수 N이 주어진다.

1 <= N <= 100,000

셋째 줄에 명령을 나타내는 0부터 7까지의 정수 N개가 순서대로 주어진다.

실험을 모두 마친 뒤 원철이와 목표 위치 사이의 거리의 최솟값을 출력한다.

정답과의 절대 또는 상대 오차는 0.001까지 허용된다.