akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>

using namespace std;

int abs(int x){
    if (x > 0) return x;
    else return -x;
    
}

int gcd(int a, int b){
    while(b != 0){
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main(){
    int n, X;
    scanf("%d %d", &n, &X);
    int x[n];
    for(int i = 0; i < n; i++){
        scanf("%d", &x[i]);
    }
    
    int d = abs(x[0] - X);
    for(int i = 1; i < n; i++){
        d = gcd(abs(x[i] - X), d);
    }
    printf("%d\n", d);
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mp make_pair
const ll mod=1e9+7;
typedef pair<int,int> pii;
typedef priority_queue<int,vector<int>,greater<int> > small_heap;
typedef priority_queue<int> big_heap;
int n;
ll a[10009];
ll mx[1000006];
ll power(ll aa,ll b)
{
    ll c=1;
    for(;b;b>>=1){
        if(b&1)c=c*aa%mod;
        aa=aa*aa%mod;
    }
    return c%mod;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        ll x=a[i];
        for(ll v=2;v*v<=x;v++){
            if(x%v)continue;
            ll cur=0;
            while(x%v==0){
                cur++;
                x/=v;
            }
            mx[v]=max(mx[v],cur);
        }
        if(x!=1)mx[x]=max(mx[x],1ll);
    }
    ll lcm=1;
    for(ll i=1;i<=1000006;i++)
    {
        if(mx[i]) lcm = (lcm * power(i, mx[i])) % mod;
    }
    log(lcm);
    ll sum=0;
    for(int i=1;i<=n;i++){
        sum=(sum+power(lcm,1)%mod*power(a[i],mod-2)%mod)%mod;
    }
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 6656
#include <stdio.h>

int main(){
    
    int a,b,c,i,n = 0;
    
    scanf("%d %d %d",&a,&b,&c);
   
    i = a;
    
    while(i != b){
        if(c % i == 0){
            n = n + 1;
        }
        i++;
    }
    
     if(a > c){
        if(b > c){
            printf("%d\n",0);
            return 0;
        }
    }    
    if(a == b){
        if(a < b < c){
            printf("%d\n",1);
            return 0;
         }
    }

    if(a == b){
        if(b == c){
        printf("%d\n",1);
        return 0;
        }
    }
    
    
    if(b == c){
        printf("%d\n",n + 1);
        return 0;
    }
    
    printf("%d\n",n);
    
    return 0;    
}

Measured memory_bytes: 596
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
// #define main int main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvpii = vector<vpii>;
template<typename A> using fn = function<A>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int &n) { return n & 1; }
constexpr bool even(const int &n) { return !odd(n); }
void solve();
main { solve(); return 0; }
// clang-format on

vector<int> eratosthenes(const int &n) {
  vector<int> v(n);
  v[0] = v[1] = false;
  loop(i, 2, v.size()) v[i] = true;
  for (int i = 2; i * i < n; i++) {
    if (v[i]) {
      for (int j = i * 2; j < n; j += i) {
        v[j] = false;
      }
    }
  }
  return v;
}

void solve() {
  vi v = eratosthenes(1000000);
  int n;
  while (cin >> n, n) {
    int i = 0, c = 0;
    while (n--) {
      while (!v[i]) i++;
      c += i++;
    }
    cout << c << endl;
  }
}

Measured memory_bytes: 10544
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<endl;}
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(int argc, char const *argv[]) {
  char s;
  cin >> s;
  if (isupper(s)) puts("A");
  else
    puts("a");
  return 0;
}

Measured memory_bytes: 3620
// Problem : B - OddString
// Contest : AtCoder - AtCoder Beginner Contest 072
// URL : https://atcoder.jp/contests/abc072/tasks/abc072_b
// Memory Limit : 256 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define eb emplace_back
#define pb push_back
#define size(s) (int)s.size()
#define int long long
#define vi vector<int>
#define vs vector<string>
#define vv vector<vector<int>>
#define pii pair<int,int>
#define m_p(x,y) make_pair(x,y)
#define vp vector<pair<int,int>>
#define setbits(x) __builtin_popcountll(x)
#define f first
#define se second
#define inc(v,n,x) v.assign(n,x)
#define incd(v,n) v.resize(n)
#define iniz(n) memset(n,0,sizeof(n))
#define inin(n) memset(n,-1,sizeof(n))
#define inimi(n) memset(n,0xc0,sizeof(n))
#define inima(n) memset(n,0x3f,sizeof(n))
#define all(v) (v).begin(),(v).end()

using namespace std;

template<typename T1,typename T2>istream &operator>>(istream &is, vector<pair<T1,T2>> &v) { for (pair<T1,T2> &t : v) is >> t.f>>t.se; return is; }
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }

const int N=200001;
double pi=acos(-1.0);
int md=1e9+7;
const int INF=1e15;
int dx1[]={0,0,-1,1};
int dy1[]={1,-1,0,0};

template<class T>
T abst(T a)
{return a<0?-a:a;}

template<class T>
T max2(T a,T b){return a>b?a:b;}
template<class T>
T min2(T a,T b){return a<b?a:b;}

void solve()
{
string s;cin>>s;
for(int i=0;i<size(s);i++)
if(i%2==0)
cout<<s[i];
}

int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)
{
    solve();
}
return 0;
}


Measured memory_bytes: 3680
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <math.h>
using namespace std;

const int MAXN = 2000 + 10;
const int MAXM = 4000 + 10;
int N, K;
int cnt = 1, Head[MAXN], Next[MAXM], To[MAXM];
int tt, ans = MAXN;

inline void add_edge(int x, int y) {
	Next[++cnt] = Head[x], To[cnt] = y, Head[x] = cnt;
}

inline void insert_edge(int x, int y) {
	add_edge(x, y), add_edge(y, x);
}

inline void Dfs(int x, int fa, int d) {
	register int i;
	++tt;
	if(!d) return;
	for(i = Head[x]; i; i = Next[i]) if(To[i] != fa) {
		Dfs(To[i], x, d - 1);
	}
}

int main() {
	register int i, j; int x, y;
	scanf("%d%d", &N, &K);
	for(i = 1; i < N; ++i)
		scanf("%d%d", &x, &y),
		insert_edge(x, y);
	if(K & 1)
		for(i = 1; i <= N; ++i)
			for(j = Head[i]; j; j = Next[j])
				tt = 0, Dfs(i, To[j], K >> 1), Dfs(To[j], i, K >> 1), ans = min(ans, N - tt);
	else
		for(i = 1; i <= N; ++i)
			tt = 0, Dfs(i, 0, K >> 1), ans = min(ans, N - tt);
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
import numpy as np
a1 = np.zeros(3, dtype=int)
a2 = np.zeros(3, dtype=int)
a3 = np.zeros(3, dtype=int)

for i in range(3):
    a1[i], a2[i], a3[i] = map(int, input().split())

n = int(input())
b = [int(input()) for i in range(n)]

a = np.array([a1, a2, a3]).T.flatten()

for i in range(n):
    a[np.where(a == b[i])] = 0
a = a.reshape(3, -1)

print("Yes") if a[0].sum()==0 or a[1].sum()==0 or a[2].sum()==0 or a[:, 0].sum()==0 or a[:, 1].sum()==0 or a[:, 2].sum()==0 or np.diag(a).sum()==0 or np.diag(a[::-1]).sum()==0 else print("No")

Measured memory_bytes: 21800
def prime_factorization(n):  # 素因数分解
    res = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                cnt += 1
                n //= i
            res.append((i, cnt))
    if n > 1:
        res.append((n, 1))
    return res


def euler_phi(X):
    """
    [1,X]の自然数のうちXと互いに素なものの個数
    """
    if X <= 0:
        raise "INVALID INPUT...X must be natural number"
    pf = prime_factorization(X)
    res = X
    for p, _ in pf:
        res //= p
        res *= (p - 1)
    return res


if __name__ == "__main__":
    N = int(input())
    print(euler_phi(N))


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

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

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


int main() {
  int N;
  cin >> N;
  vector< int > A(N);
  cin >> A;

  int64 ret = 0;
  for(int p = 1; p < N; p++) {
    int x = 0, y = N - 1;
    set< int > used;
    used.emplace(x);
    used.emplace(N - 1);
    int64 add = 0;
    for(;;) {
      x += p;
      y -= p;
      if(x == y) {
        break;
        if(used.count(x)) {
          break;
        }
        add += A[x];
        chmax(ret, add);
        break;
      }
      if(x >= N) {
        break;
      }
      if(y < p) {
        break;
      }
      if(used.count(x)) {
        break;
      }
      used.emplace(x);
      if(used.count(y)) {
        break;
      }
      used.emplace(y);
      add += A[x];
      add += A[y];
      chmax(ret, add);
    }
  }
  cout << ret << endl;
}




Measured memory_bytes: 7424
#include <bits/stdc++.h>
using namespace std;
typedef struct line
{
        int lp,rp,value;
        bool operator < (const struct line & t) const
        {
                return rp<t.rp;
        }
}LINE,*PLINE;
LINE arr[200001];
int n,m;
long long lazy[1<<19],linetree[1<<19];
long long query(int index,int lb,int rb,int lq,int rq)
{
        if(lb==lq&&rb==rq)
        {
                return linetree[index];
        }
        if(lazy[index])
        {
                linetree[index<<1]+=lazy[index];
                linetree[index<<1|1]+=lazy[index];
                lazy[index<<1]+=lazy[index];
                lazy[index<<1|1]+=lazy[index];
                lazy[index]=0;
        }
        int mid=(lb+rb)>>1;
        if(rq<=mid)
                return query(index<<1,lb,mid,lq,rq);
        else if(lq>mid)
                return query(index<<1|1,mid+1,rb,lq,rq);
        else
        {
                return max(query(index<<1,lb,mid,lq,mid),query(index<<1|1,mid+1,rb,mid+1,rq));
        }
}
void update(int index,int lb,int rb,int lq,int rq,long long value)
{
        if(lb==lq&&rb==rq)
        {
                linetree[index]+=value;
                lazy[index]+=value;
                return ;
        }
        if(lazy[index])
        {
                linetree[index<<1]+=lazy[index];
                linetree[index<<1|1]+=lazy[index];
                lazy[index<<1]+=lazy[index];
                lazy[index<<1|1]+=lazy[index];
                lazy[index]=0;
        }
        int mid=(lb+rb)>>1;
        if(rq<=mid)
                update(index<<1,lb,mid,lq,rq,value);
        else if(lq>mid)
                update(index<<1|1,mid+1,rb,lq,rq,value);
        else
        {
                update(index<<1,lb,mid,lq,mid,value);
                update(index<<1|1,mid+1,rb,mid+1,rq,value);
        }
        linetree[index]=max(linetree[index<<1],linetree[index<<1|1]);
}
int main()
{
        int i,cnt=1;
        scanf("%d %d",&n,&m);
        for(i=1;i<=m;i++)
        {
                scanf("%d %d %d",&arr[i].lp,&arr[i].rp,&arr[i].value);
        }
        sort(arr+1,arr+m+1);
        for(i=1;i<=n;i++)
        {
                update(1,0,n,i,i,query(1,0,n,0,i-1));
                while(arr[cnt].rp==i)
                {
                        update(1,0,n,arr[cnt].lp,arr[cnt].rp,arr[cnt].value);
                        cnt++;
                }
        }
        printf("%lld",linetree[1]);
        return 0;
}


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

int main(){
  int N,M,sum=0;
  cin >> N >> M;
  vector<int> A(N);
  for(int i=0; i<N; i++){
    cin>>A[i];
    sum+=A[i];
  }
  sort(A.begin(),A.end());
  if(A[N-M]*4*M < sum){
    cout<<"No"<<endl;
    return 0;
  }
    cout<<"Yes"<<endl;
}


Measured memory_bytes: 3588
import java.util.Scanner;
import java.util.Stack;

//Switching Railroad Cars
public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Stack<Integer> s = new Stack<Integer>();
		while(sc.hasNext()){
			int a = sc.nextInt();
			if(a==0)System.out.println(s.pop());
			else s.push(a);
		}
	}
}

Measured memory_bytes: 11000
#include <cstdio>
#include <iostream>
using namespace std;
int p[110][110];
int main(){
    int h,w,m,x=0;
    cin>>h>>w>>m;
    int a[m];
    for(int i=0;i<m;i++){
        cin>>a[i];
        for(int j=0;j<a[i];j++){
            if((x/w)%2==0)
			 p[x/w][x%w]=i+1;
            else
			 p[x/w][w-(x%w)-1]=i+1;
            x++;
        }
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(j==w-1)
			 printf("%d\n",p[i][j]);
            else printf("%d ",p[i][j]);
        }
    }
    return 0;
}

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

using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define repa(i,a,n) for(int i=(a);i<(n);i++)
#define rrep(i,n) for(int i=n;i>=0;i--)
#define rrepa(i,a,n) for(int i=n;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define vc vector

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int,int> pi;

int main(){

    ll n,k;
    cin>>n>>k;

    if(k==1){
        cout<<0<<"\n";
        return 0;
    }

    if(n>k)n=n-((ll)(n/k))*k;

    cout<<min(n,k-n)<<"\n";

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<stdio.h>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;
int main()
{

    int t,n,i,arra[1000],count=0;
    string s,r;
    cin>>s;
        cin>>r;
        for(i=0;i<s.size();i++)
        {
            if(s[i]!=r[i])
               count++;
        }
        cout<<count<<endl;

    return 0;
}



Measured memory_bytes: 3920
import sys
from collections import Counter
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    A = map(int, input().split())
    Aplus = [0] * N
    for i, a in enumerate(A):
        Aplus[i] = i + a + 1
    A_counter = Counter(Aplus)

    ans = 0
    for i in range(1, N + 1):
        key = i * 2 - Aplus[i-1]
        ans += A_counter[key]
        if key == Aplus[i - 1]:
            ans -= 1
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 116604
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
import threading
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, K = LI()
A = LI()

dp = [False]*(K+1)
for a in A:
    dp[a] = True

for i in range(K+1):
    for a in A:
        if (i<a):
            break
        if (not dp[i-a]):
            dp[i] = True
            break

print("First" if dp[K] else "Second")


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

int main(){
	string a;
	int b,c;
	for(int i=0;;i++){
		cin>>a;
		if(a=="-")break;
		cin>>b;
		for(int j=0;j<b;j++){
			cin>>c;
			a=a+a.substr(0,c);
			a=a.erase(0,c);
		}
	cout <<a<<endl;
	}
	return 0;
}

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

using namespace std;

typedef long long LL;

LL dp[20010];

int main()
{
    LL n,h,i,ans,d,m;
    cin >> h >> n;
    for(i = 1; i < 20010; i ++)
    {
        dp[i] = 1e10;
    }
    for(int j = 0; j < n; j ++)
    {
        cin >> d >> m;
        for(i = d; i < 20000; i ++)
        {
            dp[i] = min(dp[i],dp[i-d]+m);
        }
    }
    ans = dp[20000];
    for(i = h; i < 20000; i ++) ans = min(ans,dp[i]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3121000;
long long fact[C_SIZE];
long long finv[C_SIZE];
long long inv[C_SIZE];
long long Comb(int a,int b){
 	if(a<b||b<0)return 0;
 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
void init_C(int n){
	fact[0]=finv[0]=inv[1]=1;
	for(int i=2;i<n;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<n;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}
long long pw(long long a,long long b){
	long long ret=1;
	while(b){
		if(b%2)ret=ret*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return ret;
}
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
// ここから編集しろ
int p[210000];
int now[53];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",p+i);
	bool ok=true;
	for(int i=1;i<a;i++){
		if(p[i-1]>=p[i]){
			ok=false;
		}
	}
	if(ok){
		printf("1\n");return 0;
	}
	int left=1;
	int right=a+1;
	while(left+1<right){
		int M=(left+right)/2;
		int sz=0;
		bool ok=true;
		for(int i=0;i<a;i++){
			if(p[i]>50)continue;
			if(sz<p[i]){
				for(int j=sz;j<p[i];j++)now[j]=0;
				sz=p[i];
			}else{
				int at=-1;
				for(int j=p[i]-1;j>=0;j--){
					if(now[j]!=M-1){
						now[j]++;
						at=j;break;
					}
				}

				if(at==-1){
					ok=false;break;
				}
				for(int j=at+1;j<p[i];j++){
					now[j]=0;
				}
				sz=p[i];
			}
		}
		if(ok){
			right=M;
		}else left=M;
	}
	printf("%d\n",right);
}


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

long long A[4], D;

int main() {
	cin >> A[0] >> A[1] >> A[2] >> A[3] >> D;
	for (int i = 1; i <= 3; i++) A[i] = min(A[i], A[i - 1] * 2LL);
	cout << (D / 2LL) * A[3] + (D % 2LL) * A[2] << endl;
	return 0;
}

Measured memory_bytes: 256
import numpy as np

N = int(input())
XY_set = set(tuple(map(int, input().split())) for _ in range(N))
N = len(XY_set)

XY45 = np.array([(x + y, x - y) for x, y in XY_set]).T
ans = max(XY45[0].max() - XY45[0].min(),
          XY45[1].max() - XY45[1].min())
print(ans)


Measured memory_bytes: 90500
#!/usr/bin/env ruby

attrs = Array.new
while line = $stdin.gets
  attrs << line.chomp.split
end

S = attrs[0][0]
T = attrs[0][1]

numS = attrs[1][0].to_i
numT = attrs[1][1].to_i

U = attrs[2][0]
if S == U then
    puts "#{numS - 1} #{numT}"
else
    puts "#{numS} #{numT - 1}"
end

Measured memory_bytes: 1788
import sys
sys.setrecursionlimit(10 ** 5)
MOD = 10 ** 9 + 7
N, K = map(int, input().split())
V = {i: [] for i in range(1,N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)

def dfs(u, p, c):
    l = len([i for i in V[u] if i != p])
    n = K - 2
    if p == 0:
        n += 1
    if l == 0:
        return c
    for v in V[u]:
        if v == p:
            continue
        c *= dfs(v, u, n)
        n -= 1
        c %= MOD
    return c

print(dfs(1, 0, K))


Measured memory_bytes: 118924
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            //Out.Flush();
            Read();
        }

        static void Solve()
        {
            WriteLine(ReadLine().Replace("2017", "2018"));
        }
        static bool IsPrime(long n)
        {
            if (n <= 1) return false;
            if (n == 2) return true;
            if (n % 2 == 0) return false;
            for (var i = 3; i * i <= n; i += 2)
                if (n % i == 0)
                    return false;
            return true;
        }

        static long Mod = (long)1e9 + 7;
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static public (T1 a, T2 b) Slice<T1, T2>()
        {
            var t = ReadLine().Split();
            return (
            (T1)Convert.ChangeType(t[0], typeof(T1)),
            (T2)Convert.ChangeType(t[1], typeof(T2)));
        }
        static public (T a, T b) Slice2<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)));
        }
        static public (T a, T b, T c) Slice3<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)),
            (T)Convert.ChangeType(t[2], typeof(T)));
        }
    }
}

Measured memory_bytes: 25780
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<math.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

using namespace std;
using ll = long long int;

int main(void) {
    string s, t; cin >> s >> t;
    int a, b; cin >> a >> b;
    string u; cin >> u;
    if (u == s) cout << a - 1 << " " << b << endl;
    if (u == t) cout << a << " " << b - 1 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef bitset<35> sta;

int n,a[200005],b[200005];

int main(){
	cin>>n;
	for (int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	for (int i=n;i>=1;--i){
		if (i*2>n) b[i]=a[i];
		else{
			int sum=0;
			for (int j=i+i;j<=n;j+=i){
				sum=(sum+b[j])%2;
			}
			b[i]=sum^a[i];
		}
	}
	int tot=0;
	for (int i=1;i<=n;++i) tot+=b[i];
		cout<<tot<<endl;
	for (int i=1;i<=n;++i){
		if (b[i]) printf("%d ",i);
	}
	return 0;
}

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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 1e5 + 5;

ll get_sz(ll a, ll b){
	return (b + a) / (min(a, b) + 1);
}

ll get_val_1(ll a, ll b){
	
	//cout << "########\n" << a << " " << b << endl;
	
	ll sz = get_sz(a, b);
	ll l = 0, r = (a + b) / (sz + 1) + 2;
	while(l + 1 < r){
		
		//cout << "@@@ " << l << " " << r << endl;
		
		ll mid = (l + r) / 2;
		if (mid * (sz + 1) - 1 > a + b){	// !!!!!!!!!!!!!!!!
			r = mid;
			continue;
		}
		ll a1 = a - mid * sz;
		ll b1 = b - mid + 1;	// !!!!!!!!!!!!!!!!
		if (a1 < 0 || b1 < 0){
			r = mid;
			continue;
		}
		if (get_sz(a1, b1) <= sz){
			l = mid;
		} else {
			r = mid;
		}
		
		
	}
	return l;
}

void solve(){
	int q;
	cin >> q;
	while(q--){
		ll a, b, l, r;
		cin >> a >> b >> l >> r;
		if (abs(a - b) <= 1){
			REPN(i, l, r){
				if (i % 2 == 0 && a >= b || i % 2 == 1 && a < b){
					putchar('B');
				} else {
					putchar('A');
				}
			}
			putchar('\n');
			continue;
		}
		ll sz = get_sz(a, b);
		ll cnt_l = get_val_1(a, b);
		ll len_l = cnt_l * (sz + 1);
		
		//printf("### %lld %lld %lld\n", sz, cnt_l, len_l);
		
		for(; l <= min(r, len_l); l++){
			if (l % (sz + 1) == 0){
				putchar('B');
			} else {
				putchar('A');
			}
		}
		
		l -= len_l;
		r -= len_l;
		a -= cnt_l * sz;
		b -= cnt_l;
		
		ll cntb_r = b / sz;
		if (b % sz == 0){
			cntb_r--;
			cntb_r = max(cntb_r, 0ll);
		}
		ll len_r = cntb_r * (sz + 1);
		ll cnta_rest = a - cntb_r;
		ll cntb_rest = b - cntb_r * sz;
		for(; l <= min(r, cnta_rest); l++){
			putchar('A');
		}
		for(; l <= min(r, cnta_rest + cntb_rest); l++){
			putchar('B');
		}
		l -= (cnta_rest + cntb_rest);
		r -= (cnta_rest + cntb_rest);
		a -= cnta_rest;
		b -= cntb_rest;
		for(; l <= r; l++){
			if (l % (sz + 1) == 1){
				putchar('A');
			} else {
				putchar('B');
			}
		}
		putchar('\n');
	}
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


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

const int N=2e5+100;
const int mod=1e9+7;
typedef long long ll;

int a[N];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int ans=0;
    for(int i=1;i<=n;i++){
        if(a[i]==i)  i++,ans++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 4008
#include <stdio.h> //printf()
#include <stdlib.h> //exit()

int main() {
  int a, b;
  if (scanf("%d %d", &a, &b) < 0) {
    exit(1);
  }
  int product = a * b;
  if (product % 2 == 0) {
	printf("Even\n");
  } else {
    printf("Odd\n");
  }
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#define int long long
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

int mod = 1000000007;
int n, K;
int a[100];
int dp[101][300001];

signed main() {
	int i, j, k;
	
	cin >> n >> K;
	rep(i, n) cin >> a[i];
	
	dp[0][0] = 1;
	rep(i, n) {
		rep(j, K + 1) {
			if (!dp[i][j]) continue;
			dp[i + 1][j] += dp[i][j];
			dp[i + 1][j] %= mod;
			dp[i + 1][j + a[i] + 1] += mod - dp[i][j];
			dp[i + 1][j + a[i] + 1] %= mod;
		}
		rep(j, K) {
			dp[i + 1][j + 1] += dp[i + 1][j];
			dp[i + 1][j + 1] %= mod;
		}
	}
	
	cout << dp[n][K] << endl;
	return 0;
}

Measured memory_bytes: 234112
#include<stdio.h>
#define max(lhs,rhs) ((lhs)>(rhs)?(lhs):(rhs))

int main(void){
    register int i,j,k;
    int n,ans = 0;
    scanf("%d",&n);
    if(n < 3){
        puts("0");
        return 0;
    }
    long l[n];
    for(i = 0;i < n;i++)scanf("%ld",&l[i]);
    for(i = 0;i < n;i++)for(j = i+1;j < n;j++)for(k = j + 1;k < n;k++)if(l[i] != l[j] && l[j] != l[k] && l[i] != l[k] && (l[i]+l[j]+l[k] - max(l[i],max(l[j],l[k]))*2 > 0))
        ans++;
    printf("%d",ans);
}

Measured memory_bytes: 1728
#include<bits/stdc++.h>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define int                 long long
#define FF(i,a,b)           for(int i=a;i<b;i++)
#define BF(i,a,b)           for(int i=a;i>=b;i--)
#define vi                  vector<int>
#define MAP                 map<int,int>
#define pb                  push_back
#define MP                  make_pair
#define F                   first
#define S                   second
#define pi                  pair<int,int>
#define all(v)              v.begin(),v.end()
#define PIE                 3.1415926535897932384626433832795
#define FastIO              ios::sync_with_stdio(0); cin.tie(0);cout.tie(0)
//#define ordered_set         tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
/*

    order_of_key (k) : Number of items strictly smaller than k .
    find_by_order(k) : K-th element in a set (counting from zero).

*/
/**************************************************************************************/
                       /*Global Variables*/
const int mod = 1e9+7;
const int N = 2e5+10;
const int inf = 3e18;

/**************************************************************************************/
template <typename A>istream& operator>>(istream& input,vector<A>& x) {for(auto& i:x)input>>i;return input;}
template<typename A>ostream& operator<<(ostream& output,vector<A>& x) {for(auto& i:x)output<<i<<' ';return output;}
int add(int a, int b){return (a%mod + b%mod + mod)%mod;}
int sub(int a, int b){return (a%mod - b%mod + mod)%mod;}
int mul(int a, int b){return ((a%mod)*(b%mod) + mod)%mod;}
int Power(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)res*=a;
        a*=a;
        b>>=1;
    }
    return res;
}
signed main()
{
    FastIO;
    int T=1;
    //cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        vi a(n);
        cin>>a;
        int ans =1;
        int k=1e18;
        sort(all(a));
        bool ok=true;
        for(auto it:a)
        {
            if(ans==0)
            {
                cout<<0<<"\n";
                ok=false;
                break;
            }
            if(it>(k/ans))
            {
                cout<<-1<<"\n";
                ok=false;
                break;
            }
            else ans*=it;
        }
        if(ok)cout<<ans<<"\n";
    }

}
/*
|| Do what you can with all you have,wherever you are. ||

|| Knowing is not enough, we must apply. Wishing is not enough, we must do. ||

|| A goal is a dream with deadline. ||

|| Whether you think you can or you think you can't, you're right. ||

|| A year from now you may wish you had started today ||
*/



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

int N, M, X[100000], d[100000], sum = 0;

int main() {
    cin >> N >> M;
    for (int i = 0; i < M; ++i){
      	cin >> X[i];
    }
    sort(X, X+M);
    for (int i = 0; i < M - 1; ++i){
        d[i] = X[i+1] - X[i];
        sum += X[i+1] - X[i];
    }

    sort(d, d+M-1, greater<>());
    for (int i = 0; i < N - 1; ++i){
        sum -= d[i];
    }

    cout << sum << endl;
}


Measured memory_bytes: 1024
/*   LazyBones
*
*/

#include <bits/stdc++.h>
#include<cctype>
#include <sstream>
#include<ctime>
using namespace std;
#define rep(i,b) for(int i=0;i<b;i++)
#define getarr(a,n) for(int i=0;i<n;i++){cin>>a[i];}
#define disparr(a,n) for(int i=0;i<n;i++){cout<<a[i];}cout<<"\n";
#define disparrs(a,n) for(int i=0;i<n;i++){cout<<a[i]<<" ";}cout<<"\n";
#define disparrl(a,n) for(int i=0;i<n;i++){cout<<a[i]<<"\n";}cout<<"\n";
#define mem0(a) memset(a,0,sizeof(a));
#define ull unsigned long long int
#define ll long long int
#define ld long double
#define key pair<ld,ld>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define si set<int>
#define vii vector<pair<int,int> >
#define vi vector<int>
#define vll vector<ll>
#define vb vector<bool>
#define vvi vector<vector<int>>
#define vs vector<string>
#define all(v) v.begin(),v.end()
#define pb push_back
#define pob pop_back
#define pof pop_front
#define pf push_front
#define mp make_pair
#define F first
#define S second
//#define nu 100001
#define M 1000000007
#define mul(x,y) ((ll)(x)*(y))%M
#define tr(c,i) for(auto i = (c).begin(); i != (c).end(); i++)
#define fastio  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define INF 0x3f3f3f3f
#define MOD 998244353

int MODU(int a, int b)
{
    if(a>b)
    return a-b;
    else
    return b-a;
}
ll max3(ll a,ll b,ll c)
{
    return max(c,max(a,b));
}
ll power(ll x,ll y, ll p)
{
    ll res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
ll max(ll a,ll b)
{
    return (a>b)?a:b;
}
ll min(ll a,ll b)
{
    return (a<b)?a:b;
}
ld min(ld a,ld b)
{
    return (a<b)?a:b;
}
ll gcd(ll a,ll b)
{
    if(b==1)
    return 1;
    else if(a%b==0)
    return b;
    else
    return gcd(b,a%b);
}
ll mod(ll x){
    if(x>=0)
    return x;
    else
    return -x;
}
ll lcm(ll a,ll b){
    return (a*b)/gcd(a,b);
}

void cycle(vll c,vi& v,int u, ll& val,vi& len,int ini){
    //cout<<u<<endl;
    v[u]=1;
    if(c[u]==u){
        v[u]=2;
        val=1;
        return;
    }
    if(v[c[u]]==2){
        return;
    }
    if (v[c[u]]==1){
        if(v[c[u]]!=ini)
            return;
        val=len[u]+1-len[c[u]];
        //cout<<val<<" hf"<<endl;
        v[u]=2;
        return;
    }
    len[c[u]]=len[u]+1;
    //cout<<u<<endl;
    cycle(c,v,c[u],val,len,ini);
    v[u]=2;
    return;

}



int main()
{
    fastio;
    int n,m;
    cin>>n>>m;
    multimap<int,int> m1;
    rep(i,n){
        int a,b;
        cin>>a>>b;
        m1.insert(pii (a,b));
    }
    ll res=0;
    ll tot=0;
    for(auto it=m1.begin();it!=m1.end();it++){
        if(tot+it->S>=m){
            res+=(m-tot)*(ll)it->F;
            break;
        }
        tot+=it->S;
        res+=((ll)it->S*(ll)it->F);
    }
    cout<<res;
}


Measured memory_bytes: 4992
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; ++i) {
            A[i] = sc.nextInt();
        }
        sc.close();

        int ans = 0;
        for (int i = 0; i < N; ++i) {
            while (i + 1 < N && A[i] == A[i + 1]) {
                ++i;
            }
            if (i + 1 < N && A[i] < A[i + 1]) {
                while (i + 1 < N && A[i] <= A[i + 1]) {
                    ++i;
                }
            } else if (i + 1 < N && A[i] > A[i + 1]) {
                while (i + 1 < N && A[i] >= A[i + 1]) {
                    ++i;
                }
            }
            ++ans;
        }

        System.out.println(ans);
    }
}

Measured memory_bytes: 49160
const main = (input) => {
  input = input.split(' ');
  const A = parseInt(input[0], 10);
  const B = parseInt(input[1], 10);
  const C = parseInt(input[2], 10);
  
  if (A+B>=C) {
    console.log("Yes");
  }else{
    console.log("No");
  }
  
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 9420
import std.stdio, std.algorithm, std.conv, std.array, std.string;

void main()
{
    readln;
    auto ts = readln.split.to!(long[]);
    auto m = readln.chomp.to!int;

    long d;
    long sum = ts.sum;

    foreach (_; 0..m) {
        auto px = readln.split;
        auto p = px[0].to!int;
        auto x = px[1].to!long;

        sum += d;
        d = ts[p-1] - x;
        writeln(sum -= d);
    }
}

Measured memory_bytes: 256
//#pragma once
#include <stdio.h>
#include <string>
#include <iostream>
#include <queue>
#include <algorithm>
#include <sstream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <numeric>
#include<bitset>

using namespace std;
#define modd 1000000007


typedef pair<long long, long long> pl;



#define ll long long




/*
class UnionFind {
public:
	vector <ll> par; 
	vector <ll> siz;
	vector <ll> gr;

	// Constructor
	UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) ,gr(sz_){
		for (ll i = 0; i < sz_; ++i) par[i] = i; 
	}
	void init(ll sz_) {
		par.resize(sz_);
		siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
		for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
	}

	// Member Function
	// Find
	ll root(ll x) { // 根の検索
		while (par[x] != x) {
			x = par[x] = par[par[x]]; // x の親の親を x の親とする
		}
		return x;
	}

	// Union(Unite, Merge)
	bool merge(ll x, ll y) {
		x = root(x);
		y = root(y);
		if (x == y) return false;

		// merge technique（データ構造をマージするテク．小を大にくっつける）
		if (siz[x] < siz[y]) swap(x, y);
		siz[x] += siz[y];
		par[y] = x;
		return true;
	}



	bool issame(ll x, ll y) { // 連結判定
		return root(x) == root(y);
	}

	ll size(ll x) { // 素集合のサイズ
		return siz[root(x)];
	}


};*/


long long N, M, K, a, b, c, d,e, H, W,L;
long long A[200005] = {};
long long B[200005] = {};
long long C[200005] = {};
long long D[200005] = {};
long long E[200005] = {};
bool f, ff;
string S;
set <long long>sll;
pl bufpl;
vector <long long>vl;
vector <pl>vpl;
vector <string> vs;
set<ll> llset;

/*struct ST
{
	long long Kati;
	int bangou;

	bool operator<(const ST& another) const
	{
		return Kati < another.Kati;//比較
	};

};



vector <ST> vst;
ST st[200005];
ST bufst;
bitset<5000> bits;*/


long long modinv(long long aa, long long mm) {
	long long bb = mm, uu = 1, vv = 0;
	while (bb) {
		long long tt = aa / bb;
		aa -= tt * bb; swap(aa, bb);
		uu -= tt * vv; swap(uu, vv);
	}
	uu %= mm;
	if (uu < 0) uu += mm;
	return uu;
}


bool fs[2005][2005] = {};

int main() {


	cin >> N;

	
	cout << N/3 << endl;
	
	return 0;

}


Measured memory_bytes: 2304
#include <iostream>
using namespace std;
int main() {
	int N;
	cin >> N;
	int answer = 0;
	for (int C = 1; C <= N; C += 2) {
		int num_of_divisors = 0;
		for (int X = 1; X <= C; ++X) {
			if (C % X == 0) {
				++num_of_divisors;
			}
		}
		if (num_of_divisors == 8) {
			++answer;
		}
	}
	cout << answer << '\n';
	return 0;
}


Measured memory_bytes: 3572
package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"os"
	"strconv"
	"strings"
)

func main() {
	N := getStdinInt()
	X := getStdin()

	var cnt int64 = 0
	for i := 0; i < len(X); i++ {
		if X[i] == '1' {
			cnt++
		}
	}

	if cnt == 0 {
		for i := 0; i < N; i++ {
			fmt.Printf("%d\n", 1)
		}
		return
	} else if cnt == 1 {
		for i := 0; i < N; i++ {
			if X[i] == '0' {
				if i == N-1 || X[N-1] == '1' {
					// num % 2 なので下1桁が1の場合にはf(num)→f(1)→0
					fmt.Printf("%d\n", 2)
				} else {
					fmt.Printf("%d\n", 1)
				}
			} else {
				fmt.Printf("%d\n", 0)
			}
		}
		return
	}

	val0 := make(map[int]int64) // cnt - 1
	var sum0 int64 = 0          // cnt - 1
	val1 := make(map[int]int64) // cnt + 1
	var sum1 int64 = 0          // cnt + 1

	// 合計を先に求める
	for i := N - 1; i >= 0; i-- {
		if i == N-1 {
			val0[i] = 1
		} else {
			val0[i] = (2 * val0[i+1]) % (cnt - 1)
		}
		if X[i] == '1' {
			sum0 = modadd(sum0, val0[i], cnt-1)
		}
	}
	for i := N - 1; i >= 0; i-- {
		if i == N-1 {
			val1[i] = 1
		} else {
			val1[i] = 2 * val1[i+1] % (cnt + 1)
		}
		if X[i] == '1' {
			sum1 = modadd(sum1, val1[i], cnt+1)
		}
	}

	for i := 0; i < N; i++ {
		if X[i] == '0' {
			// X(i)分足す
			sum := modadd(sum1, val1[i], cnt+1)
			fmt.Printf("%d\n", pops(sum, cnt+1))
		} else {
			// X(i)分引く
			sum := modadd(sum0, -val0[i], cnt-1)
			fmt.Printf("%d\n", pops(sum, cnt-1))
		}
	}
}

// マイナスのmodに注意
func modadd(a, b, mod int64) int64 {
	var rtn int64 = 0
	if a+b < 0 {
		rtn = (a + b + mod) % mod
	} else {
		rtn = (a + b) % mod
	}
	return rtn
}

// f(num1)→f(num2)→...→0とする
func pops(num, mod int64) int64 {
	if mod == 1 {
		return 1
	}

	var ans int64 = 1
	for num != 0 {
		var cnt int64 = 0
		for i := 0; (1 << i) <= num; i++ {
			if num&(1<<i) != 0 {
				cnt++
			}
		}
		if cnt != 0 {
			num %= cnt
		}
		ans++
		if cnt == 0 {
			break
		}
	}
	return ans
}

func popcount(n uint64) int {
	return bits.OnesCount64(n)
}

var sc = bufio.NewReaderSize(os.Stdin, 1024*1024*10)

func getStdin() string {
	return readLine()
}
func getStdinInt() int {
	str := getStdin()
	rtn, _ := strconv.Atoi(str)
	return rtn
}
func getStdinInt2() (int, int) {
	list := getStdinIntArr()
	return list[0], list[1]
}
func getStdinInt3() (int, int, int) {
	list := getStdinIntArr()
	return list[0], list[1], list[2]
}
func getStdinInt64() int64 {
	str := getStdin()
	rtn, _ := strconv.ParseInt(str, 10, 64)
	return rtn
}
func getStdinInt64_2() (int64, int64) {
	list := getStdinIntArr64()
	return list[0], list[1]
}
func getStdinInt64_3() (int64, int64, int64) {
	list := getStdinIntArr64()
	return list[0], list[1], list[2]
}
func getStdinIntArr() []int {
	str := getStdin()
	list := strings.Split(str, " ")
	rtn := make([]int, len(list))
	for idx, val := range list {
		rtn[idx], _ = strconv.Atoi(val)
	}
	return rtn
}
func getStdinIntArr64() []int64 {
	str := getStdin()
	list := strings.Split(str, " ")
	rtn := make([]int64, len(list))
	for idx, val := range list {
		rtn[idx], _ = strconv.ParseInt(val, 10, 64)
	}
	return rtn
}
func readLine() string {
	buf := make([]byte, 0, 0)
	for {
		l, p, _ := sc.ReadLine()
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}


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

#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define read()          freopen("in.txt","r",stdin)
#define write()         freopen("out.txt","w",stdout)
#define sf(n)           scanf("%d",&n)
#define sfd(n)          scanf("%lf",&n)
#define sl(x)           scanf("%I64d",&x)
#define sfl(n)          scanf("%lld", &n)
#define sfc(n)          scanf(" %c",&n)
#define sful(n)         scanf("%llu",&n)
#define ull             unsigned long long
#define endll           pf("\n")
#define pf              printf
#define PI              acos(-1.0)
#define eps             1e-12
#define mem(a,b)        memset(a,b,sizeof(a))
#define pb              push_back
#define xx              first
#define yy              second
#define pii             pair<int, int>
#define pll             pair<ll, ll>
#define MP make_pair
#define ll              long long
#define uniq(a)      a.erase(unique(a.begin(), a.end()), a.end())
#define cnd tree[idx]
#define lnd tree[idx<<1]
#define rnd tree[(idx<<1)+1]
#define lndp (idx<<1),(b),((b+e)>>1)
#define rndp ((idx<<1)+1),(((b+e)>>1)+1),(e)
#define inf 1999999999
#define MOD  998244353
#define mod1 1000000009
#define var    int n,m,i,j,c=0,t,l,r,mid,z=0,k,x,y
#define aloc(n,t) ((t*)malloc((n)*sizeof(t)))

int dx[8]={0,0,1,1,-1,-1,1,-1};  //8 direction
int dy[8]={1,-1,1,-1,1,-1,0,0};
//int dx[4]={1,-1,0,0};  //4 direction
//int dy[4]={0,0,1,-1};

int n,m,a[200005];

int main()
{
    sf(n);
    cout<<(n^1)<<endl;
}


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

#define ll long long

int main(){
	ll n;
	cin >> n;
	if (n <= 104) {cout << 0 << endl;}
	else if (105 <= n && n <= 134) {cout << 1 << endl;}
	else if (135 <= n && n <= 164) {cout << 2 << endl;}
	else if (165 <= n && n <= 188) {cout << 3 << endl;}
	else if (189 <= n && n <= 194) {cout << 4 << endl;}
	else if (194 <= n) {cout << 5 << endl;}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,Sum;
  cin >> N ;
 
  for(int i=0;i<N;i++){
    int l,r;
    cin >> l>>r;
    Sum+=(r-l+1);
  }
  cout<<Sum<<endl;
}

Measured memory_bytes: 256
#include <iostream>

int main() {
	int n,a[100];
	std::cin >> n;
	for (int i = 0; i < n; i++) 
		std::cin >> a[i];
		for (int i = n - 1; i >= 0; i--)
			std::cout << a[i] << (i == 0 ? '\n' : ' ');
	}


Measured memory_bytes: 3088
#include<bits/stdc++.h>
using namespace std;
long long di(long long a)
{
	if(a<0)
	return 0-a;
	else return a;
}
int main()
{
	long long x,k,d;
	cin>>x>>k>>d;
	x=di(x);
	
	if(x/d>=k)
	x-=k*d;
	else {
		long long a=x/d;
		k-=x/d;
		x-=a*d;
		if(k&1)
		x=min(di(x+d),di(x-d));
	}
	cout<<x<<endl;
	return 0;
}

Measured memory_bytes: 3616
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <math.h>
#define rep(i, a, b) for(int i = a; i < (b); ++i)
using namespace std;
typedef long long ll;
 
vector<pair<int, int>> to[100010];
bool visited[100010];
ll dist[100010];
ll gcd(ll a, ll b)
{
   if (b == 0)
   {
       return a;
   }
    return gcd(b, a%b);
}
void dfs(int now, ll d) {
  visited[now] = true;
  dist[now] = d;
  for (auto p : to[now]) {
    if (visited[p.first]) continue;
    dfs(p.first, d + p.second);
  }
}
vector<int>ans(10005,0);
void f(ll n){
    for (ll x = 1; x*x<n;x++){
        for (ll y = 1; y*y<n;y++){
            for (ll z = 1; z*z<n;z++){
                ll v = (x*x)+(y*y)+(z*z)+(x*y)+(y*z)+(z*x);
                if(v<10005) ans[v]++;
            }
        }
    }
}
int find(ll k) {
    ll tag = 7777777;
    int cnt = 0;
    cout << tag%k << endl;
    while (tag%k) {
        cnt++;
        tag/=10;
        cout << tag << endl;
        
    }
    return cnt;
}
 
int main() {
    string s;
    cin >> s;
    if(s == "SRS"){
        cout << "1" << endl;
    }else if (s == "RSR"){
        cout << "1" << endl;
    }else if (s == "RSS"){
        cout << "1" << endl;
    }else if (s == "SSR"){
        cout << "1" << endl;
    }else if (s == "SRR"){
        cout << "2" << endl;
    }else if (s == "RRS"){
        cout << "2" << endl;
    }else if (s == "RRR"){
        cout << "3" << endl;
    }else {
       cout << "0" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 6020