eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Шахматы на торе

Шахматы на торе

Ліміт часу 10 секунд
Ліміт використання пам'яті 64 MiB

Маленький Петя научился играть в шахматы. Он даже умеет ставить мат двумя ладьями! И пару раз поставил своему старшему брату Васе мат. Вася расстроился и предложил Пете поиграть в шахматы на тороидальной доске n×n. Тороидальная доска получается из обычной скеливанием конца и начала каждой из вертикалей и горизонталей. Например, на тороидальной доске 8×8 король может походить с поля h1 на поле a1, или даже на a8. Ладья в этом случае ходит на произвольное положительное количество клеток по горизонтали или по вертикали (до тех пор, пока ей не мешает своя или чужая фигура).

Петя обнаружил, что на тороидальной доске поставить мат двумя ладьями несколько сложнее. Поэтому он обратился к вам за помощью.

Напишите программу, которая выводит, можно ли заматовать чёрного короля с помощью короля и двух ладей на шахматной тороидальной доске n×n, и если да, то сколько для этого потребуется ходов при оптимальной игре обеих сторон.

Вхідні дані

В первой строке задана размерность доски n (5n10). Во второй строке заданы координаты белого короля и двух ладей. В третьей строке заданы координаты чёрного короля. Координаты задаются с помощью маленькой латинской буквы, задающей вертикаль, и числа, задающего горизонталь. Первыми ходят белые. Позиция во входном файле корректна.

Вихідні дані

В первой строке выведите DRAW, если белым не удастся поставить мат, иначе выведите VICTORY. В случае победы белых выведите во второй строке число ходов, которые требуется сделать белым для постановки мата при оптимальной игре обеих сторон, а в третьей — один из оптимальных ходов белых. Пат считается ничьей.

Приклад

Вхідні дані #1
8
e1 b1 b3
c8
Вихідні дані #1
VICTORY
2
b1-b7
Джерело III Міжнародна Літня школа програмування 2012 м. Севастополь