Problem:


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



Sample input:
5
2 3 1 5
6 4 1 10
2 3 4 4
6 4 3 7
8 10 5 8


Sample output:
BABAB
AABAABAABB
A
BAABA
ABAB

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8
from numba.types import Omitted

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8, i8), cache=True)
def find_min_length(a, b):
    if a < b:
        a, b = b, a
    return (a + b) // (b + 1)

@njit((i8, i8, i8, i8), cache=True)
def f(a, b, c, d):
    L = find_min_length(a, b)
    ret = ''

    def test(a, b, L):
        # ...B の直後に A を a 個、B を b 個置けるかどうか
        ok = a >= 0 and b >= 0
        if a == 0:
            ok = ok and (b <= L - 1)
        else:
            ok = ok and (a <= L * (b + 1))
            ok = ok and (1 + b <= L * (a + 1))
        return ok

    def add(s, x, t, y, n):
        # 文字列に (s*x + t*y)*n を追加
        nonlocal c, d, ret
        if (x + y) * n < c:
            c -= (x + y) * n
            d -= (x + y) * n
            return
        m = (c - 1) // (x + y)
        c -= m * (x + y)
        d -= m * (x + y)
        n -= m
        while n and c <= d:
            if d <= x:
                ret += s * (d - c + 1)
                d = 0
                return
            if 1 <= c <= x:
                ret += s * (x - c + 1)
                c = x + 1
            ret += t * (min(d, x + y) - c + 1)
            c = 1
            d -= x + y
            n -= 1

    # AAABAAAB と n セット並べてしまって大丈夫かどうか
    l, r = 0, b + 100
    while l + 1 < r:
        m = (l + r) >> 1
        a1, b1 = a - L * m, b - m
        if test(a1, b1, L):
            l = m
        else:
            r = m
    n = l
    flag = n == 0
    add('A', L, 'B', 1, n)
    a -= L * n
    b -= n
    # 次に、A^kB
    l, r = 0, L
    while l + 1 < r:
        m = (l + r) // 2
        if test(a - m, b - 1, L):
            l = m
        else:
            r = m
    k = l
    flag = flag and k == 0
    if k:
        add('A', k, 'B', 1, 1)
        a -= k
        b -= 1
    # 以降は、Aは高々ひとつずつ
    if not a:
        add('B', b, 'A', 0, 1)
        return ret
    if not b:
        add('A', a, 'B', 0, 1)
        return ret

    # B^kA、kはなるべく少なく
    l, r = -1, L - 1
    if flag:
        r = L
    while l + 1 < r:
        m = (l + r) // 2
        if test(a, b - m, L) and b - m <= a * L:
            r = m
        else:
            l = m
    k = r

    if k >= 0:
        add('B', k, 'A', 1, 1)
        a -= 1
        b -= k
    # B^LA をいくつか
    n = min(b // L, a)
    add('B', L, 'A', 1, n)
    a -= n
    b -= n * L
    add('B', b, 'A', 0, 1)
    add('B', 0, 'A', a, 1)
    return ret

ABCD = np.array(read().split(), np.int64)[1:]

for a, b, c, d in ABCD.reshape(-1, 4):
    print(f(a, b, c, d))

Submission status: Accepted

Solution code:
for t in range(int(input())):
	a,b,c,d=map(int,input().split(' '));l,x,y,o=(a+b)//(min(a,b)+1),a+b,0,""
	if a*l<=b:x,y=0,a+b
	elif b*l>a:x,y=(a*l-b)//(l-1),(b*l-a)//(l-1)
	for i in range(c,d+1):o+="AB"[i%(l+1)==0] if i<=x else "BA"[(a+b-i+1)%(l+1)==0] if a+b-i+1<=y else "AB"[a-x+x//(l+1)-y//(l+1)==0]
	print(o)

Submission status: Accepted

Solution code:
for t in range(int(input())):
	a,b,c,d=map(int,input().split(' '));l,x,y,o=(a+b)//(min(a,b)+1),0,0,""
	if a*l<=b:y=a+b
	elif b*l<=a:x=a+b
	else:x,y=(a*l-b)//(l-1),(b*l-a)//(l-1)
	for i in range(c,d+1):o+="AB"[i%(l+1)==0] if i<=x else "BA"[(a+b-i+1)%(l+1)==0] if a+b-i+1<=y else "AB"[a-x+x//(l+1)-y//(l+1)==0]
	print(o)

Submission status: Accepted

Solution code:
for t in range(int(input())):
	a,b,c,d=map(int,input().split(' '))
	l,x,y,o=(a+b)//(min(a,b)+1),0,0,""
	if a*l<=b:y=a+b
	elif b*l<=a:x=a+b
	else:x,y=(a*l-b)//(l-1),(b*l-a)//(l-1)
	for i in range(c,d+1):o+="AB"[i%(l+1)==0] if i<=x else "BA"[(a+b-i+1)%(l+1)==0] if a+b-i+1<=y else "AB"[a-x+x//(l+1)-y//(l+1)==0]
	print(o)

Submission status: Accepted

Solution code:
T=int(input())
for t in range(T):
	a,b,c,d=map(int,input().split(' '))
	l,x,y,o=(a+b)//(min(a,b)+1),0,0,""
	if a*l<=b:y=a+b
	elif b*l<=a:x=a+b
	else:x,y=(a*l-b)//(l-1),(b*l-a)//(l-1)
	for i in range(c,d+1):o+="AB"[i%(l+1)==0] if i<=x else "BA"[(a+b-i+1)%(l+1)==0] if a+b-i+1<=y else "AB"[a-x+x//(l+1)-y//(l+1)==0]
	print(o)

Submission status: Accepted

Solution code:
T=int(input())
for TT in range(T):
    a,b,c,d=map(int,input().split(' '))
    l,x,y=(a+b)//(min(a,b)+1),0,0
    if a*l<=b:
        y=a+b
    elif b*l<=a:
        x=a+b
    else:
        x,y=(a*l-b)//(l-1),(b*l-a)//(l-1)
    out=""
    for i in range(c,d+1):
        if i<=x:
            out+="AB"[i%(l+1)==0]
        elif a+b-i+1<=y:
            out+="BA"[(a+b-i+1)%(l+1)==0]
        else:
            out+="AB"[a-x+x//(l+1)-y//(l+1)==0]
    print(out)

Submission status: Accepted

Solution code:
T=int(input())
for TT in range(T):
	a,b,c,d=map(int,input().split(' '))
	l,x,y,out=(a+b)//(min(a,b)+1),0,0,""
	if a*l<=b:y=a+b
	elif b*l<=a:x=a+b
	else:x,y=(a*l-b)//(l-1),(b*l-a)//(l-1) 
	for i in range(c,d+1):out+=("AB"[i%(l+1)==0]) if i<=x else "BA"[(a+b-i+1)%(l+1)==0] if a+b-i+1<=y else "AB"[a-x+x//(l+1)-y//(l+1)==0]
	print(out)

Submission status: Accepted

Solution code:
T=int(input())
for TT in range(T):
	a,b,c,d=map(int,input().split(' '))
	l,x,y=(a+b)//(min(a,b)+1),0,0
	if a*l<=b:
		y=a+b
	elif b*l<=a:
		x=a+b
	else:
		x,y=(a*l-b)//(l-1),(b*l-a)//(l-1) #Like G2 tong long
	out=""
	for i in range(c,d+1):
		if i<=x:
			out+="AB"[i%(l+1)==0]
		elif a+b-i+1<=y:
			out+="BA"[(a+b-i+1)%(l+1)==0]
		else:
			out+="AB"[a-x+x//(l+1)-y//(l+1)==0]
	print(out)

Submission status: Accepted

Solution code:
T=int(input())
for TT in range(T):
	a,b,c,d=map(int,input().split(' '))
	l,x,y=(a+b)//(min(a,b)+1),0,0
	if a*l<=b:
		y=a+b
	elif b*l<=a:
		x=a+b
	else:
		x,y=(a*l-b)//(l-1),(b*l-a)//(l-1)
	out=""
	for i in range(c,d+1):
		if i<=x:
			out+="AB"[i%(l+1)==0]
		elif a+b-i+1<=y:
			out+="BA"[(a+b-i+1)%(l+1)==0]
		else:
			out+="AB"[a-x+x//(l+1)-y//(l+1)==0]
	print(out)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math
Q = int(input())
num = lambda x: (x, max(0, (x - 1) // K))
sub = lambda xs, ys: [x - y for (x, y) in zip(xs, ys)]
for _ in range(Q):
    A, B, C, D = map(int, input().split())
    K = math.ceil(max(A, B) / (min(A, B) + 1))
    l, r = 0, A + 1
    while r - l > 1:
        m = (l + r) // 2
        rA, rB = sub((A, B), num(m))
        l, r = ((m, r), (l, m))[(rA + 1) * K < rB]

    f = ''
    for i in range(C - 1, D):
        na, nb = num(l)
        if i < na + nb:
            f += ('A', 'B')[i % (K + 1) == K] if i < nb * (K + 1) else 'A'
        else:
            nb, na = num(B - nb)
            j = A + B - i - 1
            f += ('B', 'A')[j % (K + 1) == K] if j < na * (K + 1) else 'B'
    print(f)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math
Q = int(input())
for _ in range(Q):
    A, B, C, D = map(int, input().split())
    K = math.ceil(max(A, B) / (min(A, B) + 1))
    lo, hi = 0, A + 1
    while hi - lo > 1:
        mid = (lo + hi) // 2
        rA, rB = A - mid, B - max(0, (mid - 1) // K)
        if (rA + 1) * K < rB:
            hi = mid
        else:
            lo = mid
 
    f = ''
    for i in range(C - 1, D):
        na = lo
        nb = max(0, (na - 1) // K)
        if i < nb * (K + 1):
            f += ('A', 'B')[i % (K + 1) == K]
        elif i < na + nb:f += 'A'
        else:
            j = A + B - i - 1
            nb = B - nb
            na = max(0, (nb - 1) // K)
            if j < na * (K + 1):f += ('B', 'A')[j % (K + 1) == K]
            else:f += 'B'
    print(f)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math
Q = int(input())
for _ in range(Q):
    A, B, C, D = map(int, input().split())
    K = math.ceil(max(A, B) / (min(A, B) + 1))
    lo, hi = 0, A + 1
    while hi - lo > 1:
        mid = (lo + hi) // 2
        rA, rB = A - mid, B - max(0, (mid - 1) // K)
        if (rA + 1) * K < rB:
            hi = mid
        else:
            lo = mid

    f = ''
    for i in range(C - 1, D):
        na = lo
        nb = max(0, (na - 1) // K)
        if i < nb * (K + 1):
            f += ('A', 'B')[i % (K + 1) == K]
        elif i < na + nb:
            f += 'A'
        else:
            j = A + B - i - 1
            nb = B - nb
            na = max(0, (nb - 1) // K)
            if j < na * (K + 1):
                f += ('B', 'A')[j % (K + 1) == K]
            else:
                f += 'B'
    print(f)

Submission status: Runtime Error

Solution code:
for t in range(int(input())):
	a,b,c,d=map(int,input().split(' '));l,o=(a+b)//(min(a,b)+1),"";x,y=(a*l-b)//(l-1),(b*l-a)//(l-1)
	if a*l<=b:x,y=0,a+b
	elif b*l<=a:x,y=a+b,0
	for i in range(c,d+1):o+="AB"[i%(l+1)==0] if i<=x else "BA"[(a+b-i+1)%(l+1)==0] if a+b-i+1<=y else "AB"[a-x+x//(l+1)-y//(l+1)==0]
	print(o)

Submission status: Runtime Error

Solution code:
for t in range(int(input())):
	a,b,c,d=map(int,input().split(' '));l,x,y,o=(a+b)//(min(a,b)+1),(a*l-b)//(l-1),(b*l-a)//(l-1),""
	if a*l<=b:x,y=0,a+b
	elif b*l<=a:x,y=a+b,0
	for i in range(c,d+1):o+="AB"[i%(l+1)==0] if i<=x else "BA"[(a+b-i+1)%(l+1)==0] if a+b-i+1<=y else "AB"[a-x+x//(l+1)-y//(l+1)==0]
	print(o)

Submission status: Runtime Error

Solution code:
for t in range(int(input())):
  a,b,c,d=map(int,input().split(' '));l,x,y,o=(a+b)//(min(a,b)+1),0,0,""
	if a*l<=b:y=a+b
	elif b*l<=a:x=a+b
	else:x,y=(a*l-b)//(l-1),(b*l-a)//(l-1)
	for i in range(c,d+1):o+="AB"[i%(l+1)==0] if i<=x else "BA"[(a+b-i+1)%(l+1)==0] if a+b-i+1<=y else "AB"[a-x+x//(l+1)-y//(l+1)==0]
	print(o)

Submission status: Runtime Error

Solution code:
import sys


def f(a, b):
    sa, sb = 'AB'
    if a < b:
        sa, sb = 'BA'
        a, b = b, a
    d = a // (b + 1)
    if a > (b + 1) * d:
        d += 1
    l = ([sa] * d + [sb]) * b
    l.extend([sa] * (a - d * b))
    if sa == 'A':
        return l
    else:
        return l[::-1]


def main():
    q = int(input())
    for line in sys.stdin:
        a, b, c, d = map(int, line.split())
        print(''.join(f(a, b)[c:d]))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import itertools

"""
def f(A,B):
  ans = ""
  ansl = 99999
  for s in itertools.permutations(["a"]*A+["b"]*B):
    s = "".join(s)
    l = 0
    p = -1
    for i in range(A+B):
      if i==A+B-1 or s[i]!=s[i+1]:
        l = max(l, i-p)
        p = i
    if l==ansl:
      ans = min(ans, s)
    elif l<ansl:
      ans = s
      ansl = l
  return ans
"""

def f2(A,B):
  if A==B:
    s = "AB"*A
  elif A>B:
    if A/(B+1)+(A%(B+1)>0) < A/B+(A%B>0):
      l = A/(B+1)
      n = A%(B+1)
      s = ""
      for i in range(B):
        s += "A"*(l+int(i<n))+"B"
      s += "A"*l
    else:
      l = A/B
      n = A%B
      s = ""
      for i in range(B):
        s += "A"*(l+int(i<n))+"B"
  else:
    if B/(A+1)+(B%(A+1)>0) < B/A+(B%A>0):
      l = B/(A+1)
      n = B%(A+1)
      s = "B"*l
      for i in range(A)[::-1]:
        s += "A"+"B"*(l+int(i<n))
    else:
      l = B/A
      n = B%A
      s = ""
      for i in range(A)[::-1]:
        s += "A"+"B"*(l+int(i<n))
  return s

"""
for A in range(1,6):
  for B in range(1,6):
    print A,B,f2(A,B)
"""

Q = input()
for _ in range(Q):
  A,B,C,D = map(int, raw_input().split())
  print f2(A,B)[C-1:D]