Задача B. (20081220) Ботвинник и Фишер ≡

Условие

В неофициальном матче по шахматам встречаются шестой чемпион мира Михаил Ботвинник и одиннадцатый чемпион Роберт Фишер. Идёт сотая игра матча. Сделано уже больше сотни ходов. После десятого перерыва в партии Михаил и Роберт решили закончить партию максимально быстро, благо их не очень волновал её результат. К счастью, на доске осталось всего 4 фигуры. У каждого из гроссмейстеров осталось по одной тяжёлой фигуре (ладья или ферзь) и, естественно, королю. Игра считается законченной, когда один из королей заматован, или у каждой из сторон остался только король. В первом случае игрок, которого заматовали, проигрывает, а во втором объявляется ничья. Все другие правила окончания игры (в том числе правило троекратного повторения позиции и правило пятидесяти ходов) в этой партии отменены.

Ваша задача — найти самый быстрый способ закончить игру.

Формат входного файла

На первой строке находится описание позиции белых фигур, на второй — чёрных. Каждая фигура определяется тремя символами. Первый — это тип фигуры: K — это король, Q — ферзь, а R — ладья. Второй и третий символ содержат описание клетки, на которой стоит данная фигура, буква соответствует номеру вертикали, а цифра — горизонтали. Например, Ka1 обозначает, что король стоит в левой нижней клетке доски. Описания фигур внутри строки разделяются пробелом. Гарантируется, что позиция корректна. Право хода в данной позиции принадлежит чёрным. Первой фигурой в каждой строке является король.

Формат выходного файла

Выведите кратчайшую последовательность ходов, приводящую к концу игры. каждый ход записывается шестью символами: первый это название фигуры, следующие два это клетка, на которой фигура стояла до хода, четвёртый это дефис ('-'), а пятый и шестой — клетка, в которую фигура походила. Если оптимальных решений несколько разрешается вывести любое.

Примеры тестов

Ka1 Qb5
Ka3 Qa8

Qa8-a4
Qb5-b2

Ka1 Qf5
Ka3 Rh8

Rh8-f8
Qf5-f1
Rf8-f1