akhauriyash/Code-Regression huggingface dataset:
import sys
from collections import deque
readline=sys.stdin.readline

def main():
    k=int(readline())
    v=list(range(k))
    inf=float('inf')
    dist=[inf]*k
    visited=[0]*k
    stack=deque([1])
    dist[1]=0
    while stack:
        v=stack.pop()
        if not visited[v]:
            nv0=10*v%k
            nv1=(v+1)%k
            if dist[nv0]>dist[v]:
                dist[nv0]=dist[v]
                stack.append(nv0)
            if dist[nv1]>dist[v]+1:
                dist[nv1]=dist[v]+1
                stack.appendleft(nv1)
            visited[v]=1
    print(dist[0]+1)

if __name__=='__main__':
    main()


Measured memory_bytes: 14668
import java.util.*;

class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int H = sc.nextInt();
        int W = sc.nextInt();
        int h = sc.nextInt();
        int w = sc.nextInt();
        int White = (H -h) * (W -w);
        System.out.println(White);  
    }
}

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

ll nextLong() { ll x; scanf("%lld", &x); return x;}


struct Trie {
  int ch[26];
  int ex;
  Trie() {
    clear();
  }
  void clear() {
    REP(i, 26) ch[i] = -1;
    ex = 0;
  }
};

const int MAX_C = 1123456;
Trie trie[MAX_C];
int trie_sz = 0;

void add_trie(const int id, const string &s, const int pos) {
  if (pos == (int)s.size()) {
    trie[id].ex = 1;
    return;
  }
  int c = s[pos] - 'a';
  if (trie[id].ch[c] == -1) {
    trie[id].ch[c] = trie_sz++;
  }
  add_trie(trie[id].ch[c], s, pos + 1);
}

void walk_trie(const int id, const string&s, const int pos, ll &ans, vector<ll>& count) {
  if (pos == (int)s.size()) {
    return ;
  }

  REP(d, 26) if (count[d] > 0) {
    int nid = trie[id].ch[d];
    if (nid != -1) {
      if (trie[nid].ex) { ans++;
      //  cout << s.substr(0, pos) << " " << (char)(d+'a') << endl;
      }
    }
  }

  int c = s[pos] - 'a';
  if (trie[id].ch[c] != -1) {
    count[c]--;
    walk_trie(trie[id].ch[c], s, pos + 1, ans, count);
  }
}

int main2() {
  int N = nextLong();
  vector<string> S;
  REP(i, N) {
    string s; cin >> s;
    reverse(ALL(s));
    S.push_back(s);
  }
  sort(ALL(S), [](const string&a, const string &b) {
    if (a.size() != b.size()) return a.size() < b.size();
    return a < b;
  });

  const int root = 0;
  trie_sz++;

  ll ans = 0;
  REP(i, N) {
    const string& s = S[i];
    vector<ll> count(26);
    REP(i, s.size()) count[s[i] - 'a']++;
    walk_trie(root, s, 0, ans, count);

    // cout << "ans=" << ans << endl;
    // cout << "add: " << s << endl;
    add_trie(root, s, 0);
  }

  cout << ans << endl;



  REP(i, trie_sz) trie[i].clear();
  trie_sz = 0;
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}

Measured memory_bytes: 130156
#include<bits/stdc++.h>
using namespace std;
long long cf(int x){
	long long b=1;
	for(int i=0;i<x;i++)b*=2;
	return b;
} 
int main(){
	long long h;
	cin>>h;
	int i=0;
	for(;h!=1;i++){
		if(h%2==1)h--;
		h/=2;
	}
	cout<<cf(i+1)-1;
	return 0;
}

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

using namespace std;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define DEBUG_MAT(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;}


typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
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 (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { -1,0, 1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
//#define mp make_pair

int main() {
  int n;
  cin >> n;
  vi a(n);
  rep (i, n) {
    cin >> a[i];
  }

  vl sum(n + 1);
  rep (i, n) {
    sum[i + 1] = sum[i] + a[i];
  }

  ll ans = INF;
  rep1 (i, n - 1) {
    chmin(ans, abs(sum[i] - (sum[n] - sum[i])));
  }
  cout << ans << endl;
}


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

int main(){
    int n;cin>>n;
    int comp[n][n];
    for(int i=0;i<n;i++)for(int j=0;j<n;j++) cin>>comp[i][j];
    
    vector<int> dp(1<<n); // 1<<n mask to check which women are assigned
    dp[0] = 1;
    for(int i=0;i<(1<<n);i++){
        int m = __builtin_popcount(i);
        for(int w = 0; w < n; w++){ // which woman
            if(!(i & 1<<w) && comp[m][w]){ // if we can assign
                int j = i | (1<<w);  //then assign
                dp[j] += dp[i];
                dp[j] %= (1000000007);
            }
        }
    }
    cout<<dp[(1<<n) - 1];
    
}

Measured memory_bytes: 11432
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = Integer.parseInt(sc.next());
		int m = Integer.parseInt(sc.next());
		int x = Integer.parseInt(sc.next());
		
		int N = (int)Math.pow(2, n);
		
		int []c = new int [n];
		int [][]a = new int [n][m];
		
		for(int i = 0 ; i < n ;i++) {
			c[i] = Integer.parseInt(sc.next());
			for(int j = 0 ; j < m ; j++) {
				a[i][j] = Integer.parseInt(sc.next());
			}
		}
		
		long max = 100000000000000L;
		
	f:	for(int i = 0 ; i < N ;i++) {
			int []ab = new int [m];
			boolean jdg = true;
			long temp = 0;
			for(int j = 0 ; j < n ;j++) {
				if(((i >> j) & 1) == 1) {
					temp += (long)c[j];
					for(int k = 0 ; k < m ;k++) {
						ab[k] += a[j][k];
					}
				}
			}
			for(int k = 0 ; k < m ; k++) {
				if(ab[k] < x){
					jdg = false; 
				}
			}
			if(jdg) {
			max = Math.min(temp,max);
			jdg = true;
			}
		}
		
		if(max != 100000000000000L) {
			System.out.println(max);
		}
		else {
			System.out.println(-1);
		}
	}

}


Measured memory_bytes: 37100
#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

void DFS(int R, int par, int K, vector< vector<int> > &G, vector< vector<int> > &ansd, vector<int> &S) {
	ALL_THE(G[R],it) if(*it != par) {
		DFS(*it,R,K,G,ansd,S);
		S[R] +=S[*it];}
	ansd[R][0] =S[R]-1;
	for(int k =1; k <= K; k++) {
		int mxd2 =min(k-1,K-k-1), sum =0;
		ALL_THE(G[R],it) if(*it != par) {
			if(mxd2 >= 0) sum +=ansd[*it][mxd2];
			else sum +=S[*it];}
		ansd[R][k] =min(sum,ansd[R][k-1]);
		ALL_THE(G[R],it) if(*it != par) {
			if(mxd2 >= 0) sum -=ansd[*it][mxd2];
			else sum -=S[*it];
			ansd[R][k] =min(ansd[R][k],ansd[*it][k-1]+sum);
			if(mxd2 >= 0) sum +=ansd[*it][mxd2];
			else sum +=S[*it];}
		// max. hlbka x, max. dlzka <= K
		// najhlbsi podstrom = x-1, zvysne min(x-1,K-x-1)
		}
	}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N,K;
	cin >> N >> K;
	vector< vector<int> > G(N);
	for(int i =0; i < N-1; i++) {
		int u,v;
		cin >> u >> v;
		G[--u].push_back(--v);
		G[v].push_back(u);}
	vector< vector<int> > ansd(N,vector<int>(K+1,0));
	vector<int> S(N,1);
	DFS(0,0,K,G,ansd,S);
	int ans =N;
	for(int i =0; i < N; i++) ans =min(ans,S[0]-S[i]+ansd[i][K]);
	cout << ans << "\n";
	return 0;}

// look at my code
// my code is amazing


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

int main(){
    int h, w;
    cin >> h >> w;
    bool field[h+1][w+1];
    for(int i = 1; i <= h; i++){
        char c;
        for(int j = 1; j <= w; j++){
            cin >> c;
            if(c == '#'){
                field[i][j] = false;
            } else {
                field[i][j] = true;
            }
        }
    }

    int ans = 0;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            int tmp = 0;
            if(field[i][j]){
                //up
                for(int k = i+1; k <= h; k++){
                    if(!field[k][j]){
                        break;
                    } else {
                        tmp++;
                    }
                }
                //down
                for(int k = i-1; k >=1; k--){
                    if(!field[k][j]){
                        break;
                    } else {
                        tmp++;
                    }
                }
                //right
                for(int k = j+1; k <= w; k++){
                    if(!field[i][k]){
                        break;
                    } else {
                        tmp++;
                    }
                }
                //down
                for(int k = j-1; k >=1; k--){
                    if(!field[i][k]){
                        break;
                    } else {
                        tmp++;
                    }
                }
                ans = max(ans, tmp+1);
            }
            if(ans == h + w - 1){
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4096
s = input()

ans = 100
for _ in 'abcdefghijklmnopqrstuvwxyz':
    S = list(s)
    cnt = 0
    for i in range(len(S)):
        if len(set(S)) == 1:
            ans = min(ans, cnt)
            break
        T = []
        for j in range(len(S)-1):
            if S[j] == _ or S[j+1] == _:
                T.append(_)
            else:
                T.append(S[j])
        cnt += 1
        S = T

print(ans)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define sz 100002
#define pb push_back
#define ff first
#define ss second
#define ll long long
#define VEC(n)  int x; vector<ll int>v;for(int i=0;i<n;i++){cin>>x;v.pb(x);}
#define TEST() int test;cin>>test; while(test--)
#define FAST() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;

//ll int LCM(ll int a,ll int b) { ll int gcd=__gcd(a,b);ll int lcm=a*b/gcd;return lcm;}
//ll int bigmod(ll int b, ll int p, ll int m){if(p==0)return 1;if(p%2!=0) return b%m*fun(b,p-1,m)%m;if(p%2==0){ ll int res=fun(b,p/2,m);return (res%m*res%m)%m;}}
//void seive() { prime[np++]=2;for(i=3; i<=sz; i+=2){if(mark[i]==0){ prime[np++]=i;for(j=i*i; j<=sz; j+=i) mark[j]=1; } }}
//string add(string s1,string s2) {string s;int j=s1.size()-1,c=0,m; for(int i=s2.size()-1; i>=0; i--) {if(j>=0)m=s2[i]-'0'+s1[j]-'0'+c;else m=s2[i]-'0'+c; if(m>9) { s+=m%10+'0';c=m/10; } else {  c=0;s+=m+'0'; }j--; } if(c!=0) {s+=c+'0'; }reverse(s.begin(),s.end());return s;}
//int pos;string mul(int n) {string s;for(int i=0; i<pos; i++) { s+="0"; }pos++;int c=0,m; for(int i=s1.size()-1; i>=0; i--) { m=(s1[i]-'0')*n+c;if(m>9) { s+=m%10+'0';c=m/10;} else { c=0; s+=m+'0';} }while(c!=0) { s+=c%10+'0';c=c/10;}    reverse(s.begin(),s.end());return s;}

int main()
{
    FAST();
    ll int n,m,res;


char ch;
cin>>ch;
for(int i='A';i<='Z';i++)
{
  
    if(ch==i){cout<<"A"<<endl;return 0;}
}
 cout<<"a"<<endl;

}



Measured memory_bytes: 3636
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization("O3")
// #pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>

#define int long long
#define double long double
#define endl '\n'
#define gcd __gcd
#define f first
#define s second
#define what_is(x) cerr << #x << " is " << x << endl;
#define all(x) x.begin(), x.end()
const int inf = 1000000;
// const int inf = __LONG_LONG_MAX__;

using namespace std;

vector<string> matrix;
int h, w;
int V;

void fast_io() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

void printSolution(int dist[400][400]) {
  int m = -1;
  for (int i = 0; i < V; i++)
    for (int j = 0; j < V; j++)
      if (dist[i][j] != inf) m = max(m, dist[i][j]);

  cout << m << "\n";
}

void floydWarshall(int graph[400][400]) {
  int dist[400][400], i, j, k;
  for (i = 0; i < V; i++)
    for (j = 0; j < V; j++) dist[i][j] = graph[i][j];

  for (k = 0; k < V; k++) {
    for (i = 0; i < V; i++) {
      for (j = 0; j < V; j++) {
        if (dist[i][k] + dist[k][j] < dist[i][j])
          dist[i][j] = dist[i][k] + dist[k][j];
      }
    }
  }

  printSolution(dist);
}

signed main() {
  fast_io();

  cin >> h >> w;
  int g[400][400];

  for (int i = 0; i < 400; i++)
    for (int j = 0; j < 400; j++) g[i][j] = inf;

  V = h * w;

  matrix.resize(h);

  for (int i = 0; i < h; i++) cin >> matrix[i];

  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (matrix[i][j] == '.') {
        int n = i * w + j;
        g[n][n] = 1;

        if (i >= 1)
          if (matrix[i - 1][j] == '.') {
            g[n - w][n] = g[n][n - w] = 1;
          }
        if (i <= h - 2)
          if (matrix[i + 1][j] == '.') {
            g[n + w][n] = g[n][n + w] = 1;
          }
        if (j >= 1)
          if (matrix[i][j - 1] == '.') {
            g[n - 1][n] = g[n][n - 1] = 1;
          }
        if (j <= w - 2)
          if (matrix[i][j + 1] == '.') {
            g[n + 1][n] = g[n][n + 1] = 1;
          }
      }
    }
  }

  floydWarshall(g);

  return 0;
}


Measured memory_bytes: 2816
n, m, c = map(int, input().split())
*B, = map(int, input().split())
cnt = 0
for i in range(n):
    *A, = map(int, input().split())
    if sum([A[j]*B[j] for j in range(m)])+c > 0:
        cnt += 1
print(cnt)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <string>
  
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)
typedef long long ll;

const ll MOD=1000000007ll;
const int MAX=5100000;

using namespace std;

int inputValue(){
    int a;
    cin >> a;
    return a;
};

void inputArray(int * p, int a){
    rep(i, a){
        cin >> p[i];
    }
};

void inputVector(vector<int> * p, int a){
    rep(i, a){
        int input;
        cin >> input;
        p -> push_back(input);
    }
}

ll fact[MAX], fact_inv[MAX];

ll power(ll a, ll b){
	ll res=1;
	while(b>0){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}

// nCr
ll comb(ll n, ll r){
	ll t=1000000;
	fact[0]=1;
	REP(i, t) fact[i+1]=fact[i]*(i+1)%MOD;
	fact_inv[t]=power(fact[t], MOD-2);
	FORR(i, 0, t) fact_inv[i]=fact_inv[i+1]*(i+1)%MOD;
	return (fact[n]*fact_inv[r])%MOD*fact_inv[n-r]%MOD;
}
  
int main()
{
  int x,y; cin >> x >> y;
  if(y%2==1){cout << "No" << endl; return 0;}
  if(y > 4*x || y < 2*x){cout << "No" << endl; return 0;}
  cout << "Yes" << endl;

  return 0;
}


Measured memory_bytes: 3640
#include <iostream>
#include <algorithm>
using namespace std;
int A, B, C, D, E, F;
int main() {
	cin >> A >> B >> C >> D >> E >> F;
	int res1 = -1, res2 = -1;
	for (int i = 0; 100 * i * A <= F; i++) {
		for (int j = 0; 100 * j * B <= F; j++) {
			for (int k = 0; k * C <= F; k++) {
				for (int l = 0; l * C <= F; l++) {
					int q = 100 * i * A + 100 * j * B + k * C + l * D, p = k * C + l * D;
					if (1 <= q && q <= F && (res1 == -1 || (res1 * q < res2 * p)) && q * E >= p * (100 + E)) res1 = p, res2 = q;
				}
			}
		}
	}
	cout << res2 << ' ' << res1 << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string>
#define ft first
#define sc second
#define pt(sth) cout << sth << "\n"
#define chmax(a, b) (a)=(a>b)?(a):(b);
#define chmin(a, b) (a)=(a<b)?(a):(b);
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=1e9+7;


/*
 for(i=0; i<N; i++)
   cin >> a[i];
*/



int main(void) {
  ll i, j, k;
  
  ll X, Y, A, B, C;
  cin >> X >> Y >> A >> B >> C;
  ll p[MAX], q[MAX], r[MAX];
  
  for(i=0; i<A; i++) cin >> p[i];
  for(i=0; i<B; i++) cin >> q[i];
  for(i=0; i<C; i++) cin >> r[i];
  sort(p, p+A); reverse(p, p+A);
  sort(q, q+B); reverse(q, q+B);
  sort(r, r+C); reverse(r, r+C);
  
  ll ans=0;
  for(i=0; i<X; i++) ans+=p[i];
  for(i=0; i<Y; i++) ans+=q[i];
  ll t=ans;
  
  ll a=X-1, b=Y-1;
  for(i=0; i<C; i++) {
    t+=r[i];
    
    if(a<0 && b<0) continue;
    
    if(a<0) {
      t-=q[b];
      b--;
    }else if(b<0) {
      t-=p[a];
      a--;
    }else if(p[a]<q[b]) {
      t-=p[a];
      a--;
    }else {
      t-=q[b];
      b--;
    }
    
    chmax(ans, t);
  }
  
  pt(ans);
  

  
  
}




Measured memory_bytes: 2560
//Optional FAST

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,avx2,tune=native")

//Required Libraries

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

//Required namespaces

using namespace std;
using namespace __gnu_pbds;

//Required defines

#define endl '\n'

#define READ(X) cin>>X;
#define READV(X) long long X; cin>>X;
#define READAR(A,N) long long A[N]; for(long long i=0;i<N;i++) {cin>>A[i];}
#define rz(A,N) A.resize(N);
#define sz(X) (long long)(X.size())
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define FORI(a,b,c) for(long long a=b;a<c;a++)
#define FORD(a,b,c) for(long long a=b;a>c;a--)

//Required typedefs

typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<long long,null_type,greater<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set1;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;

//Required Constants

const long long inf=(long long)1e18;
const long long MOD=(long long)(1e9+7);
const long long INIT=(long long)(1e6+1);
const long double PI=3.14159265358979;

// Required random number generators

// mt19937 gen_rand_int(chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 gen_rand_ll(chrono::steady_clock::now().time_since_epoch().count());

//Required Functions

ll power(ll x,ll y) 
{ 
    if (y == 0) 
        return 1; 
    ll p = power(x, y/2) % MOD; 
    p = (p * p) % MOD; 
  
    return (y%2 == 0)? p : (x * p) % MOD; 
}
ll modInverse(ll a) 
{ 
   return power(a,MOD-2); 
   
}

//Work

int main()
{
    #ifndef ONLINE_JUDGE
    if (fopen("INPUT.txt", "r"))
    {
        freopen ("INPUT.txt" , "r" , stdin);
        //freopen ("OUTPUT.txt" , "w" , stdout);
    }
    #endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    clock_t clk;
    clk = clock();
//-----------------------------------------------------------------------------------------------------------//

    READV(N);
    cout<<(1000-(N%1000))%1000<<endl;

//-----------------------------------------------------------------------------------------------------------//


    clk = clock() - clk;
    cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << endl;

    return 0;
}

Measured memory_bytes: 3796
#include <stdio.h>

int main(int ac, char **av) {
  char buf[256];
  int a, b, c, d, n, count;
  while(fgets(buf, 256, stdin) != NULL) {
    sscanf(buf, "%d", &n);
    count = 0;
    for(a = 0; a < 10; a++) {
      for(b = 0; b < 10; b++) {
        for(c = 0; c < 10; c++) {
          for(d = 0; d < 10; d++) {
            if (a + b + c + d == n) {
              count++;
            }
          }
        }
      }
    }
    printf("%d\n", count);
  }
  return 0;
}

Measured memory_bytes: 604
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vd = vector<double>;
using vvd = vector<vector<double>>;
using vvvd = vector<vector<vector<double>>>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vs = vector<string>;
using pint = pair<int, int>;
using Graph = vvi;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
bool cmp(pint a, pint b) {return a.second < b.second;}
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; }

const ll INF = 1LL<<60;
const int maxN = 15;
const int maxW = 110000;

//素数判定
bool isPrime(ll n){
   if (n < 2) return false;
   for(int i = 2; i < (ll)(sqrt(n) + 1); i++) {
      if (n % i == 0) return false;
   }
   return true;
}

int main() {
    int x;
    cin >> x;
    
    bool flg = false;
    while(!flg) {
        if(isPrime(x)) break;
        x++;
    }

    cout << x << endl;

    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repe(i,n) for (int i = 0; i <= (n); ++i)
#define repe1(i,n) for (int i = 0; i <= (n); ++i)
#define all(x) (x).begin(),(x).end()
#define pb(x) push_back(x)
#define eb(k,v) emplace_back(k,v)
#define ct(res) cout << res << "\n";
#define vi vector<int>
#define vl vector<ll>
using namespace std;
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; }
const int INF = 1e9;
const ll MOD = 1000000007;
const double pi = 3.141592653589;
using Graph = vector<vector<int>>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int n;cin>>n;
	vi s(n);rep(i,n) cin >> s[i];
	sort(all(s));
	ll total = 0;
	rep(i,n) {
		total += s[i];
	}
	int i=0;
	ll ans = 0;
	if (total%10==0) {
		while(i<n) {
			ll tmp = total;
			ll tt = tmp - s[i];
			if (tt%10!=0) {
				chmax(ans,tt);
			}
			i++;
		}
	} else {
		ans = total;
	}
	ct(ans);
}

Measured memory_bytes: 256
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define db long double
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(), (x).end()

void dout() { cerr << '\n'; }

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

#ifdef LOCAL
    #define dbg(...) cerr << #__VA_ARGS__, dout(__VA_ARGS__)
#else
    #define dbg(...) ;
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;

int v[107];

int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif

    ll n, k;
    cin >> n >> k;
    n %= k;
    if (n > k / 2) {
        n = k - n;
    }
    cout << n;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cassert>
#include<cmath>
#define ll long long
using namespace std;
inline ll read(){
	ll re=0,flag=1;char ch=getchar();
	while(ch>'9'||ch<'0'){
		if(ch=='-') flag=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
	return re*flag;
}
char s[400010];
ll n,a[400010],cnt[110][26],fib[110],fail[400010],m,b[400010],ans[26],l,r;
void getb(){
	ll i,j=0;fail[0]=fail[1]=0;
	for(i=1;i<n;i++){
//		cout<<"enter kmp "<<i<<' '<<j<<' '<<a[i]<<' '<<a[j]<<'\n';
		while(a[i]!=a[j]&&j) j=fail[j];
		j+=(a[i]==a[j]);fail[i+1]=j;
	}
//	for(i=0;i<=n;i++) cout<<i<<' '<<fail[i]<<'\n';
	for(i=0;i<n-fail[n];i++) b[i]=a[i];
	m=n-fail[n];
}
void solve(ll lim,ll type){
	ll i,j;
//	cout<<"solve "<<lim<<' '<<type<<'\n';
	if(lim<=n){
		for(i=1;i<=lim;i++) ans[a[i]]+=type;
		return;
	}
	for(i=1;i<=100;i++){
		if(fib[i]<=lim) continue;
		for(j=0;j<26;j++) ans[j]+=cnt[i-1][j]*type;
		solve(lim-fib[i-1],type);break;
	}
}
void add(ll len,ll type){
	ll i,tot=len/m;
	for(i=1;i<=m;i++) ans[b[i]]+=tot*type;
	for(i=tot*m+1;i<=len;i++) ans[b[i-tot*m]]+=type;
} 
void another(){
	add(l-1,-1);add(r,1);
}
int main(){
//	freopen("1.txt","r",stdin);
	scanf("%s",s);n=strlen(s)>>1;ll i,j;
	l=read();r=read();
	for(i=0;i<n;i++) a[i]=s[i]-'a';
	getb();
	for(i=n;i>=1;i--) a[i]=a[i-1];
	for(i=m;i>=1;i--) b[i]=b[i-1];
//	if(n%m==0){
//		another();goto print;
//	}
	for(i=1;i<=n;i++) cnt[0][a[i]]+=1,cnt[1][a[i]]+=1;
	for(i=1;i<=m;i++) cnt[1][b[i]]+=1;
	fib[0]=n;fib[1]=(n+m);
	for(i=2;i<=100;i++){
		fib[i]=fib[i-1]+fib[i-2];
		for(j=0;j<=25;j++) cnt[i][j]=cnt[i-1][j]+cnt[i-2][j];
	}
//	for(i=0;i<26;i++) cout<<i<<' '<<cnt[0][i]<<' '<<cnt[1][i]<<'\n';
	solve(l-1,-1);
	solve(r,1);
	print:
	for(i=0;i<26;i++) printf("%lld ",ans[i]);
}


Measured memory_bytes: 5376
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
template<class T> inline void chmin(T& a, T b) {if (a>b) a=b; }
template<class T> inline void chmax(T& a, T b) {if (a<b) a=b; }
inline void print() { cout << endl; }
template <class Head, class... Tail> inline void print(Head&& head, Tail&&... tail) {cout << head; if (sizeof...(tail) != 0) cout << " "; print(forward<Tail>(tail)...);}
template <class T> inline void print(vector<T>& vec) { for (auto& a : vec) {cout << a; if (&a != &vec.back()) cout << " "; } cout << endl;}
template <class T> inline void print(vector<vector<T>>& df) { for (auto& vec : df) { print(vec); }}
typedef long long ll;
const ll LINF = 1e18;
const int INF = 1e9;


int main() { 
    int N; cin >> N;
    vector<int> P;
    REP(i, N) {
        int p; cin >> p;
        P.push_back(p);
    }

    int maxV = *max_element(P.begin(), P.end());
    bool useHangaku = false;
    int price = 0;
    REP(i, N) {
        if (P[i] == maxV && !useHangaku) {
            price += P[i]/2;
            useHangaku = true;
        } else {
            price += P[i];
        }
    }

    cout << price << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int
main
(
void
)
{
int
j
,
i
,
N
,
A[
100
]
,
key
;
scanf
(
"%d"
,
&
N
)
;
for
(
j
=
0
;
j
<
N
;
j
++
)
{
scanf
(
"%d"
,
&
A
[
j
]
)
;
printf
(
"%d"
,
A
[
j
]
)
;
if
(
j
<
N
-
1
)
{
printf
(
" "
)
;
}
}
printf
(
"\n"
)
; 
for
(
j
=
1
;
j
<
N
;
j
++
)
{
key
=
A
[
j
]
;
i
=
j
-
1
;
while
(
A
[
i
]
>
0
&&
A
[
i
]
>
key
)
{
A
[
i
+
1
]
=
A
[
i
]
;
i
=
i
-
1
;
}
A
[
i
+
1
]
=
key
;
for
(
i
=
0
;
i
<
N
;
i
++
)
{
printf
(
"%d"
,
A
[
i
]
)
;
if
(
i
<
N
-
1
)
{
printf
(
" "
)
;
}
}     
printf
(
"\n"
)
;
}
return
0
;
}

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

using namespace std;

typedef long long ll;
#define mems(p) memset(p,-1,sizeof(p))
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define nl "\n"

const int mxN = 1e5;
const ll MOD = 1e9 + 7;

void fast()
{ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}

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

int main() {
	fast();
	int n, ans = 0;
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		int x;
		cin >> x;
		if (i % 2 == 1 && x % 2 == 1) {
			++ans;
		}
	}
	cout << ans << nl;
}

Measured memory_bytes: 3608
// Rustで競技プログラミングの入力をスッキリ記述するマクロ
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
  input! {
      n: usize,
      a: [usize; n]
  };
  println!("{}", a.iter().fold(0, |sum, v| sum + v) - n);
}


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

int N;

int main(){
    cin >> N;
    vector<int> aa = vector<int>(100002, 0);
    int buf;
    for(int i = 1; i<=N; i++){
        cin >> buf;
        if(buf != 0){
            aa.at(buf - 1) += 1;
        }

        aa.at(buf) +=1;
        aa.at(buf+1) +=1;
    }
    sort(aa.begin(), aa.end());

    auto it = aa.end();
    it--;
    cout << *it << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned long long 
#define f(i,x,n) for(ll int i=x;i<n;i++) 
#define re(j,x,n) for(ll int j=x;j>=n;j--)
#define f1(k,x,n) for(ll int k=x;k<=n;k++)
#define mp make_pair
#define pb push_back
#define mod 1000000007
#define MAX 1000001
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll int n;
    cin>>n;
    ll int mn=n-1,f=0;
    f1(i,2,sqrt(n))
    {
      if(n%i==0)
      {
      	f=1;
      	break;
      }
    }
    if(f==0)
    {
      cout<<n-1;
      return 0;
    }
    f1(i,2,sqrt(n))
    {
      if(n%i==0)
      { 
      	if(mn<(i-1)+((n/i)-1))
      		break;
      	mn=min(mn,(i-1)+((n/i)-1));
      }
    }
    cout<<mn;
}

Measured memory_bytes: 256
k=int(input())
ans=int(0)
n=0
dp=[0]*(1000000)
f=int(0)
for i in range(0,1000000):
    ans+=1
    n=n*10+7
    if(n%k==0):
        break
    n=n%k
    if(dp[n]):
        f=1
        break
    else:
        dp[n]=1
if(f):
    print("-1")
else:
    print(ans)
        


Measured memory_bytes: 16784
#include<bits/stdc++.h>
using namespace std;
int main(){int k,ans=0;cin>>k;for(int a=1;a<=k;a++)for(int b=1;b<=k;b++)for(int c=1;c<=k;c++)ans+=__gcd(__gcd(a,b),c);cout<<ans<<endl;}


Measured memory_bytes: 3608
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

typedef vector<int> vi;
typedef vector<bool> vb;

const int OFFSET = 80 * 160;
int H, W;
vector<vi> A, B;
vector<vector<vb> > dp;

void input_init(void) {
	cin >> H >> W;
	A.resize(H, vi(W));
	B.resize(H, vi(W));
	for (int j = 0; j < H; ++j) {
		for (int i = 0; i < W; ++i)
			cin >> A[j][i];
	}
	for (int j = 0; j < H; ++j) {
		for (int i = 0; i < W; ++i)
			cin >> B[j][i];
	}
}

void solve(void) {
	dp.resize(H, vector<vb>(W, vb(2 * OFFSET + 1, false)));
	dp[0][0][OFFSET + abs(A[0][0] - B[0][0])] = true;
	dp[0][0][OFFSET - abs(A[0][0] - B[0][0])] = true;
	for (int i = 1; i < W; ++i) {
		int diff = abs(A[0][i] - B[0][i]);
		for (int k = 0; k <= 2 * OFFSET; ++k) {
			if (dp[0][i - 1][k]) {
				dp[0][i][k + diff] = true;
				dp[0][i][k - diff] = true;
			}
		}
	}
	for (int j = 1; j < H; ++j) {
		int diff = abs(A[j][0] - B[j][0]);
		for (int k = 0; k <= 2 * OFFSET; ++k) {
			if (dp[j - 1][0][k]) {
				dp[j][0][k + diff] = true;
				dp[j][0][k - diff] = true;
			}
		}
	}
	for (int j = 1; j < H; ++j) {
		for (int i = 1; i < W; ++i) {
			int diff = abs(A[j][i] - B[j][i]);
			for (int k = 0; k <= 2 * OFFSET; ++k) {
				if (dp[j - 1][i][k]) {
					dp[j][i][k + diff] = true;
					dp[j][i][k - diff] = true;
				}
				if (dp[j][i - 1][k]) {
					dp[j][i][k + diff] = true;
					dp[j][i][k - diff] = true;
				}
			}
		}
	}
}

int val_check(void) {
	int val = 0;
	for (int i = 0; i <= OFFSET; ++i) {
		if ((dp[H - 1][W - 1][OFFSET + i] == true)
				|| (dp[H - 1][W - 1][OFFSET - i] == true)) {
			val = i;
			break;
		}
	}
	return val;
}

int main(void) {
	input_init();
	solve();
	int ans = val_check();
	cout << ans << '\n';
	return 0;
}


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

int main(){
  int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
  
  
  int x3=y1-y2+x2;
  
  int y3=x2-x1+y2;
  
  int x4=x1-y2+y1;
  
  int y4=y1-x1+x2;
  
  cout<<x3<<" "<<y3<<" "<<x4<<" "<<y4<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define lson (o<<1)
#define rson (o<<1|1)
#define fi first
#define sc second
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
using namespace std;
const double pi=acos(-1);
const double eps=1e-6;
inline int lowbit(int x){return x&(-x);}
inline int read(){
	int f=1,x=0;char ch;
	do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
	do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
	return f*x;
}
template<typename T> inline T max(T x,T y,T z){return max(max(x,y),z);}
template<typename T> inline T min(T x,T y,T z){return min(min(x,y),z);}
template<typename T> inline T sqr(T x){return x*x;}
template<typename T> inline void checkmax(T &x,T y){x=max(x,y);}
template<typename T> inline void checkmin(T &x,T y){x=min(x,y);}
template<typename T> inline void read(T &x){
x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;
}
template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){
	A ans=1;
	for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql;
	return ans;
}
struct FastIO{
	static const int S=1310720;
	int wpos;char wbuf[S];
	FastIO():wpos(0){}
	inline int xchar(){
		static char buf[S];
		static int len=0,pos=0;
		if(pos==len)pos=0,len=fread(buf,1,S,stdin);
		if(pos==len)return -1;
		return buf[pos++];
	}
	inline int read(){
		int c=xchar(),x=0;
		while(c<=32&&~c)c=xchar();
		if(c==-1)return -1;
		for(;'0'<=c&&c<='9';c=xchar())x=x*10+c-'0';
		return x;
	}
}io;
//#define read io.read
int pow(int a,int b)
{
    if(b==0) return 1;
    if(b%2) return a*pow(a,b-1);
    else return pow(a*a,b/2);
}
void nope()
{
    cout << -1 << endl;
    exit(0);
}
int main()
{
	int m, k;
	cin >> m >> k;
	int num=pow(2LL,m);
	if(m==1)
	{
		if(k==0)
		{
			cout << "0 0 1 1\n";
		}
		else
		{
			nope();
		}
		return 0;
	}
	if(k>=num)
	{
		nope();
	}
	else
	{
		for(int i=0;i<num;i++)
		{
			if(i!=k) cout << i << " ";
		}
		cout << k << " ";
		for(int i=num-1;i>=0;--i)
		{
			if(i!=k) cout << i << " ";
		}
		cout << k << endl;
	}
	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mr make_pair
using namespace std;
template <typename T> void read(T &x){
	x=0;char ch=getchar();int fh=1;
	while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
	while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	x*=fh;
}
vector<pair<int,int> > a[2][2];
int n,d1,b[610][610];
void fe(int x,int nu){
	int s1=0,s2=x;
	while (s2%2==0){s1++;s2/=2;}
	if (s1%2){
		s1/=2;
		for (int i=0;i<2*n;i++)
			for (int j=0;j<2*n;j++)
				a[nu][(i>>s1)%2].pb(mr(i,j));
	}else{
		s1/=2;
		for (int i=0;i<2*n;i++)
			for (int j=0;j<2*n;j++)
				a[nu][((i>>s1)+(j>>s1))%2].pb(mr(i,j));
	}
	if (a[nu][0].size()<a[nu][1].size())swap(a[nu][0],a[nu][1]);
}
int main(){
	read(n);
	read(d1);fe(d1,0);
	read(d1);fe(d1,1);
	for (auto x:a[0][0])b[x.first][x.second]++;
	for (auto x:a[1][0])b[x.first][x.second]++;
	for (int i=0,k=0;i<2*n;i++)
		for (int j=0;j<2*n;j++)if (b[i][j]==2&&k<n*n){cout<<i<<' '<<j<<'\n';k++;}
	return 0;
}

Measured memory_bytes: 10484
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<string>
#include<random>
#include<map>
#include<queue>
using namespace std;

long long int dfs(string s, vector<bool> b, int depth, long long int ans){
  if( depth < 0 ) return ans;
  if( depth == 0 ){
    long long int cnt = 0;
    long long int tmp = 0;

    tmp += s[0]-'0';
    for(int i=0; i<b.size(); i++){
      if( b[i] ){
        cnt += tmp;
        tmp = 0;
      }else{
        tmp *= 10;
      }
      tmp += s[i+1]-'0';
    }
    cnt += tmp;

    return cnt;
  }else{
    vector<bool> bb = b;
    bb[depth-1] = true;
    return dfs(s, b, depth-1, ans) + dfs(s, bb, depth-1, ans);
  }

  return 0;
}

int main(){

  string s;
  cin >> s;
  int d = s.size()-1;
  vector<bool> b(d, false);
  cout << dfs(s, b, d, 0) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#include <time.h>
#include <sys/timeb.h>
#include <cstdio>
#include <sys/time.h>

using namespace std;
#define ll long long
#define uint unsigned int
#define ulong unsigned long long int

int main(){
	
	string s;
	cin >> s;
	int cnt[26];
	for(int i=0;i<26;i++) cnt[i] = 0;
	
	for(auto c : s) cnt[c - 'a']++;
	for(int i=0;i<26;i++){
		if(cnt[i] == 0){
			cout << (char)('a' + i) << endl;
			return 0;
		}
	}
	
	cout << "None" << endl;
	
    return 0;
}

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

#define pb push_back
#define fi first
#define se second
#define eb emplace_back

const int N = 1000007, inf = 0x3f3f3f3f;
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;


int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	ll a, b, n; cin >> a >> b >> n;

	if(b == 1) {
		cout << 0 << endl;
		return 0;
	}
	ll x = min(n, b - 1);

	cout << (a * x) / b << endl;
}

Measured memory_bytes: 3648
A = input()

def f(x):
    if x % 2 == 0:
        return 1
    else:
        return -1

B = []
for i in range(8):
    if int(A[0]) + f(i//4) * int(A[1]) + f(i//2) * int(A[2]) + f(i) * int(A[3]) == 7:
        if f(i//4) == 1:
            B.append('+')
        else:
            B.append('-')
        if f(i//2) == 1:
            B.append('+')
        else:
            B.append('-')
        if f(i) == 1:
            B.append('+')
        else:
            B.append('-')
        flag = 1
        break
        
if flag == 1:
    print('{}{}{}{}{}{}{}{}'.format(A[0], B[0], A[1], B[1], A[2], B[2], A[3], '=7'))

Measured memory_bytes: 3064
import copy

def calc(T):
    res = 0
    L = [0]*26
    for i in range(D):
        res += S[i][T[i]-1]
        L[T[i]-1] = i+1
        for j in range(26):
            res -= C[j]*(i+1-L[j])
    return res
    
D = int(input())
C = [int(c) for c in input().split()]
S = [[int(s) for s in input().split()] for _ in range(D)]

T = [0]*D
for i in range(D):
    temp = -1
    for j in range(26):
        if temp < S[i][j]:
            temp = S[i][j]
            idx = j+1
    T[i] = idx

p = calc(T)
for i in range(D):
    for j in range(26):
        temp = copy.deepcopy(T)
        temp[i] = j+1
        newp = calc(temp)
        if p < newp:
            T[i] = j+1
            p = newp

for t in T:
    print(t)

Measured memory_bytes: 72592
# -*- coding: utf-8 -*-
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
write = sys.stdout.write
# template


def solve():
    ofs = 700
    h, w = map(int, readline().split())
    A = [list(map(int, readline().split())) for i in range(h)]
    B = [list(map(int, readline().split())) for i in range(h)]
    dp = [0]*(w+1)
    x = abs(A[0][0]-B[0][0])
    dp[0] = 1 << ofs

    for i in range(h):
        for j in range(w):
            x = abs(A[i][j]-B[i][j])
            t = dp[j] | dp[j-1]
            dp[j] = (t << x) | (t >> x)

    for i, s in enumerate(bin(dp[w-1])[-ofs-1:]):
        if int(s):
            write("%d\n" % i)
            return


if __name__ == "__main__":
    solve()


Measured memory_bytes: 41452
#https://atcoder.jp/contests/abc078/tasks/abc078_c
N = int(input())
N_List = sorted(list(map(int,input().split())))
for i in range(N-1):
    Current_N = (N_List[0]+N_List[1])/2
    del N_List[0:2]
    N_List.insert(0,Current_N)

     
print(N_List[0])

Measured memory_bytes: 9088
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {
	
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		
		char[] s = sc.next().toCharArray();
		
		int g = 0, p = 0, score = 0;
		for (int i = 0; i < s.length; i++) {
			switch (s[i]) {
				case 'p':
					if (p == g) {
						g++;
						score--;
					} else {
						p++;
					}
					break;
				case 'g':
					if (p == g) {
						g++;
					} else {
						p++;
						score++;
					}
					break;
			}
		}
		
		out.println(score);
		out.flush();
	}
	
}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;
	
	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}
	
	private byte readByte() {
		if (hasNextByte()) {
			return buffer[ptr++];
		} else {
			return -1;
		}
	}
	
	private boolean isPrintableChar(int c) {
		return '!' <= c && c <= '~';
	}
	
	private void skipUnprintable() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
			ptr++;
		}
	}
	
	public boolean hasNext() {
		skipUnprintable();
		return hasNextByte();
	}
	
	public String next() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		StringBuilder sb = new StringBuilder();
		byte b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
}


Measured memory_bytes: 9300
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <float.h>
#include <random>

#define repeat(i,n) for (int i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << '\n'
#define debugArrayP(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge].first<< " " << x[hoge].second << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = LLONG_MAX/10;
const ll MOD = 1e9+7;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string S;cin>>S;
  bool yymm=(S[2]==0+'0'&&S[3]-'0'>0)||(S[2]==1+'0'&&S[3]-'0'<3);
  bool mmyy=(S[0]==0+'0'&&S[1]-'0'>0)||(S[0]==1+'0'&&S[1]-'0'<3);
  if(yymm&&mmyy){
    cout<<"AMBIGUOUS"<<endl;
  }else if(yymm){
    cout<<"YYMM"<<endl;
  }else if(mmyy){
    cout<<"MMYY"<<endl;
  }else{
    cout<<"NA"<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author KharYusuf
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ANextAlphabet solver = new ANextAlphabet();
        solver.solve(1, in, out);
        out.close();
    }

    static class ANextAlphabet {
        public void solve(int testNumber, FastReader s, PrintWriter w) {
            w.println((char) (s.nextChar() + 1));
        }

    }

    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private FastReader.SpaceCharFilter filter;

        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {

            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars) {

                curChar = 0;

                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (numChars <= 0)
                    return -1;
            }

            return buf[curChar++];
        }

        public char nextChar() {

            int c = read();

            while (isSpaceChar(c))
                c = read();

            return (char) c;
        }

        public boolean isSpaceChar(int c) {

            if (filter != null)
                return filter.isSpaceChar(c);

            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}



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

#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--)

long long comb2(long long n) {
    return n*(n-1)/2;
}

void func(long long N, std::vector<long long> A){
    vector<long long> cnt(N);
    rep(i, N) A[i]--;
    rep(i, N) cnt[A[i]]++;
    long long total = 0;
    rep(i, N) total += comb2(cnt[i]);
    rep(i, N) {
        long long ans = total - comb2(cnt[A[i]]) + comb2(cnt[A[i]] - 1);
        cout << ans << endl;
    }
}

int main(){
    // cout << fixed << setprecision(5);

    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    func(N, std::move(A));
    return 0;
}


Measured memory_bytes: 5760