Problems
Кони ходят по очереди
Кони ходят по очереди
Переведите каждого из двух коней из одной клетки в другую за нименьшее общее число ходов.
Два коня не могут одновремнно находится в одной клетке. Ходы коней должны чередоваться.
Input data
Во входном файле записаны координаты первого и второго коня, затем координаты клеток, куда нужно их переместить.
Output data
Программа должна вывести последовательность ходов коней в виде нескольких строк. Первым символом в строке должен быть номер коня (1 или 2), затем, через пробел, координаты клетки, в которую он переставляется. Необходимо вывести любое из возможных оптимальных решений. Кони должны ходить по очереди, первым может ходить любой из коней, кони могут сделать различное число ходов.
Examples
Input example #1
a1 c2 c2 a1
Output example #1
1 b3 2 a1 1 d4 2 b3 1 c2 2 a1