← 返回题目列表

AtCoder · agc020_d

D. 最小最大重复次数

中文机器翻译题面 查看原题

分数: 1100 点

问题陈述

让 f(A, B),其中 A 和 B 为正整数,为满足以下条件的字符串:

  • f(A, B) 有长度 A + B;
  • f(A, B) 恰好包含 A 字母 A 正是 B 字母 B;
  • 的最长子串的长度 f(A, B) 由相同的字母组成(例如, AAAAA or 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
  • 所有输入值均为整数。

部分分数 通过满足以下条件的测试集将获得

  • 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