C. Нахождение порядка
ограничение по времени на тест
4 seconds
ограничение по памяти на тест
512 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Девочка Лена очень любит порядок и пытается везде его искать. Как-то раз она собиралась в университет и заметила, что в комнате ужасный беспорядок — все вещи из ее сумочки разбросаны по комнате. Конечно же, она захотела их собрать в сумочку. Беда только в том, что девочка не может нести более двух вещей одновременно и не может переносить сумочку. Также если она взяла вещь, то положить ее куда-нибудь кроме сумочки она не может — ей мешает врожденное чувство идеального порядка.

Вам заданы координаты сумочки и координаты вещей в некоторой декартовой системе координат. Известно, что девочка проходит путь между двумя объектами за время равное квадрату длины отрезка соединяющего точки, в которых находятся объекты. Также известно, что изначально координаты девочки и сумочки совпадают. Требуется найти такой порядок действий, при котором девочка соберет все вещи в сумочку за минимальное время.

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

В первой строке входного файла заданы координаты сумочки xs, ys. Во второй строке задано число n (1 ≤ n ≤ 24) — количество вещей у девочки. В следующих n строках заданы координаты вещей девочки. Все координаты не превосходят по модулю 100. Координаты всех заданных во входных данных объектов различны. Все заданные числа — целые.

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

В первую строку выведите единственное число минимальное время, требуемое девочке чтобы собрать все вещи.

Во вторую строку выведите возможный оптимальный путь Лены. Каждая вещь обозначается своим порядковым номером при задании во входных данных (от 1 до n), а позиция сумочки обозначается числом 0. Путь должен начинаться и заканчиваться в позиции сумочки. Если решений несколько, выведите любое из них.

Примеры
Входные данные
0 0
2
1 1
-1 1
Выходные данные
8
0 1 2 0
Входные данные
1 1
3
4 3
3 4
0 0
Выходные данные
32
0 1 2 0 3 0