Knight Moves on Chessboard

You are given the current position of a knight on a standard 8x8 chessboard. A knight moves in an L-shape: two squares in one direction and then one square perpendicular to that. Your task is to compute all possible moves for the knight from the given position. The moves should be sorted in lexicographical order (i.e. as strings). Note that a valid chessboard column is one of A to H and a valid row is one of 1 to 8.

Mathematically, if the knight is at position \( (c, r) \) where \( c \) is the column (with \( A=1, B=2, \ldots, H=8 \)) and \( r \) is the row, then the knight can move to positions: \[ (c + dx, r + dy) \quad \text{for } (dx, dy) \in \{(-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)\}. \] Make sure the resulting position is on the chessboard: \(1 \leq c+dx \leq 8\) and \(1 \leq r+dy \leq 8\).

inputFormat

The input consists of a single line containing the knight's current position as a two-character string (e.g., "E4").

outputFormat

Output a single line with the list of all valid moves the knight can make from the given position, sorted lexicographically and separated by a single space. For example, for input "A1", the output should be "B3 C2".

E4

C3 C5 D2 D6 F2 F6 G3 G5