Chess on a Torus
Little Petya has learned to play chess and is now capable of checkmating with two rooks! He even managed to checkmate his older brother Vasya a few times. Upset by this, Vasya proposed a new challenge: playing chess on a toroidal board of size n×n. A toroidal board is unique because the edges are connected, meaning the board wraps around both vertically and horizontally. For instance, on a toroidal 8×8 board, a king can move from square h1 to a1, or even to a8. Similarly, a rook can move any number of squares along a rank or file, provided it is not obstructed by another piece.
Petya discovered that checkmating with two rooks on a toroidal board is quite challenging. Thus, he seeks your assistance.
Your task is to write a program that determines whether it is possible for the white pieces to checkmate the black king using a king and two rooks on a toroidal n×n chessboard. If checkmate is possible, the program should also calculate the minimum number of moves required, assuming optimal play from both sides.
Input
The first line contains the size of the board n (5 ≤ n ≤ 10). The second line provides the coordinates of the white king and the two rooks. The third line gives the coordinates of the black king. The coordinates are specified using a lowercase letter for the file and a number for the rank. White moves first. The input position is guaranteed to be valid.
Output
On the first line, output DRAW if the white pieces cannot achieve checkmate. Otherwise, output VICTORY. If a victory is possible, the second line should display the number of moves required for white to checkmate with optimal play from both sides. The third line should show one of the optimal moves for white. Note that a stalemate is considered a draw.