akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define rep(i, n) for (int i=0; i < n; i++)
#define repd(i, n) for (int i = n-1; i > -1; i--)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
using namespace std;
using LP = pair<ll,ll>;
using P = pair<ll,int>;
ll inf = 1e18;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<LP> x(n), y(m);
    rep(i, n){
        int a, b;
        cin >> a >> b;
        x[i] = LP(a,b);
    }
    rep(i, m){
        int c, d;
        cin >> c >> d;
        y[i] = LP(c,d);
    }
    rep(i, n){
        P ans (inf, 0);
        rep(j, m){
            ll tmp = abs(x[i].first-y[j].first)+abs(x[i].second-y[j].second);
            ans = min(ans, P(tmp, j));
        }
        cout << ans.second+1 << endl;
    }

}

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

using namespace std;

typedef long long ll;

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

	ll n, a, b;
	cin >> n >> a >> b;

	cout << n / (a + b) * a + min(n % (a + b), a) << endl;

}


Measured memory_bytes: 256
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
#from fractions import gcd
#from math import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


n = I()
print(int(n*(n-1)//2))


Measured memory_bytes: 38384
n,a,b = map(int,input().split())
cnt = 0
mod = 1000000007

def C(n,k):
    x = 1
    y = 1
    for i in range(k):
        x *= n-i
        y *= i+1
        x %= mod
        y %= mod
    return x*pow(y,mod-2,mod)%mod

cnt += pow(2,n,mod) - 1
cnt -= C(n,a)
cnt -= C(n,b)

print(max(0,cnt%mod))

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

#define int long long 
#define pb push_back
#define S second
#define F first
#define f(i,n) for(int i=1;i<=n;i++)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int,int>

const int N = 1e5+10;
const int inf = 1e10;

int dp[N][3],a[N],b[N],c[N],n;


void solve()
{
  cin >> n ;
    
  f(i,n) cin >> a[i] >> b[i] >> c[i];
    
  for(int i=1;i<=n;i++)
  {
     f(j,3) dp[i][j] = inf;
      
     dp[i][0] = max(dp[i-1][1],dp[i-1][2]) + a[i];
     dp[i][1] = max(dp[i-1][0],dp[i-1][2]) + b[i];
     dp[i][2] = max(dp[i-1][1],dp[i-1][0]) + c[i]; 
  }   
    
  cout << max(dp[n][0],max(dp[n][1],dp[n][2]));;  
}

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

Measured memory_bytes: 4992
n,x = map(int,input().split())
import math

def f(x,y):
    a = min(x,y)
    b = max(x,y)    
    if a == 0:
        return 0
    elif b%a == 0:
        return 2*b-a
    else:
        return 2*a*math.floor(b/a) + f(a,b%a)

print(n+f(x,n-x))

Measured memory_bytes: 3060
import math
a,b,C = map(float,input().split())
C = math.pi* C / 180
area = (a * b  * math.sin(C) / 2)
print(area)
print(a + b + math.sqrt(a**2 + b**2 - 2 * a * b* math.cos(C)))
print(area * 2 / a)

Measured memory_bytes: 7696
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0; (i)<(n); (i)++)
#define each(i, c) for (auto& (i) : (c))

using namespace std;
typedef long long int lli;
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }

int gcd(int a, int b) {
    if (a < b) swap(a,b);
    int r;
    while(r=a%b) {
        a = b;
        b = r;
    }
    return b;
}

int main() {
    int n, x;
    cin >> n >> x;
    int xs[n], ds[n];
    rep(i,n) cin >> xs[i];
    rep(i,n) ds[i] = abs(x-xs[i]);
    int ans = ds[0];
    rep(i,n) ans = gcd(ans, ds[i]);
    cout << ans << endl;
    return 0;
}

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

using namespace std;
const int maxn=1e5+500;

struct node{
	int p;
	int y;
	int id;
}a[maxn];

pair<int,int>pa[maxn];

bool cmp(node a,node b){
	if(a.p!=b.p)
		return a.p<b.p;
	else
		return a.y<b.y;
}

int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i].p>>a[i].y;
		a[i].id=i;
	}
	sort(a+1,a+m+1,cmp);
	int no=0;
    for(int i=1;i<=m;i++){
        if(i>1&&a[i].p!=a[i-1].p)
            no=1;
        else
            no++;
        pa[a[i].id]=make_pair(a[i].p,no);
    }
    for(int i=1;i<=m;i++)
        printf("%06d%06d\n",pa[i].first,pa[i].second);

} 

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

h=list(map(int,input().split()))
sw=True
temp=0
ans=0
for i in range(N-1):
    if sw==True:
        if h[i]>h[i+1]:
            ans+=h[i]-temp
            sw=False
    else:
        if h[i]<h[i+1]:
            temp=h[i]
            sw=True
if sw==True:
    ans+=h[N-1]-temp

print(ans)


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

int main() {
  int N, K;
  cin >> N >> K;
  vector<int>h(N), dp(N);
  for (int i = 0; i < N; i++) {
    cin >> h.at(i);
    dp.at(i) = 1000000000;
  }
  dp.at(0) = 0;
  for (int i = 1; i < N; i++) {
    for (int j = 1; j <= K; j++) {
      if (i >= j) {
        dp.at(i) = min(dp.at(i), dp.at(i-j) + abs(h.at(i) - h.at(i-j)));
      }
    }
  }
  cout << dp.at(N-1);
}

Measured memory_bytes: 1152
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>


int main(){
	char a[11],b[11],c[11];	

	scanf("%s %s %s", a, b, c);

	printf("%c%c%c\n", a[0]-32, b[0]-32, c[0]-32 );
return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STLL(s) strtoll(s.c_str(), NULL, 10)
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
#define endl '\n';
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;


int main() {
    int n;
    cin>>n;
    vi v(n);
    rep(i,n)v[i]=i;
    vi x(n),y(n);
    rep(i,n)cin>>x[i]>>y[i];
    ld ans=0;
    do{
        ld sum=0;
        rep(i,n-1){
            sum+=sqrt(pow(abs(x[v[i]]-x[v[i+1]]),2)+pow(abs(y[v[i]]-y[v[i+1]]),2));
            //if(i==1)cout<<sqrt(pow(abs(x[v[i]]-x[v[i+1]]),2)+pow(abs(y[v[i]]-y[v[i+1]]),2))<<endl;
        }
        ans+=sum;
    }while(next_permutation(all(v)));
    int kai=1;
    rep(i,n)kai*=i+1;
    printf("%.6Lf\n",(ld)(ans)/kai);
}


Measured memory_bytes: 256
d,g = map(lambda x: int(x),input().split())
pc_list= []
ans = 0
count = 0
min = 0



for i in range(d):
    p,c = map(lambda x: int(x),input().split())
    pc_list.append([p,c])
    min += p


for j in range(1 << d):
    j_bin = format(j, 'b').zfill(d)
    for k in range(d) :
        ans += int(j_bin[k]) * (100*(1+k)*pc_list[k][0] + pc_list[k][1] )
        if j_bin[k] == '1':
            count += pc_list[k][0]
        else :
            max_re = k
    for l in range(pc_list[max_re][0]):
        if ans >= g :
            break
        ans += 100*(1+max_re)
        count += 1
    if ans >= g and min > count :
        min = count
    ans = 0
    count = 0
print(min)


Measured memory_bytes: 3064
#include<cstdio>

int main(){
	int N, M;
	scanf("%d %d", &N, &M);
	if(N&1){
		for (int i = 1; i <= M; ++i){
			printf("%d %d\n", i, M*2 + 1 - i);
		}		
	}else{
		for (int i = 1; i <= M; ++i){
			if(i&1){
				printf("%d %d\n", ((i+1)>>1), N + 1 - ((i+1)>>1));
			}else{
				printf("%d %d\n", N/2 + 1 - i/2, N/2 + 1 + i/2);
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1708
#include<bits/stdc++.h>
using namespace std;
const int N=200010,inf=1e9;
int n;
int a[N],v[N],cnt,sum[N];
struct seg
{
	int mx[N<<2];
	void init(){memset(mx,-63,sizeof(mx));}
	void pushup(int k){mx[k]=max(mx[k<<1],mx[k<<1|1]);}
	void modify(int p,int x,int l=0,int r=n,int k=1)
	{
		if(l==r){mx[k]=x;return;}
		int mid=l+r>>1;
		if(p<=mid)modify(p,x,l,mid,k<<1);
		else modify(p,x,mid+1,r,k<<1|1);
		pushup(k);
	}
	int query(int L,int R,int l=0,int r=n,int k=1)
	{
		if(L>R)return -inf;
		if(L<=l && r<=R)return mx[k];
		int mid=l+r>>1,res=-inf;
		if(L<=mid)res=max(res,query(L,R,l,mid,k<<1));
		if(R>mid)res=max(res,query(L,R,mid+1,r,k<<1|1));
		return res;
	}
}t[2];
char ans[N];
bool check(int p,int x)
{
	if(x<0)return 0;
	return t[x&1].query(p,n)>=x;
}
int main()
{
	scanf("%d",&n);
	t[1].init();
	int mx=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]>mx)v[i]=2,cnt++;
		else
			v[i]=1;
		mx=max(mx,a[i]);
	}
	for(int i=n;i;i--)
	{
		int x=t[0].query(a[i],n),y=t[1].query(a[i],n);
		t[v[i]&1].modify(a[i],x+v[i]),t[(v[i]&1)^1].modify(a[i],y+v[i]);
	}
	for(int i=n;i;i--)sum[i]=sum[i+1]+v[i]-1;
	int cntx=0,cnty=0,mxx=0,mxy=0;
	for(int i=1;i<=n;i++)
	{
		t[0].modify(a[i],0); t[1].modify(a[i],-inf);
		if(check(mxy,sum[i+1]+cntx+(a[i]>mxx)-cnty) || check(max(mxx,a[i]),sum[i+1]+cnty-cntx-(a[i]>mxx)))ans[i]='0',cntx+=mxx<a[i],mxx=max(a[i],mxx);
		else
			ans[i]='1',cnty+=mxy<a[i],mxy=max(a[i],mxy);
	}
	if(cntx!=cnty)puts("-1");
	else
		printf("%s",ans+1);
	return 0;
}


Measured memory_bytes: 11488
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, n) for (int i = 1; i <= (int)(n); i++)

int main(){
  int r, g, b;
  cin >> r >> g >> b;

  if ((100 * r + 10 * g + b) % 4 == 0){
    cout << "YES" << endl;
  }
  else
  {
    cout << "NO" << endl;
  }
  
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
 
using namespace std;
 
int main() {
 
	int n;
	int ans;

	cin >> n;
	vector<int> l(n);
	
	for (int i = 0; i < n; i++) {
		cin >> l[i];
	}
	
	sort(l.begin(), l.end());
	
	ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			for (int k = j + 1; k < n; k++) {
				if (l[k] < l[i] + l[j]) {
					ans = ans + 1;
				}
			}
		}
	}
	
	cout << ans << endl;
	return 0;
}

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


char charaHash[256];

inline int getHash(char* str);

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

	char order[12];
	char val[12];
	int mhash[1<<20];

	charaHash['A'] = 0; //00
	charaHash['T'] = 1; //01
	charaHash['C'] = 2; //10
	charaHash['G'] = 3; //11

	cin >> order;

	while(cin >> order){
		cin >> val;
		int key = getHash(val);
		int address = 1 << (key&0x1f);
		int hash_val = key >> 5;

		//cout << "val:" << val <<"	hash val:" << hash_val << "	address" << bitset<32>(address) << endl;
		if(order[0] == 'i'){
			mhash[hash_val] |= address;
		}else{
			if(mhash[hash_val] & address)cout << "yes" << endl;
			else cout << "no" << endl;
		}
	};

	return 0;
}

inline int getHash(char* str){		
	int key = 1;
	char* p = str;
	while(*p != '\0'){
		key <<= 2;
		key |= charaHash[(int)*p];
		p++;
	}
	return key;
}

Measured memory_bytes: 3388
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

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

int dp[2][2][101][101]; // ???????????? 0:ue 1: migi  ??´??????????????£?????? 0:????????£???????????? 1:????????£???

int main() {
	while (true) {
		int w, h;
		cin >> w >> h;
		if (w == 0 && h == 0) break;

		memset(dp, 0, sizeof(dp));

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

		REP(i, h) {
			REP(j, w) {
				dp[0][0][i + 1][j + 1] = dp[0][0][i][j + 1] + dp[0][1][i][j + 1];
				dp[0][1][i + 1][j + 1] = dp[1][0][i][j + 1];
				dp[1][0][i + 1][j + 1] = dp[1][0][i + 1][j] + dp[1][1][i + 1][j];
				dp[1][1][i + 1][j + 1] = dp[0][0][i + 1][j];

				REP(k, 2) REP(l, 2) dp[k][l][i + 1][j + 1] %= 100000;
			}
		}

		int ans = 0;
		REP(i, 2) REP(j, 2) ans += dp[i][j][h][w];
		cout << ans % 100000 << endl;
		
	}

	return 0;
}

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

prime = [0,0]+[1]*10**5#素数テーブル
for i in range(10**3):#エラトステネスのふるいにかける
  if prime[i]==0: continue
  for j in range(2*i, 10**5+1, i):
    prime[j]=0
  
cumul = []
for i in range(10**5+1):
  if prime[i]:
    if prime[(i+1)//2]: cumul+=[1]
    else: cumul+=[0]
  else: cumul+=[0]
    
num_table = [0]
for i in range(10**5):
  num_table+=[num_table[-1]+cumul[i+1]]
  
for i in range(N):
  L,R=map(int,input().split())
  print(num_table[R]-num_table[L-1])

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

int n,m,ex[100010],ey[100010],ans;
bool bo[410][410],boo[410],b[410];

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1; i<=m; i++) scanf("%d%d",&ex[i],&ey[i]);
	for (int i=1; i<=n; i++)
	{
		bo[i][i]=1;
		for (int j=m; j; j--)
			if (bo[i][ex[j]]||bo[i][ey[j]]) bo[i][ex[j]]=bo[i][ey[j]]=1;
		memset(boo,0,sizeof(boo)),boo[i]=1,b[i]=1;
		for (int j=m; j; j--)
		{
			if (boo[ex[j]]&&boo[ey[j]]) {b[i]=0; break;}
			if (boo[ex[j]]||boo[ey[j]]) boo[ex[j]]=boo[ey[j]]=1;
		}
	}
	for (int i=1; i<=n; i++) if (b[i])
		for (int nw,j=i+1; j<=n; j++) if (b[j])
		{
			nw=1;
			for (int k=1; k<=n; k++)
				if (bo[i][k]&&bo[j][k]) {nw=0; break;}
			ans+=nw;
		}
	return printf("%d\n",ans),0;
}

Measured memory_bytes: 1152
n=int(input())

a = 1
p = 1

while p < 1e6:
    c = 0
    t = 0
    p += 1
    while n%p < 1:
        n /= p
        x=c==t
        t += x
        c += 1-t*x
        a += x

print(a-(n<2))

Measured memory_bytes: 9260
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    X, Y = [int(x) for x in input().split()]

    for i in range(101):
        for j in range(101):
            if i + j == X and (i * 2 + j * 4 == Y or i * 4 + j * 2 == Y):
                print("Yes")
                return

    print("No")


if __name__ == '__main__':
    main()


Measured memory_bytes: 9176
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    ll n, sum = 0;
    cin >> n;
    REP(i, n){
        if(i % 3 != 0 && i % 5 != 0)sum+=i;
    }
    cout << sum << endl;
}   

Measured memory_bytes: 3596
/* Author : Harshit Jain a.k.a. iharshit009 */
#include <bits/stdc++.h>
#define vi               vector<int>
#define pb(x)            push_back(x)
#define all(x)           x.begin(), x.end()
#define sortall(x)       sort(all(x))
#define sortrev(x)       sort(all(x), greater<int>())
#define debug(x)         cout << '>' << #x << ':' << x << endl;
#define int              long long
#define ld               long double
#define endl 			 "\n";
#define mp 				 make_pair
#define pii 			 <int, int>
#define lb 				 lower_bound
#define ub				 upper_bound
#define len(a)           int((a).size())
#define prec(n)          fixed<<setprecision(n)
#define cnt(n)           __builtin_popcountll(n)
#define pi               pair<int, int>
const int mod = 1000000007;
using namespace std;
using namespace std::chrono;
// const int N = 1e5 + 5; 
// int n;
// int a[N];



int32_t main(){
auto start = high_resolution_clock::now(); // starting clock
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
t = 1;
// cin >>t;
while(t--){


int n;
cin >> n;
if(n){
	cout << 0 << endl;
}
else{
	cout << 1 <<endl;
}







}
auto stop = high_resolution_clock::now(); // stop clock
auto duration = duration_cast<microseconds>(stop - start);  // printing duration
cerr << "Time taken by function: " << duration.count() << " milliseconds" << endl; 
return 0;
}

Measured memory_bytes: 3644
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=(a);i<(b);++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;}

//vector出力
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){
  o<<"{";
  for(int i=0;i<(int)v.size();i++) o << (i>0?", ":"") << v[i];
  o<<"}";
  return o;
}

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


int main() {
  ll N,K;
  cin >> N >> K;
  vector<ll> A(N),sep(N+1,0);
  rep(i,N) {
    cin >> A[i];
    if (i>0) A[i]+=A[i-1];
    A[i]%=K;
    sep[i+1] = A[i]-(i+1);
    sep[i+1]%=K;
    if (sep[i+1]<0) sep[i+1]+=K;
  }

  ll res=0;
  map<ll,int> mp;
  mp[0]++;
  rep2(i,1,N+1) {
    if (i-K>=0) mp[sep[i-K]]--;
    mp[sep[i]]++;
    res+=mp[sep[i]]-1;
  }
  cout << res << endl;
}

Measured memory_bytes: 15872
#include<iostream>
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
/*---------------------DEBUGGING--------------------------------------------*/
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
/*-------------------------------------------------------------------------------------*/
//#define mp make_pair
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pcc pair<char,char>
#define F first
#define S second
#define int long long
#define pi 3.141592653589793238462643383279502
#define M  1000000007
#define rep(i,a,n) for(int i=a;i<n;i++)
#define INF 10000000000000
#define N 200005
#define vi vector<int>
#define all(v) v.begin(),v.end()
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

signed main()
{
   ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   int n;
   cin>>n;
   int a[n+1];
   rep(i,0,n+1)cin>>a[i];
   if(n == 0 )
   {   if(a[0]==1)
       cout<<1<<endl;
       else
       {
           cout<<-1<<endl;
       }
       return 0;
   }
   if(a[0] != 0)
   {
       cout<<-1<<endl;
       return 0;
   }
   int mx[n+1];
   mx[0]=1;
   for(int i=1;i<=n;i++)
   {
       int val=2*mx[i-1] - a[i];
       if(val < 0)
       {
           cout<<-1<<endl;
           return 0;
       }
       if(val > 1e18)
        val=1e18;
       mx[i]=val;
   }
   int ans=a[n];
   int last=a[n];
   for(int i=n-1;i>=0;i--)
   {
       int mn=min(mx[i],last)+a[i];
       ans+=mn;
       last=mn;
   }
   cout<<ans<<endl;
}


Measured memory_bytes: 5188
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
#define pb push_back
#define ld long double
#define f first
#define s second
#define in insert
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = 1e18 + 5;
const int mod = 1e9 + 7;
const int  N = 2e5 + 314;
const long double pi = 3.1415926535897932384626433832795;
void solve(){
    int n;
    cin>>n;
    cout<<((n+999)/1000)*1000-n;   
}
signed main(){
    speed;
    int t=1;
    //cin>>t;
    while(t--)solve();
}

Measured memory_bytes: 3652
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;



int main() {
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i, h) {
        cin >> s[i];
    }

    int c = 0;
    rep(i, h) {
        rep(j, w) {
            if(s[i][j] == '#') {
                ++c;
            }
        }
    }

    cout << (c == h+w-1 ? "Possible":"Impossible") << endl;
}

Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

#define _CRT_SECURE_NO_WARNINGS
#define REP(i, n) for(int i=0; i<n; i++)
#define FOR(i, m, n) for(int i=m; i<n; i++)
#define ALL(x) (x).begin(),(x).end()
#define INF 999999999

typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

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

Measured memory_bytes: 256
N = int( input() )
c_list = []
for i in range(N):
    c_list.append( int( input() ) )
    
a = c_list[:]
a.sort()
ma = a[ N - 1 ]

for i in range(N):
    t = c_list[i]
    if t == ma:
        print(a[N - 2])
    else:
        print(ma)

Measured memory_bytes: 14112
n = int(input())
index=0
timeCounterL=[0]*n
while index < n-1:
    c, s, f = map(int, input().split())
    index2=0
    while index2 < n:
        if index2 == index:
            timeCounterL[index2]+=s+c
        else:
            if index2 > index:
                break
            else:
                if timeCounterL[index2] > s:
                    amari = timeCounterL[index2]-s
                    if amari%f == 0:
                        timeCounterL[index2]+=c
                    else:
                        extraT = amari%f
                        timeCounterL[index2]+=f-extraT+c
                else:
                    timeCounterL[index2] = s+c
        index2+=1
    index+=1

for time in timeCounterL:
    print(time)

Measured memory_bytes: 3064
S = input()
MOD = 10**9 + 7
dp = [0] * 3  # num of ..A, ..AB, ..ABC
pp = [0] * 3
nq = 0
for s in S:
    pp = dp
    dp = pp.copy()
    if s == 'A':
        dp[0] += pow(3, nq, MOD)
    elif s == 'B':
        dp[1] += pp[0]
    elif s == 'C':
        dp[2] += pp[1]
    else:
        dp[0] += pp[0]*2 + pow(3, nq, MOD)
        dp[1] += pp[1]*2 + pp[0]
        dp[2] += pp[2]*2 + pp[1]
        nq += 1
    dp[0] %= MOD
    dp[1] %= MOD
    dp[2] %= MOD
print(dp[2])

Measured memory_bytes: 3188
import collections

n=int(input())
arr=list(map(int,input().split()))
cnt=collections.defaultdict(int)
for val in arr:
  cnt[val]+=1
sums=sum(arr)
q=int(input())
for _ in range(q):
  b,c=map(int,input().split())
  diff=(c-b)*(cnt[b])
  sums+=diff
  print(sums)
  cnt[c]+=cnt[b]
  cnt[b]=0

Measured memory_bytes: 24224
S=input()
a=int(S[:2])
b=int(S[2:])
if (a>12 or a==0) and 1<=b<=12:
    print("YYMM")
elif 1<=a<=12 and 1<=b<=12:
    print("AMBIGUOUS")
elif 1<=a<=12 and (b>12 or b==0):
    print("MMYY")
else:
    print("NA")

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

int main()
{

        string s, t;
        cin >> s;
        cin >> t;
        vector<char> S;
        vector<char> T;
        for (int i = 0; i < s.length(); ++i) {
                S.push_back(s[i]);
        }
        for (int i = 0; i < t.length(); ++i) {
                T.push_back(t[i]);
        }

        sort(S.begin(), S.end());
        sort(T.begin(), T.end(), greater<char>());

        int len = (s.length() > t.length()) ? t.length() : s.length();
        for (int i = 0; i < len; ++i) {
                if (T[i] > S[i]) {
                        cout << "Yes" << endl;
                        exit(0);
                }
                else if (T[i] < S[i]) {
                        cout << "No" << endl;
                        exit(0);
                }
        }
        if (s.length() >= t.length()) {
                cout << "No" << endl;
        }
        else {
                cout << "Yes" << endl;
        }


}


Measured memory_bytes: 256
s = list(map(str, input().strip()))
k = int(input())

pre = 0
cnt = 1
ans = 0
for i in s:
    if i == pre:
        cnt += 1
    else:
        ans += cnt // 2
        cnt = 1
    pre = i

ans += cnt//2

if cnt == len(s):
    print((cnt*k)//2)
    exit(0)
pcnt = cnt
dcnt = 0
for i in s:
    if i == pre:
        cnt += 1
    else:
        dcnt = cnt - pcnt
        break

if dcnt % 2 and pcnt % 2:
    ans = ans * k + k - 1
else:
    ans *= k

print(ans)


Measured memory_bytes: 38384
#include<stdio.h>
void trace(int A[],int N){
  int i;
  for(i=0;i<N;i++){
    if(i>0) printf(" ");
    printf("%d",A[i]);
  }
  printf("\n");
}

void insertionSort(int A[],int N){
  int i,j,v;
  for(i=1;i<N;i++){
    v=A[i];
    j=i-1;
    while(j >= 0&& A[j] > v){
      A[j+1]=A[j];
      j--;
    }
    A[j+1]=v;
    trace(A,N);
  }
}

int main(){
  int A[100],N,i,j;
  scanf("%d",&N);
  for(i=0;i<N;i++) scanf("%d",&A[i]);
  trace(A,N);
  insertionSort(A,N);
  
  return 0;
}


Measured memory_bytes: 2124
import java.util.Scanner;

class Main{
    int a,b;
        
    public void solve(){
        int x,y;
        Scanner sc = new Scanner(System.in);
        a = sc.nextInt();
        b = sc.nextInt();
        x = a * b;
        y = 2 * (a + b);
        System.out.println(x + " " + y);
        
    }
    
    public static void main(String[] args){
        
        new Main().solve();
                
    }

}

Measured memory_bytes: 17320
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        try (Scanner sc = new Scanner(System.in)) {
            while (sc.hasNextLong()) {
                int a = sc.nextInt();
                int b = 0;
                for (int i=0;i<10;i++){
                    for (int j=0;j<10;j++){
                        for (int k=0;k<10;k++){
                            for (int l=0;l<10;l++){
                                if (i+j+k+l == a){
                                    b++;
                                }
                            }
                        }
                    }
                }
                System.out.println(b);
            }
        }
    }
}


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

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

#define INF 99999999
#define rep(i,n) for(int (i)=0,temp=(int)(n);(i)<temp;++(i)) 
#define repi(i,start,end) for(int (i)=(start),temp=(int)(end);i<(end);++(i))
#define rfor(v,x) for(const auto& (x) : (v)) //xは値を表す
#define all(x) (x).begin(),(x).end()
#define SORT(v, n) sort((v), (v)+(n))
#define vsort(v) sort((v).begin(), (v).end())
#define vfsort(v,lambda) sort(all((v)),(lambda))
#define vint vector<int>
#define vvint vector<vector<int>> //vvint v(n,vint(n))のように宣言できる
#define vin(v) rep(i,(v).size()) {cin >> (v)[i];}
//最終奥義
//#define int long long
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int ctoi(char c) {return c-'0';}
//lambda式 -> [&](int x, int y){return x<y;}
//vector内の重複を削除-> v.erase(unique(all(v)),v.end());

signed main(void){
  int n;cin >> n;
  vector<pint> a(n);
  rep(i,n){
    int t;cin >> t;
    a[i].second=i+1;
    a[i].first=t;
  }
  vsort(a);
  rep(i,n) cout << a[i].second << " ";
  cout << endl;


}


Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int main() {
	ios::sync_with_stdio(false);
	int n,y;
	cin>>n>>y;
	y/=1000;
	if(n*10>=y&&y>=n) {
		int q=0,w=0,e=0;
		int t=10*n-y;
		int flag=0;
		for(int j=0; j<=n; j++) {
			for(int k=0; j+k<=n; k++) {
				if(5*j+9*k==t) {
					flag=1;
					w=j;
					e=k;
					break;
				}
			}
		}
		if(flag) cout<<n-w-e<<" "<<w<<" "<<e;
		else cout<<"-1 -1 -1";
	} else cout<<"-1 -1 -1";
	return 0;
}


Measured memory_bytes: 256
MOD = 10**9 + 7
N = int(input())
arr = list(map(int, input().split()))
arr.sort()
if N % 2 == 1:
    if arr[0] != 0:
        print(0)
        exit()
    if N == 1:
        print(1)
        exit()
    for i in range(2,N,2):
        if arr[i] == arr[i-1] and arr[i] == i:
            continue
        else:
            print(0)
            exit()
    print((2**((N-1)//2))%MOD)
else:
    for i in range(1,N,2):
        if arr[i] == arr[i-1] and arr[i] == i:
            continue
        else:
            print(0)
            exit()
    print((2**(N//2))%MOD)

Measured memory_bytes: 14008
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp2
{
    class Program
    {
        static void Main()
        {
            var a = Console.ReadLine().Split(' ');
            var b = Console.ReadLine().Split(' ');
            
            int[] array = new int [int.Parse(a[0])];
            for (int i = 0; i < int.Parse(a[0]); i++)
            {
                array[i] = int.Parse(b[i]);
            }

            Array.Sort(array);
            int ans = 0;
            for (int j = 0; j < int.Parse(a[1]); j++)
            {
                ans += array[j];
            }

            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 27564
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int mod=1e9+7;

int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    int ans;
    if(n>m){
        ans=(k+n-1)/n;
    }else
    ans=(k+m-1)/m;
    cout<<ans<<endl;

    return 0;
}


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

using namespace std;

int main(){
  int a, b, c;
  vector<int> div;

  cin >> a >> b >> c;
  for(int i = 1 ; i <= c ; i++){
    if(c % i == 0){
      div.push_back(i);
    }
  }

  int ans = 0;
  for(int i = a ; i <= b ; i++){
    for(int j = 0 ; j < div.size() ; j++){
      if(i == div[j]){
        ans++;
        break;
      }
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1216
#include <bits/stdc++.h>
#define MAX 2000001
using namespace std;

vector <int> arr;
int n;
long long dp[1][MAX];

long long minOper(int i, int falta){
    i = 0;
    if(falta < 0) return 100000000000000LL;
    if(falta < 6) return dp[i][falta] = falta;

    if(i == arr.size()) return 0;
    if(dp[i][falta] != -1) return dp[i][falta];

    long long prov = 100000000000000LL;
    for(int l = 0; l < arr.size(); l++){

        prov = min(prov, 1 + minOper(i + 1, falta - arr[l]));
    }
    return dp[i][falta] = prov;
}

int main(){

//    freopen("out.txt", "w", stdout);
    cin>>n;

    if(n < 6){

        cout<<n<<endl;
        return 0;
    }

    memset(dp, -1, sizeof dp);

    int pot = 1;
    while(pot * 6 < MAX){

//        setonio.insert(pot * 6);
        arr.push_back(pot * 6);
        pot *= 6;
    }
    pot = 1;
    while(pot * 9 < MAX){

//        setonio.insert(pot * 9);
        arr.push_back(pot * 9);
        pot *= 9;
    }
    sort(arr.begin(), arr.end());

    cout<<minOper(0, n)<<endl;
//    int falta;
//    int ans = 100000000000000LL;
//    for(int i = 0; i < arr.size(); i++){
//
//        falta = n;
//        int prov = 0;
//        for(int j = 0; j < arr.size(); j++){
//
//            if(falta < 0){
//
//                prov = 100000000000000LL;
//                break;
//            }
//            if(falta < 6){
//
//                prov += falta;
//                break;
//            }
//
//            falta -= arr[j];
//        }
//    }

    return 0;
}


Measured memory_bytes: 16640
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
		  　　　　　　　　　　(¸.·´ (¸.·'* ☆
					*/

#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>
#include <regex>
#include <functional>
#include <complex>
#include <list>
/*多倍長整数/cpp_intで宣言
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
*/

//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i <= (n); ++i)
#define rep2(i, n) for(int i = 2; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define reprm(i, n) for(int i = n - 1; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printin(a) printf(a ? "possible\n" : "imposible\n")
#define printdb(a) printf("%.50lf\n", a)//少数出力
#define printdbd(a) printf("%.16lf\n", a)//少数出力(桁少なめ)
#define prints(s) printf("%s\n", s.c_str())//string出力
#define all(x) (x).begin(), (x).end()
#define allsum(a, b, c) ((a + b) * c / 2)//等差数列の和、初項,末項,項数
#define pb push_back
#define priq priority_queue
#define rpriq priq<int, vector<int>, greater<int>>
#define deg_to_rad(deg) (((deg)/360.0)*2.0*PI)
#define rad_to_deg(rad) (((rad)/2.0/PI)*360.0)
#define Please return
#define AC 0
#define addf(T) [](T a, T b){return (a + b);}
#define minf(T) [](T a, T b){return min(a, b);}
#define maxf(T) [](T a, T b){return max(a, b);}


using ll = long long;

constexpr int INF = 1073741823;
constexpr int MINF = -1073741823;
constexpr ll LINF = ll(4661686018427387903);
constexpr ll MOD = 1000000007;
const long double PI = acos(-1.0L);

using namespace std;

void scans(string& str) {
	char c;
	str = "";
	scanf("%c", &c);
	if (c == '\n')scanf("%c", &c);//最初の改行対策
	while (c != '\n' && c != -1) {
		str += c;
		scanf("%c", &c);
	}
}

void scanc(char& str) {
	char c;
	scanf("%c", &c);
	if (c == -1)return;
	while (c == '\n') {
		scanf("%c", &c);
	}
	str = c;
}

double acot(double x) {
	return PI / 2 - atan(x);
}

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

ll lcm(ll number1, ll number2) {//lcmを求める
	return number1 / gcd(number1, number2) * number2;
}

ll LSB(ll n) { return (n & (-n)); }

/*-----------------------------------------ここからコード-----------------------------------------*/



int main() {

	int n, m;
	scanf("%d%d", &n, &m);
	printf("%d\n", (int)ceil((double)n / (double)m));

	Please AC;
}


Measured memory_bytes: 888
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> graph[100005];
#define white first
#define black second
#define mod 1000000007
void read_graph(int n) 
{
    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
        
     }
}
pair<ll, ll> dfs(ll node, ll par){
    pair<ll, ll> ans = {1, 1}, temp;
    for(auto child : graph[node]){
        if(child != par){temp = dfs(child, node);
        ans.white *= temp.white + temp.black;
        ans.white %= mod;
        ans.black *= temp.white;
        ans.black %= mod;
        }
    }
    return ans;
}
int main()
{
    ll n;
    cin >> n;
    read_graph(n-1);
    auto ans = dfs(1, 0);
    cout << (ans.black + ans.white)%mod;
}

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

using namespace std;

typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli>> mat;

lli n,m;

vll a,b,c;
vll dist;

lli ans;


int main(){
  cin >> n >> m;
  a = b = c = vll(m);
  dist = vll(n+1,-LONG_MAX);
  dist[1] = 0;
  for(lli i = 0;i < m;i++){
    cin >> a[i] >> b[i] >> c[i];
  }
  for(lli i = 0;i < n*2;i++){
    bool update = false;
    for(lli j = 0;j < m;j++){
      if(dist[a[j]] != -LONG_MAX && dist[b[j]] < dist[a[j]]+c[j]){
        dist[b[j]] = dist[a[j]]+c[j];
        update = true;
      }
    }
    if(update == false){
      cout << dist[n] << endl;
      return 0;
    }
  }
  bool update = false;
  for(lli i = 0;i < n*2;i++){
    for(lli j = 0;j < m;j++){
      if(dist[a[j]] != -LONG_MAX && dist[b[j]] < dist[a[j]]+c[j]){
        dist[b[j]] = dist[a[j]]+c[j];
        if(b[j] == n) update = true;
      }
    }
  }
  if(update) cout << "inf" << endl;
  else cout << dist[n] << endl;
  return 0;
}


Measured memory_bytes: 256
/* A - Registration */

#include <bits/stdc++.h>
using namespace std;

int main(){
  string S, T;
  int judge = 1;
  cin >> S >> T;
  for(int i = 0; i < S.size(); i++){
    if(S.at(i) != T.at(i)){
      // cout << S.at(i) << " " << T.at(i) << endl;
      judge = 0;
      break;
    }
  }
  if(judge == 1) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 3632
#include<stdio.h>
#define MAX_NUMBER_OF_NODE 5000001
#define INDEX_OF_ROOT 0
#define DEPTH_OF_ROOT 0



//int node[MAX_NUMBER_OF_NODE];
int number_of_node;//it is represented as H in AOJ

void insert(int);
void print_node(int , int);
void maxHeapify(int);
void buildMaxHeap();
int swap(int);

int node[MAX_NUMBER_OF_NODE];
int number_of_node;

int main()
{
 
  //int number_of_node;//it is represented as H in AOJ
  int i,id;
 
  scanf("%d",&number_of_node);
  for(i = 1 ; i <= number_of_node ; i++)scanf("%d",&node[i]);
  //for(i = 1 ; i < number_of_node ; i++)maxHeapify(i);
  for(i = number_of_node/2 ; i >= 1 ; i--)maxHeapify(i);
  //for(i = 0 ; i <= number_of_node ; i++)buildMaxHeap(void);
  //printf("\nnumber_of_node/2 = %d",number_of_node/2);
  

  //print_node(INDEX_OF_ROOT ,DEPTH_OF_ROOT );
  
  for(i = 1 ; i <= number_of_node ; i++)  printf(" %d",node[i]);
     printf("\n");
    
}


void maxHeapify(int index)
{
  int largest;
  int swap;
  int l = 2*index;
  int r = 2*index+1;

  if(l <= number_of_node && node[l] > node[index])largest = l;
  else largest = index;

  if(r <= number_of_node && node[r] > node[largest]) largest = r;

  if(largest != index )
    {
      swap = node[index];
      node[index] = node[largest];
      node[largest] = swap;
      maxHeapify(largest);
    }

  
  
}







/*
void insert(int index)
{
  int swap;
  if(index == 0)
    {
      
      return;
    }
      
  if(node[index] > node[index/2])
    {
      swap = node[index/2];
      node[index/2] = node[index];
      insert(index/2);
      node[index] = swap;
      return;
    }

}
*/

/*void print_node(int index,int depth)
{

  printf(" %d",node[index]);
  if(index*2 < number_of_index)
  

}
*/




/*#include<stdio.h>
#define MAX_NUMBER_OF_NODE 500000
#define INDEX_OF_ROOT 0
#define DEPTH_OF_ROOT 0

int node[MAX_NUMBER_OF_NODE];
int number_of_node;//it is represented as H in AOJ

void insert(int);
void print_node(int , int);
int swap(int);
int main()
{
  //int node[MAX_NUMBER_OF_NODE];
  //int number_of_node;//it is represented as H in AOJ
  int i,id;


   

  scanf("%d",&number_of_node);
  for(i = 1 ; i <= number_of_node+1 ; i++)
    {
      scanf("%d",&id);
      node[i] = id;
      insert(i);
    }


  //print_node(INDEX_OF_ROOT ,DEPTH_OF_ROOT );
  
  for(i = 1 ; i <= number_of_node ; i++)  printf("%d ",node[i]);
     printf("\n");
    
}

void insert(int index)
{
  int swap;
  if(index == 0) return;
  if(node[index] > node[index/2])
    {
      swap = node[index/2];
      node[index/2] = node[index];
      insert(index/2);
      node[index] = swap;
      return;
    }

}
*/
/*void print_node(int index,int depth)
{

  printf(" %d",node[index]);
  if(index*2 < number_of_index)
  

}
*/



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

using namespace std;

int main(){
    int n, m;
    cin >> n;
    m = 1e6;
    vector<int> A(n);
    copy_n(istream_iterator<int>(cin), n, A.begin());

    vector<int> B(m + 1);
    for (const auto &a: A)
        B[a]++;

    for (int i = 0; i <= m; i++){
        if (!B[i])
            continue;
        for (int j = 2 * i; j <= m; j += i){
            B[j]++;
        }
    }

    int ans = 0;
    for (const auto &a: A){
        if (B[a] <= 1)
            ans++;
    }

    cout << ans << endl;
}

Measured memory_bytes: 8004
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <deque>
#define INF_INT (INT_MAX / 2)
#define INF_LONG (LONG_MAX / 2)
//#define DEBUG true
#define DEBUG false
using namespace std;

const int MAX = 100001;
const int MOD = 1000000007;

typedef long long ll;
typedef pair< int, int > pii;
typedef pair< ll, ll > pll;
typedef pair< ll, int > pli;
typedef pair< int, ll > pil;

int ceil(int x, int y){
  return (x % y == 0) ? x / y : x / y + 1;
}

int gcd(int x, int y){
  return y ? gcd(y, x % y) : x;
}

int lcm(int x, int y){
  return x / gcd(x, y) * y;
}

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

  int h, w;
  cin >> h >> w;
  vector< string > a(h);
  for(int i = 0; i < h; i++) cin >> a[i];

  int dist[h][w];
  for(int i = 0; i < h; i++){
    fill(dist[i], dist[i] + w, INF_INT);
  }

  queue< pii > q;
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      if(a[i][j] == '#'){
        q.push(make_pair(i, j));
        dist[i][j] = 0;
      }
    }
  }

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

  while(!q.empty()){
    pii p = q.front();  q.pop();
    for(int i = 0; i < 4; i++){
      int ny = p.first + dy[i];
      int nx = p.second + dx[i];
      if(!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue;
      if(a[ny][nx] == '.'){
        a[ny][nx] = '#';
        dist[ny][nx] = dist[p.first][p.second] + 1;
        q.push(make_pair(ny, nx));
      }
    }
  }

  int ans = 0;
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      ans = max(ans, dist[i][j]);
    }
  }

  cout << ans << endl;

  return 0;
}


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

#define int long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

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; }

template<typename T>
void print1(T begin, T end) {
	while (begin != end) {
		cerr << (*begin) << " ";
		*begin++;
	}
	cerr << endl;
}

template<typename T>
void print2(T Array, int height, int width) {
	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			cerr << " " << Array[i][j];
		}
		cerr << endl;
	}
}

void print() { std::cerr << endl; }
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
	std::cerr << head << " ";
	print(std::forward<Tail>(tail)...);
}

template<class T>
void Add(T &a, const T &b, const T &mod=1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}

template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

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

signed main() {
	int n;
	cin >> n;
	vec<int> p(n);
	rep (i, n) {
		cin >> p[i];
	}

	int cnt = 0;
	rep (i, n) {
		if (p[i] != i+1) cnt++;
	}

	if (cnt <= 2) {
		puts("YES");
	} else {
		puts("NO");
	}

	return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())

// {{{
template<typename T>
void printmatrix(vector<vector<T> > ar){
    for (int i = 0; i < (int)ar.size(); i++) {
        for (int j = 0; j < (int)ar[0].size(); j++) {
            cout << ar[i][j];
        }
        cout << endl;
    }
}

template<typename T>
void printvector(vector<T> vec){
    for (int i = 0; i < (int)vec.size(); i++) {
        cout << vec[i] << endl;
    }
}

template<typename T>
void unique(vector<T>& vec){
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
}

template<typename T>
vector<T> cumsum(vector<T> vec){
    vector<T> newvec((T)vec.size());
    int tmp = 0;
    for (int i = 0; i < (int)vec.size(); i++) {
        tmp += vec[i];
        newvec[i] = tmp;
    }

    return newvec;
}

template<typename T>
T digitsum(T x){
    T y=0;
    while(x){
        y += x % 10;
        x /= 10;
    }

    return y;
}

template<typename T>
T gcd(T x, T y){
    if (x == 0 || y == 0) {
        return 0;
    }

    while (x != y){
        if (x > y) {
            x -= y;
        }else{
            y -= x;
        }
    }
    return x;
}

// }}}
/* vim:set foldmethod=marker: */

void solve(){
    int a1,a2,a3;
    cin >> a1 >> a2 >> a3;

    vi v(3);
    v[0] = abs(a1-a2);
    v[1] = abs(a1-a3);
    v[2] = abs(a3-a2);
    sort(all(v));
    cout << v[0] + v[1] << endl;

    return;
}

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}


Measured memory_bytes: 256
x, y, z, k = map(int, input().split())
A = list(int(i) for i in input().split())
B = list(int(i) for i in input().split())
C = list(int(i) for i in input().split())

A.sort()
A = A[::-1]
B.sort()
B = B[::-1]
C.sort()
C = C[::-1]

ABC = []

for a in range(len(A)):
    for b in range(len(B)):
        if (a+1)*(b+1) > k:
            break
        for c in range(len(C)):
            if (a+1)*(b+1)*(c+1) > k:
                break
            #print(A[a], B[b], C[c])
            ABC.append(A[a]+B[b]+C[c])

ABC.sort()
ABC = ABC[::-1]

for i in range(k):
    print(ABC[i])


Measured memory_bytes: 9160
N,K,S = map(int,input().split())

ans = []

for i in range(K):
    ans.append(S)

for i in range(N-K):

    if S == 10**9:
        ans.append(10**9-1)
    else:
        ans.append(10**9)

print (" ".join(map(str,ans)))


Measured memory_bytes: 66528