D - Min Max Repetition Editorial /

Time Limit: 2 sec / Memory Limit: 512 MB

配点 : 1100 点

問題文

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

Score : 1100 points

Problem Statement

Let f(A, B), where A and B are positive integers, be the string satisfying the following conditions:

  • f(A, B) has length A + B;
  • f(A, B) contains exactly A letters A and exactly B letters B;
  • The length of the longest substring of f(A, B) consisting of equal letters (ex., AAAAA or BBBB) is as small as possible under the conditions above;
  • f(A, B) is the lexicographically smallest string satisfying the conditions above.

For example, f(2, 3) = BABAB, and f(6, 4) = AABAABAABB.

Answer Q queries: find the substring of f(A_i, B_i) from position C_i to position D_i (1-based).

Constraints

  • 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
  • All input values are integers.

Partial Score

  • 500 points will be awarded for passing the testset satisfying 1 \leq A_i, B_i \leq 10^3.

Input

Input is given from Standard Input in the following format:

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

Output

For each query i in order of input, print a line containing the substring of f(A_i, B_i) from position C_i to position D_i (1-based).

Sample Input 1

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

Sample Output 1

BABAB
AABAABAABB
A
BAABA
ABAB