题目描述

给定正整数 $A$ 和 $B$，定义函数 $f(A, B)$ 如下：

• $f(A, B)$ 的长度为 $A + B$；
• $f(A, B)$ 包含恰好 $A$ 个字母 A 和恰好 $B$ 个字母 B；
• 在满足上述条件的前提下，$f(A, B)$ 中最长的连续相同字母子串（例如 AAAAA 或 BBBB）的长度尽可能小；
• $f(A, B)$ 是满足上述条件的字典序最小的字符串。

例如，$f(2, 3)$ = BABAB，$f(6, 4)$ = AABAABAABB。

回答 $Q$ 个查询：找出 $f(A_i, B_i)$ 中从位置 $C_i$ 到位置 $D_i$（从 1 开始）的子串。

约束条件

• $1 \leq Q \leq 10^3$
• $1 \leq A_i, B_i \leq 5 \times 10^8$
• $1 \leq C_i \leq D_i \leq A_i + B_i$
• $D_i - C_i + 1 \leq 100$
• 所有输入值都是整数。

部分得分

• 通过满足 $1 \leq A_i, B_i \leq 10^3$ 的测试集将获得 $500$ 分。

输入

从标准输入读入输入数据，格式如下：

$Q$ $A_1$ $B_1$ $C_1$ $D_1$ $A_2$ $B_2$ $C_2$ $D_2$ $:$ $A_Q$ $B_Q$ $C_Q$ $D_Q$

输出

对于每个查询 $i$，按照输入顺序打印一行，其中包含 $f(A_i, B_i)$ 中从位置 $C_i$ 到位置 $D_i$（从 1 开始）的子串。

示例输入 1

5
2 3 1 5
6 4 1 10
2 3 4 4
6 4 3 7
8 10 5 8

示例输出 1

BABAB
AABAABAABB
A
BAABA
ABAB