分数: 1100 点
问题陈述
让 f(A, B),其中 A 和 B 为正整数,为满足以下条件的字符串:
- f(A, B) 有长度 A + B;
- f(A, B) 恰好包含 A 字母
A正是 B 字母B; - 的最长子串的长度 f(A, B) 由相同的字母组成(例如,
AAAAAorBBBB) 在上述条件下尽可能小; - 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
- 所有输入值均为整数。
部分分数 通过满足以下条件的测试集将获得
- 500 积分 1 \leq A_i, B_i \leq 10^3.
输入
输入由标准输入按以下格式给出:
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