Problem J. Путешествие
Input file name: travel.in
Output file name: travel.out
Time limit: 2 s
Memory limit: 256 MB

Коля очень любит путешествовать, но еще больше он любит собирать мили. Он живет в городе A, финальная часть соревнования, в которую он вышел, будет проходить в городе B. Организаторы сообщили Коле, что он может выбрать любой маршрут. Коля очень суеверный и при путешествии на соревнование всегда делает нечётное количество пересадок.

Приятная в общении девушка сообщила Коле, что он может сделать не более K пересадок. К его счастью, он может делать пересадку в любой точке планеты (даже если там нет аэропорта). Коля не хочет, чтобы его заподозрили в пустой трате денег организаторов, поэтому пересадки он хочет делать в различных точках.

В нашем случае планета — сфера с радиусом 3959 миль и центром в начале координат. Две точки считаются различными, если расстояние между ними не менее одной сотой мили по сфере. При перемещении из точки X в точку Y всегда выбирается кратчайшее расстояние по сфере между этими точками, в этом случае Коле на его счет будет добавлено количество миль, равное этому кратчайшему расстоянию.

Заметим, что если Коля определил некоторую последовательность S из n точек для пересадки, то его путешествие будет следующим: AS1, S1S2, …, Sn − 1Sn, SnB.

Input

В первой строке записаны три целых числа XA, YA, ZA — координаты города A. Во второй строке записаны три целых числа XB, YB, ZB — координаты города B. В третьей — единственное целое число K (1 ≤ K ≤ 100). Точки A и B лежат на сфере и не совпадают. Все координаты заданы в милях.

Output

В первой строке выведите выведите два числа: максимальное количество миль (с относительной точностью не менее 10−9), которое Коля может заработать, и количество пересадок, которое он при этом должен совершить. Далее для каждой пересадки укажите, в какой точке планеты она должна быть совершена (три вещественных числа), точка должна быть на планете с относительной точностью не менее 10−9. Расстояние между любыми двумя точками путешествия (A, B, последовательность S), не обязательно последовательными, должно быть не менее 0.01 мили по сфере.

Example

travel.in travel.out
3959 0 0
-3959 0 0
1
12437.56531556199 1
0 2799.43574671754 -2799.43574671754