Square Partition Conversion

Keko has invented a new method to partition a square. Initially, there is a square which we call the round $0$ figure. In the first round (round $1$), the square is divided evenly into 4 smaller squares: top-left, top-right, bottom-left, and bottom-right. They are labeled as $\tt{A}$, $\tt{B}$, $\tt{C}$, and $\tt{D}$ respectively.

For every subsequent round, each square from the previous round is divided into 4 parts following the same pattern. In round $2$, for example, the four parts of the square originally labeled as $\tt{A}$ will be labeled $\tt{AA}$, $\tt{AB}$, $\tt{AC}$, and $\tt{AD}$ respectively (where the second letter represents the division within that square). In general, at round $n$, each cell is identified by a string of length $n$ composed of the characters {A, B, C, D}.

The mapping from letter to position within a sub-square is defined as follows (each sub-square is a $2\times2$ grid):

• $\tt{A}$: top-left cell (row offset 0, column offset 0)
• $\tt{B}$: top-right cell (row offset 0, column offset 1)
• $\tt{C}$: bottom-left cell (row offset 1, column offset 0)
• $\tt{D}$: bottom-right cell (row offset 1, column offset 1)

When the entire square is subdivided for round $n$, the grid size becomes $2^n \times 2^n$. Rows are numbered from top to bottom starting from $1$, and columns are numbered from left to right starting from $1$.

Your task is to convert between a cell's identifier (a string consisting of letters A, B, C, D) and its position (row and column numbers) in the grid.

The program should support two types of queries. Each test case begins with an integer indicating the query type:

1. If the query type is 1, then the next token is a string representing the cell's identifier. You must output the cell's position in the format "row column" (both 1-indexed).

2. If the query type is 2, then the next three integers are provided: $n$, $r$, and $c$, where $n$ is the round number (i.e. the length of the identifier), and $r$ and $c$ (1-indexed) specify the cell's row and column in the $2^n \times 2^n$ grid. You must output the corresponding cell identifier.

For example, given the identifier \tt{AB} in query type 1, the answer would be "1 2". Conversely, for query type 2 with input "2 1 2", the expected identifier is \tt{AB}.

Note: It is guaranteed that the provided row and column numbers will be valid for the specified $n$.

inputFormat

The first line contains an integer $T$, the number of test cases. Each of the following $T$ test cases begins with an integer indicating the query type.

If the query type is 1, it is followed by a string $S$ (without spaces) representing the cell identifier.

If the query type is 2, it is followed by three integers: $n$, $r$, and $c$, where $n$ (the number of rounds), $r$ (the row number), and $c$ (the column number) describe the position in a $2^n \times 2^n$ grid.

All tokens are separated by whitespace.

outputFormat

For each test case, output a single line:

• If the query type is 1, output two integers separated by a space: the row and column (both 1-indexed) corresponding to the given identifier.
• If the query type is 2, output the cell's identifier (a string consisting of exactly $n$ characters from the set {A, B, C, D}).

sample

3
1 AB
2 2 1 2
1 D

1 2
AB
2 2

</p>