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

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

using namespace std;
typedef long long ll;
const int MAXN = 1000000;

ll cnt;
vector<int> G;

void insertionsort(int *A, int N, int G) {
	for (int i = G; i < N; i++) {
		int v = A[i];
		int j = i - G;
		while (j >= 0 && A[j] > v) {
			A[j + G] = A[j];
			j -= G;
			cnt++;
		}
		A[j + G] = v;
	}
}

void shellsort(int *A, int N) {
	cnt = 0;
	int m = 1;
	do {
		G.push_back(m);
		m = 3 * m + 1;
	} while (m < N&&G.size() <= 100);
	for (int i = G.size() - 1; i >= 0; i--) {
		insertionsort(A, N, G[i]);
	}
}


int main() {
	static int n, A[MAXN];
	cin >> n;
	rep(i, n)cin >> A[i];
	shellsort(A, n);
	cout << G.size() << endl;
	for (int i = G.size() - 1; i >= 0; i--) {
		if (i != 0)cout << G[i] << " ";
		else cout << G[i] << endl;
	}
	cout << cnt << endl;
	rep(i, n)cout << A[i] << endl;

	return 0;
}


Measured memory_bytes: 6972
#include <bits/stdc++.h>
#define ll  long long
#define ull unsigned long long  
using namespace std;
#define  inf 1e6+18
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define mod 1000000007
#define  f1(i,n) for(i=1;i<=n;i++)
#define f0(i,n)  for(i=0;i<n;i++)
#define w(x)   while(x--)
const int maxn=500001;
#define  pq priority_queue
#define  ff first
#define  ss second 
#define pb  push_back
#define lb lower_bound
int main()
{
	fastio;
	int t;
	//cin>>t;
	
		ll i,j,k,l,m,n;
		cin>>n;
		if(n<=1)
		{
			cout<<0;
		}
		else
		{
		//	l=n*(n-1);
			//l=l%mod;
			l=1;
			m=1;
			k=1;
			for(i=1;i<=n;i++)
			{
				l=(l*10)%mod;
				m=(m*8)%mod;
				k=(k*9)%mod;

			}
			cout<<(l+m+mod-(2*k)%mod)%mod;
		}
		

	
}

Measured memory_bytes: 3608
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <cmath>
#include <map>
#include <iomanip>
#include <unordered_map>

using namespace std;
typedef long long  ll;

const ll mod = 1000000007;

int main()
{
	ll N;
	cin >> N;
	vector<ll> a(N);
	ll ave = 0;
	for (ll i = 0; i < N; i++)
	{
		cin >> a[i];
		ave += a[i];
	}
	ave /= N;
	ll ave1 = ave + 1;
	ll ans = 0, ans1 = 0;
	for (ll i = 0; i < N; i++)
	{
		ans += abs(a[i] - ave) * abs(a[i] - ave);
		ans1 += abs(a[i] - ave1) * abs(a[i] - ave1);
	}
	cout << min(ans, ans1) << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long c = sc.nextLong();
        long k = sc.nextLong();

        long[] t = new long[n];
        for(int i=0; i<n; i++) {
            t[i] = sc.nextLong();
        }

        Arrays.sort(t);
        int bus = 0;
        for(int i=0; i<n;) {
            int start = i;
            while(i < n && t[i] - t[start] <= k && i - start < c) i++;
            bus++;
        }
        System.out.println(bus);
    }
}


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

typedef long long int ll;

ll MOD = 1000000007;
ll INF = 100000000;

int main(){
 int N,T;
 cin >> N >> T;
 int ans = INF;
 for(int i = 0;i < N;i++){
   int a,b;cin >> a >> b;
   if(b <= T)ans = min(ans,a);
 }
 if(ans == INF){
   cout << "TLE" << endl;
   return 0;
 }
 cout << ans << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
long long n,y;
int i,j,k;
int main()
{
	cin>>n>>y;
	if(y/10000>n)
	{
		cout<<"-1 -1 -1"<<endl;
		return 0;
	}
	y=y/1000;
	for(i=0;i+j+k<=n;i++)
	{
		for(j=0;i+j+k<=n;j++)
		{
			for(k=0;i+j+k<=n;k++)
			{
				if((i*10+j*5+k*1==y)&&(i+j+k==n))
				{
					cout<<i<<" "<<j<<" "<<k<<endl;
					return 0;
				}
			}
			k=0;
		}
		j=0;
	}
	cout<<"-1 -1 -1"<<endl;
	return 0;
}

Measured memory_bytes: 256
#! /usr/bin/env python3

import sys
import numpy as np
from functools import lru_cache
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


@lru_cache(maxsize=None)
def f(x):
    if x == 0:
        return 0
    return f(x % bin(x).count('1')) + 1


N = int(readline())
X = readline().decode().rstrip()
X_ = int(X, 2)
X_cnt = X.count('1')
p1 = X_ % (X_cnt + 1)
m1 = X_ % (X_cnt - 1) if X_cnt > 1 else 0

for i in range(N):
    if X[i] == '0':
        cnt = X_cnt + 1
        acc = (p1 + pow(2, N - i - 1, cnt)) % cnt

    else:
        cnt = X_cnt - 1
        if cnt == 0:
            print(0)
            continue
        acc = (m1 - pow(2, N - i - 1, cnt)) % cnt
    print(f(acc) + 1)


Measured memory_bytes: 29376
/* ALDS1_3_B_Queue */

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>

#define N 100000
#define NM 10

typedef struct {
	char name[NM];
	int time;
} Queue;

int tail, head, sum_t;
Queue que[N];

void enqueue(Queue m);
Queue dequeue(void);
void initialize();

int main(void){
	int n, q, i;
	Queue temp;
	Queue *A = (Queue *)malloc(sizeof(Queue) * N);

	initialize();
	sum_t = 0;
	scanf("%d%d", &n, &q);
	for(i = 0; i < n; i++){
		scanf("%s%d", A[i].name, &A[i].time);
		enqueue(A[i]);
	}

	while(head != tail){
		temp = dequeue();
		if(temp.time <= q){
			sum_t += temp.time;
			printf("%s %d\n", temp.name, sum_t);
		}else{
			temp.time -= q;
			sum_t += q;
			enqueue(temp);
		}
	}

	return 0;
}

void initialize(){
	head = tail = 0;
}

void enqueue(Queue m){
	que[tail] = m;
	tail = (tail + 1) % N;
}

Queue dequeue(){
	Queue ret = que[head];

	head = (head + 1) % N;

	return ret;
}




Measured memory_bytes: 4116
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vec;
typedef vector<vec> mat;
/*Gauss_Jordan(2?????°???????????§???)
  O(n^3)
  Ax=b????§£??? A?????£?????????
  ?§£???????????¨??????????????????????????????
  ?§£???????????§????????¨?????????n+1??????????????????
  
  N???????????°??§M??????????¨???????????????´??????init?????????
  mat A(N,vec(M,0));
  vec B(N,0);
  gauss_jordan(A,B)
*/

vec gauss_jordan(const mat& A,const vec& b){
  int n=A.size();
  mat B(n,vec(n+1));
  vector<int> can(n,1);
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)B[i][j]=A[i][j]; //n*(n+1)?????????????????????

  for(int i=0;i<n;i++)B[i][n]=b[i]; //n???????????£??\

  for(int i=0;i<n;i++){
    int pivot=i;//?¬????????????¨??????????????????
    for(int j=0;j<n;j++)if(can[j] && B[j][i])pivot=j;//0??\??????1????????¢???
    swap(B[i],B[pivot]);//i??????????????£????????????
    if(B[i][i]==1)can[i] = 0;

    
    for(int j=0;j<n;j++){ //
      if(i!=j && B[j][i])//i??????-i?????????????????????
        for(int k=i;k<=n;k++)B[j][k]=B[j][k] ^ B[i][k];//i????????????i????????\??????0????????????
    }
  }
  vec x(n);
  for(int i=0;i<n;i++)x[i]=B[i][n];

  int many = 0;
  for(int i=0;i<n;i++){
    if(B[i][i] == 0) many = 1;
    if(B[i][i] == 0 && B[i][n] == 1) return vec();
  }
  if(many) return vec(n+1);
  return x;
}




mat Mult(mat A,mat B){
  assert(A[0].size() == B.size());
  int n = A.size(),m = B.size(),l = B[0].size();
  mat C(A.size(),vec(B[0].size(),0));

  for(int i=0;i<n;i++)
    for(int j=0;j<l;j++)
      for(int k=0;k<m;k++) C[i][j]^=(A[i][k]*B[k][j]);
 
  return C;
}

mat pow(mat X,int y){
  assert(X.size() == X[0].size());
  mat res(X.size(),vec(X[0].size()));
  for(int i=0;i<(int)res.size();i++) res[i][i] = 1;
  
  while(y){
    if(y%2) res = Mult(res,X);
    y/=2;
    X = Mult(X,X);

  }
  return res;
}



int main(){
  int n;
  cin>>n;
  mat A(n,vec(n));
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)cin>>A[i][j];
  
  vec B(n);
  for(int i=0;i<n;i++) cin>> B[i];
  
  int T;
  cin>>T;

  mat AT = pow(A,T);
  vec ans = gauss_jordan(AT,B);

  if(ans.empty()) cout<<"none"<<endl;
  else if(ans.size()>n) cout<<"ambiguous"<<endl;
  else {
  for(int i=0;i<(int)ans.size();i++){
    if(i)cout<<" ";
    cout<<ans[i];
  }
  cout<<endl;
  }
  return 0;
}

Measured memory_bytes: 5052
#include<iostream>
using namespace std;
main()
{
	int n;
	cin>>n;
	string s;
	cin>>s;int cou=0,cou1=0,ans1=0;
	for(int i=0;i<n;i++)
	{
		if(s[i]=='R')
		cou++;
	}
	for(int i=0;i<cou;i++)
	{
		if(s[i]=='R')
		{
			cou1++;
		}
	}
	cout<<cou-cou1<<endl;
}

Measured memory_bytes: 3708
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(_,v.size())cout<<" "<<v[_];cout<<endl;
#define show2d(v) rep(_,v.size()){rep(__,v[_].size())cout<<" "<<v[_][__];cout<<endl;}cout<<endl;
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 1e18+10 : 1e9+10;
int dx[]={0,1,0,-1,1,1,-1,-1};
int dy[]={1,0,-1,0,1,-1,1,-1};//RDLU

signed main(){
	int q;
	cin>>q;
	while(q--){
		vi in;
		vvi G(1010);
		vi co(1010);
		int t=-1;
		while(1){
			int a;
			cin>>a;
			if(!a)break;
			in.pb(a);
		}
		
		deque<int>de;
		rep(i,in.size()){
			if(in[i]>0){
				++t;
				co[t]=in[i];
				if(de.size()){
					int w=de.back();
					G[w].pb(t);
					G[t].pb(w);
					co[w]--;
					co[t]--;
				}
				de.pb(t);
			}else{
				int w=de[-1+de.size()+in[i]];
				int a=de.back();
				G[w].pb(a);
				G[a].pb(w);
				co[w]--;
				co[a]--;
			}
			while(!de.empty()){
				if(co[de.back()]==0)de.pop_back();
				else break;
			}
		}
		
		
		rep(i,1010)if(G[i].size()){
			cout<<i+1;
			sort(all(G[i]));
			rep(j,G[i].size())cout<<" "<<1+G[i][j];
			cout<<endl;
		}
	}
}











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

template<class Abel> struct UnionFind {
    vector<int> par;
    vector<int> rank;
    vector<Abel> diff_weight;

    UnionFind(int n = 1, Abel SUM_UNITY = 0) {
        init(n, SUM_UNITY);
    }
    //木の初期化
    void init(int n = 1, Abel SUM_UNITY = 0) {
         par.resize(n);//要素数1に初期化
         rank.resize(n);//ランク1に初期化
         diff_weight.resize(n);
        for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;
    }

    int root(int x) {
        if (par[x] == x) {
            return x;
        }
        else {
            int r=root(par[x]);
            diff_weight[x] += diff_weight[par[x]];//重みの累積和
            return par[x] = r;
        }
    }

    Abel weight(int x) {
        root(x);//経路圧縮
        return diff_weight[x];
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    //木の併合
    bool merge(int x, int y, Abel w) {
        w += weight(x); 
        w -= weight(y);
        x = root(x); 
        y = root(y);
        if (x == y) return false;
        //ランクが高い方を低いほうに繋げる
        if (rank[x] < rank[y]) swap(x, y), w = -w;
        //yのrootをxのrootに繋げる
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        //xがyの親になるのでxとyの差分を記録する
        diff_weight[y] = w;


        return true;
    }

    Abel diff(int x, int y) {
        return weight(y) - weight(x);
    }
};

int main() {
    int N, M;
    cin >> N >> M;
    UnionFind<int> uf(N);
    for (int i = 0; i < M; ++i) {
        int l, r, d;
        cin >> l >> r >> d;
        --l, --r;
        if (uf.issame(l, r)) {
            int diff = uf.diff(l, r);
            if (diff != d) {
                cout << "No" << endl;
                return 0;
            }
        }
        else {
            uf.merge(l, r, d);
        }
    }
    cout << "Yes" << endl;
}

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


using namespace std;
#define int long long
#define inf 99999999999999999
#define N 666666
int arr[N];
int sum1[N],sum2[N];
priority_queue <int,vector<int>,greater<int> > q1;//1 2 3
priority_queue <int,vector<int>,less<int> >q2;
signed main(){
	int n;
	cin>>n;
	for(int i=1;i<=n*3;i++){
		scanf("%lld",&arr[i]);
	}
	int tot=0;
	for(int i=1;i<=n;i++){
		tot+=arr[i];
		q1.push(arr[i]);
	}
	sum1[n]=tot;
	for(int i=n+1;i<=2*n;i++){
		int t=q1.top();
		if(arr[i]<=t){
			
		}
		else{
			tot+=abs(arr[i]-t);
			q1.pop();
			q1.push(arr[i]);
		}
		sum1[i]=tot;
	}
	
	
	tot=0;
	for(int i=3*n;i>=2*n+1;i--){
		tot+=arr[i];
		q2.push(arr[i]);
	}

	sum2[2*n+1]=tot;
	for(int i=2*n;i>=n+1;i--){
		int t=q2.top();
		if(arr[i]>=t){
			
		}else{
			tot-=abs(arr[i]-t);
			q2.pop();q2.push(arr[i]);
		}
		sum2[i]=tot;
	}
	/*for(int i=n;i<=2*n;i++) cout<<sum1[i]<<" ";
	cout<<'\n';
	for(int i=2*n+1;i>=n+1;i--) cout<<sum2[i]<<" ";
	cout<<'\n';*/
	int ans=-inf;
	for(int i=n;i<=2*n;i++){
		ans=max(ans,sum1[i]-sum2[i+1]);
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 10868
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

//試してて御免

const int cm = 1 << 17;
char ci[cm];
int cn;
inline char getcha() { 
	if (!cn) { fread(ci, 1, cm, stdin); cn = cm; }
	cn--;
	return ci[cm - cn - 1];
}

inline int getint() {
	int A = getcha() - '0';
	char C;
	while (isdigit(C = getcha())) {
		A = A * 10 + C - '0';
	}
	return A;
}


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


	int N, X;
	N = getint();
	X = getint();

	int A = 0;
	ll kotae = 0;
	rep(i, N) {
		int B = getint();
		if (A + B > X) {
			kotae += A + B - X;
			B = X - A;
		}
		A = B;
	}
	co(kotae);

	Would you please return 0;
}

Measured memory_bytes: 384
def solve(n, x, y):
    ans = [0] * n
    for i in range(1, n+1):
        for j in range(i+1, n+1):
            d = min(j-i, abs(y-j) + abs(x-i) + 1)
            ans[d] += 1
    return "\n".join(map(str, ans[1:]))

n, x, y = map(int, input().split())
print(solve(n, x, y))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
	#define PI 			acos(-1)
	#define mp			make_pair
	#define pb			push_back
	#define all(a)		(a).begin(), (a).end()
	#define srt(a)			sort(all(a))
	#define mem(a, h)	memset(a, (h), sizeof(a))
	#define f 			first
	#define s 			second
	#define MOD			1000000007
	int in(){int r=0,c;for(c=getchar();c<=32;c=getchar());if(c=='-') return -in();for(;c>32;r=(r<<1)+(r<<3)+c-'0',c=getchar());return r;}

	using namespace std;

	typedef long long 		ll;
	typedef unsigned long long 		ull;
	typedef pair<int, int>  ii;
	typedef vector<int>     vi;
	typedef vector<ii>      vii;
	typedef vector<ll>      vll;
	int main()
	{
		//ios::sync_with_stdio(false); cin.tie(0);
		//freopen("", "r", stdin);
		//freopen("", "w", stdout);
		int n;
		cin>>n;
		if(n>999)
			cout<<"ABD"<<endl;
		else
			cout<<"ABC"<<endl;
		return 0;
	}

Measured memory_bytes: 256
#include <string>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#define rep(i,n) for(int i = 0; i < (n); i++)
using namespace std;

int main()
{
    long long a, b, c, k;
    cin >> a >> b >> c >> k;
    long long  remain = k;
    long long ans = 0;
    if(remain - a <= 0){
        ans += remain * 1;
        cout << ans << endl;
        return 0;
    }else{
        ans += a * 1;
    }
    remain -= a;

    
    if(remain - b <= 0){
        cout << ans << endl;
        return 0;
    }
    remain = remain - b;

    if(remain - c <= 0){
        ans += remain * (-1);
        cout << ans << endl;
        return 0;
    }else{
        ans += c * (-1);
    }

    cout << ans << endl;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define hell 1000000007
#define fast ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
#define ll long long int
#define pi 3.1415926536
using namespace std;
/*ll dp[100001];
void digi()
{
	memset(dp,0,sizeof(dp));
	dp[1]=1;
	for(ll i=2;i<100001;i++)
	{
		count=0;
		ll x=i;
		while(x)
		{
			x/=10;
			count++;
		}
		if(count%2)
		dp[i]=dp[i-1]+1;
		else
		dp[i]=dp[i-1];
	}
}*/
void solve()
{ll t,n,k,x,y,z,d=0,p,q,l=INT_MAX,mini=0,prev;
  cin>>x>>y>>z;
  if(x-y>0)
  {
  	if(z-(x-y)>=0)
  	cout<<z-(x-y);
  	else
  	cout<<0;
  }
  else
  cout<<z;
}
 
int main()
{
  fast
ll t=1;
 
while(t--)
{solve();
 //cout<<ma<<endl;
}
return 0;}

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

int main() {
  int N, fx=0, n;
  cin >> N;

  n=N;
  for (int i = 0; i < 8; i++){
    fx += n % 10;
    n /= 10;
  }
  
  if(N % fx == 0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }

}

Measured memory_bytes: 3504
N = int(input())

row = 0
ans = 'No'

for n in range(N):
    D1, D2 = map(int, input().split())
    if D1==D2 and row<2:
        row+=1
    elif D1==D2 and row>=2:
        ans='Yes'
    else:
        row=0
print(ans)
        

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

using namespace std;
typedef long long ll;

#define out(ans) cout << ans << endl
#define in(n) cin >> n
#define floop(i, N) for (ll i = 0; i < N; i++)
#define floop1(i, N) for (ll i = 1; i <= N; i++)
#define floopi(i, j, N) for (ll j = i + 1; j < N; j++)

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;
}

constexpr int inf = 1e9;
constexpr ll linf = 1e18;

void solve();

int main()
{
    solve();
}

void solve()
{
    int r;
    in(r);
    out(r * r);
}

Measured memory_bytes: 256
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7
a.sort()

fac = [1] * (n + 1)
inv = [1] * (n + 1)
def COMinit():
    for j in range(1, n + 1):
        fac[j] = fac[j - 1] * j % mod

    inv[n] = pow(fac[n], mod - 2, mod)
    for j in range(n - 1, -1, -1):
        inv[j] = inv[j + 1] * (j + 1) % mod

def comb2(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod

COMinit()
ans = 0
for i in range(n):
    x = comb2(n-1-i, k-1)
    ans = (ans - a[i]*x % mod) % mod
    ans = (ans + a[-1-i]*x % mod) % mod
print(ans%mod)



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

typedef long long ll;
typedef pair<int, int> pi;

#define rep(i, n) for (int i = 0; i < n; i++)
#define rep_op(i, a, n) for (int i = a; i < n; i++)
#define rep_d(j, n) for (int j = n; j >= 0; j--)
#define rep_d_op(j, n, a) for (int j = n; j >= a; j--)

template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}

const int MOD = 1000000007;

const vector<int> dx = {1, 0};
const vector<int> dy = {0, 1};
const ll INF = 1LL << 60;

// int max = *max_element(vec.begin(), vec.end());
// int sum = accumulate(a.begin(), a.end(), 0);

int GCD(int a, int b) { return b ? GCD(b, a % b) : a; }

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

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    float sum = accumulate(a.begin(), a.end(), 0);

    int sel = 0;
    rep(i, n)
    {
        if (a[i] >= sum / (4 * m))
        {
            sel++;
        }
    }

    if (sel < m)
    {
        cout << "No" << endl;
    }
    else if (sel >= m)
    {
        cout << "Yes" << endl;
    }
}


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

int main()
{
   int n,k,sum=0;
   cin >> n >> k;
    vector<int> v(n);
   for (int i=0 ; i < n; i++){
       cin>>v[i]; 
   }

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

   for (int i=0; i<k; i++)
    sum += v[i];

    cout << sum <<endl;
    

}




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

using namespace std;
typedef long long ll;

int find(int u, vector<int> &fa){
    if(fa[u] == u)return u;
    return fa[u] = find(fa[u], fa);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> fa(n + 1);
    for(int i = 1; i <= n; ++i)
        fa[i] = i;
    int comp = n;
    while(m--){
        int x, y;
        cin >> x >> y;
        int u = find(x, fa);
        int v = find(y, fa);
        if(u != v){
            --comp;
            fa[u] = v;
        }
    }
    cout << comp - 1 << endl;
    return 0;
}


Measured memory_bytes: 3760
package main

import (
  "os"
  "fmt"
  "io/ioutil"
  "strings"
)

var (
  S string
  T string
)

func scan() {
  all, err := ioutil.ReadAll(os.Stdin)
  if err != nil {
    panic(err)
  }
  
  st := strings.Split(string(all), "\n")
  S = st[0]
  T = st[1]
}

func test() {
  Td := T[:len(T)-1]
  if S == Td {
    fmt.Println("Yes")
  } else {
    fmt.Println("No")
  }
}

func main() {
  scan()
  test()
}

Measured memory_bytes: 1756
#include<bits/stdc++.h>
using namespace std;
# ifdef DEB
# define debug(...) fprintf(stderr, __VA_ARGS__)
# else
# define debug(...)
#endif
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define LL long long
#define LD long double
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define pb pop_back
#define VI vector<int> 
#define VPI vector<PII> 
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define FORD(i,a,b) for(int i = (a); i >= (b); i--)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define ALL(x) (x).begin(), (x).end()
#define siz(V) ((int)V.size())

int n;
int T[30];
int A[30];

int main()
{
  ios_base::sync_with_stdio(0);
  cin>> n;
  for (int i = 0 ; i < 26; i++)
  {
    T[i] = 1000000;
  }
  for (int i = 0; i < n; i++)
  {
    string s;
    cin>> s;
    for (int j = 0 ; j < 30; j++)
    {
      A[j] = 0;
    }
    for (int j = 0; j < siz(s); j++)
    {
      A[(int)s[j] - (int)'a']++;
    }
    for (int j = 0; j < 26; j++)
    {
      T[j] = min(T[j], A[j]);
    }
  }
  for (int i = 0; i < 26; i++)
  {
    for (int j = 0; j < T[i]; j++)
    {
      cout<< (char)(i + (int)'a');
    }
  }
  cout<< "\n";
  return 0;
}

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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using pll = pair<ll,ll>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define REV(x) reverse(ALL((x)))
#define ASC(x) sort(ALL((x)))
#define DESC(x) ASC((x)); REV((x))
#define pb push_back
#define eb emplace_back

int main()
{
    ll N;
    cin >> N;
    vec H(N);
    REP(i,0,N) cin >> H[i];

    bool f = true, g = true;
    REP(i,1,N) {
        if(g) {
            if(H[i-1]-H[i] == 1) g = false;
            else if(H[i-1]-H[i] > 1) {
                f = false;
                break;
            }
        }
        else {
            if(H[i-1]-H[i] > 0) {
                f = false;
                break;
            }
            else if(H[i-1]-H[i] < 0) g = true; 
        } 
        
    }

    if(f) PR("Yes");
    else PR("No");

    return 0;
}

/*



*/

Measured memory_bytes: 3956
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
//#include <fstream>
using namespace std;

int main()
{
	const string w[] = { "apple", "peach" };
	const string t[] = { "_ALE_", "_PEH_" };
//	cut here before submit 
//	freopen("testcase.applepeach", "r", stdin);
	string str = "";
	int i;

	while (getline (cin, str ) ){
		if (str.empty() ){
			break;
		} // end if
//		vector <int> dot;
//		vector <int> camma;
		int i;
/*
		while ( str.find ('.') != string::npos ){
			dot.push_back ((int)str.find('.') );
			str.replace (str.find('.'), 1, " " );
		} // end while
		while ( str.find (',') != string::npos ){
			camma.push_back ((int)str.find(',') );
			str.replace (str.find (','), 1, " " );
		} // end while
*/
		// replace words
		for (i = 0; i < 2; ++i){
			while (str.find(w[i]) != string::npos ){
				str = str.replace (str.find(w[i]), w[i].length(),t[i] );
			} // end while
		} // end for

		// transform words
		for (i = 0; i < 2; ++i){
			while (str.find(t[i]) != string::npos ){
				str = str.replace (str.find(t[i]), t[i].length(),w[1-i] );
			} // end while
		} // end for
/*
		if (!dot.empty() ){
			for (i = 0; i < dot.size(); ++i){
				str = str.replace (dot[i], 1, "." );
			} // end for
		} // end if
		if (!camma.empty() ){
			for (i = 0; i < camma.size(); ++i){
				str = str.replace (camma[i], 1, "," );
			} // end for
		} // end if
*/
		cout << str << endl;
	} // end loop
		
	return 0;
}

Measured memory_bytes: 0
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

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

//qsort(str, n, sizeof(int), up_comp);
int up_comp(const void *a, const void *b){return *(int*)a - *(int*)b;}
int down_comp(const void *a, const void *b){return *(int*)b - *(int*)a;}
int int_sort( const void * a , const void * b ) {return strcmp(( char * )a , ( char * )b );}
int count_digit(int a){int i=0;while(a!=0){a=a/10;i++;}return i;}
int euclid( int a, int b ){int temp;if(a<b){temp=a;a=b;b=temp;}if(b<1)return -1;if(a%b==0) return b;return euclid(b,a%b);}

int main(void){
 
    int ans;
    char s[4];
    
    scanf("%s", s);
    
    if (!strcmp(s, "SUN")) {
        ans=7;
    } else  if (!strcmp(s, "MON")) {
        ans=6;
    } else if (!strcmp(s, "TUE")) {
        ans=5;
    } else if (!strcmp(s, "WED")) {
        ans=4;
    } else if (!strcmp(s, "THU")) {
        ans=3;
    } else if (!strcmp(s, "FRI")) {
        ans=2;
    } else if (!strcmp(s, "SAT")) {
        ans=1;
    }
    
    printf("%d", ans);
    
    return 0;
}



Measured memory_bytes: 1700
use std::io::*;
use std::str::FromStr;
 
/* 
The read function reads a string according to each one. 
*/
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

//main function
fn main() {
    let m:i64 = read();
    if m<1200{
	println!("ABC");
    }else if m<2800{
	println!("ARC");
    }else {
	println!("AGC");
    }
}


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

int main() {
    int N, K, R, S, P;
    string T;
    cin >> N >> K >> R >> S >> P >> T;

    map<char, int> points;
    points['r'] = P;
    points['s'] = R;
    points['p'] = S;
    vector<int> memory(N);

    ll ans = 0;
    rep(i, N) {
        if (i < K) {
            ans += points[T[i]];
            memory[i] = 1;
        } else {
            if (T[i - K] != T[i]
                || (i >= K * 2 && memory[i - K] == 0)) {
                ans += points[T[i]];
                memory[i] = 1;
            }
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 896
x,y = map(int,input().split(" "))

def gdp(x,y):
    if x > y:
        big = x
        small = y
    else:
        big = y
        small = x
    if big%small == 0:
        print(small)
        return
    else:
        gdp(small,big%small)

gdp(x,y)



Measured memory_bytes: 5600
#include <stdio.h>
#include <stdlib.h>
 
double calc(double dx1, double dy1, double dx2, double dy2) {
    dx1 = (dx1 == -0.0? 0.0: dx1);
    dy1 = (dy1 == -0.0? 0.0: dy1);
    dx2 = (dx2 == -0.0? 0.0: dx2);
    dy2 = (dy2 == -0.0? 0.0: dy2);
    if(dx1 == 0.0 || dx2 == 0.0) {
        return dx1 == dx2 || (dx1 == 0.0 && dy1 == 0.0) || (dx2 == 0.0 && dy2 == 0.0);
    }
    double result = (dy1/dx1) - (dy2/dx2);
    return result < 1e-7 && result > -1e-7 ;
}
 
int main() {
    int n, i;
    double x1, y1, x2, y2, x3, y3, x4, y4;
 
    scanf("%d", &n);
    for(i=0; i<n; ++i) {
        scanf("%lf %lf %lf %lf %lf %lf %lf %lf",
              &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4);
        if(calc(x2-x1, y2-y1, x4-x3, y4-y3)) {
            printf("YES\n");
        }else {
            printf("NO\n");
        }
    }
 
    return 0;
}


Measured memory_bytes: 2032
import math as mt
a,b,x = [int(i) for i in input().rstrip().split(' ')]
m = x/a
if m >= a*b/2:
    T = mt.degrees(mt.atan(2*(a*b - m)/(a*a)))
else:
    T = mt.degrees(mt.atan(b*b/m*0.5))
print(T)

Measured memory_bytes: 2940
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
#define INF 1000000000000000000

int main() {
    int N, K;
    cin >> N >> K;
    int R, S, P;
    cin >> R >> S >> P;
    string t;
    cin >> t;
    map<char, int> cnt;
    vector<bool> win_or_lose(N, false);
    cnt['r'] = 0;
    cnt['s'] = 0;
    cnt['p'] = 0;
    rep(i, N) {
        if (i <= K - 1)
            cnt[t[i]] += 1, win_or_lose[i] = true;
        else {
            if (t[i] == t[i - K] && win_or_lose[i - K])
                continue;
            else if (t[i] == t[i - K] && !win_or_lose[i - K])
                cnt[t[i]] += 1, win_or_lose[i] = true;
            else
                cnt[t[i]] += 1, win_or_lose[i] = true;
        }
    }

    int res = 0;
    for (auto p : cnt) {
        if (p.first == 'r')
            res += p.second * P;
        else if (p.first == 's')
            res += p.second * R;
        else if (p.first == 'p')
            res += p.second * S;
    }

    cout << res << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n)  for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define deb(x) cerr << #x <<": " << x << '\n';
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
typedef long double ld;
typedef long long ll;
int main(){
    ios;
	int n, x, t;
	cin >> n >> x >> t;
	int ans = ceil((double) n / (double) x);
	cout << ans * t;
    return 0;
}


Measured memory_bytes: 3640
def lcs(x, y, pre_lcs, pre_lcs_len):
    pm = dict((zip('ABCDEFGHIJKLMNOPQRSTUVWXYZ', [0] * 26)))
    for c in pm:
        for i, xc in enumerate(x):
            if c == xc:
                pm[c] |= (1 << i)
    
    V = (1 << len(x)) - 1
    rec = []
    
    for yc in y:
        V = ((V + (V & pm[yc])) | (V & ~pm[yc]))
        rec.append(bin(V)[-len(x):])
    
    lcs_len = bin(V)[-len(x):].count('0')
    
    if lcs_len > pre_lcs_len:
        rx = x[::-1]
        lcs = ''
        idx = 0
        for v, yc in zip(rec[::-1], reversed(y)):
            idx = v.find('0', idx)
            if yc == rx[idx]:
                lcs += yc
                if len(lcs) == lcs_len:
                    return (lcs[::-1], lcs_len)
                idx += 1
    else:
        return (pre_lcs, pre_lcs_len)

from sys import stdin

def solve():
    file_input = stdin
    ans_out = []
    for s in file_input:
        s = s.rstrip()
        if s[0] == '#':
            break
        s_len = len(s)
        sep = s_len // 2
        ans, ans_len = lcs(s[:sep], s[sep:], '', 0)
        while sep > ans_len:
            ans, ans_len = lcs(s[:-sep], s[-sep:], ans, ans_len)
            sep -= 1
            ans, ans_len = lcs(s[:sep], s[sep:], ans, ans_len)
        ans_out.append(ans)
    print(*ans_out, sep='\n')

solve()


Measured memory_bytes: 5604
#include <bits/stdc++.h>
#include<utility>
#include<algorithm>

#define pan(i,n) for(int i=0;i<n;i++)
#define pans(i,n,a) for(int i=a;i<n;i++)
#define ll long long int
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define INF 1e9+7
#define PI 3.141592653
#define inf 200007
#define P pair<ll,ll>

using namespace std;

ll ans = 1, arr[1007], gfg = 1e9+7;

void factorize(int n){
    int count =0;
    while(!(n%2)){
        n>>=1;
        count++;
    }
    if(count) arr[2]+=count;
    for (int  i = 3; i <= sqrt(n) + 2; i+=2)
    {
        count=0;
        while( n%i == 0 ){
            n/=i;
            count++;
        }
        // cout << i << " " << count << " " << n << endl;
        if(count) arr[i]+=count;
    }
    if(n>2) arr[n]+=1;
}

int main(){
    int n;
    cin>>n;
    // factorize(100);
    pans(i,n+1,1) factorize(i);
    pan(i, n + 1){
         ans=(ans*(arr[i]+1) + gfg)%gfg;
        // cout<<i<<" : "<<arr[i]<<endl;
    }
    cout<<ans;
}   

Measured memory_bytes: 256
N, M = list(map(int, input().split()))
cost = [None for _ in range(N)]
x = [None for _ in range(N)]
y = [None for _ in range(N)]
z = [None for _ in range(N)]
signums = [[1,1,1], [1,1,-1],[1,-1,1],[1,-1,-1],[-1,1,1],[-1,1,-1],[-1,-1,1],[-1,-1,-1]]
ans = 0
for i in range(N):
    x0, y0, z0 = list(map(int, input().split()))
    x[i] = x0
    y[i] = y0
    z[i] = z0

for sig in signums:
    count = 0
    for i in range(N):
        cost[i] = x[i] *sig[0] + y[i]*sig[1] + z[i]*sig[2]
    cost.sort(reverse=True)
    for i in range(M):
        count += cost[i]
    ans = max(ans, count)
print(ans)

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

int island[200000] = {0};

int main(void){
	int n, m;
	string ans = "IMPOSSIBLE";
	cin >> n >> m;
	for(int i=0; i<m; i++){
		int a, b;
		cin >> a >> b;
		if(a==1 || a==n) island[b-1]++;
		else if(b==1 || b==n) island[a-1]++;
	}
	for(int i=0; i<200000; i++) if(island[i]>=2) ans = "POSSIBLE";
	cout << ans << endl;
}

Measured memory_bytes: 1024
//
//  main.cpp
//  ABC169C2
#include <iostream>
#include <string>
using namespace std;
int main(int argc, const char * argv[]) {
    long long A,iB;
    string B;
    cin>>A>>B;
    iB=(B.at(0)-'0')*100+(B.at(2)-'0')*10+(B.at(3)-'0');
    
    cout<<A*iB/100<<endl;
    
    return 0;
}


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

using namespace std;
using ll = long long;

template<class T> inline void print(vector<T> arr) {
    cerr << "[";
    for(int i = 0; i < (int)arr.size(); i++)cerr << arr[i] << (i == (int)arr.size() - 1 ? "]" : ",");
    cerr << endl;
}


int n;
vector<vector<int>> hen;
vector<int> dist;
vector<int> par;
int nax = 0;

void dfs0(int v,int p, int dep) {
    par[v] = p;
    dist[v] = dep;
    for(auto i : hen[v]) {
        if(i == p)continue;
        dfs0(i, v, dep + 1);
    }
}

void dfs1(int v) {
    nax = max(nax, dist[v]);
    for(auto i : hen[v]) {
        if(i == par[v])continue;
        dfs1(i);
    }
}

int main()
{
    int u, v; cin >> n >> u >> v; u--, v--;
    hen.resize(n), dist.resize(n), par.resize(n);
    for(int i = 0; i < n - 1; i++) {
        int a, b; cin >> a >> b; a--, b--;
        hen[a].push_back(b);
        hen[b].push_back(a);
    }
    dfs0(v, -1, 0);
    int back = (dist[u] - 1) / 2;
    for(int i = 0; i < back; i++)u = par[u];
    dfs1(u);
    cout << (nax - 1) << endl;
}

Measured memory_bytes: 10368
#include <iostream>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <utility>
#include <string.h>
#include <map>
#include <stack>
#include <iomanip>
#include <chrono>
#include <random>
#include <math.h>
#include <time.h>
#include <bitset>
#include <assert.h>
#define rnd mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define pb push_back 
#define mp make_pair
#define ff first
#define ss second
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) x.begin(),x.end() 
#define PII pair <ll,ll>
#define N 100005
#define MOD 1000000007
#define INF 1000000000000000000
using namespace std;

int main()
{
	int n, m, A[N];
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	{
		cin >> A[i];
	}
	pair <int, int> p[N];
	for (int i = 0; i < m; ++i)
	{
		cin >> p[i].ss >> p[i].ff;
	}
	sort(A, A + n);
	sort(p, p + m);
	reverse(p, p + m);
	int l = 0;
	ll sum = 0;
	for (int i = 0; i < m; ++i)
	{
		int t = p[i].ss;
		while(l < n && t > 0 && A[l] < p[i].ff)
		{
			sum += p[i].ff;
			l++;
			t--;
		}
	}
	for (int i = l; i < n; ++i)
	{
		sum += A[i];
	}
	cout << sum;
}


Measured memory_bytes: 1408
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
l,r,d = readInts()
print(r//d - (l-1)//d)


Measured memory_bytes: 10388
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll, int> PL;
constexpr int mod = 1e9 + 7;
constexpr int INF = 2e9;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
 
  for (int i = a; i <= b * a; i++) {
    if (i % a == 0) {
      if (i % b == c) {
        cout << "YES" << endl;
        return 0;
      }
    }
  }
  cout << "NO" << endl;
  return 0;
} 

Measured memory_bytes: 3608
#include <assert.h>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using ll = long long;
using P = std::pair<ll, ll>;

#define rep(i, a, b) for (ll(i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cerr << "debug "<< i << std::endl

// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;

ll gcd(ll x,ll y){
  if(x%y==0)return y;
  else return gcd(y,x%y);
}

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  //問題文中の添え字が0-indexか1-indexか確認!

  ll t;
  std::cin>>t;

  rep(i,0,t){
    ll a,b,c,d;
    std::cin>>a>>b>>c>>d;

    if(b>a){
      std::cout<<"No\n";
      continue;
    }else if(b>d){
      std::cout<<"No\n";
      continue;
    }else if(c>=b){
      std::cout<<"Yes\n";
      continue;
    }

    ll g=gcd(b,d);
    if(b+(a%g)-g>c)std::cout<<"No\n";
    else std::cout<<"Yes\n";
  }

  return 0;
}


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

using namespace std;

#define Rep(i,a,b) for(ll i = a; i < b; ++i)
#define rep(i,b) Rep(i,0,b)
#define allof(a) (a).begin(), (a).end()

#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" : "IMPOSSIBLE")

using ll = long long;

constexpr int inf = 1e9 + 7;
constexpr ll infll = 1ll << 60ll;
constexpr ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

namespace {
    template<typename T> void chmax(T& a, T b) { a = std::max(a, b); }
    template<typename T> void chmin(T& a, T b) { a = std::min(a, b); }
    template<typename T> void chadd(T& a, T b) { a = a + b; }

    void Cout(long long x, const char* end = "\n") { std::cout << x << end; }
    template <typename T> void Cout(const T& x, const char* end = "\n") { std::cout << x << end; }
    template <typename T> void Cout(const std::vector<T>& x, const char* sep = " ", const char* end = "\n") { for (std::size_t i = 0, sz = x.size(); i < sz; i++) { std::cout << x[i] << (i == sz - 1 ? end : sep); } }

    // 標準入出力
    struct inp {
        std::size_t sz;
        inp(std::size_t _sz = 1) : sz(_sz) {}
        template <typename T> operator T () const { T a; std::cin >> a; return a; }
        template <typename T> operator std::vector<T>() const { std::vector<T> a(sz); for (std::size_t i = 0; i < sz; i++) std::cin >> a[i]; return a; }
    };

    // 2次元用の標準入出力
    template<typename T>
    struct inpn {
        std::size_t szi, szj;
        inpn(std::size_t _szi, std::size_t _szj) : szi(_szi), szj(_szj) {}
        operator std::vector<std::vector<T>>() const {
            std::vector<std::vector<T>> a(szi, std::vector<T>(szj));
            for (std::size_t i = 0; i < szi; ++i)
                for (std::size_t j = 0; j < szj; ++j) cin >> a[i][j];
            return a;
        }
    };

    inp inp1; // input one
}

int main() {

    int n, m;
    cin >> n >> m;

    chmin(n, 2 * m + 1);

    // 距離の重複をなくす
    // 輪なので2通りの距離があるが
    // 輪の半分だけで組み合わせを作ると一つの距離のみを考慮すればよい

    int ls = 1;
    int le = n / 2;
    int rs = n / 2 + 1;
    int re = n;

    if (le - ls == re - rs) {
        --le;
    }

    vector<pair<int, int>> ans;

    while (le - ls >= 1) {
        ans.emplace_back(ls++, le--);
    }
    while (re - rs >= 1) {
        ans.emplace_back(rs++, re--);
    }

    ans.resize(m);
    for (auto [x, y] : ans) {
        cout << x << " " << y << endl;
    }

    return 0;
}


Measured memory_bytes: 4324
from collections import Counter

n = int(input())
s = []
for _ in range(n):
    s.append(int(input()))
    
cnt = Counter([0, s[0]])

if len(s) > 1:
    for si in s[1:]:
        tmp = Counter([])
        for k,v in cnt.items():
            tmp[k + si] = v
            
        cnt += tmp

key_list = sorted(list(cnt.keys()), reverse=True)

for k in key_list:
    if k == 0:
        print(k)
        break
    
    elif k%10 == 0:
        continue
    
    print(k)
    break

Measured memory_bytes: 5388
#include <cstdio>

int main(){
    int H,W;
    for(;;){
        scanf("%d %d",&H,&W);
        if(H == 0 && W == 0){
            break;
        }

        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                printf("#");
            }
            printf("\n");
        }
        printf("\n");
    }
    
    return 0;
}


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


int main() {
    int n,c=0;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];

    for(int i=1;i<n-1;i++){
        if((a[i]<a[i-1] && a[i]>a[i+1]) || (a[i]>a[i-1] && a[i]<a[i+1]))
            c++;
    }
    cout<<c<<"\n";
}


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

pair<string, int> S[100000];
int cnt;

int main() {
	while (cin >> S[cnt].first >> S[cnt].second) {
		cnt++;
	}
	sort(S, S + cnt);
	for (int i = 0; i < cnt; i++) {
		if (i >= 1) {
			if (S[i].first == S[i - 1].first) {
				cout << ' ' << S[i].second;
			}
			else {
				cout << endl << S[i].first << endl << S[i].second;
			}
		}
		else {
			cout << S[i].first << endl << S[i].second;
		}
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 2788
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
#define INF 10000000000

int main() {
	long long n, index, cnt, ans = 0;
	vector<vector<long long>> table(0, vector<long long>(2));
	cin >> n;

	for (long long i = 2; i * i <= n; i++) {
		index = 0;
		while (n % i == 0) {
			index++;
			n /= i;
		}
		if (index) table.push_back({ i, index });
	}
	if (n != 1)table.push_back({ n, 1 });

	for (int i = 0; i < table.size(); i++) {
		cnt = 1;
		index = table[i][1];
		for (int j = 1; j <= index; j += cnt) {
			ans++;
			cnt++;
		}
	}

	cout << ans;
	return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define rep(i, n) for(int i= 0; i < (n); i++)
using ll= long long int;
using namespace std;
ll mod= 1e9 + 7;


int main(){
  int n,q;
  cin >> n>>q;
  int sub[n];//0-index
  sub[0]=0;
  string s;
  cin >>s;
  for(int i=1;i<n;i++){
    if(s[i-1]=='A' && s[i]=='C'){sub[i]=sub[i-1]+1;}else{sub[i]=sub[i-1];}
  }
  rep(i,q){
    int l,r;
    cin >> l >>r;
    cout << sub[r-1]-sub[l-1] << endl;
  }
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef long long int ll;

int main(){
    int n,q; cin >> n;
    ll sum=0LL;
    map<int,int> cnt; 
    vi a(n);
    for(int ix=0;ix<n;ix++){
        cin >> a.at(ix);
        sum += a.at(ix);
        cnt[a.at(ix)];
        cnt.at(a.at(ix))++;
    }
    cin >> q;
    vi b(q),c(q),diff(q);
    for(int ix=0;ix<q;ix++){
        cin >> b.at(ix) >> c.at(ix);
        diff.at(ix) = c.at(ix) - b.at(ix);
    }

    for(int ix=0;ix<q;ix++){
        if(cnt.count(b.at(ix))){
            sum += cnt.at(b.at(ix)) * diff.at(ix);
            cnt[c.at(ix)];
            cnt.at(c.at(ix)) += cnt.at(b.at(ix));
            cnt.at(b.at(ix)) = 0;
        }
        cout << sum << endl;
    }
}

Measured memory_bytes: 8564
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;

int main(){
    int n, m, x; cin >> n >> m >> x;
    vector<int> a(m);
    rep(i,m) cin >> a[i];
    int ans = 0;
    for(int i = x; i <= n; i++){
        rep(j,m){
            if(i == a[j]) ans++;
        }
    }
    int tmp = 0;
    for(int i = x; i>=0; --i){
        rep(j,m){
            if(i == a[j]) tmp++;
        }
    }
    ans = min(ans, tmp);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;

int c[5];// card

bool straight()
{
    if(c[4]==13 && c[3]==12 && c[2]==11 && c[1]==10 && c[0]==1)
        return true;
    for(int i=0; i<4; i++) {
        if(c[i+1] - c[i] != 1)
            return false;
    }
    return true;
}

int main(void)
{
    while(~scanf("%d,%d,%d,%d,%d", c, c+1, c+2, c+3, c+4)) {
        sort(c, c+5);
        if(c[0] == c[3] || c[1] == c[4]) {
            puts("four card");
        } else if((c[0] == c[2] && c[3] == c[4]) ||
                (c[0] == c[1] && c[2] == c[4])) {
            puts("full house");
        } else if(straight()) {
            puts("straight");
        } else if(c[0]==c[2] || c[1]==c[3] || c[2]==c[4]) {
            puts("three card");
        } else if((c[0]==c[1] && (c[2]==c[3] || c[3]==c[4])) ||
                (c[1]==c[2] && c[3]==c[4])) {
            puts("two pair");
        } else if(c[0]==c[1] || c[1]==c[2] || c[2]==c[3] || c[3]==c[4]) {
            puts("one pair");
        } else {
            puts("null");
        }   
    }


    return 0;
}

Measured memory_bytes: 1184