Марсоход

Один из крупнейших заказчиков компании Luxoft заказал разработку программы управления самоходной установки 'Марсоход-2012', которая отправится на красную планету в следующем году.
Вам необходимо разработать программу для навигации Марсохода таким образом, чтобы минимизировать количество шагов, затрачиваемое им для преодоления препятствия. Чтобы сдать программу, достаточно чтобы марсоход дошел до цели. Однако, игроку будут начисляться дополнительные баллы в случае, если его программа приведет Марсоход к цели за минимально возможное количество шагов.

Исходные данные (файл input.txt)
Карта местности 11х11 клеток записана как 11 строк по 11 символов + символы переноса строки.
Значения символов на карте:

Символ 'W' означает препятствие и туда двигаться нельзя.

Символ '<пробел>'означает равнину, по которой двигаться можно.

Символ 'o' означает преодолимое препятствие, любое движение на котором считается за два хода.

Символ 'X' означает цель, в которую Марсоход должен двигаться.



Значения символов, которые программа должна напечатать в консоль:

Символ 'W' - Марсоход должен сделать один шаг вперед. Ход при этом начисляется за покинутую клетку.

Символ 'Q' - Марсоход должен повернуть налево на 90 градусов. Стоимость движения = 1 ход.

Символ 'R' - Марсоход должен повернуть направо на 90 градусов. Стоимость движения = 1 ход.



Изначально Марсоход расположен в центре карты (5х5) по направлению "вниз".
Пример:

Пример содержимого файла input.txt:

WWWWWWWWWWW
WWWWWWWWWWW
WWWWWWWWWWW
WWWWWWWWWWW
WWWWWWWWWWW
WWWWW WWWWW
WWWWW WWWWW
WWWWW WWWWW
WWWWW    XW
WWWWWWWWWWW
WWWWWWWWWWW

Пример вывода консоли:


WWWQWWWW