akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

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

long long lcm(long long a, long long b) {
  return a / gcd(a, b) * b;
}
//a x + b y = gcd(a, b)
long long extgcd(long long a, long long b, long long &x, long long &y) {
  long long g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}

long long invMod(long long a, long long mod) {
  long long x, y;
  if (extgcd(a, mod, x, y) == 1) { return (x + mod) % mod; }
  return 0;
}


int n, k;
const int MOD = 1000003;
ll dp1[2][1010][1010];
ll dp1sum[2][1010][1010];
ll dp2[1010];
ll dp3[1010];

int main() {
  while (scanf("%d %d", &n, &k), n|k)  {
    int rest = k >= n ? 2 : 0;
    k = min(k, n - 1);
    MEMSET(dp1, 0);
    MEMSET(dp1sum, 0);
    MEMSET(dp2, 0);
    MEMSET(dp3, 0);
    dp1[0][1][1] = 1;
    FOREQ(i, 2, n) {
      FOREQ(j, 1, k) {
        dp1[0][i][j] = (dp1[0][i][j] + dp1[0][i - 1][j - 1]) % MOD;
        dp1[1][i][j] = (dp1[1][i][j] + dp1[1][i - 1][j - 1]) % MOD;
        dp1[0][i][1] = (dp1[0][i][1] + dp1[1][i - 1][j]) % MOD;
        dp1[1][i][1] = (dp1[1][i][1] + dp1[0][i - 1][j]) % MOD;
      }
    }
    FOREQ(i, 1, n) {
      FOREQ(j, 1, n) {
        dp1sum[0][i][j] = (dp1sum[0][i][j - 1] + dp1[0][i][j]) % MOD;
        dp1sum[1][i][j] = (dp1sum[1][i][j - 1] + dp1[1][i][j]) % MOD;
      }
    }
    FOREQ(i, 1, n) {
      FOREQ(j, 1, k) {
        dp2[i] = (dp2[i] + dp1[1][i][j]) % MOD;
      }
      FOREQ(p, 1, k) {
        if (i - p <= 0) { break; }
        dp2[i] = (dp2[i] + dp1sum[1][i - p][k - p]) % MOD;
      }
      dp2[i] = (dp2[i] * 2) % MOD;
    }
    FOREQ(i, 1, n) {
      int lsum = 0;
      FOR(d, 2, i) {
        if (i % d != 0) { continue; }
        lsum = (lsum + dp3[d]) % MOD;
      }
      dp3[i] = (dp2[i] - lsum + MOD) % MOD;
    }
    ll ans = rest;
    FOREQ(i, 2, n) {
      if (n % i != 0) { continue; }
      ans = (ans + dp3[i] * invMod(i, MOD)) % MOD;
    }
    printf("%lld\n", ans);
  }
}

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

typedef long long ll;
typedef long double ld;

int niz[100005];

int main(){
    ios_base::sync_with_stdio(false);
    cout.precision(10);
    cout<<fixed;

    int n, x;
    cin >> n >> x;
    for(int i=1; i<=n; i++) cin >> niz[i];
    n++;
    niz[n] = x;
    sort(niz+1, niz+1+n);
    int nzd = 0;
    for(int i=1; i<n; i++){
        nzd = __gcd(nzd, niz[i+1]-niz[i]);
    }
    cout << nzd;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <cmath>
int main()
{
	int n = 0, d = 0;

	std::cin >> n >> d;

	int count = 0;
	for (int i = 0; i < n; ++i)
	{
		int p = 0,q = 0;
		std::cin >> p >> q;
		unsigned long long lpp = std::abs(p);
		lpp = lpp * lpp;
		unsigned long long lqq = std::abs(q);
		lqq = lqq * lqq;
		unsigned long long ldd = std::abs(d);
		ldd = ldd * ldd;
		if (lpp+lqq <= ldd)
		{
			count++;
		}
	}
	std::cout << count << std::endl;
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

const int MOD = 1000000007;

int N, A[101];
ll mn = 1e18, sum = 0;

void search(bitset<101> bad, int x) {
    if (3*x > N) {
        for (int i = N/3+1; i <= N; ++i) if (!bad[i]) {
            if (2*i > N) {
                if (A[i] < 0) bad[i] = 1;
            } else {
                if (bad[2*i]) {
                    if (A[i] < 0) bad[i] = 1;
                } else if (A[i] < 0 && A[i]+A[2*i] < 0) bad[i] = bad[2*i] = 1;
            }
        }
        ll tmp = 0;
        FOR(i,1,N+1) if (bad[i]) tmp += A[i];
        mn = min(mn,tmp);
        return;
    }
    search(bad,x+1);
    if (!bad[x]) {
        for (int i = x; i <= N; i += x) bad[i] = 1;
        search(bad,x+1);
    } 
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> N;
	FOR(i,1,N+1) {
	    //A[i] = 1;
	    cin >> A[i];
	    sum += A[i];
	}
	search(bitset<101>(),1);
	cout << sum-mn;
}

// read!
// ll vs. int!

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
long long fac(ll a){
    long long ans=1;
    while(a>1){
        ans*=a;
        a--;
    }
    return ans;
}
int main(){
    ll n,m;
    cin >> n >> m;
    ll ans;
    ans = ((100*(n-m))+1900*m)*pow(2,m);
    cout << ans << endl;
}


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


signed main()
{

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

    int s;
    cin>>s;

    if(s==1e18)
    {
        int zz=1e9;
        cout<<0<<" "<<0<<" "<<zz<<" "<<0<<" "<<1<<" "<<zz;
        return 0;
    }
    
    vector<int>ans;
    ans.push_back(0);
    ans.push_back(0);

    if(s<=1e9)
    {
        ans.push_back(0);
        ans.push_back(1);
        ans.push_back(s);
        ans.push_back(1);
    }
    else
    {
        int mod=1e9;
        int z=s/mod;
        int rem=s%mod;
        ans.push_back(mod);
        ans.push_back(mod-rem);
        ans.push_back(1);
        ans.push_back(z+1);
    }

    for(auto i:ans)
        cout<<i<<" ";
}

Measured memory_bytes: 256
n = int(input())
A = [201]+list(map(int,input().split()))+[99]
maxp = 0
minp = A[0]
money = 1000
stock = 0
for i in range(n+1):
  if A[i] >= A[i+1] and A[i]>minp:
    money = (money//minp)*A[i]+money%minp
    minp = A[i+1]
  minp = min(minp,A[i+1])
print(money)
  

Measured memory_bytes: 61712
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<(n); i++)
long long a[110][110];
long long b[110][110];
long long c[110][110];
int main(){
    int n, m, l;
    cin >> n >> m >> l;
    rep(i, n){
        rep(j, m){
            cin >> a[i][j];
        }
    }
    rep(i, m){
        rep(j, l){
            cin >> b[i][j];
        }
    }
    rep(i, n){
        rep(j, l){
            rep(k, m){
                c[i][j] += a[i][k]*b[k][j];
            }
            cout << c[i][j];
            if (j != l-1) cout << " ";
            else cout << endl;
        }
    }
}


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

int main(void){
    string S, T;
    cin >> S;
    cin >> T;
    int res = 0;
    for(int i=0; i<S.size(); i++){
        if(S[i]!=T[i])res++;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3828
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("-ffloat-store")
 
#define int  long long
#define rep(i,begin,end) for(__typeof(end)i=(begin)-((begin)>(end));i!=(end)-((begin)>(end));i+=1-2*((begin)>(end)))
#define F first
#define S second
#define sz(x) ((int)x.size())
#define pb push_back
#define pf push_front
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define mod 1000000007
#define what_is(x) cerr << #x << " is " << x <<"\n";
#define sortA(v) sort(v.begin(), v.end())
#define sortD(v) sort(v.rbegin(), v.rend())
#define PI 3.14159265358979323846
#define vout(a) for(auto x:a) cout<<x<<" ";
#define INF (int)(2e18) //1e16
#define oset tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
 
 
using namespace __gnu_pbds;
using namespace std;
 
using ll  = long long;
using vi  = vector<int>;
using vvi = vector<vi>;
using pii = pair<int,int>;
using vii = vector<pii>;
using mi  = multiset<int>;
using mii = multiset<pii>;
using ld  = long double;
 
int lcm(int a,int b) {return (a*(b/__gcd(a,b)));}



void solve()
{
    int n,m,t,i,k,l,r,s,u,v,w,j,pos,sum=0,flag=0,count=0;
    string S,T; 
    // int a,b,da,db;
    cin>>n;
  t=!n;
  cout<<(t);
}


signed main()
{
    #ifndef ONLINE_JUDGE 
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
    {
        solve();
        if(t)cout<<"\n";
    }
    return 0;
}

Measured memory_bytes: 3648
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <random>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int main() {
    int n; cin >> n;
    vector<ll> v(n);
    rep(i,n) cin >> v[i];
    sort(v.begin(), v.end());
    double ans = 0;
    ll cnt = 2;
    for (int i = 2; i < n; i++)
    {
        v[i] *= cnt;
        cnt *= 2;
    }
    rep(i,n) {
        ans += (double) v[i] / cnt;
    }
    cout << setprecision(12) << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        
        // 数値の取得
        
        Scanner scn = new Scanner(System.in);
        int i = scn.nextInt();
        scn.close();
        
        int x = i % 10;
        
        if(x == 3) {
            System.out.println("bon");
        } else if(x == 2 || x == 4 || x == 5 || x == 7 || x == 9) {
            System.out.println("hon");
        } else {
            System.out.println("pon");
        }
    }
}

Measured memory_bytes: 35608
from math import factorial

mod=10**9+7

def cmb(n, r):
    if n-r<0:
        return 0
    else:
        return factorial(n) // factorial(r) // factorial(n - r)

n,k=map(int,input().split())


for i in range(1,k+1):
    print(((cmb(n-k+1,i)%mod)*(cmb(k-1,i-1)%mod))%mod)

Measured memory_bytes: 3316
#include<stdio.h>

int minof(int min, int x) {
  min = (min < x) ? min:x;
  return min;
}

int slove(int, int);
int slove(int a, int b) {
  int i, j, k, l, o, p, min, temp, d[4] = {}; 
  min = 268435456; 
  for(i = 1; i * i <= a; i += 1) {
    if(a % i == 0) {
      for(k = 1; k * k <= b; k += 1) {
        if(b % k == 0) {
          j = a / i;
          d[0] = i;
          d[1] = j;
          l = b / k;
          d[2] = k;
          d[3] = l;
          for(o = 0; o < 3; o += 1) {
            for(p = 3; p >= o; p -= 1) {
              if(d[p] < d[p - 1]) {
               temp = d[p];
               d[p] = d[p - 1]; 
               d[p - 1] = temp;
              };  
            };  
          };  
          min = minof(min, (d[1] - d[0]) * (d[1] - d[0]) + (d[2] - d[1]) * (d[2] - d[1]) + (d[3] - d[2]) * (d[3] - d[2]));
        };  
      };  
    };  
  };  
  return min;
}

int main() {
  int a, b;

  while(1) {
    scanf("%d %d", &a, &b);
    if(a == 0 && b == 0) {
      break;
    };  
    printf("%d\n", slove(a, b));
  };

  return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;

int main(void) {
  int N, K;
  cin >> N >> K;

  vector<ll> a(N), accum(N), paccum(N, 0);
  for(int i = 0; i < N; i++) {
    cin >> a[i];
    if (i == 0) {
      accum[0] = a[0];
      if (a[0] > 0)
        paccum[0] = a[0];
    } else {
      accum[i] = a[i] + accum[i-1];
      if (a[i] > 0)
        paccum[i] = a[i] + paccum[i-1];
      else
        paccum[i] = paccum[i-1];
    }
  }

  ll ans = 0;
  for (int i = 0; i <= N - K; i++) {
    ll mid = accum[i+K-1];
    if (i > 0)
      mid -= accum[i-1];

    ll left = 0, right = 0;
    if (i > 0)
      left = paccum[i-1];

    if (i + K < N)
      right = paccum[N-1] - paccum[i+K-1];

    ans = max(ans, mid + left + right);
    ans = max(ans, left + right);
  }

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

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i < (n+1); ++i)
using namespace std;
using ll = long long;
const int INF = -100100100;
typedef pair<int,int> P;

int main(){
    string c,s;
    cin >> s;
    c = "coffee";
    bool ans = false;
    if(s[2]==s[3]&&s[4] == s[5])ans=true;
    if(ans){
        cout<< "Yes"<<endl;
        return 0;
    }else{
        cout << "No"<<endl;
        return 0;
    }
}

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

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

using namespace std;

int main(){
  int m, d;cin>>m>>d;
  int result=0;
  rep(i, m)rep(j, d){
    if((j+1)%10<2 || (j+1)/10<2)continue;
    if( ( ((j+1)%10)*((j+1)/10) )==( i+1 ) )result++;
//    if( ( ((j+1)%10)*((j+1)/10) )==( i+1 ) )cout<<i+1<<' '<<j+1<<endl;
  }

  cout<<result<<endl;

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
long long n,m;
char a[110][110];
using namespace std;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			cout<<a[i][j];
		cout<<endl;
		for(int j=1;j<=m;j++)
			cout<<a[i][j];
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int n,f[100005],h[100005];
int main()
{
    cin>>n;
    for (int i=1;i<=n;++i)
        cin>>h[i];
    for (int i=1;i<=n;++i)
        f[i]=1e9;
    f[1]=0;
    f[2]=abs(h[2]-h[1]);
    for (int i=3;i<=n;++i)
        f[i]=min(f[i-1]+abs(h[i]-h[i-1]),f[i-2]+abs(h[i]-h[i-2]));
    cout<<f[n];
}

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

#define int long long
#define fi first
#define se second
#define otp(n) cout << n;
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define ctv(v) rep(i,(v).size()) ct(v[i])
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define repv(i,v) for(int i=0;i<(v).size();i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define pb(n) push_back(n);

int n,k,h[100000],dp[100000];

main() {
    cin >> n >> k;
    rep(i,n) {
        cin >> h[i];
        dp[i] = 1000000000000000000;
    }
    dp[0]=0;
    rep(i,n-1) {
        repo(j,i+1,min(n,i+k+1)) {
            dp[j] = min(dp[j],dp[i]+abs(h[i]-h[j]));
        }
    }
    ct(dp[n-1])
}


Measured memory_bytes: 1792
N, K = map(int, input().split())
A = list(map(lambda x: int(x) - 1, input().split()))

done = [-1]*N
done[0] = 0

tmp = 0
done[0] = 0
for k in range(1, K + 1):
    tmp = A[tmp]
    if done[tmp] >= 0:
        for _ in range((K - done[tmp]) % (k - done[tmp])):
            tmp = A[tmp]
        print(tmp + 1)
        exit()
    else:
        done[tmp] = k
print(tmp + 1)

Measured memory_bytes: 32368
use proconio::{
   fastout, input,
   marker::{Bytes, Chars, Isize1, Usize1},
};

#[fastout]
fn main() {
   input! {
      n:usize,
      a:[usize;n+1]
   }
   let n = n + 1;
   if n == 1 && a[0] == 1 {
      println!("1");
      return;
   }
   if a[0] != 0 {
      println!("-1");
      return;
   }
   let mut max = vec![0_usize; n];
   for i in (0..n).rev() {
      if i == n - 1 {
         max[i] = a[i];
      } else {
         max[i] = max[i + 1] + a[i];
      }
   }
   let mut ans = vec![0_usize; n];
   ans[0] = 1;
   for i in 1..n {
      if ans[i - 1] < a[i - 1] {
         println!("-1");
         return;
      }
      ans[i] = std::cmp::min((ans[i - 1] - a[i - 1]) * 2, max[i]);
   }
   if ans[n - 1] != a[n - 1] {
      println!("-1");
      return;
   }
   //dbg!(&ans, &max);
   println!("{}", ans.iter().sum::<usize>());
}


Measured memory_bytes: 5228
#include<stdio.h>

int main(){
  
  int i,k,n;
  char s[1000];
  
  scanf("%d",&k);
  scanf("%s",s);
  
  for(n = 0; s[n] != '\0'; n++){
    //printf("%c",s[n]);
  }
  
  if(n <= k){
    printf("%s\n",s);
  }else{
    for(i = 0; i < k; i++){
      printf("%c",s[i]);
    }
    printf("...\n");
  }
  
  return 0;
        
}

Measured memory_bytes: 1660
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
n = int(input())
graph = [[] for _ in range(n)]
for i in range(1, n):
    graph[int(input()) - 1].append(i)


def dfs(x):
    arr = [dfs(y) for y in graph[x]]
    if not (arr):
        return 0
    arr.sort(reverse=True)
    return max(i + a for i, a in enumerate(arr, 1))

print(dfs(0))


Measured memory_bytes: 230448
#include <bits/stdc++.h>
#ifdef DBP
#define deb(...) fprintf(stderr,__VA_ARGS__)
#else
#define deb(...) 0
#endif
#define fst first
#define snd second
#define fore(x,a,b) for(int x=(a), qwerty=(b); x<qwerty; x++)
#define pb push_back
#define mset(a,v) memset((a),(v),sizeof(a))
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) int((a).size())
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;

const int N=1e5+5;
string s;
int n,m,A[N],B[N],P[N],sum[N];

int find(int u){return u==P[u]?u:P[u]=find(P[u]);}
void join(int i, int j){
    int x=find(i), y=find(j);
    if(x!=y){
        sum[x] += sum[y];
        P[y] = x;
    } 
}

int main(){FIN;
    cin >> s >> m;n=SZ(s);
    fore(x,0,n)A[x+1]=s[x]-'a';
    fore(x,0,n+1)B[x]=(A[x+1]-A[x]+26)%26;
    fore(x,0,n+1)P[x]=x,sum[x]=B[x];
    fore(x,0,n+1)join(x,n-x);
    fore(x,0,m){
        int a,b;cin>>a>>b;a--;
        join(a,b);
    }
    bool can = 1;
    fore(x,0,n+1)if(find(x)==x)can &= sum[x]%26 == 0;
    cout << (can ? "YES":"NO")<<"\n";
}

Measured memory_bytes: 2000
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using VI = vector<int>;
const int INF = 1e9;
const int MXN = 0;
const int MXV = 0;
const LL MOD = 998244353;
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FOR(i, L, R) for (int i = L; i < (int)R; ++i)
#define FORD(i, L, R) for (int i = L; i > (int)R; --i)
#define IOS                                                                    \
    cin.tie(nullptr);                                                          \
    cout.tie(nullptr);                                                         \
    ios_base::sync_with_stdio(false);

int main()
{
    IOS;
    int n, s;
    cin >> n >> s;
    vector<LL> a(n + 1, 0), dp(s + 1, 0);
    LL ans = 0;
    FOR(i, 1, n + 1) { cin >> a[i]; }
    FOR(i, 1, n + 1)
    {
        FORD(j, s, a[i] - 1) { dp[j] = (dp[j] + dp[j - a[i]]) % MOD; }
        if (a[i] <= s)
        {
            dp[a[i]] = (dp[a[i]] + i) % MOD;
        }
        ans = (ans + dp[s]) % MOD;
    }
    cout << ans << '\n';
}


Measured memory_bytes: 256
x,y=map(int,input().split())
if (x+y)%3!=0 : 
    print(0)
    exit()

a=(2*y-x)//3
b=(2*x-y)//3
if a<0 or b<0 :
    print(0)
    exit()

def C(n, r ,mod=10**9+7):
    if n-r<r: r=n-r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k]) %mod

    return result % mod

print(C(a+b,b))



Measured memory_bytes: 44036
#include <bits/stdc++.h>
using namespace std;
     
int main() {
  int a, b, s = 0;
  cin >> a >> b;
  
  if (a >= b) {
    s = a;
    a--;
  } else {
    s = b;
    b--;
  }
  
  if (a >= b) s = s + a;
  else s = s + b;

  cout << s << endl;
}

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

int main(void)
{
    int cnt = 0, n;
    while (cin >> n) {
        cnt = 0;
        for (int a = 0; a <= 9; ++a)
            for (int b = 0; b <= 9; ++b)
                for (int c = 0; c <= 9; ++c)
                    for (int d = 0; d <= 9; ++d)
                        if (a + b + c + d == n)
                            ++cnt;
        cout << cnt << endl;
    }
    return 0;
}







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

#define MODNUMBER 998244353

long long pow_mod(long long a, long long n)
{ // a^n mod MODNUMBER
	long long result = 1;
	long long a_i = a;
	long long n_tmp = n;
	while (n_tmp > 0)
	{
		if (n_tmp & 0b1)
		{
			result = (result * a_i) % MODNUMBER;
			// cout << result << "\n";
		}
		a_i = a_i * a_i % MODNUMBER;
		n_tmp = n_tmp >> 1;
	}
	return result;
}

long long fact_mod(long long k)
{ // k! mod MODNUMBER

	long long result = 1;
	for (int i = 1; i <= k; i++)
	{
		result = (result * i) % MODNUMBER;
	}
	return result;
}
vector<long long> fact_mod_vector(long long k)
{ // k! mod MODNUMBER

	vector<long long> result(k + 1, 1);
	result[0] = 1;
	for (int i = 1; i <= k; i++)
	{
		result[i] = (result[i - 1] * i) % MODNUMBER;
	}
	return result;
}

long long inv_mod(long long k)
{ // k^(-1) mod MODNUMBER

	return pow_mod(k, MODNUMBER - 2);
}

/* TODO: fact_mod()の途中経過を使いまわす実装にすれば早くなるらしい */
long long comb_mod(long long n, long long k, vector<long long> *fact_result)
{ // nCk mod MODNUMBER
	return ((*fact_result)[n] *
			inv_mod(((*fact_result)[k] * (*fact_result)[n - k]) % MODNUMBER)) %
		   MODNUMBER;
}

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

	long long N, M, K;
	scanf("%lld %lld %lld", &N, &M, &K);

	long long result = 0;

	vector<long long> fact_result = fact_mod_vector(N - 1);

	for (int i = 0; i <= K; i++)
	{
		// M *(N - 1Ci * (M - 1) ^ (M - 1 - i))
		long long tmp = (comb_mod(N - 1, i, &fact_result) * pow_mod(M - 1, N - 1 - i)) % MODNUMBER;
		// cout << "i=" << i << "tmp=" << tmp << "\n";
		result = (result + tmp) % MODNUMBER;
	}

	cout << ((result * M) % MODNUMBER);
	// cout << "\n"
	// 	 << comb_mod(6, 3, &fact_result) << "\n";
	// cout << " \n"
	// 	 << fact_result[4] << " \n";
	return 0;
}

Measured memory_bytes: 4844
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

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

    int a[100005];
    rep(i,n){
        cin >> a[i];
        a[i]--;
    }

    int sum = 0;
    int c = 0;
    while(sum < 100005){
        c = a[c];
        sum++;
        if(c == 1) break;
    }
    cout << (sum == 100005 ? -1 : sum) << endl;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//順列を入力し、条件を満たす数を計算するクラス
class DividetheProblems{
    vector<int> vec; //入力された数列を格納する配列
    int answer; //整数Kの選び方の数
    void func0(); //変数answerを求める関数
public:
    DividetheProblems(vector<int> vec0);
    void print(); //変数answerを出力
};

DividetheProblems::DividetheProblems(vector<int> vec0){
    vec = vec0; //引数の配列をメンバ変数に格納
    func0(); 
}

//変数answerを求める関数
void DividetheProblems::func0(){
    sort(vec.begin(),vec.end()); //配列の値を昇順で並べ替え
    int centerIndex = vec.size() / 2; //配列の中心右のインデックスを求める
    answer = vec[centerIndex] - vec[centerIndex - 1]; //中心の2つの整数の差が答え 
}

void DividetheProblems::print(){
    cout << answer << endl;
}

int main(void){
    int N = 0;
    vector<int> vec;
    cin >> N; //配列の要素数を決定
    //配列の要素を入力
    for(int i = 0; i < N; i++){
        int value;
        cin >> value;
        vec.push_back(value);
    }
    DividetheProblems dp(vec);
    dp.print();
    return 0;
}

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

int main(){
    int W,H,x,y,r;
    cin >> W >> H >> x >> y >> r;
    if (x - r < 0 || x + r > W || y - r < 0 || y + r > H) cout << "No" << endl;
    else cout << "Yes" << endl;
    
    return 0;
}


Measured memory_bytes: 3132
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
using namespace std;

int main()
{
    int N, K;
    cin >> N >> K;
    
    int sum = 0;
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        if (K <= x) {
            sum++;
        }
    }
    
    cout << sum << endl;
    
    return 0;
}

Measured memory_bytes: 888
#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int n;
	int t;
	scanf("%d %d", &n, &t);
	long long pre = 0, sum = 0;
	for(int i = 1; i <= n; i++){
		long long m;
		scanf("%lld", &m);
		if(m - pre <= t) sum = m + sum - pre;
		else{
			sum = sum + t;
		}
		pre = m;
	}	
	printf("%lld\n", sum + t);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define ll long long
#define fr(i,a,b) for (int i=a ; i<b ; i++)
#define fre(i,a,b) for (int i=a ; i<=b ; i++)
#define mem(a, b) memset(a, (b), sizeof(a))
#define mp make_pair
#define pb push_back
#define inf (int)1e9
#define pii 3.1415926535897932384626433832795
#define mod 1000000007
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<pi> vii;
typedef map<int,int> mi;
typedef set<int> si;

const int N = 1e5+10;
 
int n;
int a[N][3];
int dp[N][3];

int solve (int day, int bef) {
	if (day == n)
		return 0;
	
	int &r = dp[day][bef];
	if (r != -1) return r;
	for (int i = 0; i < 3; i++)
		if (i != bef)
			r = max (r, solve (day+1, i) + a[day][i]);
		
	return r;
}
 
int main () {
	memset (dp, -1, sizeof dp);
	scanf ("%d", &n);
	for (int i = 0; i <n; i++)
		for (int j = 0; j < 3; j++)
			scanf ("%d", &a[i][j]);
		
	int ans = -1;
	for (int i = 0; i < 3; i++)
		ans = max (ans, solve (1, i) + a[0][i]);
	printf ("%d\n", ans);
 
	return 0;
}

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

int main(){
    string S,T,tempT;
    int mojic_S,mojic_T;

    cin >> S >> T;

    mojic_S = S.size();
    mojic_T = T.size();

    tempT = T.erase(mojic_S);

    if(mojic_S + 1 == mojic_T && S == tempT){
        cout << "Yes" << endl;    
    }else{
        cout << "No" << endl;
    }   

}

Measured memory_bytes: 3632
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
int main() {
    ll n;
    cin >> n;

    bool ok = true;
    rep(i, n) {
        ll t, x, y;
        cin >> t >> x >> y;
        if(x+y > t) {
            ok = false;
        }
        else if((x+y)%2 != t%2) {
            ok = false;
        }
    }

    if(ok) {
        out("Yes");
    }
    else {
        out("No");
    }
    
    re0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
  ll N,a,zero=0; cin>>N;
  vector<vector<ll>>keep(3,vector<ll>(2,-1));
  bool finish=false;
  for(int i=0; i<N; i++){
    cin>>a;
    if(a==0){
      zero++;
      continue;
    }
    for(int j=0; j<3; j++){
      if(keep[j][0]==-1){
        keep[j][0]=a;
        keep[j][1]=1;
        break;
      }
      if(keep[j][0]==a){
        keep[j][1]++;
        break;
      }
      if(j==2) finish=true;
    }
    if(finish){
      cout<<"No"<<endl;
      return 0;
    }
  }
  
  if(zero==N){
    cout<<"Yes"<<endl;
    return 0;
  }
  if(N%3==0){
    ll z=N/3;
    if(zero==z && keep[0][1]==2*z){
      cout<<"Yes"<<endl;
      return 0;
    }
    if(zero==0){
      if(keep[0][1]==z && keep[1][1]==z && keep[2][1]==z){
        if(((keep[0][0]^keep[1][0])^keep[2][0])==0){
          cout<<"Yes"<<endl;
          return 0;
        }
      }
    }
  }     
  cout<<"No"<<endl;
}


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

int main(){

	string a, b;
	cin >> a >> b;

	if (a.size() > b.size())
		cout << "GREATER";
	else if (a.size() < b.size())
		cout << "LESS";
	else{
		if (a>b)
			cout << "GREATER";
		else if (a<b)
			cout << "LESS";
		else
			cout << "EQUAL";
	}

	cout << endl;

	return 0;
}


Measured memory_bytes: 256
//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector") 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>


#define ll long long
#define int ll
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = l; i < r; i++)
#define repb(i, r, l) for (int i = r; i > l; i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp(a, b) make_pair(a, b)
#define ret(a) {cout << a; exit(0);}

using namespace std;

mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

typedef pair < int , int > pii ;
typedef pair < long long  , long long > pll ;

const int N = 3e5 + 1;

int n, m, k;
int a[N], f[N];

main(){
	ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i = 1 ; i <= n; i++){
		int x;
		cin >> x;
		a[x]++;
	}

	sort(a + 1 , a + 1 + n);
	int j = 1 , sum = 0;

	for(int i = 1 ; i <= n ; i++){
		while(a[j] <= i and j <= n)
			sum += a[j] , j++;

		f[i] = (sum + (n - j + 1) * i) / i;
    }	
	for(int i = 1 ; i <= n ; i++){
		int l = 1 , r = n , res = 0;
		while(l <= r){
			int m = (l + r) >> 1;
			if(f[m] >= i){
				res = m;
				l = m + 1;
			}else r = m - 1;
		}
		cout << res << '\n';
	}
	
}


Measured memory_bytes: 5632
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <math.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> P;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REPR(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define FOR(i, n, m) for (ll i = (n); i < (m); ++i)
#define FORR(i, n, m) for (ll i = (m) - 1; i >= (n); --i) 
#define FORE(x, xs) for (auto &x: (xs))
#define ALL(v) v.begin(), v.end()
#define ZERO(a) memset(a,0,sizeof(a))
#define ANSWER(x) cout << x << endl;

const int INF = 1000000009;
const int MOD = 1000000007;
const double EPS = 1e-14;
const double PI = acos(-1);

const ll MAX = 1e5+10;

ll N, Q;
ll A[MAX];
ll odd[MAX], even[MAX], S[MAX];

int main() {
    cin >> N >> Q;
    REP (i, N) {
        cin >> A[i];
        if (i == 0) {
            even[0] = A[0];
            S[0] = A[0];
        }
        else {
            odd[i] = odd[i-1];
            even[i] = even[i-1];
            S[i] = S[i-1] + A[i];
            if (i&1) odd[i] += A[i];
            else even[i] += A[i];
        }
    }
    
    REP (q, Q) {
        ll x;
        cin >> x;
        if (x >= A[N-1]) { // 最後の要素以上なら大きい方から交互にとる
            ll ans;
            if (N&1) ans =  even[N-1];
            else ans = odd[N-1];
            ANSWER(ans);
            continue;
        } else if (x <= A[0]) { // 最初の要素以下なら大きい方半分
            ANSWER(S[N-1] - S[N/2-1]);
            continue;
        }
        ll lo = 0, hi = N;
        while (hi-lo > 1) { 
            ll mid = (hi+lo)/2;
            if (A[mid] <= x) lo = mid;
            else hi = mid;
        } // lo = max{i}(A[i] <= x)
        ll idx = lo;
        ll c1, c2, c3;
        lo = idx, hi = N;
        while (hi-lo > 1) {
            ll mid = (hi+lo)/2;
            c1 = mid-lo;
            c2 = N-mid;
            c3 = c2 - c1;

            ll candL1 = A[N-c2-1], candL2 = A[N-2*c2+1];
            ll candL = (abs(candL1-x) < abs(candL2-x)) ? candL2 : candL1;
            ll candR = A[N-c2];
            if (abs(x-candL) <= abs(x-candR)) hi = mid;
            else lo = mid;
        }
        lo = max(lo, N/2 - 1); // loは青木くんが連続でとる最大
        ll ans = S[N-1] - S[lo];
        ll num = N-1 - lo;
        if (N-num*2 > 0) {
            if (N&1) ans += even[N-1-num*2];
            else ans += odd[N-1-num*2];
        }
        ANSWER(ans);
    }
}

Measured memory_bytes: 4864
#include <iostream>
#include <string>
#include <map>

using namespace std;

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

    int ans = 1;
    string w = S.substr(0, 1);
    int i = 1;
    int len = S.size();
    while(true){
        if(i == len){
            break;
        }

        for(int j = 1; i+j <= len; j++){
            if(w != S.substr(i, j)){
                w = S.substr(i, j);
                i += j;
                ans++;
                break;
            }
            if(w == S.substr(i, j) && i+j == len){
                i += j;
                break;
            }
        }
    }

    cout << ans << endl;


    return 0;
}

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

typedef long long int ll;
#define rep(i,n) for(int i = 0; i < n; i++)
#define MOD 1000000007

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

  int n = s.size();

  int cnt[n][2];
  rep(i,n) rep(j,2) cnt[i][j] = 0;
  for(int i = n-2; i >= 0; i--) {
    cnt[i][0] += cnt[i+1][0];
    cnt[i][1] += cnt[i+1][1];
    cnt[i][s[i+1] == '1'] += 1;
  }
  // rep(i,n) printf("%d %d\n",cnt[i][0],cnt[i][1]);

  ll p[n];
  p[0] = 1;
  rep(i,n-1) p[i+1] = p[i]*3%MOD;
  //rep(i,n) printf("%lld ",p[i]);
  //printf("\n");

  ll ans = 0;
  ll c = 1;
  rep(i,n) {
    if (s[i] == '1') {
      ans = (ans + c*p[n-1-i])%MOD;
      c = c*2%MOD;
    }
  }
  ans = (ans+c)%MOD;
  cout << ans << endl;


  return 0;
}

Measured memory_bytes: 5220
#include<iostream>
#include<string>

using namespace std;
typedef long long ll;

ll a[100];
int N;

int main() {
	cin >> N;
	a[0] = 2, a[1] = 1;
	for (int i = 2; i <= N; i++)a[i] = a[i - 1] + a[i - 2];
	cout << a[N] << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int maxn = 5e5 + 10;
int N, M;
LL fact[maxn], fact_inv[maxn];
LL qpow(LL a, LL b)
{
    LL res = 1;
    a %= MOD;
    while(b)
    {
        if(b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}
void preprocess()
{
    fact[0] = 1;
    for(int i = 1; i <= M; i++)
        fact[i] = fact[i-1] * i % MOD;
    fact_inv[M] = qpow(fact[M], MOD - 2);
    for(int i = M; i >= 1; i--)
        fact_inv[i-1] = fact_inv[i] * i % MOD;
}
LL comb(int a, int b)
{
    if(a < 0 || b < 0 || a < b)
        return 0;
    else
        return fact[a] * fact_inv[b] % MOD * fact_inv[a-b] % MOD;
}
LL perm(int a, int b)
{
    if(a < 0 || b < 0 || a < b)
        return 0;
    else
        return fact[a] * fact_inv[a-b] % MOD;
}
int main()
{
    scanf("%d %d", &N, &M);
    preprocess();
    LL ans = 0;
    for(int K = 0; K <= N; K++)
        ans = (ans + comb(N, K) * qpow(-1, K) % MOD * perm(M, K) % MOD * qpow(perm(M - K, N - K), 2) % MOD) % MOD;
    printf("%lld\n", (ans % MOD + MOD) % MOD);
    return 0;
}


Measured memory_bytes: 11592
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 30;
const int MOD = 1e9 + 7;

int main() {
  int n;
  scanf("%d", &n);
  map<int, int> cnt;
  while (n--) {
    int x;
    scanf("%d", &x);
    cnt[x]++;
  }
  vector<int> A;
  int64 ret = 0;
  for (auto it : cnt) {
    if (it.second >= 2) A.push_back(it.first);
    if (it.second >= 4) {
      ret = max(ret, (int64)it.first * it.first);
    }
  }
  sort(A.begin(), A.end(), greater<int>());
  if (A.size() >= 2) {
    ret = max(ret, (int64)A[0] * A[1]);
  }
  printf("%lld\n", ret);
  return 0;
}


Measured memory_bytes: 4992
#include <iostream>
#include <vector>
#include <queue>

void solve () {
    int n;
    std::cin >> n;
    std::vector<int> k(n), l(n), r(n), a, b;
    for (int i = 0; i < n; i++) {
        std::cin >> k[i] >> l[i] >> r[i];
    }

    long long ans = 0;
    std::vector<int> index[2];
    for (int i = 0; i < n; i++) {
        ans += std::min(l[i], r[i]);
        if (l[i] >= r[i]) {
            index[0].push_back(i);
        } else {
            index[1].push_back(i);
            std::swap(l[i], r[i]);
            k[i] = n - k[i];
        }
    }
    
    auto calc = [&] (const std::vector<int> &v) -> void {
        std::vector<int> idx[n + 1];
        for (int i : v) idx[k[i]].push_back(i);
        std::priority_queue<int, std::vector<int>, std::greater<int>> que;
        for (int j = 0; j < n + 1; j++) {
            for (int i : idx[j]) que.push(l[i] - r[i]);
            while (que.size() > j) que.pop();
        }
        while (not que.empty()) {
            ans += que.top();
            que.pop();
        }
    };

    for (int i = 0; i < 2; i++) calc(index[i]);

    std::cout << ans << '\n';

    return;
}

int main() {
    std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    while (t--) solve();
    return 0;
}

Measured memory_bytes: 14112
#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
const int dx[4]={ 1,0,-1,0 };
const int dy[4]={ 0,1,0,-1 };

signed main(){
    int N;
    cin >> N;
    int zoro = 0;
    rep(i, N){
        int A, B;
        cin >> A >> B;
        if(A == B) zoro++;
        else zoro = 0;
        if(zoro >= 3){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

Measured memory_bytes: 3640
W,a,b = (int(i) for i in input().split())
#desk_A,desk_B = [a,a+W],[b,b+W]
if a <= b <= a+W or a <= b+W <= a+W:
    print(0)
    exit()
if a+W < b:
    print(b-(a+W))
else:
    print(a-(b+W))


Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include <vector>
#define ll long long
using namespace std;
string s;
ll res=0;
vector<int> v;
vector<string> vs;
void takeout(int x)
{
	int tap=1;
	int t=s.size();
	int xx=x;
	while (t--)
	{
		if (x%2) v.push_back(tap);
		tap++;
		x/=2;
	}
	v.push_back(tap-1);
}
int main()
{
	cin >>s;
	for (int t=0;t<(1<<(s.size()-1));t++)
	{
		v.clear();
		vs.clear();
		takeout(t);
		int b=0;
		for (int i=0;i<v.size();i++)
		{
			string ss=s.substr(b,v[i]-b);
			//cout <<t<<" "<<ss<<"\n";
			b=v[i];
			vs.push_back(ss);
		}
		for (int i=0;i<vs.size();i++)
		{
			string ss=vs[i];
			ll r=0,tap=1;
			for (int j=ss.size()-1;j>=0;j--) r+=(ss[j]-'0')*tap,tap*=10;
			res+=r;
		}
	}
	cout <<res;
	return 0;
}

Measured memory_bytes: 256
R,G,B,N=gets.split.map &:to_i
sum=0
for r in 0..3000 do
    if r*R<=N then 
    for g in 0..3000 do
        if (r*R+g*G<=N&&(N-r*R-g*G)%B==0) then
            sum+=1
        end
    end
end
end
p sum

Measured memory_bytes: 1788
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
  
def lcm(a, b):
    return a * b // gcd (a, b)


if __name__ == '__main__':
  a,b=(int(x) for x in input().split())
  print(str(lcm(a,b)))

Measured memory_bytes: 2940
H, W, K = map(int, input().split())
canvas = [input().strip() for _ in range(H)]

canvas_as_int = [int(s.replace('.','0').replace('#','1'), 2) for s in canvas]

column_masks = [[int(s) for s in f"{j:b}".zfill(H)] for j in range(2**H)]

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f

res = 0
for i in range(2**W):
    row_masked_canvas = [popcount(n&i) for n in canvas_as_int]
    blacks = [sum(c * r for c,r in zip(column_mask,row_masked_canvas)) for column_mask in column_masks]
    res += blacks.count(K)

print(res)


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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

typedef long long ll;
typedef long double ld;

const ll Inf = 1e18;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
    string a, b, c;
    cin >> a >> b >> c;
    if ('a' <= b[0] && b[0] <= 'z') b[0] = b[0] - 'a' + 'A'; 
    cout << char('A') << b[0] << char('C') << endl;
    
    return 0;
}



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

using namespace std;

#define fst first
#define snd second
#define squ(x) ((LL)(x) * (x))
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef pair<int, int> pii;

inline int read() {
	int sum = 0, fg = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') fg = -1;
	for (; isdigit(c); c = getchar()) sum = (sum << 3) + (sum << 1) + (c ^ 0x30);
	return fg * sum;
}

const int maxn = 2e5 + 10;

int n, a[maxn];

int main() {
#ifdef xunzhen
	freopen("sum.in", "r", stdin);
	freopen("sum.out", "w", stdout);
#endif

	n = read();
	for (int i = 1; i <= n; i++) a[i] = read();

	LL ans = 0;
	for (int i = 1, j = 1, now = 0; i <= n; i++) {
		while (j <= n && !(now & a[j])) now |= a[j++];
		ans += j - i, now ^= a[i];
	}
	printf("%lld\n", ans);

	return 0;
}

Measured memory_bytes: 1024
#include <cmath>
#include <cstdio>
#include <vector>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <map>
#include <stdio.h>
#include <functional>
#include <chrono>
#include <boost/version.hpp>
using namespace std;

#define rep(i,s,n) for(ll i=s;i<(n);++i)
using ll = long long;
using pll = pair<ll, ll>;
constexpr ll INF = (1LL << 60);
constexpr ll MAX_INF = 9223372036854775807;
constexpr ll MOD = (1e9 + 7);
//constexpr ll MOD = (998244353);

using vl = vector<ll>;
using vvl = vector<vector<ll>>;

template<class T>
vector<vector<T>> vvt(T init, ll m, ll n) {
	vector<vector<T>> ans = vector<vector<T>>(m, vector<T>(n, init));
	return move(ans);
}

template<class T>
vector<T> vt(T init, ll n) {
	vector<T> ans = vector<T>(n, init);
	return move(ans);
}

template<class T>
T maxVec(vector<T>& v) {
	T ans = -INF;
	rep(i, 0, v.size()) {
		ans = max(ans, v[i]);
	}
	return ans;
}

// 素数判定
bool judge(ll n) {
	for (ll i = 2; i * i <= n; i++) if (n %= i)return false;
	return true;
}


template <class C>
void print(const C & c, std::ostream & os = std::cout)
{
	std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, ", "));
	os << std::endl;
}
/*
ll count(ll n,ll r) {
	ll ans = 0,check = 1;
	rep(i,0, r) {
		if ((n & check) > 0) {
			ans++;
		}
		check = check << 1;
	}
	return ans;
}
*/
bool sortreverse(ll a, ll b) {
	return a > b;
}


ll kiriage(ll a, ll b) {
	if (a % b == 0)return a / b;
	return a / b + 1;
}

ll n, m, t, q, s,k,h,w,x,y;

void warshall_floyd(ll v_num,vector<vector<long long>> &d) {
	for (long long k = 0; k < v_num; k++) {       // 経由する頂点
		for (long long i = 0; i < v_num; i++) {    // 始点
			for (long long j = 0; j < v_num; j++) {  // 終点
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
}

ll modpow(ll n, ll a, ll m) {
	if (n > 1000000000) {
		printf("large");
		exit(0);
	}
	if (a == 0)return 1;
	if (a % 2 == 0) {
		ll b = modpow(n, a / 2, m);
		if (b*b > 1000000000) {
			printf("large");
			exit(0);
		}
		
		return (b * b);
	}
	else if (a % 2 == 1) {
		ll b = modpow(n, a -1, m);
		if (b*n > 1000000000) {
			printf("large");
			exit(0);
		}
		return (n * b);
	}
}

long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}


int main() {
	// ↓この２行が追加部分
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	ll f;
	cin >> n >> k;

	ll ans = 0;
	rep(i, k, n+2) {
		//ans += (((kaijyo[n + 1] * kaijyoINV[i])%MOD) * kaijyoINV[n+1-i]) %MOD;
		//ans %= MOD;
		ll minNum = (i - 1) * i / 2, maxNum = (n + 1) * n / 2 - (n + 1 - i) * (n - i) / 2;
		ans += (maxNum - minNum + 1) % MOD;
		ans %= MOD;
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 3780
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(ll i = 0; i<(ll)(n); i++)
#define REPS(i,n) for (ll i = 1; i<=(ll)(n); i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define pb push_back
#define MOD 1000000007
#define MOD2 998244353
#define PI 3.141592653
#define INF 100000000000000 //14

int main(){
    ll n; cin >> n;
    vector<ll> a(n);
    vector<ll> b(n);
    REP(i,n){
        cin >> a[i] >> b[i];
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    if (n%2) cout << b[(n-1)/2]-a[(n-1)/2]+1 << endl;
    else cout << b[n/2]+b[n/2-1]-a[n/2]-a[(n-1)/2]+1 << endl;
}

Measured memory_bytes: 6424