akhauriyash/Code-Regression huggingface dataset:
import std.stdio, std.string, std.conv, std.range;
import std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, std.random, core.bitop;

enum inf = 1_001_001_001;
enum infl = 1_001_001_001_001_001_001L;


void main() {
    auto s = readln.chomp.to!(char[]);
    int k;
    scan(k);

    int N = s.length.to!int;

    foreach (i ; 0 .. N) {
        if (s[i] == 'a') continue;
        int x = 'z' - s[i] + 1;
        if (x <= k) {
            k -= x;
            s[i] = 'a';
        }
    }

    k %= 26;

    if (k > 0) {
        s[$ - 1] = (s[$ - 1] + k).to!char;
    }

    writeln(s);
}



void scan(T...)(ref T args) {
    auto line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront;
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;
    foreach (arg; args) if (x > arg) {
        x = arg;
        isChanged = true;
    }
    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;
    foreach (arg; args) if (x < arg) {
        x = arg;
        isChanged = true;
    }
    return isChanged;
}

void yes(bool ok, string y = "Yes", string n = "No") {
    return writeln(ok ? y : n);
}


Measured memory_bytes: 2588
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        for(int i = 0; i < 4; i++){
            switch(scan.nextInt()){
                case 1:
                    System.out.println(scan.nextInt() * 6000);
                    break;
                case 2:
                    System.out.println(scan.nextInt() * 4000);
                    break;
                case 3:
                    System.out.println(scan.nextInt() * 3000);
                    break;
                default:
                    System.out.println(scan.nextInt() * 2000);
                    break;
            }
        }
        scan.close();
    }
}


Measured memory_bytes: 26196
import sys
import os
if sys.platform=="darwin":
   base = os.path.dirname(os.path.abspath(__file__))
   name = os.path.normpath(os.path.join(base, '../Documents/input.txt'))
   #print(name)
   sys.stdin = open(name)

n,a,b = map(int,input().split())

if a > b:
   print(0)
   exit()

if n == 1:
	if a == b:
		print(1)
		exit()
	else:
		print(0)
		exit()

print( (b-a)*(n-2)+1 )


Measured memory_bytes: 38384
I=->{gets.split.map &:to_i}
N,Q=I[]
A=[1,c=1,1,*[0]*(N-2),1]
Q.times{
	a,b=I[]
	A[a],A[b]=A[b],A[a]
(c==a||c==b)&&c=a+b-c
	A[c-1]=A[c+1]=1
}
p A.reduce(:+)-2

Measured memory_bytes: 4220
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC target ("avx,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define len(v) ((int)v.size())
#define all(v) v.begin(), v.end()
#define oset tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define orz ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);    
#define inp freopen("input.txt","r",stdin);freopen("out.txt","w",stdout); 
ll mod=1e9+7;
void io(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //cout.tie(NULL);    
    
}
const int N=2e5+5;

ll pre[N][26];
int main() {
    io();
    ll i,j,k,n,m,prev=0,cnt=0;
    string s,t;

    cin>>s>>t;
    n=s.length();
    s+=s;
    for(i=2*n-1;i>=0;i--){
        for(j=0;j<26;j++){
            if(i!=(2*n-1))
                pre[i][j]=pre[i+1][j];
            else
                pre[i][j]=2*n;
            pre[i][s[i]-'a']=i;
        }
    }
    
    prev=-1;
    ll ans=-1;
    for(i=0;i<t.length();i++){
        prev=(ans+1)%n;
        k=pre[prev][t[i]-'a'];
        if(k==2*n){
            cout<<"-1";
            return 0;
        }
        ans +=  pre[prev][t[i]-'a'] - prev +1;

        
    }
    cout<<ans+1;
}





Measured memory_bytes: 41324
#include<bits/stdc++.h>
using namespace std;
const int maxv=1000010;
typedef long long ll;
ll n;
ll a[maxv];
ll b[maxv];
ll c[maxv];
ll ans[maxv][3];

int main()
{

    cin>>n;


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

    ans[0][0]=a[0];
    ans[0][1]=b[0];
    ans[0][2]=c[0];
    for(int i=1; i<n; i++)
    {
        ans[i][0]+=max(ans[i-1][1],ans[i-1][2])+a[i];
        ans[i][1]+=max(ans[i-1][0],ans[i-1][2])+b[i];
        ans[i][2]+=max(ans[i-1][0],ans[i-1][1])+c[i];


    }
    ll result=max(ans[n-1][2],max(ans[n-1][0],ans[n-1][1]));
    cout<<result;

    return 0;

}


Measured memory_bytes: 10496
#include <stdio.h>
#include <cmath>
#include <bits/stdc++.h>



using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;


//container util
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define B 380000


int main(void){

	int N; scanf("%d", &N);

	double ans = 0.0;
	REP(i,N){
		double x; 
		char u[4];
		scanf("%lf %s", &x, u);

		if(strcmp(u,"JPY") == 0) ans += x;
		else{
			ans += x* B;
		}
	}

	printf("%f\n",ans);

	return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
#define fast                                                                   \
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define ll long long
#define f(i, n) for (int i = 0; i < n; i++)
#define fo(i,a,n) for (i = a; i <= n; i++)
#define F first
#define S second
#define pii pair<int,int>
#define sz size()
#define all(v) v.begin(),v.end()
#define pb push_back
#define pf push_front    
#define PB pop_back
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<int>
#define mp make_pair
#define mod 1000000007
typedef unsigned long long ull;
const int N = 200005;
const int MOD = 998244353 ;


void solve(){
    int n, m;
    cin>>n>>m;
    if(m < n)cout<<"No";
    else cout<<"Yes";
}

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


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

int main()
{
 int n;
 cin>>n;
 double p[n];
 for(int i=0; i<n; i++)cin>>p[i];
 double dp[n+1]={0};
 
 dp[0]=1;
 for(int coins=0; coins<n; coins++)
 {
     for(int i = coins+1; i>=0; i--)
     {
     	dp[i] = (i==0?0:dp[i-1]*p[coins]) + dp[i]*(1-p[coins]);
	 }
 }
 double ans=0;
 for(int heads = 0; heads<=n; heads++)
 {
 	int tails = n-heads;
 	if(heads>tails)ans += dp[heads];
 }
 printf("%.10lf\n", ans);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pii;
typedef vector< pii > vii;

#define ll          long long
#define ff          first
#define ss          second
#define pb          push_back
#define mkp         make_pair
#define sz          size()

#define forf(a,b,c)    for(int i=a;i<=b;i+=c)
#define forr(a,b,c)    for(int i=a;i>=b;i-=c)
#define all(a)      a.begin(),a.end()
#define mem(a,b)    memset(a,b,sizeof(a))
#define pi          2*acos(0.0)
#define End         return 0;

#define scan1(a)    scanf("%d",&a)
#define scan2(a,b)  scanf("%d %d",&a,&b)
#define scan3(a,b,c)  scanf("%d %d %d",&a,&b,&c)
#define scanl(a)    scanf("%lld",&a)
#define scanll(a,b) scanf("%lld %lld",&a,&b)
#define scanlll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)

#define print1(a)    printf("%d",a)
#define print2(a,b)  printf("%d %d",a,b)
#define print3(a,b,c)  printf("%d %d %d",a,b,c)
#define printl(a)    printf("%lld",a)
#define printll(a,b) printf("%lld %lld",a,b)
#define printlll(a,b,c) printf("%lld %lld %lld",a,b,c)

#define MAXN        100000007
#define INF 0x3f3f3f3f
//int dx[]={+1,-1,+0,+0};///Four Directions
//int dy[]={+0,+0,+1,-1};///Four directions
//int dx [] = {+1,-1,+0,+0,-1,-1,+1,+1};///Eight Directions
//int dy [] = {+0,+0,+1,-1,+1,-1,-1,+1};///Eight Directions

//int mark[10007];vi prime;void seive(){for(int i=2;i<10000;i++){if(mark[i]==0){prime.pb(i);for(int j=i+i;j<=10000;j+=i)mark[j]=1;}}}

//freopen("input.txt", "r", stdin);

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

   int n,k,res=0;
   cin>>n>>k;
   int mark[n+3]; mem(mark,0);
   for(int i=1;i<=k;i++) {
    int c; cin>>c;
    while(c--) {
        int cc; cin>>cc;
        mark[cc]=1;
    }
   }

   for(int i=1;i<=n;i++) if(mark[i]==0) res++;

   cout<<res<<endl;
   End;
}


Measured memory_bytes: 3656
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>

using namespace std;
typedef long long ll;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, f, n) for (ll i = (f); i < (n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define repv(v) for (auto it = (v).begin(); it != (v).end(); it++)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define INIT cin.tie(0); ios::sync_with_stdio(false);

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

ll const INF = 1LL << 60;
ll const MOD = 1000000007;

int main() {
    INIT;

    ll N;
    cin >> N;
    vector<ll> a(N);
    rep(i, N) cin >> a[i];

    sort(ALL(a), greater<ll>());
    ll suma = 0;
    ll sumb = 0;

    rep(i, N) {
        if (i % 2 == 0) {
            suma += a[i];
        } else {
            sumb += a[i];
        }
    }

    cout << suma - sumb << endl;

    return 0;
}

Measured memory_bytes: 3660
#!/usr/bin/env python3
n,x = map(int,input().split())	
a = list(map(int,input().split()))
ans = 0
for i in range(n-1):
    ans += max(0,a[i]+a[i+1]-x)
    a[i+1] = max(0,a[i+1]-max(0,a[i]+a[i+1]-x))
print(ans)

Measured memory_bytes: 14600
str = input()
cnt = 0
 
for i in range(3):
  if str == 'RRR':
    cnt = 3
  elif str == 'RRS':
    cnt = 2
  elif str == 'SRR':
    cnt = 2
  elif str == 'SSS':
    cnt = 0
  else:
    cnt = 1
    
print(cnt)

Measured memory_bytes: 8980
#include<stdio.h>
int sort(int sorted[3])
{
	int i, j,tmp;
	for(i=0;i<3;i++)
		for(j=i+1;j<3;j++)
			if (sorted[i] > sorted[j])
			{
				tmp = sorted[i];
				sorted[i] = sorted[j];
				sorted[j] = tmp;
			}

}

int main()
{
	int a, b, c;
	int n;
	scanf("%d", &n);
	int i,sorted[3];
	for (i = 0; i < n; i++)
	{
		scanf("%d %d %d", &a, &b, &c);
		sorted[0] = a; sorted[1] = b; sorted[2] = c;
		sort(sorted);
		if (sorted[2] * sorted[2] == sorted[0] * sorted[0] + sorted[1] * sorted[1])
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}

Measured memory_bytes: 580
#include <bits/stdc++.h>
using namespace std;
#define INF 2147483647
#define INFF 9223372036854775807
#define ll long long
#define REP(i,n) for(long long i=0;i<n;i++)
#define REPP(i,m,n) for(long long i=m;i<n;i++)
#define ALL(N) (N.begin(),N.end())
#define de cout << "line : " << __LINE__ << " debug" << endl;
#define pb push_back
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    cin.tie(0);    
	ios::sync_with_stdio(false);
    string S;
    cin >> S;
    vector<char> V;
    bool flag = 0;
    REP(i,S.size()-1){
        if(S[i] == S[i+1]){
            if(i != S.size()-2){
              	V.pb(S[i]);
                V.pb(S[i+1]+S[i+2]);
                i += 2;
              	if(i == S.size()-2) V.pb(S[i+1]);
            }
            else{
              V.pb(S[i]+S[i+1]);
              break;
            }
        }
        else if(S[i] != S[i+1]){
            V.pb(S[i]);
          	if(i == S.size()-2) V.pb(S[i+1]);
        }
    }
    cout << V.size() << endl;
}

Measured memory_bytes: 788
# ABC129 E

L=input()
N=len(L)
p=10**9+7

def pow_k(x,n,p=10**9+7):
    if n==0:
        return 1
    K=1
    while n>1:
        if n%2!=0:
            K=(K*x)%p
        x=(x*x)%p
        n//=2
    return (K*x)%p


res=0
tmp=1
for i in reversed(range(N)):
    if L[N-1-i]=='1':
        res=(res+tmp*pow_k(3,i,p))%p
        tmp=(2*tmp)%p
print((res+tmp)%p) 

Measured memory_bytes: 73544
import sys
import time

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    m, k = list(map(int, readline().split()))

    if m == 0:
        if k == 0:
            print(0, 0)
        else:
            print(-1)
    elif m == 1:
        if k == 0:
            print(0, 0, 1, 1)
        else:
            print(-1)
    else:
        if k < 2 ** m:
            x = [i for i in range(2 ** m)]
            x.remove(k)
            y = x[::-1]
            ans = x + [k] + y + [k]
            print(*ans)
        else:
            print(-1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 69484
import itertools as itt
import math

k = int(input())

ans = 0
for i in itt.combinations_with_replacement(range(1, k+1), 3):
    if i[0] == i[1] and i[0] != i[2]:
        ans += 3 * math.gcd(math.gcd(i[0], i[1]), i[2])
    elif i[1] == i[2] and i[1] != i[0]:
        ans += 3 * math.gcd(math.gcd(i[0], i[1]), i[2])
    elif i[0] == i[1] and i[0] == i[2]:
        ans += math.gcd(math.gcd(i[0], i[1]), i[2])
    else:
        ans += 6 * math.gcd(math.gcd(i[0], i[1]), i[2])

print(ans)

Measured memory_bytes: 9176
import sys
 
x = []
i = 0
for line in sys.stdin:
    if i==0:
        lx = int(line)
    else:
        x.append([int(i) for i in line.split()])
    i = 1
 
rb = range(4)
rf = range(3)
rr = range(10)
rooms = [[[0 for i in rr] for j in rf]for k in rb]
for e in x:
    i,j,k,l = e
    rooms[i-1][j-1][k-1] += l
 
for i in rb:
    for j in rf:
        print '',
        for k in rr:
            print rooms[i][j][k],
        print
    if i<len(rb)-1: print '#' * 20



Measured memory_bytes: 4684
N, M = map(int, input().split())
cnt = [0] * (N+1)
for _ in range(M):
    ta,tb = map(int, input().split())
    cnt[ta] += 1
    cnt[tb] += 1
cond = 0
for i in range(1,N+1):
    if cnt[i] % 2 == 1:
        cond = 1
        break

if cond:
    print('NO')
else:
    print('YES')

Measured memory_bytes: 3828
#include <stdio.h>
int main(void){
  int n,i,j,l,o,ky,b,k,ans=-1000000000,md[100]={},my[100][11];
  int w[10]={1,2,4,8,16,32,64,128,256,512};
  scanf("%d",&n);
  for (i=0;i<n;i++){
    for (j=0;j<10;j++){
      scanf("%d",&b);
      md[i]+=w[j]*b;
    }
  }
  for (i=0;i<n;i++){
    for (j=0;j<11;j++){
      scanf("%d",&my[i][j]);
    }
  }
  for (i=1;i<1024;i++){
    k=0;
    for (j=0;j<n;j++){
      o=i&md[j];
      ky=0;
      for (l=0;l<10;l++){
        if (o&w[l]) ky++;
      }
      k+=my[j][ky];
    }
    if (ans<k) ans=k;
  }
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 128
f=lambda:map(int,input().split())
h,w,n=f()
c=[(h-2)*(w-2)]+[0]*9
d={}
while n:
 n-=1;x,y=f()
 for i in range(9):
  a=x+i%3,y+i//3
  if h>=a[0]>2<a[1]<=w:t=d[a]=d.get(a,0)+1;c[t-1]-=1;c[t]+=1
print(*c)

Measured memory_bytes: 166480
#include <iostream>
#include <sstream>

using namespace std;

string reverse(string s) {
	string ans = "";
	int i = s.size()-1;
	for (int j = 0; i >= 0; i--, j++)
		ans += s[i];
	return ans;
}

string add(string n, string m) {
	string ans;
	int a, carry = 0;
	if (n.size() < m.size())
		swap(n, m);
	int i = n.size();
	int j = m.size();
	for (; i > 0; i--) {
		a = (n[i-1] - '0') + carry;
		if (j) {
			a = a + (m[j-1] - '0');
			j--;
		}
		if (a > 9) {
			a -= 10;
			carry = 1;
		} else {
			carry = 0;
		}
		stringstream ss;
		ss << a;
		string t = ss.str();
		ans += t[0];
	}
	if (carry)
		ans += "1";
	return reverse(ans);
}

int main() {
	string n, m, ans;
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> n >> m;
		ans = add(n, m);
		if (ans.size() > 80)
			cout << "overflow" << endl;
		else
			cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 1240
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
using ll=long long;
static const ll mod = 1e9 + 7;
static const ll INF = 1LL << 50;
using namespace std;



signed main(){
	int n;
	cin>>n;
	vector<ll>a(n);
	vector<int>idx(n+5);
	rep(i,n){
		cin>>a[i];
		idx[a[i]]=i+1;
	}
	set<ll>s;
	s.emplace(n+1);
	s.emplace(0);
	ll ans=0;
	for(int64_t i=1;i<=n;++i){//値の小さなものから見ていく
		auto right=s.upper_bound(idx[i]);
		auto left=right;
		left--;
		ans+=i*(*right-idx[i])*(idx[i]-*left);
		s.emplace(idx[i]);
	}
	cout<<ans<<endl;
	return 0;
}

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

const string cindex="ABWXYZS";
const string next[]={"XY","YX","BY","SZ","XS","WB","SS"};

int getCityIndex(char c){
	for(int i=0;i<cindex.size();++i) if(cindex[i]==c) return i;
}
int main(void){
	string s;
	while(cin>>s){
			if(s[0]=='#')break;
			char c='A';
			for(int i=0;i<s.size();++i){
				c=next[getCityIndex(c)][s[i]-'0'];
			}
			cout<<((c=='B')?"Yes":"No")<<endl;
	}
}

Measured memory_bytes: 1192
#include <stdio.h>

int main(void)
{
	long long int a, b, c, d;
	long long int greatest;

	scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
	
		greatest = a * c;
	
	if (a * d > greatest)
	{
		greatest = a * d;
	}
	if (b * c > greatest)
	{
		greatest = b * c;
	}
	if (b * d > greatest)
	{
		greatest = b * d;
	}
	printf("%lld\n", greatest);
	
}

Measured memory_bytes: 1732
using System;
using System.IO;
using System.Linq;

namespace Tree
{
    class Rooted_Trees
    {
        struct Node
        {
            public int id;
            public int parent;
            public int depth;
            public int[] childlen;
            public string type;
        }
        static void Main(string[] args)
        {
            int size = int.Parse(Console.ReadLine());
            var nodes = new Node[size];

            for (int i = 0; i < size; i++)
                nodes[i].parent = -1;

            for (int i = 0; i < size; i++)
            {
                var token = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
                var id = token[0];
                nodes[id].id = id;

                var k = token[1];
                if (k == 0) nodes[id].type = "leaf";
                else nodes[id].type = "internal node";
                nodes[id].childlen = new int[k];
                for (int j = 0; j < k; j++)
                {
                    nodes[id].childlen[j] = token[2 + j];
                    nodes[token[2 + j]].parent = id;
                }
            }

            for (int i = 0; i < size; i++)
                if (nodes[i].parent == -1)
                {
                    nodes[i].type = "root";
                    SetDepth(nodes, i, 0);
                    break;
                }

            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            for (int i = 0; i < size; i++)
                Console.WriteLine("node {0}: parent = {1}, depth = {2}, {3}, ["+ string.Join(", ", Array.ConvertAll(nodes[i].childlen, n => n.ToString()))+"]", nodes[i].id, nodes[i].parent, nodes[i].depth, nodes[i].type);

            Console.Out.Flush();
        }

        static void SetDepth(Node[] nodes, int id, int depth)
        {
            nodes[id].depth = depth;
            for (int i = 0; i < nodes[id].childlen.Length; i++)
                SetDepth(nodes, nodes[id].childlen[i], depth + 1);
        }
    }
}

Measured memory_bytes: 29504
import sys
fastinput = sys.stdin.readline
from collections import deque
S = input()
Q = int(input())
ans = deque([S])
Reverse = False
for q in range(Q):
    query = fastinput().split()
    if query[0]=="1":
        Reverse = not Reverse
    elif (query[1]=="1") ^ Reverse:#左側にくっつく
        ans.appendleft(query[2])
    else:
        ans.append(query[2])
SS = "".join(list(ans))
if Reverse:
    SS = "".join(reversed(SS))
print(SS)


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

int main() {
    long long n,m;
    cin >> n >> m;
    long long a[n];
    for (long long  i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a+n);

    vector<pair<long,long> > v;
    for (long long j = 0; j < m; j++) {
        long long bj, cj;
        cin >> bj >> cj;
        v.push_back(make_pair(cj,bj));
    }
    sort(v.begin(), v.end(), greater<pair<long,long> >());

    long long idx = 0;
    for (int i = 0; i < m; i++) {
        long long b = v[i].second;
        long long c = v[i].first;
        if (a[idx] >= c) {
            break;
        }
        for (int j = 0; j < b; j++) {
            if (a[idx] >= c) {
                break;
            }
            a[idx] = c;
            idx++;
        }
    }

    long long ret = 0;
    for (int i = 0; i < n; i++) {
        ret += a[i];
    }
    cout << ret << endl;
}


Measured memory_bytes: 3188
#include <iostream>
#include <limits.h>
#include <math.h>
using namespace std;

long long pow(long long n, long long k) {
    long long m = 1;
    for (int i = 0; i < k; i++) m *= n;
    return m;
}

int main(void){
    long long n;
    cin >> n;
    
    if (n == 1) {
        cout << 1 << endl;
        return 0;
    }
    
    long long d = 0, b = 1;
    while (n >= b) {
        d++;
        b *= 10;
    }
    
    for (int i = 10; i > 0; i--) {
        if (n >= i * pow(10, d - 1) - 1) {
            cout << 9 * (d - 1) + i - 1 << endl;
            return 0;
        }
    }
    
    
}


Measured memory_bytes: 256
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define SORT(a) sort((a).begin(), (a).end())
#define RSORT(a) sort((a).rbegin(), (a).rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define RREP(i, n) for (int i = n; 0 <= i; i--)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define FORSTEP(i, start, end, step) for (int i = start; i < end; i += step)
#define ALL(a) a.begin(), a.end()
typedef long long ll;
const int INF = 100100100;
using namespace std;

class UnionFind {
  public:
    // 親の番号を格納する。大家だった場合は－1
    vector<int> Parent;

    // 作るときはparentの値をすべて-1にする
    //こうするとすべてばらばらになる
    UnionFind(int N) { Parent = vector<int>(N, -1); }

    // Aがどのグループに属しているか調べる
    int root(int A) {
        if (Parent[A] < 0)
            return A;
        return Parent[A] = root(Parent[A]);
    }

    int size(int A) {
        return -Parent[root(A)]; //親をとっていきたい
    }

    // AとBをくっつける
    bool connect(int A, int B) {
        A = root(A);
        B = root(B);
        //すでにくっついているからくっつけない
        if (A == B)
            return false;

        // 大きい方(A)に小さい方(B)をくっつけたい
        //大小が逆のばあいひっくり返す
        if (size(A) < size(B))
            swap(A, B);
        Parent[A] += Parent[B];
        Parent[B] = A;
        return true;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<int> A(M), B(M);
    REP(i, M) {
        cin >> A[i] >> B[i];
        // 1番目の島を0番目にしたい
        A[i]--;
        B[i]--;
    }

    vector<ll> ans(M);
    ans[M - 1] = (ll)N * (N - 1) / 2;

    UnionFind uni(N);
    for (int i = M - 1; 1 <= i; i--) {
        ans[i - 1] = ans[i];
        //繋がっていないのが繋がったとき
        if (uni.root(A[i]) != uni.root(B[i])) {
            ans[i - 1] -= (ll)uni.size(A[i]) * uni.size(B[i]);
            uni.connect(A[i], B[i]);
        }
    }

    REP(i, M) cout << ans[i] << endl;

    return 0;
}

Measured memory_bytes: 3328
// Getting Started - Insertion Sort

using System;
using System.Collections.Generic;

class program
{
    public static void Main()
    {
        var str = Console.ReadLine().Split(' ');
        var x = int.Parse(str[0]);
        var y = int.Parse(str[1]);
        Console.WriteLine(gcd(x, y));
    }

    public static int gcd(int x, int y)
    {
        var high = x > y ? x : y;
        var low = high == x ? y : x;
        
        while (true)
        {
            var m = 0;
            while (high - m * low >= 0)
            {
                m++;
            }
            m--;
            
            if (high - m * low == 0)
            {
                return low;
            }
            else
            {
                var buf = high - low * m;
                high = low;
                low = buf;
            }
        }
    }
}

Measured memory_bytes: 5604
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <set>
#include <bitset>
#include <unordered_map>

using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
template <class T>
using Vvec = vector<vector<T> >;

int main()
{
    ll N, D, A;
    cin >> N >> D >> A;
    vector<Pll> fox(N);
    for(int i=0; i<N; i++) cin >> fox[i].first >> fox[i].second;

    sort(fox.begin(), fox.end());
    vector<ll> d(N+1);
    d[0] = fox[0].second;
    for(int i=1; i<N; i++) d[i] = fox[i].second - fox[i-1].second;

    ll s = 0, ans = 0;
    ll j = 0;
    for(int i=0; i<N; i++){
        while(j < N && fox[i].first + 2*D >= fox[j].first) j++;
        s += d[i];
        // for(int i=0; i<N; i++) cout << d[i] << " "; cout << endl;
        if(s <= 0) continue;
        ll c = s/A;
        if(s%A!=0) c++;
        ans += c;
        d[i] -= c*A;
        d[j] += c*A;
        s -= c*A;
        // cout << c << endl;
    }

    cout << ans << endl;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007

int main(){
    FAST
    int a,b;
    cin>>a>>b;
    if(a/10==0 && b/10==0)cout<<a*b;
    else cout<<-1;
    return 0;
}

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

cw = 0
dw = {}
ca = 0
d = {}
for i in range(m):
    p, s = input().split()
    if d.get(p) == "AC":
        continue
    if p not in dw:
        dw[p] = 0
    if s == "WA":
        dw[p] += 1
    else:
        ca += 1
        cw += dw[p]
    d[p] = s

print(ca, cw)            

Measured memory_bytes: 28104
#include <atcoder/math>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <iomanip>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <cassert>
#include <stack>
#include <climits>
#include <array>
#include <unordered_set>
#include <unordered_map>
#include <memory>
#include <functional>
#include <cfloat>
#include <numeric>

int main() {
	int t; std::cin >> t;
	for (auto i = 0; i < t; ++i) {
		int n, m, a, b; std::cin >> n >> m >> a >> b;
		std::cout << atcoder::floor_sum(n, m, a, b) << '\n';
	}
}


Measured memory_bytes: 3644
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)

const int mo = 1e9 + 7;
typedef long long ll;
ll ans;
void solve()
{
    string s;
    cin>>s;
    if(s=="Sunny")cout<<"Cloudy"<<endl;   
    else if(s=="Cloudy")cout<<"Rainy"<<endl;   
    else cout<<"Sunny"<<endl;   
}
main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    solve();
    return 0;
}

Measured memory_bytes: 256
from collections import defaultdict

N, M = map(int, input().split(' '))

cleared = set()
penalties = defaultdict(int)

for _ in range(M):
    q, result = input().split(' ')
    if result == 'AC':
        cleared.add(q)
    elif q not in cleared:
        penalties[q] += 1

print(len(cleared), sum([penalties[q] for q in cleared]))


Measured memory_bytes: 25180
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int int_sort(const void *a, const void *b){
  if(*(int *)a > *(int *)b){
    return -1;
  }else if(*(int *)a == *(int *)b){
    return 0;
  }
  return 1;
}

int main(void){
  int n, k, i, a, f, c[200000], sum=0;
  for(i=0;i<200000;i++) c[i]=0;
  scanf("%d %d",&n,&k);
  for(i=0;i<n;i++){
    scanf("%d",&a);
    c[a-1]++;
  }
  qsort((void *)c, 200000, sizeof(c[0]), int_sort);
  /*printf("mark: ");
  for(i=0;i<n;i++) printf("%d, ",c[i]);
  printf("\n");*/
  for(i=k;i<n;i++) sum+=c[i];
  printf("%d\n",sum);
  return 0;
}


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

using namespace std;
typedef long long ll;
typedef long double ld;
const double pi = 3.141592654;
void solve()
{
    ll n,m;
    set<ll> st;
    map<ll,ll> mp;
    cin>>n>>m;
    ll v[m];
    string s[m];
    for(int i=0;i<m;i++)
    {
        cin>>v[i]>>s[i];

    }
    ll wa=0,ac=0;
    for(int i=0;i<m;i++)
    {
        if(st.count(v[i])!=1 && s[i]=="WA")
            mp[v[i]]++;
        else if(st.count(v[i]) != 1 && s[i]=="AC")
        {
            st.insert(v[i]);
            wa+=mp[v[i]];
            ac++;

        }


    }
    cout<<ac<<" "<<wa<<endl;

}
int main()
{
#ifndef oj
    //freopen("input", "r", stdin);
    //freopen("output.txt","w",stdout);
#endif
    // system("cls");
    //getchar();
    // cout<<adj[1][0];

    int t,sum=0;
    // cin>>t;
    t=1;
    while(t--)
    {
        solve();

    }


}




Measured memory_bytes: 17408
#include <bits/stdc++.h>
typedef long long LL;
#define SORT(c) sort((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

using namespace std;
int main(void)
{
  for(;;){
    int n;
    cin >> n;
    if(!n) return 0;
    vector<int> l;
    double H=1e+5;
    l.resize(n);
    REP(i,n) cin >> l[i];
    int anss,ansa,ansc;
    REP(s,16) REP(a,16) REP(c,16){
      vector<int> r;
      r.resize(n);
      r[0]=(a*s+c)%256;
      REP(i,n-1) r[i+1]=(a*r[i]+c)%256;
      vector<int> his;
      his.assign(256,0);
      REP(i,n) ++his[(l[i]+r[i])%256];
      double tmpH=0.0;
      REP(i,256)
	if(his[i]) tmpH-=1.0*his[i]/n*log(1.0*his[i]/n);
      if(tmpH+1e-6<H){
	anss=s;
	ansa=a;
	ansc=c;
	H=tmpH;
      }
    }
    cout << anss << ' ' << ansa << ' ' << ansc << endl;
  }
}

Measured memory_bytes: 1240
def larger(x, y):
	if x > y:
		return x
	return y

N = int(input())
S = input()
max = 0
X = 0
for i in range(0, N):
	if S[i] == 'I':
		X += 1
	elif S[i] == 'D':
		X -= 1
	max = larger(max, X)
print(max)

Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, begin, end) for (ll i = (begin); i < (end); i++)
#define REP(i, n) FOR(i, 0, n)
#define IFOR(i, begin, end) for (ll i = (begin)-1; i >= (end); i--)
#define IREP(i, n) IFOR(i, n, 0)
#define SORT(a) sort(a.begin(), a.end())
#define ISORT(a) sort(a.begin(), a.end(), greater<ll>())
#define REVERSE(a) reverse(a.begin(), a.end())
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v)                                                              \
  cout << #v << "=(" << v[0];                                                  \
  FOR(i_debug, 1, v.size()) { cout << "," << v[i_debug]; }                     \
  cout << ")" << endl;
#define mdebug(m)                                                              \
  cout << #m << "=" << endl;                                                   \
  REP(i_debug, m.size()) {                                                     \
    REP(j_debug, m[i_debug].size()) { cout << m[i_debug][j_debug] << ","; }    \
    cout << endl;                                                              \
  }
#define Lower_bound(v, x)                                                      \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x)                                                      \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)

#define ll long long
// #define f first
// #define s second
#define mp make_pair
#define pb push_back
#define INF 1000000000000000000

using vec = vector<ll>;
using mat = vector<vec>;
using Pii = pair<ll, ll>;
using PiP = pair<ll, Pii>;
using PPi = pair<Pii, ll>;
using bvec = vector<bool>;
using Pvec = vector<Pii>;

template <typename T> void readv(vector<T> &a) { REP(i, a.size()) cin >> a[i]; }
void readv_m1(vector<int> &a) {
  REP(i, a.size()) {
    cin >> a[i];
    a[i]--;
  }
}

ll mod = 1000000007;

int main() {
  ll S, W;
  cin >> S >> W;

  if (W >= S)
    cout << "unsafe" << endl;
  else
    cout << "safe" << endl;

  return 0;
}

Measured memory_bytes: 3620
import java.util.*;
import java.util.stream.Collectors;

public class Main{
    Scanner in = new Scanner(System.in);

    void solve(){
        List<String> list = Arrays.asList(in.nextLine().replaceAll(",|\\."," ").split("[ ]+"));
        System.out.println(String.join(" ", list.stream().filter(s -> 2 < s.length() && s.length() < 7).collect(Collectors.toList())));
    }
    
    public static void main(String[] args){
        new Main().solve();    
    }
}

Measured memory_bytes: 32716
import sys
from bisect import bisect_left as bl
readline = sys.stdin.readline

def euler_tour(root, Edge):
    N = len(Edge)
    stack = [root]
    used = [False]*N
    tour = []
    down = []
    dist = [0]*N
    ta = tour.append
    sa = stack.append
    St = [None]*N
    En = [None]*N
    cnt = -1
    while stack:
        cnt += 1
        vn = stack.pop()
        ta(vn)
        
        if St[vn] is None:
            St[vn] = cnt
        En[vn] = cnt
        if used[vn]:
            continue
        for vf in Edge[vn]:
            if used[vf]:
                sa(vf)
            else:
                dist[vf] = 1+dist[vn]
                down.append(vf)
        stack.extend(down)
        down = []
        used[vn] = True
    return St, En, tour, dist





N = int(readline())
A = list(map(int, readline().split()))
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)

_, _, L, dist = euler_tour(0, Edge) 

table = [None]*N
table[0] = (-1, -1)
dp = [A[0]]
pre = 0
Ans = [None]*N
for l in L[1:]:
    al = A[l]
    if dist[pre] > dist[l]:
        x, j = table[pre]
        if x == -1:
            dp.pop()
        else:
            dp[j] = x
    else:
        if dp[-1] < al:
            dp.append(al)
            table[l] = (-1, -1)
        else:
            idx = bl(dp, al)
            x = dp[idx]
            dp[idx] = al
            table[l] = (x, idx)
    pre = l
    Ans[l] = len(dp)
        
print('\n'.join(map(str, Ans)))

Measured memory_bytes: 170012
parseline(str) = parse.(Int, split(str))
function DoubleDots()
    N, M = parseline(readline())
    graph = [Int[] for _ in 1:N]
    for ab in parseline.(readlines())
        isempty(ab) && continue
        a, b = ab
        push!(graph[a], b)
        push!(graph[b], a)
    end
    torch = zeros(Int, N)
    torch[1] = 1
    que = [1]
    while !isempty(que)
        b = popfirst!(que)
        for a in graph[b]
            torch[a]==0 && (push!(que, a); torch[a] = b)
        end
    end
    println("Yes")
    for t in torch[2:end]
        println(t)
    end
end
DoubleDots()

Measured memory_bytes: 247672
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

int main(void) {
	int H, W, N, *a, **map, h=0, w=0;
	scanf("%d %d %d", &H, &W, &N);
	a = (int *)malloc(N * sizeof(int));
	for (int i = 0; i < N; i++) {
		scanf("%d", &a[i]);
	}
	map = (int **)malloc(H * sizeof(int *));
	for (int i = 0; i < H; i++) {
		map[i] = (int *)malloc(W * sizeof(int));
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < a[i]; j++) {
			map[h][w] = i+1;
			if (h % 2 == 0) { 
				if (w == W - 1) {
					h++;
				}
				else {
					w++;
				}
			}
			else {
				if (w == 0) {
					h++;
				}
				else {
					w--;
				}
			}
		}
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			printf("%d", map[i][j]);
			if (j != W - 1) {
				printf(" ");
			}
		}
		printf("\n");
	}
	return 0;
}


Measured memory_bytes: 384
mod io{
    use std::io::*;
    pub fn read<T: ::std::str::FromStr>()->T{
        let stdin=stdin();
        let ret=stdin.lock().bytes().map(|c|c.unwrap()as char)
        .skip_while(|c|c.is_whitespace())
        .take_while(|c|!c.is_whitespace())
        .collect::<String>().parse().ok().unwrap();
        ret
    }
}
use io::read;
fn main(){
    let a=read::<i64>();
    let b=read::<i64>();
    let c=read::<i64>();
    println!("{}",b/c-(a-1)/c+(if a==0&&c>1{1}else{0}));
}


Measured memory_bytes: 4352
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
ll gcdll(ll a, ll b ){
    ll r, tmp;
    if(a<b){
        tmp = a;
        a = b;
        b = tmp;
    }
    r = a % b;
    while(r!=0){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a,b;
    cin >> a >> b;
    ll x = gcdll(a,b);
    ll y = x;
    ll ans = 0;
    ll k=2;
    while(x>1){
        bool f=true;
        while(x%k==0){
            if(f){
                ans++;
                f=false;
            }
            x/=k;
        }
        k++;
        if(k*k>y){
            if(x>1){
                ans++;
            }
            break;
        }
    }
    cout << ans+1 << endl;
    return 0;
}

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

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
const int maxn = 100050;

long long t[maxn], ans;
int n;

long long gcd(long long a,long long b){return !b?a:gcd(b,a%b);}

int main()
{
	scanf("%d",&n);
	fo(i,1,n) scanf("%lld",&t[i]);
	ans = t[1];
	fo(i,2,n) ans = ans/gcd(t[i],ans)*t[i];
	printf("%lld\n",ans);
	return 0;
}

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

int main(){
    string s,t;
    cin >> s >> t;
    int n = s.size();
    int ans = 0;
    rep(i,n){
        if(s[i] != t[i])ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3916
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
#include<complex>

using namespace std;

#define ll long long
#define ld long double
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

const double PI=acos(-1);
const double EPS=1e-9; //うまくいかなかったらゆるめる

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef vector<pii> vp;
typedef vector<vi> vvi;

int gcd(int a, int b){if(b==0) return a;return gcd(b,a%b);}
int lcm(int a, int b){return a/gcd(a,b)*b;}

#define MAX 200005

long long fac[MAX], finv[MAX], inv[MAX];

void init() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int 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;
    }
}

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



signed main(void) {
    init();
    int n,k;
    cin >> n >> k;
    map<int,int> ma;
    vi a(n);
    rep(i,n)cin >> a[i],ma[a[i]]++;
    sort(all(a));
    int ans = 0;
    int small = 0;
    for(auto x:ma){
        int cnt = x.second;
        int num = x.first;
        int large = n - cnt - small;
        //cout << num << " " << cnt << " " << small << " " << large << endl;
        //numがmaxになるとき、small+cntからk個えらんでいてsmallからk個選んでいないとき
        int ma = ncr(small+cnt, k) - ncr(small,k) + MOD;
        ma %= MOD;
        int t1 = ma*num%MOD;
        //numがminになるとき、large+cntからk個えらんでいてlargeからk個選んでいないとき
        int mi = ncr(large+cnt, k) - ncr(large,k) + MOD;
        mi %= MOD;
        int t2 = mi*num%MOD;
        ans += t1 - t2 + MOD;
        ans %= MOD;

        small += cnt;
    }
    cout << ans << endl;
}


Measured memory_bytes: 11520
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

char s[200001];
int a[200000];
int b[200000];
int f[200000];
vector <int> v[200000];

int main() {
    int n, m, i;
    queue <int> q;
    
    scanf("%d %d", &n, &m);
    scanf("%s", s);
    
    for (i = 0; i < m; i++) {
        int x, y;
        
        scanf("%d %d", &x, &y);
        
        x--;
        y--;
        
        if (x == y) {
            v[x].push_back(x);
            
            if (s[x] == 'A') {
                a[x]++;
            } else {
                b[x]++;
            }
        } else {
            v[x].push_back(y);
            v[y].push_back(x);
            
            if (s[x] == 'A') {
                a[y]++;
            } else {
                b[y]++;
            }
            
            if (s[y] == 'A') {
                a[x]++;
            } else {
                b[x]++;
            }
        }
    }
    
    for (i = 0; i < n; i++) {
        if (a[i] == 0 || b[i] == 0) {
            f[i] = 1;
            q.push(i);
        }
    }
    
    while (!q.empty()) {
        int x = q.front();
        
        q.pop();
        
        for (i = 0; i < v[x].size(); i++) {
            int y = v[x][i];
            
            if (s[x] == 'A') {
                a[y]--;
            } else {
                b[y]--;
            }
            
            if (f[y] == 0 && (a[y] == 0 || b[y] == 0)) {
                f[y] = 1;
                q.push(y);
            }
        }
    }
    
    for (i = 0; i < n; i++) {
        if (f[i] == 0) {
            puts("Yes");
            
            return 0;
        }
    }
    
    puts("No");
    
    return 0;
}


Measured memory_bytes: 13184
#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);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define dunk(a) cout << (a) << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n, h;
	cin >> n >> h;
	vector<ll> a(n), b(n);
	rep(i, n) cin >> a[i] >> b[i];

	ll res = 0;
	ll t = 0;
	sort(rall(a));

	rep(i, n) {
		if (b[i] > a[0]) {
			res++;
			t += b[i];
		}
	}

	if (t >= h) {
		sort(rall(b));
		ll p = 0;
		ll ans = 0;
		rep(i, n) {
			if (b[i] > a[0]) {
				p += b[i];
				ans++;
			}
			if (p >= h) {
				dunk(ans);
				break;
			}
		}
	}
	else {
		ll ans = res;
		h -= t;
		ans += h % a[0] == 0 ? h / a[0] : int(h / a[0]) + 1;
		dunk(ans);
	}

	return 0;
}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define _GLIBCXX_DEBUG
#define fi first
#define se second

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vd = vector<double>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vvd = vector<vd>;
using vvvi = vector<vvi>;
using vvvll = vector<vvll>;
using vvvd = vector<vvd>;

const double pi=acos(-1);
const ll MOD=1e9+7;
const ll INF=(1LL<<60);

vector< int64_t > divisor(int64_t n) {
    vector< int64_t > ret;
    for(int64_t i = 1; i * i <= n; i++) {
        if(n % i == 0) {
            ret.push_back(i);
            if(i * i != n) ret.push_back(n / i);
        }
    }
sort(begin(ret), end(ret));
return (ret);
}

ll f(ll a,ll b){
    return a*a*a*a+a*a*a*b+a*a*b*b+a*b*b*b+b*b*b*b;
}

int main() {
    ll x;
    cin>>x;
    for (ll i=0;i<200;i++){
        for (ll j=-200;j<200;j++){
            ll n=i;
            ll m=j;
            ll i1=n*n*n*n*n;
            ll i2=m*m*m*m*m;
            if (i1-i2==x){
                cout<<i<<" "<<j<<endl;
                return 0;
            }
        }
    }



    return 0;
}

Measured memory_bytes: 3600
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int W =sc.nextInt();
        int H =sc.nextInt();
        int x =sc.nextInt();
        int y =sc.nextInt();
        int r =sc.nextInt();
        if(x+r>W){
            System.out.println("No");
        }else if(y+r>H){
            System.out.println("No");
        }else if(0>x-r){
            System.out.println("No");
        }else if(0>y-r){
            System.out.println("No");
        }else{
            System.out.println("Yes");
        }
    }
}


Measured memory_bytes: 26276
#include<cstdio>
#include<vector>
#include<algorithm>
#include <functional>
using namespace std;
using ll = long long;

int main(){
	int N;
	scanf("%d", &N);
	int A[N];
	for (int i = 0; i < N; ++i) scanf("%d", A + i);
	vector<int> plus;
	ll sum = 0;
	int change = 0;
	for (int i = 0; i < N; ++i){
		int tmp;
		scanf("%d", &tmp);
		A[i] -= tmp;
		if(A[i] > 0) plus.push_back(A[i]);
		else if(A[i] < 0){
			sum += A[i];
			change++;
		}
	}
	int answer = 0;
	sort(plus.begin(), plus.end(), greater<int>());
	while(sum < 0 && answer < plus.size()){
		sum += plus[answer++];
	}
	if(sum < 0) printf("-1\n");
	else printf("%d\n", change + answer);
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <utility>
#include <functional>
#include <deque>
#include <cctype>
#include <stack>
#include <bitset>

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

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

const ll mod = 1000000007;
const ll INF = 1 << 30;
const ll INF2 = 9000000000000000000LL;
bool fl = true;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
std::string abc = "abcdefghijklmnopqrstuvwxyz";
struct edge { ll to, cost; };
struct edge1 { ll from, to, cost; };
double pai = 3.141592653589793;
std::vector<P>v[100010];

int main() {
	int n;
	std::cin >> n;
	std::cout << 0 << std::endl;
	std::string s[100010];
	std::cin >> s[0];
	if (s[0] == "Vacant")exit(0);
	std::cout << n - 1 << std::endl;
	std::cin >> s[n - 1];
	if (s[n - 1] == "Vacant")exit(0);
	int l = 0, r = n - 1;
	for (int i = 0;i < 18;i++) {
		int mid = (l + r) / 2;
		std::cout << mid << std::endl;
		std::cin >> s[mid];
		if (s[mid] == "Vacant")exit(0);
		else if (s[l] == s[mid] && (mid - l) % 2 == 1)r = mid, s[r] = s[mid];
		else if (s[l] != s[mid] && (mid - l) % 2 == 0)r = mid, s[r] = s[mid];
		else if (s[r] != s[mid] && (r - mid) % 2 == 0)l = mid, s[l] = s[mid];
		else if (s[r] == s[mid] && (r - mid) % 2 == 1)l = mid, s[l] = s[mid];
	}
}

Measured memory_bytes: 4048
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>
using namespace std;

int main() {
	vector<bool> exist(26, false);
	char buf;
	while (cin >> buf) {
		exist[buf - 'a'] = true;
	}
	int answer = 0;
	while (answer < 26) {
		if (!exist[answer]) {
			printf("%c\n", 'a' + answer);
			return 0;
		}
		answer++;
	}
	cout << "None" << endl;
}

Measured memory_bytes: 256