题目描述

小可可发明了一种新的正方形划分方法。

首先我们有一个正方形，称为第 $0$ 轮图形。将该正方形均匀划分成 $4$ 个部分------左上、右上、左下和右下，分别编号为 $A, B, C, D$，称为第 $1$ 轮图形。

接着，将第 $1$ 轮图形中的每一个部分再次划分为 $4$ 个部分，得到第 $2$ 轮图形。每个部分的命名方式为：上一轮编号 + 当前划分编号。例如，第 $1$ 轮中 $A$ 的右上部分编号为 $AB$。

第 $3$ 轮及以上的图形以此类推。

输入格式

从 square.in 输入。

第一行一个整数 $T$，表示测试数据组数。

接下来每组测试数据有两种形式之一：

• 0 n x y：询问第 $n$ 轮图形中第 $x$ 行第 $y$ 列的格子的编号
• 1 str：询问编号为 $str$ 的格子的位置

输出格式

向 square.out 输出。

对于每组测试数据：

• 若为 0 n x y，输出一个字符串 $str$
• 若为 1 str，输出三个整数 $n, x, y$

样例

输入

3
0 1 2 1
1 AB
0 2 3 4

输出

C
2 1 2
DB

样例解释

• 第 1 组：第 1 轮第 2 行第 1 列，对应编号 $C$
• 第 2 组：编号 $AB$ 位于第 2 轮第 1 行第 2 列
• 第 3 组：第 2 轮第 3 行第 4 列，对应编号 $DB$

说明

更多样例详见 square/square*.in/ans 文件。

数据范围

• 数据点 1：$1 \le T \le 10$，$1 \le n \le 2$
• 数据点 2~3：$1 \le T \le 10$，$1 \le n \le 10$
• 数据点 4~5：$1 \le T \le 5 \times 10^4$，$n = 10$
• 数据点 6：$1 \le T \le 5 \times 10^4$，$1 \le n \le 30$，仅 0 n x y
• 数据点 7：$1 \le T \le 5 \times 10^4$，$1 \le n \le 30$，仅 1 str
• 数据点 8~10：$1 \le T \le 5 \times 10^4$，$1 \le n \le 30$