akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define X first
#define Y second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
template<class T> using vv=vector<vector<T>>;
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=1e9+7;

int K;
int mind[114514];
priority_queue<pii, vector<pii>, greater<pii>> que;

int main() {
  scanf("%d", &K);  
  fill(mind, mind+K, MOD);
  
  mind[1] = 1;
  que.push(pii(1, 1));
  while (!que.empty()) {
    auto p = que.top(); que.pop();
    int c = p.X;
    int v = p.Y;
    if (mind[v] < c) continue;

    int u;
    u = (v+1)%K;
    if (mind[u] > mind[v]+1) {
      mind[u] = mind[v]+1;
      que.push(pii(mind[u], u));
    }

    u = (v*10)%K;
    if (mind[u] > mind[v]) {
      mind[u] = mind[v];
      que.push(pii(mind[u], u));
    }
  }
  printf("%d\n", mind[0]);
}



Measured memory_bytes: 1276
a = int(input())
b = int(input())
c = int(input())
x = int(input())

count = 0
result = 0
for aa in range(a+1):
    for bb in range(b+1):
        for cc in range(c+1):
            result = aa*500 + bb*100 + cc*50
            if result == x:
                count+=1

print(count)

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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define INF         INT_MAX/3
#define LLINF       LLONG_MAX/3
#define MOD         (1000000007LL)
#define MODA(a, b)  a=((a)+(b))%MOD
#define MODP(a, b)  a=((a)*(b))%MOD
#define inc(i, l, r)   for(int i=(l);i<(r);i++)
#define dec(i, l, r)   for(int i=(r)-1;i>=(l);i--)
#define pb          push_back
#define se          second
#define fi          first
#define mset(a, b)  memset(a, b, sizeof(a))

using LL  = long long;
using G   = vector<vector<int>>;

int di[] = {0, -1, 0, 1};
int dj[] = {1, 0, -1, 0};
// }}}

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    int n;cin >> n;
    map<int, int> cnt;
    set<LL> st;
    inc(i, 0, n){
        int a;cin >> a;
        st.insert(a);
        cnt[a]++;
    }
    vector<LL> v;
    for(auto a : st){
        if(cnt[a] < 2) continue;
        v.pb(a);
    }
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    int m = v.size();
    if(m == 0){
        cout << 0 << endl;
    }else if(m == 1){
        if(cnt[v[0]] >= 4){
            cout << v[0]*v[0] << endl;
        }else{
            cout << 0 << endl;
        }
    }else{
        if(cnt[v[0]] >= 4){
            cout << v[0]*v[0] << endl;
        }else{
            cout << v[0]*v[1] << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 9600
/*zhen hao*/
#include <bits/stdc++.h>
using namespace std;

#define lson l, m, rt*2
#define rson m + 1, r, rt*2+1
#define xx first
#define yy second

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;

int main() {
#ifdef JUDGE
  freopen("case.in", "r", stdin);
#endif
  int n, cnt = 0;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (x & 1) cnt++;
  }
  cnt & 1 ? puts("NO") : puts("YES");
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

typedef long long ll;

using namespace std;

int main() {
    int S;
    cin >> S;
    int h = S / 3600;
    int mod_h = S % 3600;
    int m = mod_h / 60;
    int s = mod_h % 60;
    cout << h  << ':' << m << ':' << s << endl;

    return 0;
}




Measured memory_bytes: 3092
# coding: utf-8

N,M = list(map(int,input().split()))

A = list(map(int,input().split()))

tmp = {}
for i in A:
    if i in tmp.keys():
        tmp[i] += 1
    else:
        tmp[i] = 1 

for i in range(M):
    B, C = list(map(int,input().split()))
    if C in tmp.keys():
        tmp[C] += B
    else:
        tmp[C] = B

ans = 0
for i in sorted(tmp.keys(), reverse = True):
    if N >= tmp[i]:
        N -= tmp[i]
        ans += i * tmp[i]
    else:
        ans += i * N
        break
print(ans)

Measured memory_bytes: 32064
INF = 10**9 + 1

def merge(a,left,mid,right)
  count = 0
  lSize = mid-left;
  rSize = right-mid;
  l = []
  r = []
  (0...lSize).each do |i|
    l[i] = a[left+i]
  end
  (0...rSize).each do |i|
    r[i] = a[mid+i]
  end
  l[lSize] = INF
  r[rSize] = INF
  i,j=0,0
  (left...right).each do |k|
    count += 1
    if l[i] <= r[j]
      a[k] = l[i]
      i += 1
    else 
      a[k] = r[j]
      j += 1
    end
  end
  return count
end

def mergeSort(a,left,right)
  count = 0
  if left+1 < right
    mid = (left+right)/2;
    count += mergeSort(a,left,mid)
    count += mergeSort(a,mid,right)
    count += merge(a,left,mid,right)
  end
  return count
end

n = gets.to_i
a = gets.split.map(&:to_i)
count = mergeSort(a,0,n)
printf("%s\n%d\n",a.join(" "),count)


Measured memory_bytes: 63200
#include <stdio.h>
#include <string.h>

int main(){
  char Sd[51],T[51],ans[51],anskari[51];
  ans[0]='\0';
  anskari[0]='\0';
  int Sdl,Tl,flag;
  scanf("%s",Sd);
  scanf("%s",T);
  Sdl=strlen(Sd);
  Tl=strlen(T);
  for(int i=0;i<Sdl-Tl+1;i++){
    flag=0;
    for(int j=0;j<Tl;j++){
      if(Sd[i+j]=='?'||Sd[i+j]==T[j]){
      }else{
	flag=1;
      }
    }
    if(flag==0){
      strcpy(anskari,Sd);
      for(int j=0;j<Sdl;j++){
	if(j>=i&&j<i+Tl){
  	  anskari[j]=T[j-i];
	}else if(anskari[j]=='?'){
	  anskari[j]='a';
	}
      }
      if(strcmp(anskari,ans)<0||ans[0]=='\0'){
	strcpy(ans,anskari);
      }
    }
  }
  if(ans[0]=='\0'){
    printf("UNRESTORABLE");
  }else{
    printf("%s",ans);
  }
  return 0;
}


Measured memory_bytes: 128
//agc021_a.cpp
//Sat Feb 24 20:59:22 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;

int main(){
	long x;
	cin >> x;

	long keta = 0;
	long temp = x;
	long unit = 1;
	while (temp!=0){
		temp /= 10;
		keta++;
		unit = unit * 10;
	}

	unit = unit/10;
	long answer;
	for (int i=0;i<10;i++){
		long temp = unit - 1 + unit*i;
		if (temp<=x){
			answer = 9*(keta-1)+i;
		}
	}

	cout << answer << endl;
}

Measured memory_bytes: 256
#![allow(
    non_snake_case,
    unused_variables,
    unused_assignments,
    unused_mut,
    unused_imports,
    dead_code
)]
//use proconio::fastout;
use proconio::input;
use proconio::marker::*;
use std::cmp::*;
use std::collections::*;
//use std::collections::VecDeque;

fn main() {
    input! {
       N:usize,
       XYP:[(i64,i64,i64);N]
    }
    // 各鉄道パターンについて、集落からの距離
    let inf = std::i64::MAX;
    let mut dtate = vec![vec![0i64; N]; 2i64.pow(N as u32) as usize];
    let mut dyoko = vec![vec![0i64; N]; 2i64.pow(N as u32) as usize];
    for i in 0..dtate.len() {
        //let l: Vec<bool> = format!("{:0>15b}", i).chars().map(|c| c == '1').collect();
        //let sum = l.iter().fold(0, |sum, &a| sum + if a { 1 } else { 0 });

        for j in 0..N {
            dtate[i][j] = XYP[j].0.abs();
            dyoko[i][j] = XYP[j].1.abs();
            for k in 0..N {
                if (i >> k) & 1 == 1 {
                    dtate[i][j] = min(dtate[i][j], (XYP[j].0 - XYP[k].0).abs());
                    dyoko[i][j] = min(dyoko[i][j], (XYP[j].1 - XYP[k].1).abs());
                }
            }
            dtate[i][j] *= XYP[j].2;
            dyoko[i][j] *= XYP[j].2;
        }
    }
    let mut ans = vec![std::i64::MAX; N + 1];
    for i in 0..(3usize.pow(N as u32)) {
        // i の j bit目が0なら、j番目の町に路線なし、1なら東西線、2なら南北線とする。
        // iから、dtate[x]とdyoko[y]のxとyを求める。
        let mut x = 0;
        let mut y = 0;
        let mut ii = i;
        let mut n = N;
        for j in 0..N {
            let tmp = ii % 3;
            // 順番がおかしくなるけど、全部合計するので気にしない。
            x *= 2;
            y *= 2;
            match tmp {
                1 => x += 1,
                2 => y += 1,
                _ => n -= 1,
            }
            ii /= 3;
        }
        let mut t = 0;
        for j in 0..N {
            t += min(dtate[x][j], dyoko[y][j]);
        }
        ans[n] = min(ans[n], t);
    }
    for i in 0..=N {
        println!("{}", ans[i]);
    }
}


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


int main() {
    int a[5],k;

    rep(i,5)cin>>a[i];
    cin>>k;

    bool flag = true;
    rep(i,5)rep(j,i){
        if(a[i]-a[j] > k)flag = false;
    }
    if(flag == true) cout<<"Yay!"<<endl;
    else cout<<":("<<endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define N 100005
#define mp make_pair
#define pb push_back
#define f first
#define se second
vector<int>adj[N];
vector<bool>vis(N,false);
int cnt=0;
bool prime[1000004];
void dfs(int v)
{   
    vis[v]=true;
    for(auto it:adj[v])
        if(!vis[it])
            dfs(it);
}
bool isPerfectSquare(long double x) 
{   
  // Find floating point value of  
  // square root of x. 
  long double sr = sqrt(x); 
  
  // If square root is an integer 
  return ((sr - floor(sr)) == 0); 
} 
void prime_check() 
{  
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=1000000; p++) 
    { 
        if (prime[p] == true) 
        {  
            for (int i=p*p; i<=1000000; i += p) 
                prime[i] = false; 
        } 
    } 
} 
int main()
{
  ll h,a;
  cin>>h>>a;
  if(h%a!=0)
    cout<<h/a+1;
  else
    cout<<h/a;
}

Measured memory_bytes: 2560
n = gets.to_i

a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)
c = gets.split.map(&:to_i)

ans = (0...n).inject(0) do |r, i|
  extra = a[i + 1] == a[i] + 1 ? c[a[i] - 1] : 0
  r + b[a[i] - 1] + extra
end

puts ans


Measured memory_bytes: 1788
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#include <numeric>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <functional>
#include <assert.h>
using ll=long long;
#define int ll
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define SZ(x) ((int)x.size())
#define fi first
#define se second
const int INF = 1e15;
using namespace std;

template<class T> using vc=vector<T>;
template<class T> using vvc=vc<vc<T>>;

using pi=pair<int,int>;
using vi=vc<int>;

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

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(20);

    static const double pi=3.141592653589793;
    double a,b,c,d; cin >> a >> b >> c >> d;
    double p=fabs(d*6.0-(c*30+d/2));
    if(p>180) p=360-p;
    cout << sqrt(a*a+b*b-2*a*b*cos(2*pi*p/360)) << endl;
}

Measured memory_bytes: 4252
#include <iostream>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <functional>
#include <map>
#include <set>
#define Rep(i, n) for(int i=0;i<n;++i)
#define rep(i, n) for(int i=1;i<=n;++i)
#define ll long long int
#define INF 100000000
#define INFLL 100000000000
#define MOD 1000000007
#define PI 3.14159265359
#define All(a) (a).begin(), (a).end()

using namespace std;
using P = pair<ll, ll>;
 
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

struct Edge {
  int to;     
  ll weight; 
  Edge(int t, ll w) : to(t), weight(w) { }
};



int H, W;
int A[100][100];
int B[100][100];
bool dp[100][100][15000];

int main () {
  cin >> H >> W;

  rep(i, H) {
    rep(j, W) {
      cin >> A[i][j];
    }
  }

  rep(i, H) {
    rep(j, W) {
      cin >> B[i][j];
    }
  }

  dp[1][1][abs(A[1][1] - B[1][1])] = true;

  rep(i, H) {
    rep(j, W) {
      if (i == 1 && j == 1) {
        continue;
      }

      if (i != 1) {
        Rep(k, 15000) {
          if (dp[i-1][j][k]) {
            dp[i][j][k + abs(A[i][j] - B[i][j])] = true;
            dp[i][j][abs(k - abs(A[i][j] - B[i][j]))] = true;
          }
        }
      }

      if (j != 1) {
        Rep(k, 15000) {
          if (dp[i][j-1][k]) {
            dp[i][j][k + abs(A[i][j] - B[i][j])] = true;
            dp[i][j][abs(k - abs(A[i][j] - B[i][j]))] = true;
          }
        }
      }
    }
  }

  Rep(k, 15000) {
    if (dp[H][W][k]) {
      cout << k << "\n";
      return 0;
    }
  }
}

Measured memory_bytes: 117248
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
import math
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    r = int(input())
    print(2 * r * math.pi)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()


Measured memory_bytes: 65432
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint mod = 1e9 + 7;
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzl(x))
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
lint power(lint base, lint exponent, lint module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ lint root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position mv[4] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); } string to_string(string x){ return x; }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++) ans += to_string(*i) + " "; if(!ans.empty()) ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<lint> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } lint C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };
template<class itr> bool next_sequence(itr first, itr last, int max_bound){ itr now = last; while(now != first){ now--; (*now)++; if((*now) == max_bound){ (*now) = 0; }else{ return true; } } return false; }

int main(){
    int N, M;
    cin >> N >> M;
    lint l = -1e9, r = 1e9;
    for(int i = 0; i < M; i++){
        lint L, R;
        cin >> L >> R;
        L--;
        l = max(l, L);
        r = min(r, R);
    }
    cout << max(0ll, r - l) << endl;
}


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

#define LL long long
#define ULL unsigned long long int
LL INF=1000000000000000001;
#define mx 100009
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<pii> vii;
typedef vector<pll> vll;

#define READ 	freopen("in.txt","r",stdin)
#define WRITE  	freopen("out.txt","w",stdout)
#define BOOST	ios_base::sync_with_stdio(false)


#define sf 	scanf
#define pf 	printf
#define F  	first
#define S  	second
#define pb 	push_back
#define NL	pf("\n")
#define si(x)		sf("%d",&x);
#define sii(x,y)	sf("%d%d",&x,&y);
#define siii(x,y,z)	sf("%d%d%d",&x,&y,&z);
#define sl(x)		sf("%lld",&x);
#define sll(x,y)	sf("%lld%lld",&x,&y);
#define slll(x,y,z)	sf("%lld%lld%lld",&x,&y,&z);
#define clr(x,y) 	memset(x,y,sizeof (x) )
#define ch 			printf("Came Here!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n")
#define SV(v)		sort(v.begin(),v.end())
#define SVR(v)		sort(v.begin(),v.end(),cmp)
#define FOR(i,n)	for(i=0;i<n;i++)
#define loop(i,s,n) for(i=s;i<n;i++)
#define rev(i,s,n)	for(i=n;i>=s;i--)
// graph direction array [4]
//LL X[4]={0,0,1,-1};
//LL Y[4]={1,-1,0,0};
// graph direction array [8]
//int X[8]={0,0,1,-1,-1,1,1,-1};
//int Y[8]={1,-1,0,0,-1,-1,1,1};
// comparison function for sort
//bool cmp( LL a,LL b ){
//	return a>b;
//}


// ------------------------------------------------------------
// POWER SET WITH BITMASK
//void powerSet(char *st, int set_size){
//
//    unsigned int pow_set_size = pow(2, set_size);
//    int counter, j,i;
//	vector<char> xxx;
//	for(counter = 0; counter < pow_set_size; counter++){
//		xxx.clear();
//		for(j = 0; j < set_size; j++){
//			if(counter & (1<<j))
//				xxx.pb( st[j] );
////				cout<<st[j];
//		}
//      NL;
//	}
//}



// ------------------------------------------------------------
// Big Mod
//#define mod 1000007
//LL bigMOd( LL a,LL p ){
//
//    if( p==0 )return 1%mod;
//    LL x = bigMOd( a,p/2 );
//    x = ((x%mod)*(x%mod))%mod;
//    if( p%2 ){
//        x = ((x%mod)*(a%mod))%mod;
//    }
//    return x;
//}

LL n,m;


int main(){

//	READ;WRITE;
//	BOOST;
    LL i,j,k,t,cs=0,q,r,c,x,d,u,v,a,b;
    cin>>i>>j;
    if( i%3==0 )cout<<"Possible";
    else if( j%3==0 )cout<<"Possible";
    else if( (i+j)%3==0 )cout<<"Possible";
    else cout<<"Impossible";
    NL;

//    main();
//    ch;
//    sl(t);
//    while(t--){
//        sl(n);
////        ch;
//    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
using namespace std;
int main() {
  
  int N;cin>>N;
  vector<int> vec(N);
  for(int i=0;i<N;i++){
    cin>>vec[i];
  }
  
  sort(vec.begin(),vec.end());
  
  int x=vec[(N-1)/2];
  int y=vec[(N-1)/2+1];
  
  int ans=-1;
  
  if(x==y){
    cout<<0<<endl;
  }
  else{
  for(int i=x;i<=y;i++){
    ans++;
  }
  cout<<ans<<endl;
  }
}

Measured memory_bytes: 3688
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
	long long A,V,B,W,T;
	scanf("%lld%lld%lld%lld%lld",&A,&V,&B,&W,&T);
	if (abs(A-B)>(V-W)*T)
	{
		printf("NO\n");
	} else printf("YES\n");
}

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

int main()
{
    int N;
    string A, B, C;
    int ans = 0;

    cin >> N >> A >> B >> C;

    for( int i = 0; i < N; ++i ){
        if( A[i] == B[i] && B[i] == C[i] ) continue;
        else if( A[i] == B[i] || A[i] == C[i] || B[i] == C[i] ) ans += 1;
        else ans += 2;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
H, W = map(int, input().split())
src = []
for i in range(H):
    src.append(list(input()))
L = [[0]*W for i in range(H)]
R = [[0]*W for i in range(H)]
U = [[0]*W for i in range(H)]
D = [[0]*W for i in range(H)]

for h in range(H):
    for w in range(W):
        if src[h][w] == '#':
            L[h][w] = 0
        elif w == 0:
            L[h][w] = 1
        else:
            L[h][w] += L[h][w-1] + 1

for h in range(H):
    for w in range(W)[::-1]:
        if src[h][w] == '#':
            R[h][w] = 0
        elif w == W - 1:
            R[h][w] = 1
        else:
            R[h][w] += R[h][w + 1] + 1

for w in range(W):
    for h in range(H):
        if src[h][w] == '#':
            U[h][w] = 0
        elif h == 0:
            U[h][w] = 1
        else:
            U[h][w] += U[h-1][w] + 1

for w in range(W):
    for h in range(H)[::-1]:
        if src[h][w] == '#':
            D[h][w] = 0
        elif h == H - 1:
            D[h][w] = 1
        else:
            D[h][w] += D[h+1][w] + 1

ans = 0
for i in range(H):
    for j in range(W):
        tmp = R[i][j] + L[i][j] + U[i][j] + D[i][j] - 3
        ans = max(ans, tmp)
print(ans)


Measured memory_bytes: 310536
#include "bits/stdc++.h"
#define int long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(obj) begin(obj), end(obj)
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define sqr(x) (x) * (x)
#define cube(x) (z) * (z) * (x)
#define LOWER_BOUND(A, key) distance(A.begin(), lower_bound(ALL(A), key))
#define UPPER_BOUND(A, key) distance(A.begin(), upper_bound(ALL(A), key))
#define itn int

using namespace std;
using ll      = long long;
const int MOD = (int)(1e9 + 7);
const int INF = (int)(1e13 + 7);

template <class T = int>
int in() {
  T x;
  cin >> x;
  return x;
}
unordered_map<int, int> element_num; //change type if you need
template <class T>
void counter(T container) {
  for (int i = 0; i < container.size(); i++) {
    element_num[container[i]] += 1;
  }
}
int bpm(int x, int y) {
  if (x == 0)
    return 0;
  else if (y == 0) {
    return 1;
  }
  int ans = 1;
  x %= MOD;
  int digit = (int)((log((double)y) / log((double)2) / 1 + 1));
  for (int i = 0; i < digit; i++) {
    if (((y >> i) & 1u) == 1) {
      ans *= x;
      ans %= MOD;
    }
    x = x * x;
    x %= MOD;
  }
  return ans;
}
signed main() {
  int N = in();
  vector<int> A(N);
  rep(i, N) {
    cin >> A[i];
  }
  sort(ALL(A));
  counter(A);
  if (element_num[0] == 1) {
    int num = 0;
    rep(i, 100000) {
      if (element_num[2 * (i + 1)] == 2) {
        num += 1;
      } else if (element_num[2 * (i + 1)] == 0) {
        if (A.size() == 2 * num + 1) {
          cout << bpm(2, num) << endl;
          return 0;
        } else {
          break;
        }
      } else {
        break;
      }
    }
  } else if (element_num[1] == 2) {
    int num = 0;
    FOR(i, 1, 100000) {
      if (element_num[2 * i + 1] == 2) {
        num += 1;
      } else if (element_num[2 * i + 1] == 0) {
        if (A.size() == 2 * num + 2) {
          cout << bpm(2, num + 1) << endl;
          return 0;
        }
      } else {
        break;
      }
    }
  }
  cout << 0 << endl;
}


Measured memory_bytes: 5260
#include<stdio.h>
int main(void)
{
	int a,b,c,d,x,y;
	
	scanf("%d",&a);
	scanf("%d",&b);
	scanf("%d",&c);
	scanf("%d",&d);
	
	x=a*b;
	y=c*d;
	if(x>y) {
		printf("%d\n",x);
	}
	else if(x==y) {
		printf("%d\n",x);
	}
	else if(x<y) {
		printf("%d\n",y);
	}
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <istream>
#include <set>
#include <queue>
#define rep0(i,n) for (long long int i = 0; i <= (n); ++i)
#define rep1(i,n) for (long long int i = 1; i <= (n); ++i)
#define REP(a,b) for (long long int i = a; i <= (b); ++i) 
#define ps push_back 
using namespace std;
typedef long long ll;
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	string s;
	string ans;
	cin >> s;
	REP(0, s.length() - 1) {
		if (i % 2 == 0) {
			ans += s[i];
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 592
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <stack>

typedef long long ll;

using namespace std;

int main() {
    int x, a;
    cin >> x >> a;
    
    if(x < a) {
        cout << 0 << endl;
    }
    else {
        cout << 10 << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <algorithm>
#include <tuple>
#include <cmath>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int> >
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
using namespace std;

int N, K;
int a[105];
bool dp[100000 + 10]; //山にk枚残っている場合手番の人が負ける場合false そうでない場合true

int main(void) {
    cin >> N >> K;
    rep(i, N) {
        cin >> a[i];
    }
    
    rep(i, a[0]) {
        dp[i] = false;
    }
    rep(i, N-1) {
        REP(j, a[i], a[i+1] - 1) {
            dp[j] = false;
            REP(k, 0, i) {
                if (dp[j-a[k]] == false) {
                    dp[j] = true;
                    break;
                }
            }
        }
    }
    
    REP(i, a[N-1], K) {
        dp[i] = false;
        REP(j, 0, N-1) {
            if (dp[i-a[j]] == false) {
                dp[i] = true;
                break;
            }
        }
    }
    
    cout << ((dp[K]) ? "First" : "Second") << endl;
    
    return 0;
}



Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()		 //sort(all(vi S)) sort(all(string S))
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }

using P = pair<int, int>;		//P.first, P.second
typedef long long ll;
typedef vector<int> vi;
typedef set<int> seti;
typedef vector<string> vs;

const int MOD = 1e9+7;
const int INF = 1e9;
int main() {
    int N;
    cin>>N;
    vector<ll> a(N);
    vector<int>pos(N+1);
    rep(i,N){
        cin>>a[i];
        pos[a[i]] = i;
    }
    ll ans = 0;
    multiset<int> s; s.insert(-1); s.insert(-1); s.insert(N); s.insert(N);
    s.insert(pos[N]);
    for (int i = N-1; i >= 0; --i){
        auto itr = s.lower_bound(pos[i]);
        ll nxt = *itr; itr++; ll nxt2 = *itr;
        itr = s.lower_bound(pos[i]); itr--;
        ll pre = *itr; itr--; ll pre2 = *itr;
        ans += (pos[i]-pre)*(nxt2-nxt)*i;
        ans += (pre-pre2)*(nxt-pos[i])*i;
        s.insert(pos[i]);
    }
    cout<<ans<<endl;

}

Measured memory_bytes: 6144
#include<vector>
#include<iostream>
using namespace std;
#define MAX_V 1000
#define MAX_E 2000
#define INF 1e9
struct edge {
	int from, to, cost;
};
int V, E, d[MAX_V];
edge es[MAX_E];
bool find_negative_loop(int s)
{
	int count=0;
	for (int i = 0; i < V; i++)
	{
		d[i] = INF;
	}
	d[s] = 0;
	while (true)
	{
		bool update = false;
		count++;
		for (int i = 0; i < E; i++)
		{
			if (d[es[i].from] != INF && d[es[i].to] > d[es[i].from] + es[i].cost)
			{
				if (count == V)
				{
					return true;
				}
				d[es[i].to] = d[es[i].from] + es[i].cost;
				update = true;
			}
		}
		if (!update)
		{
			break;
		}

	}
	return false;
}

int main()
{
	int r;
	cin >> V >> E >> r;
	for (int i = 0; i < E; i++)
	{
		cin >> es[i].from >> es[i].to >> es[i].cost;
	}
	if (find_negative_loop(r))
	{
		cout << "NEGATIVE CYCLE" << endl;
	}
	else
	{
		for (int i = 0; i < V; i++)
		{
			if (d[i] ==INF)
			{
				cout << "INF" << endl;
			}
			else
			{
				cout << d[i] << endl;
			}
		}
	}
	return 0;

	
}





Measured memory_bytes: 3128
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
#define to_s to_string
#define len(v) (int)v.size()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define print(x) cout << (x) << '\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
ll MOD = 1e9 + 7;
ll devc(ll x, ll y) { return 1 + (x - 1) / y; }

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);

    string S;
    cin >> S;
    vector<ll> X(4);
    rep(i, 4) X[i] = S[i] - '0';

    struct hold{
        ll sum;
        string ans;
        ll counter;
    };
    stack<hold> sk;
    sk.push({X[0],to_string(X[0]),0});

    string ans;

    while(!sk.empty()){
        hold H = sk.top();
        if(H.counter == 3 && H.sum == 7) ans = H.ans;
        sk.pop();
        
        ll now = ++H.counter;
        if(now <= 3){
            sk.push({H.sum + X[now], H.ans + "+" + to_string(X[now]), now});
            sk.push({H.sum - X[now], H.ans + "-" + to_string(X[now]), now});
        }
    }

    print(ans+"=7");

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep2(i, m, n) for(int i=int(m); i<int(n); i++)
#define rep(i, n) rep2(i, 0, n)
#define ALL(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
const int INF = int(1e9)+10;
const ll INFll = ll(1e18)+10;
const ld EPS = 1e-10;
const int MOD = int(1e9)+7;

int main() {
  int N, T; cin >> N >> T;
  vector<P> AB(N);
  rep(i, N) cin >> AB[i].first >> AB[i].second;
  sort(ALL(AB));

  VV dp(N+1, V(T));
  rep(i, N) rep(t, T) {
    dp[i+1][t] = dp[i][t];
    if (t >= AB[i].first) {
      dp[i+1][t] = max(dp[i+1][t], dp[i][t-AB[i].first] + AB[i].second);
    }
  }

  int cmax = 0;
  int ans = 0;
  for (int i = N; i >= 0; i--) {
    cmax = max(cmax, AB[i].second);
    ans = max(ans, dp[i][T-1] + cmax);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 35584
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<list>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<functional>
#include<set>

using namespace std;

#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define INF 9223372036854775807
#define MOD 1000000007
#define pb push_back
#define F first
#define S second

typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef pair<ll, ll> pll;

ll n = 0, m = 0, ans = 0, sum = 0, cnt = 0, temp = 0;
string s;
bool flag;

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

#define MAX 11111

int main(void) {
  vll a;
  cin >> n;
  FOR(i, 0, n) {
	cin >> temp;
	m = max(m, temp);
	a.pb(temp);
  }

  FOR(i, 0, n) {
	if (llabs((m - a[i]) - a[i]) < llabs((m - ans) - ans)) ans = a[i];
  }

  cout << m << " " << ans << endl;

  /*
  sort(ALL(a));

  temp = lower_bound(ALL(a), m / 2) - a.begin();

  if (llabs((m - a[temp - 1]) - a[temp - 1]) > llabs((m - a[temp]) - a[temp])) {
	cout << m << " " << a[temp] << endl;
  }
  else {
	cout << m << " " << a[temp - 1] << endl;
  }*/

  return 0;
}


Measured memory_bytes: 1400
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> x(n), y(n), h(n);
    rep(i,n) cin >> x[i] >> y[i] >> h[i];
    for(int cy = 0; cy <= 100; ++cy){
        for(int cx = 0; cx <= 100; ++cx){
            int H;
            rep(i,n){
                if(h[i] > 0){
                    H = h[i] + abs(x[i] - cx) + abs(y[i] - cy);
                    break;
                }
            }
            bool ok = true;
            rep(i,n){
                int high = H - abs(x[i] - cx) - abs(y[i] - cy);
                chmax(high, 0);
                if(h[i] != high){
                    ok = false;
                    break;
                }
            }
            if(ok){
                cout << cx << " " << cy << " " << H << endl;
                return 0;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 3584
#include "bits/stdc++.h"
#define PRECISION(x) cout << fixed << setprecision(x)
#define FAST_IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define ALLR(X) (X).rbegin(), (X).rend()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define F first
#define S second

using namespace std;
 
template<class T> void max_self(T & a, const T & b) { if(a < b) a = b; }
template<class T> void min_self(T & a, const T & b) { if(a > b) a = b; }
typedef long long LL;
const int INF = 1e9 + 7;
const double PI = acos(-1.0);
const double EPS = (1e-9);



int main(){
	FAST_IO
	
	int A, B;
	cin >> A >> B;
	
	auto check = [&](double p){

		if((int)(p * 0.08) != A) return false;
		if((int)(p * 0.10) != B) return false;
		return true;
	};
	
	for(double price = 1; price <= 2600; ++price){
		if(check(price)){
			cout << price << "\n";
			return 0;
		}
	}
	
	cout << "-1\n";
	
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    char s[16];
    cin>>s;
    int l=strlen(s),ans=0;
    for(int i=0;i<l;i++)
    {
        if(s[i]=='o')
        {
            ans++;
        }
    }
    if((ans+(15-l))>=8)
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }
    return 0;
}


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

int main(void) {
	int l,r,d;
	int count=0;
	scanf("%d%d%d",&l,&r,&d);
	for(int i=l;i<=r;i++){
		if(i%d==0)count++;
	}
	printf("%d\n",count);
}


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

int main() {
  int N, K; cin >> N >> K;
  bool p[N]; for (int i = 0; i < N; i++) p[i] = false;
  for (int k = 0; k < K; k++) {
    int d; cin >> d;
    for (int i = 0; i < d; i++) {
      int a; cin >> a;
      p[a-1] = true;
    }
  }
  int c = 0;
  for (int i = 0; i < N; i++) c += !p[i];
  cout << c << endl;
}

Measured memory_bytes: 3584
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<vector<int>> ch(N);
    vector<int> par(N, -1);

    for (int i = 0; i < N; ++i) {
        int v, k;
        cin >> v >> k;

        ch[v].resize(k);
        for (int& c : ch[v]) {
            cin >> c;
            par[c] = v;
        }
    }

    int r = min_element(par.begin(), par.end()) - par.begin();
    vector<int> d(N, 0);
    queue<int> que;
    que.push(r);
    while (!que.empty()) {
        int v = que.front();
        que.pop();

        for (int sv : ch[v]) {
            d[sv] = d[v] + 1;
            que.push(sv);
        }
    }

    for (int v = 0; v < N; ++v) {
        cout << "node " << v << ": parent = " << par[v] << ", depth = " << d[v] << ", ";
        cout << (par[v] < 0 ? "root" : (ch[v].empty() ? "leaf" : "internal node")) << ", [";
        for (int i = 0; i < ch[v].size(); ++i) {
            cout << ch[v][i] << (i < ch[v].size() - 1 ? ", " : "");
        }
        cout << "]" << endl;
    }
    return 0;
}



Measured memory_bytes: 6832
//ヘッダー
#include<bits/stdc++.h>
using namespace std;

//型定義
typedef long long ll;

//定数
const int INF=1e+9;
const int MOD=1e+9+7;

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

//グローバル変数


//ライブラリ挿入


int main(){
    int N,W;
    cin >> N >> W;
    vector<vector<ll>> V(4);
    int w1,w,v;
    cin >> w >> v;
    w1=w;
    V[0].push_back(v);
    REP2(i,1,N){
        cin >>w>>v;
        V[w-w1].push_back(v);
    }

    REP(i,4){
        sort(V[i].begin(),V[i].end(),greater<ll>());
    }

    vector<vector<ll>> Vsum(4,vector<ll>(110,0));
    REP(i,4){
        REP(j,V[i].size()){
            Vsum[i][j+1]=Vsum[i][j]+V[i][j];
        }
    }
    

    ll ans=0;
    REP(i,V[0].size()+1){
        REP(j,V[1].size()+1){
            REP(k,V[2].size()+1){
                REP(l,V[3].size()+1){
                    if(w1*i+(w1+1)*j+(w1+2)*k+(w1+3)*l<=W){
                        ans=max(ans,Vsum[0][i]+Vsum[1][j]+Vsum[2][k]+Vsum[3][l]);
                    }
                }
            }
        }
    }
    cout << ans <<endl;

    
}

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

int main() {
  int A, B, C=0;
  cin >> A >> B;
  if (A > B) {
      C = A;
      A --;
  }
  else {
      C = B;
      B --;
  }
  if (A > B) {
      C += A;
  }
  else {
      C += B;
  }
  cout << C << endl;
}




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

#define int long long
#define ll long long
#define rep(i,n) for (ll i = 0; i < (n) ; i++)
ll ltmp;
int f(string s,int a){
  if(a==0)return -1;
  int res=0,t=1;
  reverse(s.begin(),s.end());
  for(int i=0;i<s.size();i++){
    (res+=t*(s[i]=='1'))%=a;
    (t*=2)%=a;
  }
  return res;
}
int p(int a){
  int res=0;
  while(a){
    if(a&1)res++;
    a>>=1;
  }
  return res;
}
int F(int a){
  int res=0;
  while(a){
    res++;
    a%=p(a);
  }
  return res;
}

ll getMod(ll value,ll mod){
    if(value == 0) return 0;
    return (value + mod) % mod;
}

#define base10_6 1000000    //1e6
ll getPower(ll value,ll shisu,ll mod){
    ll ans = 1;
    ll cnt = shisu;
    while(cnt>0){
        if(cnt%2==1){
            ans = ans * value % mod;
        }
        value = value * value % mod;
        cnt = cnt/2;
    }
    return ans;
}
ll bit2[1000010]={};

ll mod_p[base10_6+10]={};
ll mod_m[base10_6+10]={};
ll getIntSubstr(string s,ll start_index,ll length){
    return atoi(s.substr(start_index,length).c_str());
}

signed main(){
    int n;cin>>n;
    string s;cin>>s;
    int sum=0;
    for(char p:s)sum+=p=='1';
  
    ll base_pop = 0;
    string S = s;
    ll N = n;
    rep(ni,N){
        bit2[ni] = getIntSubstr(S,ni,1);
        //bit2[ni] = 1;
        base_pop+=bit2[ni];
    }
    sum = base_pop;

    ll basev= 1;

    basev=1;



    ll base_pop_p;
    ll base_pop_m;
    base_pop_p = base_pop+1;
    base_pop_m = base_pop-1;
    if(base_pop_m==0) base_pop_m=1;

    basev = 1;
    ltmp = 1;
    for( ll keta = 1 ; keta <=base10_6 ; keta++ ){
        mod_p[keta] = basev;
        basev = basev * 2;
        basev = getMod(basev,base_pop_p); 
    }
    basev = 1;
    for( ll keta = 1 ; keta <= base10_6 ; keta++ ){
        mod_m[keta] = basev;
        basev = basev * 2;
        basev = getMod(basev,base_pop_m); 
    }

    ll base_f1_p = 0;
    ll base_f1_m = 0;
    for( ll keta = 1 ; keta <=N ; keta++ ){
        ll ind = N -keta;
        base_f1_p += mod_p[keta] * bit2[ind];
        base_f1_m += mod_m[keta] * bit2[ind];
        base_f1_p = getMod(base_f1_p,base_pop_p );
        base_f1_m = getMod(base_f1_m,base_pop_m );
    }

    int A=f(s,sum+1);
    int B=f(s,sum-1);


  for(int i=0;i<n;i++){
    if(sum==1&&s[i]=='1'){
      cout<<0<<endl;
      continue;
    }
    if(s[i]=='0'){
      int res=A;
      res+=getPower(2,n-i-1,sum+1);res%=sum+1;
      cout<<F(res)+1<<endl;
    }
    else{
      int res=B;
      res-=getPower(2,n-i-1,sum-1);
      res+=sum-1;res%=sum-1;
      cout<<F(res)+1<<endl;
    }
  }
}


Measured memory_bytes: 21024
#include <bits/stdc++.h>
using namespace std;
const long double PI = 3.141592653589793;
const long double DEL = 1e-10;
const int mod =  1000000007;

#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define mpq priority_queue<int,vector<int>,greater<int>>
#define deb(a) cerr << #a << ": " << a << endl
#define vvpii vector<vector<pair<int,int>>>
#define ftt cin>>t;for(int tt=1;tt<=t;++tt)
#define Rev(v) reverse(v.begin(),v.end())
#define Sort(v) sort(v.begin(),v.end())
#define mem(a,b) memset(a,b,sizeof(a))
#define forr(i,a,b) for(i=a;i<=b;i++)
#define umii unordered_map<int,int>
#define vpii vector<pair<int,int>>
#define all(a) a.begin() , a.end()
#define vvi vector<vector<int>>
#define pq priority_queue<int>
#define sqr(a) (((a) * (a)))
#define double long double
#define dbg cout<<"\nhi\n"
#define pii pair<int,int>
#define mii map<int,int>
#define vb vector<bool>
#define vi vector<int>
#define int long long
#define nl cout<<"\n"
#define pb push_back
#define sp <<" "<<
#define ss second
#define ff first
inline void read(int &x)
{
      int c = getchar();
      x = 0;
      int neg = 0;
      for(; ((c<48 || c>57) && c != '-'); c = getchar());
      if(c=='-')
      {
            neg = 1;
            c = getchar();
      }
      for(; c>47 && c<58 ; c = getchar())
      {
            x = (x<<1) + (x<<3) + c - 48;
      }
      if(neg)
      {
            x = -x;
      }
}
int fpow(int x, int n)
{
    int res = 1;
    while(n){
          if(n&1){
                res = res * x % mod;
          }
          x = x * x % mod;
          n>>=1;
    }
    return res;
}
int gcd(int a,int b)
{
    if(b == 0)
    {
          return a;
    }
    return gcd(b,a % b);
}
void sieve(int n)
{
      bool prime[1000006];
      memset(prime, true, sizeof(prime));
      int rootn = (int)sqrt(n);
      for (int p = 2; p <= rootn; p++)
      {
            if (prime[p] == true)
            {
                  for (int i = p*p; i <= n; i += p)
                  {
                        prime[i] = false;
                  }
            }
      }
      prime[1] = 0;
}
const int N = 100050;
int cnt, sum, mid, mx, mn, ans, a[N], b[N];
int n, m, d, i, j, k, l, p, q, r, t, w, x, y, z;
bool f, f1, f2;
string s;

//******************************************* CHECK CONSTRAINTS **************************************************

int check(int i,int j,int k)
{
      vi v = {i,j,k};
      Sort(v);
      return v[2] < v[0] + v[1];
}

int32_t main()
{     fio;
      cin>>n;
      forr(i,1,n)
      {
            cin>>a[i];
      }
      ans = 0;
      forr(i,1,n)
      {
            forr(j,i+1,n)
            {
                  forr(k,j+1,n)
                  {
                        if(a[i]==a[j] || a[j]==a[k] || a[i]==a[k])
                        {
                              continue;
                        }
                        if(check(a[i],a[j],a[k]))
                        {
                              //cout<<a[i] sp a[j] sp a[k];nl;
                              ans++;
                        }
                  }
            }
      }
      cout<<ans;
     
}


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

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

    vector<bool> row(h);
    vector<bool> col(w);
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (a[i][j] == '#') {
                row[i] = true;
                col[j] = true;
            }
        }
    }

    for (int i = 0; i < h; i++) {
        if (row[i]) {
            for (int j = 0; j < w; j++) {
                if (col[j]) {
                    cout << a[i][j];
                }
            }
            cout << endl;
        }
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <string>
#include <queue>
#include <numeric>
#include <ctype.h>
#include <limits>
#include <iomanip>

#define rep(i,n) for (int i = 0; i < n; i++)
#define all(x) (x).begin(),(x).end()
using namespace std;

typedef long long ll;

int main() {
	/*int n;
	cin >> n;
	int ans = pow(n, 3);
	cout << ans;*/


	/*int n;
	cin >> n;
	vector<int>a(n), b(n), c(n);
	rep(i, n)cin >> a[i];
	rep(i, n)cin >> b[i];
	rep(i, n - 1)cin >> c[i];
	int ans = 0;
	ans = accumulate(all(b), 0);
	for (int i = 0; i < n - 1; i++) {
		if (a[i + 1] - a[i] == 1)ans += c[a[i]-1];
	}
	cout << ans;*/


	int n;
	cin >> n;
	vector<int>b(n);
	rep(i, n - 1)cin >> b[i];
	int ans = b[0] + b[n - 2];
	for (int i = 1; i < n - 1; i++) {
		ans += min(b[i], b[i - 1]);
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256