akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<bitset>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
const int maxn = 2e6+10;
struct node
{
    int l,r,id;
 
}t[maxn];
int a[maxn],cnt[maxn],res[maxn];
int ans,block;
int n,q;
bool cmp(node a,node b){  //按照奇偶性排序
    if( (a.l/block)==(b.l/block) ){  //当左端点位于同一个块时
        if( (a.l/block)%2 )  //左端点的块序号为奇数时
            return a.r<b.r;  //按照从小到大排
        else   //左端点的块序号为偶数时
            return a.r>b.r;   //按照从大到小排
    }
    else  //当左端点不位于同一个块时
        return a.l<b.l;  //按照块的位置进行排序
    //return (a.l/block)^(b.l/block) ? a.l<b.l : ( ((a.l/block)&1)?a.r<b.r:a.r>b.r );
}
void add(int x)
{
    cnt[x]++;
    if(cnt[x]==1)
        ans++;
}
void del(int x)
{
    cnt[x]--;
    if(!cnt[x])
        ans--;
}
int main()
{
    int l,r;
    scanf("%d",&n);
    scanf("%d",&q);
    block = sqrt(1.0*n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&t[i].l,&t[i].r);
        t[i].id = i;
    }
    sort(t+1,t+q+1,cmp);   //对查询排序
    l = t[1].l , r = t[1].l-1;
    ans = 0;
    for(int i=1;i<=q;i++)
    {
        while(l>t[i].l)  add(a[--l]);
        while(r<t[i].r)  add(a[++r]);
        while(l<t[i].l)  del(a[l++]);
        while(r>t[i].r)  del(a[r--]);
        res[t[i].id] = ans;
    }
    for(int i=1;i<=q;i++)
        printf("%d\n",res[i]);
    return 0;
}

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

//テストケースはあんまり見ないほうが良い。デバッグする能力が必要.
int main(){
    int n;
    cin >> n;
    string s,t;
    cin >> s >> t;
    rep(i,n){
        cout << s[i] << t[i];
    }
    cout << endl;
    return 0;
}

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

int main(){
  string S;
  cin >>S;

  int count =0;
  for(int i=0;i<4;i++){
    if(S.at(i)=='+'){
    count++;
    }
    else if(S.at(i)=='-'){
      count--;
    }
  }
  cout <<count << endl;
}


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

#define ASC(vec) vec.begin(), vec.end()		// 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend()	// 降順ソート 例:sort(DESC(vec));
#define rep(i, n) for(int i = 0; i < (n); i++)
#define Rep(i, n) for(int i = 1; i < n; i++)

const int mod = 1000000007;
const int inf = (int)1e9 + 7;
const long long INF = 1LL << 60;

using ii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vd = vector<double>;
using vb = vector<bool>;
using vl = vector<ll>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvb = vector<vector<bool>>;
using vii = vector<pair<int, int>>;

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

ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
ll LCM(ll a, ll b) { return (a * b) / GCD(a, b); }
int round_int(int a, int b) { return (a + (b - 1)) / b; }

// 素因数分解; 返り値は(素数, 乗数)のvector配列
vector<pair<ll, int>> factorize(ll n) {
	vector<pair<ll, int>> res;
	for (ll i = 2; i * i <= n; ++i) {
		if (n % i) continue;
		res.emplace_back(i, 0);
		while (n % i == 0) {
			n /= i;
			res.back().second++;
		}
	}
	if (n != 1) res.emplace_back(n, 1);
	return res;
}

constexpr array<int, 9> dx = { 0, 1, 0, -1, -1, 1, 1, -1, 0 };
constexpr array<int, 9> dy = { 1, 0, -1, 0, 1, 1, -1, -1, 0 };
constexpr auto MAX = 100000;

// ──────────────────────────────────────────────────────────────────

// UnionFind 解説：https://youtu.be/TdR816rqc3s?t=8424

struct UnionFind {
	vi d;
	UnionFind(int n = 0) : d(n, -1) {}

	int find(int x) {
		if (d[x] < 0) return x;
		return d[x] = find(d[x]);
	}

	bool unite(int x, int y) {
		x = find(x), y = find(y);

		if (x == y) return false;

		if (d[x] > d[x]) swap(d[x], d[x]);
		d[x] += d[y];
		d[y] = x;
		return true;
	}

	bool same(int x, int y) { return find(x) == find(y); }
	int size(int x) { return -d[find(x)]; }
};

int deg[100005];
vi to[100005];

int main() {
	int n, m, k;
	cin >> n >> m >> k;

	UnionFind uf(n);
	rep(i, m) {
		int a, b;
		cin >> a >> b;
		a--, b--;

		deg[a]++;
		deg[b]++;

		uf.unite(a, b);
	}

	rep(i, k) {
		int a, b;
		cin >> a >> b;
		a--, b--;

		to[a].push_back(b);
		to[b].push_back(a);
	}

	rep(i, n) {
		int ans = uf.size(i) - 1 - deg[i];
		for (int u : to[i]) {
			if (uf.same(i, u)) --ans;
		}
		printf("%d%c", ans, i == n - 1 ? '\n' : ' ');
	}
}

Measured memory_bytes: 7040
#include <bits/stdc++.h>
using namespace std;
#include<chrono>
#define ll long long
#define ld long double
#define eb emplace_back
#define pb push_back
#define mt make_tuple
#define tc  ll t; cin>>t; while(t--)
#define io ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
#define F first
#define S second
#define vi vector<ll>
#define pii pair<ll,ll>
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define vii vector<pair<ll,ll>>
ll gcd(ll n,ll m)
{
    if(n==0)
            return m;
    return gcd(m%n,n);
}
bool ifprime(ll n)
{
if(n==1)
return false;
    ll i;
for(i=2;i*i<=n;i++)
{
if(n%i==0)
return false;
 
}
return true;
}
void disp(vi v)
{
    for(auto u:v)
    cout<<u<<" ";
    cout<<"\n";
}
void remleadzero(vector<int> &v)
{
    vector<int> u;
    int i=0;
    while(v[i]==0)
        i++;
    while(i<v.size())
    {
        u.push_back(v[i]);
        i++;
    }
    v=u;
}
#define mod 1000000007LL
/*
void myscanf(long long *n)
{
    register long long c=getchar_unlocked();
    *n=0;
    for(;(c<48 ||c>57);c=getchar_unlocked())
        ;
    for(;(c>47 && c<58);c=getchar_unlocked())
    {
        *n=(*n<<1)+(*n<<3)+(c&15);
    }
 
}
void fastscan(long long &number)
{
    bool negative = false;
    register long long c;
 
    number = 0;
 
    c = getchar_unlocked();
    if (c=='-')
    {
 
        negative = true;
 
        c = getchar_unlocked();
    }
 
 
    for (; (c>47 && c<58); c=getchar_unlocked())
        number = number *10 + c - 48;
 
 
    if (negative)
        number *= -1;
}
*/
ll fast_expo(ll n,ll m, ll md)
{
    ll a=1;
    while(m>0)
    {
        if(m&1) a=(a*n)%md;
        n=(n*n)%md;
        m/=2;
    }
    return a%md;
}
long long sqroot(long long n){
    long double N = n;
    N = sqrtl(N);
    long long sq = N-2;
    sq = max(sq,0LL);
    while(sq*sq<n){
        sq++;
    } 
    if((sq*sq)==n)
        return sq;
    return -1;
}

int main()
{
    io;
    
    ll h;
    cin>>h;
    ll n = 1, ans=0;
    while(n*h>0){
        ans+=n;
        h/=2;
            n*=2;

        // cout<<h<<' ' <<ans<<'\n';
        // if(h<=0)
            // break;
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;

main() {
  int64_t h, w;
  cin >> h >> w;
  
  vector<vector<bool>> m(h);
  for (auto i : irange(0L, h)) {
    string s;
    cin >> s;
    for (auto c : s) {
      m[i].push_back(c == '#');
    }
  }
  
  vector<vector<int64_t>> a(h, vector<int64_t>(w));
  for (auto i : irange(0L, h)) {
    int64_t k = 0;
    for (auto j : irange(0L, w)) {
      if (m[i][j]) {
        k = 0;
      } else {
        ++k;
      }
      a[i][j] += k;
    }
    k = 0;
    for (auto j : irange(w - 1, -1L, -1L)) {
      if (m[i][j]) {
        k = 0;
      } else {
        ++k;
      }
      a[i][j] += k;
    }
  }
  for (auto j : irange(0L, w)) {
    int64_t k = 0;
    for (auto i : irange(0L, h)) {
      if (m[i][j]) {
        k = 0;
      } else {
        ++k;
      }
      a[i][j] += k;
    }
    k = 0;
    for (auto i : irange(h - 1, -1L, -1L)) {
      if (m[i][j]) {
        k = 0;
      } else {
        ++k;
      }
      a[i][j] += k;
    }
  }

  int64_t ans = 0;
  for (auto i : irange(0L, h)) {
    for (auto j : irange(0L, w)) {
      ans = max(ans, a[i][j]);
    }
  }
  
  cout << ans - 3 << endl;
}

Measured memory_bytes: 32256
#include<bits/stdc++.h>
using namespace std;
long double X[200100];
int N;
long long Count(long double len)
{
  long long Ans=0;
  for(int i=0;i<N;i++)
  {
    Ans+=(long long)(X[i]/len);//解答引っ張ってきた人の条件。なぜか通る
    //Ans+= ceil(X[i]/len)-1;//多少遅くなるがこっちが正解
  }
  return Ans;
}

int main()
	{
	  long long K;
	  cin>>N>>K;
	  for(int i=0;i<N;i++)
	{
		cin>>X[i];
		//X[i]-=0.1;
	}

  long double l=1,r=1e9;
  //while(l<r-0.1)//解答を引っ張ってきた人の条件。なぜかOKだったが、lとｒの整数部が異なる状態でループを出ると問題になるはず
	//for(int i=0;i<35;i++)//OK log2(10^9)=30.二分探索だとこのやり方安定する。ただし、浮動小数のせいか34以上でないと通らず。
  //while(!((ceil(r)-ceil(l)) == 0))//NG:左端が初期値0のままだと、右端のceilは0にならず、無限ループ
	while(!((floor(r)-floor(l)) == 0))//OK:右端がぴったり整数にならなければ成立.(あまりよくない)
  {
    long double mid=(l+r)/2;
    if(Count(mid)<=K) r=mid;
    else	l=mid;
  }
  cout<<(long long)(l+0.999)<<endl;
  return 0;
}


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

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<string> v(n);
    vector<vector<int>> vis(n, vector<int>(m, 0));
    vector<vector<int>> dis(n, vector<int>(m, 0));
    queue<pair<int,int>> q;
    for(int i = 0; i < n; i++) {
        cin >> v[i];
        for(int j = 0; j < m; j++) {
            if(v[i][j] == '#') {
                q.push({i, j});
                vis[i][j] = 1;
            }
        }
    }
    int ans = 0;
    while(q.size()) {
        pair<int,int> top = q.front();
        q.pop();
        int x = top.first, y = top.second;
        for(int k = 0; k < 4; k++) {
            int x_ = x + dx[k], y_ = y + dy[k];
            if(x_ >= 0 && x_ < n && y_ >= 0 && y_ < m && vis[x_][y_] == 0) {
                vis[x_][y_] = 1;
                q.push({x_,y_});
                dis[x_][y_] = dis[x][y] + 1;
                ans = max(ans, dis[x_][y_]);
            }
        }
    }
    cout << ans;
}


Measured memory_bytes: 17424
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		StringBuilder sb = new StringBuilder();
		for (int k = 0; k < n; k++) {
		    char[] arrA = sc.next().toCharArray();
		    char[] arrB = sc.next().toCharArray();
		    int a = arrA.length;
		    int b = arrB.length;
		    int[][] counts = new int[a + 1][b + 1];
		    for (int i = 1; i <= a; i++) {
		        for (int j = 1; j <= b; j++) {
		            if (arrA[i - 1] == arrB[j - 1]) {
		                counts[i][j] = counts[i - 1][j - 1] + 1;
		            } else {
		                counts[i][j] = Math.max(counts[i - 1][j], counts[i][j - 1]);
		            }
		        }
		    }
		    sb.append(counts[a][b]).append("\n");
		}
		System.out.print(sb);
	}
}



Measured memory_bytes: 64056
class Dice:
    
    def __init__(self,ls):
        self.a = ls[1-1] # top
        self.b = ls[2-1] # front
        self.c = ls[3-1] # right
        self.d = ls[4-1] # left
        self.e = ls[5-1] # back
        self.f = ls[6-1] # bottom
    
    def E(self):
        self.a, self.c, self.f, self.d = self.d, self.a, self.c, self.f
    def W(self):
        self.a, self.c, self.f, self.d = self.c, self.f, self.d, self.a
    def S(self):
        self.a, self.b, self.f, self.e = self.e, self.a, self.b, self.f
    def N(self):
        self.a, self.b, self.f, self.e = self.b, self.f, self.e, self.a   
                        
import random
ls = map(int,raw_input().split())
q = int(raw_input())
for i in range(q):
    dice = Dice(ls)
    a,b = map(int,raw_input().split())
    while dice.a != a or dice.b != b:
        i = random.choice([1,2,3,4])
        if i == 1: dice.E()
        elif i == 2: dice.W()
        elif i == 3 : dice.S()
        elif i == 4 : dice.N()
    print dice.c

Measured memory_bytes: 5408
li_word=["a","i","u","e","o"]
while True :
    num=int(input())
    if num==0:
        break
    else:
        li=[]
        for i in range(num):
            name=[]
            airport=list(input())
            for i in range (len(airport)):
                if i==0 or airport[i-1] in li_word:
                    name.append(airport[i])
            li.append(tuple(name))
        li_set=list(set(li))
        if len(li) != len(li_set):
            print(-1)
        else:
            a=0
            while True:
                a+=1
                check=[]
                for i in li:
                    check.append(i[:a])
                if len(check)==len(list(set(check))):
                    print(a)
                    break

Measured memory_bytes: 7788
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int range = scan.nextInt() * 2 + 1;

		int answer = 0;
		if (n % range == 0) {
			answer = n / range;
		} else {
			answer = n /range + 1;
		}
		System.out.println(answer);
	}
}

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

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N, X;
	int MAX_LEFT[200009], MAX_RIGHT[200009];
	int A[200009];
	cin >> N;
	for (int i = 1; i <= N; ++i) {
		cin >> A[i];
		if (i == 1) {
			MAX_LEFT[i] = A[i];
		} else {
			MAX_LEFT[i] = max(MAX_LEFT[i - 1], A[i]);
		}
	}
	MAX_RIGHT[N + 1] = -1e9;
	for (int i = N; i >= 1; --i) {
		if (i == N) {
			MAX_RIGHT[i] = A[i];
		} else {
			MAX_RIGHT[i] = max(MAX_RIGHT[i + 1], A[i]);
		}
	}
	for (int i = 1; i <= N; ++i){
		cout << max(MAX_LEFT[i - 1], MAX_RIGHT[i + 1]) << '\n';
	}
	return 0;
}

Measured memory_bytes: 3968
#include <cstdio>

template<class T>void fr(T &a) {
    T s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    a=w*s;
}
template<class T>T fr() {T a;fr(a);return a;}
#define R() fr<int>()

int book[5];

int main() {
	book[R()]=book[R()]=1;
	for(int i=1;i<=3;i++) if(!book[i])printf("%d\n",i);
	return 0;
}

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

using namespace std;

using ll = long long;
using p  = pair<ll, ll>;
constexpr ll INF = 1LL << 62;

int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll V[3];
    ll& A = V[0];
    ll& B = V[1];
    ll& C = V[2];
    ll K;
    cin >> A >> B >> C;
    cin >> K;
    
    sort(V, V + 3);
    cout << A + B + (C << K) << endl;
    
    return 0;
}


Measured memory_bytes: 256
while True:
    (n, x) = [int(i) for i in input().split()]
    if n == x == 0: break
    count = 0
    for i in range(1,n - 1):
        for j in range(i + 1 ,n):
            if i + j + j + 1 > x: break
            for k in range(j + 1 ,n + 1):
                if i + j + k == x:
                    count += 1
                    break
    print(count)

Measured memory_bytes: 6724
#include<cstdio>
#include<functional>
#include<algorithm>
using namespace std;
int main(void)
{
	int n,a,i,sum,x,mi;
	scanf("%d",&n);
	sum=0;	mi=999;
	for(i=1;i<=n;i++)	{
		scanf("%d",&a);
		sum+=a;
		x=sum/i;
		mi=min(mi,x);
	}
	printf("%d\n",mi);
	return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3


string solve(int l,string s,string t){
  ll n,m;
  n = s.size();
  m = t.size();
  ll maxc=0;
  rep(i,l+1){ // s i
    if(l-n*i>=0 && (l-n*i)%m==0){
      maxch(maxc,i);
    }
  }
  string res;
  rep(i,maxc)res+=s;
  while(res.size()<l)res+=t;
  return res;
}

int main(){
  ll l;
  string s,t;
  cin>>l>>s>>t;
  cout<<min(solve(l,s,t),solve(l,t,s))<<endl;
}


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

int main(){
  int n, a;
  cin >> n;
  vector<int>  b(n);
  for(int i=0;i<n;i++){
    b.at(i) = 0;
  }
  for(int i=0;i<n-1;i++){
    cin >> a;
    b.at(a-1)++;
  }
  for(int i=0;i<n;i++){
    cout << b.at(i) << endl;
  }
}

Measured memory_bytes: 4052
#include<bits/stdc++.h>
    using namespace std;
  #define int long long int
    #define endl "\n"
    #define MOD 1000000007
    #define mod 1000000007
    #define M 1000000007
    
    #define pb push_back
    #define take(a,b,c) for(int b=0;b<c;b++) cin>>a[b]
  //  #define mp make_pair
  #define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  #define mx 400005
  #define fiint(a,b) memset(a,b,sizeof(a))  
  #define bitcount __builtin_popcount
  #define fori(i,a,b) for(int i=a;i<b;i++)
  #define ford(i,a,b) for(int i=a;i>=b;i--)
  #define debug(x) cout<<x<<endl;
  #define cases(t) int t; cin>>t; while(t--)
  #define inf1 INT_MAX
  #define all(a) a.begin(),a.end()
  #define vec vector<int>
  #define pii pair<int,int>
  #define plii pair<int,int>
  #define pint pair<int,int>
  #define ff first
  #define ss second
  #define lb lower_bound
  #define ub upper_bound
  #define bs binary_search
  #define sz(x) (int)x.size()
#define PI                    3.14159265359

bool prime[10000001];

void sieveFunction(int maxLimit){
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1]=false;
    for(int i=2; maxLimit >= i ; i++){
        if(prime[i]){
            for(int j=2*i ; maxLimit >= j ; j+=i)
                prime[j]=false;
        }
    }
}

void add_self(int& a, int b) {
    a += b;
    if(a >= mod) {
        a -= mod;
    }
}

void sub_self(int& a, int b) {
    a -= b;
    if(a < 0) {
        a += mod;
    }
}

signed  main() 
{ 
	int n,k;cin>>n>>k;
	vec v(n+1);
	fori(i,1,n+1)cin>>v[i];
	vec dp(k+1);
	dp[0]=1;	
	fori(child , 1 , n+1)
	{
		vec temp(k+1);
			
		ford(used,k, 0  )
		{
			int  l=used + 1 ;
			int r = used + min(k-used , v[child]);
			if(l<=r)
			{	
				add_self(temp[l],dp[used]);
				if(r+1 <=k )
				sub_self(temp[r+1], dp[used]);
			}

		}
		int pre=0;
		fori(i,0,k+1)
		{
			add_self(pre,temp[i]);
			add_self(dp[i],pre);
		}	


	}
		cout<<dp[k]<<endl;

}

 


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

int main(){
  int n;
  cin >> n;
  long a[3*n], sumk[n+1];
  long nsum = 0;
  priority_queue<long, vector<long>, greater<long>> que;
  rep(i,n){
    cin >> a[i];
    que.push(a[i]);
    nsum += a[i];
  }
  sumk[0] = nsum;
  rep(i,n){
    cin >> a[n+i];
    que.push(a[n+i]);
    sumk[i+1] = sumk[i]+a[n+i]-que.top();
    que.pop();
  }
  nsum = 0;
  priority_queue<long> que2;
  rep(i,n){
    cin >> a[2*n+i];
    nsum += a[2*n+i];
    que2.push(a[2*n+i]);
  }
  long ans = sumk[n]-nsum;
  rep(i,n){
    que2.push(a[2*n-i-1]);
    nsum += a[2*n-1-i]-que2.top();
    ans = max(ans, sumk[n-1-i]-nsum);
    que2.pop();
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 8492
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<ll,ll> P;

void Main() {
  ll n;
  cin >> n;
  P a[n];
  rep(i,n) {
    ll x,d;
    cin >> x >> d;
    a[i]=P(x+d,x-d);
  }
  sort(a,a+n);
  ll ans=0;
  ll x=-MAXL;
  rep(i,n) {
    if(x<=a[i].S) {
      ans++;
      x=a[i].F;
    }
  }
  pr(ans);
}

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


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define int long long
#define uint unsigned int
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORR(i, a, b) for (int i = (a); i >= (b); --i)
#define ALL(a) (a).begin(), (a).end()
#define ALLR(a) (a).rbegin(), (a).rend()
#define SZ(a) ((int)(a).size())
#define PB(a) push_back(a)
#define EMP emplace
#define EMPB(...) emplace_back(__VA_ARGS__)
#define MP(a, b) make_pair(a, b)
#define MT(...) make_tuple(__VA_ARGS__)
#define Bit(n) (1LL << (n))
using namespace std;
using pii = pair<int, int>;
template <class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template <class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
const int MOD = 1000000007;
const int INF = 1LL << 30;
const double EPS = 1e-10;

int N, K;
int h[100010];

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> N >> K;
  REP(i, N) cin >> h[i];
  sort(h, h+N);
  int ans = INF;
  for (int i = 0; i+K <= N; i++) {
    chmin(ans, h[i+K-1]-h[i]);
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 1;

int par[MAX_N];
int ranks[MAX_N];
ll size[MAX_N];

void init(int n){
  for(int i = 0; i < n; i++) {
    par[i] = i; ranks[i] = 0; size[i] = 1;
  }
}

int find(int x){
  if(par[x] == x){
    return x;
  } else{
    int r = find(par[x]);
    return par[x] = r;
  }
}

void unite(int x, int y){
  x = find(x), y = find(y);
  if (x == y) return;
  if (ranks[x] < ranks[y]) swap(x, y);
  if (ranks[x] == ranks[y]) ranks[x]++;
  par[y] = x;
  size[x] += size[y];
}

bool same(int x, int y){
  return find(x) == find(y);
}

int main(){
  ll N, M;
  cin >> N >> M;
  int A[M+1], B[M+1];
  for(int i = 1; i <= M; i++) cin >> A[i] >> B[i];
  init(N+1);
  ll ans[M+1];
  ans[M] = (N*(N-1))/2;
  for(int i = M; i >= 1; i--){
    if(same(A[i],B[i])) ans[i-1] = ans[i];
    else{
      ans[i-1] = ans[i] - size[find(A[i])]*size[find(B[i])];
      unite(A[i], B[i]);
    }
  }
  for(int i = 1; i <= M; i++){
    cout << ans[i] << endl;
  }
  return 0;
}


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

using str = string;
using ss = stringstream;

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

    str s;cin>>s;
    int sz=s.size();

    if(s[sz-1]=='s')s+="es";
    else s+="s";

    cout<<s<<"\n";

    return 0;
}


Measured memory_bytes: 3648
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
#define int long long int
#define mod 1000000007
int function(string &str,int initial,int final,int memo[][4],int status)
{
	if(initial>final)
	{
		if(status==3)
		  return 1;
		else
		  return 0;
	}
	if(memo[initial][status]!=-1)
	{
		return memo[initial][status];
	}
	else
	{
		if(status==0)
		{
			int answer=0;
			if(str[initial]=='A')
			{
				answer+=function(str,initial+1,final,memo,status);
				answer+=function(str,initial+1,final,memo,status+1);
			}
			else if(str[initial]=='?')
			{
				answer+=function(str,initial+1,final,memo,status+1);
				answer+=3*function(str,initial+1,final,memo,status);
			}
			else
			{
				answer+=function(str,initial+1,final,memo,status);
			}
			answer=answer%mod;
			memo[initial][status]=answer;
			return answer;
		}
		else if(status==1)
		{
			int answer=0;
			if(str[initial]=='B')
			{
				  answer+=function(str,initial+1,final,memo,status+1);
				  answer+=function(str,initial+1,final,memo,status);
			}
			else if(str[initial]=='?')
			{
				answer+=function(str,initial+1,final,memo,status+1);
				answer+=3*function(str,initial+1,final,memo,status);
			}
			else
			{
				answer+=function(str,initial+1,final,memo,status);
			}
			answer=answer%mod;
			memo[initial][status]=answer;
			return answer;
		}
		else if(status==2)
		{
			int answer=0;
			if(str[initial]=='C')
			{
				answer+=function(str,initial+1,final,memo,status);
				answer+=function(str,initial+1,final,memo,status+1);
			}
			else if(str[initial]=='?')
			{
				answer+=function(str,initial+1,final,memo,status+1);
				answer+=3*function(str,initial+1,final,memo,status);
			}
			else
			{
				answer+=function(str,initial+1,final,memo,status);
		    }
			answer=answer%mod;
			memo[initial][status]=answer;
			return answer;
		}
		else
		{
			int answer=0;
			if(str[initial]=='?')
			{
				answer+=3*function(str,initial+1,final,memo,status);
				answer=answer%mod;
			}
			else
			{
				answer=answer+function(str,initial+1,final,memo,status);
				answer=answer%mod;
			}
			memo[initial][status]=answer;
			return answer;
		}
	}
}
int32_t main()
{
	string str;
	cin>>str;
	int n=str.size();
	int memo[n+1][4];
	int i,j;
	for(i=0;i<=n;i++)
	{
		for(j=0;j<4;j++)
		{
			memo[i][j]=-1;
		}		
	}
	int answer=function(str,0,n-1,memo,0);
	cout<<answer<<endl;
}


Measured memory_bytes: 11392
ABC = list(map(int,input().split()))
ABC.sort()
if ABC[0]%2 == ABC[1]%2:
    a = int((ABC[1]-ABC[0])/2)
    b = ABC[2] - ABC[1]
    print(a+b)
elif ABC[0]%2 == ABC[2]%2:
    a = int((ABC[2]-ABC[0])/2)
    b = int((ABC[2]+1-ABC[1])/2)
    print(a+b+1)
else:
    a = int((ABC[2]-ABC[1])/2)
    b = int((ABC[2]+1-ABC[0])/2)
    print(a+b+1)

Measured memory_bytes: 3064
from collections import deque
s=deque(input())
N=len(s)
A=[]
for i in range(N):
  a=s.popleft()
  if len(A)!=0:
    if A[-1]!=a:
      A.pop()
    else:
      A.append(a)
  else:
    A.append(a)
print(N-len(A))

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

long gcd(long n, long m) {
	if (n == 0)return m;
	if (n < m)swap(n, m);
	return gcd(n % m, m);
}

int main() {
	int a, p; cin >> a >> p;
	cout << (3 * a + p) / 2;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll      long long int   
#define ld      long double
#define pii     pair<int ,int>
#define pld     pair<ld ,ld>
#define all(v)  v.begin(),v.end()
#define F       first
#define S       second
#define mod     1000000007
#define pb      push_back
#define MP      make_pair
#define mset(x) memset(x, 0, sizeof(x));
#define ios     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define inf     1000000000000000007
const int N=300006;
ll n,k,ans,cnt,sz,i;
string s;
vector<ll>v;
void run(){
    cin>>n>>k;
    cin>>s;
    cnt=1;
    for(i=1;i<n;i++)
        if(s[i]==s[i-1]) cnt++;
        else v.pb(cnt),ans+=cnt-1,cnt=1;
    v.pb(cnt);
    ans+=cnt-1;
    sz=v.size();
    while(k--)
    {
        if(sz>=2) ans+=2,sz--;
        //else if(sz>=2) ans++,sz--;
        else break;
    } 
    ans=min(ans,n-1);
    cout<<ans;
}
 
 
void setup(){
    ios;
    //cout << setprecision(20);
    // #ifndef ONLINE_JUDGE
    // freopen("input", "r", stdin);
    // freopen("output", "w", stdout);
    // #endif
}
 
signed main(){
    setup();
    int tests = 1;
    //cin >> tests;
    for(int i = 1; i <= tests; i++) run();
    return 0;
}

Measured memory_bytes: 1480
#include <bits/stdc++.h>
#define VI vector<int>
#define VVI vector<vector<int>>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define MOD 1000000007
#define INF 1e18
#define All(x) (x).begin(), (x).end()
typedef long long ll;
using namespace std;

int main() {
  int K;
  cin >> K;
  ll sum = 0;
  for (int i = 1; i <= K;i++){
    for (int j = 1; j <= K;j++){
      for (int k = 1; k <= K;k++){
        sum +=__gcd(__gcd(i,j),k);
      }
  }
  }
  cout << sum << endl;

  return 0;
}

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


int main (){
	ll n;
	cin >> n;
	for(int i=1; i<=n; i++){
		ll z=2*i,jwb=0;
		for(int j=2; j<=sqrt(z); j++){
			for(int k=2; k*k+j*j<=z; k++){
				ll l=z-j*j-k*k;
				if(l>=4 && trunc(sqrt(l))==sqrt(l)){
					ll x=(j+k+sqrt(l))/2-sqrt(l),y=(j+k+sqrt(l))/2-k,z=(j+k+sqrt(l))/2-j;
					if(x>=1 && y>=1 && z>=1)jwb++;
				}
			}
		}
		cout << jwb << endl;
	}
	
}

Measured memory_bytes: 3664
using System;
class Program
{
  static void Main (string[] args)
  {
    int N = int.Parse(Console.ReadLine());
    double yen = 0.0;
    double btc = 0.0;
    for (int i = 0; i < N; i++) {
      string[] otoshidama = Console.ReadLine().Split(' ');
      if (otoshidama[1] == "JPY") {
        yen += double.Parse(otoshidama[0]);
      } else {
        btc += double.Parse(otoshidama[0]);
      }
    }
    Console.WriteLine(yen + (btc * 380000.0));
  }
}

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


int foo(int c[2][60][60], int y, int x){
	if(c[1][y][x] == 1) return 0;
	c[1][y][x] = 1;
	if(c[0][y][x] == 0) return 0;
	
	for(int i = -1; i <= 1; i++)
		for(int j = -1; j <= 1; j++)
			foo(c, y+i, x+j);
	
	return 1;
}

int main(){
	int h, w;
	
	while(1){
		int  c[2][60][60] = {}, count = 0;
		
		cin>>w>>h;
		
		if(w == 0 && h == 0) break;
		
		for(int i = 1; i <= h; i++)
			for(int j = 1; j <= w; j++)
				cin>>c[0][i][j];
		
		for(int i = 1; i <= h; i++)
			for(int j = 1; j <= w; j++)
				if(foo(c, i, j) == 1) count++;
				
		cout<<count<<endl;
	}
	return 0;
}


Measured memory_bytes: 3232
n, m = map(int, input().split())

list_k = list()
list_p = list()

for i in range(m):
    list_k.append(list(map(int, input().split())))

list_p = list(map(int, input().split()))

answer = 0

for i in range(2 ** n):
    # print(format(i, 'b').zfill(n))

    switch = format(i, 'b').zfill(n)[::-1]

    for idx, p in enumerate(list_p):
        check_k = list_k[idx][1:]

        target_switch = [switch[k - 1] for k in check_k]

        if target_switch.count('1') % 2 != p:
            break
    else:
        answer += 1

print(answer)


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

typedef long long int ll;
#define INF 1999999999
#define MODA 1000000007

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    if((s[0] == s[1] && s[1] == s[2]) || (s[1] == s[2] && s[2] == s[3]))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;



    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <string>
#include <set>

using namespace std;
typedef long long ll;

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n; cin >> n;
    string s; cin >> s;
    int unq = 1;
    for(int i = 1; i < s.size(); ++i){
        if(s[i] == s[i-1]) continue;
        else unq++;
    }

    cout << unq << "\n";
}

Measured memory_bytes: 512
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp38 {
    class Program {
        static void Main(string[] args) {
            var st = Console.ReadLine().Split(' ').ToArray();

            string X = st[0];
            string Y = st[1];

            var list = new List<string> { "A", "B", "C", "D", "E", "F" };

            if (list.IndexOf(X) < list.IndexOf(Y)) {
                Console.WriteLine("<");
            } else if (list.IndexOf(X) > list.IndexOf(Y)) {
                Console.WriteLine(">");
            } else {
                Console.WriteLine("=");
            }
            


        }
    }
}


Measured memory_bytes: 13152
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath> 
using namespace std;

int main(){
    int N;
    cin >> N;
    int a[10000];
    for(int i=0;i<N;i++)
        cin >> a[i];

    int count = 0;

    for(int i=0;i<N;i++){
        do{
            if(a[i]%2 == 0){
                a[i] = a[i]/2;
                count++;
            }
        }while(a[i]%2 == 0);
    }

    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<math.h>
#include<time.h>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<set>
#include<stack>
#include<queue>
#include<cstdlib>
#include<algorithm>
#include<random>
#include<cassert>
using namespace std;
#include<boost/multiprecision/cpp_int.hpp>
namespace boost_multiprecision = boost::multiprecision;
#define LL long long
#define CINT boost_multiprecision::cpp_int
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483648
#define INT_MAX 2147483647
#define LL_MIN -9223372036854775808
#define LL_MAX 9223372036854775807
#define segment_size 65536
#define ROOP() while(true)

int main(){
	string S;
	cin >> S;
	vector<pair<int,int>> a;
	a.push_back(make_pair(3,0));
	for(int i=0; i<S.size(); i++){
		int tmp;
		switch(S[i]){
		case 'J':
			tmp = 0;
			break;
		case 'O':
			tmp = 1;
			break;
		case 'I':
			tmp = 2;
			break;
		}
		if(a.back().first == tmp) a.back().second++;
		else a.push_back(make_pair(tmp,1));
	}
	int ans = 0;
	for(int i=1; i<a.size()-1; i++){
		if(a[i-1].first==0 && a[i].first==1 && a[i+1].first==2 
			&& a[i-1].second >= a[i].second && a[i+1].second >= a[i].second)
			ans = max(ans,a[i].second);
	}
	cout << ans << endl;
    return 0;
}


Measured memory_bytes: 12624
#include "bits/stdc++.h"
using namespace std;

#define fi first
#define se second
#define pb push_back
#define int long long
#define all(x) (x).begin(), (x).end()

using LL = long long;
using LD = long double;
using pii = pair<int, int>;
using vii = vector<pii>;

const int INF = 1e18;
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;

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

	string s;
	cin >> s;

	int ff = (s[0] - '0') * 10 + (s[1] - '0');
	int ss = (s[2] - '0') * 10 + (s[3] - '0');
	
	bool yymm = (1 <= ss and ss <= 12);
	bool mmyy = (1 <= ff and ff <= 12);

	if (yymm and mmyy) cout << "AMBIGUOUS\n";
	else if (yymm and !mmyy) cout << "YYMM\n";
	else if (!yymm and mmyy) cout << "MMYY\n";
	else cout << "NA\n";

    return 0;
}


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

const long long constant = (1e9 + 7);

long long getSum(vector<long long> arr)
{
    long long sum = 0;
    int len = int(arr.size());
    for(int i = len - 1; i >= 0; i--)
    {
        sum = (sum + ((2 * i - len + 1)%constant * arr[i])%constant)%constant;
    }
    return (sum + constant)%constant;
}


int main()
{
    int xNum, yNum;
    long long tmpX, tmpY;
    vector<long long> xArr;
    vector<long long> yArr;
    cin>>xNum>>yNum;
    while(xNum > 0)
    {
        cin>>tmpX;
        xArr.push_back(tmpX);
        xNum --;
    }
    while(yNum > 0)
    {
        cin>>tmpY;
        yArr.push_back(tmpY);
        yNum --;
    }
    long long sum = (getSum(xArr) * getSum(yArr))%constant;
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 3444
import java.util.Scanner;
import java.util.Objects;
import java.util.Arrays;

public class Main {

  public static void main(String[] args) {

    final Scanner scanner = new Scanner(System.in);

    final int N = scanner.nextInt();
    PlanEntry[] plan = new PlanEntry[N + 1];
    plan[0] = new PlanEntry(0, 0, 0);

    for (int i = 1; i <= N; i++) {
      plan[i] = new PlanEntry(scanner.nextInt(), scanner.nextInt(), scanner.nextInt());
    }

    for (int i = 0; i < N; i++) {
      if (!canTravel(plan[i], plan[i + 1])) {
        System.out.println("No");
        return;
      }
    }
    System.out.println("Yes");

  }
  public static boolean canTravel(final PlanEntry from, final PlanEntry to) {
    // distance
    final int dist = Math.abs(from.getX() - to.getX())
        + Math.abs(from.getY() - to.getY());
    if (dist > to.getTime() - from.getTime()) {
      return false;
    }
    // position
    return to.getTime() % 2 == (to.getX() + to.getY()) % 2;
  }

}
class PlanEntry {

  private int time;
  private int x;
  private int y;
  public PlanEntry(final int time, final int x, final int y) {
    this.time = time;
    this.x = x;
    this.y = y;
  }
  public int getTime() {
    return this.time;
  }
  public int getX() {
    return this.x;
  }
  public int getY() {
    return this.y;
  }
  @Override
  public String toString() {
    return "PlanEntry [time = " + this.time + ", x = " + this.x + ", y = " + this.y + "]";
  }
  @Override
  public boolean equals(final Object object) {
    if (object == null) {
      return false;
    }
    if (object == this) {
      return true;
    }
    if (!(object instanceof PlanEntry)) {
      return false;
    }
    final PlanEntry other = (PlanEntry) object;
    return Objects.equals(this.time, other.time)
        && Objects.equals(this.x, other.x)
        && Objects.equals(this.y, other.y);
  }
  @Override
  public int hashCode() {
    return Objects.hash(this.time, this.x, this.y);
  }

}


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

using namespace std;

template<typename T>
void in(T *a)
{
    for (int i = 0; i < sizeof(a)/sizeof(int); i++) {
        cin >> a[i];
    }
}

int main()
{
    int n;
    string s;
    int ans = 0;
    int cnt = 0;

    cin >> n >> s;

    for (int i = 0; i < n; i++) {
        if (s[i] == '.') {
            cnt++;
        }
    }

    ans = cnt;

    for (int i = 0; i < n; i++) {
        if (s[i] == '#') {
            cnt++;
        }
        else {
            cnt--;
        }
        if (cnt < ans) ans = cnt;
    }

    cout << ans << endl;
}


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

using namespace std;
using   ll=long long;

#define fast        	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define endl        	"\n"
#define pb          	push_back
#define mp          	make_pair
#define F           	first
#define S           	second
#define int             long long int
#define pll				pair<int , int>

#define ALL(v)      	v.begin(),v.end()
#define ALLR(v)     	v.rbegin(),v.rend()
#define pii         	3.14159265358979323
#define inf     		LLONG_MAX
#define ones(x)     	__builtin_popcount(x)
#define fill(a,b)   	memset(a,b,sizeof(a))
#define mod 			1000000007
#define hell            998244353 

ll mod_pow(ll a,ll b,ll m) 
{
    ll res = 1;
    while(b)	
    {
        if(b&1) 	
        {
        	res=(res*a) % m;
        }
        a=(a*a) % m;
        b>>=1;
    }
    return res;
}

ll mod_inverse(ll a) 
{
	return mod_pow(a , mod-2 , mod);
}

void solve() 
{
	int n;
	
	cin >> n;
	
	int a[n];
	
	int sum = 0;
	
	for(int i = 0; i < n; ++i) {
		cin >> a[i];
		
		sum += a[i];
	}
	
	int num = 0;
	
	for(int i = 1; i < n; i += 2) {
		num += a[i];
	}
	
	int seq[n];
	
	seq[0] = sum - 2*num;
	
	for(int i = 1; i < n; ++i) {
		int tm = a[i-1] - seq[i-1]/2;
		seq[i] = 2*tm;
	}
	
	for(int i = 0; i < n; ++i) {
		cout << seq[i] << " ";
	}
}

signed main() {
    fast;
    
    int t = 1;
    
	//cin >> t;
    
    while(t--) {
        solve();
    }
 
    return 0;
}


Measured memory_bytes: 5188
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr ll MOD = 1e9 + 7;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        if (a < b) {
            cout << "No" << endl;
            continue;
        }
        if (d < b) {
            cout << "No" << endl;
        } else {
            if (c >= b) {
                cout << "Yes" << endl;
            } else {
                ll p = a % b, q = __gcd(d % b, b) % b;
                if (q == 0) {
                    if (p > c) {
                        cout << "No" << endl;
                    } else {
                        cout << "Yes" << endl;
                    }
                    continue;
                }
                ll k = (c - p) / q + 1;
                if (p + k * q < b) {
                    cout << "No" << endl;
                } else {
                    cout << "Yes" << endl;
                }
            }
        }
    }
}

Measured memory_bytes: 256
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_C main
#include "bits/stdc++.h"
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LLONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using psi = pair<string, int>;
// functions

#endif


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

    int N, M; cin >> N >> M;
    vi A(M), B(M); 
    REP(i, M) {
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
    }

    vvi es(N);
    REP(i,M) {
        es[A[i]].push_back(B[i]);
        es[B[i]].push_back(A[i]);
    }

    queue<int> que;
    que.push(0);
    vb vis(N, false);
    vi dist(N, INF);
    dist[0] = 0;

    while(!que.empty()) {
        int x = que.front(); que.pop();
        vis[x] = true;

        for(int nx : es[x]) {
            if (vis[nx]) continue;

            dist[nx] = min(dist[nx], dist[x] + 1);
            que.push(nx);
        }
    }

    string ans = dist[N - 1] <= 2 ? "POSSIBLE" : "IMPOSSIBLE";
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 14832
# coding: utf-8
#-------------------------------------------------------------------
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------

N = int(input())

ans=a=b=ba=ab=0

for _ in range(N):
	s = input()
	ab+=s.count('AB')
	if (s[0]=='B')and(s[-1]=='A'): ba+=1
	if (s[0]=='B')and(s[-1]!='A'): b +=1
	if (s[0]!='B')and(s[-1]=='A'): a +=1

ans+=ab
ans+=max(0,ba-1)

#if (abs(a-b)>0)and(ba>0): ans+=1
if ba>0:
	if b>0:
		ans+=1
		b-=1
	if a>0:
		ans+=1
		a-=1

ans+=min(b,a)


print(ans)


p(a,b,ba,ab)



Measured memory_bytes: 3064
/*Function Template*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MAX = 510000;
const int MOD = 1e17;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define Rep(i, n) for(ll i = 1; i < (n); i++)
#define ALL(a)  (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll fac[MAX], finv[MAX], inv[MAX];


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;
}
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }

}
ll Len(ll n) {
  ll s=0;
  while(n!=0) s++, n/=10;
  return s;
}


ll Sint(ll n) {
  ll m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(ll i=s-1;i>=0;i--) m+=n/((ll)pow(10,i))-(n/((ll)pow(10,i+1)))*10;
  return m;
}


ll Svec(vector<ll> v){
  ll n=0;
  for(ll i=0;i<v.size();i++) n+=v[i];
  return n;
}


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


ll LCM(ll a,ll b){
  return a/GCD(a,b)*b;
}


ll Factorial(ll n){
  ll m=1;
  while(n>=1) m*=n,n--;
  return m;
}

void runlength(string s,vector<pair<char,ll>> &p){
  ll x=1;
  if(s.size()==1){
    p.push_back(pair<char,ll>(s[0],1));
  }
  for(ll i=0;i<s.size()-1;i++){
    if(s[i]==s[i+1]){
      x++;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[i],x));
      }
    }else{
      p.push_back(pair<char,ll>(s[i],x));
      x=1;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[s.size()-1],x));
      }
    }
  }
}




ll COM(ll n,ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

const int MAX_N=100010;
vector<bool> sieve_of_eratosthenes(){
  vector<bool> isPrime(MAX_N+1,true);
  for(int i=2;i<=MAX_N;i++){
    if(isPrime[i]){
      for(int j=2*i;j<=MAX_N;j+=i){
        isPrime[j]=false;
      }
    }
  }
  return isPrime;
}



/*↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓*/
int main() {
  IOS;
  ll n;
  cin>>n;
  vector<ll> v(n);
  rep(i,n) cin>>v[i];
  ll ans=MOD,tmp=v[0],sum=Svec(v)-v[0];
  rep(i,n-1){
    ans=min(ans,abs(tmp-sum));
    
    tmp+=v[i+1];
    sum-=v[i+1];
    
  }
  cout<<ans<<endl;
  
  
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
int main()
{
    string s;
    cin>>s;
    int q;cin>>q;
    string ans = s;
    string here = s;
    string front = "",back = "";
    int revc = 0,tc = 0;
    while(q--) {
        int t; cin>>t;
        if(t == 1) {
            revc++;
            tc++;
        }
        else {
            int f;string c;cin>>f>>c;
            if(f == 1) {
                if(tc % 2 == 0) {
                    front = c+front;
                }
                else {
                    back = back + c;
                }
            }
            else {
                if(tc % 2 == 0) {
                    back = back + c;
                }
                else {
                   front = c + front ;
                }
            }
        }
    }
    s = front + s+ back;
    if(tc % 2 == 0) {
        cout<<s<<endl;;
    }
    else {
        reverse(s.begin(),s.end());
        cout<<s<<endl;
    }
    return 0;
}

Measured memory_bytes: 1512