akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <atcoder/mincostflow>
#include <iostream>
#include <vector>

#define rep(i, j, n) for (int i = j; i < (n); ++i)
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  vector<string> g(n);
  rep(i, 0, n) cin >> g[i];
  int s = n * m;
  int t = n * m + 1;
  int inf = 1 << 30;
  int ans = 0;

  atcoder::mcf_graph<int, int> mcf(n * m + 2);
  int piece = 0;
  rep(i, 0, n) {
    rep(j, 0, m) {
      if (g[i][j] != '#') {
        if (j + 1 < m && g[i][j + 1] != '#')
          mcf.add_edge(i * m + j, i * m + j + 1, inf, 0);
        if (i + 1 < n && g[i + 1][j] != '#')
          mcf.add_edge(i * m + j, (i + 1) * m + j, inf, 0);
        mcf.add_edge(i * m + j, t, 1, 10000 - (i + j));
      }
      if (g[i][j] == 'o') {
        mcf.add_edge(s, i * m + j, 1, 0);
        ++piece;
        ans -= 10000 - (i + j);
      }
    }
  }
  auto res = mcf.flow(s, t, piece);
  for (auto v : mcf.edges()) {
    if (v.flow > 0 && v.to == t) ans += v.cost;
  }
  cout << -ans << endl;
  return 0;
}


Measured memory_bytes: 4092
N=int(input())
B=[]
for _ in range(N):
    B.append(input())

M=int(input())
R=[]
for _ in range(M):
    R.append(input())

from collections import Counter

ans=0
for b in B:
    ans=max(ans,Counter(B)[b]-Counter(R).get(b,0))

print(ans)


Measured memory_bytes: 39024
N = int(input())
Hs = list(map(int, input().split()))

def is_large(h_main, hs):
    if len(hs) == 0:
        return True

    for h in hs:
        if h_main < h:
            return False
    return True


ans = 0
for i, H in enumerate(Hs):
    if is_large(H, Hs[:i]):
        ans += 1
print(ans)        


Measured memory_bytes: 2940
n,*a=map(int,open(0).read().split())
b=[0]*-~n
for i in range(n,0,-1):b[i]=(sum(b[j]for j in range(i,n+1,i))+a[i-1])%2
c=[i for i in range(n+1)if b[i]]
print(len(c),*c)

Measured memory_bytes: 14076
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<string>
using namespace std; 
char ai[100005];
int bi[100005];
int main()
{
	memset(bi,0,sizeof(bi));
	int a,b; cin>>a>>b;getchar();
	for(int i=1;i<=a;i++){
		scanf("%c",&ai[i]);
	//	printf("%c\n",ai[i]);
	}
	int sum = 0;
	for(int i=1;i<a;i++){
		if(ai[i]=='A'&&ai[i+1]=='C'){
			sum++;
			bi[i] = sum - 1;
		//	bi[i+1] = sum;
		}
		bi[i+1] = sum;
	}
//	for(int i=1;i<=a;i++){
//	cout<<bi[i]<<endl;
//	}
	for(int i=0;i<b;i++){
		int q,w; cin>>q>>w;
		int su = bi[w] - bi[q];
		cout<<su<<endl;
	}
	return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
 
using namespace std;
 
int n,i,s,m,a,b,dist[2005],x,y,k[2005],cek[2005][2005];
vector <int> v[2005];
queue <int> q;
 
int main() 
{
    cin>>n>>x>>y;
    v[x].push_back(y);
    v[y].push_back(x);
    for (int i=1; i<n; i++)
    {
        v[i].push_back(i+1);
        v[i+1].push_back(i);
    }
    
    for (int s=1; s<n; s++)
    {
        for (int i=0; i<2003; i++) dist[i]=0;
        q.push(s);
        dist[s]=1;
        while (!q.empty()){
            a=q.front();
            q.pop();
            for (int i=0; i<v[a].size(); i++)
                if (dist[v[a][i]]==0) {
                    dist[v[a][i]]=dist[a]+1;
                    q.push(v[a][i]);
                }
        }
        for (int i=1; i<=n; i++)
            if (dist[i]==0 && i!=s) ; else if (!cek[s][i] && !cek[i][s]) { k[dist[i]-1]++; cek[s][i]=1; cek[i][s]=1; }
    }
    for (int i=1; i<n; i++)
        cout<<k[i]<<endl;
}


Measured memory_bytes: 16000
S = input()

pattern1 = '0'
pattern2 = '1'

even = True
pattern1 = 0
pattern2 = 0
for s in S:
    if even:
        if s == '0':
            pattern1 += 1
        else:
            pattern2 += 1
    else:
        if s == '0':
            pattern2 += 1
        else:
            pattern1 += 1
    even = not even
print(str(min(pattern1, pattern2)))


Measured memory_bytes: 3188
#include<iostream>
#include <string>
#include<stdio.h>

using namespace std;


int main() {

	int n, q, C = 0;
	long long int S[1000000] = { 0 }, T[50000] = { 0 }, check[50000] = { 0 };
	
	cin >> n;
	for (int i = 0; i < n; i++) cin >> S[i];

	cin >> q;
	for (int i = 0; i < q; i++) cin >> T[i];
	
	for (int i = 0; i < q; i++) {
		int key = T[i];
		int left = 0, right = n;

		while (left < right) {
			int mid = (right + left) / 2;

			if (S[mid] == key) {
				C++;
				break;
			}
			else if (key < S[mid]) {
				right = mid;
			}
			else {
				left = mid + 1;
			}

			if (left == right) break;
		}
		
	}

		cout << C << endl;

		return 0;
	}

	







Measured memory_bytes: 11284
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int gcd(int x, int y){
	if (y == 0) return x;
	return gcd(y, x%y);
}
int gcd1(int x, int y, int z) {
	int u = gcd(x, y);
	int v = gcd(y, z);
	return gcd(u, v);
}
int main() {
	int n;
	scanf("%d", &n);
	ll s = 0;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				s = s+gcd1(i, j, k);
			}
		}
	}
	printf("%lld\n", s);
	return 0;
}

Measured memory_bytes: 3812
#include<stdio.h>
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
    int num[3];
    int sankaku=0,eikaku=0,tyokkaku=0,donkaku=0;
    while(1){
        scanf("%d %d %d", num,num+1,num+2);
        sort(num,num+3);
        if(num[0]+num[1] <= num[2]){
            printf("%d %d %d %d\n",sankaku,tyokkaku,eikaku,donkaku);
            return 0;
        }
        sankaku+=1;
        if(num[0]*num[0] + num[1]*num[1] > num[2]*num[2]) eikaku+=1;
        if(num[0]*num[0] + num[1]*num[1] == num[2]*num[2]) tyokkaku+=1;
        if(num[0]*num[0] + num[1]*num[1] < num[2]*num[2]) donkaku+=1;
    }
}


Measured memory_bytes: 3272
#include <bits/stdc++.h>
using namespace std;
int main(){
  int d;
  cin >> d;
  if(d==25){
    cout << "Christmas" << endl;
   }
   else if(d==24){
    cout << "Christmas Eve" << endl;
   }
   else if(d==23){
    cout << "Christmas Eve Eve" << endl;
   }
    else{
    cout << "Christmas Eve Eve Eve" << endl;
   }
   return 0;
  
}


Measured memory_bytes: 3640
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce



sys.setrecursionlimit(2147483647)
INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
s = S()
l = 0
r = 0
for i in s:
    if i == ')':
        if l:
            l -= 1
        else:
            r += 1
    else:
        l += 1



print('(' * r + s + ')' * l)



Measured memory_bytes: 39664
#include<bits/stdc++.h>
using namespace std;

int n,a,b,k;

int main()
{
    scanf("%d%d%d",&n,&a,&b);
    for(int i=1;i<=n;i++)
    {
        int x=0,d=i;
        for(int j=1;;j++)
        {
            x+=d%10;
            d/=10;
            if(d==0)
            {
                break;
            }
        }
        if(x>=a&&x<=b)
        {
            k+=i;
        }
    } 
    printf("%d\n",k);
}

Measured memory_bytes: 256
fn compute_dp(n: u32, val: &Vec<u32>, wgt: &Vec<u32>) -> Vec<Vec<u32>> {
    let max_l = 100000;
    let max_dp_n = (1 << 10) - 1;
    let dp_n = std::cmp::min(n, max_dp_n) as usize;

    let dp0 = (0..=max_l)
                  .map(|i| if i < wgt[0] { 0 }
                                    else { val[0] }).collect();
    let mut vec: Vec<Vec<u32>> = Vec::new();
    vec.push(dp0);

    (1..dp_n).for_each(|u| {
        let p = (u - 1) / 2;
        let dpu = (0..=max_l)
                  .map(|i| { let ii = i as usize;
                             if i < wgt[u] { vec[p][ii] }
                             else { let jj = (i - wgt[u]) as usize;
                                    std::cmp::max(vec[p][ii],
                                                  vec[p][jj] + val[u]) }
                      }).collect();
        vec.push(dpu) });
    vec
}

fn solve(u: u32, l: u32, dp: &Vec<Vec<u32>>, val: &Vec<u32>, wgt: &Vec<u32>)
   -> u32
{
    let uu = u as usize;
    let ll = l as usize;
    if uu < dp.len() {
        dp[uu][ll]
    } else {
        let p  = (u - 1) / 2;
        let s = solve(p, l, &dp, &val, &wgt);
        if l >= wgt[uu] {
            std::cmp::max(s, val[uu] + solve(p, l - wgt[uu], &dp, &val, &wgt))
        } else {
            s
        }
    }
}


/// Read functions
/// https://qiita.com/penguinshunya/items/cd96803b74635aebefd6

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}


fn main() {
    let n: u32 = read();
    let val_wgt: Vec<Vec<u32>> = read_vec2(n);

    let mut val: Vec<u32> = Vec::new();
    let mut wgt: Vec<u32> = Vec::new();
    val_wgt.into_iter().for_each(|vw| { val.push(vw[0]); wgt.push(vw[1]) });

    let dp = compute_dp(n, &val, &wgt);

    let q: u32 = read();
    let query: Vec<Vec<u32>> = read_vec2(q);

    query.into_iter().for_each(|ul| {
        let u = ul[0];
        let l = ul[1];
        println!("{}", solve(u - 1, l, &dp, &val, &wgt))
        });
}


Measured memory_bytes: 409248
#include<bits/stdc++.h>
using namespace std;

char M(char a,char b){
    if(a=='T'&&b=='T')
        return 'T';
    if(a=='T'&&b=='F')
        return 'F';
    if(a=='F'&&b=='T')
        return 'T';
    if (a == 'F' && b == 'F')
        return 'T';
}

int main(){
    int N;
    cin >> N;
    vector<char> P(N);
    for (int i = 0; i < N;i++)
        cin >> P[i];
    char res = P[0];
    for(int i=1;i<N;i++){
        res = M(res, P[i]);
    }
    cout << res << endl;
}


Measured memory_bytes: 3188
char_list = "abcdefghijklmnopqrstuvwxyz"
char_count = {}
for c in char_list:
    char_count[c] = 0
s = ""
while True:
    try:
        s += input().lower()
    except EOFError:
        break
for c in s:
    if c in char_count:
        char_count[c] += 1
for char, count in char_count.items():
    print("{} : {:d}".format(char, count))



Measured memory_bytes: 5568
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>   
using namespace std;
using namespace __gnu_pbds;
typedef long long ll; 
#define int long long
typedef unsigned long long lu;
typedef vector<ll> v;
typedef vector<vector<ll> > vv;
typedef vector<string>  vs;
typedef vector<pair<ll,ll>> vpr;
typedef vector<bool>vb;
typedef vector<double>vd;
typedef long double ld;
#define f(i,n) for(ll i = 0; i < n; i++)
#define ff(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define endl "\n"
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define amax(x,y) if(y>x) x=y;
#define amin(x,y) if(y<x)x=y;
#define bg(x) x.begin()
#define sz(x) (ll)x.size()
#define in(x,n) for(ll i=0;i<n;i++)cin>>x[i]
#define out(x,n) for(ll i=0;i<n;i++)cout<<x[i]<<" " 
#define mxt(a) *(max_element(a.begin(),a.end()))
#define mnt(a) *(min_element(a.begin(),a.end())
#define tc ll t;cin>>t;while(t--)
typedef pair<ll,ll> pi;
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
#define yesno(f) if(f) yes else no
const v dx = {1, -1, 0, 0};
const v dy = {0, 0, 1, -1};
const ld PI = 2 * acos(0.0);
ll cel(ll x1,ll y1){if((x1%y1)==0)return x1/y1;else return x1/y1+1;}
ll power(ll a,ll b,ll m)
{
    if(b==0)
        return 1;
    ll d=power(a,b/2,m);
    d=(d*d)%m;
    if(b&1)
        d=(d*a)%m;
    return d;
}
const ll mod=1e9+7;
int MOD(int a)
{
    if(a<0)
        a+=mod;
    if(a>=mod)
        a%=mod;
    return a;
}
// set_name.find_by_order(k) It returns to an iterator to the kth element (counting from zero) in the set in O(logn) time
// set_name.order_of_key(k) It returns to the number of items that are strictly smaller than our item k in O(logn) time.
/*string operations :
str.substr (x,y) : returns a substring str[x],str[x+1],...str[x+y-1]
str.substr (x) : returns a substring str[x],... end of string
str.find(qtr) : returns the first occurenece of qtr in str */
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int n,k;cin>>n>>k;
    v a(n);in(a,n);
    int l=1,f=*max_element(all(a));
    int ans;
    while(l<=f)
    {
    	int mid=(l+f)/2;
    	int op=0;
    	for(int i=0;i<n;i++)
    	{
    		op+=cel(a[i],mid)-1;

    	}
    	if(op<=k)
    	{
    		ans=mid;
    		f=mid-1;
    	}
    	else
    		l=mid+1;
    }
    cout<<ans<<endl;

    return 0;

}

Measured memory_bytes: 4740
#include <cstdio>
#include <algorithm>
 

int n, m;
int x[100000];
int dd[100000];
int max = 0;
int maxj = 0;
int sum = 0;
int d = 0;
 
void quickSort(int numbers[], int array_size) {
  std::sort(numbers, numbers + array_size);
}

void solve() {
  if (n < m) {
    for (int i = 0; i < m - 1; i++) {
      dd[i] = x[i+1] - x[i];
    }
  }
  quickSort(dd, m - 1);
  for (int i = 0; i < m - n; i++) {
    d += dd[i];
  }
}
 
int main() {
  scanf("%d", &n);
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    scanf("%d", &x[i]);
  }
  quickSort(x, m);
  solve();
  printf("%d\n", d);
 
  return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  int sum =0;
  for (int i = 0;i<n;i++){
    int a,b;
    cin >> a >> b;
    sum += b - a + 1;
  }
  cout << sum <<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i],a[i]--;
  vector<int> idx(n);
  rep(i,n) idx[a[i]] = i; //各数字の位置を記録
  set<int> s;
  ll ans = 0;
  for(int x = n-1; x >= 0; x--){
    int i = idx[x]; //xの位置を取得
    ll c = 0;
    
    s.insert(i); //setにxの位置を入れる
    vector<int> l(2,-1),r(2,n);
    
    auto it = s.find(i);
    rep(j,2){
      if(it == s.begin()) break;
      it--;
      l[j] = *it;
    }
    
    it = s.find(i);
    rep(j,2){
      it++;
      if(it == s.end()) break;
      r[j] = *it;
    }
    vector<int> ls(2),rs(2);
    ls[0] = i-l[0]; ls[1] = l[0]-l[1];
    rs[0] = r[0]-i; rs[1] = r[1]-r[0];
    c = (ll)ls[0]*rs[1]+(ll)ls[1]*rs[0];
    
    ans += c*(x+1);
  }
  
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); ++i)
#define rep0(i,n) for (int i=0; i<=(int)(n); ++i)
#define rep1(i,n) for (int i=1; i<=(int)(n); ++i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using Graph = vector<vi>;  // vi <=> vl
using vb = vector<bool>;
using boolGraph = vector<vb>;
using P = pair<int, int>;  // int <=> ll
const int MOD = 1e9+7;
const int MOD2 = 998244353;
const double EPS = 1e-9;

template<typename T>
struct is_vector : false_type{};

template<typename T>
struct is_vector<vector<T>> : true_type{};

template<typename T>
ostream &operator << (ostream &ostr, const vector<T> &vec) {
  if (vec.empty()) {
    return ostr;
  }
  ostr << vec.front();
  for (auto itr = ++vec.begin(); itr != vec.end(); ++itr) {
    if (is_vector<T>()) ostr << "\n" << *itr;
    else ostr << ' ' << *itr;
  }
  return ostr;
}

template<typename T>
bool CompareBySecond(pair<T, T> a, pair<T, T> b) {
  if (a.second != b.second) {
    return a.second < b.second;
  } else {
    return a.first < b.first;
  }
}

void solve() {
  ll n; cin >> n;
  vl arr(5);
  rep(i,5) cin >> arr[i];
  ll MIN = *min_element(ALL(arr));
  ll ans = 5 + (n-1) / MIN;
  cout << ans << endl;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>

#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const double EPS=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
int D,x,y;
vector<int> d1;
vector<int> d2;

int f(int a,int b){
	int sum = 0;
	for(int i = 0;i < a;i++){
		sum += d1[d1.size() - 1 - i];
	}
	for(int j = 0;j < b;j++){
		sum += d2[d2.size() - 1 - j];
	}
	return sum;
}

int main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(0);
	cin>>D;
	cin>>x;

	for(int i = 0;i < x;i++){
		char c;
		int z;
		cin>>c>>z;
		if(c != 'D')continue;
		d1.push_back(z);
	}
	sort(d1.begin(),d1.end());
	cin>>y;
	for(int i = 0;i < y;i++){
		string c;
		cin>>c;
		int z;
		cin>>z;
		if(c != "DD")continue;
		d2.push_back(z);
	}
	sort(d2.begin(),d2.end());
	int x = d1.size();
	int y = d2.size();
	int ans = 0;
	for(int i = 0;i <= x;i++){
		for(int j = 0;j <= y;j++){
			if(i + j*2 > D)break;
			ans = max(ans,f(i,j));
		}
	}
	cout <<ans<<endl;
	return 0;
}

Measured memory_bytes: 1244
#include<iostream>

using namespace std;

const int MAX = 1000001;
bool data[MAX];
int n,a,b;

void solve(){
  data[a] = data[b] = true;

  for(int i = 1; i < MAX; i++){
    if(i-a>0) data[i] = (data[i] || data[i-a]);
    if(i-b>0) data[i] = (data[i] || data[i-b]);
  }

  int ans = 0;
  for(int i = 1; i <= n; i++)
    if(!data[i]) ans++;

  cout << ans << endl;
}

int main(){
  while(cin >> n >> a >> b && n+a+b){
    fill(data,data+MAX,false);
    solve();
  }
  return 0;
}

Measured memory_bytes: 2136
#include <bits/stdc++.h>
using namespace std;

int main () {
  char c;
  cin >> c;
  if ((c == 'a')||(c == 'i')||(c == 'u')||(c == 'e')||(c == 'o')) {
    cout << "vowel" << endl;
  }
  else {
    cout << "consonant" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef long long int lli;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

const int n = 26;
const int INF = 10000005;

int main(){
    int days;
    cin >> days;

    // 満足度が下がる値
    vector<int> bad(n);
    rep(i, n) cin >> bad[i];

    // そのコンテストをその日に開いた時の満足度
    vector<vector<int>> score(days+1, vector<int>(n));
    for(int d = 1; d <= days; d++){
        rep(i, n) cin >> score[d][i];
    }

    // 最後にそのコンテストが開かれたのが何日前か
    vector<vector<int>> preD(days+1, vector<int>(n, 0));

    // 日付毎で満足度が最大になるコンテストを開く
    vector<int> sats(days+1, 0), cons(days+1, 0);
    for(int d = 1; d <= days; d++){
        int maxSat = -INF, maxCon = 0;

        // d日のi番目のコンテストを開いたときの満足度を計算し、最大になるコンテストと満足度を記録する
        rep(i,n){
            int conSat = score[d][i] + sats[d-1];
            vector<int> copyPreD = preD[d-1];
            rep(j,n){
                if (i == j) continue;
                copyPreD[j]++;
                conSat -= bad[j] * copyPreD[j];
            }
            if (chmax(maxSat, conSat)){
                maxCon = i;
            }
        }

        // 最も良いスコアとコンテストを更新
        sats[d] = maxSat;
        cons[d] = maxCon+1;

        // 開いたコンテストの最終日を更新
        rep(i,n){
            if (i == maxCon) preD[d][i] = 0;
            else preD[d][i] = preD[d-1][i] + 1;
        }
    }
    
    for(int d = 1; d <= days; d++){
        cout << cons[d] << endl;
    }
}

Measured memory_bytes: 3720
#include <bits/stdc++.h>
using namespace std;

int main() {
  int h, w;
  cin >> h >> w;
  vector<vector<string>> data(h, vector<string>(w));
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cin >> data.at(i).at(j);
    }
  }
  int a, b;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (data.at(i).at(j) == "snuke") {
        a = i;
        b = j;
      }
    }
  }
  char c = b + 1 + 64;
  cout << c << a + 1 << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)

int main(){
    string s; cin >> s;
    int n = s.size();
    int beg,end;
    for(int i = 0; i < n; i++){
        if(s[i] == 'A'){
            beg = i;
            break;
        }
    }
    for(int i = n-1; i >= 0; i--){
        if(s[i] == 'Z'){
            end = i;
            break;
        }
    }
    cout << end - beg + 1 << endl;
}


Measured memory_bytes: 640
import sys
for i in range(sys.maxsize):
    h,w=map(int,input().split())
    if h==0 and w==0:
        break
    else:
        for j in range(h):
            l=[]
            for k in range(w):
                if (j % 2 == 0 and k % 2 == 0) or (j % 2 == 1 and k % 2 == 1):
                    l.append("#")
                else:
                    l.append(".")
            print("".join(l))
    print("")


Measured memory_bytes: 5620
#include <bits/stdc++.h>

using namespace std;
typedef uint64_t u64;
typedef int64_t i64;
typedef double db;

int main() {
  u64 K, N;
  vector<u64> A;
  cin >> K >> N;
  A.resize(N);
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
  }

  // calc
  u64 v = K;
  for (int i = 0; i < N; i++) {
    int j = (i + 1) % N;
    v = min(v, K - (A[j] + K - A[i]) % K);
  }
  cout << v << endl;
  return 0;
}


Measured memory_bytes: 4824
(defun split (string)
  (loop :for char :across string 
      :collect char)) 

(defun check_echo (list1 list2)
  (cond 
    ((null list1) "Yes")
    ((equal (car list1) (car list2)) (check_echo (cdr list1) (cdr list2)))
    (T "No")))


(let ((n (read))
      (str (split (read-line))))
     (if (evenp (mod n 2))
         (princ (check_echo  (nthcdr (/ n 2) str) str))
         (princ "No")))

Measured memory_bytes: 4456
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main(){
	char *s;
	unsigned long int i,j,n;
	s=malloc(sizeof(char)*100000);
	scanf("%s",s);
	n=strlen(s);
	for(i=j=0;i<n;i++){
		if(s[i]=='0' && i%2==0)j++;
		if(s[i]=='1' && i%2==1)j++;
	}
	printf("%d",(int)(j<n-j?j:n-j));
	free(s);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using Vbo = vector<bool>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using VVbo = vector<Vbo>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
#define rep2(i, m, n) for(ll i=int(m); i<int(n); ++i)
#define drep2(i, m, n) for(ll i=int(m)-1; i>=int(n); --i)
#define rep(i, n) rep2(i, 0, n)
#define drep(i, n) drep2(i, n, 0)
#define all(a) a.begin(), a.end()
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << " "; return os; }
template<typename T> inline int count_between(vector<T> &a, T l, T r) { return lower_bound(all(a), r) - lower_bound(all(a), l); } // [l, r)
inline int Log2(ll x) { int k; for (k = 0; x > 0; ++k) x >>= 1; return k; } // number of binary digits
const int INF  = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS   = 1e-10;
const ld PI    = acos(-1.0);
const int MOD  = int(1e9)+7;


map<ll, ll> memo;
map<ll, bool> done;

ll n, a, b, c, d;

ll dp(ll x) {
  if (done[x]) return memo[x];
  if (x == 0) return 0;
  if (x == 1) return d;

  ll res = INFll;
  if (ld(res)/d + 1 >= x) res = d*x;
  chmin(res, dp(x/2) + (x%2)*d + a);
  chmin(res, dp(x/3) + (x%3)*d + b);
  chmin(res, dp(x/5) + (x%5)*d + c);
  chmin(res, dp((x+1)/2) + (2-x%2)*d + a);
  chmin(res, dp((x+2)/3) + (3-x%3)*d + b);
  chmin(res, dp((x+4)/5) + (5-x%5)*d + c);

  done[x] = true;
  memo[x] = res;
  return res;
}


int main() {
  int t; cin >> t;
  rep(_, t) {
    done.clear();
    memo.clear();
    cin >> n >> a >> b >> c >> d;
    cout << dp(n) << "\n";
  }
  return 0;
}


Measured memory_bytes: 5208
#include <iostream>
#include<iomanip>
#include <numeric>
#include <string>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <cmath>

#define repd(i,a,b); for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define ll long long int
 
 
using namespace std;
int main() {
 string s;
  cin >> s;
  int z = (int)(s.length());
  int i=0,ans=0,k;
  rep(j,z){
    i=j;
    while(s[i] == 'A' || s[i] == 'T' || s[i] == 'G' || s[i] == 'C') {
      i++;
    }
    ans = max(ans,i-j);
  }
    
  cout << ans;
 return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cmath>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
const double PI=3.1415926535897932;
using namespace std;
typedef long long ll;

vector <ll>ans(10001);
ll c;
ll q(ll n){
    for(int i=1;i<=sqrt(n);i++){
        for(int j=i;j<=sqrt(n);j++){
            for(int k=j;k<=sqrt(n);k++){
                ll a=i*i+k*k+j*j+i*j+k*j+i*k;
                if(a<=10000){
                    //cout<<i<<" "<<j<<" "<<k<<endl;
                    if(i==j&&j==k)ans[a-1]+=1;
                    else if(i!=j&&j!=k&&k!=i)ans[a-1]+=6;
                    else ans[a-1]+=3;
                }
            }
        }
    }
    cout<<c<<endl;
    return 0;
}
int main(void){
    ll n;
    cin>>n;
    q(n);
    for(int x=1;x<n;x++){
        cout<<ans[x]<<endl;
    }
    
}

Measured memory_bytes: 3712
#include<bits/stdc++.h>
#define MAIN 200010
using namespace std;
int main()
{
    int n,k;
    while(cin>>n>>k)
    {
        map <int,int> mps;
        for(int i=1; i<=n; i++)
        {
            int tmp;
            cin>>tmp;
            mps[tmp]++;
        }
        vector <int> vec;
        for(auto ret : mps)
            vec.push_back(ret.second);
        sort(vec.begin(),vec.end());
        int ans=0,num=mps.size();
        if(num<=k)
        {
            cout<<"0"<<endl;
            continue ;
        }
        for(int i=0; i<num-k; i++)
                ans+=vec[i];
        cout<<ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 10748
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define ll long long
inline ll read()
{
	ll x=0,w=0;char ch=getchar();
	while(!isdigit(ch))w|=ch=='-',ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return w?-x:x;
}
int n;
char s[1000],t[1000];
int main()
{
////////////////////////b
    n=read();scanf("%s",s+1);scanf("%s",t+1);
    for(reg int i=1;i<=n;++i)cout<<s[i]<<t[i];
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
using namespace std;
int main(void){
    int n,l,m,x=0,ans=0;
    cin>>n>>l;
    int a[n];
    int aa[n];
    m=l*1;
    for(int i=1;i<=n;i++){
        a[i-1]=l;
        aa[i-1]=l*i;
        l++;
        if(abs(m)>aa[i-1]){
            m=aa[i-1];
            x=i-1;
        }
        ans=ans+a[i-1];
    }
    cout << ans-a[x] <<endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<map>
#include<algorithm>
#include<string>
using namespace std;
int a[1000005],n,n1,a1[1000005],su[1000005],tot,ct;
bool f1[1000005];
map<int,int>mp,m1;
inline void prime()
{
	f1[0]=f1[1]=1;
	for(int i=2;i<=1000000;i++)
	{
		if(!f1[i])
			su[++ct]=i;
		for(int j=1;j<=ct&&su[j]*i<=1000000;j++)
			f1[su[j]*i]=1;
	}
}
inline void X(int x)
{
	n1++;
	bool ff=0;
	for(int j=1;j<=ct&&su[j]<=x;j++)
	{
		int i=su[j];
		if(x%i==0)
		{
			ff=1;
			if(mp[i]+1!=n1)
				continue;
			mp[i]++;
			int cnt=0;
			while(x%i==0)
				x/=i,cnt++;
			if(m1[i]==0)
			{
				m1[i]=cnt;
				a1[++tot]=i;
			}
			m1[i]=min(m1[i],cnt);
		}
	}
	if(x>1&&mp[x]+1==n1)
	{
		mp[x]++;
		if(m1[x]==0)
			a1[++tot]=x;
		m1[x]=1;
	}
}
inline int pow(int x,int y)
{
	int ret=1;
	while(y)
	{
		if(y%2==1)
			ret*=x;
		x*=x;
		y/=2;
	}
	return ret;
}

int main()
{
	prime();
	scanf("%d%d",&n,&a[0]);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a,a+n+1);
	for(int i=0;i<n;i++)
		if(a[i+1]!=a[i])
		{
			if(a[i+1]-a[i]==1)
			{
				printf("1");
				return 0;
			}	
			X(a[i+1]-a[i]);
		}
	int ans=1;
	for(int i=1;i<=tot;i++)
		if(mp[a1[i]]==n1)
			ans*=pow(a1[i],m1[a1[i]]);
	printf("%d",ans);
}

Measured memory_bytes: 5632
#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
#define POWER9 1000000000
#define MOD POWER9+7
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483647
#define INT_MAX 2147483647
#define LL_MIN (LL)-9223372036854775807
#define LL_MAX (LL)9223372036854775807
#define PI 3.14159265359

int main(){
	cin.tie(0);
	
	int N,M;
	cin >> N >> M;
	bool pos[100000] = {};
	int c[100000];
	for(int i=0; i<N; i++) c[i] = 1;
	pos[0] = true;
	for(int i=0; i<M; i++){
		int x,y;
		cin >> x >> y;
		x--; y--;
		if(pos[x]) pos[y] = true;
		c[x]--; c[y]++;
		if(c[x] == 0) pos[x] = false;
	}
	int ans = 0;
	for(int i=0; i<N; i++){
		if(pos[i]) ans++;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 768
object Main extends App {
  import scala.io.StdIn._
  val n = readLine.trim.toInt
  for (_ ← 0 until n){
    val nums = readLine.trim.split(' ').map(_.toInt).toList
    println(
      if (canMake(nums)) "YES"
      else "NO"
    )
  }
  def canMake(num: List[Int], left: Int = 0, right: Int = 0): Boolean = {
    num match{
      case Nil ⇒ true
      case h::t if h > left && h > right ⇒ canMake(t, h, right) || canMake(t, left, h)
      case h::t if h > left ⇒ canMake(t, h, right)
      case h::t if h > right ⇒ canMake(t, left, h)
      case _ ⇒ false
    }
  }
}


Measured memory_bytes: 43944
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long ll;
int main() {
  int n, k,d=2;
  scanf("%d %d", &n, &k);
  vector<int> v;
  while(true){
    if(d<k){
      v.push_back(k/d+(k%d?1:0));
    }else{
      v.push_back(1);  
      break;
    }
    d*=2;
  }
  int s=v.size(),t=min(n+1,k);
  ll dk=max(0,n-k+1)*pow(2,s),dn=n*pow(2,s);
  rep(i,s){
    if(v[i]>n)continue;
    dk+=(t-v[i])*pow(2,s-i-1);
    t=v[i];
  }
  printf("%.12f",(double)dk/(double)dn);
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<complex>
#include<string>
#include<cstring>
using namespace std;
#define rep2(x,from,to) for(long long x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
#define INF 100000000
#define debug(x) cout<<#x<<": "<<x<<endl

#define all(x) x.begin(),x.end()
typedef pair<long long,long long> P;
typedef pair<long long,P> PP;
long long n;
long long ans;
long long a[100006];
int main()
{
	cin>>n;
	rep(i,n)
	{
		cin>>a[i];
	}
	rep(i,n)
	{
		ans+=(long long)(a[i]/2);
		if(a[i]%2==1&&a[i+1]!=0)
		{
			ans++;
			a[i+1]--;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main()
{
  ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  int N=0,m=0;
  cin>>N;
  m=N%1000;
  if(m==0)
    cout<<m<<endl;
  else
    cout<<1000-m<<endl;   
  return 0;
}

Measured memory_bytes: 3192
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E17;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
///////////////////////////////////////


int main(){fastio
    ll n;cin>>n;
    ll a[n];rep(i,0,n-1)cin>>a[i];
    ll b[n];rep(i,0,n-1)cin>>b[i];
    ll c[n-1];rep(i,0,n-2)cin>>c[i];
    ll ans=0;
    rep(i,0,n-1)ans+=b[i];
    rep(i,0,n-2){
        if(a[i]+1==a[i+1]){
            ans+=c[a[i]-1];
        }
    }
    
    cout<<ans<<endl;
    return 0;
}

/*

#define N 200005
ll n;
ll a[N];

ll ret[N][2];
void cal(){
    set<l_l>s;
    memset(ret,-1,sizeof(ret));
    rep(i,0,n-1){
        while(!s.empty()){
            l_l t=*s.begin();
            if(t.first<a[i]){
                ret[t.second][0]=i;
                s.erase(t);
            }
        }
        s.insert(l_l(a[i],i));
    }
    rep(i,0,n-1){
        
    }
}

int main(){fastio
    
    cin>>n;
    rep(i,0,n-1)cin>>a[i];
    ll dp[n][4];
    cal();
    rep(i,0,n-1)rep(j,0,1){
        dp[i][j]=ret[i][j];
    }
    reverse(a,a+n);
    cal();
    rep(i,0,n-1)rep(j,0,1){
        dp[i][j+2]=ret[i][j];
    }
    reverse(a,a+n);
    
    
    
    return 0;
}
 */













Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int s[100007];

int main(){
	int n;
	int q;
	cin >> n;
	int i;
	for(i=0;i<n;i++){
		cin >> s[i];
	}
	
	sort(s,s+n);
	int count = 0;
	cin >> q;
	for(i = 0; i<q;i++){
		int r;
		cin >> r;
		int head = 0;
		int end = n-1;
		while(head<=end){
			int mid = (head+end)/2;
			if(s[mid]>r){
				end = mid-1;
			}else if(s[mid]<r){
				head = mid+1;
			}else{
				count++;
				break;
			}
		}
	}
	cout << count <<endl;
	return 0;
} 


Measured memory_bytes: 3440
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())
#define endl "\n"

ll f(string s) {
    if (s == "Male") return 0;
    else return 1;
}

int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    ll n;
    cin >> n;
    ll low = 0, high = n;
    cout << 0 << endl;
    string s;
    cin >> s;
    if (s == "Vacant") {
        return 0;
    }
    ll fir = f(s);
    while((low + 1) < high) {
        ll mid = (low + high) / 2;
        cout << mid << endl;
        cin >> s;
        if (s == "Vacant") {
            return 0;
        }
        if (mid % 2 == 0) {
            if (f(s) != fir) {
                high = mid;
            }
            else {
                low = mid;
            }
        }
        else {
            if (f(s) != fir) {
                low = mid;
            }
            else {
                high = mid;
            }
        }
    }
    cout << low << endl;
    cin >> s;
    return 0;
}


Measured memory_bytes: 852
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const ll MOD = (ll) (1e9 + 7);
const double PI = acos(-1.0);
const int limit = 100010;

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbg2(x_) for(auto a_ : x_) cerr << a_ << " "; cerr << endl;
#define dbg3(x_ , sx_) rep(i, sx_) cerr << x_[i] << " "; cerr << endl;
vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

inline ll CEIL(ll a, ll b) {
    return (a + b - 1) / b;
}

//------------------------------------------------------

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b, t;
    cin >> a >> b >> t;
    cout << (t / a) * b << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    int Max = -1, ans = 0;

    int t;
    while(n --) {
        cin >> t;
        Max = max(Max, t);
        if(t >= Max) ans += 1;
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.*;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int Tests = sc.nextInt();
		for (int test = 0; test < Tests; test ++) {
			long a = sc.nextInt();
			long b = sc.nextInt();
			long l = sc.nextInt();
			long r = sc.nextInt();
			long len = (Math.max(a, b) - 1) / (Math.min(a, b) + 1) + 1;
			long lena, lenb;
			if (a >= len * b) {
				lena = a + b; lenb = 0;
			} else if (b >= len * a) {
				lena = 0; lenb = a + b;
			} else {
				lena = (len * a - b) / (len - 1);
				lenb = (len * b - a) / (len - 1);
			}
			boolean B = a - lena + lena / (len + 1) - lenb / (len + 1) == 0;
			for (long i = l - 1; i < r; ++ i) {
				char pc;
				if (i < lena) {
					if (i % (len + 1) == len) pc = 'B';
					else pc = 'A';
				}
				else if (i >= a + b - lenb) {
					if ((a + b - i - 1) % (len + 1) != len) pc = 'B';
					else pc = 'A';
				}
				else if (B) pc = 'B';
				else pc = 'A';
				System.out.print(pc);
			}
			System.out.println();
		}
	}
}

Measured memory_bytes: 37536
#include<iostream>
using namespace std;
static const int MAX = 120;
char M[MAX][MAX + 1];
int h, w;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
void dfs(int y, int x, char c)
{
	M[y][x] = 'a';
	for (int i = 0; i < 4; i++) {//??£??\4???????????¢?????????????????????a??§?¶?????????????
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (0 <= nx < w && nx < w && 0 <= ny && ny < h && M[ny][nx] == c) {
			dfs(ny, nx, c);
		}
	}
}


int main()
{
	while (cin >> h >> w, !(w==0 && h==0)) {
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> M[i][j];
			}
		}
		int counter = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (M[i][j] == '#' || M[i][j] == '*' || M[i][j] == '@') {
					char c = M[i][j];
					dfs(i, j, c);
					counter++;
				}
			}
		}
		cout << counter << endl;
	}

	
    return 0;
}

Measured memory_bytes: 3552
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(ll i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long int ll;
typedef pair<ll,ll> Pi;
typedef tuple<ll,ll,ll> Tu;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const double PI=3.14151926535;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
const ll tMOD=(ll)998244353;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int mdx[8]={0,1,0,-1,1,1,-1,-1},mdy[8]={-1,0,1,0,1,-1,1,-1};


template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int n;
string s;
int q;
set<int> st[30];
int main(){
    cin>>n;
    cin>>s;
    cin>>q;
    REP(i,s.size()){
        st[s[i]-'a'].insert(i);
    }
    REP(i,q){
        int x;
        cin>>x;
        if(x==1){
            int y;
            char z;
            cin>>y>>z;
            y--;
            st[s[y]-'a'].erase(y);
            s[y]=z;
            st[z-'a'].insert(y);
        }else{
            int y,z;
            cin>>y>>z;
            y--,z--;
            int ans=0;
            REP(i,26){
                auto itr=st[i].lower_bound(y);
                if(itr!=st[i].end()){
                    if(*itr<=z)ans++;
                }
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 24196
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include<string>

#define all(c) (c).begin(),(c).end()

using namespace std;

int now;
string s;

int number(){
  int res=0;
  while('0'<=s[now] && s[now]<='9'){
    res*=10;
    res+=s[now]-'0';
    now++;
  }
  return res;
}

int factor(){

  if(s[now]=='['){
    vector<int>v;
    while(s[now]=='['){
      now++;
      v.push_back(factor());
      now++;
    }
    sort(all(v));
    if(v.size()<2)return v[0];
    int sum=0;
    for(int i=0;i<v.size()/2+1;i++){
      sum+=v[i];
    }
    return sum;
  }
  else if('0'<=s[now] && s[now]<='9'){
    int res=number()/2+1;
    
    return res;
  }
}

int main(void){

  int tc;
  cin >> tc;

  cin.ignore();

  while(tc--){
    now=0;
    getline(cin,s);
    cout << factor() << endl;
  }
  return 0;
}

Measured memory_bytes: 1276
#include <bits/stdc++.h>

using namespace std;

int del (int n){
    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(n % i == 0){
            ans++;
        }
    }
    return ans;
}

int n , ans , cnt;
vector < int > v;

int main(){
cin >> n;
for(int i = 1; i <= n; i++){
    int x = del(i);
    if(i % 2 != 0){
        if(x == 8){
            cnt++;
        }
    }
}
cout << cnt;
return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#define rep(i,n) for (int i=0; i<n;++i)
#define rep_down(i,n) for (int i=n-1; i>=0;--i)
#define ALL(a)  (a).begin(),(a).end()
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;
const int INF = 1000000007;
int N, M;
ll A[100002];
priority_queue<ll> que;

int main() {
  cin.sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  cin >> N >> M;
  ll a;
  rep(i, N){
    cin >> a;
    que.push(a);
  }

  rep(i, M) {
    ll q = que.top();
    que.pop();
    que.push(q/2);
  }
  ll sm = 0;
  rep(i, N){
    ll q = que.top();
    que.pop();
    sm += q;
  }


  cout << sm << "\n";
  return 0;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    string s;
    cin>>s;
    ll n = s.size();
    vector<int> a(3);
    for(int i=0; i<n; i++) {
        if(s[i] == 'a') a[0]++;
        if(s[i] == 'b') a[1]++;
        if(s[i] == 'c') a[2]++;
    }
    if(abs(a[0]-a[1]) < 2 && abs(a[1]-a[2]) < 2 && abs(a[2]-a[0]) < 2) {
        cout<<"YES"<<"\n";
    }
    else cout<<"NO"<<"\n";
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <string>

int main() {
  size_t H, W;
  std::cin >> H >> W;

  std::vector<std::string> S(H);
  for (auto& si: S) std::cin >> si;

  for (size_t i = 0; i < H; ++i)
    for (size_t j = 0; j < W; ++j) {
      if (S[i][j] == '#') continue;
      S[i][j] = '0';
      for (size_t di: {-1, 0, 1})
        for (size_t dj: {-1, 0, 1}) {
          size_t ni = i+di;
          size_t nj = j+dj;
          if (!(ni < H && nj < W)) continue;
          if (S[i+di][j+dj] == '#')
            ++S[i][j];
        }
    }

  for (const auto& si: S)
    std::cout << si << std::endl;
}

Measured memory_bytes: 256
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(12);

    int n;
    long long K;
    cin >> n >> K;
    map<int, long long> cnts;
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        cnts[a] += b;
    }

    int res = -1;
    for (auto& p : cnts) {
        if (K <= p.second) {
            res = p.first;
            break;
        } else {
            K -= p.second;
        }
    }

    cout << res << '\n';


    return 0;
}

Measured memory_bytes: 7568
#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0; i<n ; ++i)
#define REP(i,a,b) for(int i=a; i<b; ++i)
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

//プロトタイプ宣言
void faster(void);
ll gcd(auto , auto);
ll get_digent(auto);
ll POW(auto , auto);
ll vec_max(auto & , string);
ll vec_min(auto & , string);

int main(){
  ll a,b;
  cin >> a >> b;
  ll g = gcd(a,b);
  ll temp1 = a/g;
  ll temp2 = b/g;
  ll lcm = temp1*temp2*g;
  cout << lcm << endl;
}


























//以下、ライブラリ

//同期解除
void faster(void){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
}

//ユークリッドの互除法
ll gcd(auto a, auto b) {
  return (b ? gcd(b, a%b) : a);
} 

//桁数取得
ll get_digent(auto x){
  string s;
  s = to_string(x);
  ll digent = s.size();
  return digent;
} 

//べき乗計算
ll POW(auto x, auto y){
  if(y==0) return 1;
  if(y%2 == 1){
    ll temp = POW(x,y-1);
    return (temp*x);
  }
  else{
    ll temp = POW(x,y/2);
    return temp*temp;
  }
} 

//配列内の最大要素の添え字取得or要素取得
ll vec_max(auto &v, string s){
  auto itr = max_element(v.begin(),v.end());
  ll element = *itr;
  ll place = itr - v.begin();
  if(s == "element") return element;
  else if(s == "place") return place;
  else return -1;
}

//配列内の最小要素の添え字取得or要素取得
ll vec_min(auto &v, string s){
  auto itr = min_element(v.begin(),v.end());
  ll element = *itr;
  ll place = itr - v.begin();
  if(s == "element") return element;
  else if(s == "place") return place;
  else return -1;
}

Measured memory_bytes: 256