分数：$1100$ 分

问题描述

设 $f(A, B)$ 为满足以下条件的字符串，其中 $A$ 和 $B$ 为正整数：

• $f(A, B)$ 的长度为 $A + B$；
• $f(A, B)$ 包含恰好 $A$ 个字母 A 和恰好 $B$ 个字母 B；
• 在上述条件下，$f(A, B)$ 中相同字母的最长子串长度尽可能小；
• $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 的索引）。

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

BABAB
AABAABAABB
A
BAABA
ABAB