akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

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

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

const string YES = "Yes";
const string NO = "No";

int main(){
    string s;
    cin >> s;
    int n = s.size();
    int m = (n - 1) / 2;
    if (m==1) {
        if (s[0] != s[2]) {
            cout << NO << endl;
            return 0;
        }
    }
    rep(i, m/2+1) {
        if (s[i]!=s[m-1-i]||s[i]!=s[m+1+i]||s[i]!=s[n-1-i]) {
            cout << NO << endl;
            return 0;
        } 
    }
    cout << YES << endl;
    return 0;
}



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

if N == 1:
	ans = 3
elif N == 2:
	ans = 3
else:
	ans = 1
	while N != 1:
		if N%2 == 0:
			N = N//2
			ans += 1
		else:
			N = 3*N+1
			ans += 1

print(ans+1)

Measured memory_bytes: 3060
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 100291

int isPrime[ MAX_N + 1 ] = { 0, 0, 1, 1 };

void quickSort( int *, int, int );
int median( int, int, int );
void insertionSort( int *, int );

int main( void ) {
	int i, j, N, P, cnt, p[ 22 ], sum[ 253 ];

	for ( i = 5; i <= MAX_N; i += 6 )
		isPrime[ i ] = 1;

	for ( i = 7; i <= MAX_N; i += 6 )
		isPrime[ i ] = 1;

	for ( i = 5; i * i <= MAX_N; i += 6 )
		if ( isPrime[ i ] )
			for ( j = i * 2; j <= MAX_N; j += i )
				isPrime[ j ] = 0;

	for ( i = 7; i * i <= MAX_N; i += 6 )
		if ( isPrime[ i ] )
			for ( j = i * 2; j <= MAX_N; j += i )
				isPrime[ j ] = 0;

	for ( ; scanf( "%d %d", &N, &P ), N != -1; printf( "%d\n", sum[ P - 1 ] ) ) {
		cnt = 0;
		for ( i = N + 1; cnt < 22; i++ )
			if ( isPrime[ i ] )
				p[ cnt++ ] = i;

		cnt = 0;
		for ( i = 0; i < 22; i++ )
			for ( j = i; j < 22; j++ )
				sum[ cnt++ ] = p[ i ] + p[ j ];

		quickSort( sum, 0, 252 );
	}

	return 0;
}

void quickSort( int *data, int l, int r ) {
	if ( l < r ) {
		int i = l, j = r, pivot = median( data[ i ], data[ ( i + j ) / 2 ], data[ j ] ), tmp;

		while ( 1 ) {
			for ( ; data[ i ] < pivot; i++ ) ;
			for ( ; pivot < data [ j ]; j-- ) ;
			if ( i >= j )
				break;

			tmp = data[ i ];
			data[ i ] = data[ j ];
			data[ j ] = tmp;

			i++;
			j--;
		}

		if ( i - l < 20 )
			insertionSort( data + l, i - l );
		else
			quickSort( data, l, i - 1 );

		if ( r - j < 20 )
			insertionSort( data + j + 1, r - j );
		else
			quickSort( data, j + 1, r );
	}
}

int median( int x, int y, int z ) {
	if ( x < y )
		if ( y < z )
			return y;
		else if ( z < x )
			return x;
		else
			return z;
	else if ( z < y )
		return y;
	else if ( x < z )
		return x;
	else
		return z;
}

void insertionSort( int *data, int n ) {
	int i, j, tmp;

	for ( i = 1; i < n; i++ ) {
		tmp = data[ i ];

		for ( j = i; j && data[ j - 1 ] > tmp; j-- )
			data[ j ] = data[ j - 1 ];

		data[ j ] = tmp;
	}
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const int MX = 52;
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int s[MX][MX];
    int h,w;
    cin>>h>>w;

    FOR(i,1,h+1) FOR(j,1,w+1){
        char c;
        cin>>c;
        s[i][j] = (c=='#')?1:0;
    }

    FOR(i,1,h+1) FOR(j,1,w+1){
        if(s[i][j]==1){
            if( (s[i-1][j] | s[i][j-1] | s[i+1][j] | s[i][j+1]) == 0 ){
                puts("No");
                return 0;
            }
        }
    }

    puts("Yes");
    return 0;
}

Measured memory_bytes: 256
using System;

namespace _173_a
{
    internal class Payment
    {
        private static void Main(string[] args)
        {
            var price = int.Parse(Console.ReadLine() ?? throw new InvalidOperationException());
            if (price % 1000 == 0)
            {
                Console.WriteLine(0);
            }
            else
            {
                Console.WriteLine(1000 - price % 1000);
            }
        }
    }
}

Measured memory_bytes: 27436
#include<iostream>
using namespace std;
int main(){
    int a,b,c,k;
    cin >> a >> b >> c >> k;
   
    if(k <= a)cout << k << endl;
    else if(k <= a+b)cout << a << endl;
    else cout << a - (k-(a+b)) << endl;
    return 0;
}


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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	long long int n,x,l;
	cin>>n>>x;
	vector<long long int> v;
	while(n--){
		cin>>l;
		v.push_back(l);
	}
	long long int c=0,temp=0;
	for(long long int i=0;i<v.size();i++){
		temp+=v[i];
		if(temp<=x){
			c++;
		}
	}
	cout<<c+1;
	return 0;
}

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

int main() {

	char w[101];
	scanf("%s", w);
	map<char, int> ma;
	int n = strlen(w);
	for(int i = 0; i < n; i++) {
		ma[w[i]] += 1;
	}
	bool ans = true;
	for(int i = 0; i < (int)ma.size(); i++) {
		if(ma[i] % 2 != 0){
			ans = false;
			break;
		}
	}
	if(ans) {
		printf("%s\n", "Yes");
	}else {
		printf("%s\n", "No");
	}
}


Measured memory_bytes: 256
N = int(input())
a = list(map(int,input().split()))

ans = "No"
two_mul = []
four_mul = []
for i in a:
    if i % 2 == 0 and i % 4 != 0:
        two_mul.append(i)
    elif i % 4 == 0:
        four_mul.append(i)

if len(four_mul) == 0:
    if len(two_mul) == N:
        ans = "Yes"
else:
    if len(two_mul) == 0:
        if len(four_mul) >= N//2:
            ans = "Yes"
    else:
        if ((N - len(two_mul))+1)//2 <= len(four_mul):
            ans = "Yes"

print(ans)

Measured memory_bytes: 14252
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll LLINF = 9223372036854775807;
const int MOD = 1000000007;

int main() {
  int N; cin >> N;
  cout << "ABC" << N << endl;
  return 0;
}

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

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

int main() {
    int n; cin >> n;
    cout << n << ':';
    if (is_prime(n)) {
        cout << " " << n << endl;
        return 0;
    }
    int i = 2;
    while (n > 1) {
        if (n % i == 0) {
            cout << " " << i;
            n /= i;
        } else {
            i++;
        }
    }
    cout << endl;
}


Measured memory_bytes: 3104
# ABC051 C - Back and Forth
sx,sy,tx,ty = map(int, input().split())
x=-sx
y=-sy
sx+=x
sy+=y
tx+=x
ty+=y
tx=abs(tx)
ty=abs(ty)

ans=[]
ans+=['U']*ty
ans+=['R']*tx
ans+=['D']*ty
ans+=['L']*tx
ans+=['L']
ans+=['U']*(ty+1)
ans+=['R']*(tx+1)
ans+=['D']
ans+=['R']
ans+=['D']*(ty+1)
ans+=['L']*(tx+1)
ans+=['U']

print(''.join(ans))

Measured memory_bytes: 3188
def read_data():
    N, M = map(int, input().split())
    Es = [[] for _ in range(N)]
    Cs = [[float('inf')] * N for n in range(N)]
    for m in range(M):
        a, b, c = map(int, input().split())
        Es[a - 1].append(b - 1)
        Cs[a - 1][b - 1] = -c
    return N, M, Es, Cs

def solve(N, M, Es, Cs):
    dist = [float('inf')] * N
    dist[0] = 0
    for i in range(N + 1):
        for v in range(N):
            Cv = Cs[v]
            for e in Es[v]:
                c = Cv[e]
                if dist[v] != float('inf') and dist[e] > dist[v] + c:
                    dist[e] = dist[v] + c
                    if (i == N - 1):
                        d = dist[N - 1]
                    if (i == N):
                        if d != dist[N - 1]:
                            return 'inf'
    return -dist[N - 1]

N, M, Es, Cs = read_data()
print(solve(N, M, Es, Cs))


Measured memory_bytes: 13172
import math
 
ans = [0 for i in range(31)]
ans[0] = 1
ans[1] = 1
ans[2] = 2
for i in range(3, 31):
    ans[i] = ans[i-1] + ans[i-2] + ans[i-3]
 
while True:
    N = int(input())
    if N == 0:
        break
 
    print(math.ceil(ans[N]/3650))


Measured memory_bytes: 5668
n,m,x=map(int,input().split())
C=[[] for i in range(n)]
for i in range(n):
  A=list(map(int,input().split()))
  C[i]=[A[0],A[1:]]
  
  
cost=float("inf")
for bit in range(1<<n):
  #print([j for j in range(n) if bit>>j & 1 ])
  for i in range(m):
    if sum([C[j][1][i] for j in range(n) if bit>>j & 1 ])<x:
      break
  else:
    cost=min(cost, sum([C[j][0] for j in range(n) if bit>>j & 1 ]))
    #print(cost)
print(cost if cost<float("inf") else -1)
               
               
              

Measured memory_bytes: 9164
import sys
S = input()

def isKaibun(txt, n):
    for i in range(n):
        if txt[i] == txt[-(i+1)]:
            continue
        else:
            print("No")
            sys.exit()
    return 0

l = len(S)
isKaibun(S, l//2)

l_b = (l-1)//2 
isKaibun(S[:l_b], l_b//2)

l_a = (l+3)//2
isKaibun(S[l_a-1:], (l-l_a)//2)

print("Yes")

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

int main() {
  int N;
  cin>>N;
  vector<int>a(N);
  
  for(int i=0;i<N;i++){
    cin>>a[i];
  }
  sort(a.begin(),a.end());
  
  int min=a[0];
  int max=a[N-1];
  
  cout<<max-min<<endl;
}


Measured memory_bytes: 256
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define l first
#define r second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const int N=200010;
int n,q;
struct Segment
{
    struct node
    {
        int l,r,val,lazy;
    }tree[N*4];
    void build(int u,int l,int r)
    {
        tree[u]={l,r,n,n+1};
        if(l==r) return;
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
    }
    void pushdown(int u)
    {
        if(tree[u].lazy==n+1) return;
        tree[u<<1].val=min(tree[u<<1].val,tree[u].lazy);
        tree[u<<1|1].val=min(tree[u<<1|1].val,tree[u].lazy);     
        tree[u<<1].lazy=min(tree[u<<1].lazy,tree[u].lazy);
        tree[u<<1|1].lazy=min(tree[u<<1|1].lazy,tree[u].lazy);
        tree[u].lazy=n+1;
    }
    void modify(int u,int l,int r,int val)
    {
        if(tree[u].l>=l&&tree[u].r<=r)
        {
            tree[u].lazy=min(tree[u].lazy,val);
            tree[u].val=min(tree[u].val,val);
            return;
        }
        pushdown(u);
        int mid=tree[u].l+tree[u].r>>1;
        if(l<=mid) modify(u<<1,l,r,val);
        if(r>mid) modify(u<<1|1,l,r,val);
    }
    int query(int u,int p)
    {
        if(tree[u].l==tree[u].r) return tree[u].val;
        pushdown(u);
        int mid=tree[u].l+tree[u].r>>1;
        if(p<=mid) return query(u<<1,p);
        else return query(u<<1|1,p);
    }
}a,b;
int row,col;
int main()
{
    IO;
    int T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>q;
        a.build(1,1,n);
        b.build(1,1,n);
        ll res=1ll*(n-2)*(n-2);
        col=row=n;
        while(q--)
        {
            int op,x;
            cin>>op>>x;
            if(op==1)
            {
                col=min(col,x);
                res-=b.query(1,x)-2;
                a.modify(1,1,row,x);
            }
            else
            {
                row=min(row,x);
                res-=a.query(1,x)-2;
                b.modify(1,1,col,x);
            }
        }
        cout<<res<<'\n';
    }
    return 0;
}

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

int main(){
  int W,H, x, y;
  double s;
  cin >> W >> H >> x >> y;

  s = (double)W * (double)H / 2.0;

  if(W % 2 == 0 && H % 2 == 0){
    if(W / 2 == x && H / 2 == y){
      cout << s << " " << 1 << endl;
    }else{
      cout << s << " " << 0 << endl;
    }
  }else{
      cout << s << " " << 0 << endl;
  }
}

Measured memory_bytes: 256
#define M 200
T[M],A[M],B[M],C[M],Z[M][M],d;
main(D,n,i,j,x){
	memset(Z,0xff,sizeof(Z));
	for(scanf("%d%d",&D,&n);d<D;d++)scanf("%d",T+d);
	for(i=0;i<n;i++)if(scanf("%d%d%d",A+i,B+i,C+i),A[i]<=T[0]&&T[0]<=B[i])Z[0][i]=0;
	for(d=0;d<D-1;d++)for(i=0;i<n;i++)if(~Z[d][i])for(j=0;j<n;j++)if(A[j]<=T[d+1]&&T[d+1]<=B[j])if(x=Z[d][i]+abs(C[i]-C[j]),Z[d+1][j]<x)Z[d+1][j]=x;
	for(x=i=0;i<n;i++)if(x<Z[D-1][i])x=Z[D-1][i];
	printf("%d\n",x);
exit(0);}

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

using ll =  long long;
using pint =  pair<int,int>;

#define rep(i,n) for(int (i)=0,temp=(int)(n);(i)<temp;++(i))
#define repi(i,start,end) for(int (i)=(start),temp=(int)(end);i<(end);++(i))
#define rfor(x,v) for(const auto& (x) : (v))
#define all(x) (x).begin(),(x).end()
#define SORT(v, n) sort((v), (v)+(n))
#define vsort(v) sort((v).begin(), (v).end())
#define vfsort(v,lambda) sort(all((v)),(lambda))
#define vint vector<int>
#define vvint vector<vector<int>> //vvint v(n,vint(n))
#define vin(v) rep(i,(v).size()) {cin >> (v)[i];}
//最終奥義 #define int long long
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
//lambda: [&](int x, int y){return x<y;}

signed main(void){
  int n,m;cin>>n>>m;
  vector<pint> ab(m);
  rep(i,m)cin>>ab[i].first>>ab[i].second;
  vfsort(ab,[](pint x,pint y){
      if(x.second!=y.second)return x.second<y.second;
      else return x.first<y.first;
      });
  //rep(i,m)cout << ab[i].first << " " << ab[i].second << endl;
  
  int ans=0;
  int pos=0;
  rep(i,m){
    if(ab[i].first<pos)continue;
    ans++;
    pos=ab[i].second;
  }
  cout << ans << endl;
}


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

const double pi  = 2 * acos(0.0);
const double eps = 1e-8;

#define REP(i,a,b) for(int i=(a); i<(b);++i)
#define rep(i,n) REP(i,0,n)
#define INF (1<<29)
#define INFLL (1LL<<62)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

int main(void) {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;

  vector<int> a(n);
  ll cand[2] = {};

  rep(i, n) cin >> a[i];

  ll acc = 0;
  rep (i, n) {
    acc += a[i];
    if (i % 2 == 0) {
      if (acc <= 0) {
        cand[0] += abs(acc) + 1;
        acc = 1;
      }
    } else {
      if (acc >= 0) {
        cand[0] += abs(acc) + 1;
        acc = -1;
      }
    }
  }

  acc = 0;
  rep (i, n) {
    acc += a[i];
    if (i % 2 == 0) {
      if (acc >= 0) {
        cand[1] += abs(acc) + 1;
        acc = -1;
      }
    } else {
      if (acc <= 0) {
        cand[1] += abs(acc) + 1;
        acc = 1;
      }
    }
  }

  ll ans = min(cand[0], cand[1]);
  cout << ans << endl;

  return 0; 
}


Measured memory_bytes: 640
def ad(a,bank):
	if a not in bank:
		bank[a] = 1
	else:
		bank[a] += 1

def rp(a,b,bank):
	ans = 0
	if a in bank:
		t = bank[a]
		ans = t
		bank[a] = 0
		if b not in bank:
			bank[b] = t
		else:
			bank[b] += t
		
	return ans
# your code goes here
n = int(input())
arr = list(map(int, input().split()))

bank = dict()
su = 0

for a in arr:
	ad(a,bank)
	su += a

q = int(input())
for i in range(q):
	b,c = map(int, input().split())
	t = rp(b,c,bank)
	if b in bank:
		su = su - (t*b) + (t*c)
	
	print(su)


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

using namespace std;
typedef long long ll;




int main()
{
    
    int D;
    cin >> D;
    if (D == 25) {
        cout << "Christmas" << endl;
    }else if (D == 24) {
        cout << "Christmas Eve" << endl;
    }else if (D == 23) {
        cout << "Christmas Eve Eve" << endl;
    }else if (D == 22) {
        cout << "Christmas Eve Eve Eve" << endl;
    }
    
    return 0;
}



Measured memory_bytes: 256
def f_b():
    n, *d = map(int, open(0).read().split())
    c = [0]*(max(d)+1)
    for i in range(n):
        c[d[i]] += 1

    a = 0 if d[0]!=0 or c[0]>1 else 1
    m = 998244353
    for i in range(1, len(c)):
        a = a*c[i-1]**c[i]%m

    print(a)

if __name__ == "__main__":
    f_b()


Measured memory_bytes: 13956
import sys
import numpy as np
def proc(C, L, R, Order, N, Q):
    pl = pr = 0
    ans = 0
    A = np.zeros(N+1, dtype=np.int32)
    Ans = np.zeros(Q, dtype=np.int32)
    for idx_LR in Order:
        l = L[idx_LR]
        r = R[idx_LR]
        while pr < r:
            pr += 1
            c = C[pr]
            if A[c] == 0:
                ans += 1
            A[c] += 1
        while pl > l:
            pl -= 1
            c = C[pl]
            if A[c] == 0:
                ans += 1
            A[c] += 1
        while pr > r:
            c = C[pr]
            A[c] -= 1
            if A[c] == 0:
                ans -= 1
            pr -= 1
        while pl < l:
            c = C[pl]
            A[c] -= 1
            if A[c] == 0:
                ans -= 1
            pl += 1
        Ans[idx_LR] = ans
    return Ans

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    cc = CC('my_module')
    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)
    build = cc_export(proc, "i4[:](i4[:],u4[:],u4[:],i8[:],i4,i4)")
    cc.compile()

from my_module import proc
def main():
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    C = np.empty(N+1, dtype=np.int32)
    C[0] = 0
    C[1:] = np.array(input().split(), dtype=np.int32)
    LR = np.array(sys.stdin.buffer.read().split(), dtype=np.uint32)
    L = LR[::2]
    R = LR[1::2]
    B = L>>9<<20|R
    Idx = (L>>9&1).astype(np.bool)
    B[Idx] = L[Idx]>>9<<20|(1<<20)-R[Idx]
    Order = np.argsort(B)
    Ans = proc(C, L, R, Order, N, Q)
    print("\n".join(map(str, Ans.tolist())))

main()


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

int main() {
  ll h;
  cin >> h;

  ll bunretsu = 1;
  ll attack = 0;
  while (true) {
    if (h < 2) {
      attack += bunretsu;
      break;
    } else {
      h = h/2;
      attack += bunretsu;
      bunretsu *= 2;
    }
  }
  
  cout << attack << endl;
  return 0;
}

// 1 -> 1
// 2 -> 1 + 2
// 3 -> 1 + 2
// 4 -> 1 + 2 + 4
// 5 -> 1 + 2 + 4
// 6 -> 1 + 2 + 4
// 7 -> 1 + 2 + 4
// 8 -> 1 + 2 + 4 + 8


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
string S;
ll mo=1000000007;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	int cur=0;
	ll ret=1;
	FORR(c,S) {
		if(c=='B') {
			if(cur%2==1) {
				ret=ret*cur%mo;
				cur--;
			}
			else {
				cur++;
			}
		}
		else {
			if(cur%2==1) {
				cur++;
			}
			else {
				ret=ret*cur%mo;
				cur--;
			}
		}
	}
	if(cur>0) ret=0;
	FOR(i,N) ret=ret*(i+1)%mo;
	cout<<ret<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


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

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

ll lcm(ll a, ll b){
  return a/gcd(a,b) * b;
}
ll func2(ll n){
  ll res = 0;
  while(n%2 == 0){
    n /= 2;
    res++;
  }
  return res;
}

ll zyou(ll a,ll b){//a＾b
  ll res = 1;
  for(int i = 1;i<=b;i++){
    res *= a;
  }
  return res;
}
struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t),weight(w){ }
};

typedef pair<int,int> P;
using Graph = vector<vector<Edge>>;

ll calc(ll a, ll b, ll p){//aのb乗をpで割った余り
  if(b == 0) return 1;

  else if(b%2 == 0){
    ll d = calc(a,b/2,p);
    return (d*d)%p;
  }
  else if(b%2 == 1){
    return (a * calc(a,b-1,p))%p;
  }
}



bool is_prime(int n){//nが素数であるかどうか判定 iで割り切れると素数でない
    if(n == 1) return false;//1は例外
    for(int i = 2;i*i <= n;i++){
        if(n%i == 0) return false;
    }
    
    return true;
}
int dfs(int x,int y,int H,int W,vector<vector<char>> &masu){
  if(masu[x][y] == '#'){

  }
}
bool palin(string S){
  int n = S.size();
  bool flag = true;
  if(n%2 == 0){
    for(int i = 0;i<=n/2-1;i++){
      if(S[i] != S[n-i-1]){
        flag = false;
        break;
      }
    }
  }
  else if(n%2 == 1){
    for(int i = 0;i<=n/2-1;i++){
      if(S[i] != S[n-i-1]){
        flag = false;
        break;
      }
    }
  }
  return flag;
}
int main(){
  int N,K;
  cin >> N >> K;
  vector<ll> h(N);
  rep(i,N){
    cin >> h[i];
  }
  sort(h.begin(),h.end());
  ll ans = 800000000000;
  for(int i = 0;i<=N-K;i++){
    ans = min(ans,h[i+K-1] - h[i]);
  }
  cout << ans << endl;

}

Measured memory_bytes: 1024
// 最小公倍数
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cassert>

#include<vector>
#include<queue>
#include<set>

using namespace std;

int EuclidMethodOfDivision(int x, int y);

int main(void)
{
	int n, num;
	int L_C_M, G_C_F;
	vector<int> v_num;

	cin >> n;

	for(int i = 0; i < n; i++)
	{
		cin >> num;
		v_num.push_back(num);
	}

	// ==================================================
	// 2つの自然数をa, bとすると最小公倍数は以下の式で求められる
	// ( 最小公倍数 ) = ( a * b ) / ( 最大公約数 )
	// ==================================================

	// 最小公倍数の初期値として, 最初の入力値を入れておく
	L_C_M = v_num[0];

	for(int i = 1; i < n; i++)
	{

		// 2数の最大公約数を求める
		G_C_F = EuclidMethodOfDivision(L_C_M, v_num[i]);

		// 最小公倍数を上書きする
		L_C_M = ( L_C_M * v_num[i] ) / G_C_F;
	}

	printf("%d\n", L_C_M);

	return 0;
 }

 // 最大公約数を求める関数 ( ユークリッドの互除法 )
 // x, y : 最大公約数を求める2数
 int EuclidMethodOfDivision(int x, int y)
 {
 	if( x < y )
 	{
 		// x > y の関係になるように設定
 		swap(x, y);
 	}

 	// 割り算の余り
 	int r;

 	// ユークリッドの互除法で最大公約数を探索する
 	// y = 0となった時の x が x と y の最大公約数
 	while( y > 0 )
 	{
 		r = x % y;
 		x = y;
 		y = r;
 	}

 	return x;
 }



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

#define REP(i,s,n) for(int i=s; i<n; ++i)
#define rep(i,n) REP(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false

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

int main(){

	ll n;
	cin >> n;
	vector<pair<ll, ll>> a(n);
	rep(i, n){
		cin >> a[i].first;
		a[i].second = i+1;
	}

	SORT(a);

	rep(i, n){
		cout << a[i].second;
		if(i != n - 1) cout << " ";
	}
	cout << endl;

	return 0;
}


Measured memory_bytes: 2432
import java.util.Scanner

object Main {
  val sc = new Scanner(System.in)
  def main(args: Array[String]): Unit = {
    
    val n = sc.nextInt
    val (a,b,c) = (sc.nextInt, sc.nextInt, sc.nextInt)
    val ll = Seq.fill(n)(sc.nextInt)
    val nn = Math.pow(4, n).toInt
    
    val target = (1 until nn).toArray.map(l => zeroEmbeddingtoString(l.toBinaryString, 2 * n))

    val res =
      target.foldLeft(Int.MaxValue){(min, bin) =>
        def culcSum(strBin: String, sums: (Int, Int, Int), useCount: (Int, Int, Int), ll: Seq[Int]) :( (Int, Int, Int), (Int, Int, Int)) ={
          if (strBin.isEmpty) (sums, useCount)
          else strBin.substring(0,2) match{
            case "01" => culcSum(strBin.substring(2), sums.copy(sums._1 + ll.head,sums._2          , sums._3          ), useCount.copy(useCount._1 + 1, useCount._2     , useCount._3    ), ll.tail)
            case "10" => culcSum(strBin.substring(2), sums.copy(sums._1          ,sums._2 + ll.head, sums._3          ), useCount.copy(useCount._1    , useCount._2 + 1 , useCount._3    ), ll.tail)
            case "11" => culcSum(strBin.substring(2), sums.copy(sums._1          ,sums._2          , sums._3 + ll.head), useCount.copy(useCount._1    , useCount._2     , useCount._3 + 1), ll.tail)
            case _    => culcSum(strBin.substring(2), sums, useCount, ll.tail)
          }
        }
        
        val temp = culcSum(bin, (0,0,0), (0,0,0), ll)
        val ((s1,s2,s3), (c1,c2,c3)) = temp

        if(c1 * c2 * c3 == 0) min
        else{
          val sum =
            Math.abs(a - s1) + Math.abs(b - s2) + Math.abs(c - s3) +
              ( (if(c1 != 0) c1 - 1 else 0) + (if(c2 != 0) c2 - 1 else 0) + (if(c3 != 0) c3 - 1 else 0) ) * 10
          Math.min(min,sum)
        }
      }

    println(res)
  }

  def zeroEmbeddingtoString(str: String, index: Int): String ={
    val l = str.length
    List.fill(index - l)("0").mkString + str
  }
}

Measured memory_bytes: 79016
l = int(input())
vals = list(map(int, input().split(" ")))
costs = list(map(int, input().split(" ")))

diffs = []

for i in range(0, l):
    diffs.append(vals[i] - costs[i])

tmp = list(filter(lambda x: x > 0,   diffs))
print(sum(tmp))

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

void HMS(int tm){
	int h,m,s;
	h = tm/3600;
	m = (tm-h*3600)/60;
	s = tm%60;
	
	cout<<setw(2)<<setfill('0')<<h<<":";
	cout<<setw(2)<<setfill('0')<<m<<":";
	cout<<setw(2)<<setfill('0')<<s<<endl;
}

int main() {
	int h,m,s;
	int tm;
	while(cin>>h>>m>>s,(h+1)|(m+1)|(s+1)){
		tm = h*60*60 + m*60 + s;
		
		int norm_rest = 2*60*60 - tm;
		int tri_rest = 2*60*60*3 - tm*3;
		
		HMS(norm_rest);
		HMS(tri_rest);
	}
	return 0;
}

Measured memory_bytes: 1168
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
using Pl=pair<ll,ll>;
using PPl=pair<ll,Pl>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
template<int mod>
struct ModInt{
	int x;
	ModInt():x(0){}
	ModInt(long long y):x(y>=0?y%mod:(mod-(-y)%mod)%mod){}
	ModInt &operator+=(const ModInt &p){
		if((x+=p.x)>=mod)x-=mod;
		return *this;
	}
	ModInt &operator-=(const ModInt &p){
		if((x+=mod-p.x)>=mod)x-=mod;
		return *this;
	}
	ModInt &operator*=(const ModInt &p){
		x=(int)(1LL*x*p.x%mod);
		return *this;
	}
	ModInt &operator/=(const ModInt &p){
		*this*=p.inverse();
		return *this;
	}
	ModInt operator-()const{return ModInt(-x);}
	ModInt operator+(const ModInt &p)const{return ModInt(*this)+=p;}
	ModInt operator-(const ModInt &p)const{return ModInt(*this)-=p;}
	ModInt operator*(const ModInt &p)const{return ModInt(*this)*=p;}
	ModInt operator/(const ModInt &p)const{return ModInt(*this)/=p;}
	bool operator==(const ModInt &p)const{return x==p.x;}
	bool operator!=(const ModInt &p)const{return x!=p.x;}
	ModInt inverse()const{
		int a=x,b=mod,u=1,v=0,t;
		while(b>0){
			t=a/b;
			a-=t*b;
			swap(a,b);
			u-=t*v;
			swap(u,v);
		}
		return ModInt(u);
	}
	friend ostream &operator<<(ostream &os,const ModInt<mod> &p){
		return os<<p.x;
	}
	friend istream &operator>>(istream &is,ModInt<mod> &a){
		long long x;
		is>>x;
		a=ModInt<mod>(x);
		return (is);
	}
};

const int mod=1e9+7;
using mint=ModInt<mod>;
int main(){
	int h,w,K;
	cin>>h>>w>>K;
	vector<vector<mint>> dp(h+1,vector<mint>(w));
	dp[0][0]=1;
	REP(i,h){
		REP(j,w){
			REP(k,1<<(w-1)){
				//is it vaild?
				bool f=true;
				REP(l,w-2){
					if((k&(1<<l))&&(k&(1<<(l+1)))){
						f=false;
					}
				}
				if(!f){
					continue;
				}
				if(k&(1<<j)){
					dp[i+1][j+1]+=dp[i][j];
				}else if(k&(1<<(j-1))){
					dp[i+1][j-1]+=dp[i][j];
				}else{
					dp[i+1][j]+=dp[i][j];
				}
			}
		}
	}
	cout<<dp[h][K-1]<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;

public class Main{
	public static int eqaualValue(char[] x, int i, int j){
		if( x[i] == x[i+j] && x[i] == x[i+2*j] ){
			if( x[i] == 'o' ){
				return 0;
			} else if( x[i] == 'x' ){
				return 1;
			} 
		}
		return -1;
	}
	
	public static String judge(String str){
		char[] x = str.toCharArray();
		for(int i = 0; i < str.length(); i++){
			x[i] = str.charAt(i);
		}
		for(int i = 0; i < 3; i++){
			if( eqaualValue(x, i, 3) == 0 ){
				return "o";
			} else if( eqaualValue(x, i, 3) == 1 ){
				return "x";
			}
		}
		for(int i = 0; i < 3; i++){
			if( eqaualValue(x, 3*i, 1) == 0 ){
				return "o";
			} else if( eqaualValue(x, 3*i, 1) == 1 ){
				return "x";
			}
		}
		if( eqaualValue(x, 0, 4) == 0 ){
			return "o";
		} else if( eqaualValue(x, 0, 4) == 1 ){
			return "x";
		}
		if( eqaualValue(x, 2, 2) == 0 ){
			return "o";
		} else if( eqaualValue(x, 2, 2) == 0 ){
			return "x";
		}
		return "d";
	}
	
	public static void main(String[] args) throws IOException{
		Scanner stdIn = null;
		List<String> result = new ArrayList<String>();
		
		try{
			stdIn = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
			while( stdIn.hasNext() ){
				String str = stdIn.next();
				result.add(judge(str));
			}
			for(String s : result){
				System.out.println(s);
			}
		} finally {
			if( stdIn != null ){
				stdIn.close();
			}
		}
	}
}

Measured memory_bytes: 12000
import numpy as np

s = np.array(list(input()), dtype=np.unicode)
t = np.array(list(input()), dtype=np.unicode)

ls = len(s)
lt = len(t)
L = ls- lt + 1
dif = np.empty(L, dtype=np.int64)
for i in range(L):
    dif[i] = np.count_nonzero(s[i:i+lt] != t)
ans = np.min(dif)
print(ans)

Measured memory_bytes: 27232
import itertools
def d(x,y):
    return ((x[0]-y[0])**2+(x[1]-y[1])**2) ** 0.5

N = int(input())
X = []
for _ in range(N):
    x, y = map(int, input().split())
    X.append((x,y))
r = 0
#print(X)
c = 0
for p in itertools.permutations(range(N)):
    c += 1
    for i in range(N-1):
#        print(p[i], p[i+1])
        r += d(X[p[i]], X[p[i+1]])
print(r/c)


Measured memory_bytes: 40684
/* Author : Aaryan Srivastava ^__^ */ 
#include <bits/stdc++.h>
#include <random>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#define pb push_back
#define mt make_tuple
#define ff first
#define ss second   
#define rep(i,n) for(int i = 0 ; i < (n) ; i++)
#define repA(i,x,y) for(int i = (x) ; i <= (y) ; i++)
#define repD(i,x,y) for(int i = (x) ; i >= (y) ; i--)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define setval(a,val) memset(a,val,sizeof(a))
#define Randomize mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define trav(x , a) for(auto &x : a)
#define sz(a) ((int)a.size())
typedef long long ll ; 

#define int ll

using namespace std;

const int N = 3e5 +5 ;
const int mod = 1e9 + 7 ;
const ll inf = 1e18 ;
const int SZ = 101 ;
const double eps = 1e-9 ;
using namespace __gnu_pbds;
using ordered_set =  tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ;

typedef pair<int, int> pii; 
typedef pair<int , pii> ipii ;
typedef pair<pii , int> piii ; 
typedef unsigned long long ull ;
typedef long double ld;

ll po(ll x,ll y,ll p = mod) {ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}

void solve()
{
  int a , b;
  cin >> a >> b;
  if(a > b) swap(a , b);
  int l = 0 , r = inf + 5LL ;
  while(r - l > 1){
  	int m = l + (r - l) / 2; 
    int k = (1LL * a * b - 1) / m ;
    if( m <= k ) l = m;
    else r = m;
  }
  if(l == 0){
    cout << 0 ;
  	return ;
  }
  
  int cnt = 2 * l - ( (a * b - 1) / l == l ) - ( l >= a ) ;
  cout << cnt;
}   

     
int32_t main(int32_t argc, char *argv[])
{
    ios::sync_with_stdio(0);    
    cin.tie(0); cout.tie(0);
    int TC = 1, t = 0;
    cin >> TC ;
    while(t++ < TC)
    {
        //cout << "Case #" << t << ": " ;
        solve();
        cout << "\n" ;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>


#define fs first
#define sc second

using namespace std;

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

const ll mod = 998244353;
ll fact[210200];
ll invfact[210200];

inline ll take_mod(ll a){
    return (a % mod + mod) % mod;
}

inline ll add(ll a, ll b){
    return take_mod(a+b);
}

inline ll sub(ll a, ll b){
    return take_mod(a-b);
}


inline ll mul(ll a, ll b){
    return take_mod(a * b);
}

inline ll powMod(ll x, ll n){
    ll res = 1LL;
    while(n > 0){
        if(n & 1) res = mul(res, x);
        x = mul(x, x);
        n >>= 1;
    }
    return res;
}

ll mod_inv(ll x){
    return powMod(x, mod-2);
}

// nは上限
void make_fact(ll n){
    fact[0] = 1;
    ll res = 1;
    for(int i = 1; i <= n; i++){
        fact[i] = res;
        res = mul(res, i+1);
    }
}

// nは上限
void make_invfact(ll n){
    invfact[0] = 1;
    invfact[n] = mod_inv(fact[n]);
    for(int i = n-1; i >= 1; i--){
        invfact[i] = mul(invfact[i + 1], i + 1);
    }
}

ll perm(ll n, ll k){
    return mul(fact[n], invfact[n-k]);
}

ll comb(ll n, ll k){
    return mul(mul(fact[n], invfact[n-k]), invfact[k]);
}

ll dp[110][101000];
int w[110], v[110];

int main(){
    int N, W;
    cin >> N >> W;
    for(int i = 0; i < N; i++){
        cin >> w[i] >> v[i];
    }

    for(int i = 0; i < 110; i++){
        fill(dp[i], dp[i]+101000, 0);
    }

    for(int i = 1; i <= N; i++){
        for(int j = 0; j <= W; j++){
            if(j + w[i-1] <= W){
                dp[i][j+w[i-1]] = max(dp[i][j+w[i-1]], dp[i-1][j] + v[i-1]);
            }
            dp[i][j] = max(dp[i][j], dp[i-1][j]);

        }
    }

    ll res = 0;
    for(int i = 0; i <= W; i++){
        res = max(res, dp[N][i]);
    }

    cout << res << endl;


    return 0;
}


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

int main(){
  int n;
  cin >> n;
  int n1,n2,n3,n4;
  n1 = n / 1000;
  n2 = (n % 1000)/100;
  n3 = (n % 100)/10;
  n4 = n % 10;
  if((n1 == n2 && n1 == n3) || (n2 == n3 && n2 == n4)){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <algorithm>
#include <cmath>
#include <stack>
#include <set>
using namespace std;

#define REP(i,n) for(int (i)=0; (i)<(n); (i)++)
#define FOR(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define PUSH(n,v) for(int i=0; i<(n); i++) {int j; cin >> j; v.push_back(j);}
#define ALL(v) v.begin(), v.end()

int main() {
    vector<int> v;
    int i;
    while(cin >> i) {
        v.push_back(i);
    }
    sort(ALL(v), greater<int>());
    cout << v[0] << endl;
    cout << v[1] << endl;
    cout << v[2] << endl;
    return 0;
}

Measured memory_bytes: 1220
unittest
{
	assert( [ "7", "500 600" ].parse.expand.solve == "OK" );
	assert( [ "4", "5 7" ].parse.expand.solve == "NG" );
	assert( [ "1", "11 11" ].parse.expand.solve == "OK" );
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto k = input.front.to!( long );
	input.popFront;
	auto ab = input.front.split.to!( long[] );
	return tuple( k, ab[ 0 ], ab[ 1 ] );
}

auto solve( long k, long a, long b )
{
	auto c = ( b / k ) * k;
	return ( a <= c ) ? "OK" : "NG";
}


Measured memory_bytes: 2764
#include<stdio.h>
#include<stdlib.h>
int com(const int *a, const int *b){
  if(*a < *b)
    return -1;
  else if(*a == *b)
    return 0;
  else
    return 1;
}
int main(){
  int i,tmp,n,max=0;
  int d[100000];
  int abc=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&d[i]);
  }
  qsort(d,n,sizeof(int),(int (*)(const void *,const void *))com);
  printf("%d\n",d[n/2]-d[n/2-1]);
  return 0;
}

Measured memory_bytes: 892
import os
import sys
from io import BytesIO, IOBase
# from collections import defaultdict as dd
# from collections import deque as dq
# import itertools as it
# from math import sqrt, log, log2
# from fractions import Fraction
import heapq
def main():
    n = int(input())
    nums = list(map(int, input().split()))
    nums.sort(reverse=True)
    if n<=3:
        print(sum(nums[:n-1]))
        exit()
    

    hp = list()
    ans = 0
    # Push the first three intervals
    heapq.heappush(hp, (-nums[1], nums[0]))
    heapq.heappush(hp, (-nums[2], nums[0]))
    heapq.heappush(hp, (-nums[2], nums[1]))
    ans = sum(nums[:2])

    i = 3
    while i < n:
        comfort, big = heapq.heappop(hp)
        ans += -comfort

        small = -comfort

        curr = nums[i] # what enters the circle

        #push the smaller interval
        heapq.heappush(hp, (-curr, small))
        heapq.heappush(hp, (-curr, big))
        i += 1
    print(ans)






































# region fastio
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# endregion
 
if __name__ == "__main__":
    main()

Measured memory_bytes: 112128
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string> 
#include <vector> 
using namespace std;
  
int main(){
    /*??£???????????????????????????
            int a[2];
            cin >> a[1] >> a[2];
            cout << "[+] " << a[1] + a[2] << endl;
            cout << "[-] " << a[1] - a[2] << endl;
            cout << "[*] " << a[1] * a[2] << endl;
            cout << "[/] " << a[1] / a[2] << endl;
    */

    int a;
    while(cin >> a){
        if(a == 0){break;}
        int p[a][3],ave,ave2;
        for (int i = 1; i <= a; i++)
        {
            string ans;
            cin >> p[i][0] >> p[i][1] >> p[i][2]; 
            ave = ( p[i][0] + p[i][1] + p[i][2] ) / 3;
            ave2 = ( p[i][0] + p[i][1] ) / 2;            
            if(p[i][0]  >= 100 or p[i][1]  >= 100 or p[i][2]  >= 100){ans = "A";
            }else if(ave >= 80 or ave2 >= 90){
                ans = "A";
            }else if(ave >= 70){
                ans = "B";
            }else if(ave >= 50){
                if(p[i][0] >= 80 or p[i][1] >= 80){
                    ans = "B";
                }else{
                    ans = "C";
                } 
            }else{
                ans = "C";  
            }
            cout << ans << endl;
        }

    }
}

Measured memory_bytes: 1188
MOD = 10 ** 9 + 7

def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    max_bin_digits = len(bin(max(A))[2:])
    cnts = [0] * max_bin_digits

    for a in A:
        for i in range(max_bin_digits):
            if 1 << i & a:
                cnts[i] += 1

    ans = 0
    for i in range(max_bin_digits):
        ans += cnts[i] * (N - cnts[i]) * 2 ** i
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 122936
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int[] g = new int[a];
		int min=101;
		int max=0;
		int ans = 0;
		for(int i = 0; i<a; i++){
			int b = sc.nextInt();
			g[i]=b;
			if(b<min){
				min=b;
			}
			if(b>max){
				max=b;
			}
		}
		ans+=min;
		while(min<max){
		for(int i = 0; i <a; i++){
			if(g[i]>min){
				if(i==0){
					ans++;
				}else{
				if(g[i-1]>min){
					
				}else{
					ans++;
				}
				}
			}
		}
			min++;
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 23252
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int a,i;
    char s[10];
    while(~scanf("%s",s))
    {
        a=0;
        for(i=0; i<4; i++)
        {
            if(s[i]=='+')
                a+=1;
            else if(s[i]=='-')
                a-=1;
        }
        printf("%d\n",a);
    }
    return 0;
}


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

mapAC = [False]*(n+1)
countWA = [0]*(n+1)

for i in range(m):
    p, s = input().split()
    p = int(p)
    if s == 'AC':
        mapAC[p] = True
    else:
        countWA[p] += 1*(not mapAC[p])
countWA = map(lambda x, y: x*y, countWA, mapAC)
print(mapAC.count(True), sum(countWA))

Measured memory_bytes: 45528
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll MOD = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
const double EPS = 1e-9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
int main() {
	ll x = 1; ll y = 1;
	int n; cin >> n;
	rep(i, n) {
		ll s, t;
		cin >> s >> t;
		if (x <= s && y <= t) {
			x = s; y = t;
		}
		else if (x > s&&y<=t) {
			ll d = (x - (ll)1) / s; d++;
			x = d * s; y = d * t;
		}
		else if(x<=s){
			ll d = (y - (ll)1) / t; d++;
			x = d * s; y = d * t;
		}
		else {
			ll d1 = (x - (ll)1) / s; d1++;
			ll d2 = (y - (ll)1) / t; d2++;
			ll d = max(d1, d2);
			x = d * s; y = d * t;
		}
	}
	cout << x + y << endl;
	return 0;
}

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

int main(void) {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  double average = (double)accumulate(a.begin(), a.end(), 0) / n;
  double d=numeric_limits<double>::max();
  int f;
  for (int i = 0; i < n; i++) {
    if (fabs(average-a[i])<d) {
      d=fabs(average-a[i]);
      f=i;
    }
  }
  cout << f << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll inf = 922337203685477;
const ll mininf = -922337203685477;
const ll nax = 0;

ll a, b, n;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
	
	cin >> a >> b >> n;
	ll x = min(n, b - 1);
	ll left = a * x / b;
	ll right = a * (x / b);
	cout << left - right << '\n';
}


Measured memory_bytes: 3692
//In the name of God
#include<bits/stdc++.h>

using namespace std;

const int N = 2e3 + 100;
int n , k , a[N] , b[N] , res , now;
vector<int>e[N];

void dfs0(int v , int p = -1 , int h = 0){
	if(h > k / 2)
		return ;
	now++;
	for(auto u : e[v])
		if(u != p)
			dfs0(u , v , h+1);
}

void dfs1(int v , int x , int p = -1, int h = 0){
	if(h > k / 2)
		return ;
	now++;
	for(auto u : e[v])
		if(u != p && u != x)
			dfs1(u , x , v , h+1);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;	res = n;
	for(int i=1 ; i < n ; i++){
		cin >> a[i] >> b[i];
		e[a[i]].push_back(b[i]);
		e[b[i]].push_back(a[i]);
	}
	if(k&1){
		for(int i=1 ; i < n ; i++){
			now = 0;
			dfs1(a[i] , b[i]);
			dfs1(b[i] , a[i]);
			res = min(res , n - now);
		}
	}
	else{
		for(int i=1 ; i <= n ; i++){
			now = 0;
			dfs0(i);
			res = min(res , n - now);
		}
	}
	cout << res;
	return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
	cout<<"square1001"<<endl;
	return 0;
}


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

#define ll long long
#define PI acos(-1.0)
#define FOR(I, A, B) for (int I = (A); I < (B); ++I)

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

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

using namespace std;

vector<int> ed[100050];
bool fg = 0;
int st;

void dfs(int pos,int lst)
{
	for(auto v : ed[pos])
	{
		if(v == lst) continue;
		if(v == st)
		{
			fg = 1;
			return ;
		}
		if(ed[v].size() == 4) continue;
		dfs(v,pos);
	}
}

int main()
{
	int n,m; scanf("%d%d",&n,&m);
	for(int i = 1;i <= m; ++ i)
	{
		int u,v; scanf("%d%d",&u,&v);
		ed[u].push_back(v);
		ed[v].push_back(u);
	}
	vector<int> fw;
	for(int i = 1;i <= n; ++ i)
	{
		if(ed[i].size() & 1)
		{
			puts("No");
			return 0;
		}
		else if(ed[i].size() >= 6)
		{
			fg = 1;
		}
		else if(ed[i].size() == 4) fw.push_back(i);
	}
	if(fw.size() >= 3 || fg) {puts("Yes"); return 0;}
	if(fw.size() <= 1) {puts("No"); return 0;}
	int c = 0;
	for(auto v : fw)
	{
		fg = 0; st = v;
		dfs(v,0);
		c += fg;
	}
	if(c == 2) puts("Yes"); else puts("No");
}

Measured memory_bytes: 6912