402062: GYM100637 H A frog in the desert

In the endless desert at point A there is a strategic nuclear submarine "The Frog" buried in the sand. The military headquarters decided to change the dislocation of The Frog to point B. Without having any chance to cancel that decision it came an issue to find out how the buried submarine could be moved from one point of the flat desert to another.

It turned out that The Frog's design engineering team solved that problem years ago during construction stage. Design engineers installed the real teleport on The Frog. The problem seemed over, as it turned out that the teleport has only K operation modes which differ only in the teleportation distance, that is for each mode there is a predefined distance L_i, which the submarine would move in a given direction.

It is necessary to find the minimal total route distance for The Frog to be moved to destination point.

The first line contains five integers X_A, Y_A, X_B, Y_B ( - 150 ≤ X_A, Y_A, X_B, Y_B ≤ 150) — Cartesian coordinates of two different points A and B, and K (0 < K ≤ 5) — the number of teleport modes. The second line contains K integers L_i (0 < Li ≤ 150) — the teleportation distance for each operation mode.

In the first line output the minimal route distance.

In the second line output number M — the count of teleportations in the minimal route.

In the following M lines output 2 real numbers each with the accuracy up to 10^- 6 — coordinates (x_i, y_i), where The Frog will be found after i-th teleportation.

If there are several minimal routes, output any of them.

1 1 4 5 3
2 3 5

5
2
2.2000000000 2.6000000000
4.0000000000 5.0000000000

0 0 18 0 2
10 5

20
3
4 3
14 3
18 0