akhauriyash/Code-Regression huggingface dataset:
/* AtCoder My Practice
 * author: Leonardone @ NEETSDKASU
 */   /* ABC075 D 解説読後 */
const UNI = 100000;
class UInt {
  num = [0, 0, 0, 0];
  setValue(v: number): UInt {
    for (let i = 0; i < 4; i++) {
      this.num[i] = v % UNI;
      v = (v / UNI) | 0;
    }
    return this;
  }
  less(that: UInt): Boolean {
    for (let i = 3; i >= 0; i--) {
      if (this.num[i] < that.num[i]) {
        return true;
      } else if (this.num[i] > that.num[i]) {
        return false;
      }
    }
    return false;
  }
  sub(that: UInt): UInt {
    let ret = new UInt();
    let car = 0;
    for (let i = 0; i < 4; i++) {
      ret.num[i] = this.num[i] - that.num[i] - car;
      if (ret.num[i] < 0){
        car = 1;
        ret.num[i] += UNI;
      } else {
        car = 0;
      }
    }
    return ret;
  }
  mul(that: UInt): UInt {
    let ret = new UInt();
    let car = 0;
    for (let i = 0; i < 4; i++) {
      ret.num[i] += car;
      for (let j = 0; j < 4; j++) {
        ret.num[i+j] += this.num[i] * that.num[j];
      }
      car = (ret.num[i] / UNI) | 0;
      ret.num[i] %= UNI;
    }
    return ret;
  }
  toString(): string {
    let s = '';
    for (let i = 3; i >= 0; i--) {
      if (s.length === 0) {
        if (this.num[i] > 0) {
          s = this.num[i].toString();
        }
      } else {
        const n = (UNI + this.num[i]).toString();
        s += n.substring(1);
      }
    }
    return s.length === 0 ? '0' : s;
  }
}
let buf = '';
process.stdin.setEncoding('utf8');
process.stdin.on('readable', () => {
  let s = process.stdin.read();
  if (s !== null) { buf += s.toString(); }
});
process.stdin.on('end', () => {
  const lines = buf.trim().split("\n");
  const getVals = (p) => lines[p].split(' ').map( (x) => parseInt(x) )
  const [n, k] = getVals(0);
  let rects: {x: number, y: number}[] = [];
  for (let i = 0; i < n; i++) {
    const [x, y] = getVals(i+1);
    rects[i] = {x, y};
  }
  let ans: UInt | null = null;
  for (let i1 = 0; i1 < n; i1++) {
    for (let i2 = i1+1; i2 < n; i2++) {
      let y1 = rects[i1].y;
      let y2 = rects[i2].y;
      if (y1 === y2) { continue; }
      if (y2 < y1) {
        [y1, y2] = [y2, y1];
      }
      for (let j1 = 0; j1 < n; j1++) {
        for (let j2 = j1+1; j2 < n; j2++) {
	      let x1 = rects[j1].x;
          let x2 = rects[j2].x;
          if (x1 === x2) { continue; }
          if (x2 < x1) {
            [x1, x2] = [x2, x1];
          }
          let cnt = 0;
          for (let p = 0; p < n; p++) {
            const r = rects[p];
            if (r.x < x1 || x2 < r.x) { continue; }
            if (r.y < y1 || y2 < r.y) { continue; }
            cnt++;
          }
          if (cnt >= k) {
            const Y1 = (new UInt()).setValue(y1);
            const Y2 = (new UInt()).setValue(y2);
            const X1 = (new UInt()).setValue(x1);
            const X2 = (new UInt()).setValue(x2);
            const s = Y2.sub(Y1).mul(X2.sub(X1));
            if (ans === null || s.less(ans)) {
              ans = s;
            } 
          }
        } // j2
      } // j1
    } // i2
  } // i1
  console.log(ans.toString());
});

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

int main() {
  ll a, b, k;
  cin >> a >> b >> k;
  rep(i, k) {
    if (i%2) {
      if (b%2) {
        b--;
        a += b/2;
        b /= 2;
      } else {
        a += b/2;
        b /= 2;
      }
    } else {
      if (a%2) {
        a--;
        b += a/2;
        a /= 2;
      } else {
        b += a/2;
        a /= 2;
      }
    }
  }
  cout << a << ' ' << b << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <queue>
#include <vector>
#include <cstring>

using std::cin;
using std::cout;
using std::cerr;
using std::endl;

const int vx[4] = { 0, 1, 0, -1 }, vy[4] = { 1, 0, -1, 0 };

int W, H;
std::string s[21];
bool is_searched[21][21];

int solve() {
  int sx, sy;

  for (int i = 0; i < H; ++i) {
    for (int j = 0; j < W; ++j) {
      if (s[i][j] == '@') {
        sx = i, sy = j;
        goto L;
      }
    }
  }
L:

  std::memset(is_searched, false, sizeof is_searched);

  int ans = 1;

  std::queue<std::pair<int, int> > que;
  que.push({ sx, sy });
  is_searched[sx][sy] = true;

  while (!que.empty()) {
    std::pair<int, int> p = que.front();
    que.pop();

    for (int i = 0; i < 4; ++i) {
      int nx = p.first + vx[i], ny = p.second + vy[i];

      if (0 <= nx && nx < H && 0 <= ny && ny < W && !is_searched[nx][ny] && s[nx][ny] == '.') {
        ans++;
        is_searched[nx][ny] = true;
        que.push({ nx, ny });
      }
    }
  }

  return ans;
}

int main() {
  while (cin >> W >> H, H | W) {
    for (int i = 0; i < H; ++i) {
      cin >> s[i];
    }

    int ans = solve();

    cout << ans << endl;
  }

  return 0;
}


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

int main() {
    int N, D;
    cin >> N >> D;

    vector<vector<int>> X(N, vector<int>(D));
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < D; x++) {
            cin >> X[y][x];
        }
    }

    int n = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i != j) {
                double dist = 0.0;
                for (int x = 0; x < D; x++) {
                    dist += pow(X[i][x] - X[j][x], 2.0);
                }

                dist = sqrt(dist);
                if (ceil(dist) == dist) {
                    n++;
                }
            }
        }
    }

    cout << n / 2 << endl;
}

Measured memory_bytes: 256
def gcd(a,b):
    if a<b:
        a,b=b,a
    if(a%b==0):
        return  b    
    c=b       
    b=a%b
    return gcd(c,b)      
n=int(input())
a=list(map(int,input().split()))
s=gcd(a[0],a[1])
for i in range(2,n):
    s=gcd(s,a[i])
print(s)    


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

int main(void) {
	int n;
	char moji[53];
	int num[53];
	int snum[14] = {};
	int hnum[14] = {};
	int cnum[14] = {};
	int dnum[14] = {};

	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> moji[i] >> num[i];
	}
	for (int t = 1; t <= 13; t++) {
		for (int i = 1; i <= n; i++) {
			if ((moji[i] == 'S') && (num[i] == t)) {
				snum[t] = 1;
				break;
			}
		}
	}
	for (int t = 1; t <= 13; t++) {
		for (int i = 1; i <= n; i++) {
			if ((moji[i] == 'H') && (num[i] == t)) {
				hnum[t] = 1;
				break;
			}
		}
	}
	for (int t = 1; t <= 13; t++) {
		for (int i = 1; i <= n; i++) {
			if ((moji[i] == 'C') && (num[i] == t)) {
				cnum[t] = 1;
				break;
			}
		}
	}
	for (int t = 1; t <= 13; t++) {
		for (int i = 1; i <= n; i++) {
			if ((moji[i] == 'D') && (num[i] == t)) {
				dnum[t] = 1;
				break;
			}
		}
	}

	for (int i = 1; i <= 13; i++) {
		if (snum[i] != 1) {
			cout << "S " << i<<"\n";
		}
	}
	for (int i = 1; i <= 13; i++) {
		if (hnum[i] != 1) {
			cout << "H " << i << "\n";
		}
	}
	for (int i = 1; i <= 13; i++) {
		if (cnum[i] != 1) {
			cout << "C " << i << "\n";
		}
	}
	for (int i = 1; i <= 13; i++) {
		if (dnum[i] != 1) {
			cout << "D " << i << "\n";
		}
	}
	return 0;
}

Measured memory_bytes: 3096
#include <stdio.h>
#include <string.h>
char s[10];
int a,w,t,r;
int main(){
	int n,i;
	scanf("%d",&n);
	while(n--){
		scanf("%s",s);
		if(s[0]=='A')a++;//统计首字母数量
		else if(s[0]=='W')w++;
		else if(s[0]=='T')t++;
		else if(s[0]=='R')r++;
	}
	printf("AC x %d\n",a);
	printf("WA x %d\n",w);
	printf("TLE x %d\n",t);
	printf("RE x %d\n",r);
	return 0;
}

Measured memory_bytes: 1728
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please


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


	int N, M;
	cin >> N >> M;
	int A[100001] = {};
	rep(i, M) {
		int a;
		cin >> a;
		A[a] = 1;
	}

	ll dp[100001] = {};
	dp[0] = 1;
	ll mod = 1e9 + 7;

	rep1(i, N) {
		if (A[i] == 0) {
			dp[i] = dp[i - 1];
			if (i - 2 >= 0) dp[i] += dp[i - 2];
			dp[i] %= mod;
		}
	}

	co(dp[N]);

	Would you please return 0;
}

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

#define sp ' '
#define endl '\n'
#define st first
#define nd second
#define sz(x) ((long long int)x.size())
#define pb push_back
#define pob pop_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define forn(xx, yy) for(long long int yy = 0; yy < xx; ++yy)
#define prn(xx) cout << xx << '\n'
#define prs(xx) cout << xx << ' '
#define test cout << "TEST " << tn++ << '\n';

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;

const long long int mod = 1e9 + 7;
const long long int inf = 2e9 + 13;
const long double pi = acos(-1.0);
const long double eps = 1e-9;

ll mx(ll x, ll y){ return (x>y?x:y); }
ll mn(ll x, ll y){ return (x<y?x:y); }
ll tn = 1;

void max_self(ll &x, ll y){ x = mx(x, y); }
void min_self(ll &x, ll y){ x = mn(x, y); }
void add(ll &x, ll y){ x%=mod; x += (y%mod); x%=mod; }
void mul(ll &x, ll y){ x%=mod; x *= (y%mod); x%=mod; }

ll us(ll n, ll x, ll m){
    if(!x) return 1;
    ll a = us(n, x>>1, m);
    return (((a*a)%m)*(x&1?n:1))%m;
}

int main(int argc, char **argv){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll N; cin >> N;
    vll ver(4, 0);

    for(ll i = 0; i < N; ++i){
        string v; cin >> v;
        if(v == "AC") ver[0]++;
        if(v == "WA") ver[1]++;
        if(v == "TLE") ver[2]++;
        if(v == "RE") ver[3]++;
    }
    cout << "AC x " << ver[0] << endl;
    cout << "WA x " << ver[1] << endl;
    cout << "TLE x " << ver[2] << endl;
    cout << "RE x " << ver[3] << endl;


    return 0;
}

//cikisir



Measured memory_bytes: 3640
A,B,C,X,Y = map(int,input().split())

#全部Cで買うとき
a = 2*C*min(X,Y) + 2*C*(max(X,Y)-min(X,Y))

#片方を全部Cで買うとき
if X > Y:
    b = 2*C*Y + (X-Y)*A
elif Y > X:
    b = 2*C*X + (Y-X)*B
else:
    b = a
    
#全部AとBで買うとき
c = A*X + B*Y

print(min(a,b,c)) 

Measured memory_bytes: 9176
#include <iostream>
#include <stdlib.h>
#include <math.h>
using namespace std;

int compare_int(const void *a, const void *b)
{
    return *(int*)b - *(int*)a;
}

int max(int n1, int n2, int n3){

    int max = n1;
    if( max < n2 ) {
        max = n2;
    }
    if( max < n3 ) {
        max = n3;
    }

    return max;
}

int main(void){
    
    int N;
    cin >> N;
    int  L[N];
    for(int i=0; i<N; i++){
        cin >> L[i];
    }
    qsort(L, N, sizeof(int), compare_int);
    int 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[i] >= L[j]+L[k]){
                    break;
                }
                ans++;
            }
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  long long n,i,sa=0,s=0,a[10010],b[10010];
  scanf("%lld",&n);
  for(i=0;i<n;i++)scanf("%lld",&a[i]);
  for(i=0;i<n;i++)scanf("%lld",&b[i]);
  for(i=0;i<n;i++){
    if(a[i]>b[i])sa+=(a[i]-b[i])*2;
    else{
      if(a[i]%2-b[i]%2){
	sa+=2;
	b[i]++;
      }
      s+=b[i]-a[i];
    }
  }
  printf("%s\n",sa>s?"No":"Yes");
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
using namespace std; 

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

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

  int A[100000];
  for(int i=0;i<n;i++){
    cin>>A[i];
  }
  vector<ll>dp(n,INF);
  dp[0]=0;

  for(int i=1;i<n;i++){
    for(int j=1;j<=k;j++){
      if(i-j>=0){
      dp[i]=min(dp[i],dp[i-j]+abs(A[i]-A[i-j]));
      }
    }
  }
  cout<<dp.back()<<endl;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
struct edge{int to,nxt;}e[200005];
int n,m,et,rx,rt,head[100005],fa[100005],a[100005],tot,b[100005],r;
inline void adde(int x,int y) {e[++tot]=(edge){y,head[x]},head[x]=tot;}
inline int getf(int x) {return fa[x]==x?x:fa[x]=getf(fa[x]);}
inline void dfs(int x,int fl,int f=0)
{
	a[x]=fl,fa[x]=f;
	for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=f) dfs(e[i].to,-fl,x),a[x]+=a[e[i].to];
}
int main()
{
	scanf("%d%d",&n,&m),et=0,rt=1,memset(head,0,sizeof(head));
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1,x,y;i<=m;i++) {scanf("%d%d",&x,&y);if(getf(x)!=getf(y)) adde(x,y),adde(y,x),fa[getf(x)]=getf(y);else rt=x,rx=y;}
	memset(a,0,sizeof(a)),fa[rt]=0,dfs(rt,1),tot=0,r=0;
	if(n!=m) {if(a[rt]) return puts("-1"),0;}
	else
	{
		for(int x=rx;x;x=fa[x]) b[++tot]=a[x];
		if(tot&1)
		{
			if(a[rt]&1) return puts("-1"),0;
			for(int x=rx;x;x=fa[x]) a[x]-=(a[rt]>>1);
		}
		else
		{
			if(a[rt]) return puts("-1"),0;
			sort(b+1,b+tot+1);
			for(int x=rx;x;x=fa[x]) a[x]-=b[tot>>1];
		}
	}
	for(int i=1;i<=n;i++) r+=abs(a[i]);
	return printf("%d\n",r),0;
}

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

int main(){
    int a,b,c;
    cin>>a;
    cin>>b;
    cin>>c;
    int x = abs(a-b);
    int y = abs(a-c);
    int z = abs(b-c);
    vector<int> data = {x,y,z};
    sort(data.begin(),data.end(),greater<int>());
    int result = data[1]+data[2];
    cout<<result<<endl;
}

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

memo = [0 for i in range(n+1)]


def luca(i):
    if i == 0:
        memo[i] = 2
        return memo[i]
    if i == 1:
        memo[i] = 1
        return memo[i]
    if memo[i] != 0:
        return memo[i]
    memo[i] = luca(i-1) + luca(i-2)
    return memo[i]


print(luca(n))


Measured memory_bytes: 3060
#include <stdio.h>

int main(void) {
	int n;
	int s[14] = {};
	int h[14] = {};
	int c[14] = {};
	int d[14] = {};
	scanf("%d",&n);
	for(int i = 0; i < n*2; i++){
		char tempc;
		int tempn;
		scanf("%c%d",&tempc,&tempn);
		switch(tempc){
			case 'S':
			s[tempn]++;
			break;
			case 'H':
			h[tempn]++;
			break;
			case 'C':
			c[tempn]++;
			break;
			case 'D':
			d[tempn]++;
			break;
		}
	}
	for(int i = 1; i < 14; i++)if(!s[i])printf("S %d\n",i);
	for(int i = 1; i < 14; i++)if(!h[i])printf("H %d\n",i);
	for(int i = 1; i < 14; i++)if(!c[i])printf("C %d\n",i);
	for(int i = 1; i < 14; i++)if(!d[i])printf("D %d\n",i);
	return 0;
}


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

using namespace std;

void solver()
{
	int n;
	cin >> n;
	vector<vector<int>> A(n, vector<int>(n - 1));
	vector<int> prg(n, 0);
	vector<int> updatedplr(n);
	int dayc = 0;
	int mc = 0;
	int mn = (n * (n - 1)) / 2;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n - 1; j++) {
			cin >> A[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		updatedplr[i] = i;
	}
	
	while (mn != mc){
		vector<bool> mflag(A.size(), false);
		vector<int> tmp;
		bool zflag = true;
		for (int j = 0; j < updatedplr.size(); j++) {
			int plr = updatedplr[j];
			if (prg[plr] < A[plr].size()) {
				int epr = A[plr][prg[plr]] - 1;
				if (plr == A[epr][prg[epr]] - 1 && !mflag[plr] && !mflag[epr]) {
					prg[plr]++;
					prg[epr]++;
					mflag[plr] = true;
					mflag[epr] = true;
					mc++;
					tmp.push_back(epr);
					tmp.push_back(plr);
					zflag = false;
				}
			}
		}
		if (zflag) {
			cout << -1 << endl;
			return;
		}
		updatedplr = tmp;
		dayc++;
	}

	cout << dayc << endl;

}

int main(void)
{
	solver();

	return 0;
}

Measured memory_bytes: 4224
#include<bits/stdc++.h>
using namespace std;
typedef signed long long int ll;
ll inf=1000000007;



const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}



int main(){
    string s;
    cin>>s;
    
    int n;
    n=(int)s.size();
    
    ll dp[100010][4]={};
    dp[n][3]=1;
    //for(int i=0;i<3;i++) dp[n][i]=0;
    for(int i=n-1;i>=0;i--){
        
        //char c=s[i];
        
        /*for(int j=3;j>=0;j--){
            if(i==n){
                dp[i][j] = (j == 3 ? 1 : 0);
                //if(j==3) dp[i][j]=1;
                //else dp[i][j]=0;
            }else{
                
                dp[i][j]=dp[i+1][j]*(s[i] =='?' ? 3 : 1);
                if(j < 3 && (s[i] == '?' || s[i] == "ABC"[j])){
                        dp[i][j] += dp[i+1][j+1];

                }
                dp[i][j]%=inf;
            
            }
        
        }*/
            if(s[i]=='?'){
            //j=3
            //何を書くかで三通り
            dp[i][3]=3*dp[i+1][3];
            
            //j=2
            //?にA,B,Cを入れて丸しない
            dp[i][2]=3*dp[i+1][2]+dp[i+1][3];
            //cを入れて丸
            //dp[i][2]+=dp[i+1][3];
            
            //j=1
            //A,B,Cで丸しない
            dp[i][1]=3*dp[i+1][1]+dp[i+1][2];
            //Bで丸
            //dp[i][1]+=dp[i+1][2];
            
            //j=0
            //丸しない
            dp[i][0]=3*dp[i+1][0]+dp[i+1][1];
            //Aで丸
            //dp[i][0]+=dp[i+1][1];
            }else if(s[i]=='C'){
            //j=3
            dp[i][3]=dp[i+1][3];
            //j=2
            //丸をするかしないか
            dp[i][2]=dp[i+1][2]+dp[i+1][3];
            //j=1
            dp[i][1]=dp[i+1][1];
            //j=0;
            dp[i][0]=dp[i+1][0];
            }else if(s[i]=='B'){
            //j=3
            dp[i][3]=dp[i+1][3];
            //j=2
            dp[i][2]=dp[i+1][2];
            //j=1
            dp[i][1]=dp[i+1][1]+dp[i+1][2];
            
            dp[i][0]=dp[i+1][0];
            
            }else if(s[i]=='A'){
            //j=3
            dp[i][3]=dp[i+1][3];
            //j=2
            dp[i][2]=dp[i+1][2];
            
            dp[i][1]=dp[i+1][1];
            
            dp[i][0]=dp[i+1][0]+dp[i+1][1];
            }
        
        
        dp[i][0]%=inf;
        dp[i][1]%=inf;
        dp[i][2]%=inf;
        dp[i][3]%=inf;
    }
    
    cout<<dp[0][0]<<endl;
    
    
    return 0;
}


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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);  
	long long ans = 0;
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	for(int i = 0; i < n - 1; i++) {
		ans += a[i];
	}
	ans += a.back() / 2;
	cout << ans << endl;
	return 0;	
	
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
using namespace std;

typedef long long ll;
typedef double db;
typedef long double ldb;

template<class T> inline void checkmin(T &a,const T &b){if(b<a) a=b;}
template<class T> inline void checkmax(T &a,const T &b){if(b>a) a=b;}

const int inf=1e9+10;
const int maxn=1e5+10;

ll dpin[maxn],dpout[maxn],mod;
int n,father[maxn];
vector <int> g[maxn];

void dfs1(int x,int fa){
	father[x]=fa;
	ll ret=1ll;
	for(int i=0;i<g[x].size();i++){
		int to=g[x][i];
		if(to==fa) continue;
		dfs1(to,x);
		ret=(ret*dpin[to])%mod;
	}
	dpin[x]=(ret+1)%mod;
}

void dfs2(int x,int fa){
	vector <ll> v1,v2;
	for(int i=0;i<g[x].size();i++){
		int to=g[x][i];
		if(to==fa) v1.pb(1ll),v2.pb(1ll);
		else v1.pb(dpin[to]),v2.pb(dpin[to]);
	}
	for(int i=1;i<v1.size();i++) v1[i]=(v1[i-1]*v1[i])%mod;
	for(int i=v2.size()-2;i>=0;i--) v2[i]=(v2[i+1]*v2[i])%mod;
	for(int i=0;i<g[x].size();i++){
		int to=g[x][i];
		if(to==fa) continue;
		ll ret=1;
		if(i>0) ret=(ret*v1[i-1])%mod;
		if(i<v2.size()-1) ret=(ret*v2[i+1])%mod;
		ret=(ret*dpout[x])%mod;
		ret=(ret+1)%mod;
		dpout[to]=ret;
		dfs2(to,x);
	}
}

int main(){
	scanf("%d%d",&n,&mod);
	for(int i=0;i<n-1;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		u--; v--;
		g[u].pb(v); g[v].pb(u);
	}
	dfs1(0,-1);
	dpout[0]=1ll; dfs2(0,-1);
	for(int i=0;i<n;i++){
		ll ans=dpout[i];
		for(int j=0;j<g[i].size();j++){
			int to=g[i][j];
			if(to==father[i]) continue;
			ans=(ans*dpin[to])%mod;
		}
		printf("%d\n",ans);
	}
	return 0;
}


Measured memory_bytes: 24704
#include "bits/stdc++.h"
using namespace std;
 
////////////// Prewritten code follows. Look down for solution. ////////////////

#define fs first
#define sc second
#define pb push_back
#define len(x) ((int)(x).size())
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

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

const ll LINF = 1e18;
const int INF = 1e9;
const int MOD = 1e9+7;

/// command for char arrays with spaces -> scanf(" %[^\n]", text);
 
////////////////////////// Solution starts below. //////////////////////////////

int main(){
  fastio;
	int n;
	cin >> n;
	vector<ll> a(n+1), b(n+1), c(n+1);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	for(int i = 1; i <= n; i++){
		cin >> b[i];
	}
	for(int i = 1; i < n; i++){
		cin >> c[i];
	}
	ll p = 0;
	for(int i = 1; i <= n; i++){
		p += b[a[i]];
		if(i > 1){
			if(a[i] == a[i-1]+1){
				p += c[a[i-1]];
			}
		}
	}
	cout << p << endl;
	return 0;
}

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

int cmpnum(const void *n1,const void *n2){
  if(*(int *)n1 > *(int *)n2)
    return -1;	
  else if (*(int *)n1 < *(int *)n2)
    return 1;
  else
    return 0;
}

int main(){
  int x,n;
  int sa = 1000,min,minnum,right,left;
  int i,f1=0,f2=0;
  scanf("%d %d",&x,&n);
  if(n==0){
    printf("%d",x);
    exit(0);
  }
  int p[n];
  for(i=0;i<n;i++)
    scanf("%d",&p[i]);
  qsort(p,sizeof(p)/sizeof(p[0]),sizeof(int),cmpnum); //降順に並べ替える
  //printf("%d %d %d %d\n",p[0],p[1],p[2],p[3]);
  
  for(i=0;i<n;i++){
    if(abs(x-p[i]) <= sa){
      min=p[i];
      minnum=i;
      sa=abs(x-p[i]);
    }
  }
  //printf("min:%d minnum:%d\n",min,minnum);
  for(i=0;i<n-minnum;i++){
    //printf("r  %d %d\n",p[minnum+i],p[minnum]-i);
    if(p[minnum+i] != p[minnum]-i){
      right = p[minnum]-i;
      f1++;
      i=n-minnum-1;
    }
  }
  if(f1==0)
    right=p[n-1]-1;
  for(i=0;i<minnum+1;i++){
    //printf("l  %d %d\n",p[minnum-i],p[minnum]+i);
    if(p[minnum-i] != p[minnum]+i){
      left = p[minnum]+i;
      f2++;
      i=minnum;
    }
  }
  if(f2==0)
    left=p[0]+1;
  //printf("l:%d r:%d\n",left,right);
  if(abs(x-right) > abs(x-left))
    printf("%d",left);
  else if(abs(x-right) == abs(x-left))
    printf("%d",right);
  else
    printf("%d",right);
}

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


int main() {
    int a,b,c;
    cin>>a>>b>>c;
    cout<<c<<" "<<a<<" "<<b<<endl;
    return 0;
}



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

using namespace std;

int main(int argc, char*argv[]) {
  int n;
  cin >> n;
  vector<long long> a (n, 0);    
  for(int i=0; i<n; i++) {
    cin >> a[i];
    a[i] -= (i+1);
  }

  sort(a.begin(), a.end());
  long long min = a[0];
  
  long long sum = 0;
  for(int i=0; i<n; i++) {
    a[i] -= min;
    sum += a[i];
  }
  
  long long best = sum;
  
  long long offset = 0;
  for(int i=0; i<n; i++) {
    if(a[i] > offset) {
      sum -= (n - i) * (a[i] - offset);
      sum += i * (a[i] - offset);
      offset = a[i];
      best = std::min(best, sum);
    }
  }
  cout << best << endl;
  return 0;
}

Measured memory_bytes: 1792
//07
#include<iostream>

using namespace std;

int main(){
  int n;
  cin>>n;
  while(n--){
    int x,y,w,h;
    cin>>x>>y>>w>>h;
    int nn;
    cin>>nn;
    int ans=0;
    while(nn--){
      int xx,yy;
      cin>>xx>>yy;
      ans+=x<=xx&&xx<=x+w&&y<=yy&&yy<=y+h;
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 1160
object Main extends App {
  val input1 = readLine
  val input2 = readLine
  val N = input1
  val d_i = input2.split(" ").map(_.toInt)
  val s = d_i.sum
  val result = d_i.foldLeft(0)((l, r) => l + (s - r) * r) / 2
  println(result)
}


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

int main() {
	int n, a;
	int max_e = 0, max_o = 0, sec_e = 0, sec_o = 0;

	int e, o, e2, o2;
	cin >> n;
	map<int ,int> even, odd;
	for (int i = 1; i <= n; i++) {
		cin >> a;
		if (i % 2)odd[a]++;
		else even[a]++;
	}
	for (pair<int,int> p :even) {
		if (max_e < p.second)max_e = p.second,e = p.first;

	}
	for (pair<int, int> p : even) {
		if (p.first == e)continue;
		if (sec_e < p.second)sec_e = p.second, e2 = p.first;

	}

	for (pair<int, int> p : odd) {
		if (max_o < p.second)max_o = p.second, o = p.first;
	}
	for (pair<int, int> p : odd) {
		if (p.first == o)continue;
		if (sec_o < p.second)sec_o = p.second, o2 = p.first;
	}

	if(e != o)cout << ((n / 2) - max_e) + ((n + 1) / 2 - max_o) << endl;
	else {
		cout << min((((n / 2) - sec_e) + ((n + 1) / 2 - max_o)),
			(((n / 2) - max_e) + ((n + 1) / 2 - sec_o))) << endl;
	}
}


Measured memory_bytes: 4992
using System;

public class Hello
{
    public static void Main()
    {
        var p = new string[] { "lunch", "dinner", "midnight" };
        while (true)
        {
            var n = int.Parse(Console.ReadLine().Trim());
            if (n == 0) break;
            var a = new int[3];
            var b = new int[3];
            for (int i = 0; i < n; i++)
            {
                string[] line = Console.ReadLine().Trim().Split(' ', ':');
                var h = int.Parse(line[0]);
                var m = int.Parse(line[1]);
                var m2 = int.Parse(line[2]);
                var t1 = 60 * h + m;
                var t2 = (m2 - m + 60) % 60;
                bool ok;
                ok = t2 <= 8 ? true : false;
                if (t1 >= 660 && t1 <= 899)
                {
                    b[0]++;
                    if (ok) a[0]++;
                }
                else if (t1 >= 1080 && t1 <= 1259)
                {
                    b[1]++;
                    if (ok) a[1]++;
                }
                else if ((t1 >= 1260 && t1 <= 1439) | (t1 >= 0 && t1 <= 119))
                {
                    b[2]++;
                    if (ok) a[2]++;
                }
            }
            for (int i = 0; i < 3; i++)
                if (b[i] == 0) Console.WriteLine("{0} no guest", p[i]);
                else Console.WriteLine("{0} {1}", p[i], a[i] * 100 / b[i]);
        }
    }
}


Measured memory_bytes: 15880
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  cin>>n;
  int e[n][n],g[n][n];
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cin>>e[i][j];
      g[i][j]=e[i][j];
    }
  }
  for(int k=0;k<n;k++)
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
	e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
  
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      if(e[i][j]!=g[i][j]){
	cout<<-1<<endl;
	return 0;
      }

  int ans=0;
  for(int i=0;i<n;i++) 
    for(int j=i;j<n;j++)
      ans+=e[i][j];
  
  //cout<<ans<<endl;
  
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      int flg=0;
      for(int k=0;k<n;k++){
	if(i==k||j==k) continue;
	if(e[i][j]==e[i][k]+e[k][j])
	  flg=1;
      }
      if(flg) ans-=e[i][j];
    }
  }
  cout<<ans<<endl;
  
  return 0;
}


Measured memory_bytes: 1664
all_cards = [[],[],[],[]]
for i in range(4):
	for j in range(13):
		all_cards[i].append(j+1)

n = int(raw_input())
for i in range(n):
	card = raw_input().split(" ")
	#print card
	if card[0] == "S":
		all_cards[0].remove(int(card[1]))
	elif card[0] == "H":
		all_cards[1].remove(int(card[1]))
	elif card[0] == "C":
		all_cards[2].remove(int(card[1]))
	else:
		all_cards[3].remove(int(card[1]))

for i in range(len(all_cards[0])):
	print("S {:}".format(all_cards[0][i]))
for i in range(len(all_cards[1])):
	print("H {:}".format(all_cards[1][i]))
for i in range(len(all_cards[2])):
	print("C {:}".format(all_cards[2][i]))
for i in range(len(all_cards[3])):
	print("D {:}".format(all_cards[3][i]))

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

t_old = 0
x_old = 0
y_old = 0

possible = True

for _ in range(N):
    t, x, y = list(map(int, input().split()))

    t_diff = t - t_old
    x_diff = x - x_old
    y_diff = y - y_old

    xy_diff = x_diff + y_diff

    checker = t_diff - xy_diff

    if (checker >= 0) & (checker % 2 == 0):
        pass

    else:
        possible = False
        break

    t_old = t
    x_old = x
    y_old = y

if possible:
    print("Yes")

else:
    print("No")


Measured memory_bytes: 3064
/*
 * main.cpp
 *
 *  Created on: 2018/04/26
 *      Author: mac
 */

#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>


using namespace std;

int main(){

	vector<string> cards(3);
	
	for(int i = 0;i < 3;i++){
		cin >> cards[i];
	}
	
	int turn = 0;
	
	while(true){
		if(cards[turn].empty()){
			cout << (char) ( 'A' + turn);
			break;
		}
		int next = cards[turn][0] - 'a';
		cards[turn].erase(0,1);
		turn = next;
	}
	
	
	
	
    return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0; (i)<(n); (i)++)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define ll long long
#define pp pair<int,int> 
#define v(T) vector<T>
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
const int INF = 1001001001;
//int 2×10の9乗
//vector<vector<int>> a(n, vector<int>(m));
  //rep(i,n) rep(j,m) cin >> a[i][j]; 
//cout << fixed << setprecision(10);
//int gcd(int x, int y){
  //if(y==0) return x;
  //return gcd(y, x%y);
//}
//sort小さい順(昇順)
 
int main(){
  int n;
  cin >> n;
  v(int) h(n);
  rep(i,n) cin >> h[i];
  int cnt2=0;
  rep(i,n){
    while(h[i]!=0){
      int cnt1=0;
      for(int j=i; j<n-1; j++){
        if(h[j+1]>=h[j]) cnt1++;
        else break;
      }
      for(int j=i; j<=i+cnt1; j++) h[j]--;
      cnt2++;
    }
  }
  cout << cnt2 << endl; 
}    

Measured memory_bytes: 256
D, G = map(int, input().split())
P = []
C = []
ans = 10 ** 9
for i in range(D):
    p, c = map(int, input().split())
    P.append(p)
    C.append(c)

for i in range(2 ** D):
    a = 0
    b = 0
    for j in range(D):
        if (i >> j) & 1 :
            a += 100 * P[j] * (j + 1) + C[j]
            b += P[j]
    for k in range(D - 1, -1, -1):
        if (i >> k) & 1:
            continue
        if a >= G:
            break
        for l in range(P[k]):
            a += 100 * (k + 1)
            b += 1
            if a >= G:
                break
    ans = min(ans, b)
print(ans)

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

int main() {
  string s;
  cin >> s;
  rep(i, 3) {
    if (s[i] == s[i+1]) {
      cout << "Bad" << endl;
      return 0;
    }
  }
  cout << "Good" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, x)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
int lcm(int a, int b) { return a * b / gcd(a, b); }

int main(void)
{
    string abc = "ABC";
    string num = "";
    cin >> num;
    abc += num;
    cout << abc << endl;
    return 0;
}

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

#include <cstdio>
#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>
#include <cassert>
#include <iomanip>
#include <set>
/*多倍長整数/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 printim(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.0)//等差数列の和、初項,末項,項数
#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);}
#define nopf(T) [](T a){return a;}


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 && c != ' ') {
		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) {
	return number1 / gcd(number1, number2) * number2;
}

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

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



int main() {

	int n, k;
	scanf("%d%d", &n, &k);
	printf("%d\n", (--n + --k - 1) / k);

	Please AC;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String t = sc.nextLine();
        sc.close();
        char[] sChar = s.toCharArray();
        char[] tChar = t.toCharArray();

        int count = 0;
        for(int i = 0; i < 3; i++){
            if(sChar[i]==tChar[i]){
                count++;
            }
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 21844
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007LL
#define llMAX 9223372036854775807LL
#define llMIN -9223372036854775808LL
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける


//BFS
vector<vector<pair<int,int>>> g;
const int N = 3e6;
int used[N];

ll k,n;

void bfs(int i){
  used[i] = 0;
  queue<int> que;
  queue<int> que_big;
  que.push(i);
  int id;
  //col[i] = c;
  for(ll iii=0;iii<1000000;iii++){
    
    while (!que.empty()) {
        //cout << que.front() << " "; // 先頭要素を参照する
        id=que.front();
        int lootlen=used[id];
        for(auto to : g[id]) {
          if (to.second==k){
            if (lootlen==0)continue;
            ll newlen=((lootlen-1)/k)*k+k;
            if (used[to.first]>newlen){
              que_big.push(to.first);
              used[to.first]=newlen;
            }
          }else{
            if (used[to.first]>lootlen+1){
              if ((lootlen+1)%k!=0){
                que.push(to.first);
                used[to.first]=lootlen+1;
              }else{
                que_big.push(to.first);
                used[to.first]=lootlen+1;
                ll nid=(to.first+n)%(2*n);
                if (used[nid]>lootlen+1){
                  que_big.push(nid);
                  used[nid]=lootlen+1;
                }
              }
            }
          }
        }
        que.pop(); // 先頭要素を削除
    }

    if (que_big.empty()){
      break;
    }else{
      while (!que_big.empty())
      {
        que.push(que_big.front());
        que_big.pop();
      }
    }

  }


  return;
}







int main(){
  
  REP(ii,N){
    used[ii]=2100000000;
  }

  ll h,w,x1,x2,y2,y1;
  ll ans=0;
  cin>>h>>w>>k;
  n=h*w;
  cin>>x1>>y1>>x2>>y2;
  x1--;
  y1--;
  x2--;
  y2--;

  vvi data(w, vi(h));  // N * M の2次元配列
  g.resize(n*3+100);
  for(ll i=0;i<h;i++){
    string s;
    cin>>s;
    for(ll j=0;j<w;j++){
      if (s[j]!='.')data[j][i]=1;
    }
  }


  for(ll j=0;j<h;j++){
    for(ll i=0;i<w;i++){
      ll a,b,c,an,bn;
      a=j*w+i;
      an=j*w+i+n;

      if (i!=w-1)
      {
        b=j*w+i+1;
        if (data[i+1][j]==0){
          g[a].emplace_back(b, 0);
        }
      }
      
      if (i!=0)
      {
        b=j*w+i-1;
        if (data[i-1][j]==0){
          g[a].emplace_back(b, 0);
        }
      }

      if (j!=h-1)
      {
        bn=(j+1)*w+i+n;
        if (data[i][j+1]==0){
          g[an].emplace_back(bn, 0);
        }
      }
      
      if (j!=0)
      {
        bn=(j-1)*w+i+n;
        if (data[i][j-1]==0){
          g[an].emplace_back(bn, 0);
        }
      }

      g[a].emplace_back(an, k);
      g[an].emplace_back(a, k);


    }
  }


  bfs(x1*w+y1);
  bfs(x1*w+y1+n);
  
  ans=min(used[x2*w+y2],used[x2*w+y2+n]);
  //cout<<ans<<endl;
  if (ans==2100000000){
    cout<<-1<<endl;
    return 0;
  }else{
    ans=(ans-1)/k+1;
  }

  cout<<ans<<endl;
  return 0;
  //2100000000


}

Measured memory_bytes: 217872
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 2010;
int a[maxn], n, z, w;
int main(void) {
    while(~scanf("%d%d%d", &n, &z, &w)) {
        for(int i = 0; i < n; ++i)
            scanf("%d", a + i);
        if(n == 1) {
            printf("%d\n", abs(a[0] - w));
            continue;
        }
        printf("%d\n", max(abs(a[n - 2] - a[n - 1]), abs(a[n - 1] - w)));
    }
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("unroll-loops") 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#define int long long
#define fr(i,a,b) for(int i = a ; i <= b ; ++i)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define pb push_back
#define fst first
#define snd second
using namespace __gnu_pbds;
using ordered_set =
 tree<int, null_type,less<int>,
 rb_tree_tag,tree_order_statistics_node_update>;
//find_by_order(k):returns iterator to kth element starting from 0
//order_of_key(k):returns count of elements strictly smaller than k
typedef long long ll;typedef pair<int, int> pii;
typedef vector<int> vi;typedef long double ld;
template<class T>
using min_heap = priority_queue<T,vector<T>,greater<T>>; 
template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
template<typename T> T lcm(T a, T b){return(a*(b/gcd(a,b)));}
template<typename T> 
void remdup(vector<T>& v) {
	sort(all(v)); v.erase(unique(all(v)), v.end());
}
template<typename T> void re(vector<T> &v) {trav(i,v) cin >> i;}
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
#ifdef np
#include "C:\Users\navodit\Desktop\mycodes\pr.h"
#else
#define trace(...)
#endif

#define MOD 1000000007  





void solve(){
	int h ;
	cin >> h ;
	int cnt = 0 , cur = 1 ;
	while(h){
		h/=2;
		cnt+=cur;
		cur*=2;
	}
	cout << cnt << endl;
}

signed main() {
	unsyncIO();
	int tt =1 ;
	// cin >> tt;
	rep(i,0,tt) solve();













#ifdef np
	cout <<endl<<endl<< "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}


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

long min(int b,int e, long* A);
long max(int b,int e, long* A);

int main(void){
  int n,q;
  int com,b,e;
  cin>>n;
  long A[n];
  for(int i=0;i<n;i++){
    cin>>A[i];
  }
  cin>>q;
  for(int i=0;i<q;i++){
    cin>>com>>b>>e;
    if(com==0){
      cout<<min(b,e,A)<<endl;
    }
    else{
      cout<<max(b,e,A)<<endl;
    }
  }
  return 0;
}


long min(int b,int e,long* A){
  long retval=1000000010;
  for(int i=b;i<e;i++){
    if(retval>A[i]){
      retval=A[i];
    }
  }
  return retval;
}

long max(int b,int e,long* A){
  long retval=-1000000010;
  for(int i=b;i<e;i++){
    if(retval<A[i]){
      retval=A[i];
    }
  }
  return retval;
}



Measured memory_bytes: 3112
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
//ll mod = 998244353;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main() {
    int n;
    ll t;
    cin >> n >> t;
    ll now = 0;
    vector<ll> tnum(n);
    rep(i, n) cin >> tnum[i];
    now = tnum[0] + t;
    ll ans = now;
    for (int i = 1; i < n; ++i) {
        if (tnum[i] > now) {
            ans += t;
            now = tnum[i] + t;
        }
        else {
            ans += t - (now - tnum[i]);
            now += t - (now - tnum[i]);
        }
        // cout << now << " " << ans << endl;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4740
#include<bits/stdc++.h>
using namespace std;
int takahashi;
string S;
main(){
  cin>>S;
  for(int i=0;i<S.size();++i){
    if(S[i]=='+'){
      ++takahashi;
    }else if(S[i]=='-'){
      --takahashi;
    }else{
      assert(false);
    }
  }
  cout<<takahashi<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>;
using namespace std;
int main(){
  int n;
  cin >> n;
  int nums[n];
  for(int i = 0; i < n;i ++) cin >> nums[i];
  int cnt = 0;
  for(int i = 1; i < n - 1; i++){
    if(!(nums[i] < nums[i + 1] && nums[i] < nums[i - 1]) && !(nums[i] > nums[i + 1] && nums[i] > nums[i - 1])) cnt++;
  }
  cout << cnt;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using static System.Console;
using static System.Math;
using static MyIO;
using static MyUtil;

public class C { public static void Main() => (new Solver()).Solve(); }

public class Solver
{
	public void Solve()
	{
		long N = GetLong();
		var A = GetLongs(N + 1);

		var rest = A.Sum() - 1;
		var cnt = new long[N + 1];
		cnt[0] = 1;
		for(long i = 0; i < N; i++)
		{
			if(cnt[i] < A[i])
			{
				WriteLine(-1);
				return;
			}
			var next = Max(0, cnt[i] - A[i]);
			var branch = Min(rest, next);
			cnt[i + 1] = 2 * branch + (next - branch);
			rest -= branch;
		}
		if(cnt[N] != A[N])
		{
			WriteLine(-1);
			return;
		}
		WriteLine(cnt.Sum());
	}
}

public static class MyIO
{
	private static string[] args = new string[0];
	private static int cnt = 0;
	private static IEnumerable<string> getArgs(long N) => Range(0, N).Select(_ => getArg());
	private static string getArg()
	{
		if(cnt == args.Length) { args = Console.ReadLine().Split(); cnt = 0; }
		return args[cnt++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static decimal GetDecimal() => decimal.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(long N) => getArgs(N).Select(int.Parse).ToArray();
	public static long[] GetLongs(long N) => getArgs(N).Select(long.Parse).ToArray();
	public static double[] GetDoubles(long N) => getArgs(N).Select(double.Parse).ToArray();
	public static decimal[] GetDecimals(long N) => getArgs(N).Select(decimal.Parse).ToArray();
	public static string[] GetStrings(long N) => getArgs(N).ToArray();
}

public static class MyUtil
{
	public static void chmax<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) < 0) x = y; }
	public static void chmin<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) > 0)	x = y; }
	public static void swap<T>(ref T x, ref T y) { T tmp = x; x = y; y = tmp; }
	public static long rightShift(long x, long y) => (x >> (int)y);
	public static long leftShift(long x, long y) => (x << (int)y);
	public static bool contains(long s, long x) => (rightShift(s, x) & 1L) == 1L;
	public static long gcd(long x, long y) => (y == 0) ? x : gcd(y, x % y);
	public static long lcm(long x, long y) => (x / gcd(x,y)) * y;	
	public static IEnumerable<int> Range(long start, long count) => Enumerable.Range((int)start, (int)count);
	public static void Sort(this List<string> source) => source.Sort(StringComparer.Ordinal);
}


Measured memory_bytes: 38308
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,m,ans=0;
    cin >> n >> m;
    vector<vector<int>> sw(m);
    for(int i=0;i<m;i++){
        int k;
        cin >> k;
        for(int j=0;j<k;j++){
            int d;
            cin >> d;
            d--;
            sw[i].push_back(d);
        }
    }
    int p[m];
    for(int i=0;i<m;i++) cin >> p[i];
    for(int i=0;i<(1<<n);i++){//スイッチを総当たり
        bitset<10> s(i);
        bool AllLight = 1;
        for(int j=0;j<m;j++){//電球の点灯判定
            int cnt = 0;//何個スイッチオンか
            for(auto k:sw[j]){
                if(s.test(k)) cnt++;
            }
            if(cnt%2!=p[j]) AllLight=0;
        }
        if(AllLight) ans++;
    }
    cout << ans << endl; 
}


Measured memory_bytes: 3660
#include<stdio.h>
#define MAX 100000
#define SENTINEL 2000000000

struct Card {
    char suit;
    int value;
    int id;
};

int partition(struct Card A[], int n, int p, int r){
    int i,j;
    struct Card t,x;
    x = A[r];
    i = p-1;
    for (j = p;j<r;j++){
        if (A[j].value <= x.value){
            i++;
            t = A[i]; A[i] = A[j]; A[j] = t;
        }
    }
    t = A[i+1]; A[i+1] = A[r]; A[r] = t;
    return i+1;
}

void quickSort(struct Card A[], int n, int p, int r){
    int q;
    if (p<r){
        q = partition(A, n, p, r);
        quickSort(A, n, p, q-1);
        quickSort(A, n, q+1, r);
    }
}

int main(){
    int n, i, v;
    struct Card A[MAX];
    char S[10];
    int stable = 1;

    scanf("%d", &n);

    for (i=0;i<n;i++){
        scanf("%s %d", S, &v);
        A[i].suit = S[0];
        A[i].value = v;
        A[i].id = i;
    }

    quickSort(A, n, 0, n-1);

    for (i=0;i<n;i++){
        if (A[i-1].value == A[i].value && A[i-1].id > A[i].id){
            stable = 0;
            break;
        }
    }

    if (stable == 1) printf("Stable\n");
    else printf("Not stable\n");
    for (i=0;i<n;i++){
        printf("%c %d\n", A[i].suit, A[i].value);
    }

    return 0;
}


Measured memory_bytes: 2888
N, W = map(int, input().split())

w = [0] * N
v = [0] * N

for i in range(N):
    w[i], v[i] = map(int, input().split())

INF = 10**13 

V = (10**5)+1
# dp[n][v] = n番目までで価値vとなる最小の重さ
dp = [INF] * V
dp[0] = 0
for i in range(N):
    for j in reversed(range(0, V)):
        if (j - v[i] >= 0):
            dp[j] = min(dp[j], dp[j - v[i]] + w[i])

ans = 0
for j in range(V):
    if dp[j] <= W:
        ans = max(ans, j)

print(ans)


Measured memory_bytes: 74436
import java.util.*;

public class Main {
    private static final Scanner scn = new Scanner(System.in);
    
    public static void main(String[] args) {
        int[] ary = {scn.nextInt(), scn.nextInt(), scn.nextInt()};
        Arrays.sort(ary);
        System.out.println(ary[0] + " " + ary[1] + " " + ary[2]);
    }
}

Measured memory_bytes: 26192
# Author: cr4zjh0bp
# Created: Sat Mar 28 10:36:41 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

o = ns()
e = ns()

s = []
i = 0
for i, j in zip(o, e):
    s.append(i)
    s.append(j)

if len(o) > len(e):
    s.append(o[-1])
elif len(e) > len(o):
    s.append(e[-1])

print(*s, sep="")

Measured memory_bytes: 3064