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
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

Legolas: 2014-01-12 17:19:59

For
1
4 5
Output:
A1B3A5C4D2B1A3B5D4C2B4A2C1D3C5A4B2D1C3D5
isn't this a valid sequence and lexicographically smaller
than the output given?

It's wrong, because the input is of the format column*row.
@Mathew Reeder: It would be better if you can make the input in normal form.

Last edit: 2014-01-12 17:29:11
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:0.391s
Source limit:30000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Al-Khawarizm 2006