H. Жаба в пустыне
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

В точке A бескрайней пустыни закопана стратегическая атомная подводная лодка «Жаба». Командование приняло решение сменить место базирования АПЛ на точку B. С командованием спорить бессмысленно, поэтому встал вопрос как переместить закопанную подводную лодку из одной точки плоской пустыни в другую.

Выяснилось, что проектировщики АПЛ продумали этот вопрос еще на этапе строительства и заложили в её конструкцию самый настоящий телепорт. Казалось, что проблема решена, но выяснилось что телепорт имеет всего K режимов работы, которые отличаются между собой только расстоянием перемещения объекта, то есть для каждого режима известно расстояние Li, на которое переместится лодка в заданном направлении при активации телепорта.

Необходимо найти минимальный по суммарной длине маршрут перемещения АПЛ с использованием телепорта.

Входные данные

В первой строке пять целых чисел XA, YA, XB, YB ( - 150 ≤ XA, YA, XB, YB ≤ 150) — декартовы координаты двух различных точек A и B, и K (0 < K ≤ 5) — количество режимов работы телепорта.

Во второй строке K целых чисел Li (0 < Li ≤ 150) — расстояние телепортации в каждом из режимов.

Выходные данные

В первой строке необходимо вывести длину минимального маршрута.

Во второй строке вывести число M — количество телепортаций в минимальном по длине маршруте.

В последующих M строках выведите по 2 действительных числа с точностью до 10 - 6 — координаты (xi, yi), в которых АПЛ окажется после i-ой телепортации.

Если минимальных по длине маршрутов несколько, выведите любой из них.

Примеры
Входные данные
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