COMCB - Complete Chess Boards

no tags 

BuggyD has always been fascinated with chess boards (though he really sucks at chess). He makes an observation that a chess board is complete with respect to knights and rooks and incomplete with respect to bishops (unless the dimensions are 1 × 1). A complete chess board is one in which it is possible to traverse all the squares starting from one possible square. Knights have always been his favourite pieces and he has decided to analyze completeness with respect to knights. Given the dimesions of the chess board help BuggyD find the lexicographically first path that visits all squares of a chess board with a knight.

Each square must be traversed only once. Note that a knight can only move two squares in one direction and one square perpendicular to the previous direction.

Input

The first line of the input contains an integer t, the number of test cases. t test cases follow.

Each test case consists of a single line cotaining two integers (X and Y) separated by a single space, specifying the dimensions of the chess board. The numbers 1 to X denote rows and the capital letters A to Y denote the coloumns. Each square is represented by its column index followed by it's row index - for example, B4 denotes the square in the 4th row and 2nd column.

The total number of squares on the chess board will be no more than 26.

Output

For each test case output one line consisting of the lexicographically first path of the knight, or "-1" (quotes for clarity) if the chess board is incomplete with respect to a knight.

Example

Input:
1
4 5

Output:
A1B3C1A2B4D3E1C2D4E2C3A4B2D1E3C4A3B1D2E4

hide comments
nadstratosfer: 2019-12-17 11:49:44

Didn't expect to use the approach that I previously only read about, would have skipped the problem assuming I didn't have the skillz! My initial ideas led nowhere though and adapting them to the situation, I've invented an algorithm others pick up at school. Waste of time for some I guess, awesome experience for me. Highly recommended problem for other self-trained coders!

Luv Karakoti: 2014-07-21 22:26:14

I am not able to comprehend the meaning of the phrase 'first lexicographical' path. Can please someone clarify this?
P.S.Are we ordering it in dictionary-wise? Because if we are ordering them as in the dictionary, then a sequence
A1B3C1A2B4C2 shall occur before
A1B3C1A2B4D3

Krunal: 2011-03-04 00:37:56

What if input is given as:
3
0 0
0 12
12 0
output should be "-1". Judge is not checking that I guess.

Krunal: 2011-03-04 00:18:07

One Help: It is "Lexicographic order"
For example,
(1) 3 4 has possible outputs "A1C2A3B1D2B3C1D3B2D1C3A2" & "A1C2A3B1D2B3C1A2C3D1B2D3"...latter one is the answer. I got two WAs :( , Be careful.
(2) For 4 6 "A1B3C1A2B4C2D4E2F4D3E1F3D2B1A3C4B2A4C3E4F2D1E3F1"

Last edit: 2011-03-04 00:38:48

Added by:Matthew Reeder
Date:2006-10-29
Time limit:1s
Source limit:30000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Al-Khawarizm 2006