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

using namespace std;

typedef long long int li;
typedef vector<li> vi;
typedef pair<li,li> pi;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define B begin()
#define E end()
#define f(i,l,r) for(li i=l;i<=r;++i)
#define fr(i,l,r) for(li i=l;i>=r;--i)
#define u_map unordered_map

li fastpow(li base,li exp,li M) 
{
    li res=1;
    while(exp>0) {
        if(exp&1)
            res=(res*base)%M;

        base=(base*base)%M;
        exp>>=1;
    }
    return res;
}
    
int main()
{    
    ios_base::sync_with_stdio(false);
        cin.tie(NULL);

        li n,k;

        cin>>n>>k;

        li a[n];

        for(li i=0;i<n;i++)
            cin>>a[i];

        li b[n];

        for(li i=0;i<n;i++)
            cin>>b[i];

        sort(a,a+n);

        sort(b,b+n,greater<li>());

        li start=-1,end=1e12;

        li mid=(start+end)/2;

        while(start+1<end)
        {            
            mid=(start+end)/2;
            
            li cnt=0;

            f(i,0,n-1)
            {
                cnt+=max(a[i]-mid/b[i],0ll);
            }

            if(cnt<=k)
                end=mid;
            else
                start=mid;
        }

        cout<<end;

    return 0;
}


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

using namespace std;

int main(){
  int n; cin >> n;
  int a, b, c;
  for(int i = 0; i < n; i++){
    int x, y, z; cin >> x >> y >> z;
    if(i == 0){
      a = x, b = y, c = z;
    }
    else{
      int na = x + max(b, c);
      int nb = y + max(a, c);
      int nc = z + max(a, b);
      a = na, b = nb, c = nc;
    }
  }
  cout << max(a, max(b, c)) << endl;
  return 0;
}


Measured memory_bytes: 256
from collections import deque

def main():
    H, W = map(int, input().split())
    S = list(input() for _ in range(H))

    Q = deque([(0, 0)])
    d = [[float('inf')] * W for _ in range(H)]
    d[0][0] = 0
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    while Q:
        h, w = Q.popleft()

        if h == H - 1 and w == W - 1:
            break

        for i in range(4):
            nh = h + dy[i]
            nw = w + dx[i]

            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and d[nh][nw] == float('inf'):
                d[nh][nw] = min(d[nh][nw], d[h][w] + 1)
                Q.append((nh,nw))

    if d[H-1][W-1] == float('inf'):
        print(-1)
        exit()
    cnt = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                cnt += 1

    print(cnt - d[H-1][W-1] - 1)

         

    


if __name__ == "__main__":
    main()

Measured memory_bytes: 41072
// kartikay26
#include <bits/stdc++.h>
using namespace std;
#define debug(x...) 
#ifdef LOCAL
#include "prettyprint.hpp"
#endif
void print(){cout << endl;} void prints(){}
template<typename T=int> T get(){T x; cin >> x; return x;}
template<typename T> void get(T* x, int n){for (int i = 0; i < n; ++i) { cin >> x[i]; }}
template<typename T> void get(T& x, int n){for (int i = 0; i < n; ++i) { cin >> x[i]; }}
template<typename T, typename... A> void print(T x,A... r){cout << x << " ";print(r...);}
template<typename T, typename... A> void prints(T x,A... r){cout << x << " ";prints(r...);}
typedef long long int ll; typedef double db; typedef vector<ll> vi; typedef pair<ll, ll> pii;
#define int ll
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define clear(x) memset(x, 0, sizeof(x))
#define fast_io() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

const int mod = 1e9+7;
const int N = 1e6+1;

int32_t main(){
	fast_io();

	#define push(a, b) b = min(b, a); // using a push to b

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

	int dp[int(2e5+1)]; // int dp[v] = min wt to gen value v
	for (int i = 0; i < int(2e5+1); ++i) {
		dp[i] = LLONG_MAX/2;
	}

	dp[0] = 0;

	for (int i = 0; i < N; ++i) {
		int wt = w[i], vl = v[i];
		for (int v = 100000; v >= 0; --v) {
			push(dp[v] + wt, dp[v+vl]);
		}
	}

	int ans = 0;
	for (int i = 0; i <= 100000; ++i) {
		if(dp[i] <= W) ans = max(ans, i);
	}

	print(ans);
	
	return 0;
}

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


N=int(input())
S=input()
K=int(input())

c=S[K-1]

ans=""
# 1文字ずつ処理
s = "abcdefghijklmnopqrstuvwxyz"
for a in S:
	if a==c:
		ans = ans + a
	else:
		ans = ans + '*'

print(ans)



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

using ll = long long;

int main() {
    int N, M;
    while(cin >> N >> M, N) {
        vector<ll> mi(N), ma(N);
        for(int i = 0; i < M; ++i) {
            ll S, k;
            cin >> S >> k;
            if(k == 1) {
                int c;
                cin >> c;
                c--;
                mi[c] += S;
                ma[c] += S;
            } else {
                for(int j = 0; j < k; ++j) {
                    int c;
                    cin >> c;
                    c--;
                    ma[c] += S;
                }
            }
        }
        ll res = 0;
        for(int i = 0; i < N; ++i) {
            for(int j = 0; j < N; ++j) {
                if(i == j) {
                    continue;
                }
                res = max(res, ma[j] - mi[i]);
            }
        }
        cout << res + 1 << endl;
    }
}


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

typedef vector<vector<int> > P;

P c(60,vector<int>(60)),d(60,vector<int>(60)),x(60,vector<int>(60));
int n,K;

P floyd(P a,P b){
	P h(60,vector<int>(60));
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				h[i][j]+=a[i][k]*b[k][j];
				if(h[i][j]>=MOD) h[i][j]%=MOD;
			}
		}
	}
	return h;
}

void dfs(int k)
{
	if(k==0) return;
	int w=1,cnt=0;
	while(w<=k){
		w*=2;
		cnt++;
	}
	w/=2;
	cnt--;
	x=c;
	for(int i=1;i<=cnt;i++){
		x=floyd(x,x);
	}
	d=floyd(d,x);
	dfs(k-w);
}

signed main()
{
	ios::sync_with_stdio(false);
	cin>>n>>K;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>c[i][j];
		}
	}
	for(int i=1;i<=n;i++) d[i][i]=1;
	dfs(K);
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			ans+=d[i][j];
			if(ans>=MOD) ans-=MOD;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 512
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

h,w,k=nii()
c=[list(input()) for i in range(h)]

b_cnt=0
for i in c:
  b_cnt+=i.count('#')

ans=0
for i in range(2**h):
  for j in range(2**w):
    h_use=[]
    for ii in range(h):
      if (i>>ii)&1:
        h_use.append(ii)
    w_use=[]
    for jj in range(w):
      if (j>>jj)&1:
        w_use.append(jj)

    t_cnt=0
    for s in h_use:
      t_cnt+=c[s].count('#')
    for s in w_use:
      for t in range(h):
        if c[t][s]=='#':
          t_cnt+=1

    for s in h_use:
      for t in w_use:
        if c[s][t]=='#':
          t_cnt-=1

    if b_cnt-t_cnt==k:
      ans+=1

print(ans)

Measured memory_bytes: 9240
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)
#define repitr(itr,a) for(auto itr=a.begin();itr!=a.end();++itr)
#define P pair<int,int>
const int MOD=1e9+7;
const int INF=2e9;


int main() {
    ios_base::sync_with_stdio(false);

    string a,b; 
    cin >> a >> b;
    int flag=0;
    if (a.size()>b.size()) flag=1;
    else if (a.size()<b.size()) flag=-1;
    else {
        rep(i,a.size()) {
            if (a[i]>b[i]) {
                flag=1;
                break;
            } else if (a[i]<b[i]) {
                flag=-1;
                break;
            }
        }
    }
    if (flag==1) cout << "GREATER" << endl;
    else if (flag==-1) cout << "LESS" << endl;
    else cout << "EQUAL" << endl;
    

    return 0;   
}


Measured memory_bytes: 256
using System;

namespace abc062A
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            string[] str = Console.ReadLine().Split();
            int A = int.Parse(str[0]);
            int B = int.Parse(str[1]);
            int[] Arrey = new int[] { 0, 2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0 };
            if (Arrey[A-1] == Arrey[B-1])
                Console.WriteLine("Yes");
            else
                Console.WriteLine("No");
        }
    }
}


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

int h,w,n,k;
int a[100010];
int s[110][110];

int main()
{
    scanf("%d %d",&h,&w);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    int i,j;k=1;
    for(i=1;i<=h;i++)
    {
        for(j=1;j<=w;j++)
        {
            if(a[k]!=0)s[i][j]=k,a[k]--;
            else k++,j--;
        }
        i++;
        if(i>h)break;
        for(j=w;j>=1;j--)
        {
            if(a[k]!=0)s[i][j]=k,a[k]--;
            else k++,j++;
        }
    }
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            printf("%d ",s[i][j]);
        }
        putchar('\n');
    }
    return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
ll MOD = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)
int main() {
    int n, a, b;
    cin >> n >> a >> b;
    if ( abs(a-b-1) % 2 == 0 ) cout << "Borys" << endl;
    else                       cout << "Alice" << endl;
    return 0;
}


Measured memory_bytes: 256
#import numpy as np
#import math
import sys

read = lambda: sys.stdin.readline().rstrip()

class Solution(object):
    def binomial_coefficients(self, n, A):

        n0 = max(A)

        mid, r, cur = n0 / 2, -1, float("inf")
        for i in A:
            if i != n0:
                x = abs(mid - i)
                if x < cur:
                    r, cur = i, x
        return n0, r

def main():
    n0 = int(read())
    A0 = tuple(map(int, read().split()))

    res0, res1 = Solution().binomial_coefficients(n0, A0)

    print(res0, res1)
 
if __name__ == "__main__":
    main()

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

#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define RFOR(i, a, b) for(int i=(a); i>=(b); i--)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) RFOR(i, n, 0)
#define dump(x)  cout << #x << " = " << (x) << endl;

typedef long long ll;
typedef pair<int, int> ii;
const ll INF = 1e18;
const int inf = 1e8;


void solve()
{
  ll N;
  scanf("%lld",&N);
  ll M;
  scanf("%lld",&M);
  ll X;
  scanf("%lld",&X);
  ll Y;
  scanf("%lld",&Y);
  vector<ll> x(N);
  for(int i = 0 ; i < N ; i++){
    scanf("%lld",&x[i]);
  }
  vector<ll> y(M);
  for(int i = 0 ; i < M ; i++){
    scanf("%lld",&y[i]);
  }
  x.push_back(X);
  y.push_back(Y);
  sort(x.begin(),x.end());
  sort(y.begin(),y.end());
  if (x.back()>=y[0]) cout << "War" << endl;
  else cout << "No War" << endl;
}

int main()
{
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <ctype.h>
#include <math.h>
#include <stack>
#include <string>
#include <string.h>
using namespace std;
double PI = 3.1415926535897932;
long mod = 1000000007;

const long INF = 1e9 + 1;

int main() {
  int a,b;
  cin >> a >> b;
  cout << a*b-(a+b-1) << endl;
}


Measured memory_bytes: 3552
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
 
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;
using vs = vector<string>;
using vb = vector<bool>;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REV(c) reverse(ALL(c))
#define sz(v) (int)v.size()
#define endl '\n'
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
template<class T> inline void prn(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << ' ';}
template<class T> inline void printv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << (i == n - 1 ? endl : ' ');}
template<class T> inline void printvv(vector<vector<T>>& v) {for (auto u : v) printv(u);}
template<class T> inline void printlnv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << endl;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}
 
void solve() {
    int t;
    cin >> t;
    while (t--) {
        ll n, m, a, b;
        cin >> n >> m >> a >> b;
        cout << floor_sum(n, m, a, b) << endl;
    }
}

Measured memory_bytes: 3668
n=int(input())
a=list(map(int,input().split()))
ushiro=list()
mae=list()
for i in range(n):
    if i%2:#1
        mae.append(a[i])
    else:
        ushiro.append(a[i])
p=ushiro[::-1]+mae if n%2 else mae[::-1]+ushiro
print(*p)

Measured memory_bytes: 30912
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<deque>
#include<tuple>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cstdint>
#include<unordered_map>
#include<sstream>
#include<boost/multiprecision/cpp_int.hpp>

#define rep(i, n) for(int i = 0; i < ( int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define vi vector<int>
#define vll vector<ll>
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define pb push_back

namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

typedef pair<int, int> P;

bool ps1(const P& element1, const P& element2)
{//first昇順
	return element1.first < element2.first;
}
bool ps2(const P& element1, const P& element2)
{//first降順
	return element1.first > element2.first;
}
bool ps3(const P& element1, const P& element2)
{//second昇順
	return element1.second < element2.second;
}
bool ps4(const P& element1, const P& element2)
{//second降順
	return element1.second > element2.second;
}


int main()
{
	int n, a, b, c, d;
	cin >> n >> a >> b >> c >> d;
	string s;
	cin >> s;
	int count = 0;
	bool ans = true;

	FOR(i, a - 1, c) {
		if (s[i] == '#') {
			count++;
		}
		else {
			count = 0;
		}
		if (count >= 2) {
			ans = false;
		}
	}
	count = 0;
	FOR(i, b - 1, d) {
		if (s[i] == '#') {
			count++;
		}
		else {
			count = 0;
		}
		if (count >= 2) {
			ans = false;
		}
	}
	if (c < b) {
		//iii
		if (ans) {
			cout << "Yes" << endl;
		}
		else {
			cout << "No" << endl;
		}
	}
	else if(b<c&&d<c) {
		//ii
		//cout << "ii" << endl;
		bool ans1 = false;
		int blank = 0;
		FOR(i, b - 2, d+1) {
			if (s[i] == '.') {
				blank++;
			}
			else {
				blank = 0;
			}
			if (blank >= 3) {
				ans1 = true;
			}
			//cout << blank << endl;
		}
		if (ans1 && ans) {
			cout << "Yes" << endl;
		}
		else {
			cout << "No" << endl;
		}
	}
	else if(b<c&&c<d) {
		//i
		if (ans) {
			cout << "Yes" << endl;
		}
		else {
			cout << "No" << endl;
		}
	}

}



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

int main() {
  
  int N, A, B;//A is Alice's point. B is Bob's point.
  
  cin >> N;
  
  vector <int> a (N);
  
  //cout << N << endl;
  
  for (int i = 0; i < N; i++){
    
    cin >> a.at(i);
      
  }
  
  sort(a.begin(), a.end());
  
  reverse(a.begin(), a.end());
  
  A = 0;
  B = 0;
  for (int i = 0; i < N; i++){
    
    if (i % 2 == 0){
      A += a.at(i);
      //cout << "Aliceは " << a.at(i) << " の札をとった" << " (A = " << A << " )" << endl;
    }
    
    else{
      B += a.at(i);
      //cout << "Bobは " << a.at(i) << " の札をとった" << " (B = " << B << " )"  << endl;
    }
  }
  
  cout << A - B << /*" 点差で Alice の勝利だ！おめでとー" <<*/ endl;
  
}


Measured memory_bytes: 256
x  = input()
ans = 0
n = len(x)
if n % 2 == 0:
    for i in range(int(n/2)):
        if x[i] != x[-i-1]:
            ans += 1
else: 
    for i in range(int(n/2)):
        if x[i] != x[-i-1]:
            ans += 1

print(ans)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
typedef long long ll;
const ll M = 1000000007;
//べき乗高速化
ll mpow(ll x, ll n){
	ll ans = 1;
	while(n != 0){
		if (n&1) ans = ans * x % M;
		x = x*x % M;
		n  = n >> 1;
	}
	return ans;
}

int main(){
	ll n,a,b;
	cin >> n >> a >> b;
	
	ll temp1 = 1;
	ll temp2 = 1;
	for (ll i = 1; i <= a; ++i) {
		temp1 *= (n+1-i)*mpow(i,M-2) % M;
		temp1 %= M;
	}
	for (ll i = 1; i <= b; ++i) {
		temp2 *= (n+1-i)*mpow(i,M-2) %M;
		temp2 %= M;
	}
	
	ll ans = mpow(2,n) - temp1 - temp2 - 1;
 	if(ans % M >= 0){
 		cout << ans % M << endl;
 	}else{
 		cout << M + ans%M << endl;
 	}
   
    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
using namespace std;
typedef long long ll;
vector<ll> node[100005];
bool used[100005]={false};
ll grundy(ll pos){
  ll cnt=0;
  for(int i=0;i<node[pos].size();i++){
    ll to=node[pos][i];
    if(!used[to]) cnt++;
  }
  if(cnt==0) return 0;
  else if(cnt==1){
    for(int i=0;i<node[pos].size();i++){
      ll to=node[pos][i];
      if(!used[to]){
        used[to]=true;
        return grundy(to)+1;
      }
    }
  }
  else{
    ll res=0;
    for(int i=0;i<node[pos].size();i++){
      ll to=node[pos][i];
      if(!used[to]){
        used[to]=true;
        res^=grundy(to)+1;
      }
    }
    return res;
  }
}
int main(){
  ll n;
  cin>>n;
  for(int i=1;i<n;i++){
    ll s,t;
    cin>>s>>t;
    node[s].push_back(t);
    node[t].push_back(s);
  }
  for(int i=1;i<=n;i++) used[i]=false;
  used[1]=true;
  cout<<(grundy(1)==0?"Bob":"Alice")<<endl;
}


Measured memory_bytes: 6656
#include<stdio.h>
int main() {
	int a, b, c;
	scanf("%d %d %d", &a, &b, &c);
	if (a < b) {
		if ((a < c) && (c < b)) {
			printf("Yes\n");
		}
		else {
			printf("No\n");

		}
	}
	else {
		if ((b < c) && (c < a)) {
			printf("Yes\n");
		}
		else {
			printf("No\n");
		}
	}
	return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
#define NIL -1
#define MAX 100000

typedef struct{
  int parent,left,right;
}Node;

Node T[MAX];
int n, D[MAX];

void setDepth(int u, int d){
  D[u] = d;
  if(T[u].right != NIL)setDepth(T[u].right,d);
  if(T[u].left != NIL)setDepth(T[u].left,d+1);
}

void print(int u){
  int i,c;
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].parent);
  printf("depth = %d, ",D[u]);

  if(T[u].parent == NIL){
    printf("root, ");
  } else if (T[u].left == NIL){
    printf("leaf, ");
  } else {
    printf("internal node, ");
  }
  printf("[");
  for(i=0,c=T[u].left;c!=NIL;i++,c=T[c].right){
    if(i)printf(", ");
    printf("%d",c);
  }
  printf("]\n");
}

int main(){
  int i,j,id,k, l, r, root = 0;
  scanf("%d",&n);

  for(i=0;i<n;i++)
    T[i].parent = T[i].left = T[i].right = NIL;

  for(i=0;i<n;i++){
    scanf("%d %d",&id,&k);
    for(j=0;j<k;j++){
      scanf("%d",&r);
      if(j==0)T[id].left = r;
      else T[l].right = r;
      l = r;
      T[r].parent = id;
    }
  }

  for(i=0;i<n;i++) if(T[i].parent==NIL)root = i;

  setDepth(root,0);

  for(i=0;i<n;i++) print(i);

  return 0;
}



Measured memory_bytes: 6396
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(), (x).end())
#define ALL(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define reps(i, m, n) for (ll i = m; i < n; i++)
#define repr(i, m, n) for (ll i = m; i >= n; i--)
#define de(x) cout << #x << "=" << x << endl;
#define SP << " " <<
template <class T> bool maxi(T &a, const T &b) {
    if (a < b) { a = b; return 1;} return 0;}
template <class T> bool mini(T &a, const T &b) {
    if (b < a) { a = b; return 1;} return 0;}
#define dame {cout<< "-1" <<"\n"; return;}
#define INF2 1000000000000000037
#define INF  1000000007
#define MOD  1000000007
using namespace std;
using ll = long long;
using ld = long double;
using P  = pair<ll,ll>;
//--GLOBAL---------------------------------
struct BIT
{
    int M;
    vector<ll> bit;
    BIT(int n=500050): M(n), bit(M+1,0) {}

    void add(int a, ll w) { // aを +w  aは 1-indexed
        for(int x=a; x<=M; x+= x& -x){
            bit[x] += w;
        }
    }

    ll sum(int a) { // [1,a] 1-indexed
        ll ret=0;
        for(int x=a; x>0; x-= x& -x){
            ret+= bit[x];
        }
        return ret;
    } // 左上のものをすべて足す

    ll get(ll k){ // k-th number 1-indexed 二分探索
        //k-1までが全部入るresの1つ後を求める。
        ll res=0; // kがたまるまでresを増やす。
        ll N=1; while(N <= M) N*=2;
        for(int i=N/2; i>0; i/=2 ){
            if(res + i <= M and bit[res+i] <k){
            k = k-bit[res+i];
            res+=i;
            }
        }
        return res+1; // 1-indexed resまでは新kまでが全部入る
    }
};

//--MAIN-----------------------------------
void Main() {
    ll N; cin>>N;
    string S; cin>>S;
    BIT bit[26];
    rep(i,N){
        ll cn=S[i]-'a';
        bit[cn].add(i+1,1);
    }
    ll Q; cin>>Q;
    while(Q--){
        ll qq; cin>>qq;
        if(qq==1){
            ll x; char c; cin>>x>>c; --x;
            ll cn=c-'a';
            bit[cn].add(x+1,1);
            cn=S[x]-'a';
            bit[cn].add(x+1,-1);
            S[x]=c;
        }
        else{
            ll l,r; cin>>l>>r;
            ll ans=0;
            rep(i,26){
                ll x=bit[i].sum(r)-bit[i].sum(l-1);
                if(x>0) ++ans;
            }
            cout<< ans <<"\n";
        }
    }

}

//--START----------------------------------
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
}
//-----------------------------------------


Measured memory_bytes: 102556
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<string>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<queue>
#include<functional>
#include<iso646.h>
#include<bitset>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<long long> vll;
typedef pair<long long, long long> pll;

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

ll dp[50][2];

// 整数を2進法表記した文字列（0埋めしてk桁にする）を返す
string tobin(ll n, ll k) {
	string out = "";
	ll len = 1;
	ll div = 1;
	while (1) {
		if (n / div < 2) {
			break;
		}
		len++;
		div *= 2;
	}
	for (ll i = 0; i < len; i++) {
		if (n / div >= 1) {
			out = out + "1";
			n -= div;
		}
		else {
			out = out + "0";
		}
		div /= 2;
	}
	if (out.length() <= k) {
		out = string(k - out.length(), '0') + out;
	}

	return out;
}


int main() {
	ll strlen = 50;
	ll N, K;
	ll i, j;
	cin >> N >> K;
	string sK = tobin(K, strlen);
	vector<string> A;
	for (i = 0; i < N; i++) {
		ll a;
		cin >> a;
		A.push_back(tobin(a, strlen));
	}

	dp[0][0] = 0;
	dp[1][0] = -1;

	for (i = 1; i <= strlen; i++) {
		ll n_0 = 0;
		for (j = 0; j < N; j++) {
			if (A[j][i - 1] == '0') {
				n_0++;
			}
		}
		ll n_1 = N - n_0;

		if (sK[i - 1] == '0') {
			dp[0][i] = dp[0][i - 1] + (ll)pow(2, strlen - i) * n_1;
			if (dp[1][i - 1] == -1) {
				dp[1][i] = -1;
			}
			else {
				dp[1][i] = dp[1][i - 1] + (ll)pow(2, strlen - i) * max(n_0, n_1);
			}
		}
		else {
			dp[0][i] = dp[0][i - 1] + (ll)pow(2, strlen - i) * n_0;
			if (dp[1][i - 1] == -1) {
				dp[1][i] = (ll)pow(2, strlen - i) * n_1;
			}
			else {
				dp[1][i] = max(dp[0][i - 1] + (ll)pow(2, strlen - i) * n_1, dp[1][i - 1] + (ll)pow(2, strlen - i) * max(n_0, n_1));
			}
		}

	}
	cout << max(dp[0][strlen], dp[1][strlen]) << endl;

	return 0;
}


Measured memory_bytes: 13488
#include<iostream>
#include<iomanip>
#include<cassert>
#include<math.h>
#include<complex>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<functional>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=2e18;
const ll MOD=1e9+7;

ll X,Y,A,B,C;
ll p[100010],q[100010],r[100010];
vector<ll> v;
int main(){
    cin>>X>>Y>>A>>B>>C;
    for(ll i=0;i<A;i++){
        cin>>p[i];
    }
    for(ll i=0;i<B;i++){
        cin>>q[i];
    }
    for(ll i=0;i<C;i++){
        cin>>r[i];
        v.push_back(r[i]);
    }
    sort(p,p+A,greater<ll>());
    sort(q,q+B,greater<ll>());
    for(ll i=0;i<X;i++){
        v.push_back(p[i]);
    }
    for(ll i=0;i<Y;i++){
        v.push_back(q[i]);
    }
    sort(v.begin(),v.end(),greater<ll>());
    ll ans=0;
    for(ll i=0;i<X+Y;i++){
        ans+=v[i];
    }
    cout<<ans<<endl;
    return 0;
}

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

const ll N=1e5+5;
ll n, h[N], dp[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(ll i=1; i<=n; i++) cin>>h[i];
    dp[2]=abs(h[2]-h[1]);
    for(ll i=3; i<=n; i++){
        ll a = dp[i-1]+abs(h[i]-h[i-1]);
        ll b = dp[i-2]+abs(h[i]-h[i-2]);
        dp[i] = min(a,b);
    }
    cout<<(ll)dp[n];

}


Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double n = sc.nextDouble();

        if(n==1){
            System.out.println("1.0000000000");
            return;
        }else if(n % 2 == 0){
            System.out.println("0.5000000000");
        }else {
            System.out.println(((n+1)/2) /n);
        }



    }
}

Measured memory_bytes: 23124
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

const INF: i64 = 100000000000;

fn shortest_path(graph: &Vec<Vec<(usize, i64)>>, start: usize) -> (Vec<i64>, Vec<bool>) {
    let n = graph.len();
    let mut dist = vec![INF; n];
    dist[start] = 0;
    for _ in 0..n {
        for v in 0..n {
            for &(to, cost) in &graph[v] {
                if dist[v] == INF || dist[to] <= dist[v] + cost {
                    continue;
                }
                dist[to] = dist[v] + cost;
            }
        }
    }

    let mut negative = vec![false; n];
    for _ in 0..n {
        for v in 0..n {
            for &(to, cost) in &graph[v] {
                if dist[v] == INF {
                    continue;
                }
                if dist[to] > dist[v] + cost {
                    dist[to] = dist[v] + cost;
                    negative[to] = true;
                }
                if negative[v] {
                    negative[to] = true;
                }
            }
        }
    }

    return (dist, negative);
}

fn main() {
    let v = read_vec::<usize>();
    let (n, m, p) = (v[0], v[1], v[2] as i64);

    let mut edges = vec![Vec::new(); n];
    for i in 0..m {
        let v = read_vec::<usize>();
        let (a, b, c) = (v[0] - 1, v[1] - 1, v[2] as i64);
        edges[a].push((b, p - c));
    }
    let (dist, negative) = shortest_path(&edges, 0);
    if negative[n - 1] {
        println!("-1");
    } else {
        println!("{}", max(-1 * dist[n - 1], 0));
    }
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define repi(i,x) for(auto i=(x).begin(),i##_fin=(x).end();i!=i##_fin;i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
string solve(bool a) { return ((a) ? "Yes" : "No"); }
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int , int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
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;}
template <class T, class U>ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os << "(" << p.first << "," << p.second << ")";
	return os;
}
template <class T>ostream& operator<<(ostream& os, const vector<T>& v) {
	os << "{";
	rep(i, v.size()) {
		if (i) os << ",";
		os << v[i];
	}
	os << "}";
	return os;
}
template <class T, class U>istream& operator>>(istream& is, pair<T, U>& p) {
	is >> p.first >>p.second ;
	return is;
}
template <class T>istream& operator>>(istream& is,  vector<T>& v) {
	rep(i, v.size()) {
		is >> v[i];
	}
	return is;
}
const long long INFLL = 1LL<<60;
const int INF = 1<<30;
const double PI=acos(-1);
int main(){
	int r;
	int ans=0;
	cin >>r;
	cout<<3*r*r<<endl;
}

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

void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	ll sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		sum += a[i];
	}
	ll s = 0, res = 0;
	ll mod = 1e9 + 7;
	for (int i = 0; i < n; i++) {
		s += a[i];
		res += a[i] * ((sum - s) % mod);
		if (res >= mod) res %= mod;
	}
	cout << res;
}
// s = a1a2 + a1a3 + ... + a1an // a1(sum - a1)
//	+  a2a3 + a2a4 + ... + a2an // a2(sum - a1 - a2)
//  ... 
//  + a(n - 1)an //
// sum(1...n)(ai(sum - sum(1...i)))
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	for (int i = 1; i <= t; i++) {
		solve();
	}
}

Measured memory_bytes: 3960
def dsum(n,x):
  for i in range(n-1):
    x //= 10
  return x % 10  

a, b = map(int, input().split())
total = 0
for i in range(a,b+1):
  if dsum(1,i) == dsum(5,i) and dsum(2,i) == dsum(4,i):
    total += 1
print(total)

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

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> v(n);
    int a;
    int sum = 0;

    for(int i=0; i<n; i++) cin >> v[i];
    for(int i=0; i<n; i++) sum += v[i];

    int cnt = 0;
    for(int i=0; i<n; i++) if((v[i]*(4*m)) >= sum) cnt++;
    
    if(cnt >= m)
        cout << "Yes" << endl;
    else 
        cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
    void solve(){
        Scanner scan = new Scanner(System.in);
        long a = scan.nextInt();
        long b = scan.nextInt();
        long c = scan.nextInt();
        System.out.println(c - a - b > 0 && 4 * a * b < (c - a - b) * (c - a - b) ? "Yes" : "No");
    }

    public static void main(String[] args){
        new Main().solve();
    }
}


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

// 復習場所
int N, A, B, C;
vector<int> l;
/*
    それぞれの竹に対して
    1. 使わない
    2. Aに使う
    3. Bに使う
    4. Cに使う
    のどれか
    N<=8だからdakara
*/
int dfs(int n, int a, int b, int c){
    if(n==N){
        // a, b, cに一本も竹がない場合を除く
        if(a==0 or b==0 or c==0){
            return 2e5;
        }
        // a, b, cの最初の竹を選ぶ時にも10を足しているため、30を引く
        int tmp = abs(a-A) + abs(b-B) + abs(c-C) - 30;
        return tmp;
    }

    int ans1 = dfs(n+1, a, b, c);
    int ans2 = dfs(n+1, a+l[n], b, c) + 10;
    int ans3 = dfs(n+1, a, b+l[n], c) + 10;
    int ans4 = dfs(n+1, a, b, c+l[n]) + 10;

    return min({ans1, ans2, ans3, ans4});

}


int main() {
    cin >> N >> A >> B >> C;
    l.resize(N);
    for(int i=0; i<N; i++){
        cin >> l[i];
    }

    cout << dfs(0, 0, 0, 0) << endl;

    return 0;
}

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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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

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

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  char c;
  cin >> c;
  if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'){
    cout << "vowel" << endl;
  }else{
    cout << "consonant" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
  int s = 1, x = 1, y = 1, a, b, ans = -1;
  vector<int> price;
  while(s > 0) {
    cin >> x >> y >> s;
    for(int i = 1; i < s; i++) {
      for(int j = 1; j < s; j++) {
	a = (int) i*(100+x)/100;
	b = (int) j*(100+x)/100;
	if(a+b == s){
	  a = (int) i*(100+y)/100;
	  b = (int) j*(100+y)/100;
	  if(ans < a+b) ans = a+b;
	}
      }
      if(i == s-1){
	cout << ans << endl;
	ans = -1;
      }
    }
  }
  return 0;
}
      

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    int N, M;
    cin >> N >> M;
    
    vector<vector<int>> light_bulb(M);
    rep(i, M){
        int K;
        cin >> K;
        rep(j, K){
            int k;
            cin >> k;
            k--;
            light_bulb[i].push_back(k);
        }
    }
    
    vector<int> p(M);
    rep(i, M){
        cin >> p[i];
    }
    
    int ans=0;
    for(int bit=0; bit<(1<<N); bit++){
        vector<int> push_light_bulb(M, 0);
        for(int i=0; i<N; i++){
            if(bit>>i&1){
                rep(j, light_bulb.size()){
                    rep(k, light_bulb[j].size()){
                        if(i==light_bulb[j][k]){
                            push_light_bulb[j]++;
                        }
                    }
                }
            }
        }
        
        bool res=true;
        rep(j, push_light_bulb.size()){
            if(p[j]!=push_light_bulb[j]%2){
                res=false;
            }
        }
        if(res) ans++;
    }
    
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pii pair<int,int>
#define mk make_pair
#define pb push_back
#define eps 1e-12
#define sd(x) scanf("%d",&x)
#define sdl(x) scanf("%lld",&x)
#define pd(x) printf("%d\n",x)
#define pdl(x) printf("%lld\n",x)
#define MAXN 200009
using namespace std;
int fans[MAXN];
vector<pii> v;
int main()
{
	int n;
	sd(n);
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		v.pb(mk(x,i));
	}
	sort(v.begin(),v.end());
	for(int i=0;i<(n/2);i++)
	{
		fans[v[i].second]=v[n/2].first;
	}
	for(int i=(n/2);i<v.size();i++)
	{
		fans[v[i].second]=v[(n/2)-1].first;
	}
	for(int i=0;i<n;i++)
	{
		pd(fans[i]);
	}
	return 0;
}

Measured memory_bytes: 4720
#include <iostream>
#include <functional>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <iomanip>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;++i)
#define repi(i,n) for(ll i=n-1;i>=0;--i)
#define sll(n) scanf("%lld", &n);
#define slf(n) scanf("%lf", &n);
#define pll pair<ll, ll>
typedef long long ll;
typedef double lf;
// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
typedef long long ll;
const int max_n = 200010;
const int mod = 1000000007;
// const int mod = 998244353;

vector<ll> as;
vector<ll> bs;


void Main(){
    // bool is_ok = true;
    // printf("------------- V=%lld---------\n", V);
    ll N, a, b;
    sll(N);
    rep(i, N){
      sll(a);
      sll(b);
      as.emplace_back(a);
      bs.emplace_back(b);
    }

    sort(as.begin(), as.end());
    sort(bs.begin(), bs.end());

    ll ans;
    if(N % 2){
      ll min_x = as[N / 2];
      ll max_x = bs[N / 2];
      // cout << "max x, min_x " << max_x << "," <<min_x <<endl;

      ans = max_x - min_x + 1;
    }else{
      ll min_x = as[(N-1) / 2] + as[N / 2];
      ll max_x = bs[(N-1) / 2] + bs[N / 2];
      // cout << "max x, min_x " << max_x << "," <<min_x <<endl;
      ans = max_x - min_x + 1;
    }
    

    
    cout << ans << endl;
    // M * (M-1)^(N-k-1) * nCk

}

int main(){
    Main();

    return 0;

}

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

// #LIB#

using namespace std;
using ll = long long;
#define double long double
#define rep(i, n) for (long long i = 0; i < (n); ++i)
#define repr(i, a, b) for (auto i = (a); i < (b); ++i)
#define itr(x, c) for (auto&& x : (c))
#define updatemax(t, v) ((t) = std::max((t), (v)))
#define updatemin(t, v) ((t) = std::min((t), (v)))
#define endl _endl
const char _endl = (cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout.precision(16), '\n');

int main() {
  ll h, w;
  cin >> h >> w;
  vector<string> s(h);
  rep(i, h) cin >> s[i];
  vector<vector<bool>> wall(w, vector<bool>(h));
  rep(x, w) rep(y, h) wall[x][y] = s[y][x] == '#';
  vector<vector<ll>> xcon(w, vector<ll>(h)), ycon(w, vector<ll>(h));
  rep(y, h) {
    rep(x, w) xcon[x][y] = wall[x][y] ? 0 : (x ? xcon[x - 1][y] : 0) + 1;
    for (ll x = w - 1; x > 0; --x) {
      if (!wall[x - 1][y]) updatemax(xcon[x - 1][y], xcon[x][y]);
    }
  }
  rep(x, w) {
    rep(y, h) ycon[x][y] = wall[x][y] ? 0 : (y ? ycon[x][y - 1] : 0) + 1;
    for (ll y = h - 1; y > 0; --y) {
      if (!wall[x][y - 1]) updatemax(ycon[x][y - 1], ycon[x][y]);
    }
  }
  ll ans = -1;
  rep(x, w) rep(y, h) updatemax(ans, xcon[x][y] + ycon[x][y] - 1);
  cout << ans << endl;
}


Measured memory_bytes: 70764
using System;
using System.Linq;
using System.Collections.Generic;

using E = System.Linq.Enumerable;

public class Program
{
    public static void Main()
    {
        var nk = Console.ReadLine().Split().Select(x => long.Parse(x)).ToArray();
        var (n, k) = (nk[0], nk[1]);
        var seqA = Console.ReadLine().Split().Select(x => int.Parse(x)).Prepend(1).ToArray();

        ++k;

        var (t, s) = (0, 1);
        var vs = new int[seqA.Length];
        while (k-- > 0 && vs[s] < 1)
        {
            vs[s] = vs[t] + 1;
            (t, s) = (s, seqA[s]);
        }

        if (k < 0)
        {
            s = t;
        }

        k %= vs[t] - vs[s] + 1;
        while (k-- > 0)
        {
            s = seqA[s];
        }

        Console.WriteLine(s);
    }
}


Measured memory_bytes: 43876
N = gets.to_i
S = gets.chomp
Q = gets
Qs = readlines.map(&:split)

@h = Hash.new{|h, k| h[k] = []}
@s = "_" + S.dup
S.each_char.with_index(1){|c, i| @h[c] << i}

def update(i, c)
  d = @s[i]
  return if c == d
  @s[i] = c
  @h[d].delete_at(@h[d].bsearch_index{|x| x >= i})
  @h[c].insert((@h[c].bsearch_index{|x| x >= i} || -1), i)
end

def _kind?(c, l, r)
  (@h[c].bsearch{|x| x >= l} || N + 1) < (@h[c].bsearch{|x| x > r} || N + 1)
end

def kind(l, r)
  ('a' .. 'z').count{|c| _kind?(c, l, r)}
end

Qs.each do |a, b, c|
  if a == '1'
    update(b.to_i, c)
  else
    puts kind(b.to_i, c.to_i)
  end
end

Measured memory_bytes: 18848
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int sosu(long long x){
	int count = 0;
	if(x==2)return 1;
	
	for(long long i=3;i*i<=x;i=i+2){
		if(x%i==0)return 0;
	}
	return 1;
}

int main(){
	
	string s;
	cin >> s;
	int count = 0;
	
	if(s[0]=='A'){
		s[0]='a';
		count++;
	}else{
		cout << "WA" << endl;
		return 0;
	}
	
	for(int i=2;i<s.size()-1;i++){
		if(s[i]=='C'){
			s[i]='c';
			count++;
		}
	}
	
	if(count!=2){
		cout << "WA" << endl;
		return 0;
	}
	
	for(int i=0;i<s.size();i++){
		if('a'<=s[i] && s[i]<='z'){
		}else{
			cout << "WA" << endl;
			return 0;
		}	
	}

	cout << "AC" << endl;
	return 0;
}



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

int main(){
  ll N,M,X;
  cin >> N >> M >> X;
  vector<ll> C(N);
  vector<vector<ll>> A(N,vector<ll>(M));
  rep(i,N){
    cin >> C.at(i);
    rep(j,M){
      cin >> A.at(i).at(j);
    }
  }
  ll ans = INF;
  rep(mask,1<<N){
    ll num = 0;
    vector<ll> y(M);
    rep(i,N){
      if(mask & (1<<i)){
        num += C.at(i);
        rep(j,M){
          y.at(j) += A.at(i).at(j);
        }
      }
    }
    bool b = 1;
    rep(i,M){
      if(y.at(i)<X){
        b=0; break;
      }
    }
    if(b){
      ans = min(ans,num);
    }
  }
  if(ans==INF){
    cout << "-1" << endl;
  }else{
    cout << ans << endl;
  }
}


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

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif


int main() {
  ios:: sync_with_stdio(false);
  cin.tie();
  string s, t;
  cin >> s >> t;
  int ans = t.length();
  for (int i = 0; i + (t.length()) <= s.length(); i++) {
    int cur = 0;
    for (int j = 0; j < t.length(); j++) {
      if (t[j] != s[i + j]) {
        cur++;
      }
    }
    ans = min(ans, cur);
  }
  cout << ans;
  return 0;
}




Measured memory_bytes: 3640
#include    <bits/stdc++.h>
#include    <ext/pb_ds/assoc_container.hpp>
#include    <ext/pb_ds/trie_policy.hpp>
#include    <ext/rope>

#define     ll              long long
#define     ld              long double
#define     fi              first
#define     se              second
#define     sz(x)           x.size()
#define     mp              make_pair
#define     pb              push_back
#define     eb              emplace_back
#define     all(x)          begin(x), end(x)
#define     rall(x)         rbegin(x), rend(x)
#define     rep(i, x, n)    for (ll i = x; i < n; i++)
#define     fastio()        ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0)

using       namespace std;
using       namespace __gnu_pbds;
using       namespace __gnu_cxx;

mt19937     rng(chrono::steady_clock::now().time_since_epoch().count());

typedef     vector<int>     vi;
typedef     vector<vi>      vvi;
typedef     pair<int, int>  ii;
typedef     vector<ii>      vii;
typedef     vector<ll>      vl;
typedef     vector<vl>      vvl;
typedef     pair<ll, ll>    pll;
typedef     vector<pll>     vll;

inline void EXECUTE_TIME() {cout << endl << setprecision(10) << fixed << "CPU Time: " << clock() / double(CLOCKS_PER_SEC) << " sec(s)\n";}

template <class T> inline T RD(T &a) {T x; cin >> x; return a = x;}
template <class T> inline T gcd(T a, T b) {if (b) return gcd(b, a % b); else return a;}
template <class T> inline T lcm(T a, T b) {return a / gcd(a,b) * b;}
template<typename T> using ordered_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;

const int N = 5e5 + 10;
const int bl = 700;
int n, q;

int a[N];

int cnt[N];
int res = 0;

int ans[N];

struct queries {
    int l, r, id;
};

bool cmp(queries p, queries q) {
    if (p.l / bl != q.l / bl) return p.l < q.l;
    return (p.l / bl & 1) ? (p.r < q.r) : (p.r > q.r);
}

queries query[N];

void add(int i) {
    cnt[a[i]]++;
    if (cnt[a[i]] == 1) res++;
}

void sub(int i) {
    cnt[a[i]]--;
    if (cnt[a[i]] == 0) res--;
}

void solve() {
    sort(query, query + q, cmp);
    int cur_l = 0, cur_r = -1;
    queries x;
    for (int i = 0; i < q; i++) {
        x = query[i];
        while (cur_l > x.l) {
            cur_l--;
            add(cur_l);
        }
        while (cur_r < x.r) {
            cur_r++;
            add(cur_r);
        }
        while (cur_l < x.l) {
            sub(cur_l);
            cur_l++;
        }
        while (cur_r > x.r) {
            sub(cur_r);
            cur_r--;
        }
        ans[x.id] = res;
    }
    for (int i = 0; i < q; i++) {
        cout << ans[i] << endl;
    }
}

signed main()
{
//    freopen("test.inp","r",stdin);
//    freopen("test.out","w",stdout);
	fastio();

	cin >> n >> q;
	rep(i, 0, n) cin >> a[i];
	rep(i, 0, q) {
        cin >> query[i].l >> query[i].r;
        query[i].l--, query[i].r--;
        query[i].id = i;
	}
	solve();
}


Measured memory_bytes: 15444
//============================================================================
// Name        : e.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

int main() {
	int n,k;cin>>n>>k;
	vector<int> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	vector<int> v;
	int ans=1;
	int sum=0;
	for(int i=0;i<n;i++){
		sum+=a[i];
	}
	for(int i=1;i*i<=sum;i++){
		if(sum%i)continue;
		v.push_back(i);
	}
	int vs=v.size();
	for(int i=0;i<vs;i++){
		v.push_back(sum/v[i]);
	}
	for(int i=0;i<v.size();i++){;
		vector<int> p,m;
		for(int j=0;j<n;j++){
			p.push_back(v[i]-(a[j]%v[i]));
			m.push_back(a[j]%v[i]);
		}
		sort(p.begin(),p.end());
		sort(m.begin(),m.end());
		for(int j=1;j<n;j++){
			p[j]+=p[j-1];
			m[j]+=m[j-1];
		}
		for(int j=0;j<n-1;j++){
			if(p[j]==m[n-2-j]){
				if(p[j]<=k){
					ans=max(ans,v[i]);
				}
				break;
			}
			if(j==n-2){
//				for(int k=0;k<n;k++){
//					cout<<p[k]<<' ';
//				}cout<<endl;
//				for(int k=0;k<n;k++){
//					cout<<m[k]<<' ';
//				}cout<<endl;
				ans=max(ans,v[i]);
			}
		}

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


Measured memory_bytes: 256