akhauriyash/Code-Regression huggingface dataset:
# d
N,K = map(int, input().split())
xy = []
for _ in range(N):
    xy.append( tuple(map(int, input().split())) )
xs,ys = map(list, zip(*xy))
xs.sort()
ys.sort()
ans = float('inf')
for l in range(N):
    for r in range(l+1,N):
        for b in range(N):
            for t in range(b+1,N):
                xl,xr = xs[l],xs[r]
                yb,yt = ys[b],ys[t]
                cnt = 0
                for xi,yi in xy:
                    if xl<=xi<=xr and yb<=yi<=yt: 
                        cnt += 1
                if cnt>=K:
                    ans = min(ans, (xr-xl)*(yt-yb))
print(ans)

Measured memory_bytes: 48732
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while ('0'>ch||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do {(t*=10)+=ch-'0';ch=getchar();} while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
const ll mod=998244353;
const int maxn=4010;
int n,k;
ll jc[maxn],iv[maxn],ivjc[maxn],mi[maxn],res[maxn];
ll c(ll x,ll y) {
	if (x<y) return 0;
	return jc[x]*ivjc[y]%mod*ivjc[x-y]%mod;
}
ll solve(int N,int K,int b) {
	ll ans=c(N+b-1,b-1);
	if (!b) {
		ans=0;
		for (int q=1;q<=K;q++)
			ans+=c(N-1,q-1)*mi[q]%mod*c(K,q)%mod,ans%=mod;
		return ans;
	}
	for (int q=1;q<=min(N,K);q++)
		ans+=c(N+b-1,q+b-1)*mi[q]%mod*c(K,q)%mod,ans%=mod;
	return ans;
}
int main() {
	//freopen("1.txt","r",stdin);
	read(k); read(n);
	jc[0]=iv[0]=ivjc[0]=1;
	jc[1]=iv[1]=ivjc[1]=1;
	for (int i=2;i<maxn;i++) {
		jc[i]=jc[i-1]*i%mod;
		iv[i]=iv[mod%i]*(mod-mod/i)%mod;
		ivjc[i]=ivjc[i-1]*iv[i]%mod;
	}
	mi[0]=1;
	for (int i=1;i<maxn;i++) mi[i]=mi[i-1]*2%mod;
	for (int i=2;i<=k+1;i++) {
		int tmp=i/2;
		if (i%2==0) res[i]=(solve(n,tmp-1,k-i+1)+solve(n-1,tmp-1,k-i+1))%mod;
		else res[i]=solve(n,tmp,k-i+1);
	}
	for (int i=2;i<=k+1;i++) printf("%lld\n",res[i]);
	for (int i=k;i>=2;i--) printf("%lld\n",res[i]);
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
typedef long long int ll;
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4
#define pii pair<int,int>


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

  // a[0]>0
  ll sump[n], cntp = 0;
  rep(i,n){
    if (i==0){
      sump[i] = max<ll>(a[i], 1);
      cntp += max<ll>(0,1-a[i]);
    }
    else if (i%2==0){
      sump[i] = max<ll>(sump[i-1] + a[i], 1);
      cntp += max<ll>(0,1-a[i]-sump[i-1]);
    }
    else {
      sump[i] = min<ll>(sump[i-1] + a[i], -1);
      cntp += -min<ll>(0,-1-a[i]-sump[i-1]);
    }
  }

  // a[0]<0
  ll summ[n], cntm = 0;
  rep(i,n){
    if (i==0){
      summ[i] = min<ll>(a[i], -1);
      cntm += -min<ll>(0,-1-a[i]);
    }
    else if (i%2==1){
      summ[i] = max<ll>(summ[i-1] + a[i], 1);
      cntm += max<ll>(0,1-a[i]-summ[i-1]);
    }
    else {
      summ[i] = min<ll>(summ[i-1] + a[i], -1);
      cntm += -min<ll>(0,-1-a[i]-summ[i-1]);
    }
  }
  
  cout << min(cntm, cntp) << endl;


  // cout << fixed << setprecision(6);
  return 0;
}


Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);

    int t;
    cin>>t;
    while(t--)
    {

        ll a,b,d;
        cin>>a>>b;
        d=a*b;
        if(a>b)
            swap(a,b);
        if((a==b) || (a+1==b)){
            cout<<(2ll*a)-2ll<<endl;
        }
        else{
           ll c=sqrt(d);
           if(c*(c+1)<d)
            cout<<(2ll*c)-1ll<<endl;
        else if(c*c==d)
            cout<<(2ll*c)-3ll<<endl;
           else
            cout<<(2ll*c)-2ll<<endl;
        }
    }


    return 0;
}


Measured memory_bytes: 3580
N = int(input())
P = list(map(int, input().split()))
c = 0
for i in range(N):
    f = 1
    if P[i] == i+1:
        if i != N - 1:
            if P[i+1] != i+1:
                t = P[i]
                P[i] = P[i+1]
                P[i+1] = t
                c += 1
        else:
            if P[i-1] != i+1:
                t = P[i]
                P[i] = P[i-1]
                P[i-1] = t
                c += 1
print(c)


Measured memory_bytes: 83968
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    s = input()
    if s == "Sunny":
        print("Cloudy")
    elif s == "Cloudy":
        print("Rainy")
    else:
        print("Sunny")
    return

#B
def B():
    s = S()
    for i in range(len(s)):
        if i%2:
            if s[i] not in ["L","U","D"]:
                print("No")
                return
        else:
            if s[i] not in ["R","U","D"]:
                print("No")
                return
    print("Yes")
    return

#C
def C():
    n,k,q = LI()
    a = IR(q)
    f = [k-q]*(n)
    for i in range(q):
        ai = a[i]-1
        f[ai] += 1
    for i in f:
        if i <= 0:
            print("No")
        else:
            print("Yes")
    return

#D
def D():
    n,m = LI()
    a = LI()
    q = []
    for i in range(n):
        heappush(q,-a[i])
    for i in range(m):
        x = heappop(q)
        x *= -1
        x >>= 1
        heappush(q,-x)
    print(-sum(q))
    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    D()


Measured memory_bytes: 61336
import sys
sys.setrecursionlimit(10**7)    
from collections import deque
input = sys.stdin.readline

seen=[]
#seen=dict()
path=[]

def dfs(g, v,add):
    xx[v]+=add
#    path.append(v)
    seen[v]=True
    for next_v in g[v]:
        if seen[next_v]:
            continue
        dfs(g, next_v,xx[v])
#    path.append(v)

    return

icase=-1
if icase==-1:
    n,q=map(int,input().split())
#    g = [deque([]) for _ in range(n)]
    ab=[[int(x) for x in input().split()] for  _ in range(n-1)]
    px=[[int(x) for x in input().split()] for  _ in range(q)]

    g = [set() for _ in range(n)]
    for ai,bi in ab:
        g[ai-1].add(bi-1)
        g[bi-1].add(ai-1)
    g=tuple(g)

    xx=[0]*n
    for pi,xi in px:
        xx[pi-1]=xx[pi-1]+xi
if icase==0:
    n,q=map(int,input().split())
#    g = [deque([]) for _ in range(n)]
    g = [set() for _ in range(n)]
    for i in range(n-1):
        ai,bi=map(int,input().split())
#        g[ai-1].append(bi-1)
#        g[bi-1].append(ai-1)
        g[ai-1].add(bi-1)
        g[bi-1].add(ai-1)
    g=tuple(g)
    xx=[0]*n
    for i in range(q):
        pi,xi=map(int,input().split())
        xx[pi-1]=xx[pi-1]+xi
elif icase==3:
    n,q=6,2
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1,2])
    g[1]=deque([0,3,4])
    g[2]=deque([0,5])
    g[3]=deque([1])
    g[4]=deque([1])
    g[5]=deque([2])
    p=[0]*q
    x=[0]*q
    p[0]=0
    x[0]=10    
    p[1]=0
    x[1]=10    
    xx=[0]*n
    for i in range(q):
#        pi,xi=map(int,input().split())
        xx[p[i]]=xx[p[i]]+x[i]
elif icase==1:
    n,q=3,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([2])
    g[1]=deque([2])
    g[2]=deque([0,1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=2
    x[1]=100
    p[2]=0
    x[2]=1    
    xx=[0]*n
    for i in range(q):
#        pi,xi=map(int,input().split())
        xx[p[i]]=xx[p[i]]+x[i]
#ans:1 111 101
elif icase==2:
    n,q=4,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1])
    g[1]=deque([0,2,3])
    g[2]=deque([1])
    g[3]=deque([1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=0
    x[1]=100
    p[2]=2
    x[2]=1    
    xx=[0]*n
    for i in range(q):
#        pi,xi=map(int,input().split())
        xx[p[i]]=xx[p[i]]+x[i]
#ans:100 110 111 110

#c=[0]*n

seen=[False]*n
#for i in range(n):
#    seen[i]=False
dfs(g,0,0)

#print(path)

'''
seen=[False]*n

c=[0]*n
cpt=0
for pt in path:
    if seen[pt]==False:
        seen[pt]=True
#        print("pt:",pt,"cpt:",cpt,"xx[pt]:",xx[pt],"c[pt]:",c[pt]+cpt+xx[pt])
        cpt=cpt+xx[pt]
        c[pt]=c[pt]+cpt
    else:
        seen[pt]=False
        cpt=cpt-xx[pt]
           
for i in range(n):
    print(c[i],end=" ")
print()
'''

ans=" ".join(map(str,xx[0:]))
print(ans)
    


Measured memory_bytes: 326152
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int cal(string s)
{
	return 100*(s[0]-'0')+10*(s[1]-'0')+(s[2]-'0');
}

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

	string s; cin>>s;
	int mn=INT_MAX;
	for(int i=0;i<s.length()-2;i++)
	{
		mn=min(mn,abs(cal(s.substr(i,3))-753));
		//cout<<s.substr(i,3)<<" "<<cal(s.substr(i,3))<<"\n";
	}
	cout<<mn<<"\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>
 
using namespace std;
using ll =long long;
 
bool is_int_lround(double x){
  return std::lround(x)==x;
}
int ketasuu(int x){
  int n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}
ll gcd11(ll x, ll y){
  long long a= max(x,y), b=min(x,y), c=a%b;
  while( c!=0){
    a =b;
    b =c;
    c = a%b;
  }
  return b;
}
 
int ab(int x, int y){
  if(x>=y){
    return x-y;
  }
  else if(y>x){
    return y-x;
  }
}
int main(){
  int p,q,r;
  
  cin >>p>>q>>r;
  
  cout <<  min(p+q,min(q+r,r+p))  <<endl;

}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <stdlib.h>

typedef long double ld;
typedef long long ll;

using namespace std;

int main() {
	int n;
	cin >> n;
	int ret = 1000 * (n / 500);
	n %= 500;
	ret += 5 * (n / 5);
	cout << ret << endl;

	return 0;
}


Measured memory_bytes: 3556
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=2010,Mo=1000000007;
int f[N][N][2];
int main() {
    int n,k,d=1;
    cin>>n>>k;
    for(int i=1;i<=n-k-1;i++) (d+=d)%=Mo;
    f[n][0][0]=f[n][1][1]=1;
    for(int i=n-1;i;i--) {
	for(int j=n-1;~j;j--)
	    (f[i+1][j][0]+=f[i+1][j+1][0])%=Mo;
	for(int j=1;j<=n;j++)
	    f[i][j][1]=(f[i+1][j-1][1]+f[i+1][j-1][0])%Mo;
	for(int j=0;j<=n;j++)
	    f[i][j][0]=(f[i+1][j][1]+f[i+1][j][0])%Mo;
    }
    cout<<(1LL*f[1][n-k][0]*d%Mo+Mo)%Mo;
    return 0;
}

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

int N;
int h[200100], a[200100];

struct segtree {
    int size;
    vector<int> node;
    
    segtree(int n) {
        size = 1;
        while (size<n) size *= 2;
        node.resize(2*size-1);
        fill(node.begin(), node.end(), 0);
    }

    void update(int k, int a) {
        k += size-1;
        node[k] = a;
        while (k>0) {
            k = (k-1)/2;
            node[k] = max(node[2*k+1], node[2*k+2]);
        }
    }
    
    int query(int a, int b, int k, int l, int r) {
        if (r<=a || b<=l) return 0;
        if (a<=l && r<=b) return node[k];
        else {
            int vl = query(a, b, 2*k+1, l, (l+r)/2);
            int vr = query(a, b, 2*k+2, (l+r)/2, r);
            return max(vl, vr);
        }
    }
    
    int get(int a, int b) {
        return query(a, b, 0, 0, size);
    }
};
 
signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N;
    rep(i, N) cin >> h[i];
    rep(i, N) cin >> a[i];
    segtree st(200100);
    rep(i, N) st.update(h[i], st.get(0, h[i])+a[i]);
    cout << st.get(0, 200100) << endl;
}

Measured memory_bytes: 7552
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		sc.useDelimiter("\\s");
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		
		if(a < b && b < c){
			System.out.println("Yes");
		}else
		{
			System.out.println("No");
		}
	}

}

Measured memory_bytes: 26108
import numpy as np
from bisect import bisect_left, bisect_right
N, K = map(int, input().split())
count = 0
lis = np.array([0] * (10 ** 5))
for n in range(N):
    a, b = map(int, input().split())
    lis[a - 1] += b
for n in range(100000):
    K -= lis[n]
    if K <= 0:
        print(n + 1)
        break

Measured memory_bytes: 14028
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const ll INF = 1e18;
#define pu push
#define pb push_back
#define mp make_pair
#define print(x) cout << (x) << endl;
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define SORT(x) sort(x.begin(),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define fi first
#define sc second

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // cout << fixed << setprecision(10);
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    long double sum = 0;
    rep(i,N) {
        cin >> A.at(i);
        sum += A.at(i);
    }
    SORT(A);
    if(A.at(N-M)>=sum/4/M) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

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

#define int long long
#define fi first
#define se second
#define otp(n) cout << n;
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define ctv(v) rep(i,(v).size()) ct(v[i])
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define repv(i,v) for(int i=0;i<(v).size();i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define pb(n) push_back(n);

int a,b;

main() {
    cin >> a >> b;
    if (b%a) ct(b-a)
    else ct(b+a)
}


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

#define INF (2e9)
#define FOR(i, a, b) for (ll (i) = (a); (i) < (b); ++(i))
#define REP(i, n) FOR(i, 0, n)

using namespace std;

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

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

using ll = long long;
using ld = long double;

#define ALL(x) (x).begin(), (x).end()
template<class T>
using vc = vector<T>;
using vi = vc<ll>;
using vvi = vc<vi>;

template<class T>
using va = valarray<T>;
using vad = va<ld>;
using vai = va<ll>;

vi Read(ll n) {
    auto      v = vi(n);
    for (auto i = std::size_t(0); i < n; ++i) {
        cin >> v[i];
    }
    return v;
}

template<class T>
void Dump(const T& A) {
    for (const auto& value : A)
        cout << value << "\n";
}

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

    ll n;
    cin >> n;
    const auto v = Read(n);

    int n_q;
    cin >> n_q;
    REP(i, n_q) {
        int q, min, max;
        cin >> q >> min >> max;

        if (q == 0){
            ll ans = INF;
            FOR(j, min, max) chmin(ans, v[j]);
            cout << ans << endl;
        }
        else {
            ll ans = -INF;
            FOR(j, min, max) chmax(ans, v[j]);
            cout << ans << endl;
        }
        
    }

    return 0;
}



Measured memory_bytes: 3176
#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = m; i < (n); i++)
#define RFOR(i, m, n) for (int i = (m - 1); i >= 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;

int main() {
  int n;
  cin >> n;
  int a[n];
  double sum = 0;
  REP(i, n) {
    int tmp;
    cin >> tmp;
    a[i] = tmp;
    sum += tmp;
  }
  int average = round(sum / n);
  int anser = 0;
  REP(i, n) {
    anser += pow(a[i] - average, 2);
  }
  cout << anser << endl;
  return 0;
}

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

using ll = long long;
using ull = unsigned 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 (a>b) { a=b; return 1; } return 0; }
#define rep(i, n) REP(i, 0, n)
#define rep_rev(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
ll t1,t2,t3;
const ll mod = 1000000007;
const int INF = 1e9;
const ll INFLONG = 1e18;

int main(){
    ll s;
    cin >> s;
    vector<ll> dp(s+1);
    dp[0] = 1;
    rep(i,s){
        REP(j,3,s+1){
            if(i + j <= s){
                dp[i+j] += dp[i];
                dp[i+j] %= mod;
            }
        }
        // rep(i,s+1){
        //     cout << dp[i] << " " ;
        // }
        // cout << endl;
    }
    cout << dp[s] << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=100007;
int h[N],dp[N];
main()
{
    int n,k;
    scanf("%lld%lld",&n,&k);
    for(int i=0;i<n;i++)
        scanf("%lld",&h[i]);
    dp[0]=0;
    for(int i=1;i<n;i++)
    {
        if(i>=k)
        {
            dp[i]=1e9;
            for(int j=i-1;j>=i-k;j--)
                dp[i]=min(dp[i],dp[j]+abs(h[i]-h[j]));
        }
        else
        {
            dp[i]=1e9;
            for(int j=0;j<i;j++)
                dp[i]=min(dp[i],dp[j]+abs(h[i]-h[j]));
        }
    }
    printf("%lld\n",dp[n-1]);
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define ll long long
#define P pair<int, int>

using namespace std;
int mod = 1000000007;

int main() {
  string s;
  cin >> s;
  cin >> s;

  cout << 'A' << s.at(0) << 'C' << endl;
}


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

using namespace std;

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)

using ll = long long;
using P = std::tuple<int,int>;

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

int N, Q;
std::vector<int> G[100100];
int start[100100], friends[100100];
int buckets[450], parts[200200];
int doubling[17][100100];

void makeDoubling(){
    for(int i=0;i+1<=16;++i){
        for(int j=1;j<=N;++j){
            if(doubling[i][j] == -1){
                doubling[i+1][j] = -1;
            }else{
                doubling[i+1][j] = doubling[i][doubling[i][j]];
            }
        }
    }
}

void dfs(int v, int& n){
    start[v] = n++;
    
    for(int u : G[v]){
        dfs(u, n);
    }

    friends[v] = n++;
}

void update(int l, int r){
    while(l < r && l % B > 0){
        ++parts[l];
        ++l;
    }

    while(l < r && r % B > 0){
        --r;
        ++parts[r];
    }

    l /= B;
    r /= B;

    while(l < r){
        ++buckets[l];
        ++l;
    }
}

inline int query2(int v){
    return buckets[start[v] / B] + parts[start[v]];
}

int query(int v){
    int lb = 0, ub = 100100, res = v;
    
    while(std::abs(ub - lb) > 1){
        int mid = (lb + ub) / 2;
        int x = v, y = mid, z = 0;

        while(y > 0){
            if(x != -1 && y % 2 == 1){
                x = doubling[z][x];
            }
            ++z;
            y >>= 1;
        }
        
        if(x != -1 && query2(x) == query2(v)){
            lb = mid;
            res = x;
        }else{
            ub = mid;
        }
    }

    return res;
}

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

    while(true){
        std::cin >> N >> Q;
        if(N == 0){return 0;}

        memset(doubling[0], -1, sizeof(doubling[0]));

        for(int i=1;i<=N;++i){
            G[i].clear();
        }
        
        for(int i=0;i<N-1;++i){
            int p;
            std::cin >> p;

            G[p].emplace_back(i+2);
            doubling[0][i+2] = p;
        }

        makeDoubling();

        // for(int i=0;i<16;++i){
        //     printf("# %d\n", i);
        //     for(int j=1;j<=N;++j){
        //         printf("%d\n", doubling[i][j]);            
        //     }
        // }
    
        int ET_N = 0;
        dfs(1, ET_N);

        memset(buckets, 0, sizeof(buckets));
        memset(parts, 0, sizeof(parts));
        
        update(start[1], friends[1]);
    
        // {
        // int v = 3;
        // update(start[v], friends[v]);
        // }    
        // for(int v = 1;v<=N;++v){
        //     int q = query(v);
        //     printf("%d\n", q);
        // }
        // exit(0);
        
        ll sum = 0;
        for(int i=0;i<Q;++i){
            std::string q;
            int v;
            std::cin >> q >> v;

            if(q[0] == 'M'){
                update(start[v], friends[v]);
            }else{
                sum += query(v);
                // printf("%d\n", query(v));
            }
        }

        printf("%lld\n", sum);
    }
}

Measured memory_bytes: 21900
/*Remember: The Struggle is Important*/

//CF,CC,AtC,SPOJ: hp1999
//HE: hemant269
//HR: hemant2132

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

#define     int          long long int
#define     ld           long double
#define     fast()       ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)       x.begin(),x.end()
#define     mem(a,b)     memset(a,b,sizeof(a))
#define     gcd(a,b)     (__gcd((a),(b)))
#define     lcm(a,b)     (((a)*(b))/gcd((a),(b)))
#define     pb           push_back
#define     ins          insert
#define     pii          pair<int,int>
#define     F            first
#define     S            second
#define     show(x)      for(auto c:x)cout<<c<<" ";cout<<"\n";
#define     show2(x)     for(auto c:x)cout<<c.F<<" "<<c.S<<"\n";

const int inf=1e18,M=1e9+7;
const int N=1;

void solve()
{
    int n;
    cin>>n;

    int ans=1ll<<((int)(log2(n)+1));
    --ans;
    cout<<ans;
}

int32_t main()
{
    fast();

    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
        //cout<<"\n";
    }

    return 0;
}



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

int main(){
    int n,k,count=0;
    cin >> n >> k;
    map<int,int>Map;
    for(int i=0;i<k;i++){
        int a=0;
        cin >> a;
        for(int j=0;j<a;j++){
            int b=0;
            cin >> b;
            Map[b]++;
        }
    }
    for(int i=0;i<n;i++){
        if(Map[i+1]==0)count++;
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef long long int ll;
const int N=1e5+5,M=1e4+5;
int n,k,a[N],memo[N][105];
int solve(int ind, int c){
    if(~memo[ind][c])
        return memo[ind][c];
    if(ind==n-1)
        return memo[ind][c]=abs(a[ind]-a[ind-c]);
    if(c==k)
        return memo[ind][c]=abs(a[ind]-a[ind-c])+ solve(ind+1,1);
    if(!c)
        return memo[ind][c]=solve(ind+1,1);
    return memo[ind][c]= min( abs(a[ind]-a[ind-c])+ solve(ind+1,1), solve(ind+1,c+1) ) ;
}
int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    memset(memo,-1,sizeof memo);
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>a[i];
    cout<<solve(0,0)<<'\n';
    return 0;
}


Measured memory_bytes: 47872
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 200010
#define MOD 1000000007
using namespace std;
int dp[MAXN];
int n,a[MAXN];
int las[MAXN];
int main(){
	SF("%d",&n);	
	for(int i=1;i<=n;i++)
		SF("%d",&a[i]);
	dp[0]=1;
	for(int i=1;i<=n;i++){
		dp[i]=dp[i-1];
		if(las[a[i]]&&las[a[i]]!=i-1)
			dp[i]=(dp[i]+dp[las[a[i]]])%MOD;
		las[a[i]]=i;
//		PF("[%d %d]\n",i,dp[i]);
	}
	PF("%d",dp[n]);
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n{},d{};
    cin>>n>>d;
    d = 2*d +1;
    if(n%d!=0)
    cout<<n/d +1 <<endl;
    else{
        cout<<n/d<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
int d[100005];
int main()
{
	int n;
	while ( ~scanf( "%d", &n ) )
	{
		int a = 0, b = 0, c = 0;
		for ( int i = 0; i < n; i++ )
		{
			scanf( "%d", d+i );
			if ( d[i]%4==0 )
				a++;
			else if ( d[i]%2==0 )
				b++;
			else
				c++;
		}
		if ( b )
			c++;
		if ( a - c >= -1 )
			printf( "Yes\n" );
		else
			printf( "No\n" );
	}
}


Measured memory_bytes: 512
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
	int N,r=0;
	scanf("%d",&N);
	vector<vector<int> >v(N+1);
	v[0].resize(N);
	for(int i=1;i<=N;i++){
		v[i].resize(N+1);
		for(int j=1;j<=N;j++)scanf("%d",&v[i][j]);
	}
	for(int i=0;i<N;i++)for(int j=0;j<=N;j++)v[i+1][j]+=v[i][j];
	for(int i=0;i<=N;i++)for(int j=0;j<N;j++)v[i][j+1]+=v[i][j];
	for(int i0=0;i0<N;i0++)for(int i1=i0+1;i1<=N;i1++){
#if 1
		int r0=v[i0][0]-v[i1][0]-v[i0][1]+v[i1][1],r1=r0;
		int s=0;
		if(N>1)s=v[i0][1]-v[i1][1]-v[i0][2]+v[i1][2];
		r1=max(r1,r0+s);
		for(int k=2;k<N;k++){
			r0+=v[i0][k-1]-v[i0+1][k-1]-v[i0][k]+v[i0+1][k];
			if(i1-i0>1)r0+=v[i1-1][k-1]-v[i1][k-1]-v[i1-1][k]+v[i1][k];
			r0=max(r0,v[i0][k-1]-v[i1][k-1]-v[i0][k]+v[i1][k]);
			s=v[i0][k]-v[i1][k]-v[i0][k+1]+v[i1][k+1];
			r1=max(r1,r0+s);
		}
		//printf("%d %d %d\n",i0,i1,r1);
		r=max(r,r1);
#else
		for(int j0=0;j0<N;j0++)for(int j1=j0+1;j1<=N;j1++){
			int n=v[i0][j0]-v[i1][j0]-v[i0][j1]+v[i1][j1];
			int m=0;
			if(i1-i0>2&&j1-j0>2)m=v[i0+1][j0+1]-v[i1-1][j0+1]-v[i0+1][j1-1]+v[i1-1][j1-1];
			r=max(r,n-m);
		}
#endif
	}
	printf("%d\n",r);
}

Measured memory_bytes: 1380
#!/usr/bin/env run-cargo-script

#![allow(unused_imports)]

use std::cmp;
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
use std::fmt;
use std::io::{self, BufWriter, Read, StdinLock, Write};
use std::ops::{Add, Div, Mul, Sub};
use std::str::{self, FromStr};

fn solve(a: u32, b: u32, c: u32, d: u32) -> String {
    if a + b > c + d {
        "Left"
    } else if a + b < c + d {
        "Right"
    } else {
        "Balanced"
    }.to_owned()
}

fn main() {
    let stdin = io::stdin();
    let mut sc = Scanner::new(stdin.lock().bytes());
    println!("{}", solve(sc.next(), sc.next(), sc.next(), sc.next()));
}

struct Scanner<R: Read> {
    buf: Vec<u8>,
    bytes: io::Bytes<R>,
}

#[allow(dead_code)]
impl<R: Read> Scanner<R> {
    fn new(bytes: io::Bytes<R>) -> Self {
        Scanner {
            buf: Vec::with_capacity(1024),
            bytes: bytes,
        }
    }

    fn next<T: FromStr>(&mut self) -> T
    where
        <T as FromStr>::Err: fmt::Debug,
    {
        let buf = &mut self.buf;
        buf.clear();
        self.bytes
            .by_ref()
            .map(Result::unwrap)
            .skip_while(|&c| c == ' ' as u8 || c == '\n' as u8)
            .take_while(|&c| !(c == ' ' as u8 || c == '\n' as u8))
            .foreach(|c| buf.push(c));
        str::from_utf8(&buf).unwrap().parse().unwrap()
    }

    fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T>
    where
        <T as FromStr>::Err: fmt::Debug,
    {
        (0..n).map(|_| self.next()).collect()
    }

    fn pairs<T1: FromStr, T2: FromStr>(&mut self, n: usize) -> Vec<(T1, T2)>
    where
        <T1 as FromStr>::Err: fmt::Debug,
        <T2 as FromStr>::Err: fmt::Debug,
    {
        (0..n).map(|_| (self.next(), self.next())).collect()
    }

    fn trios<T1: FromStr, T2: FromStr, T3: FromStr>(&mut self, n: usize) -> Vec<(T1, T2, T3)>
    where
        <T1 as FromStr>::Err: fmt::Debug,
        <T2 as FromStr>::Err: fmt::Debug,
        <T3 as FromStr>::Err: fmt::Debug,
    {
        (0..n)
            .map(|_| (self.next(), self.next(), self.next()))
            .collect()
    }

    fn mat<T: FromStr>(&mut self, m: usize, n: usize) -> Vec<Vec<T>>
    where
        <T as FromStr>::Err: fmt::Debug,
    {
        (0..m).map(|_| self.vec(n)).collect()
    }

    fn strings_as_mat<T, F: FnMut(u8) -> T>(&mut self, h: usize, mut f: F) -> Vec<Vec<T>> {
        (0..h)
            .map(|_| {
                self.bytes
                    .by_ref()
                    .map(Result::unwrap)
                    .skip_while(|&c| c == ' ' as u8 || c == '\n' as u8)
                    .take_while(|&c| !(c == ' ' as u8 || c == '\n' as u8))
                    .map(&mut f)
                    .collect()
            })
            .collect()
    }
}

trait Foreach {
    type Item;
    fn foreach<F: FnMut(Self::Item)>(self, f: F);
}

impl<T, I: Iterator<Item = T>> Foreach for I {
    type Item = T;

    fn foreach<F: FnMut(T)>(self, mut f: F) {
        self.fold((), move |(), x| f(x));
    }
}


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

const int MAXN=100000+10;
vector<int> edge[MAXN];//用邻接表来实现树的存储
int n,cnt[3];//cnt用来记录颜色数量
int tree[MAXN];//tree数组储存每个节点的颜色，1是指black，2指white

void bfs()
{
    queue<int> q;
    q.push(1),q.push(n);//Fennec先，Snuke后，所以先后入队
    while(!q.empty())
    {
        int temp=q.front();
        q.pop();
        cnt[tree[temp]]++;//注意位置！！（咳咳）
        for(int i=0;i<edge[temp].size();++i)//枚举所有节点
        {
            int v=edge[temp][i];
            //cnt[tree[temp]]++;  不要在意细节（^_^）
            if(tree[v])continue;
            else tree[v]=tree[temp];//判断是否涂过色
            q.push(v);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    memset(tree,0,sizeof(tree));
    cin>>n;
    for(int i=1;i<n;++i)
    {
        int x,y;
        cin>>x>>y;
        edge[x].push_back(y);
        edge[y].push_back(x);//邻接表建树
    }
    tree[1]=1,tree[n]=2;
    bfs();
    if(cnt[2]>=cnt[1])//因为Fennec先手，所以如果最终结果相同，很明显是Snuke赢了
        cout<<"Snuke"<<endl;
    else
        cout<<"Fennec"<<endl;
    return 0;
}

Measured memory_bytes: 6272
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FASTIO cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
#define loop(i,a,b) for(int i=a; i<b; i++)
#define INF 10000000000099ll
#define mod 1000000007

ll solve(vector<int> wt, vector<int> val, int W, int n)
{
    ll dp[n+1][W+1];
    memset(dp, 0, sizeof dp);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=W; j++){
            if(wt[i]<=j){
                dp[i][j]= max(val[i]+ dp[i-1][j-wt[i]], dp[i-1][j]);
            }else{
                dp[i][j]= dp[i-1][j];
            }
        }
    }
    return dp[n][W];
}

int main()
{
    FASTIO;
    int n, W;
    cin>>n>>W;
    vector<int> wt(n+1);
    vector<int> val(n+1);
    loop(i, 1, n+1){
        cin>>wt[i];
        cin>>val[i];
    }
    cout<<solve(wt, val, W, n);
    return 0;
}




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

template<typename T, typename U> void cmax(T &a, U b) { if (a < b) a = b; }
template<typename T, typename U> void cmin(T &a, U b) { if (a > b) a = b; }

signed main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);

  int N;
  cin >> N;
  long A = LONG_MIN, B = LONG_MAX;
  long C = LONG_MIN, D = LONG_MAX;
  for (int i = 0; i < N; i++) {
    int x, y;
    cin >> x >> y;
    cmax(A, x + y);
    cmin(B, x + y);
    cmax(C, x - y);
    cmin(D, x - y);
  }
  cout << max(A - B, C - D) << "\n";
}

Measured memory_bytes: 3624
import java.util.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {
  static Scanner sc = new Scanner(System.in);
  public static void main(String[] args) {
    // aoj version
    while(true) {
      int n = sc.nextInt();
      int m = sc.nextInt();
      if(n==0)break;
      @SuppressWarnings({"unchecked"})
      ArrayList<Integer>[] graph = (ArrayList<Integer>[])new ArrayList[n];
      for(int i = 0; i < n; i++) graph[i] = new ArrayList<Integer>();
      for(int i = 0; i < m; i++) {
        int a = sc.nextInt(); a--;
        int b = sc.nextInt(); b--;
        graph[a].add(b);
        graph[b].add(a);
      }
      boolean[] flags = new boolean[n];
      for(int f : graph[0])
        flags[f] = true;
      for(int f : graph[0])
        for(int ff : graph[f])
          flags[ff] = true;
      flags[0] = false;
      int count = 0;
      for(boolean f : flags) if(f) count++;
      System.out.println(count);
    }
  }
}

Measured memory_bytes: 13000
#include<stdio.h>
#include<math.h>

int main() {
    //変数の宣言
    int i, n, hako[1000];
    double h, sum;
    
    while (1) {
        //入力
        scanf("%d", &n);
        if (n == 0) {
            break;
        }
        
        //初期化
        sum = 0;
        h = 0;
        
        for (i=0; i<n; i++) {//nの分だけ
            scanf("%d", &hako[i]);
            sum += hako[i]; //足してく
        }
        
        sum = sum / n;
        
        for (i=0; i<n; i++) {
            h = h + pow (hako[i] - sum, 2.0); //(hako[i] - sum)^2.0 ←double
        }
        
        h = h / n;
        
        //出力
        printf("%lf\n", pow(h, 1.0/2.0));
    }
    
    return 0;
}



Measured memory_bytes: 2104
#include <iostream>
#include <string>

using namespace std;

int main(){
    int i = 0;
    string str;
    getline(cin, str);

    while(str[i]) {
         if( isupper( str[i] ) != 0 ) {
             cout <<  char(str[i] + 0x20);
         } else if ( islower( str[i] ) != 0 ){
             cout << char(str[i] - 0x20);
         } else {
             cout << str[i];
         }
        i++;
    }
    cout << endl;
    return 0;
}


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


#define DEBUG

using namespace std;

const ll MOD = 998244353;
const ll INF = (ll)1000000007 * 1000000007;


#ifdef DEBUG
#define PRINT(A) std::cout << (#A) << ":" << (A) << std::endl;
#else
#define PRINT(A)
#endif

typedef pair<int, int> P;

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

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


ll N, M, K;
ll A[201];


signed main() {

    string S; cin >> S;

    int len = S.length();

    string res[10];

    int count = 0;

    rep(i, len){
        if(S[i] == 'A' || S[i] == 'C' || S[i] == 'G' || S[i] == 'T'){
            res[count].push_back(S[i]);
        }
        else{
            count++;
        }
    }
    
    int max = 0;
    int maxCount = 0;
    rep(i,10){
        if(chmax(max, (int)res[i].length())){
            maxCount = i;
        }
    }
    cout << res[maxCount].length() << endl;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-


def can_contains(S, T):
  for s, t in zip(S, T):
    if s != '?' and s != t:
      return False

  return True


def main():
  Sd = input()
  T = input()

  len_T = len(T)

  if len(Sd) < len_T:
    print('UNRESTORABLE')
    return 

  for idx in range(len(Sd) - len_T, -1, -1):
    if can_contains(Sd[idx:idx + len_T], T):
      result = Sd.replace('?', 'a')
      result = result[:idx] + T + result[idx + len_T:] 
      
      print(result)
      return

  print('UNRESTORABLE')


if __name__ == '__main__':
  main()


Measured memory_bytes: 3064
#include<stdio.h>

int gcd(int num1,int num2);
void change(int *num1,int *num2);

int main(void)
{
  int num1,num2;

  scanf("%d %d",&num1,&num2);

  printf("%d\n",gcd(num1,num2));

  return 0;
}


void change(int *num1,int *num2)
{
  int tmp;

  if(*num1>*num2)
    {
      tmp=*num1;
      *num1=*num2;
      *num2=tmp;
    }
}

int gcd(int num1,int num2)
{
  int num3;
  
  change(&num1,&num2);

  num3=num1%num2;
  
  while(num3>0)
    {
      num1=num2;
      num2=num3;
      num3=num1%num2;
    }
  
  return num2;
}



Measured memory_bytes: 2064
import java.io.PrintWriter;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int[] p = new int[100001];
		int [] p2017 = new int[100001];
		int count = 0;
		for (int i = 2; i <= 100000; i++) {
			if (p[i] != -1) {
				p[i] = 1;
				if (p[(i + 1) / 2] > 0)
					count++;
				for (int j = 2; i * j <= 100000; j++) {
					p[i * j] = -1;
				}
			}
			p2017[i] = count;
		}
		int q = Integer.parseInt(sc.next());
		int l;
		int r;
		for (int i = 0; i < q; i++) {
			l = Integer.parseInt(sc.next());
			r = Integer.parseInt(sc.next());
			out.println(p2017[r] - p2017[l - 1]);
		}
		out.flush();
	}
}

Measured memory_bytes: 53372
n = int(input())
t,a = map(int,input().split())
ar = list(map(int,input().split()))
mxt,tt,ind = 100000000, 0,0
for i in range(n):
    tt = t - ar[i]*0.006
    f = 0
    if a<0 and tt < 0:
        f, a,tt =1, abs(a),abs(tt)
    if abs(a-tt) < mxt:
        mxt = abs(a-tt)
        ind = i
    if f == 1:
        a = -a
print(ind+1)

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

int n;
long long ans=0;
string a[100001];
int cnt[5];

int main(){
	cin>>n;
	for (int i=0;i<n;i++) {
		cin>>a[i];
		if (a[i][0]=='M') cnt[0]++;
		else if (a[i][0]=='A') cnt[1]++;
		else if (a[i][0]=='R') cnt[2]++;
		else if (a[i][0]=='C') cnt[3]++;
		else if (a[i][0]=='H') cnt[4]++;
	}
	for(int i = 0; i < 5; i++) 
    	if (cnt[i]) for(int j = i + 1; j < 5; j++) 
      		if (cnt[j]) for(int k = j + 1; k < 5; k++) 
        		if (cnt[k]) ans += 1ll * cnt[i] * cnt[j] * cnt[k];
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 6144
#!/usr/bin/env python3
import sys
import itertools

def solve(S: str):
    LEN = len(S)
    bit_list = list(itertools.product([0, 1], repeat=LEN-1))
    s = S[::-1]
    answer=0
    for b in bit_list:
        a = 0
        keta =0 
        for i in range(LEN):
            a += int(s[i])*10**keta
            if i == LEN-1:
                break
            keta+=1
            if b[i] == 1:
                keta = 0
        answer += a
            
            
    print(answer)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)
    solve(S)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>
#include<array>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i, a, b) for(int i = a; i < b; i++)
#define rrep(i, a, b) for(int i = b - 1; i >= a; i--)
#define repl(i, a, b) for(long long i = a; i < b; i++)
#define rrepl(i, a, b) for(long long i = b - 1; i >= a; i--)
#define ALL(a) a.begin(), a.end()
using pii = pair<int,int>;
using piii = pair<pii,int>;
using pll = pair<long long, long long>;
using plll = pair<pll, long long>;

template<class T>inline bool chmax(T &a, const T &b) {if(a<b){a = b; return 1;} return 0; };
template<class T>inline bool chmin(T &a, const T &b) {if(a>b){a = b; return 1;} return 0; };
void iosetup() {
    cin.tie(nullptr);ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
}
//----------------------- edit from here ---------------------------------

bool between(ll x, ll y1, ll y2){
    if(y1 > y2) swap(y1, y2);
    y1++, y2--;
    if(!(y1 <= y2)) return false;

    while(x > 0){
        if(x % 3 == 1){
            if(y2 - y1 > 3) return true;
            repl(y, y1, y2 + 1) if(y % 3 == 1) return true;
        }
        x /= 3; y1 /= 3; y2 /= 3;
    }
    return false;
}

ll get_extra(ll x1, ll y1, ll x2, ll y2){
    ll ans = 0;
    ll three = 1;
    rep(i, 0, 35){
        if(x1 / three == x2 / three and 
            between(x1 / three, y1 / three, y2 / three)){
            ll tmp = min(min(x1 % three, x2 % three) + 1,
                 three - max(x1 % three, x2 % three));
            chmax(ans, tmp);
        }
        three *= 3;
    }
    return ans;
}

ll get_dist(ll x1, ll y1, ll x2, ll y2){
    return abs(x1 - x2) + abs(y1 - y2) + 
        2 * max(get_extra(x1, y1, x2, y2) ,get_extra(y1, x1, y2, x2));
}
int main(){
    iosetup();
    int Q; cin >> Q;
    while(Q--){
        ll a, b, c, d; cin >> a >> b >> c >> d; a--, b--, c--, d--;       
        cout << get_dist(a, b, c, d) << endl;
    }
    return 0;
}

Measured memory_bytes: 3652
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;

int main(){
    int n, k;
    cin >> n >> k;

    long long int c[n], d[n];
    // input a_i cards
    for(int i=0; i<n; i++){
        cin >> c[i];
        d[i] = 0;
    }
    // sort descend
    for(int i=0; i<n; i++){
        for(int j=0; j<n-i-1; j++){
            if(c[j] < c[j+1]){
                swap(c[j], c[j+1]);
            }
        }
    }

    for(int i=0; i<n; i++){
        vector<int> hyou;
        long long int list = 0;
        for(int j=i; j<n; j++){
            if(list + c[j] >= k){
                hyou.push_back(j);
                for(int v=0; v < hyou.size(); v++){
                    d[hyou[v]] = 1;
                }
                hyou.resize(0);
            }else{
                hyou.push_back(j);
                list += c[j];
            }
        }
    }

    int ans = 0;

    for(int i=0; i<n; i++){
        if(!d[i]) ans++;
    }

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

Measured memory_bytes: 384
N, M = map(int, input().split())


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


u = UnionFind(N+1)
for _ in range(M):
    a, b = map(int, input().split())
    u.union(a, b)

mx = 0
for i in range(1, N+1):
    mx = max(mx, u.size(i))

print(mx)


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

using namespace std;

using ll = long long;
using ld = long double;

template <class T>
using vec = vector<T>;
template <class T>
using vec2 = vector<vector<T>>;

constexpr int INF = numeric_limits<int>::max();
constexpr ll INFL = numeric_limits<ll>::max();
constexpr ll MOD = 1000000007; // 10^9+7

#define rep(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)

int main()
{
    int n;
    ll d;
    cin >> n >> d;
    int ret = 0;
    rep(i, n)
    {
        ll x, y;
        cin >> x >> y;
        if (d * d >= x * x + y * y)
        {
            ret++;
        }
    }

    cout << ret << endl;

    return 0;
}


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

int main()
{
  string S;
  cin >> S;
  if((S[0] == S[1]) &&
    (S[1] == S[2]) &&
    (S[2] == S[0]))
    cout << "No" << endl;
  else
    cout << "Yes" << endl;
  
  return 0;
}

Measured memory_bytes: 3560
import sys
input=sys.stdin.readline

def main():
    K,S = map(int, input().split())
    n = 0
    for i in range(K+1):
        for j in range(K+1):
            if S-i-j >= 0 and S-i-j <= K:
                n += 1
    print(n)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
a, b = map(int, input().split())


def quo(x, y):
    return x // y


def remain(x, y):
    return x % y


def div(x, y):
    return x / y


d = quo(a, b)
r = remain(a, b)
f = div(a, b)

print(f"{d} {r} {f:.6f}")



Measured memory_bytes: 5628
#include <stdio.h>

int main(){
  int n, k;
  scanf("%d%d", &n, &k);
  int a[n];
  for(int i = 0; i < n; i++){
    scanf("%d", &a[i]);
  }

  for(int i = k; i < n; i++){
    if(a[i] > a[i - k]){
      printf("Yes\n");
    }else{
      printf("No\n");
    }
  }
}


Measured memory_bytes: 2424
#include <stdio.h>



int main(int argc, char **argv)
{
	unsigned int a,b;
	unsigned int swap;
	unsigned int i;
	char inputs[22];
	
	
	fgets( inputs , sizeof( inputs ), stdin );
	sscanf( inputs , "%d %d", &a, &b );
	
	if( a == 0 || b == 0 )
		return -1;
	
	if( a > b ){
		swap = a;
		a = b;
		b = swap;
	}
	
	i = 0;
	while( i < 1000000000 ){
		if( ( swap = b % a ) == 0 ){
			break;
		}
		b = a;
		a = swap;
		i++;
	}
	
	printf("%d\n",a);
	
	
	return 0;

}

Measured memory_bytes: 1848
#include<iostream>

using namespace std;

int main(void)
{
	int n,m,x;
	cin >> n >> m >> x;

	int a[m];
	for(int i=1;i<=m;i++)
		cin >> a[i-1];

	int l=0,r=0;

	for(int i=1;i<=m;i++)
	{
		if(a[i-1]<x)
			l++;
		else
			r++;
	}

	cout << min(l,r) << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
  char *s="python3 -c\""
"a,b,c,d=map(int,input().split());print(['RLiegfhtt'[a+b>c+d::2],'Balanced'][a+b==c+d])\n"
"\"";
  system(s);
  return 0;
}            

Measured memory_bytes: 3280
#include<bits/stdc++.h>
#include<algorithm>
#define int long long
#define ll long long
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define bs binary_search
#define mp make_pair
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ld long double
#define meme(a,no)  memset(a,no,sizeof(a))


using namespace std; 

const int INF=1e9+7;
/*
const int N=2*100000+5;

const int mod=998244353;

vector<vector<int>>v(N);

int vis[N]={0};

int level[N];*/

long long binpow(ll a,ll b){
    ll res=1;
    while(b>0){
        if(b&1){
            res=res*a;
        }
        a=a*a;
        b>>=1;
    }
    return res;
}

long long binpow_mod(ll a,ll b,ll c){
    ll res=1;
    while(b>0){
        if(b&1){
            res=res*a%c;
        }
        a=a*a%c;
        b>>=1;
    }
    return res;
}
/*void dfs(int a){
    vis[a]=1;
    for(auto x:v[a]){
        if(!vis[x]){
            dfs(x);
        }
    }
}*/
//vector<bool>v;
//vector<int>isfactor;

/*void Seive(int n){
    v.assign(n+1,true);
    isfactor.assign(n+1,0);
    v[0]=false; v[1]=false;
    for(int i=2;i<=n;i++){
        if(v[i]){
            isfactor[i]=i;
            for(int j=i*i;j<=n;j+=i){
                if(v[j]){
                    v[j]=false;
                    isfactor[j]=i;
                }
            }
        }
    }
    
}*/
int32_t main(){
    ios
    int T;
    //cin>>T;
    T=1;
    while(T--){
        int n;
        cin>>n;
        int a[n];
        int i,j,k,l;
        for(i=0;i<n;i++){
            cin>>a[i];
        }
        int sum=0;
        for(i=1;i<n;i++){
            if(a[i]<a[i-1]){
                int diff=a[i-1]-a[i];
                sum+=diff;
                a[i]+=diff;
            }
        }
        cout<<sum<<endl;
    }
    
    
    
    
}

Measured memory_bytes: 5200