Knight's Moves: Compute Valid Chess Knight Transitions

Given the position of a knight on an 8x8 chessboard, compute all the valid moves the knight can make. The position is provided in the standard algebraic notation (for example, d4). Recall that a knight moves in an 'L' shape: two squares in one direction and then one square perpendicular to that. Mathematically, if the knight is at position \( (x, y) \), then its possible moves are given by adding one of the offsets \( (\pm2, \pm1) \) and \( (\pm1, \pm2) \) such that the resulting coordinates satisfy \( 1 \leq x \leq 8 \) and \( 1 \leq y \leq 8 \).

Your task is to output the list of valid moves in lexicographical order (based on standard string ordering) separated by a single space. See the input and output sections for further clarifications.

inputFormat

The input is provided via standard input (stdin). A single line containing a string of length 2 representing the knight's current position in algebraic notation (for example, d4).

outputFormat

Output a single line to standard output (stdout) containing all valid moves of the knight in lexicographical order, separated by a single space. For example, if the valid moves are b3, b5, c2, c6, e2, e6, f3, f5, then the output should be:

b3 b5 c2 c6 e2 e6 f3 f5

d4

b3 b5 c2 c6 e2 e6 f3 f5