Ученые в IT-компании разработали квантовый суперкомпьютер. Опытный образец, разработанный учеными, содержит n × m квантовых процессоров, организованных в виде сетки из n строк и m столбцов. Обозначим процессор в j -й ячейке i -й строки как ( i , j ) .

Ученые запустили квантовый суперкомпьютер, однако после окончания вычислений произошел сбой в электропитании, из-за чего часть процессоров оказалась повреждена. В распоряжении исследователей осталось всего лишь k уцелевших процессоров.

Результат вычислений находится в памяти процессора (1, 1) , а устройство вывода подключено к процессору ( n , m ) . Для передачи информации от одного процессора к другому используется квантовая телепортация. Особенность квантовой телепортации заключается в том, что с увеличением расстояния возникает нестабильность, требующая дополнительной энергии. Поэтому чтобы обеспечить перенос информации от процессора ( x _i , y _i ) к процессору ( x _j , y _j ) требуется 2 ^{max (| x _i - x _j |, | y _i - y _j |)} единиц энергии. Ученые хотят перенести информацию с процессора (1, 1) на процессор ( n , m ) , затратив минимальное количество энергии. При этом можно использовать в качестве промежуточных другие уцелевшие процессоры. Использовать поврежденные процессоры нельзя.

Требуется написать программу, которая по описанию уцелевших процессоров определяет, каким образом необходимо передавать данные между процессорами, чтобы перенести информацию из процессора (1, 1) в процессор ( n , m ) , потратив минимальное суммарное количество энергии.