Woncheol's Rebellion

Woncheol is participating in ALPS (Algorithm of Lonely Person Simulation), an experiment that observes how loneliness affects a person.

The experiment site is a two-dimensional integer grid. Initially, Woncheol is at (XM, YM) and faces upward. An observer gives Woncheol N commands in order. Each command is an integer k from 0 to 7. When command k is given, Woncheol rotates 45 * k degrees counterclockwise from his current direction, then moves one step to the adjacent integer grid point directly in front of him.

A woman Woncheol wants to get closer to is standing at (XB, YB). After the experiment ends, Woncheol wants the distance between his final position and her position to be as small as possible.

Woncheol learned all commands before the experiment and realized that following them exactly might move him farther away from the target. Therefore, for at most one command, he may execute a different command from 0 to 7 instead of the original command. He may also leave every command unchanged.

Find the minimum possible distance from Woncheol's final position to the target position after all commands are executed.

The first line contains four integers XM YM XB YB, the starting coordinates of Woncheol and the target coordinates.

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

The second line contains the number of commands N used in the experiment.

1 <= N <= 100,000

The third line contains N integers from 0 to 7, the commands in order.

Print the minimum possible distance between Woncheol and the target position after the experiment ends.

An absolute or relative error of at most 0.001 is accepted.