akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (int64_t)(n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

#define chmax(a, b) (a) = max(a, b)
#define chmin(a, b) (a) = min(a, b)

vector<bool> eratosthenes_sieve(size_t size) {
  vector<bool> is_prime(size + 1, true);
  for (size_t i = 0; i <= size; i++) {
    if (i < 2) {
      is_prime[i] = false;
    } else if (is_prime[i]) {
      for (size_t j = 2 * i; j <= size; j += i) {
        is_prime[j] = false;
      }
    }
  }
  return move(is_prime);
}

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

  constexpr int MAXFACTOR = 1'000'000;
  auto sieve = eratosthenes_sieve(MAXFACTOR);
  vector<int> primes;
  vector<int> idx(sieve.size());
  irep(i, MAXFACTOR) {
    if (sieve[i]) {
      idx[i] = primes.size();
      primes.push_back(i);
    }
  }

  vector<int> num_factor(primes.size(), 0);
  rep(i, N) {
    int a;
    cin >> a;

    for (int i = 0; i < primes.size() and primes[i] * primes[i] <= a; i++) {
      if (a % primes[i] == 0) {
        num_factor[i]++;
        while (a % primes[i] == 0) {
          a /= primes[i];
        }
      }
    }
    if (sieve[a]) {
      num_factor[idx[a]]++;
    }
  }

  int result = 0;
  for (auto &elm : num_factor) {
    chmax(result, elm);
  }

  cout << (result <= 1 ? "pairwise coprime"
                       : (result < N ? "setwise coprime" : "not coprime"))
       << endl;

  return 0;
}

Measured memory_bytes: 8068
//============================================================================
// Name        : TopCoderCompetition.cpp
// Author      : taguchi
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <bitset>
#include <algorithm>
#include <map>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <numeric>
#include <list>
#include <sstream>
using namespace std;
//#define P pair<int,int>
//#define max 999999
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
#define rep(i,n) for(ull i = 0;i<n;i++)
#define pb(n) push_back(n)
#define clear(n) memset(n,0,sizeof(n))

typedef vector<int> vi;
typedef vector<string> vs;
struct edge{int cost,to;};

vector<string> split(string &in,char delimiter){
	vector<string> re; uint cur = 0,next;
	while((next = in.find_first_of(delimiter,cur)) != string::npos){
		re.pb(string(in,cur,next-cur));
		cur = next + 1;
	}
	re.pb(string(in,cur,in.size()-cur));
	return re;
}
vector<int> split_int(string &in, char delimiter){
	vector<string> str = split(in,delimiter);
	vector<int> re;
	rep(i,str.size()){
		re.pb(strtol(str[i].c_str(),NULL,10));
	}
	return re;
}

class Range{
public:
	int a,b;
	Range(int an,int bn) : a(an),b(bn){}

	bool operator()(int n){
		return a<=n&&n<=b;
	}
	bool isCross(Range x){
		return x(a) || x(b);
	}
	bool contains(Range x){
		return this->a <= x.a && x.b <= this->b;
	}
};

vector<int> nums;
ull dp[110][25];
ull dfs(int n, int sum){
	ull result = 0;
	if(sum < 0 || sum > 20) return 0;
	if(dp[n][sum] != -1) return dp[n][sum];
	if(n == nums.size() - 1) {
		if(nums[n] == sum) return 1;
		else return 0;
	}
	result = dfs(n+1,sum + nums[n]) + dfs(n+1,sum - nums[n]);
	return dp[n][sum] = result;
}
int main(){
	int N;
	rep(i,110)rep(j,25){
		dp[i][j] = -1;
	}
	cin >> N;
	rep(i,N){
		int a;
		cin >> a;
		nums.pb(a);
	}
	cout << dfs(1,nums[0]) << endl;
	return 0;
}

Measured memory_bytes: 0
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 3e3 + 5;
const double eps = 1e-9;
int c[MAXN], vis[MAXN][MAXN][2];
ll dp[MAXN][MAXN][2];

void solve(int a, int b, int x) {
    if (vis[a][b][x]) return;
    if (a == b) {
        if (x)
            dp[a][b][x] = -c[a];
        else
            dp[a][b][x] = c[a];
        vis[a][b][x] = 1;
        return;
    }
    if (a < b) {
        solve(a, b - 1, x ^ 1);
        solve(a + 1, b, x ^ 1);
        if (x)
            dp[a][b][x] = min(dp[a][b - 1][x ^ 1] - c[b], dp[a + 1][b][x ^ 1] - c[a]);
        else
            dp[a][b][x] = max(dp[a][b - 1][x ^ 1] + c[b], dp[a + 1][b][x ^ 1] + c[a]);
    }
    vis[a][b][x] = 1;
}

int main()
{
    int n;
    ni(n);
    nai(c, n);
    solve(0, n - 1, 0);
    prl(dp[0][n - 1][0]);
    return 0;
}


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

int main(){
  int N,M;
  cin >> N >> M;
  vector<pair<int,int>> a(N);
  for(int i=0;i<N;i++){
    cin >> a.at(i).first >> a.at(i).second;
  }
  
  sort(a.begin(),a.end());
  
  long long yen =0;
  int cnt =0;
  
  for(int i=0;i<N;i++){
    int buy = min(M, a[i].second);
 
		yen += (long long)buy * a[i].first;
 
		M -= buy;
  }
  
  cout << yen << endl;
  /*
  for(int i=0;i<N;i++){
    if(cnt < M && cnt+a.at(i).second < M){
	  yen += a.at(i).first * a.at(i).second;
      cnt += a.at(i).second;
    }else if(cnt < M && cnt+a.at(i).second >= M){
      yen += a.at(i).first *(M-cnt);
      //cnt = M;
      break;
    }
  }*/
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define smax(a, b) ((a) < (b) ? ((a)=(b), true) : false)
#define smin(a, b) ((a) > (b) ? ((a)=(b), true) : false)
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
using namespace std;

int n, m;
vector <int> graph[100001];
int degree[100001];
int dep[100001];
vector <int> emp;

void dfs(int a)
{   
    for(int t : graph[a]) {
        degree[t]--;
        dep[t] = max(dep[t], dep[a]+1);
    
        if(degree[t] == 0)
        {
            dfs(t);
        }
    }
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        graph[y].push_back(x);
        degree[x]++;  
    }
    for(int i = 1; i <= n; i++)
    {
        if(degree[i] == 0)
        {
            emp.push_back(i);
        }
    }

    for(int e : emp)
    {
        dfs(e);
    }

    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        ans = max(ans, dep[i]);
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 9600
#include <algorithm>
#include <cmath>
#include <climits>
#include <functional>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

using namespace std;
using ll  = long long;


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

    int A1, A2, A3;
    cin >> A1 >> A2 >> A3;
    if(A1+A2+A3 >= 22)
        cout << "bust" << endl;
    else
        cout << "win" << endl;
}

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

#define N   10000
#define NIL -1

typedef struct{
  int p, r, l;
} Node;

Node T[N];
int n, D[N], H[N];

void scan(void){
  int i, u, right, left;
  
  cin >> n;
  for(i=0; i<n; i++) T[i].p = T[i].r = T[i].l = NIL;

  for(i=0; i<n; i++){
    cin >> u >> right >> left;
    T[u].r = right; T[u].l = left;
    if(right != NIL) T[right].p = u;
    if(left != NIL) T[left].p = u;
  } 
}

void Depth(int u, int d){
  D[u]=d;
  if(T[u].r != NIL) Depth(T[u].r, d+1);
  if(T[u].l != NIL) Depth(T[u].l, d+1);
}

int Height(int u){
  int h1=0, h2=0;
 
  if(T[u].r != NIL) h1=Height(T[u].r) + 1;
  if(T[u].l != NIL) h2=Height(T[u].l) + 1;
 
  return H[u] = max(h1,h2);
}

void print(int u){
  
  printf("node %d: parent = %d, ", u, T[u].p);

  if(T[u].p == NIL) printf("sibling = %d, ", NIL); 
  else if(T[T[u].p].l != u) printf("sibling = %d, ", T[T[u].p].l);
  else if(T[T[u].p].r != u) printf("sibling = %d, ", T[T[u].p].r);
  else printf("sibiling = %d, ", NIL);

  if(T[u].r != NIL && T[u].l != NIL) printf("degree = 2, ");
  else if(T[u].r == NIL && T[u].l == NIL) printf("degree = 0, ");
  else printf("degree = 1, ");

  printf("depth = %d, height = %d, ", D[u], H[u]);
  
  if(T[u].p == NIL) printf("root\n");
  else if(T[u].r != NIL || T[u].l != NIL) printf("internal node\n");
  else printf("leaf\n");
}

int main(){

  int i, root;

  scan();

  for(i=0; i<n; i++){
    if(T[i].p == NIL){
      root = i;
      break;
    }
  }

  Depth(root, 0);
  Height(root);
  
  for(i=0; i<n; i++) print(i);
  
  return 0;
}

Measured memory_bytes: 3140
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

cnt = 0
before = -100
for i in range(n):
    cnt += b[a[i] - 1]

    if before + 1 == a[i]:
        cnt += c[before-1]

    before = a[i]
print(cnt)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep2(i, s, n) for(int i=s; i<(n); ++i)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;

static const int INTINF = (2147483647);
static const ll LLINF = (9223372036854775807);
static const int MAX = 100001;
static const ll MOD = 1000000007;

void printArray(vector<int> v){
    rep(i, v.size()){
        if(i) cout << " ";
        cout<< v[i];
    }
    cout << endl;
}

void print2dArray(vector<vector<int> > vv){
    rep(i, vv.size()){
        rep(j, vv[i].size()){
            if(j) cout << " ";
            cout << vv[i][j];
        }
        cout << endl;
    }
}

//--global--//


/*******-c++14 don't include-*******/
template<typename T>
T gcd(T a, T b){if( b == 0)return a; return gcd(b, a%b); }
template<typename T>
T lcm(T a, T b){return a*b/gcd(a,b); }
void printArr(int *a, int len){for(int i=0; i<len; i++){if(i)cout << " ";cout << a[i];}cout << endl;}
/*******---------------------*******/

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

ll solve(ll a){
    if(a == 0)return 1;
    ll tmp = a;
    if(!(tmp % 10 == 0)) tmp = 1;
    ll tmp2 = tmp;
    tmp2 /= 10;
    if(tmp2 % 5 == 0) tmp *= 10;
    return tmp * solve(a-2);
}

int main(int argc, const char * argv[]) {
    //提出時、消す----//
    //--------------//



    ll n = 0;

    cin >> n;

    if(n%2 == 1) {
        cout << 0 << endl;
        return 0;
    }
    
    ll res = 0;
    for(ll i=5; i<=n; i*=5){
        res += n/2 / i;
    }

    cout << res << endl;


    return 0;
}


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

using namespace std;

long long k;
int A;
int B;
int C;

int main() {
	cin >> A >> B >> C >> k;
	if(k & 1) {int a = B + C, b = A + C, c = A + B; A = a, B = b, C = c;}
	if(abs(A - B) > 1e18) puts("Unfair");
	else cout << A - B;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>

using namespace std;

int main(){
    int n;
    while(cin >> n && n){
        int cnt =0;
        for(int i=1; i<500;i++){
            int sum=0;
            int j=i;
            while(sum<=n){ 
                sum+=j;
                if(sum==n && j!=n){cnt++;}
                j++;
            }
        }
        cout << cnt<<endl;
    }

    return 0;
}

Measured memory_bytes: 3088
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////
int N, H;
int a[100100], b[100100];
int ans = INF;
void def(int h,int a,int b) {

}
int main() {
	cin >> N >> H;
	vector<pii>V;
	for (int i = 0; i < N; ++i) {
		cin >> a[i] >> b[i];
		V.push_back({ a[i],0 });
		V.push_back({ b[i],1 });
	}
	sort(V.begin(), V.end(),greater<pii>());
	int ans = 0;
	for (int i = 0; i < V.size();) {
		if (V[i].second == 1) {
			H -= V[i].first;
			ans++;
			if (H <= 0) {
				cout << ans << endl;
				return 0;
			}
			i++;
		}
		else {
			if (H%V[i].first == 0) {
				ans += (H / V[i].first);
			}
			else {
				ans += (H / V[i].first) + 1;
			}
			cout << ans << endl;
			return 0;
		}
	}

	return 0;
}


Measured memory_bytes: 3956
#include <bits/stdc++.h>
#include <cstdio>
#include <algorithm>
using namespace std;
#define r(i,n) for(int i=0;i<n;i++)
#define ll long long
const ll mod = 1000000007;


int main(){
  int n;
  string s;
  scanf("%d", &n);
  cin>>s;

  int cnt=0;


  r(i,n){
    //cout<<cnt<<endl;



    if(s.at(i)=='(')cnt++;
    if(s.at(i)==')' and cnt == 0){cout<<'(';}
    else if(s.at(i)==')')cnt--;

  }

  //cout<<cnt<<endl;
  if(cnt<0){
    r(i,abs(cnt))cout<<'(';
    cout<<s<<endl;
  }else{
    cout<<s;
    r(i,abs(cnt))cout<<')';
    cout<<endl;
  }



  return 0;
}


Measured memory_bytes: 256
N, K = map(int, input().split())
d = [0 for _ in range(K)]
sunuke = [0 for _ in range(N)]

for i in range(K):
    d[i] = int(input())
    a = list(map(int, input().split()))
    for i in a:
        sunuke[i-1] += 1

print(sunuke.count(0))

Measured memory_bytes: 9080
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jaynil
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CLower solver = new CLower();
        solver.solve(1, in, out);
        out.close();
    }

    static class CLower {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int count = 0;
            int ans = 0;
            int x = in.nextInt();
            for (int i = 1; i < n; i++) {
                int temp = in.nextInt();
                if (temp <= x) count++;
                else count = 0;
                ans = Math.max(count, ans);
                x = temp;
            }
            out.println(ans);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 38360
/*
 Educational Dp Contest Atcoder
 
 */

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
#define int long long int
typedef complex<long double> cd;
const long double pi=acos(-1);
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <db, db> pdd;
typedef vector<int> vi;
typedef vector<vector<int> > matrix;

#define m1 make_pair
#define pb push_back
#define flush fflush(stdout)
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define reset(x,v) memset(x,v,sizeof(x))

#define fi first
#define se second
#define endl "\n"
#define debug(x) (cerr << #x << ": " << x << "\n")
#define setbits(x) __builtin_popcount(x)
#define setbitsll(x) __builtin_popcountll(x)
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define all(x) x.begin(),x.end()

inline ll gcd(ll a,ll b){if(a==0) return b;return gcd(b%a,a);}
inline ll power(ll a,ll n,ll m){if(n==0)return 1;ll p=power(a,n/2,m);p=(p%m*p%m)%m;if(n%2) return (p%m*a%m)%m;else return p;}

const ll MOD =998244353;
const ll hell=1000000007;
const int INF=1e16;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
template<typename T>
using ordered_set=tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 rng(seed);

const int N=1005;

int dp[N][N];
string s[N];
void solve()
{
    
    int n,m;
    cin>>n>>m;
    
    for(int i=0;i<n;i++)
        cin>>s[i];
    dp[1][1]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(i==1&&j==1)
                continue;
            if(s[i-1][j-1]=='.')
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%hell;
        }
    cout<<dp[n][m]<<endl;
    
    
    
}

int32_t main()
{
    
    IOS;
    //FILE *fin = freopen("in","r",stdin);
    //FILE *fout = freopen("out","w",stdout);
    int t;
    t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 9216
#include<iostream>
using namespace std;
int main() {
	int N;
	int p[100];
	int max = 0;
	int maxNum = -1;
	int ans = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> p[i];
		if (max <= p[i]) {
			max = p[i];
			maxNum = i;
		}
	}
	for (int j = 0; j < N; j++) {
		if (maxNum != j) {
			ans += p[j];
		}
		else {
			ans += (p[j] / 2);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

class UnionFindTree:
    def __init__(self, n: int):
        self.n = n
        self.root = [-1] * (n+1)
        self.rank = [0] * (n+1)
    def findRoot(self, x: int) -> int:
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.findRoot(self.root[x])
            return self.root[x]
    def unite(self, x: int, y: int):
        x = self.findRoot(x)
        y = self.findRoot(y)
        if x == y:
            return
        elif self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
    def same(self, x: int, y: int) -> bool:
        if self.findRoot(x) == self.findRoot(y):
            return True
        else:
            return False
    def count(self, x: int) -> int:
        return -self.root[self.findRoot(x)]


def main():
    n, q = map(int, input().split())
    UFT = UnionFindTree(n-1)
    for _ in range(q):
        com, x, y = map(int, input().split())
        if com == 0:
            UFT.unite(x, y)
        else:
            if UFT.same(x, y):
                print(1)
            else:
                print(0)


if __name__ == '__main__': main()


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


int main()
{
    int a,b,c,k;
    cin>>a>>b>>c>>k;

    long long sum = 0;
    while(k)
    {

        sum+=min(a,k);
        k-=min(a,k);
        a=0;

        k-=min(b,k);
        b=0;

        sum-=min(c,k);
        k-=min(c,k);
        c=0;

        if(a==0 && b==0 && c==0) break;
        
    }
    cout<<sum<<endl;
    
    
    return 0;
}


Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int n;
    cin >> n;
    ll a[n], f = 0, l, s = 1;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        if(i < n - 1) {
            f += 2 * s * a[i];
            s *= -1;
        }
        else l = a[i] * 2;
    }
    ll ans[n] = {0};
    ans[0] = (f + l) / 2;
    ans[n - 1] = l - ans[0];
    for(int i = n - 2; i > 0; i--) {
        ans[i] = 2 * a[i] - ans[i + 1];
    }
    for(int i = 0; i < n; i++) cout << ans[i] << " ";
}


Measured memory_bytes: 2816
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

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
















int main(){
    ll n;
    cin >> n;
    vector<vector<ll>> g(n);
    REP(i, n - 1){
        ll a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<ll> v1, v2;
    [&, dfs = [&](auto && dfs, ll now, ll par, bool flag) -> void {
        if(flag) v2.push_back(now);
        else v1.push_back(now);
        for(auto &next : g[now]){
            if(next == par) continue;
            dfs(dfs, next, now, !flag);
        }
    }](){ dfs(dfs, 0, -1, false); }();
    vector<ll> ans(n);
    if(v1.size() <= n / 3){
        vector<bool> used(n + 1);
        REP(i, v1.size()){
            ans[v1[i]] = 3 * (i + 1);
            used[3 * (i + 1)] = true;
        }
        ll idx = 1;
        REP(i, v2.size()){
            while(used[idx]){
                idx++;
            }
            ans[v2[i]] = idx;
            used[idx] = true;
        }
    }
    else if(v2.size() <= n / 3){
        vector<bool> used(n + 1);
        REP(i, v2.size()){
            ans[v2[i]] = 3 * (i + 1);
            used[3 * (i + 1)] = true;
        }
        ll idx = 1;
        REP(i, v1.size()){
            while(used[idx]){
                idx++;
            }
            ans[v1[i]] = idx;
            used[idx] = true;
        }
    }
    else{
        vector<bool> used(n + 1);
        ll idx = 1;
        REP(i, v1.size()){
            if(idx > n){
                idx = 3;
            }
            ans[v1[i]] = idx;
            used[idx] = true;
            idx += 3;
        }
        idx = 1;
        REP(i, v2.size()){
            while(used[idx]){
                idx++;
            }
            ans[v2[i]] = idx;
            used[idx] = true;
        }
    }
    REP(i, n){
        cout << ans[i] << " \n"[i == n - 1];
    }
}

Measured memory_bytes: 19688
#include <iostream>
using namespace std;

bool checkPrimeNumber( int x ) {
	for( int i = 3; i < x; i+=2 ) {
		if( x % i == 0 ) {
			return false;
		}
	}
	return true;
}

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

	if ( x == 2 ) {
		cout << x << endl;
		return 0;
	}
	if ( x%2 == 0 ) x+=1;

	bool isFound = false;
	int limit = 20000000;
	while( !isFound ) {

		if ( x > limit ) break;

		isFound = checkPrimeNumber(x);
		if( isFound ) break;

		x += 2;
	}

	cout << x << endl;
	return 0;

}

Measured memory_bytes: 256
import java.io.PrintWriter

fun main(args: Array<String>) {
    PrintWriter(System.out).use { out ->
        solve(out)
        out.flush()
    }
}

fun solve(out: PrintWriter) {
    val s = readLine()!!
    println(s.length / 2 - s.count { it == 'p' })
}

fun readInteger() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntegerList() = readStringList().map(String::toInt)
fun readLongList() = readStringList().map(String::toLong)
fun readDoubleList() = readStringList().map(String::toDouble)


Measured memory_bytes: 34208
#include <stdio.h>

int main(void)
{
  while(1)
    {
  int H,W;

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

  if(H==0 && W==0)
    {
      break;
    }

  for(int y=0;y<H;y++)
    {
      for(int x=0;x<W;x++)
	{
	  if(x == W - 1)
	    {
	      printf("#\n");
	    }
	  else
	    {
	      printf("#");
	    }
	}
    }
  printf("\n");
    }
  
  return 0;
}

Measured memory_bytes: 1016
#include <algorithm>
#include <bitset>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repk(i, k, n) for (int i = k; i < n; i++)
#define MOD 1000000007
#define INF 1e9
#define PIE 3.14159265358979323

template <class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
T GCD(T a, T b) {
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}
template <class T>
inline T LCM(T a, T b) {
    return (a * b) / GCD(a, b);
}

using namespace std;
//#inculude <bits/stdc++.h>
#define int long long

template <class T>
map<T, T> prime_factorize(T n) {
    map<T, T> res;
    for (T i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            res[i]++;
            n /= i;
        }
    }
    if (n != 1)
        res[n] = 1;
    return res;
}

namespace my {
void merge(std::map<int, int> &a, std::map<int, int> b) {
    for (auto i = b.begin(); i != b.end(); i++) {
        if (a[i->first] > 0)
            a[i->first] += i->second;
        else
            a[i->first] = i->second;
    }
}
} // namespace my

signed main() {
    int n;
    cin >> n;
    int res = 1;
    map<int, int> m;
    repk(i, 1, n + 1) my::merge(m, prime_factorize(i));
    for (auto itr = m.begin(); itr != m.end(); itr++) {
        res *= (itr->second + 1) % MOD;
        res %= MOD;
    }
    cout << res << endl;
}

Measured memory_bytes: 3624
X,K,D=map(int,input().split())

X=abs(X)
if X>=K*D:
  print(X-K*D)
elif X==0:
  if K%2==0:
    print(0)
  else:
    print(D)
else:
  step=X//D
  X-=step*D
  K-=step
  if K%2==0:
    print(X)
  else:
    print(D-X)

Measured memory_bytes: 9196
#include <bits/stdc++.h>
#define FOR(i, l, r) for(int i = (int)l; i <= (int)r; ++i)
#define REP(i, r) for(int i =(int)0; i < (int)r; ++i)

using namespace std;
typedef long long ll;
const int Nmax = 1e3 + 11;
const int MOD = 1e9 + 7;

int n, m, f[Nmax][Nmax];
char c[Nmax][Nmax];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    FOR(i, 1, n) FOR(j, 1, m) {
        cin >> c[i][j];
    }
    FOR(i, 1, n) FOR(j, 1, m) {
        if (i == 1 && j == 1) {
            f[i][j] = 1;
            continue;
        }
        if (c[i][j] == '.') f[i][j] = (f[i - 1][j] + f[i][j - 1]) % MOD;
    }
    cout << f[n][m];
}


Measured memory_bytes: 5248
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N; cin>>N;
    vector<int> A(N);
    for(int i=0;i<N;i++){
        cin>>A[i];
    }
    vector<int> B(N);
    for(int i=0;i<N;i++){
        cin>>B[i];
    }
    vector<int> C(N,0);
    for(int i=0;i<N-1;i++){
        cin>>C[i];
    }
    int ans=0;
    for(int i=0;i<N;i++){
        ans=ans+B[A[i]-1];
        if(i>0&&A[i]-A[i-1]==1){
            ans=ans+C[A[i]-2];
        }
    }
    cout<<ans;

    return 0;
}

Measured memory_bytes: 256
import sys

N = int(input())

As = [int(n) for n in input().split()]
As_set = set(As)

limit = 10**18

prod = 1

if 0 in As_set:
    print(0)
    sys.exit(0)

over = False
for A in As:
    prod *= A
    if prod > limit:
        print(-1)
        sys.exit(0)

print(prod)

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

int main(void){
  int n;cin >> n;
  int h[n];rep(i,n)cin >> h[i];
  for(int i=n-1;i>=0;--i){
    if(h[i-1] > h[i])h[i-1] -= 1;
    if(h[i-1] > h[i]){cout << "No" << endl;return 0;}
  }
  cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <sstream>
#include <stack>
#include <iomanip>
#include <numeric>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <cassert>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define BEGIN(x) x.begin()
#define END(x) x.end()
#define ALL(x) BEGIN(x), END(x)
#define PAIR make_pair
#define VEC(type) vector<type >
#define endl '\n'
#define FIR first
#define SEC second
#define PB push_back
#define SZ(x) ((int)x.size())

#define FOR(i, A, B) for(auto i = (A);i != (B); i++)
#define FORD(i, A, B) for(auto i = (A);i != (B); i--)

#define READRANGE(begin, end) FOR(it, begin, end) cin >> *it
#define READVEC(V) READRANGE(BEGIN(V), END(V))

using namespace std;

typedef long long lint;
typedef pair<int, int> Pii;
typedef pair<int, lint> Pil;
typedef pair<lint, lint> Pll;
typedef pair<lint, int> Pli;

template<class U, class V>
istream& operator >>(istream& in, pair<U, V>& pr) {
    return in >> pr.first >> pr.second;
}

template<class U, class V>
ostream& operator <<(ostream& out, pair<U, V>& p) {
    return out << p.first << " " << p.second;
}

template<class T>
ostream& operator <<(ostream& out, vector<T> vec) {
    for (T& e : vec)
        out << e << " ";
    return out << endl;
}

// ---- BEGIN LIBRARY CODE ----
// ---- END LIBRARY CODE ----
void io_init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
};

void solveSingleCase(int caseNo)
{
    int N;
    cin >> N;
    VEC(int) A(N);
    READVEC(A);

    const int MAXN = 1000000;
    VEC(bool) bad(MAXN + 1, false);
    map<int, int> counter;

    for (int a : A) if (!bad[a]) {
        FOR(m, 2, MAXN / a + 1)
            bad[a * m] = true;
        counter[a]++;
        if (counter[a] >= 2)
            bad[a] = true;
    }

    int ret = 0;
    for (int a : A)
        if (!bad[a])
            ret++;

    cout << ret << endl;
};

int main(int argc, char **argv)
{
    io_init();

    // Actual program code starts here.
    int T = 1;
    // cin >> T;
    FOR(tcase, 1, T + 1) {
        solveSingleCase(tcase);
    }
    return 0;
};


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

string S;

int main() {
    cin >> S;
    int N = S.length();

    int ans = 0;
    for (int i = 0; i < N/2; i++) {
        if (S[i] != S[N-1-i]) ans++;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;

int main(){
	string in, out = "";
	while(cin>>in){
		int ap = in.find("apple");
		int pe = in.find("peach");
		if(ap>=0){
			in.replace(ap,5, "peach");
		}
		else if(pe>=0){
			in.replace(pe,5, "apple");
		}
		if(out ==""){
			out += in;
		}
		else{
			out += " ";
			out += in;
		}
	}
	cout << out << endl;
	return 0;
}

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

using namespace std;


int main() {

    int N, T;
    cin >> N >> T;
    vector<int> t(N);
    for (int i = 0; i < N; ++i) {
        cin >> t[i];
    }

    // 差分行列
    vector<int> dif(N - 1, 0);
    for (int i = 0; i < N - 1; ++i) {
        dif[i] = t[i + 1] - t[i];
    }

    int x = 0;
    // N-1回
    for (int i = 0; i < N - 1; ++i) {
        int d = dif[i];
        if (d >= T) {
            x += T;
        }
        if (d < T) {
            x += d;
        }
    }
    // N回目
    x += T;
    int ans = x;
    cout << ans << endl;
}

Measured memory_bytes: 1792
H, W = map(int, input().split())

L = ["." * (W+2)] + [("." + input() + ".") for _ in range(H)] + ["." * (W+2)]
flg = False
for i in range(H):
  if flg:
    print ("No")
    break
  for j in range(W):
    if L[i][j] == "#":
      if all((L[i-1][j] == ".", L[i+1][j] == ".", L[i][j+1] == ".", L[i][j-1] == ".")):
        flg = True
        break

else:
  print ("Yes")

Measured memory_bytes: 3064
#include <stdio.h>

int main(){
  int x,y,a=0,i,temp=0;
  scanf("%d %d",&x,&y);
  
  if(x<y)
    {
      temp=y;
      y = x;
      x = temp;
    }
  a = x % y;
  while(a !=0)
    {
      x = y;
      y = a;
      a = x%y;
    }

  
  printf("%d\n",y);
 
  return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
/// TONI BO$$ was here
/// #MLC

using namespace std;
int r[100001];
vector <long long> v;
int main()
{
    int i,j;
    long long n,x,m;
    scanf("%lld%lld%lld",&n,&x,&m);
    r[x]=1;
    v.push_back(x);
    for(i=2; i<=n; i++)
    {
        x=(x*x)%m;
        if(r[x])
            break;
        r[x]=1;
        v.push_back(x);
    }
    if(i>n || r[0]==1)
    {
        long long s=0;
        for(auto it : v)
            s+=it;
        printf("%lld",s);
        return 0;
    }
    long long s=0,s2=0,s3=0;
    for(i=0; i<v.size() && v[i]!=x; i++) s3+=v[i];
    n-=i;
    for(j=i; j<i+n%(v.size()-i); j++)
        s2+=v[j];
    for(j=i; j<v.size(); j++) s+=v[j];
    printf("%lld",s*(n/(v.size()-i))+s2+s3);

    return 0;
}
///492443256042078
///492443256176507


Measured memory_bytes: 4292
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
using Graph = vector<vector<int>>;
const int INT_INF = 1001001001;
const int dx[8] = {1,0,-1,0,1,1,-1,-1};
const int dy[8] = {0,1,0,-1,1,-1,1,-1};

int main(){
    int h,w;
    cin >> h >> w;
    char s[h][w];
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin >> s[i][j];
        }
    }
    char ans[h][w];
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            ans[i][j] = '0';
        }
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(s[i][j] == '#'){
                for(int dir = 0;dir < 8;dir++){
                    int nh = i + dx[dir];
                    int nw = j + dy[dir];
                    if(nh<0||nh>=h||nw<0||nw>=w) continue;
                    ans[nh][nw]++;
                }
            }
        }
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(s[i][j] == '#') ans[i][j] = '#';
        }
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cout << ans[i][j];
        }
        cout << endl;
    }

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
using namespace std;
using P = pair<int, int>;
using ll = long long;


ll sup = 100100100100100100;
int main()
{
    // input
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    rep(i,n) cin >> h[i];

    // dp
    vector<ll> dp(n, sup); // the cost to get to the scaffold of index_n
    dp[0] = 0;

    rep(i,n-1) {
        for(int j=1; j<=k; j++){
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j] - h[i]));
            if(i+j==n-1) break;
        }
    }

    cout << dp[n-1] << endl;


    return 0;
}


Measured memory_bytes: 1408
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String s = reader.readLine();
        String t = reader.readLine();
        boolean flag = true;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != t.charAt(i))
                flag = false;
        }
        if (flag) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 32764
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder();

            int n = int.Parse(Console.ReadLine());

            for (int i = 0; i < n; i++)
            {
                string txt = Console.ReadLine();

                txt = txt.Replace("Hoshino", "Hoshina");

                sb.AppendLine(txt);
            }
            Console.Write(sb);
        }
    }
}

Measured memory_bytes: 8892
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=100000000000000000;

int main() {
    string s;
    cin >> s;
    ll n=s.size()+1;
    vector<ll> a(n,0);
    rep(i,s.size()){
        if (s[i]=='>') a[i+1]=0;
        else a[i+1]=a[i]+1;
    }
    rep(i,s.size()){
        if (s[n-2-i]=='<') a[n-2-i]=a[n-2-i];
        else a[n-2-i]=max(a[n-2-i],a[n-1-i]+1);
    }
    ll ans=0;
    rep(i,n){
        ans+=a[i];
    }
    cout << ans << endl;
}


Measured memory_bytes: 4740
y = input()
y = input().split()
y = [ int(x) for x in y]
sum_go = []
sum_back = []
for i in range(1, len(y)):
    sum_go.append(sum(y[0:i] ))
    sum_back.append(sum(y[i:] ))
#print(sum_go)
#print(sum_back)
result = []
for i in range(len(sum_go)):
    result.append( abs(sum_go[i] - sum_back[i]) )
print(min(result))

Measured memory_bytes: 3064
# A^5-B^5=(B+d)^5-B^5

X=int(input())

div=[1,X]

for i in range(2,X):
    if X%i==0:
        div.append(i)
        div.append(X//i)
    if i*i>=X:
        break

for d in div:
    for j in range(-100000,100000):
        A=j+d
        B=j
        if A**5-B**5==X:
            print(str(A)+" "+str(B))
            exit(0)
            


Measured memory_bytes: 9164
#include <ctime>
#include <iomanip>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <list>
#include <queue>
#include <stack>
#include <numeric>
using namespace std;

#define int long long
#define INF 1e18
#define EPS 1e-9
#define NIL -1
#define N 100

signed main() {
    int n, m; cin >> n >> m;
    vector<int> x(m); for(int i = 0; i < m; i++) cin >> x[i];

    int ans = 0;
    if(n >= m) {
        cout << ans << endl;
        return 0;
    }

    sort(x.begin(), x.end());

    vector<int> y(m - 1);
    for(int i = 0; i < m - 1; i++) y[i] = x[i + 1] - x[i];

    sort(y.begin(), y.end());

    for(int i = 0; i < m - n; i++) ans += y[i];

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
#![allow(unused_imports)]
#![allow(dead_code)]

use std::thread;
use std::io::{ self, Read };
use std::fmt;
use std::iter::Iterator;
use std::cmp::*;
use std::collections::*;
use std::str::*;

#[derive(Default)]
struct Input {
    buf: Vec<String>
}

impl Input {
    fn new() -> Input {
        Input { buf: Vec::new() }
    }

    fn read<T: FromStr>(&mut self) -> T 
    where <T as FromStr>::Err: fmt::Debug {
        self.next().unwrap().parse::<T>().unwrap()
    }

    fn read_n<T: FromStr>(&mut self, n: usize) -> Vec<T>
    where <T as FromStr>::Err: fmt::Debug {
        let mut v = Vec::new();
        for _ in 0..n { v.push(self.read::<T>()); }
        v
    }
}

impl Iterator for Input {
    type Item = String;
    fn next(&mut self) -> Option<String> {
        while self.buf.is_empty() {
            let mut s = String::new();
            let _res = io::stdin().read_line(&mut s);
            self.buf = s.split_whitespace().map(|s| s.to_owned()).collect::<Vec<_>>();
            self.buf.reverse();
        }
        self.buf.pop()
    }
}

struct UnionFind {
    c: Vec<(usize, usize)>
}

impl UnionFind {
    fn new(n: usize) -> UnionFind {
        UnionFind { c: (0..n).map(|u| (u, 0)).collect::<Vec<_>>() }
    }

    fn root(&self, u: usize) -> usize {
        let v = self.c[u].0;
        if u == v { u } else { self.root(v) }
    }

    fn is_same(&self, u: usize, v: usize) -> bool {
        self.root(u) == self.root(v)
    }

    fn size(&self, u: usize) -> usize {
        self.c[u].1
    }

    fn unite(&mut self, u: usize, v: usize) {
        let ru = self.root(u);
        let rv = self.root(v);
        let su = self.size(u);
        let sv = self.size(v);
        if su > sv {
            self.c[rv] = (ru, su + sv);
        } else {
            self.c[ru] = (rv, su + sv);
        }
    }
}

fn run() {
    let mut ip = Input::new();
    let n = ip.read::<usize>();
    let m = ip.read::<usize>();
    let mut e = Vec::new();
    for _ in 0..m {
        let u = ip.read::<usize>();
        let v = ip.read::<usize>();
        let w = ip.read::<i64>();
        e.push((w, u, v));
    }
    e.sort();
    let mut uf = UnionFind::new(n);
    let mut y = 0i64;
    for (w, u, v) in e {
        if !uf.is_same(u, v) {
            uf.unite(u, v);
            y += w;
        }
    }
    println!("{}", y);
}

fn main() {
    let _ = thread::Builder::new()
        .stack_size(10 * 1024 * 1024)
        .spawn(run).unwrap()
        .join();
}


Measured memory_bytes: 13128
def solve2(N, S):
    W = [0]*N
    W[0] = 1 if S[0] == '.' else 0
    for i in range(1, N):
        W[i] = W[i-1] + (1 if S[i] == '.' else 0)
    ans = min(W[-1], N-W[-1])
    temp = []
    for i in range(N-1):
        #print('left={}, right={}'.format(W[i], W[-1]-W[i]))
        left = i+1-W[i]
        right = W[-1]-W[i+1]
        #print(left, right)
        ans = min(ans, left+right)
        temp.append(left+right)
    return ans


# ... i / i+1 ####
# ####
N = int(input())
S = str(input())
print(solve2(N, S))


Measured memory_bytes: 19304
#include <bits/stdc++.h>
using namespace std;
//Kodid in Dongo Ĝifun 4
//IP aĝres: 192.168.12.233

int main(){
	int qwq;
	scanf("%d",&qwq);
	while(qwq--){
		long long a,b,c,d;
		scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
		vector<pair<int,int> > ans;
		long long gen=(a+b)/(min(a,b)+1);
		int l=-1,r=a/gen+1;
		while(r-l>1){
			int m=(l+r)>>1;
			long long A=a-m*gen,B=b-max(0,m-1);
			if((A+1)*gen>=B&&A>=0&&B>=0){
				l=m;
			}else{
				r=m;
			}
		}
		a-=l*gen;
		b-=max(0,l-1);
		if(!l){
			long long bb=b%gen;
			if(a*gen<b){
				ans.push_back(make_pair(2,b-a*gen));
				ans.push_back(make_pair(4,a));
			}else if(!bb){
				long long xx=b/gen;
				ans.push_back(make_pair(1,a-xx+1));
				ans.push_back(make_pair(2,gen));
				ans.push_back(make_pair(4,xx-1));
			}else{
				long long xx=b/gen;
				ans.push_back(make_pair(1,a-xx));
				ans.push_back(make_pair(2,bb));
				ans.push_back(make_pair(4,xx));
			}
		}else{
			ans.push_back(make_pair(3,l-1));
			ans.push_back(make_pair(1,gen));
			if(a*gen<b-1){
				ans.push_back(make_pair(2,b-a*gen));
				ans.push_back(make_pair(4,a));
			}else{
				ans.push_back(make_pair(2,1));
				b--;
				long long xx=(b+gen-1)/gen;
				ans.push_back(make_pair(1,a-xx+1));
				ans.push_back(make_pair(2,b-(xx-1)*gen));
				ans.push_back(make_pair(4,xx-1));
			}
		}
		string s;
		for(int i=c;i<=d;i++){
			long long rem=i-1;
			for(int j=0;j<(int)ans.size();j++){
				long long len=ans[j].second;
				if(ans[j].first>=3){
					len*=gen+1;
				}
				if(rem<len){
					if(ans[j].first==1){
						s+='A';
					}else if(ans[j].first==2){
						s+='B';
					}else{
						rem%=gen+1;
						if(ans[j].first==3){
							if(rem==gen){
								s+='B';
							}else{
								s+='A';
							}
						}else{
							if(!rem){
								s+='A';
							}else{
								s+='B';
							}
						}
					}
					break;
				}else{
					rem-=len;
				}
			}
		}
		cout<<s<<endl;
	}
	return 0;
}
//ª¡ª¡ª¡ª¡ª¡ª¡ª¡ª¡ª¡ª¡//


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define MOD 1000000007
using namespace std;

int dp[4001],n,a,b,c,i;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int h,a;
    cin >> h >> a;
    int ans=h/a;
    if(h%a) ans++;
    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		Long N = sc.nextLong();
		Long M = sc.nextLong();

		Long ans = 0L;

		while(1 <= N && 2 <= M){
			Long s_num = N;
			Long c_num = M / 2;

			Long scc_num = s_num < c_num ? s_num : c_num;

			ans += scc_num;

			N -= scc_num;
			M -= scc_num * 2;

			N = M / 2;
			M = M / 2;
		}

		System.out.println(ans);

		sc.close();
	}

}


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

#define ll long long
#define all(x) (x).begin(), (x).end()
const long long INF = 1LL << 60;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)  //(i, 10) i=0～i=9まで
#define repr(i, n) for (int i = n; i >= 0; i--)   // (i, 10) i=10～i=0まで
#define FOR(i, m, n) for (int i = m; i < n; i++)  // (i, 3, 10) i=3～i=9まで

// 総数を1000000007で割った余り
const long long mod = 1e9 + 7;

int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    // cout << fixed << setprecision(5);

    // 入力
    int r, g, b;
    cin >> r >> g >> b;

    // 処理
    int number = r * 100 + g * 10 + b;

    // 出力
    cout << (number % 4 == 0 ? "YES" : "NO ") << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
 
using namespace std;
 
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)

long gcd(long a, long b){
	if (a%b==0){
		return b;
	}
	else{
		return gcd(b,a%b);
	}
}

long lcm(long a, long b){
	return (a*b) / gcd(a,b);
}
 
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a < b) { a = b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a > b) { a = b; return 1; } return 0; }
 
typedef long long ll;
 
const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS = 1e-10;

int main(){
	ll n, a, b;
	
	cin >> n >> a >> b;
	
	ll s = b - a;
	
	if (s == 0) cout << "1" << endl;
	else if (n == 1)cout << "0" << endl;
	else {
		if (s < 0) cout << "0" << endl;
		else {
			ll ma = b;
			ll mi = a;
			
			cout << (mi+(n-1)*ma)-((n-1)*mi+ma)+1 << endl;
		}
	}
	
	return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from collections import deque
from itertools import product
import heapq


def read():
    H, W = map(int, input().strip().split())
    CH, CW = map(int, input().strip().split())
    DH, DW = map(int, input().strip().split())
    S = [[0 for j in range(W)] for i in range(H)]
    for i in range(H):
        s = list(input().strip())
        for j in range(W):
            if s[j] == "#":
                S[i][j] = -2
            else:
                S[i][j] = -1
    return H, W, CH, CW, DH, DW, S


def solve(H, W, CH, CW, DH, DW, S):
    DIR0 = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    DIR1 = [
        (-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
        (-1, -2), (-1, -1), (-1, 1), (-1, 2),
        (0, -2), (0, 2),
        (1, -2), (1, -1), (1, 1), (1, 2),
        (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)
    ]
    S[CH-1][CW-1] = 0
    q = deque()
    q.appendleft((CH-1, CW-1))
    while q:
        # キューの先頭から候補を取り出す
        y0, x0 = q.popleft()
        d0 = S[y0][x0]
        # 距離0で到達可能な場所をキューの先頭に入れる
        for dy, dx in DIR0:
            ny, nx = y0 + dy, x0 + dx
            if 0 <= ny < H and 0 <= nx < W and (S[ny][nx] == -1 or S[ny][nx] > d0):
                q.appendleft((ny, nx))
                S[ny][nx] = d0
        # 距離1で到達可能な場所をキューの末尾に入れる
        for dy, dx in DIR1:
            ny, nx = y0 + dy, x0 + dx
            if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == -1:
                q.append((ny, nx))
                S[ny][nx] = d0+1
    return S[DH-1][DW-1]


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


Measured memory_bytes: 86336