akhauriyash/Code-Regression huggingface dataset:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

A = [LIST() for _ in range(3)]
N = INT()
b = [INT() for _ in range(N)]

for n in b:
  for i in range(3):
    for j in range(3):
      if A[i][j] == n:
        A[i][j] = 0
        
for i in range(3):
  if sum(A[i]) == 0:
    print("Yes")
    exit()
    
for i in range(3):
  if A[0][i] + A[1][i] + A[2][i] == 0:
    print("Yes")
    exit()
    
if A[0][0] + A[1][1] + A[2][2] == 0:
  print("Yes")
  exit()
  
if A[0][2] + A[1][1] + A[2][0] == 0:
  print("Yes")
  exit()
  
print("No")

Measured memory_bytes: 5204
#define	_USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <string>
#include <set>
#include <complex>
using namespace std;
int main(){
	
	int n;
	string s;
	
	while(cin>>n,n!=0){
		cin>>s;
		while(n--){
		int count=1;
		string a="";
		char c =s[0];
		for(int i=1;i<s.size();i++){
			if(c==s[i])
				count++;
			else{
				a=a+to_string(count)+c;
				c=s[i];
				count=1;
			}
			
		}
		a=a+to_string(count)+c;
		s=a;
	}
	cout<<s<<endl;
	}
	
}

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

#define rep(i, n) for(int i = 0; i < n; ++i)
#define all(a) a.begin(), a.end()
#define ll long long
#define mod 1e9+7

using namespace std;

int main()
{
  ll n, x;
  cin >> n >> x;
  vector<ll> a(n);

  ll cnt = 0;
  ll prev = 0;

  rep(i, n) {
    ll tmp;
    cin >> tmp;
    if (tmp > x) {
      cnt += tmp - x;
      a[i] = x;
    } else {
      a[i] = tmp;
    }

    if (prev + a[i] > x) {
      ll diff = prev + a[i] - x;
      a[i] -= diff;
      cnt += diff;
    }
    prev = a[i];
  }

  cout << cnt << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

int A, B;

int main() {
	cin >> A >> B;
	cout << max({ A + B,A - B,A*B }) << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
  int x,i;
  int a[100];

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

  for(i = 0;i < x-1;i++){
    printf("%d ",a[x-i-1]);
  }
 
  printf("%d\n",a[0]);
  return 0;
}

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

#define db(x) cout<<x<<'\n'
#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define repi(i,n) for(int i=0;i<(n);++i)
//#define repA(i,a,n) for(int i=a;i<=(n);++i)
//#define repD(i,a,n) for(int i=a;i>=(n);--i)
#define ll long long int
#define endl '\n'
#define lld long long double
#define vi vector<int> 
#define vl vector<ll> 
#define vb vector<bool> 
#define vvi vector<vector<int>  >
#define err(t) cout<<"Error : "<<t<<endl;
#define all(v) v.begin(),v.end()
#define mp make_pair
#define M 100000
#define MD 1000000007 //998244353
#define pb push_back
#define rep(i,a,b) for(ll i = a; i <= (b); i++)
#define pii pair<int,int>
#define pll pair<ll,ll> 
#define vec(a) vector<a >
#define se second
#define fi first
#define inf 0xffffffff
#define inchar getchar_unlocked
#define outchar(x) putchar_unlocked(x)
//template <typename T>
//using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll binpow(ll a,ll b){	if(a==0) return 0; if(b==0) return 1;ll ans=1;while(b>0){if(b&1) ans=ans*a; a=a*a; b=b>>1;}	return ans;}
template <typename T> 
T Min(T a,T b){ return a<b?a:b; }
template <typename T>
T Max(T a,T b){ return a>b?a:b; }

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	// int n;cin>>n;
	// string s;cin>>s;
	
	//ll n;cin>>n; vl a(n); repi(i,n) cin>>a[i];
	int n,l;
	cin>>n>>l;
	vector<string> a(n); repi(i,n) cin>>a[i];
	sort(all(a));
	repi(i,n) cout<<a[i]; cout<<endl;
	
	/*
	int test1;cin>>test1;while(test1--){ 
				
	 }
	 //*/
return 0;
}



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

const int MAX=200;
int a[MAX];

void print(int a[], int n)
{
	for(int i=0;i<n;i++){
		if(i!=0)
			cout << " ";
		cout << a[i];
	}
	cout << endl;
}

int main()
{
	int n;
	cin >> n;
	for(int i=0;i<n;i++)
		cin >> a[i];
	
	print(a, n);	
	for(int i=1;i<n;i++)
	{
		int k=a[i];
		int j=i-1;
		while(a[j]>=0 && a[j]>k){
			a[j+1]=a[j];
			j--;
		}
			a[j+1]=k;
		print(a, n);
	}
	
	return 0;
}


Measured memory_bytes: 3068
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Comparator.reverseOrder());
        
        while (true) {
            String order = sc.next();
            if (order.startsWith("i")) {
                pq.add(sc.nextInt());

            } else if (order.startsWith("ex")) {
                System.out.println(pq.poll());

            } else {
                break;
            }
        }
    }
}



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

typedef long long ll;
ll all[55],ap[55];
ll solve(int n,ll x);

int main(void){
  int n;
  ll x,ans;
  cin >> n >> x;
  all[0]=ap[0]=1;
  for (int i=1;i<=n;i++){
    all[i]=all[i-1]*2+3;
    ap[i]=ap[i-1]*2+1;
  }
  ans=solve(n,x);
  cout << ans << endl;
  return 0;
}

ll solve(int n,ll x){
  if (n==0) return x;
  if (x<=n) return 0;
  if (x==all[n]) return ap[n];
  if (x<=all[n-1]+1) return solve(n-1,x-1);
  if (x==all[n-1]+2) return ap[n-1]+1;
  return ap[n-1]+solve(n-1,x-all[n-1]-2)+1;
}

Measured memory_bytes: 256
import bisect
import sys
def input():
    return sys.stdin.readline().strip()
S = []
count = {}
total = 0

for _ in range(int(input())):
    order = tuple(map(int,input().split()))
    value = order[1]
    if order[0] == 0:
        if value in count:
            count[value] += 1
        else:
            count[value] = 1
            bisect.insort(S,value)
        total += 1
        print(total)
    elif order[0] == 1:
        if value in count:
            print(count[value])
        else:
            print(0)
    elif order[0] == 2:
        if value in count:
            total -= count[value]
            count[value] = 0

    else:
        left = bisect.bisect_left(S,order[1])
        right = bisect.bisect(S,order[2])

        out = []

        for i in range(left,right):
            out += [S[i]]*count[S[i]]
        
        for i in out:
            print(i)
"""  
    print(S)
    print(count)
"""


Measured memory_bytes: 18332
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
using namespace std;
int main(){
  int a[4]={0},b[10]={0};
  for(int i=0;i<4;i++) cin>>a[i];
  for(int i=0;i<4;i++){
    b[a[i]]=1;
  }
  if(b[1]>0&&b[4]>0&&b[7]>0&&b[9]>0) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}


Measured memory_bytes: 256
/* Your prologue will be the story. */
/* Copyright by HenryLi */
#include<iostream>
#include<algorithm>
#include<queue>
#include<string>
#include<map>
#include<vector>
#include<set>
#include<sstream>
#include<stack>
#include<ctime>
#include<cmath>
#include<cctype>
#include<climits>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<iomanip>
#include<bitset>
#include<complex>
using namespace std;
template <class _T> inline void read(_T &_x) {
	int _t; bool _flag=false;
	while((_t=getchar())!='-'&&(_t<'0'||_t>'9')) ;
	if(_t=='-') _flag=true,_t=getchar(); _x=_t-'0';
	while((_t=getchar())>='0'&&_t<='9') _x=_x*10+_t-'0';
	if(_flag) _x=-_x;
}
typedef long long LL;
int a, b, c, d;
int main() {
	//freopen("A.in","r",stdin);
	//freopen("A.out","w",stdout);
	read(a), read(b), read(c), read(d);
	cout << ((d & 1) ? b - a : a - b) << endl;
	return 0;
}



Measured memory_bytes: 256
a = []
for i in range(5):
    a.append(int(input()))
k = int(input())
ans = 0
for i in range(4):
    for j in range(i+1, 5):
        if a[j] - a[i] > k:
            ans = 1
if ans == 1:
    print(':(')
else:
    print('Yay!')

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ll unsigned long long int
#define mod 998244353 
#define pb push_back
//#define mp make_pair
#define INF 2000000011LL
#define INFLL 1000000000000000011LL
#define eps 1e-9
#define pp pair < pair<ll,ll> , ll> 
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define foll(i,j,k) for(ll i=j;i<=k;i++)
#define clr(a) memset(a,0,sizeof(a))
#define vi vector<int>
#define vll vector<ll>
#define sz(a) a.size()
#define len(a) a.length()
#define all(a) a.begin(),a.end()
#define io_file freopen("Contest/input_file.in", "r", stdin); freopen("Contest/output_file.in", "w", stdout)

const int MAXN = 2e5+5;
using namespace std;
ll power(ll x, ll y)
{
  ll res = 1;
  while(y>0)
  {
    if(y&1)
       {
         res = (res*x)%mod;
        }
     x = (x*x)%mod;
     y = y>>1;
  }
    return res;
}
// std::vector<ll> divi[100004];
// void divisor(int n)
// {
//    for(ll i=1;i<=n;i++)
//    {
//      for(ll j=i;j<=n;j+=i)
//      {
//        divi[j].pb(i);
//      }
//    }
// }



ll n;
ll a[200005];
map<ll,ll>m;

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

}



Measured memory_bytes: 14336
/*input
6 1
6 5 2 5 3 2
*/
#include<bits/stdc++.h>
using namespace std;

#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test int t;cin>>t;while(t--)
#define X first
#define Y second
#define pb push_back
#define all(s) s.begin(),s.end()

typedef pair<int,int> ii;
typedef long long ll;

const int MOD = 1e9+7;


void solve(){
    ll n,k;
    cin >> n >> k;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin >> arr[i];
        arr[i]--;
    }
    ll len=0,cycle=0,starting;
    bool vis[n] = {false};
    for(int i=0;i<n;i++)
        vis[i] = false;

    int i =0;
    while(true){
        // cout << i+1 << "\n";
        if(vis[i]){
            starting = i;
            break;
        }
        vis[i] = true;
        i = arr[i];
    }
    // cout << starting+1 << "\n";
    i = 0;
    vector<int> arr1,arr2;
    while(i!=starting){
        len++;
        arr1.push_back(i);
        i = arr[i];
    }
    // for(auto it: arr1)
    //     cout << it+1 << " ";
    // cout << "\n";
    // cout << len << "\n";
    // memset(vis,false,sizeof(vis));
    for(int j=0;j<n;j++)
        vis[j] = false;
    if(len==0)
        starting = 0;
    i=starting;

    while(!vis[i]){
        cycle++;
        arr2.push_back(i);
        vis[i] = true;
        i = arr[i];
    }
    // cout << starting+1 << " " << len << " " << cycle << "\n";
    
    // for(auto it: arr2)
    //     cout << it+1 << " ";
    // cout << "\n";
    if(k<len){
        cout << arr1[k]+1 << "\n";
        return;
    }
    k -= len;
    k %= cycle;
    cout << arr2[k]+1 << "\n";
}

int main(){
    FIN;   
    // test
    solve();
}

Measured memory_bytes: 5264
#include <bits/stdc++.h>
using namespace std;
string s;
int main(){
	cin>>s;int n=s.size(),ans;
	ans=n;
	for(int i=1;i<n;i++)
		if(s[i]!=s[i-1])
			ans=min(ans,max(i,n-i));
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 512
package main

import (
	"fmt"
	"os"
	"strconv"
	"strings"
	"bufio"
	"sort"
)

var (
	sc = bufio.NewScanner(os.Stdin)
	buf = make([]byte, 1000)
)

func scanText() string{
	sc.Scan()
	return sc.Text()
}

func scanTextArray(n int) []string {
	out := make([]string, n)
	for i, v := range(strings.Split(scanText(), "")) {
		out[i] = v
	}
	return out
}

func scanInt() int {
	out, e := strconv.Atoi(scanText())
	if e != nil {
        panic(e)
    }
	return out
}

func scanIntArray(n int) []int {
	out := make([]int, n)
	for i, v := range(strings.Split(scanText(), " ")) {
		num, e := strconv.Atoi(v)
		if e != nil {
			panic(e)
		}
		out[i] = num
	}
	return out
}
//  template end

// Request start
type Request struct {
	Start int
	End int
}

type Requests []Request

func (r Requests) Remove(i int) {
	if i == len(r)-1 {
		r = r[:i]
	} else {
		r = append(r[:i], r[i+1:]...)
	}
}

func (r Requests) Len() int{
	return len(r)
}

func (r Requests) Swap(i, j int) {
	r[i], r[j] = r[j], r[i]
}

type ByStart struct {
	Requests
}

func (b ByStart) Less(i, j int) bool {
	return b.Requests[i].Start < b.Requests[j].Start
}

type ByEnd struct {
	Requests
}

func (b ByEnd) Less(i, j int) bool {
	return b.Requests[i].End < b.Requests[j].End
}
// Request end




var (
	requests = make(Requests, 0)
	N, M = 0, 0
	ans = 1
)

func f() {
	be := ByEnd{requests}
	sort.Sort(be)
	end := be.Requests[0].End
	for i:=1; i<len(be.Requests); i++ {
		req := be.Requests[i]
		if req.Start >= end {
			end = req.End
			ans++
		}
	}
	fmt.Println(ans)
}

func main() {
	sc.Buffer(buf, 10000)
	nm := scanIntArray(2)
	N, M = nm[0], nm[1]
	requests = make(Requests, M)
	for i:=0; i<M; i++ {
		ab := scanIntArray(2)
		requests[i] = Request{Start : ab[0], End : ab[1]}
	}
	f()
}

Measured memory_bytes: 4992
#include <iostream>
#include <vector>
#include <cstring>

constexpr int MAX_N=(int)1e5;

int n;

std::vector<int> G[MAX_N];

bool used[MAX_N];

int path[MAX_N];

std::vector<int> vec;

bool search(int s,int t){

    path[s]=1;

    vec.emplace_back(s);

    if(s==t)
        return true;

    for(int i=0;i<G[s].size();++i){
        int to=G[s][i];
        if(!path[to]&&search(to,t))
            return true;
    }

    vec.pop_back();

    path[s]=0;

    return false;
}

void paint(){
    for(int i=(vec.size()+1)/2;i<vec.size();++i)
        path[vec[i]]=2;
}

int dfs(int m,int c){

    used[m]=true;

    int res=1;

    for(auto&& to : G[m]){
        if(!used[to]&&(path[to]==0||path[to]==c))
            res+=dfs(to,c);
    }

    used[m]=false;

    return res;
}

int main() {

    std::cin>>n;

    int a,b;

    for(int i=0;i<n-1;++i){
        std::cin>>a>>b;
        G[a-1].emplace_back(b-1);
        G[b-1].emplace_back(a-1);
    }

    search(0,n-1);

    paint();

    int fst=dfs(0,1);
    std::memset(used,false,sizeof(used));
    int snd=dfs(n-1,2);

    if(fst>snd)
        std::cout<<"Fennec"<<std::endl;
    else
        std::cout<<"Snuke"<<std::endl;

    return 0;
}

Measured memory_bytes: 11384
#include<bits/stdc++.h>
#define lint long long int
#define rep(i,n) for(int i=0;i<int(n);i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define arep(i,a,n) for(int i=a;i<n;i++)
#define sort(a) sort(a.begin(),a.end())
#define reverse(a) reverse(a.begin(),a.end())
#define fill(a,x) fill(a.begin(),a.end(),x)
#define eb(data) emplace_back(data)
#define pb(data) emplace_back(data)
#define mp make_pair
#define ALNUM 26
#define vint vector<int>
#define vlint vector<lint>
#define F first
#define S second
#define ALL(data) data.begin(),data.end()
#define GEts(s) getline(cin,s);
#define UNIQUE(vec) vec.erase(unique(vec.begin(), vec.end()), vec.end())

using namespace std;
template<typename Rast>inline void out(Rast rast){cout<<rast<<"\n";return;}
template<typename Rast>inline void in(Rast& rast){cin>>rast;return;}
template<typename T>istream& operator >> (istream& is, vector<T>& vec){for(T& x: vec) is >> x;return is;}
template<typename First, typename... Rest>void in(First& first, Rest&... rest){cin >> first;in(rest...);return;}
template<typename First, typename... Rest>void out(First first, Rest... rest){cout << first<<" ";out(rest...);return;}
template<typename T>T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template<typename T1,typename T2>bool chmax(T1& a,T2 b){if(a<b){a=b;return true;}else{return false;}}
template<typename T1,typename T2>bool chmin(T1& a,T2 b){if(a>b){a=b;return true;}else{return false;}}
template<typename T>T lcm(T a, T b){return a * b / gcd(a, b);}
static const double pi = 3.141592653589793;
int modpow(int a,int n,int p){if (n==0)return 1%p; if(n==1)return a%p;if(n%2==1)return (a*modpow(a,n-1,p))%p;lint t=modpow(a,n/2,p);return (t*t)%p;}//a^n%p
lint MOD=pow(10,9)+7;
//lint MOD=998244353;
lint inf=pow(2,50);
int intinf=pow(2,30);
/**int dirx[]={1,0};int diry[]={0,1};//*///右、下
/**int dirx[]={0,1,0,-1};int diry[]={-1,0,1,0};//*///四方位
/**int dirx[]={-1,0,1,1,1,0,-1,-1};int diry[]={-1,-1,-1,0,1,1,1,0};//*///八方位


class unionfind{
public:
	vector<int> table;
	void init(int size){
		table.resize(size);
		rep(i,size)table[i]=i;
	};
	int root(int index){
		if(table[index]==index)return index;
		else{
			int hoge=root(table[index]);
			table[index]=hoge;
			return hoge;
		}
	};
	bool same(int x,int y){
		return(root(x)==root(y));
	};
	int marge(int x,int y){
		int yroot=root(y);
		int xroot=root(x);
		if(xroot==yroot)return 0;
		table[yroot]=xroot;
		return 0;
	}
};



int main(){
	cin.tie(0);ios::sync_with_stdio(false);cout<<std::fixed<<std::setprecision(19);
	lint n,d;
	in(n,d);
	int count=0;
	rep(i,n){
		lint x,y;
		in(x,y);
		lint dis=x*x+y*y;
		if(dis<=d*d)count++;
	}
	out(count);
	return 0;
}


Measured memory_bytes: 3640
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <algorithm>
#include <array>
#include <complex>
#include <string>
#include <utility>
int main(){
    int x,y,n;
    std::cin >> x >> y;
    std::string s;
    std::cin >> s;
    for(int i=0;i<x+y+1;i++){
        
        if(i!=x&&s[i]=='-'){
            std::cout << "No" << std::endl;
            return 0;
        }
        if(i==x&&s[i]!='-'){
            std::cout << "No" << std::endl;
            return 0;
        }
    }
    std::cout << "Yes";
    std::cout << std::endl;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(int(1e6))

N = int(input())
xy = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    xy[i] = (x, y)

import itertools
seq = list(itertools.permutations(range(N)))
ds = [0] * N
route_d = [0] * len(seq)
dists = {}
k = 0
for route in seq:
    d = 0
    i = route[0]
    for j in route[1:]:
        vec = (i, j) if (i < j) else (j, i)
        if not (vec in dists):
            import math
            dx = xy[j][0] - xy[i][0]
            dy = xy[j][1] - xy[i][1]
            dists[vec] = math.sqrt(dx**2 + dy**2)
        d += dists[vec]
        i = j
    route_d[k] = d
    k += 1

ans = sum(route_d) / len(route_d)

print(ans)


Measured memory_bytes: 9328
#include<stdio.h>
#define N 100000
#define Q 50000
int binarySearch(int,int,int*);

int main(){
  int n,q,i,c = 0;
  int S[N],T[Q];
  
  scanf("%d",&n);
  for(i = 0; i < n; i++)
    scanf("%d",&S[i]);
  scanf("%d",&q);
  for(i = 0; i < q; i++){
    scanf("%d",&T[i]);
    c += binarySearch(n,T[i],S);
  }
  printf("%d\n",c);
  
  return 0;
}

int binarySearch(int n,int key,int a[]){
  int left = 0,right = n,mid;
  
  while(left < right){
    mid = (left + right)/2;
    if(a[mid] == key){
      return 1;
    }
    else if(key < a[mid]){
      right = mid;
    }
    else{
      left = mid + 1;
    }
  }
  return 0;
}

Measured memory_bytes: 1184
K = int(input())

a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

print(a[K-1])


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string s;
  cin>>s;
  int a=0;
  for(int i=0; i<s.size()/2; i++){
    
    if(s[i]!=s[s.size()-1-i])
      a++;
  }
  cout<<a<<endl;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main
{
  public static void main(String[] args) throws NumberFormatException, IOException
  {
    BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

    ArrayList<Float> inputList = new ArrayList<>();

    while (input.ready())
    {
      inputList.add(Float.parseFloat(input.readLine()));
    }
    final float ans = getDiffHight(inputList);
    System.out.println(ans);
  }

  private static float getDiffHight(ArrayList<Float> list)
  {
    float maxHight = Float.MIN_VALUE;
    float minHight = Float.MAX_VALUE;

    for (Float each : list)
    {
      if (each > maxHight)
      {
        maxHight = each;
      }
      if (each < minHight)
      {
        minHight = each;
      }
    }
    return maxHight - minHight;
  }
}

Measured memory_bytes: 24316
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define all(a) (a).begin(),(a).end()
#define rep(i,q) for(int i = 0; q > i; i++)
#define MOD 1000000007
int kaijo_waru(int n,int s){
  int ans = n;
  rep(i,s-1){
    ans = ans*n%MOD;
  }
  return ans;
}
int main(){
  int N;
  cin >> N;
  vector<int> A;
  int tmp;
  rep(i,N){
    cin >> tmp;
    A.push_back(tmp);
  }
  sort(all(A));
  bool ok = true;
  int kekka;
  if(N % 2 == 0){//guu
    kekka = N/2;
    int syoki = 1;
    rep(i,N){
      if(syoki + (i/2*2) != A[i]){
        ok = false;
        break;
      }
    }

  } else {//ki -
    kekka = (N - 1) / 2;
    int syoki = 0;
    rep(i,N){
      if(syoki + ((i+1)/2*2) != A[i]){
        ok = false;
        break;
      }
    }
  }
  if(N==1&&A[0]==0) cout << 1 << endl;
  else if(ok) cout << kaijo_waru(2,kekka) << endl;
  else cout << 0 << endl;
}

Measured memory_bytes: 892
#include<iostream>

using namespace std;

int main() {
	int n;
	cin >> n;
	int k = n / 4, d = n / 7;

	for (int i = 0; i <= k; i++) {
		for (int j = 0; j <= d; j++) {
			if (4 * i + 7 * j == n) {
				cout << "Yes" << endl;
				return 0;
			}
		}
	}
	cout << "No" << endl;
	
	return 0;
}

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

#define x first
#define y second
#define pb push_back
#define mp make_pair

#define all(a) (a).begin(), (a).end()
#define sz(a) (int) (a).size()

#define ll long long

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll a, b, c;
    cin >> a >> b >> c;
    cout << b+min(c, a+b+1) << '\n';
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
int main(void)
{
	int N;
	int A[200010];
	int max = 0;
	int num = 0;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
		if (i == 0) {
			max = A[i];
			num = i;
		}
		else {
			if (max < A[i]) {
				max = A[i];
				num = i;
			}
		}
	}
	sort(A, A + N);

	for (int j = 0; j < N; j++) {
		if (j == num) {
			printf("%d\n", A[N - 2]);
		}
		else {
			printf("%d\n", max);
		}
	}

	return 0;
}


Measured memory_bytes: 2432
N = int(input())
ans = 1
A = list(map(int, input().split()))
prev = A[0]
trend = 0
for a in A[1:]:
    if (a - prev) * trend < 0:
        ans += 1
        trend = 0
    elif trend == 0:
        if a - prev > 0:
            trend = 1
        elif a - prev < 0:
            trend = -1
    prev = a
print(ans)


Measured memory_bytes: 14228
# code-festival-2016-qualbB - Qualification simulator
def main():
    N, A, B = tuple(map(int, input().rstrip().split()))
    S = input().rstrip()
    ans, a, b = [], 0, 0
    for i in S:
        if i == "a":
            if a < A + B:
                ans += ["Yes"]
                a += 1
            else:
                ans += ["No"]
        elif i == "b":
            if a < A + B and b < B:
                ans += ["Yes"]
                a += 1
                b += 1
            else:
                ans += ["No"]
        else:
            ans += ["No"]
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

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

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define showall(obj) for(auto x:obj)cout<<x<<endl;
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
typedef vector<int> vint;
typedef vector<ll> vll;
const int inf = 100100100;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
	int n;
	cin>>n;
	ll ans = 0;
	rep(i,n){
		ll a;
		cin>>a;
		ans = __gcd(ans,a);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]

dp = [0] * (H+1)

for i in range(1, 1+H):
  dp[i] = 10 ** 8
  for A, B in AB:
    if i >= A:
      t = dp[i - A] + B
      if t < dp[i]:
        dp[i] = t
    else:
      if B < dp[i]:
        dp[i] = B

# print(dp)
print(dp[-1])


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

#define MAX 2000001
#define INFTY 100000000

int A[MAX+1], h, k;

void maxHeapify(int );
void increasekey(int ,int );
void insert(int );
void extract(void );

int main(){
  int k;
  char s[20];

  while(1){
    scanf("%s", s);
    
    if(s[0] == 'e' && s[1] == 'n' && s[2] == 'd') break;
    else if(s[0] == 'i' && s[1] == 'n' && s[2] == 's' && s[3] == 'e' && s[4] == 'r' && s[5] == 't'){
      scanf("%d", &k);
      insert(k);
    }
    else if(s[0]=='e' && s[1] == 'x' && s[2] == 't' && s[3] == 'r' && s[4] == 'a' && s[5] == 'c' && s[6] == 't')
      extract();
  }

  return 0;
}



void maxHeapify(int k){
  int temp;
  int left, right, big;
  int e;
  
  left = 2*k;
  right = 2*k+1;

  if(left <= h && A[k] < A[left]) big = left;
  else big = k;
  
  if(right <= h && A[big] < A[right]) big = right;
  if(big != k){
    temp = A[k];
    e--;
    A[k] = A[big];
    A[big] = temp;
    maxHeapify(big);
  }

  return ;
}

void increasekey(int i, int k){
  int temp;
  int z;
  
  A[i] = k;
  
  while(i>1 && A[i] > A[i/2]){
    temp = A[i];
    A[i] = A[i/2];
    z++;
    A[i/2] = temp;
    i = i/2;
  }

  return ;
}


void insert(int k){
  int x;
  
  h++;
  A[h] = INFTY*(-1);
  x++;
  increasekey(h, k);

  return ;
}

void extract(){
  int y;
  
  printf("%d\n", A[1]);
  A[1] = A[h--];
  y++;
  maxHeapify(1);

  return ;
}




Measured memory_bytes: 5604
#include <iostream>
#include <algorithm>
using namespace std;
main () {
	string str;
	int q;
	cin >> str >> q;
	for (int i=0; i<q; i++) {
		string code;
		int a, b;
		cin >> code >> a >> b;
		if (code == "print") cout << str.substr(a, b-a+1) << endl;
		if (code == "reverse") reverse(str.begin()+a, str.begin()+b+1);
		if (code == "replace") {
				string p;
				cin >> p;
				str.replace(a, b-a+1, p);
		}
	}
}

Measured memory_bytes: 3224
#include <stdio.h>

int a[100001];
int b[100001], *pb = b + 1;

int main(void) {
	int n;
	scanf("%d", &n);
	for (int i = 0; i != n; ++i) scanf("%d", a + i);
	*pb++ = a[0];
	for (int i = 1; i != n; ++i) {
		if (a[i] > pb[-1]) *pb++ = a[i];
		else {
			int* p1 = b + 1, *p2 = pb;
			while (p1 <= p2) {
				int* p = p1 + (p2 - p1) / 2;
				if (a[i] > *p) p1 = p + 1;
				else p2 = p - 1;
			}
			*p1 = a[i];
		}
	}
	printf("%d\n", pb - b - 1);
	return 0;
}



Measured memory_bytes: 3468
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const ll mod = 1000000007;
const ll INF = mod * mod;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
typedef vector<int> vec;
typedef vector<string> svec;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
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; }
//#define int long long

void solve() {
	int s; cin >> s;
	set<int> se;
	se.insert(s);
	int m = 1;
	while(true) {
		if(s & 1) {
			s = 3 * s + 1;
		} else {
			s = s / 2;
		}
		m ++;
		if(se.count(s)) {
			cout << m << endl;
			break;
		} else {
			se.insert(s);
		}
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init();
	solve();
	//cout << "finish" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
int dp[2][3010][2];
int ans;
const int md=1e9+7;
void add(int &a,int b)
{
	a+=b;
	if(a>=md)a-=md;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;i++)dp[0][i][0]=1;
	for(int i=1;i<=m;i++)
	{
		int ii=i&1;
		memset(dp[ii],0,sizeof(dp[ii]));
		for(int j=0;j<=n;j++)
		{
			for(int st=0;st<2;st++)
			{
				int nst;
				if(j>=1)
				{
					nst=st;
					if(j==1)nst=1;
					add(dp[ii][j-1][nst],dp[ii^1][j][st]);//rr
					add(dp[ii][j][nst],dp[ii^1][j][st]);//rb
				}
				if(j<n)
				{
					nst=st;
					if(!j)nst=1;
					add(dp[ii][j+1][nst],dp[ii^1][j][st]);//bb
					add(dp[ii][j][nst],dp[ii^1][j][st]);//br
				}
			}
		}
	}
	for(int i=0;i<=n;i++)add(ans,dp[m&1][i][1]);
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 256
parseInt(x) = parse(Int,x)

function main()
	a,b,c,k = map(parseInt, split(readline()))
	v = [a,b,c]
	x = [0 1 1;1 0 1;1 1 0]
	x = x^k
	v = x*v
	if abs(v[1]-v[2]) >= 1000000000000000000
		print("Unfair")
	else
		print(v[1]-v[2])
	end
end
main()

Measured memory_bytes: 157080
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
typedef long long int lint;
using namespace std;

//二次元累積和
struct cumulative_sum_2d {
    using lint = long long int;
    int sz;
    vector<vector<lint>> data;
    vector<vector<lint>> sum;
    cumulative_sum_2d(const int _sz) : sz(_sz) {
        data.assign(sz, vector<lint>(sz));
        sum.assign(sz + 1, vector<lint>(sz + 1));
    }
    vector<lint>& operator[](const int k) {
        return data[k];
    }
    void build() {
        for (int i = 0; i < sz; i++)
            for (int j = 0; j < sz; j++)
                sum[i + 1][j + 1] =
                    sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + data[i][j];
    }
    //[a,b)×[c,d)の和を計算
    lint query(const int a, const int b, const int c, const int d) const {
        return sum[b][d] - sum[b][c] - sum[a][d] + sum[a][c];
    }
};

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    cumulative_sum_2d cum(n);
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        cum[l][r]++;
    }
    cum.build();
    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        cout << cum.query(x, y + 1, x, y + 1) << endl;
    }
}

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

int main() {
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // #endif

    int n,k;
    cin>>n>>k;
    int ans = 0;
    for(int i = 0;i < n;i++) {
        int x;
        cin>>x;
        if(x >= k) ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
#include<cstdio>
#include<cstdlib>
using namespace std;
 
#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592
 
const double EPS = 1e-10;
 
using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;


 
int main(){
    string s,t; cin >> s >> t;
    int n = s.size();
    int m = t.size();
    bool flag = false;
    for(int i = n-m; i >= 0; i--){
        bool ok = true;
        rep(j,m){
            if(s[i+j] != t[j] && s[i+j] != '?') ok = false;
        }
        if(ok){
            flag = true;
            rep(j,m){
                if(s[i+j] == '?') s[i+j] = t[j];
            }
            break;
        }
    }
    if(!flag){
        cout << "UNRESTORABLE" << endl;
        return 0;
    }
    rep(i,n) if(s[i] == '?') s[i] = 'a';
    cout << s << endl;
}

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

typedef long long int ll;
const int MOD = 1000000007;

ll mod_pow(ll x, ll n){
    ll res = 1;
    while(n > 0){
        if (n & 1) res = res * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return res;
}

ll modinv(ll a){
    return mod_pow(a, MOD-2);
}

int main(){
    ll n, a, b;
    cin >> n >> a >> b;
    ll ans = mod_pow(2, n);
    ll ma = 1;
    for(int i = 0; i < a; i++){
        ma *= (n-i);
        ma %= MOD;
        ma *= modinv(a-i);
        ma %= MOD;
    }
    ll mb = 1;
    for(int i = 0; i < b; i++){
        mb *= n-i;
        mb %= MOD;
        mb *= modinv(b-i);
        mb %= MOD;
    }
    ans += MOD - ma;
    ans %= MOD;
    ans += MOD - mb;
    ans %= MOD;
    ans += MOD - 1;
    ans %= MOD;
    cout << ans << endl;
    return 0;
}

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

#define REP(i, n, m) for(int i = n; i < m; i++)
#define REPR(i, n, m) for(int i = n; i >= m; i--)
#define LREP(i, n, m) for(ll i = n; i < m; i++)
#define LREPR(i, n, m) for(ll i = n; i >= m; i--)

#define INF 1e9 + 1;
#define MOD 1e9 + 7;

typedef long long ll;
//typedef pair<int, int > P;
//typedef pair<ll, ll > LP;

using namespace std;

int gcd(int a, int b){
    if(a < b) swap(a, b);
    return b?gcd(b, a%b):a;
}

int N, K;

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

    cin >> N >> K;

    int x[N];
    int idx;

    REP(i, 0, N) cin >> x[i];

    REP(i, 0, N - 1){
        if(x[i] <= 0 && x[i+1] >= 0){
            idx = i;
        }
    }
    
    if(x[0] >= 0){
        cout << x[K-1] << endl;
    }else if(x[N-1] < 0){
        cout << - x[N-K] << endl;
    }else{
        int start = max(0, idx-K+1);
        int ans = INF;
        REP(i, start, N - K + 1){
            ans = min(ans, abs(x[i]) + 2 * abs(x[i+K-1]));
            ans = min(ans, 2 * abs(x[i]) + abs(x[i+K-1]));
        }
        cout << ans << endl;
    }
}


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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (ll i = 0; i < n; i++) {
        cin >> a[i];
    }
    long double mx = 0, cur = 0;
    for (ll i = 0; i < k; ++i) {
        cur += (a[i] + 1) / 2.0;
    }
    mx = max(mx, cur);
    for (ll i = k; i < n; ++i) {
        cur = cur - (a[i - k] + 1) / 2.0 + (a[i] + 1) / 2.0;
        mx = max(mx, cur); 
    }
    cout << fixed << setprecision(6) << mx;
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<deque>
#include<iomanip>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;
typedef pair<LL,int> LP;
const int INF=1<<30;
const LL MAX=1e9+7;

void array_show(int *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%d%c",array[i],(i!=array_n-1?middle:'\n'));
}
void array_show(LL *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%lld%c",array[i],(i!=array_n-1?middle:'\n'));
}
void print_YES_NO(bool answer){cout<<(answer?"YES":"NO")<<endl;}
void print_Yes_No(bool answer){cout<<(answer?"Yes":"No")<<endl;}
void print_POSSIBLE_IMPOSSIBLE(bool answer){cout<<(answer?"POSSIBLE":"IMPOSSIBLE")<<endl;}

int main(){
	double n,t;
	cin>>n>>t;
	double a,b,c;
	double s=0;
	int i,j,k;
	for(i=1;i<=n;i++){
		a=i;
		for(b=1;a<t;b*=2,a*=2);
		s+=1.0/b/n;
	}
	cout<<fixed<<setprecision(10)<<s<<endl;
}


Measured memory_bytes: 256
import collections
import sys
sys.setrecursionlimit(100000)
def root(X):
	if cards[X]==X:
		return X
	else:
		cards[X]=root(cards[X])
		return cards[X]
def unite(X,Y):
	x=root(X)
	y=root(Y)
	if x==y:
		return
	else:
		cards[x]=y
def same(X,Y):
	return root(X)==root(Y)
def show(x):
	print(cards[x])
		
N,M=[int(i) for i in input().split()]
cards=[i for i in range(N+1)]
for i in range(M):
	X,Y,Z=[int(i) for i in input().split()]
	if same(X,Y):
		pass
	else:
		unite(X,Y)
a=[]
for i in range(1,N+1):
	a.append(root(cards[i]))
print(len(set(a)))

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

using namespace std;

int main(int argc, const char *argv[])
{
  int n;
  cin >> n;

  vector<int> a(n);

  // cnts[i]: iがcnts[i]個ある
  vector<unsigned long long> cnts(n + 1, 0);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    cnts[a[i]]++;
  }

  unsigned long long sum = 0;
  for (int i = 0; i <= n; i++) {
    unsigned long long cnt = cnts[i];
    if (cnt >= 2) {
      sum += cnt * (cnt - 1) / 2;
    }
  }

  // cout << "sum:" << sum << "\n";

  for (int i = 0; i < n; i++) {
    unsigned long long cnt = cnts[a[i]];
    unsigned long long sub_cnt = cnt - 1;
    // cout << cnt << " " << sub_cnt << "\n";
    // cout << a[i] << " " << cnt << " " << sub_cnt << ": ";
    unsigned long long ans1 = (cnt * (cnt - 1) / 2);
    unsigned long long ans2 = sub_cnt * (sub_cnt - 1) / 2;
    // unsigned long long ans3 = (unsigned long long)sum - (ans1 - ans2);
    unsigned long long ans3 = (ans1 - ans2);
    unsigned long long ans4 = sum - ans3;
    cout << ans4 << "\n";
    // if (i == n - 1) {
      // cout << "cnt " << cnt << "\n";
      // cout << "sub_cnt " << sub_cnt << "\n";
      // cout << "sum " << sum << "\n";
      // cout << "ans1 " << ans1 << "\n";
      // cout << "ans2 " << ans2 << "\n";
      // cout << "ans3 " << ans3 << "\n";
      // cout << "ans4 " << ans4 << "\n";
    // }
  }
  
  return 0;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
#define Priq priority_queue<int,vi,greater<int>>
#define pb push_back
#define mp make_pair
#define INF (1ll<<60)
signed main(){
  int N; cin>>N;
  cout<<pow(N,3)<<endl;
  }


Measured memory_bytes: 256
use std::io::stdin;
use std::str::FromStr;

fn main(){
    let _n: usize = get_one();
    let mut s = get_chars();
    s.reverse();
    let m = s.iter().fold(0, |acc, &c| if c == '1' {acc + 1} else {acc});
    let mut z: Vec<Vec<usize>> = Vec::new();
    let mut d: Vec<usize> = vec![1, 1, 1];
    for _i in 0..s.len() {
        z.push(d.iter().map(|&x| x).collect());
        if m==0 {
            d = vec![1, 1, d[2]*2 % (m+1)]
        } else if m == 1 {
            d = vec![1, d[1]*2 % m, d[2]*2 % (m+1)];
        } else {
            d = vec![d[0]*2 % (m-1), d[1]*2 % m, d[2]*2 % (m+1)];
        }
    }
    // println!("m: {}", m);
    // for i in 0..d.len() {
        // println!("d: {}", d[i]);
    // }
    // println!("");

    let mut start_bases = Vec::new();
    for i in 0..3 {
        let mut b = 0;
        for j in 0..s.len() {
            if s[j] == '1' {
                b += z[j][i];
                if m == 1 && i ==0 {
                    b = 1;
                } else {
                    b %= m-1+i;
                }
            }
        }
        start_bases.push(b);
    }

    let mut starts = Vec::new();
    for i in 0..s.len() {
        if s[i] == '0' {
            let mut l = start_bases[2];
            l += z[i][2];
            starts.push(Some(l % (m+1)));
        } else {
            if m == 1 {
                starts.push(None);
            } else {
                let mut l = start_bases[0];
                l += (m-1) - z[i][0];
                starts.push(Some(l % (m-1)));
            }
        }
    }

    // for i in 0..starts.len() {
    //     println!("s: {}", starts[i]);
    // }
    // println!("");

    let anss: Vec<usize> = starts.iter().rev().map(
        |i| i.map(|i| f(i) + 1).unwrap_or(0)
    ).collect();

    for ans in anss {
        println!("{}", ans);
    }
}

fn f(n: usize) -> usize {
    if n == 0 { 0 }
    else {
        let p = popcount(n);
        1 + f(n % p)
    }
}

fn popcount(n: usize) -> usize {
    if n == 0 { 0 }
    else { n % 2 + popcount(n/2) }
}

#[allow(dead_code)]
fn get_line() -> String {
    let mut s = String::new();
    match stdin().read_line(&mut s){
        Ok(_) => {s.trim().to_string()}
        Err(_) => String::new()
    }
}

#[allow(dead_code)]
fn get_vec<T: std::str::FromStr>() -> Vec<T> {
    let line = get_line();
    line.split_whitespace().filter_map(|x| x.parse().ok()).collect()
}

#[allow(dead_code)]
fn get_one<T: FromStr + Copy>() -> T {
    let v = get_vec();
    v[0]
}

#[allow(dead_code)]
fn get_pair<T: FromStr + Copy>() -> (T, T) {
    let v = get_vec();
    (v[0], v[1])
}

#[allow(dead_code)]
fn get_triple<T: FromStr + Copy>() -> (T, T, T) {
    let v = get_vec();
    (v[0], v[1], v[2])
}

#[allow(dead_code)]
fn get_chars() -> Vec<char> {
    get_line().chars().collect()
}

#[allow(dead_code)]
fn vec_min(xs: &Vec<i64>) -> i64 {
    xs.iter().map(|&x|x).fold(std::i64::MAX, std::cmp::min)
}

#[allow(dead_code)]
fn vec_max(xs: &Vec<i64>) -> i64 {
    xs.iter().map(|&x|x).fold(std::i64::MIN, std::cmp::max)
}

#[allow(dead_code)]
fn vec_sum(xs: &Vec<i64>) -> i64 {
    xs.iter().fold(0, |acc, &x| acc+x)
}


Measured memory_bytes: 18716
#include <stdio.h>

int max(int a,int b){
  if(a>b){
    return a;
  }
  return b;
}

int min(int a,int b){
  if(a>b){
    return b;
  }
  return a;
}

int main(void){
  int N,A,B;
  scanf("%d%d%d",&N,&A,&B);

  printf("%d %d\n",min(A,B),max(A+B-N,0));

  return 0;
}

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

int main() {
	long long n; cin >> n;
	long long res = 0;
	if(n % 2 == 1) {
		cout << "0" << endl;
		return 0;
	}
	while (n)
	{
		n /= 5;
		res += n / 2;
	}
	cout << res << 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))

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<int> A(N);
	rep(i,N)cin>>A[i];
	int mini,Asum,Amin;
	do {
		Amin=inf;
		rep(i,N){
			if(A[i]>0&&Amin>A[i]){
				mini=i;
				Amin=A[i];
			}
		}
		Asum=0;
		rep(i,N){
			if(A[i]>0&&i!=mini){
				A[i]%=Amin;
				Asum+=A[i];
			}
		}
	}while(Asum>0);
	cout<<Amin<<endl;
}

Measured memory_bytes: 768
import collections

N = int(input())
A = [int(input()) for _ in range(N)]

A_c = collections.Counter(A)
A_max = max(A)
A_2 = sorted(list(set(A)), reverse=True)
if len(A_2) >= 2:
    A_2ndmax = A_2[1]

for i in range(N):
    if A_c[A_max] >= 2:
        print(A_max)
    else:
        if A[i] != A_max:
            print(A_max)
        else:  # A[i]==A_max
            print(A_2ndmax)


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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

l = []
for i in range(1,1000001):
  l.append(i*i) 

a = make_divisors(n)
b = 1
c = 1
if len(a) % 2 == 0:
  b = a[len(a)//2]
  c = a[len(a)//2-1]
else:
  b = a[(len(a)-1)//2]
  c = a[(len(a)-1)//2]
  
ans = b-1+c-1

import math
if n in l:
  ans = 2* math.sqrt(n) - 2
print(int(ans))


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

int main(){
    string s;
    cin >> s;
    string ans = "Yes";
    for(int i = 0;i < s.size();i++){
        if(i % 2 == 0){
            if(s.at(i) == 'L'){
                cout << "No" << endl;
                return 0;
            }
        }else{
            if(s.at(i) == 'R'){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
string s,ss;
int main()
{
	cin >>s>>ss;
	for (int i=s.size()-ss.size();i>=0;i--)
	{
		bool fl=1;
		for (int j=0;j<ss.size();j++)
		{
			if (s[i+j]=='?') continue;//跳过下面语句直接进入下一个循环 
			if (s[i+j]!=ss[j])         
			{
				fl=0;
				break;                //结束循环
			}
		}
		if (fl)                   //没有break，匹配成功 
		{
		    for (int j=0;j<ss.size();j++) if (s[i+j]=='?') s[i+j]=ss[j];
		    for (int j=0;j<s.size();j++) if (s[j]=='?') s[j]='a';
		    cout <<s;
		    return 0;
		}
	}
	cout <<"UNRESTORABLE";
	return 0;
}

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

int main(void) {
	char a,b;
	cin >> a >> b;
	if(a=='H'){
		if (b=='H') cout << 'H' << endl;
		else cout << 'D' << endl;
	}else{
		if (b=='H') cout << 'D' << endl;
		else cout << 'H' << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int gcd(int x,int y){
    if(y==0)return x;

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

int main(){

    int W,A,B;
    cin>>W>>A>>B;

    if(A<=B&&B<=(A+W)||B<=A&&A<=(W+B)){
        cout<<0<<endl;
    }else{
        if((A+W)<B){
            cout<<B-(A+W)<<endl;
        }else{
            cout<<A-(B+W)<<endl;
        }
    }

    return 0;
}

Measured memory_bytes: 256