akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> start;
vector<vector<int>> goal;
int mem[100001];
int lp(int in) {
    if(mem[in] >= 0)
        return mem[in];
    if(goal[in].size() == 0) {
        mem[in] = 0;
        return 0;
    } else {
        int max = -1;
        for(int i = 0; i < goal[in].size(); i++) {
            int from = goal[in][i];
            if(max < lp(from))
                max = lp(from);
        }
        mem[in] = max + 1;
        return max + 1;
    }
}
int main(void) {
    int N, M;
    cin >> N >> M;
    start = vector<vector<int>>(N + 1);
    goal = vector<vector<int>>(N + 1);
    for(int i = 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
        start[x].push_back(y);
        goal[y].push_back(x);
    }

    for(int i = 1; i <= N; i++) {
        mem[i] = -1;
    }

    int answer = -1;
    for(int i = 1; i <= N; i++) {
        if(start[i].size() == 0) {
            if(answer < lp(i))
                answer = lp(i);
        }
    }
    cout << answer << endl;
    return 0;
}


Measured memory_bytes: 16256
#pragma GCC optimize("Ofast",3,"inline")
#include<bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
#define m_p make_pair
#define y1 ygftgfgcdtfgxffgx
#define y2 yfdsesgvtyghftfvv
#define x1 xvyr6cf6fgcfgf676
#define x2 xcr6rfc5r66y6r6fr
#define up_bound upper_bound
#define low_bound lower_bound
#define next_per next_permutation
#define pb push_back
#define i_to_s to_string
typedef priority_queue<int> p_queue;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n,m;
ll res;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n>>m;
	while(n>0)n-=m,res++;
	cout<<res;
	return 0;
}


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

int main(){

    bool holds = true;
    vector<int> mem(4,0);//0が三角形の数　１が直角　２が鋭角　３が鈍角
    vector<int> tri(3);

    while(holds){
        vector<int> node(3);
        int a,b,c;
        cin>>node[0]>>node[1]>>node[2];

        for(int i=0;i<3;i++){
            if(node[i] >= node[(i+1)%3] + node[(i+2)%3]){
                holds = false;
            }
            else {
               sort(node.begin(),node.end());
               a = node[2];
               b = node[1];
               c = node[0];
            }
        }

        if(holds){
            mem[0]++;
            if(a*a > b*b + c*c) mem[3]++;
            else if (a*a < b*b + c*c) mem[2]++;
            else mem[1]++;
        }
    }
    for(int i=0;i<3;i++){
        cout<<mem[i]<<" ";
    }
    cout<<mem[3]<<endl;
}


Measured memory_bytes: 3144
#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <cstdlib>
using namespace std;

int MiddleSquareMethod(int s){
	ostringstream oss;
	oss<<setfill('0')<<setw(8)<<s*s;
	return atoi(oss.str().substr(2,4).c_str());
}

int main() {
	int n,s;
	cin>>n;
	for(int i=0;i<n;++i){
		cin>>s;
		cout<<"Case "<<i+1<<":"<<endl;
		for(int j=0;j<10;++j){
			s = MiddleSquareMethod(s);
			cout<<s<<endl;
		}
	}
	return 0;
}

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

int main() {
    int N;
    cin>>N;
    for (int i=1;i<=N;i++) {
        if (i*108/100==N) {
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<":("<<endl;
}

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

int read()
{
	int s=0;
	char c=getchar(),lc='+';
	while (c<'0'||'9'<c) lc=c,c=getchar();
	while ('0'<=c&&c<='9') s=s*10+c-'0',c=getchar();
	return lc=='-'?-s:s;
}
void write(int x)
{
	if (x<0)
	{
		putchar('-');
		x=-x;
	}
	if (x<10) putchar(x+'0');
	else
	{
		write(x/10);
		putchar(x%10+'0');
	}
}
void print(int x,char c='\n')
{
	write(x);
	putchar(c);
}

int main()
{
	int n=read(),a=read();
	print(n/a+(n%a?1:0));

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}

#ifdef DEBUG
template <class T, class N> void verr(const T& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << "\n" << flush; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << "\n" << flush; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 5e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//

int main() {
    init();
    ll A, B, C, K;
    cin >> A >> B >> C >> K;
    cout << (K % 2 == 0 ? A - B : B - A) << endl;
}

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

const int MOD=(int)1e9+7;

long long bipow(long long base,long long expo){
  long long ans=1;
  while(expo>0){
    if(expo&1){
      ans*=base;
      ans%=MOD;
    }
    expo>>=1;
    base*=base;
    base%=MOD;
  }
  return ans;
}

long long mod_inv(long long a,long long m){
  long long b=m,u=1,v=0;
  while(b){
    long long t=a/b;
    a-=t*b;
    swap(a,b);
    u-=t*v;
    swap(u,v);
  }
  u%=m;
  if(u<0) u+=m;
  return u;
}

long long nCk(long long n,long long k){
  long long a=1;
  long long b=1;
  long long count=1;
  for(long long i=n;count<=k;i--){
    a*=i;
    a%=MOD;
    count++;
  }
  for(long long i=k;i>=1;i--){
    b*=i;
    b%=MOD;
  }
  
  return (a*mod_inv(b,MOD))%MOD;
}

int main(){
  long long n,a,b;
  cin >> n >> a >> b;

  long long ans=bipow(2,n)-1;
  //cout << ans << endl;
  ans-=nCk(n,a);
  if(ans<0) ans+=MOD;
  ans-=nCk(n,b);
  if(ans<0) ans+=MOD;
  cout << ans%MOD << endl;

  return 0;
}


Measured memory_bytes: 256
l = [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]
n = int(input())

print(l[n-1])

Measured memory_bytes: 3060
def bubble_sort(num_list):
    list_length = len(num_list)-1
    cnt = 0

    for i in range(list_length):
        for j in range(list_length,i,-1):
            if num_list[j] < num_list[j-1]:
                num_list[j],num_list[j-1] = num_list[j-1],num_list[j]
                cnt += 1
    return num_list,cnt

n = int(input())
num_list = list(map(int,input().split()))
ans_list,cnt = bubble_sort(num_list)
str_ans_list = [str(i) for i in ans_list]
print(' '.join(str_ans_list))
print(cnt)


Measured memory_bytes: 5604
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<queue>
#include<map>
#include<vector>
#define N 2700000
#define ll long long
#define ls (now<<1)
#define rs ((now<<1)|1)
#define RG register
using namespace std;
inline int read(){
    RG int x=0,o=1; RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=((x<<3)+(x<<1))+ch-'0',ch=getchar();
    return x*o;
}

int n,m,a[510][511],top;
struct mona { int a,b,c,d; } ans[N];

int main(){
	n=read(),m=read();
	for(RG int i=1;i<=n;++i)
		for(RG int j=1;j<=m;++j)
			a[i][j]=read();
	for(RG int i=1;i<=n;++i){
		if((i&1)){
			for(RG int j=1;j<m;++j)
				if((a[i][j]&1))
					ans[++top]=(mona) { i,j,i,j+1 },a[i][j+1]++;
			if((a[i][m]&1)&&i!=n) ans[++top]=(mona) { i,m,i+1,m },a[i+1][m]++;
		}
		else{
			for(RG int j=m;j>1;--j)
				if((a[i][j]&1))
					ans[++top]=(mona) { i,j,i,j-1 },a[i][j-1]++;
			if((a[i][1]&1)&&i!=n) ans[++top]=(mona) { i,1,i+1,1 },a[i+1][1]++;
		}
	}
	cout<<top<<endl;
	for(RG int i=1;i<=top;++i)
		printf("%d %d %d %d\n",ans[i].a,ans[i].b,ans[i].c,ans[i].d);
}


Measured memory_bytes: 6272
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int main(){
    ll a,b; cin>>a>>b;
    ll A=a, B=b;
    map<ll,ll> m;
    vector<ll> primes;
    for(ll div=2; div*div<=a; div++){
        if(A%div==0){
            //primes.push_back(div);
            m[div]=1;
            while(A%div==0) A/=div;
        }
    }
    if(A>1) m[A]=1;
    for(ll div=2; div*div<=b; div++){
        if(B%div==0){
            if(m[div]==1) primes.push_back(div);
            while(B%div==0) B/=div;
        }
    }
    if(B>1) if(m[B]==1) primes.push_back(B);
    cout<<primes.size()+1<<endl;
    return 0;
}

Measured memory_bytes: 256
N,Y=map(int,input().split())
c=0
for x in range(N+1):
    for y in range(N+1-x):
        z=N-x-y
        if x*10000+y*5000+z*1000==Y:
            print(x,y,z)
            c=1
            break
    if c==1:
        break
if c==0:
    print(-1,-1,-1)

Measured memory_bytes: 3060
#include <iostream>


#define endl '\n'
#define pi acos(-1)
#define euler_e 2.71828
#define pii pair<int,int>
#define pb push_back
#define all(a) a.begin(),a.end()
#define ll long long
#define ull unsigned long long
#define io freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
void mycode();
const ll int mod=998244353;
ll int ceil(ll int a,ll int b){return (a+b-1)/b;}
ll int min(ll int a, ll int b){if(a>b)return b;else return a;}
bool bit_check(ll int a,int i){
  if((a & (1LL<<i)))return 1;
  return 0;
}
ll int bit_toggle(ll int a,int i){
  return (a^(1LL<<i));
}
ll int bit_sum(ll int a,int i){
  return a+(1LL<<i);
}
ll int bit_sub(ll int a,int i){
  return a-(1LL<<i);
}
ll int mod_power(ll int x,ll int y){//x^y%p
  ll int p=mod;
  ll int 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 int power_of(ll int a,int b){
  if(a==0)return -1;
  return 1+power_of(a/b,b);
}
ll int power(ll int a, ll int b) {
	if(a==1)return 1;
    ll int res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
//__int128
int main(){
	boost;
	//io;
	//auto start = chrono::high_resolution_clock::now();
	mycode();
	//auto end = chrono::high_resolution_clock::now();cerr << "\nExecution time: "<< chrono::duration_cast<chrono::milliseconds>(end - start).count() << " ms" << endl;
	return 0;
}
#include<map>
	bool init[2000000];
void mycode(){
	int t,k;
	cin>>t;
	map<int,int>mp;
	for(int i=0;i<t;i++){cin>>k;mp[k]++;}
	int count=0;
	for(auto x:mp){
		if(x.second==1 && !init[x.first])count++;
		if(!init[x.first])for(int i=x.first;i<=1000000;i+=x.first){
			init[i]=true;
		}
	}
	cout<<count;
}

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

int main(void){
    int a,b,h;
    char *p;
    char str[8];
    
    p = fgets(str, 8, stdin);
    a = atoi(p);
    p = fgets(str, 8, stdin);
    b = atoi(p);
    p = fgets(str, 8, stdin);
    h = atoi(p);

    printf("%d\n", ((a+b)*h)/2);
    return 0;
}


Measured memory_bytes: 128
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = 1ll << 60;
const ll mod = (ll)1e9 + 7;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define print(s) cout << s;
#define println(s) cout << s << endl;
#define printd(s, f) cout << fixed << setprecision(f) << s << endl;


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

	vector<int> a(n);
	for (int i = 0; i < n; i++)
	{
		a[i] = i + 1;
	}

	do
	{
		bool sp = false;
		for (int i : a)
		{
			print((sp ? " " : "") << i);
			sp = true;
		}
		println("");
	} while (next_permutation(a.begin(), a.end()));
}


Measured memory_bytes: 3136
// RAKSHIT KADAM
 
//  -- Declare array globally...
 #include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree< int ,  null_type ,  less<int> ,  rb_tree_tag ,  tree_order_statistics_node_update>
// find_by_order returns iterator to  element present at that index...
// order_of_key returns no. of elements having value stricktly less than that given in the order_of_key();
#warning !!!check the size of arrayss!!!
 
// NUMERIC DEFINITIONS :
    #define INF 1000000000000000005
    #define inf 1000000003
    #define MOD  1000000007
    #define newMOD  998244353
    #define MAX 200006
    #define pi 3.1415926535897932384626433832795
#define ld long double
 #define ll long long
 #define int long long
 
 #define P(gg) for(auto rax:gg){cout<<rax<<" ";}cout<<endl;
 #define Need_for_speed(activated) ios_base :: sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
 #define satisfy ll t; cin>> t; while(t--)
 #define inp(n) int n;cin >> n
 #define mp make_pair
 #define pb push_back
 #define endl "\n"
 #define x first
 #define y second
 #define fore(i,a,b) for(ll i=a;i<b;i++)
 #define forci(i,n) for(ll i=0;i<n;i++)
 #define vi vector<ll>
 #define Endl endl
 #define lb lower_bound
 #define ub upper_bound
#define pii pair<ll,ll>
 
 #define input freopen("input.txt", "r", stdin),freopen("output.txt", "w", stdout)
 #define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
using namespace std;
ll gcd(ll a, ll b){if (b == 0)return a;return gcd(b, a % b);}
int power(int x, unsigned int y, unsigned int m){ if (y == 0) return 1;int p = power(x, y/2, m) % m;  p = (p * p) % m;return (y%2 == 0)? p : (x * p) % m;}
ll modInverse(int a, int m){{ return power(a, m-2, m);}}
const int maxn = 500066;
 void solve()
{
    ll a,b;cin>>a>>b;
    if(a>9 || b>9)
    {
        cout<<"-1";return;
    }
    cout<<a*b<<endl;
}
signed main()
{
   Need_for_speed(activated);

//satisfy
//    {
//  solve();
//   }
   
    solve();
    return 0;
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
string s,st;
int x=1,len;
inline void write(long long x)    
{
    if (x<0)
    {
    	putchar('-');
    	x=-x;
	}
	if (x>9)
      write(x/10);
    putchar(x%10+'0');
}
int main()
{
    cin>>st;
    s=' '+st;
    len=st.size();
    if (s[1]=='0'||s[len]=='1')
	{
        write(-1);
        return 0;
    }
    for (register int i=1;i<len;++i)
      if (s[i]^s[len-i])
	  {
        write(-1);
        return 0;
      }
    for (register int i=2;i<=len;++i)
	{
        write(x);putchar(' ');
        write(i);putchar('\n');
        if (s[i-1]=='1')
		  x=i;
    }
    return 0;
}

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

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

    ll x; cin >> x;
    ll a = 100;
    int ans = 0;
    while( a < x){
        a *= 1.01;
        ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using vs = vector<string>;
using in6 = int64_t;
using ind = double;
using pii = pair<int,int>;
using psi = pair<string,int>;
using vpi = vector<pii>;
using vps = vector<psi>;
#define rep(i, n) for (in6 i = 0; i < (in6)(n); i++)
#define repa(i,a,n) for(in6 i = a; i < (in6)(n); i++)
#define repdown(i,n) for(in6 i = n; i > 0; i--)
#define kyun ios::sync_with_stdio(false)
#define hinata cout << "\n"
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define inf 2147483647

int main() {
  kyun;
  int n,m;
  cin >> n >> m;
  vi data(n);
  rep(i,n) cin >> data[i];
  double sum = 0;
  cout << fixed << setprecision(10);
  rep(i,n) sum += data[i];
  sort(all(data));
  reverse(all(data));
  bool ans = 1;
  double check = sum / (4*m);
  if(check > data[m-1]) ans = 0;
  if(ans) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
/*
ID: learnin7
TASK: test
LANG: C++                 
*/
/* LANG can be C++11 or C++14 for those more recent releases */
#include<bits/stdc++.h>

/*  Macros from Endagorion */
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;


int main(){
        
    ios_base::sync_with_stdio(0);
    
    //ofstream fout ("test.out");
    //ifstream fin ("test.in");
    //fin >> a >> b;
    //fout << a+b << endl;
    string s;
    int n=0;
    string res="",a="";
    cin>>s;
    for(int i=0;i<s.length();i++){
        if(s[i]=='A' || s[i]=='C' || s[i]=='G' || s[i]=='T'){
            res += s[i];
            if(n<res.length()){
                n = res.length();
                a = res;
            }
        }
        else{
            res = "";
        }
    }

        cout<<a.length()<<endl;
    return 0;
}



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

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

using namespace std;

int main(){
  ll a,b;cin>>a>>b;
  if(a>0){
    cout<<"Positive";
  }else if(a<=0 && b>=0){
    cout<<"Zero";
  }else if(a<0 && b<0 && !((b-a)%2)){
    cout<<"Negative";
  }else{
     cout<<"Positive";
 }
  return 0;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;

int main() {
    ll n;
    cin >> n;

    cout << (n-1)*n/2 << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <bitset>
#include <cassert>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <sstream>
#include <stdio.h>
#include <string>
#include <vector>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define POW(n) ((n) * (n))
#define ALL(a) (a).begin(), (a).end()
#define dump(v) (cerr << #v << ": " << v << endl)
#define cerr                                                                   \
  if (true)                                                                    \
  cerr

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<unsigned long long> vull;
typedef pair<int, int> pp;       // int aa = pp.first;
typedef tuple<int, int, int> tp; // int aa = get<0>(tp);

// ll n = to_T<ll>("114514")
template <class T> T to_T(const string &s) {
  istringstream is(s);
  T res;
  is >> res;
  return res;
}
template <class T> string to_s(const T &a) {
  ostringstream os;
  os << a;
  return os.str();
}

int all[100100];

class BIT {
public:
  vector<int> bit;
  int M;

  BIT(int M) : bit(vector<int>(M + 1, 0)), M(M) {}

  int get(int i) const {
    if (!i)
      return 0;
    return bit[i] + get(i - (i & -i));
  }

  void add(int i, int x) {
    // if (i > M)
    //   return;
    // bit[i] += x;
    // add(i + (i & -i), x);
    for (int in = i; in < M; in += in & -in)
      bit[in] += x;
  }
};

void solve(long long N, long long M, vector<long long> l, vector<long long> r) {
  BIT bit(100010);

  vector<tp> vtp;
  REP(i, N) { vtp.push_back(tp(r[i] - l[i] + 1, l[i], r[i])); }
  sort(ALL(vtp));

  int pc = 0;
  FOR(m, 1, M + 1) {
    ll ans = 0;

    while (pc < N && get<0>(vtp[pc]) < m) {
      bit.add(get<1>(vtp[pc]), 1);
      bit.add(get<2>(vtp[pc]) + 1, -1);
      pc++;
    }

    ans += N - pc;

    for (int v = m; v <= 100000; v += m) {
      ans += bit.get(v);
    }

    cout << ans << endl;
  }
}

int main() {
  ios::sync_with_stdio(false);
  long long N;
  long long M;
  cin >> N;
  vector<long long> r(N - 1 + 1);
  vector<long long> l(N - 1 + 1);
  cin >> M;
  for (int i = 0; i <= N - 1; i++) {
    cin >> l[i];
    cin >> r[i];
  }
  solve(N, M, l, r);
  return 0;
}


Measured memory_bytes: 16368
"use strict";
    
const main = arg => {
    arg = arg.trim().split("\n");
    const N = parseInt(arg[0].split(" ")[0]);
    const W = parseInt(arg[0].split(" ")[1]);
 
    const wv = arg.slice(1, N + 1).map(n=>n.split(" ").map(l=>parseInt(l)));
    
    let dp = []
    for(var i=0;i<N+1;i++){
        dp.push(Array(W+1).fill(0));
    }
    
    for(let i=1; i<N+1; i++) {
        const w = wv[i-1][0];
        const v = wv[i-1][1];
        
        for(let j=0; j<W+1; j++) {
            if(w > j) {
                // 単体で重さオーバーなら前回のを引き継ぐ
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = Math.max(dp[i-1][j], v + dp[i-1][j - w]);
            }
        }
    }
    
    console.log(dp[N][W]);

    /*    
      let dp = []
      for(var i=0;i<W+1;i++){
        dp.push( Array(N+1).fill(0) );
      }
    
      var result = 0;
  for(var i=0;i<N;i++){
    for(var w=0;w<=W;w++){
 
      var weight = items[i][0]
      var value = items[i][1]
 
      if(weight <= w){
        dp[w][i+1] = Math.max(dp[w][i], dp[w-weight][i] + value);
      }else{
        dp[w][i+1] = dp[w][i];
      }
 
      if(dp[w][i+1] > result){result = dp[w][i+1];}
 
    }
  }
  */
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 187436
N,C = gets.split.map &:to_i
D = (0...C).map{ gets.split.map &:to_i }.transpose
S = (0...3).map{ Array.new(C,0) }
(0...N).each{ |i| 
  gets.split.map(&:to_i).each_with_index{ |c,j|
    S[(i+j)%3][c-1] += 1
  }
}
T = (0...3).map{ |m|
  (0...C).map{ |c|
    dc = D[c-1]
    v = 0
    sm = S[m]
    (0...C).each{ |c| v += dc[c]*sm[c] }
    v
  }
}

ans = 1000*N*N
(0...C).to_a.permutation(3).each{ |x,y,z| 
  v = T[0][x] + T[1][y] + T[2][z] 
  ans = v if v < ans
}
p ans


Measured memory_bytes: 2428
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;

int n,t,x,y,nx,ny,last,d;

int main(){
	int i;
	scanf("%d",&n);
	nx=0; ny=0; last=0;
	for (i=1;i<=n;i++){
		scanf("%d%d%d",&t,&x,&y);
		d=abs(x-nx)+abs(y-ny);
		if (t-last<d){
			printf("No\n");
			return 0;
		}
		if (t-last-d&1){
			printf("No\n");
			return 0;
		}
		nx=x; ny=y;
		last=t;
	}
	printf("Yes\n");
	return 0;
} 

Measured memory_bytes: 256
#include <iostream>
#include <bitset>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
using namespace std;
using ll = long long int;
#define REP(i,n) for(int i=0;i<n;i++)

int main()
{
    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;

    S[K-1] = S[K-1] - ('A' - 'a');
    cout << S << endl;
}

Measured memory_bytes: 256
//header{{{
#include<bits/stdc++.h>
  
using namespace std;
 
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define setout(n,x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10)
#define int long long
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod = 1e9+7; 

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
  
int gcd(int a,int b){ return b ? gcd(b,a % b) : a;}
int lcm(int a,int b){ return a / gcd(a,b) * b;}
//}}}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> c(n),s(n),f(n);
	rep(i,n-1){
		cin >> c[i] >> s[i] >> f[i];
	}
	rep(i,n-1){
		int now = s[i] + c[i];
		for(int j = i+1;j < n-1;++j){
			if(now <= s[j]){
				now = s[j] + c[j];
				continue;
			}
			now = (now - s[j] + f[j] - 1) / f[j] * f[j] + s[j] + c[j];
		}
		cout << now << '\n';
	}
	cout << 0 << '\n';
	return 0;
}


Measured memory_bytes: 256
even = []
odd = []
count = 0
win = 0
lose = 0
gets.chomp.split('').map do |x|
  if count.even?
    lose += 1 if x == "p"
  else
    win += 1 if x == "g"
  end
  count += 1
end
# p win, lose
puts win - lose


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

int main() {
  int A, P;
  cin >> A >> P;
  int ans = (A * 3 + P) / 2;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.*;
 
public class Main {
	public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    long ans = 0;
    for (int b = 1; b <= N; b++) {
      if (K < b) {
        int plus;
        if ((N + 1) % b > K) {
          plus = (b - K) * ((N + 1) / b) + ((N + 1) % b) - K;
        } else {
          plus = (b - K) * ((N + 1) / b);
        }
        // System.out.println(String.format("b = %d, plus = %d", b, plus));
        ans += plus;
        if (K == 0) ans--;
      }
    }
    System.out.println(ans);
  }

  //指定した値以上の先頭のインデックスを返す
  private static final int lowerBound(final int[] arr, final int value) {
    int low = 0;
    int high = arr.length;
    int mid;
    while (low < high) {
      mid = ((high - low) >>> 1) + low;   //(low+high)/2のオーバーフロー対策
      if (arr[mid] < value) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    return low;
  }
 
  //指定した値より大きい先頭のインデックスを返す
  private static final int upperBound(final int[] arr, final int value) {
    int low = 0;
    int high = arr.length;
    int mid;
    while (low < high) {
      mid = ((high - low) >>> 1) + low;   //(low+high)/2のオーバーフロー対策
      if (arr[mid] <= value) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    return low;
  }
}

Measured memory_bytes: 23764
'''
Created on 2020/09/04

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  N=int(pin())
  S=pin()[:-1]

  cnt=0
  l=["0","1","2","3","4","5","6","7","8","9"]
  for i in l:
    for j in l:
      for k in l:
        c=[i,j,k]
        n=0
        for m in S:
          if m==c[n]:
            if n==2:
              cnt+=1
              break
            else:
              n+=1
  print(cnt)
  return
main()
#解説AC

Measured memory_bytes: 9264
#include <stdio.h>

#define MAX(x, y) ((x) > (y) ? (x) : (y))

int r[100][100];

int main(){
  int row = 0, height = 0, i, j;
  while(scanf("%d", &r[row][height]) != EOF && r[row][height] != 100){
    height++;
    if(getchar() == '\n'){
      row++;
      height = 0;
    }
  }

  for(i = 1;i < row / 2 + 1;i++){
    r[i][0] += r[i - 1][0];
    for(j = 1; j < i + 1;j++)
      r[i][j] += MAX(r[i - 1][j - 1], r[i - 1][j]);
  }

  for(;i < row + 1;i++){
    for(j = 0;j < row - i + 1;j++)
      r[i][j] += MAX(r[i - 1][j], r[i - 1][j + 1]);
  }

  printf("%d\n", r[row][0]);
  return 0;
}

Measured memory_bytes: 640
// 基本テンプレート

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int

template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}

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

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
constexpr ll INF = 1001001001001001LL;
constexpr ll MOD = 1000000007LL;

int dp[41][1 << 17];
signed main() {
    int N, X, Y, Z; cin >> N >> X >> Y >> Z;
    int ngbit = ((1LL << (X+Y+Z)) + (1LL << (X+Y)) + (1LL << X)) >> 1LL;
    int sum = X+Y+Z;
    int mask = (1 << sum) - 1;

    dp[0][0] = 1;
    int base = 1;
    rep(i,0,N) (base *= 10) %= MOD;

    rep(i,0,N) rep(bit,0,1<<sum) repq(k,1,10) {
        int nbit = mask & ( (bit << k) ^ (1 << (k-1)) );
        if((nbit & ngbit) == ngbit) continue;
        (dp[i+1][nbit] += dp[i][bit]) %= MOD;
    }

    int sub = 0;
    rep(i,0,1<<sum) (sub += dp[N][i]) %= MOD;
    cout << (base - sub + MOD) % MOD << endl;
    return 0;
}

Measured memory_bytes: 41216
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int mod=1e9+7;

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

void add(int &a,int b)
{
    a=(a+b)%mod;
}

signed main()
{
    string L; cin>>L;
    int N=L.size();
    int ans=0,cnt=0;
    for(int i=0;i<N;i++){
        if(L[i]=='1'){
            int tmp=mod_pow(2,cnt)*mod_pow(3,N-i-1)%mod;
            add(ans,tmp);
            cnt++;
        }
    }
    add(ans,mod_pow(2,cnt));
    cout<<ans<<endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int MAX = 100000;
const int INF = 1e9;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};
#define PI 3.14159265358979323846264338327950L
#define MOD 1000000007
//setprecision(15)

int minf[MAX + 1];
int s[MAX + 1];
// エラトステネスの篩
void sieve() {
	memset(minf, -1, sizeof(minf));
	for (int i = 2; i <= MAX; i++) {
		if (minf[i] != -1) continue;
		minf[i] = i;
		for (int j = i * 2; j <= MAX; j += i) {
			minf[j] = i;
		}
	}
}

void make_tbl_2017() {
	int cnt = 0;
	for (int i = 3; i <= MAX; i++) {
		s[i] = cnt;
		if (minf[i] == i && minf[(i+1)/2] == (i+1)/2) cnt++;
	}
}

int main() {
	sieve();
	make_tbl_2017();
	int Q; cin >> Q;
	int ans[100000];
	rep(i, Q) {
		int l, r; cin >> l >> r;
		if (minf[r] == r && minf[(r+1)/2] == (r+1)/2) {
			ans[i] = s[r] - s[l] + 1;
		} else {
			ans[i] = s[r] - s[l];
		}
	}
	rep(i, Q) {
		cout << ans[i] << endl;
	}
}

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

n = int(input())

a = list(map(int, input().split()))
a.sort()

c = [0] * (10**6+1)
for i in a:
    c[i] += 1

uni = []
a = list(set(a))

for i in a:
    if c[i] == 1:
        uni.append(i)

b = [0 for _ in range(10**6+1)]

for i in a:
    for j in range(i*2, 10**6+1, i):
        b[j] = 1

cnt = 0
for i in uni:
    if b[i] == 0:
        cnt += 1

print(cnt)

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

#define REP(i,n) for(int i = 0 ; i < n ; ++i)
#define ll long long int
using namespace std;

int main()
{
  ll x,y;
  cin >> x >> y;
  int i=0;
  while(x<=y){
    i++;
    x*=2;
  }
  cout << i << endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int data[10];
    for( int i =0; i< 10 ; i++ )
    {
        cin>>data[i];
    }

    for( int i =9; i>=7; i--)
    {
        for(int j = 0; j< i; j ++)
        {
            if( data[j] > data[j+1])
            {
                int tmp;
                tmp = data[j];
                data[j] = data[j+1];
                data[j+1] =tmp;
            }
        }
    }
    for (int i = 9; i >= 7; i--)
    {
        cout<<data[i]<<endl;
    }

    return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<bitset>
#include<cstdio>
using namespace std;

int n,m,ans=0,x[200005],y[200005];
bool vis[405];
bitset<500> s[405];

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d",x+i,y+i);
	for(int i=1;i<=n;i++){
		s[i][i]=true;
		for(int j=m;j>=1;j--){
			if(s[i][x[j]]&s[i][y[j]]){
				vis[i]=true;break;
			}else if(s[i][x[j]])s[i][y[j]]=true;
			else if(s[i][y[j]])s[i][x[j]]=true;
		}
	}
	for(int i=1;i<=n-1;i++){
		if(vis[i])continue;
		for(int j=i+1;j<=n;j++){
			if(vis[j])continue;
			if((s[i]&s[j]).none())ans++;
		}
	}
	printf("%d",ans);
}

Measured memory_bytes: 1024
n = int(input())
g = [[]for i in range(n)]
def swap(n):
    if n == 1:
        return 0
    else:
        return 1
for i in range(n-1):
    u,v,w = map(int,input().split())
    u = u-1
    v = v-1
    w = w%2
    g[u].append([v,w])
    g[v].append([u,w])
ans = [-1 for i in range(n)]
from collections import deque
d = deque([[0,0]]) #左は頂点の数字、右は塗った色
while d:
    p,q = d.popleft()
    ans[p] = q
    for j,w in g[p]:
        if ans[j] != -1:
            continue
        else:
            if w == 1:
                d.append([j,swap(q)])
            else:
                d.append([j,q])
for i in range(n):
    print(ans[i])

Measured memory_bytes: 85024
#include <iostream>
 
using namespace std;
 
int main () {
   long A,B,K;
   cin>>A>>B>>K;
   if (A>=K){
       cout<<A-K<<' '<<B;
   }
   else if((A+B)<=K){
   cout<<0<<' '<<0;
   }
   else{
       cout<<0<<' '<<(A+B)-K;}
       return 0;
   }


Measured memory_bytes: 256
/*	
TELL YOUR CODE TO START BELIEVING IN GOD!!
THEY HATE US BECAUSE THEY AIN'T US
	ARIJIT SUR 
	duke_knight
	IIT ISM 
 WORK SO HARD THAT YOUR IDOL BECOMES YOUR COMPETITOR 
 */
#include<bits/stdc++.h>
#define pb push_back
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define f q.front()
#define SIZE (ll)(1e5)
#define mod (ll)(1e9+7)
using namespace std;
typedef long long int ll;

int main()
{
    IOS
    string s;
    cin>>s;
    if(s[2]==s[3] && s[4]==s[5] ) printf("Yes\n");
    else printf("No\n");
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PA;
typedef priority_queue<int> PQ;
typedef vector<int> VE;
#define int long long
#define INF 1000000009
#define INFL 1000000000000000018
#define mod 1000000007
#define pb push_back
#define MAXN 100005

int n;

signed main()
{
    cin >> n;
    for(int i = 0; i < 100; i++){
        for(int j = 0; j < 100; j++){
            if(n == 4 * i + 7 * j){
                printf("Yes\n");
                return 0;
            }
        }
    }

    printf("No\n");

    return 0;
}


Measured memory_bytes: 256
n, k = map(int, input().split())
a = list(map(int, input().split()))
m = 10**9+7
p, q = 0, 0

for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            if i < j: p += 1
            q += 1

print((p*k + (q*k*(k-1) // 2)) % m)


Measured memory_bytes: 3188
#include<iostream>
#include<string>
#include<stdio.h>
#include<cctype>
#include<algorithm>
#include<climits>
#include<cmath>
#include<map>
#define INF INT_MAX
using namespace std;

string s;
int list[100010];
int N, Q;
int l, r;
int cnt;

int main(){
	cin >> N >> Q;
	cin >> s;
	for (int i = 0; i < N; i++){
		list[i] = cnt;
		if (s[i] == 'A'){
			if (s[i + 1] == 'C')cnt++;
		}
	}
	cnt = 0;

	for (int i = 0; i < Q; i++){
		cin >> l >> r;
		cout << list[r - 1] - list[l - 1] << endl;
	}

	return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using gpp_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename L> using gpp_map = tree<T, L, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using gpp_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define Return(ans) { cout << (ans) << endl; return 0; }
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;

//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};

const int mod = 1000000007;
//const int mod = 998244353;
//#define Add(x, y) x = (x + (y)) % mod
//#define Mult(x, y) x = (x * (y)) % mod



signed main(){

    int N; cin >> N;
    vec P(N); cin >> P;
    int ans = 0, m = INF;
    REP(i, N){
        if(P[i] <= m) ans++;
        Min(m, P[i]);
    }
    Out(ans);

    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
const int M=1e5+10;
int a[M],cnt;
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x;scanf("%d",&x);
        a[x]++;
    }
    int cost=0;
    for(int i=1;i<M;i++)if(a[i]>=2)
    {
        if(a[i]%2==0)
        {
            cost+=a[i]-2;
            cnt++;
        }
        else cost+=a[i]-1;

    }
    cost+=(cnt/2)*2;
    if(cnt%2==1)cost+=2;
    printf("%d\n",n-cost);
}


Measured memory_bytes: 640
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys


def solve(S, K):
    if min(S) == max(S) == '1':
        return 1
    else:
        for i in range(len(S)):
            if S[i] != '1':
                if K <= i:
                    return 1
                else:
                    return int(S[i])

S = input()
K = int(input())
print(solve(S, K))                

# assert solve('111', 1) == 1
# assert solve('111', 2) == 1
# assert solve('111', 3) == 1

# assert solve('12', 1) == 1
# assert solve('12', 2) == 2
# assert solve('12', 100) == 2

# assert solve('21', 1) == 2
# assert solve('21', 2) == 2
# assert solve('21', 100) == 2

# assert solve('121', 1) == 1
# assert solve('121', 2) == 2
# assert solve('121', 3) == 2
# assert solve('121', 100) == 2

# assert solve('1121', 1) == 1
# assert solve('1121', 2) == 1
# assert solve('1121', 3) == 2
# assert solve('1121', 100) == 2


Measured memory_bytes: 6596
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
    queue<int> Q;
vector<int> u[500000];
int cnt=0,color[500000];
// white 0 gray 1 black 2
// void BFS(int s,int n){
//     if(color[s]==0){
//         cnt++;
//         color[s]=cnt;
//         Q.push(s);
//         while(Q.size()!=0){
//             int tmp=Q.front();
//             Q.pop();
//             for(int j=0;j<u[tmp].size();j++){
//                 int to = u[tmp][j];
//                 if(color[to]==0){
//                     color[to]=cnt;
//                     Q.push(to);
//                 }
//             }
//         }
//     }
// }
int main(){
    int n,m,s,t,q;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>s>>t;
        u[s].push_back(t); 
        u[t].push_back(s);
    }
    cin>>q;
    for(int s=0;s<n;s++){
        if(color[s]==0){
            cnt++;
            color[s]=cnt;
            Q.push(s);
            while(Q.size()!=0){
                int tmp=Q.front();
                Q.pop();
                for(int j=0;j<u[tmp].size();j++){
                    int to = u[tmp][j];
                    if(color[to]==0){
                        color[to]=cnt;
                        Q.push(to);
                    }
                }
            }
    }
    }
    for(int i=0;i<q;i++){
        cin>>s>>t;
        if(color[s]==color[t]){
            cout<<"yes"<<endl;
        }
        else{
            cout<<"no"<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 18392
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define piii pair<int,pii>
#define pll pair<ll,ll>
#define plii pair<ll,pii>
#define vi vector<int>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define mx 100001
#define eps 0.00000000001
#define mod 1000000007
#define pi acos(-1)
#define inf 100000000
#define loop(i,b,n) for(int i=b;i<n;++i)
#define rev_loop(i,b,n) for(int i=b;i>=n;--i)
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int main()
{
    fio;
    ll a,b,c,k;
    cin>>a>>b>>c>>k;
    if(a>=k)
    {
        cout<<k<<endl;
    }
    else if(a+b>=k)
        cout<<a<<endl;
    else
    {
        int r = k - a-b;
        cout<<a-r<<endl;
    }
    return 0;
}



Measured memory_bytes: 3616
#include <iostream>

using namespace std;
int get(int a, int b)
{
    if (a > b)return 2100000000;
    else return b - a;
}
int main()
{
    int a, b;
    cin >> a >> b;
    cout << min(min(get(a, b), get(-a, b) + 1), min(get(a, -b) + 1, get(-a, -b) + 2)) << endl;
    
    return 0;
}

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

const int INF = 1001001001;


int main(){
    ll n,a;
    cin>>n;
    ll maxa=0;

    cin>>a;
    if(n==1){
        cout<<0;
        return 0;
    }
    maxa = max(a,maxa);
    ll s=0;
    rep(i,n-1){
        cin>>a;
        maxa = max(a,maxa);
        s+=maxa-a;
    }
    cout<<s;
    return 0;
}




Measured memory_bytes: 3632
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
using namespace std;

const int dx[4] = {0,0,-1,1};
const int dy[4] = {-1,1,0,0};

struct P{
	int x, y;
	P(){}
	P(int x_, int y_){
	}
};

// memo[a] := テ」ツδ妥」ツつコテ」ツδォテ」ツ?ョテァツ環カテヲツ??a テ」ツ?セテ」ツ?ァテ」ツ?ョテヲツ可凝ヲツ閉ー
map<vector<vector<int> >, int> memo;

// テ・ツョツ古ヲツ按静」ツ?療」ツ?ヲテ」ツ??」ツつ凝」ツ?凝」ツ?ゥテ」ツ??」ツ??
bool is_goal(const vector<vector<int> > &a){
	for(int i = 0; i < 8; i++){
		int x = i % 4, y = i / 4;
		if( a[y][x] != i ) return false;
	}
	return true;
}

// テァツゥツコテァツ卍ステ」ツ?ョテ、ツスツ催ァツスツョテ」ツつ津ィツソツ氾」ツ??
int search(const vector<vector<int> > &a){
	for(int i = 0; i < 8; i++){
		int x = i % 4, y = i / 4;
		if( a[y][x] == 0 ) return i;
	}
	return -1;
}

void bfs(vector<vector<int> > a){	
	memo[a] = 0;
	queue<vector<vector<int> > > q;
	q.push(a);
	
	while( !q.empty() ){
		vector<vector<int> > v = q.front(); q.pop();
		int cost = memo[v];
		
		// テァツゥツコテァツ卍ステ」ツ?ョテ、ツスツ催ァツスツョテ」ツつ津ィツソツ氾」ツ??
		int p = search(v);
		int x = p % 4, y = p / 4;
		// テァツゥツコテァツ卍ステ」ツ?ョテ、ツスツ催ァツスツョテ」ツ?ョテッツシツ氾ヲツ鳴ケテ・ツ青妥」ツ?ョテ、ツスツ催ァツスツョテ」ツ?ィテ、ツコツ、テヲツ渉崚」ツ?療」ツ?ヲテ」ツ?ソテ」ツつ?
		for(int i = 0; i < 4; i++){
			int mx = x + dx[i], my = y + dy[i];
			if( mx < 0 || my < 0 || 4 <= mx || 2 <= my ) continue;
			
			swap(v[y][x], v[my][mx]);
			if( !memo.count(v) ){ // テ」ツ?セテ」ツ??ヲツ篠「テァツエツ「テ」ツ?療」ツ?ヲテ」ツ?ェテ」ツ?凝」ツ?」テ」ツ?淌」ツつ嘉」ツつュテ」ツδ・テ」ツδシテ」ツ?ォテ・ツ?・テ」ツつ古」ツつ?
				memo[v] = cost + 1;
				q.push(v);
			}
			swap(v[y][x], v[my][mx]);
		}
	}
}

int main(){
	{
		vector<vector<int> > a(2, vector<int>(4));
		for(int i = 0; i < 8; i++){
			int x = i % 4, y = i / 4;
			a[y][x] = i;
		}
		// テ・ツケツ?・ツ?ェテ・ツ?暗ヲツ篠「テァツエツ「 (テヲツ慊?・ツ按敕」ツ?ォテ」ツ?凖」ツ?ケテ」ツ?ヲテ」ツ?ョティツァツ」テ」ツつ津ヲツアツづ」ツつ?」ツ?ヲテ」ツ?甘」ツ??
		bfs(a);
	}
	vector<vector<int> > a(2, vector<int>(4));
	
	while( cin >> a[0][0] ){
		for(int i = 1; i < 8; i++){
			int x = i % 4, y = i / 4;
			cin >> a[y][x];
		}
		
		
		cout << memo[a] << endl;
	}
}

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

int main() {
  string n;
  cin >> n;
  ll sn = 0;
  rep(i, n.size()) {
    sn += (n[i] - '0');
  }
  ll rem = stoi(n) % sn;
  if(!rem) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 3560
#include "bits/stdc++.h"
using namespace std;

struct Union {
	int Par;
	int Rank;
};

static Union Road[200000], Rail[200000];

void init(int X) {
	for (int i = 0; i < X; i++) {
		Road[i].Par = i;
		Road[i].Rank = 0;
		Rail[i].Par = i;
		Rail[i].Rank = 0;
	}
}

int root(int X, Union Y[]) {
	if (Y[X].Par == X) return X;
	else return Y[X].Par = root(Y[X].Par, Y);
}

void unite(int X, int Y, Union Z[]) {
	X = root(Z[X].Par, Z), Y = root(Z[Y].Par, Z);
	if (X == Y) return;
	if (Z[X].Rank < Z[Y].Rank) Z[X].Par = Y;
	else {
		Z[Y].Par = X;
		if (Z[X].Rank == Z[Y].Rank) Z[X].Rank++;
	}
}

bool same(int X, int Y, Union Z[]) {
	return root(Z[X].Par, Z) == root(Z[Y].Par, Z);
}

int main() {
	int N, K, L;
	cin >> N >> K >> L;
	init(N);
	for (int i = 0; i < K; i++) {
		int p, q;
		cin >> p >> q;
		p--, q--;
		unite(p, q, Road);
	}
	for (int i = 0; i < L; i++) {
		int r, s;
		cin >> r >> s;
		r--, s--;
		unite(r, s, Rail);
	}
	map<pair<int, int>, int> mp;
	for (int i = 0; i < N; i++) {
		mp[{root(Road[i].Par, Road), root(Rail[i].Par, Rail)}]++;
	}
	for (int i = 0; i < N; i++) {
		if (i != 0) cout << " ";
		cout << mp[{root(Road[i].Par, Road), root(Rail[i].Par, Rail)}];
	}
}

Measured memory_bytes: 15104