eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 64 MiB

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

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

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