Кони ходят по очереди

Переведите каждого из двух коней из одной клетки в другую за нименьшее общее число ходов.

Два коня не могут одновремнно находится в одной клетке. Ходы коней должны чередоваться.

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

Во входном файле записаны координаты первого и второго коня, затем координаты клеток, куда нужно их переместить.

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

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

Примеры