stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <algorithm>

#include <iostream>

#include <math.h>

#include <stdio.h>

#include <string>

#include <sstream>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <cmath>

#include <bitset>

 

using namespace std;

bool hasSearched[100][100000];

int dp[100][100000];

int v[100] = {0};

int w[100] = {0};

int N;



void init(){

	for(int i = 0; i < 100; i++){

		for(int j = 0; j < 100000; j++){

			hasSearched[i][j] = false;

		}

	}

}



int solve(int i,int U){

	if(i == N){

		return 0;

	}else if(U < w[i]){

		return solve(i+1,U);

	}

	if(hasSearched[i][U] == true) return dp[i][U];

	int res1,res2;

	res1 = solve(i+1,U-w[i]) + v[i];

	res2 = solve(i+1,U);

	dp[i][U] = max(res1,res2);

	hasSearched[i][U] = true;

	return max(res1,res2);

}



int main()

{

	init();

	int W;

	cin>>N>>W;

	for(int i = 0; i < N; i++){

		cin>>v[i]>>w[i];

	}

	cout<<solve(0,W)<<endl;

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 11.41181320250412x):
#include <algorithm>

#include <iostream>

#include <math.h>

#include <stdio.h>

#include <string>

#include <sstream>

#include <vector>

#include <set>

#include <stack>

#include <map>

#include <cmath>

#include <queue>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;

typedef unsigned long long ll;

#define MAX_N 100







int main()

{

	int n,maxWeight;

	cin>>n>>maxWeight;

	int *value = new int[n];

	int *weight = new int[n];

	vector<vector<int>> dp(n+1,vector<int>(maxWeight+1));

	rep(i,n+1){

		rep(j,maxWeight+1) dp[i][j] = 0;

	}

	rep(i,n){

		cin>>value[i]>>weight[i];

	}

	for(int i = 1; i <= n; i++){

		for(int j = 0; j <= maxWeight; j++){

			if( j >= weight[i-1]){

				dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i-1]] + value[i-1]);

			}else{

				dp[i][j] = dp[i-1][j];

			}

		}

	}

	int ans = 0;

	rep(j,maxWeight+1){

		ans = max(ans,dp[n][j]);

	}

	cout<<ans<<endl;

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstring>



using namespace std;



const int INF = -1;



int N, W;

int v[101], w[101];

int dp[101][10001];



// i???????????§???????????§???j??\????????????

int solve(int i, int j) {

    if (dp[i][j] != INF) return dp[i][j];

    int res;

    if (i == N) res = 0;

    else if (j < w[i]) res = solve(i+1, j);

    else res = max(solve(i+1, j), solve(i+1, j - w[i]) + v[i]);

    return dp[i][j] = res;

}



int main() {

    memset(dp, -1, sizeof(dp));

    cin >> N >> W;

    for (int i = 0; i < N; ++i) cin >> v[i] >> w[i];

    cout << solve(0, W) << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.9550984260647444x):
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))

using ll = long long;

using P = pair<int, int>;

using namespace std;



template<class T> void vin(vector<T>& v, int n) {

    v.resize(n);

    for (int i = 0; i < n; ++i) {

        cin >> v[i];

    }

}



int N, W;

int w[1010], v[1010];

int dp[101][101010];



int rec(int i, int j) {

    if (dp[i][j] >= 0) return dp[i][j];

    int res;

    if (i >= N) {

        res = 0;

    }

    else if (j < w[i]) {

        res = rec(i + 1, j);

    }

    else {

        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]);

    }

    return (dp[i][j] = res);

}



int main() {

    cin >> N >> W;

    rep(i, N) {

        cin >> v[i] >> w[i];

    }

    fill(dp[0], dp[N], -1);

    cout << rec(0, W) << endl;

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstring>



using namespace std;



const int INF = -1;



int N, W;

int v[101], w[101];

int dp[101][10001];



// i???????????§???????????§???j??\????????????

int solve(int i, int j) {

    if (dp[i][j] != INF) return dp[i][j];

    int res;

    if (i == N) res = 0;

    else if (j < w[i]) res = solve(i+1, j);

    else res = max(solve(i+1, j), solve(i+1, j - w[i]) + v[i]);

    return dp[i][j] = res;

}



int main() {

    memset(dp, -1, sizeof(dp));

    cin >> N >> W;

    for (int i = 0; i < N; ++i) cin >> v[i] >> w[i];

    cout << solve(0, W) << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.418390419522541x):
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))

using ll = long long;

using P = pair<int, int>;

using namespace std;



template<class T> void vin(vector<T>& v, int n) {

    v.resize(n);

    for (int i = 0; i < n; ++i) {

        cin >> v[i];

    }

}



int N, W;

int v[101], w[101];

int dp[101][10001];



int rec(int idx, int cap) {

    if (dp[idx][cap] >= 0) return dp[idx][cap];

    int ret;

    if (idx >= N) {

        ret = 0;

    }

    else if (cap < w[idx]) {

        ret = rec(idx+1, cap);

    }

    else {

        ret = max(rec(idx+1, cap), rec(idx+1, cap-w[idx])+v[idx]);

    }

    return (dp[idx][cap] = ret);

}



int main() {

    cin >> N >> W;

    rep(i, N) {

        cin >> v[i] >> w[i];

    }

    fill(dp[0], dp[N], -1);

    cout << rec(0, W) << endl;

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))

using ll = long long;

using P = pair<int, int>;

using namespace std;



template<class T> void vin(vector<T>& v, int n) {

    v.resize(n);

    for (int i = 0; i < n; ++i) {

        cin >> v[i];

    }

}



int N, W;

int w[1010], v[1010];

int dp[101][101010];



int rec(int i, int j) {

    if (dp[i][j] >= 0) return dp[i][j];

    int res;

    if (i >= N) {

        res = 0;

    }

    else if (j < w[i]) {

        res = rec(i + 1, j);

    }

    else {

        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]);

    }

    return (dp[i][j] = res);

}



int main() {

    cin >> N >> W;

    rep(i, N) {

        cin >> v[i] >> w[i];

    }

    fill(dp[0], dp[N], -1);

    cout << rec(0, W) << endl;

    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 2.2599324722571397x):
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))

using ll = long long;

using P = pair<int, int>;

using namespace std;



template<class T> void vin(vector<T>& v, int n) {

    v.resize(n);

    for (int i = 0; i < n; ++i) {

        cin >> v[i];

    }

}



int N, W;

int v[101], w[101];

int dp[101][10001];



int rec(int idx, int cap) {

    if (dp[idx][cap] >= 0) return dp[idx][cap];

    int ret;

    if (idx >= N) {

        ret = 0;

    }

    else if (cap < w[idx]) {

        ret = rec(idx+1, cap);

    }

    else {

        ret = max(rec(idx+1, cap), rec(idx+1, cap-w[idx])+v[idx]);

    }

    return (dp[idx][cap] = ret);

}



int main() {

    cin >> N >> W;

    rep(i, N) {

        cin >> v[i] >> w[i];

    }

    fill(dp[0], dp[N], -1);

    cout << rec(0, W) << endl;

    return 0;

}
// Slower C++ solution:
#include <stdio.h>

#include<math.h>

#include <algorithm>

using namespace std;



int value[100],weight[100];

int N,W;

int** table;





int func(int index,int sum_w,int sum_v){

	if(table[W-sum_w][index] != 0){

		return sum_v + table[W-sum_w][index];

	}else{

		if(index < N-1){

			if(W-sum_w >= weight[index]){

				table[W-sum_w][index] = max(func(index+1,sum_w+weight[index],value[index]),func(index+1,sum_w,0));

				return sum_v + table[W-sum_w][index];

			}else{

				table[W-sum_w][index] = func(index+1,sum_w,0);

				return sum_v + table[W-sum_w][index];

			}



		}else{

			if(W-sum_w >= weight[index]){

				table[W-sum_w][index] = value[index];

				return sum_v + value[index];

			}else{

				table[W-sum_w][index] = 0;

				return sum_v;

			}

		}

	}

}



int main(){



	scanf("%d %d",&N,&W);



	table = new int*[10001];

	for(int i = 0; i < 10001; i++){

		table[i] = new int[100];

		for(int k=0;k < 100;k++)table[i][k] = 0;

	}



	for(int i=0;i<N;i++){

		scanf("%d %d",&value[i],&weight[i]);

	}



	printf("%d\n",func(0,0,0));



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.839107522821439x):
#include <stdio.h>

#include <cmath>

#include <algorithm>



using namespace std;



int main(){



	int N,W;

	scanf("%d %d",&N,&W);



	int w[N],v[N];



	int** dp = new int*[W+1];

	for(int i=0; i < W+1; i++){

		dp[i] = new int[N+1];

		for(int k=0; k < N+1; k++)dp[i][k] = 0;

	}



	for(int i=0; i < N; i++){

		scanf("%d %d",&v[i],&w[i]);

	}





	for(int i = N-1; i >= 0; i--){

		for(int k = 1; k <= W; k++){

			if(w[i] <= k){

				dp[k][i] = max(dp[k][i+1],dp[k-w[i]][i+1] + v[i]);

			}else{

				dp[k][i] = dp[k][i+1];

			}

		}

	}



	printf("%d\n",dp[W][0]);



    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

#include <cstring>

#define MAX_INT  100005

#define MAX_N  100

#define MAX_W  10000

using namespace std;





//??\???

int N, W;

int w[MAX_N], v[MAX_N];



// dp table

int dp[MAX_N + 1][MAX_W + 1];





// i: i????????\?????? item ?????????

// rw: ?????????????????? w ??\???

// return: ???????????????????????§???

int rec(int i, int rw) {

  // dp lookup

  if (dp[i][rw] > 0) {

    return dp[i][rw];

  }



  int res;

  if(i == N) {

    // ?????????????????????

    res = 0;

  } else if ( rw < w[i] ) {

    // ??\?????????

    res = rec(i + 1, rw);

  } else {

    // ??\???????????¨????????????

    // ??\????????´?????¨??\???????????´??????????????????

    res = max( rec(i + 1, rw), rec(i + 1, rw - w[i]) + v[i] );

  }



  dp[i][rw] = res;

  return res;



}







int main() {



  memset(dp, -1, sizeof(dp));



  cin >> N >> W;

  for (int i = 0; i < N; i++) {

    cin >> v[i] >> w[i];

  }



  cout << rec(0, W) << endl;



}

// Faster C++ solution for the same problem (measured speedup: 5.0621934022226425x):
#include <iostream>

#include <iomanip>

#include <algorithm>

#include <vector>



#define debug(x) cout << #x << "==" << x << endl;



const int INF = 1e+8;



using namespace std;



//??\???

#define MAX_N 100

#define MAX_W 10000

int N, W_LIM;

int V[MAX_N], W[MAX_N];



// dp table

int dp[MAX_N][MAX_W];

bool checked[MAX_N][MAX_W];



// int n: n???????????§?????????????????£???

// int w: w??\??????????????§

// return: ?????§?????????

int rec(int i, int w) {



  if( i == -1 ) { return 0; }   // out of bounds ??????????????????!



  if(checked[i][w] == true) {return dp[i][w]; }

  checked[i][w] = true;



  int ret;



  if (w < W[i]) {

    ret = rec(i - 1, w);

  } else {

    ret = max( rec(i - 1, w), rec(i - 1, w - W[i]) + V[i]);

  }



  return dp[i][w] = ret;



}





int main() {

  ios::sync_with_stdio(false);



  cin >> N >> W_LIM;



  for(int i = 0; i < N; i++) {

    cin >> V[i] >> W[i];

  }



  cout << rec(N-1, W_LIM) << endl;



  return 0;

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

#include <cstring>

#define MAX_INT  100005

#define MAX_N  100

#define MAX_W  10000

using namespace std;





//??\???

int N, W;

int w[MAX_N], v[MAX_N];



// dp table

int dp[MAX_N + 1][MAX_W + 1];





// i: i????????\?????? item ?????????

// rw: ?????????????????? w ??\???

// return: ???????????????????????§???

int rec(int i, int rw) {

  // dp lookup

  if (dp[i][rw] > 0) {

    return dp[i][rw];

  }



  int res;

  if(i == N) {

    // ?????????????????????

    res = 0;

  } else if ( rw < w[i] ) {

    // ??\?????????

    res = rec(i + 1, rw);

  } else {

    // ??\???????????¨????????????

    // ??\????????´?????¨??\???????????´??????????????????

    res = max( rec(i + 1, rw), rec(i + 1, rw - w[i]) + v[i] );

  }



  dp[i][rw] = res;

  return res;



}







int main() {



  memset(dp, -1, sizeof(dp));



  cin >> N >> W;

  for (int i = 0; i < N; i++) {

    cin >> v[i] >> w[i];

  }



  cout << rec(0, W) << endl;



}

// Faster C++ solution for the same problem (measured speedup: 5.006843972482288x):
#include <iostream>

#include <vector>



using namespace std;



template<typename T>

vector<vector<T>> make_2d_vector(size_t rows, size_t cols, T init)

{ return vector< vector<T> >(rows, vector<T>(cols, init)); }





#define debug(x) cout << #x << "==" << x << endl;



const int inf = 100000000;



typedef long long ll;



int main() {

  ios::sync_with_stdio(false);



  int N, W;

  cin >> N >> W;





  vector<int> v(N), w(N);

  for(int i = 0; i < N; i++) { cin >> v[i] >> w[i]; }



  // // dp

  // dp[i][j] := i?????? ?????§?????????????????£??? ??????j ??\?????§????????§??????

  vector< vector<int> > dp = make_2d_vector(N+1, W+1, 0);

  for(int i = 1; i <= N; i++ ) {

    for(int j = 1; j <= W; j++ ) {

      if( j >= w[i-1] ) {

        dp[i][j] = max( dp[i-1][j], dp[i-1][ j-w[i-1] ] + v[i-1]);

      } else {

        dp[i][j] = dp[i-1][j];

      }

    }

  }



  cout << dp[N][W] << "\n";











  // dp[i][j] := i???????????§?????????????????£??? ??????j??\??? ??§????????§??????

  // vector< vector<int> > dp = make_2d_vector(N+1, W+1, 0);

  // for(int i = 1; i <= N; i++) {

  //   for(int j = 0; j <= W; j++) {

  //     if( w[i-1] <= j )

  //       dp[i][j] = max( dp[i-1][j], dp[i-1][j - w[i-1]] + v[i-1]);

  //     else

  //       dp[i][j] = dp[i-1][j];

  //   }

  // }

  // cout << dp[N][W] << "\n";



  // // dp[i][j] := i???????????§?????????????????£????????? j ??§????????§??????

  // auto dp = make_2d_vector(N + 1, W + 1, 0);

  // for(int i = 1; i <= N; i++) {

  //   for(int j = 0; j <= W; j++) {

  //     if( w[i-1] <= j )

  //       dp[i][j] = max( dp[i-1][j], dp[i-1][j - w[i-1]] + v[i-1] );

  //     else

  //       dp[i][j] = dp[i-1][j];

  //   }

  // }



  // cout << dp[N][W] << "\n";



  return 0;

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

using namespace std;



const int N = 101;

const int W = 10001;



int table[N][W];

int n, w;

int value[N];

int weight[N];



int dp(int ni, int wi)

{

    if (ni < 0) return 0;

    if (wi <= 0) return 0;

    if (table[ni][wi] != -1) return table[ni][wi];

    int t = 0;

    if (wi >= weight[ni]) {

        t = dp(ni-1, wi-weight[ni]) + value[ni];

    }

    return table[ni][wi] = max(t, max(dp(ni-1, wi), dp(ni, wi-1)));

}



int main()

{

    cin >> n >> w;

    fill(&table[0][0], &table[N-1][W], -1);

    for (int i=0; i < n; ++i) {

        cin >> value[i] >> weight[i];

    }

    cout << dp(n-1, w) << endl;

}

// Faster C++ solution for the same problem (measured speedup: 5.125821417464051x):
#include <iostream>

#include <algorithm>

using namespace std;



const int N = 101;

const int W = 10001;



int dp[N][W];

int weight[N];

int value[N];



int main()

{

    int n, w;

    cin >> n >> w;

    for (int i=0; i < n; ++i) {

        cin >> value[i] >> weight[i];

    }



    // i = ????????????????????§????????¨???

    // j = ??????????????§?????????????????§

    for (int j=0; j <= w; ++j) {

        for (int i=0; i <= n; ++i) {

            int a = (i-1 >= 0 ? dp[i-1][j] : 0);

            int b = (j-1 > 0 ? dp[i][j-1] : 0);

            int c = (i > 0 && j-weight[i-1] >= 0 ? dp[i-1][j-weight[i-1]]+value[i-1] : 0);

            dp[i][j] = max(max(a, b), c);

        }

    }



    cout << dp[n][w] << endl;



    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

using namespace std;



const int N = 101;

const int W = 10001;



int table[N][W];

int n, w;

int value[N];

int weight[N];



int dp(int ni, int wi)

{

    if (ni < 0) return 0;

    if (wi <= 0) return 0;

    if (table[ni][wi] != -1) return table[ni][wi];

    int t = 0;

    if (wi >= weight[ni]) {

        t = dp(ni-1, wi-weight[ni]) + value[ni];

    }

    return table[ni][wi] = max(t, max(dp(ni-1, wi), dp(ni, wi-1)));

}



int main()

{

    cin >> n >> w;

    fill(&table[0][0], &table[N-1][W], -1);

    for (int i=0; i < n; ++i) {

        cin >> value[i] >> weight[i];

    }

    cout << dp(n-1, w) << endl;

}

// Faster C++ solution for the same problem (measured speedup: 5.1227451257216305x):
#include <iostream>

#include <queue>

#include <vector>

using namespace std;



const int NM = 101;

const int WM = 10001;

int dp[NM][WM];

int v[NM];

int w[NM];



int main()

{

    int N, W;

    cin >> N >> W;



    for (int i=1; i <= N; ++i) {

        cin >> v[i] >> w[i];

    }



    for (int i=0; i <= W; ++i) {

        dp[0][i] = 0;

    }



    for (int i=1; i <= N; ++i) {

        for (int j=0; j <= W; ++j) {

            if (j-w[i] < 0) {

                dp[i][j] = dp[i-1][j];

            }

            else {

                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);

            }

        }

    }



    cout << dp[N][W] << endl;



    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



using ll = long long;



#define int long long



#define REP(i, n) for (int i = 0; i < (n); ++i)

#define SIZE(a) ((int)(a).size())



string brucik(int a, int b, int c, int d) {

	int n = a + b;

	pair<int,string> rs;

	rs = {n + 1, ""};

	REP(mask, 1<<n) {

		int ca, cb;

		ca = cb = 0;

		int mx = 0, last = -1, cur = 0;

		string curS;

		REP(i, n) {

			int bit = (mask >> i) & 1;

			if (bit) ++cb; else ++ca;

			if (bit) curS += 'B'; else curS += 'A';

			if (bit != last) cur = 0;

			++cur;

			last = bit;

			mx = max(mx, cur);

		}

		if (ca != a || cb != b) continue;

		pair<int,string> here = {mx, curS};

		rs = min(rs, here);

	}

	return rs.second.substr(c, d-c+1);

}



string solve(int a, int b, int c, int d) {

	int rv = 0;

	// brucik(a, b, c, d);

	if (a < b) {

		swap(a, b);

		c = a + b - c - 1;

		d = a + b - d - 1;

		swap(c, d);

		rv = 1;

	}

	string result;

	int r = (a + b) / (b + 1);

	if (r == 1) {

		for (int i = c; i <= d; ++i) {

			result += i % 2 ? 'B' : 'A';

		}

	} else {

		int x = (r*(a+1)-b-1)/(r*r-1);

		int y = ((a-r*x+1)*r - (b-x))/r;

		x *= r+1;

		y += x;

		for (int i = c; i <= d; ++i) {

			int now = i;

			if (now < x) {

				result += now % (r + 1) == r ? 'B' : 'A';

			} else 

			if (now < y) {

				result += 'A';

			} else {

				now -= y;

				now = a + b - now - 1;

				now -= y;

				result += now % (r + 1) == r ? 'A' : 'B';

			}

		}

	}

	if (rv) {

		reverse(result.begin(), result.end());

		for (auto& c : result) c = 'A' + 'B' - c;

	}

	return result;

}



main() {

	ios::sync_with_stdio(false);

	cin.tie(0);



	// cout << solve(11, 9, 0, 19) << endl;

	// cout << brucik(11, 9, 0, 19) << endl;



	// for (int a = 1; a <= 12; ++a) {

	// 	for (int b = 1; b <= 12; ++b) {

	// 		if (solve(a, b, 0, a + b - 1) != brucik(a, b, 0, a + b - 1)) {

	// 			cout << a << ' ' << b << endl;

	// 			cout << solve(a, b, 0, a + b - 1) << ' ' << brucik(a, b, 0, a + b - 1) << endl;

	// 			return 0;

	// 		}

	// 	}

	// }



	int t;

	cin >> t;

	REP(i, t) {

		int a, b, c, d;

		cin >> a >> b >> c >> d;

		--c; --d;

		cout << solve(a, b, c, d) << '\n';

	}



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.322992299769218x):
#include<cstdio>

#include<algorithm>

using namespace std;

int T,k,n,a,b,c,d;

int main() {

	scanf("%d",&T);

	while(T--) {

		scanf("%d%d%d%d",&a,&b,&c,&d);

		n=a+b;

		int l=0,r=n+1,mid,A,B;

		k=(max(a,b)-1)/(min(a,b)+1)+1;;

		while(l<r) {

			mid=(l+r)>>1;

			A=a-mid/(k+1)*k-mid%(k+1);

			B=b-mid/(k+1);

			if(B<=1ll*A*k)l=mid+1;

			else r=mid;

		}

		A=a-l/(k+1)*k-l%(k+1);

		B=b-l/(k+1);

		r=l+B-A*k+1;

		for(int i=c; i<=min(d,l); i++)putchar(i%(k+1)?'A':'B');

		for(int i=max(c,l+1); i<=d; i++)putchar((i-r)%(k+1)?'B':'A');

		puts("");

	}

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <sstream>

#include <iomanip>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cctype>

#include <cstring>

#include <vector>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <iterator>

#include <bitset>

#include <ctime>

#include <complex>



using namespace std;



#define FOR(i,a,b) for (int i = (a); i < (b); i++)

#define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)

#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)

#define FILL(a,value) memset(a, value, sizeof(a))



#define SZ(a) (int)a.size()

#define ALL(a) a.begin(), a.end()

#define PB push_back

#define MP make_pair



typedef unsigned long long LL;

typedef vector<int> VI;

typedef pair<int, int> PII;



const double PI = acos(-1.0);

const int INF = 1000 * 1000 * 1000 + 7;

const LL LINF = INF * (LL) INF;



const double EPS = 1e-6;

const int MAX = 300 + 47;



int a, b, c, d;







int main()

{

    int q;

    scanf("%d", &q);

    FOR(_, 0, q)

    {

        scanf("%d%d%d%d", &a, &b, &c, &d);

        --c, --d;

        int res = (a + b) / (min(a, b) + 1);

        int l = 0, r = a + 1;

        while(r - l > 1)

        {

            int m = (l + r) / 2;

            int x = (m - 1) / res;

            if ((a - m + 1) * 1LL * res >= b - (m-1) / res)

                l = m;

            else r = m;

        }

        string ans = "";

        FOR(i, c, d+1)

            if (i < l + (l-1)/res)

            {

                if (i % (res + 1) == res)

                    ans += 'B';

                else

                    ans += 'A';

            }

            else

            {

                if ((a + b - i - 1) % (res + 1) == res)

                    ans += 'A';

                else

                    ans += 'B';

            }

        printf("%s\n", ans.c_str());

    }

}


// Faster C++ solution for the same problem (measured speedup: 5.210670390688458x):
#include<cstdio>

#include<algorithm>

using namespace std;

int T,k,n,a,b,c,d;

int main() {

	scanf("%d",&T);

	while(T--) {

		scanf("%d%d%d%d",&a,&b,&c,&d);

		n=a+b;

		int l=0,r=n+1,mid,A,B;

		k=(max(a,b)-1)/(min(a,b)+1)+1;;

		while(l<r) {

			mid=(l+r)>>1;

			A=a-mid/(k+1)*k-mid%(k+1);

			B=b-mid/(k+1);

			if(B<=1ll*A*k)l=mid+1;

			else r=mid;

		}

		A=a-l/(k+1)*k-l%(k+1);

		B=b-l/(k+1);

		r=l+B-A*k+1;

		for(int i=c; i<=min(d,l); i++)putchar(i%(k+1)?'A':'B');

		for(int i=max(c,l+1); i<=d; i++)putchar((i-r)%(k+1)?'B':'A');

		puts("");

	}

	return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

inline int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

int m;

int main()

{

    m=read();

    while(m--)

    {

        int a=read(),b=read(),lt=read(),rt=read();

        int len=(a+b)/(min(a,b)+1);

        int l=1,r=a,mid,res=0;

        while(l<=r)

        {

            mid=l+r>>1;

            int cnt=(mid+len-1)/len;

            int lefta=a-mid,leftb=b-cnt+1-len;

            if(1LL*lefta*len<leftb) r=mid-1;

            else res=mid,l=mid+1;

        }

        int cnt=(res+len-1)/len,prelen=cnt?cnt-1+res:0;

        int lefta=a-res,leftb=b-max(0,cnt-1),first=leftb-(lefta*len);

        for(int j=lt;j<=rt;++j)

        {

            if(j<=(cnt-1)*(len+1)) putchar(j%(len+1)?'A':'B');

            else if(j<=prelen) putchar('A');

            else if(j<=prelen+first) putchar('B');

            else putchar((j-prelen-first)%(len+1)==1?'A':'B');

        }

        puts("");

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.132864379025211x):
#include<cstdio>

#include<algorithm>

using namespace std;

int T,k,n,a,b,c,d;

int main() {

	scanf("%d",&T);

	while(T--) {

		scanf("%d%d%d%d",&a,&b,&c,&d);

		n=a+b;

		int l=0,r=n+1,mid,A,B;

		k=(max(a,b)-1)/(min(a,b)+1)+1;;

		while(l<r) {

			mid=(l+r)>>1;

			A=a-mid/(k+1)*k-mid%(k+1);

			B=b-mid/(k+1);

			if(B<=1ll*A*k)l=mid+1;

			else r=mid;

		}

		A=a-l/(k+1)*k-l%(k+1);

		B=b-l/(k+1);

		r=l+B-A*k+1;

		for(int i=c; i<=min(d,l); i++)putchar(i%(k+1)?'A':'B');

		for(int i=max(c,l+1); i<=d; i++)putchar((i-r)%(k+1)?'B':'A');

		puts("");

	}

	return 0;

}