akhauriyash/Code-Regression huggingface dataset:
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <iostream>
#include <fstream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <map>
#include <functional>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
#include <cstdint>
#include <chrono>

using namespace std;
#define     loop(n,i,a)     for(ll i=a;i<n;i++)
#define     loopR(n,i,a)    for(ll i=a-1;i>=n;i--)
#define     all(arr,n)      arr,arr+n
#define     allv(v)         (v).begin(),(v).end()
#define     rallv(v)        (v).rbegin(),(v).rend()
#define     m_p             make_pair
#define     ll              long long
#define     pii             pair<ll,ll>
#define     vi              vector<int>
#define     vll             vector<ll>
#define     vii             vector<pii>
#define     sz(x)           (int)x.size()
#define     pb              push_back
#define     endl            "\n"
#define     Endl            "\n"
#define     f               first
#define     s               second
#define     mem(dp,n)       memset(dp,n,sizeof dp)
template<typename T>void max_self(T &a,T b){a=max(a,b);}
template<typename T>void min_self(T &a,T b){a=min(a,b);}
int dx[] = { 1 , 0 ,-1 , 0 ,-1 ,-1 , 1 , 1 };
int dy[] = { 0 , 1 , 0 ,-1 ,-1 , 1 ,-1 , 1 };
int KnightI[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int KnightJ[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
void fast(){
    std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
vector<string> vec_splitter(string s) {
    s += ',';
    vector<string> res;
    while(!s.empty()) {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out(
        vector<string> __attribute__ ((unused)) args,
        __attribute__ ((unused)) int idx,
        __attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
    if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
const ll mxN=4e5+10,oo=0x3f3f3f3f,MOD=1e9+7;
const long double PI = acos(-1),eps=1.0e-14;
void solve(){
    int n,x;
    cin>>n>>x;
    vll v;
    loop(n,i,0){
        ll y;
        cin>>y;
        v.pb(y);
    }
    v.pb(x);
    sort(allv(v));
    ll res=0;
    loop(n,i,0){
        res=__gcd(res,v[i+1]-v[i]);
    }
    cout<<res<<endl;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    fast();
    solve();

}


Measured memory_bytes: 4256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <sstream>
#include <cmath>
#include <functional>
#include <fstream>
#include <cstdlib>
typedef long long ll;
const ll MOD = 1e9+7;


#define REP(i, N) for (ll i = 0; i < (N); i++)
#define REPP(i, a, b) for (ll i = (a); i < (b); i++)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define VSORT(c) sort((c).begin(),(c).end())
#define SZ(x) ((ll)(x).size())
//vvintを作る　マクロで　 #define vvint(N,M) vector<vector<ll>>

using namespace std;
// 変数初期化
vector<ll> bsv; // binary_search用のvector
ll a,b,c,n,m;
typedef pair<ll, ll> Pll;
vector<Pll> facts; // 素因数分解の結果格納用(基数:乗数)
vector<vector<ll> > bit_search_v; //nit全探索の結果格納用

// index が条件を満たすかどうか
bool isOK(ll index, ll key) {
    if (bsv[index] >= key) return true;
    else return false;
}

// 汎用的な二分探索のテンプレ
ll binary_search(int key) {
    int ng = -1;
    int ok = (ll)bsv.size();

    /* ok と ng のどちらが大きいかわからないことを考慮 */
    while (abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;

        if (isOK(mid, key)) ok = mid;
        else ng = mid;
    }
    // OK(key以上となる)のindex番号を返す
    return ok;
}

// 最大公約数
int gcd(int a, int b) {
    if (b==0) return a;
    else return gcd(b, a%b);
}

// 最小公倍数
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

//　素因数分解
void prime_fact(ll target){
    ll base=2, exp=0;
    while (base*base<=target) {
        while (target%base==0) {
            target /= base; exp++;
        }
        if (exp>0) {
            facts.push_back(make_pair(base, exp));
        }
        base++; exp=0;
    }
    if (target>1) facts.push_back(make_pair(target,1));
}
// prime_factの結果の確認用
void print_facts(){
    for (int i=0; i<facts.size(); i++) {
        cout << facts[i].first << " " << facts[i].second << endl;
    }
}

// bit全探索
void bit_search(ll target){
    for (ll i=0; i<(1<<target); ++i) {
        if (i==0) continue;
        vector<ll> v;
        for (ll j=0; j<target; ++j) {
            if (i&(1<<j)) v.push_back(j);
            if (i&(1<<j)) cout << i << "  :  " << j << endl;
        }
        bit_search_v.push_back(v);
    }
}
// bit全探索の結果確認用
void print_bit_search(){
    for (ll i=0; i<bit_search_v.size(); ++i) {
        for (ll j=0; j<bit_search_v[i].size(); ++j) {
            cout << bit_search_v[i][j] << " ";
        }
        cout << endl;
    }
}



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

    string s;
    cin >> s;;
    if(s == "ABC"){
        cout << "ARC" << endl;
        return 0;
    }

    cout << "ABC" << endl;
    

    return 0;
}

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

using namespace std;

typedef long long ll;

bool chk(ll k, ll n){
	ll t = n;
	while(t >= k){
		if(t % k == 0){
			t /= k;
		}else{
			t %= k;
		}
	}

	return t == 1;
}

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

	ll n;
	cin >> n;

	ll ans = 1;
	ll t = n - 1;
	for(ll i = 2; i * i <= n; i++){
		ll cnt = 0;
		while(t % i == 0){
			cnt++;
			t /= i;
		}
		ans *= cnt + 1;
	}

	if(t > 1) ans *= 2;

	for(ll k = 2; k * k<= n; k++){
		if(n % k == 0){
			if(chk(k, n)) ans++;
			if(k * k < n){
				if(chk(n / k, n)) ans++;
			}
		}
	}
	
	cout << ans<< endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, A;
  int a;
  
  cin >> N >> A;
  
  a = N % 500;
  
  if ( A >= a ){
	cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

#define MOD 1000000007

typedef long long ll;

ll fac[222222] = {1, 1};
ll inv[222222] = {1, 1};
ll fiv[222222] = {1, 1};

ll permutation(ll n, ll r)
{
	ll i, ret = 1;

	for (i = n; i >= n - r + 1; i--)
		ret = ret * i % MOD;

	return ret;
}

ll pow2(ll n)
{
	if (!n)
		return 1;

	ll t = pow2(n / 2);

	if (n % 2 == 0)
		return t * t % MOD;
	else
		return t * t % MOD * 2 % MOD;
}

int main(void)
{
	ll n, a, b, i;

	scanf("%lld %lld %lld" ,&n, &a, &b);

	for (ll i = 2; i <= max(a, b); i++)
	{
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
		fiv[i] = fiv[i - 1] * inv[i] % MOD;
	}

	ll ans = pow2(n) - permutation(n, a) * fiv[a] % MOD - permutation(n, b) * fiv[b] % MOD - 1;

	printf("%lld" ,(ans + 2 * MOD) % MOD);
	return 0;
}

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

int main() {

    int S,W;
    cin >> S >> W;
    
    if (W >= S) {
        cout << "unsafe" << endl;
    }
    
    else { cout << "safe" << endl;
         }
}



Measured memory_bytes: 3592
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    s = str(readline().rstrip().decode('utf-8'))
    cnt = 0
    for i in range(len(s)):
        if cnt == 0:
            if s[i] == "C":
                cnt += 1
        elif cnt == 1:
            if s[i] == "F":
                print("Yes")
                exit()
    print("No")


if __name__ == '__main__':
    solve()


Measured memory_bytes: 38256
#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>;

int main() {
  ll x, k, d;
  cin >> x >> k >> d;

  x = abs(x);
  ll ans;

  if (x / d > k) {
    ans = x - d * k;
  } else {
    ll e = x / d;
    k -= e;
    x -= e * d;
    if (k % 2 == 1) x = abs(x - d);
    ans = x;
  }

  cout << ans << endl;
  return 0;
}


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

using namespace std;

#define REP(i,n) for(int (i) = (0);(i) < (n);++i)

int main(){
	int n;cin >> n;
	REP(i, n){
		REP(j, n){
			if(i >= j)continue;
			for(int k = 30;k >= 0;k--){
				if((i & (1 << k)) != (j & (1 << k))){
					cout << (k + 1) << " ";
					break;
				}
			}
			cout << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(ll i = 0; i < (ll) n; i++)
#define vl vector<long long>
#define vs vector<string>

int main() {
    ll X; cin >> X;
    if(X >= 30){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

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

long long A, B, C;
int solve() {
    for (int i = 0; i < 50; ++i) {
        if (A & 1) return i;
        if (B & 1) return i;
        if (C & 1) return i;
        long long tA = (B + C) / 2;
        long long tB = (C + A) / 2;
        long long tC = (A + B) / 2;
        A = tA, B = tB, C = tC;
    }
    return -1;
}

int main() {
    cin >> A >> B >> C;
    cout << solve() << endl;
}

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

int q, mas[10][10], dy[] = { 1, 1, 2}, dx[] = { 0, 1, 0};
int draw[][5][5] = {
  /*Small*/
  {{ 0, 0, 1, 0, 0},
   { 0, 1, 1, 1, 0},
   { 0, 0, 1, 0, 0}},
  //*midium*/
  {{ 0, 0, 1, 1, 1},
   { 0, 0, 1, 1, 1},
   { 0, 0, 1, 1, 1}},
  /*large*/
  {{ 0, 0, 1, 0, 0},
   { 0, 1, 1, 1, 0},
   { 1, 1, 1, 1, 1},
   { 0, 1, 1, 1, 0},
   { 0, 0, 1, 0, 0}},
};

bool check( int y, int x, int w){
  for(int i = 0 ; i < 5 ; i++ ){
    for(int j = 0 ; j < 5 ; j++ ){
      if(x + j - 2 < 0) continue;
      if(mas[y + i][x + j - 2] - draw[w][i][j] < 0) return false;
    }
  }
  return true;
}

void paint( int y, int x, int w){
  for(int i = 0 ; i < 5 ; i++ ){
    for(int j = 0 ; j < 5 ; j++ ){
      if(x + j - 2 < 0) continue;
      mas[y + i][x + j - 2] -= draw[w][i][j];
    }
  }
}

void repaint( int y, int x, int w){
  for(int i = 0 ; i < 5 ; i++ ){
    for(int j = 0 ; j < 5 ; j++ ){
      if(x + j - 2 < 0) continue;
      mas[y + i][x + j - 2] += draw[w][i][j];
    }
  }
}

bool rec( int y, int x, int n){
  if( n < 0 ) return false;
  if( y == 10 ) return n == 0;
  if( mas[y][x] == 0 ) return rec( y + (x == 9), (x + 1) % 10, n);
  for(int i = 0 ; i < 3 ; i++ ){
    if(!check( y, x, i)) continue;
    paint( y, x, i);
    if(rec( y, x, n - 1)){
      cout << x + (i == 1) << " " << y + 1 + (i == 2) << " " << i + 1 << endl;
      return true;
    }
    repaint( y, x, i);
  }
  return false;
}

int main(){
  cin >> q;
  for(int i = 0 ; i < 10 ; i++ ){
    for(int j = 0 ; j < 10 ; j++ ){
      cin >> mas[i][j];
    }
  }
  rec( 0, 0, q);
 }

Measured memory_bytes: 1160
#include <iostream>
#include <string>
#include <algorithm> 
#include <cstdlib>
#include <map>
#include <queue>
#include <vector>
#include <cmath>
#include <limits>
#include <stack>
#define ll long long
using namespace std;
int main(){
    string s;
    string ans;
    cin >> s;
    for(int i=0;i<s.size();i++){
        if(s[i]=='1')ans=ans+'1';
        else if(s[i]=='0')ans=ans+'0';
        else{
            if(ans.empty()){
            }else{
                ans.erase(ans.size()-1);
            }
        }
    }
    cout << ans << endl;
}

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



signed main(){
    ll n;
    cin>>n;
    ll res=0;
    ll m=0;
    for(ll i=0;i<n;i++){
        ll t;
        cin>>t;
        if(t>m){
            m =t;
        }
        else res+=m-t;
    }
    cout<<res<<endl;
}

Measured memory_bytes: 3636
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size1,init=nil,size2=1) #size2に二次元配列時の最初の要素数、size1に次の配列の大きさ、initに初期値を投げることでその配列を返す
  if size2==1
    return Array.new(size1){init}
  else
    return Array.new(size2){Array.new(size1){init}}
  end
end

N,M=get_i
broken=array(N+2,0)
M.times do|i|
    a=gets.to_i
    broken[a]=1
end
dp=array(N+1,0)

dp[0]=1
dp[1]=1 if broken[1].zero?
(N-1).times do|i|
    dp[i+2]=dp[i]+dp[i+1] if broken[i+2].zero?
    dp[i+2]%=10**9+7
end
puts dp[N]

Measured memory_bytes: 3580
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

#define _CRT_SECURE_NO_WARNINGS
#define TLong long long 

// fact(n)
int fact(int n){
	if(n == 1)	return 1;
	else return (n * fact(n - 1));
}

// combination(n,r)
int combination(int n, int r){
	if(r == 0 || r == n)	return 1;
	else if(r == 1)	return n;
	return (combination(n - 1, r - 1) + combination(n - 1, r));
}

// gcd(a,b)
int gcd(int a,int b){
	int ret;
	ret = (b == 0) ? a : gcd(b, a % b);
	return ret;
}

// lcm(a.b)
int lcm(int a,int b){
	return (a * b) / gcd(a,b);
}

// qsort(array, size, sizeof(int),comp);
int comp(const int *a,const int *b){
	return (*a - *b);
}

// append(array,*size,addNum)
void append(int *array,int *size,int num){
	realloc(array, sizeof(int) * (*size + 1));
	array[(*size)] = num;
	++(*size);
}

// pop(array,*size) & nongetpop(array,*size)
int pop(int *array,int *size){
	int temp = array[(*size - 1)];
	realloc(array,sizeof(int) * (*size - 1));
	--(*size);
	return temp;
}

void nongetpop(int *array,int *size){
	realloc(array,sizeof(int) * (*size - 1));
	--(*size);
}

int main(int argc, char const *argv[])
{
	int m;
	scanf("%d",&m);
	printf("%d\n", 48 - m);
	return 0;
}



Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    string t;
    cin >> t;
    //sとtの最後以外の文字が一緒ならおけ　
    if(t.substr(0,s.length())== s) cout << "Yes" <<endl;
    else cout << "No" <<endl;
}   

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pii> vpi;
typedef map<int,int> mapii;
typedef map<int,bool> mapib;
typedef map<char,int> mapci;
typedef priority_queue<int> pr;

#define small 1e-9
#define big5 1000000005
#define big7 1000000007
#define big 100000
#define pi 3.1415926

#define inp(arr,n) for(int i=0;i<n;i++)cin>>arr[i];
#define cum(arr,n,cumm) cumm[0]=arr[0];for(int i=1;i<n;i++)cumm[i]=cumm[i-1]+arr[i];
#define bsdk ios_base::sync_with_stdio(false);cin.tie(NULL);
#define disp(arr) for(auto i:arr)cout<<i<<" ";cout<<"\n"
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define yess cout<<"Yes\n"
#define noo cout<<"No\n"
#define m1 cout<<"-1\n"
#define nl <<endl
#define hs cout<<"#"

#define fori(a, b, c) for (a = (b); (a) <= (c); ++(a))
#define ford(a, b, c) for (a = (b); (a) >= (c); --(a))
#define rep(i,n) fori(i,0,n-1)
#define repi(i,n) fori(i,1,n-1)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pob pop_back
#define ub upper_bound
#define lb lower_bound
#define allv(v) v.begin(), v.end()
#define sorti(v) sort(allv(v))
/*bool isprime[big+1];
vector<int> primes;
void makesieve()
{
    ll i,j;
    rep(i,big+1)
        isprime[i]=false;
    isprime[2]=true;
    for(i=3;i<=big;i+=2)
        isprime[i]=true;
    for(i=3;i<=big;i+=2)
    {
        if(isprime[i])
            for(j=i*i;j<=big;j+=i)
            isprime[j]=false;
    }
    rep(i,big+1)
    {
        if(isprime[i])
            primes.pb(i);
    }
}
vpi fact(ll n)
{
    ll i=0;
    vpi pf;
    ll c;
    while(primes[i]*primes[i]<=n)
    {
        if(n%primes[i]==0)
        {
            c=0;
            while(n%primes[i]==0)
                {
                    n=n/primes[i];
                    c++;
                }
            pf.pb(mp(primes[i],c));
        }
        i++;
    }
    if(n!=1)
        pf.pb(mp(n,1));
    return pf;
}
ll poww(ll n,ll m){
    if(m==0)return 1;
    if(m==1)return n;
    ll ans = poww(n,m/2);
    if(m%2==1) return (ans*ans)*n;
    else return (ans*ans);
}*/

void solve()
{
    int n;
    cin>>n;
    string s;
    int a,b,c,d;
    a=b=c=d=0;
    while(n--)
    {
        cin>>s;
        if(s=="AC")
            a++;
        else if(s=="WA")
            b++;
        else if(s=="TLE")
            c++;
        else
            d++;
    }
    cout<<"AC x "<<a nl;
    cout<<"WA x "<<b nl;
    cout<<"TLE x "<<c nl;
    cout<<"RE x "<<d nl;
}
int main()
{
    bsdk
    int t;
    //cin>>t;
    t=1;
    //makesieve();
    while(t--) solve();
    return 0;
}


Measured memory_bytes: 3644
k = int(input())
 
n = [1, 2, 3, 4, 5, 6, 7, 8, 9]
if k < len(n):
    print(str(n[k-1]))
else:
    count = 9
    while 1:
        x = n.pop(0)
        if x % 10 != 0:
            n.append(10*x + x % 10 - 1)
            count += 1
        n.append(10*x + x % 10)
        count += 1
        if x % 10 != 9:
            n.append(10*x + x % 10 + 1)
            count += 1
        if count >= k:
            print(n[-(count-k)-1])
            break
        



Measured memory_bytes: 5852
def resolve():
    s = input()
    print(
        sum(
            eval(s)
            for s in [
                "".join(
                    s[i] + "+" if i < 9 and 1 << i & b else s[i] for i in range(len(s))
                )
                for b in range(2 ** (len(s) - 1))
            ]
        )
    )


if __name__ == "__main__":
    resolve()

Measured memory_bytes: 39664
#include<stdio.h>
#define MAX 100000
int main(){
  int n, i;
  int A[MAX+1];

  scanf("%d", &n); // input the number of data
  for ( i = 1; i <= n; i++ ) scanf("%d", &A[i]);

  for ( i = 1; i <= n; i++ ) {
    printf("node %d: key = %d, ", i, A[i]);
    if ( i / 2 >= 1 )printf("parent key = %d, ", A[i/2]);
    if ( i*2 <= n ) printf("left key = %d, ", A[i*2]);
    if ( i*2+1 <= n ) printf("right key = %d, ", A[i*2+1]);
    printf("\n");
  }
  
  return 0;
}



Measured memory_bytes: 2596
#include <stdio.h>
#include <math.h>

int main(void) {
	long X;
	long A, B;
	long ta, tb;
	
	scanf("%ld", &X);
	
	for(A = 0; ; A++ ) {
		if( (ta = pow(A, 5)) == X ) {
			B = 0;
			break;
		}
		if( ta < X ) {
			for(B = -1; ; B-- ) {
				if( (tb = (ta - pow(B, 5))) == X) {
					break;
				}
				if( tb > X ) {
					B = 0;
					break;
				}
			}
		}
		else {
			for(B = 1; ; B++ ) {
				if( (tb = (ta - pow(B, 5))) == X) {
					break;
				}
				if( tb < X ) {
					B = 0;
					break;
				}
			}
		}
		
		if( B != 0 ) {
			break;
		}
	}
	
	printf("%ld %ld\n", A, B);
	
	return 0;
}


Measured memory_bytes: 2536
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define ll long long
using namespace std; 
const int N=200010;
ll n,num,m,x; 
ll a[N],f[N],s[N]; 
void solve(ll x,ll k){
	if (x<a[1]){
		s[x]+=k;
		return;
	}
	ll l=1,r=num,y;
	while (l<=r){
		ll mid=(l+r)/2;
		if (a[mid]<=x){
			y=mid;
			l=mid+1;
		}else r=mid-1;
	}
	f[y]+=k*(x/a[y]);
	x=x%a[y];
	if (x) solve(x,k);
}
int main(){
	scanf("%lld%lld",&n,&m);
	num=1;
	a[1]=n;
	for (ll i=1; i<=m; i++){
		scanf("%lld",&x);
		while (x<=a[num]&&num)
			--num;
		num++;
		a[num]=x;
	}
	f[num]=1;
	for (ll i=num-1; i>=1; i--){
		f[i]+=f[i+1]*(a[i+1]/a[i]);
		solve(a[i+1]%a[i],f[i+1]);
	}
	for (ll i=a[1]; i>=1; i--)
		s[i]+=s[i+1];
	for (ll i=1; i<=a[1]; i++)
		s[i]+=f[1];
	for (ll i=1; i<=n; i++)
		printf("%lld\n",s[i]);
	return 0;
}

Measured memory_bytes: 5572
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)
ans = 0
for i in range(1,n+1,2):
  if len(make_divisors(i)) == 8:
    ans += 1
print(ans)

Measured memory_bytes: 3188
#include <iostream>

using namespace std;

int main(){

  int N,Y;

  scanf("%d %d", &N, &Y);

  for(int i=0; i<=N; i++){
    for(int j=0; i+j<=N; j++){
      if(10000*i+5000*j+1000*(N-i-j)==Y){
        cout << i << ' ' << j << ' ' <<  N-i-j << endl;
        return 0;
      }
    }
  }

  cout << "-1 -1 -1" << endl;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
#define REPi(i, a, b) for(int i=int(a); i<int(b); i++)
#define MEMS(a,b) memset(a,b,sizeof(a))
#define mp make_pair
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll MOD = 1e9+7;
const ll INF = 1e12;

ll N;
ll A[200100];
vector<ll> G[200100];
ll ans[200100];

void dfs(ll v, vector<ll>& table, ll parant){
    int idx = lower_bound(table.begin(), table.end(), A[v]) - table.begin();
    ll orig = table[idx];
    if(table[idx] > A[v])
        table[idx] = A[v];

    ll len = lower_bound(table.begin(), table.end(), INF) - table.begin();
    ans[v] = len;

    int first = -1;
    for(auto&& n : G[v]){
        if(n == parant)
            continue;
        else{
            dfs(n, table, v);
        }
    }

    table[idx] = orig;
}

int main(){
    cin >> N;
    REP(i,N){
        ll a;
        cin >> a;
        A[i] = a;
    }

    REP(i,N-1){
        ll u, v;
        cin >> u >> v;
        u--, v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    vector<ll> table(N, INF);
    dfs(0, table, -1);

    REP(i,N){
        cout << ans[i] << endl;
    }
    return 0;
}


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

int parent(int n) { return n / 2; }
int left(int n) { return n * 2; }
int right(int n) { return n * 2 + 1; }

int main()
{
    int n;
    cin >> n;
    int a[n + 1];
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        printf("node %d: key = %d, ", i, a[i]);
        if (parent(i) > 0)
            printf("parent key = %d, ", a[parent(i)]);
        if (left(i) <= n)
            printf("left key = %d, ", a[left(i)]);
        if (right(i) <= n)
            printf("right key = %d, ", a[right(i)]);
        cout << endl;
    }
}


Measured memory_bytes: 3244
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define PI acos(-1.0)
#define lowbit(x) (x&-x)
#define pb(x) push_back(x)
#define mp(x) make_pair(x)

typedef long long ll;
typedef long double ld;
const int maxn=1e6+10;
map<int,int> a,b;

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        a[x]++;
    }
    int m;
    scanf("%d",&m);
    for(int i=0;i<m;i++)
    {
        int x;
        scanf("%d",&x);
        b[x]++;
    }
    map<int,int>::iterator it1,it2;
    it1=a.begin();
    it2=b.begin();
    while(it2!=b.end()&&it1!=a.end())
    {
        if(it1->first!=it2->first)
        {
            it1++;
            continue;
        }
        if(it1->second<it2->second)
            break;
        it2++;
    }
    if(it2!=b.end()||it1==a.end())
        printf("NO\n");
    else
        printf("YES\n");
    return 0;
}


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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define ALL(a) (a).begin(), (a).end()
#define rALL(a) (a).rbegin(), (a).rend()
#define SZ(x) ((int)(x).size())
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 28;
const ll INF64 = 1ll << 55;
const int mod = 1000000007;
//const int mod = 998244353;

template <class T>inline bool chmin(T &a, const T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline bool chmax(T &a, const T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline void line_out(const vector<T> vec) {
  int n = SZ(vec);
  rep(i, n) {
    cout << vec[i];
    if(i < n-1) cout << " ";
  }
  cout << endl;
  return;
}

struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};


int main()
{
  int n; cin >> n;
  vector<vector<P>> vec(n);
  rep(i, n) {
    int a; cin >> a;
    rep(j, a) {
      int x,y;
      cin >> x >> y;
      --x;
      vec[i].emplace_back(x, y);
    }
  }

  int ans = 0;
  for(int bit = 0; bit < 1<<n; ++bit) {
    bool ok = true;
    int c = 0;

    rep(i, n) if(bit & 1<<i) {
      ++c;
      for(auto d : vec[i]) {
        int x = d.first, y = d.second;
        if(y == 1) if(!(bit & 1<<x)) ok = false;
        if(y == 0) if(bit & 1<<x) ok = false;
      }
    }

    if(ok) chmax(ans, c);
    
  }
  cout << ans << endl;
}

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

#define ll       long long
#define LL       long long
#define ull      unsigned ll
#define pii      pair<int, int>
#define pll      pair<ll, ll>
#define mp       make_pair
#define ff       first
#define ss       second
#define sz(s)    (int) s.size()
#define all(s)   s.begin(), s.end()

template<typename T> inline void smin(T &a, T b) {
    a = a < b ? a : b;
}
template<typename T> inline void smax(T &a, T b) {
    a = a > b ? a : b;
}

template<typename T> inline void Int(T &n) {
    n = 0;
    int f = 1;
    register int ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) n = (n << 3) + (n << 1) + ch - '0';
    n *= f;
}
template<typename T, typename TT> inline void Int(T &n, TT &m) {
    Int(n), Int(m);
}
template<typename T, typename TT, typename TTT> inline void Int(T &n, TT &m, TTT &l) {
    Int(n), Int(m, l);
}

#define error(args...) { string _s = #args; replace(all(_s), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {
    cout << endl;
}
template<typename T, typename... Args> void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << ", ";
    err(++it, args...);
}

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

int add(int a, int b) {
    a += b;
    if(a >= mod) a -= mod;
    return a;
}
int sub(int a, int b) {
    a -= b;
    if(a <= 0) a += mod;
    return a;
}
int mul(int a, int b) {
    return (ll) a * b % mod;
}

const int inf = (int) 2e9 + 5;
const ll  Inf = (ll) 2e18 + 5;
const int   N = (int) 2e5 + 5;




int solve() {
    int n, w;
    Int(n, w);
    vector<ll> dp(w + 1, 0);
    for(int i = 1; i <= n; i++) {
        ll wt, val; Int(wt, val);
        for(int j = w; j >= 0; j--) {
            if(j - wt >= 0) smax(dp[j], dp[j - wt] + val);
        }
    }
    ll ans = 0;
    for(int i = 1; i <= w; i++) {
        smax(ans, dp[i]);
    }
    printf("%lld\n", ans);
    return 0;
}

int main() {
    int test = 1, tc = 0;
    //Int(test);
    while(test--) {
        //printf("Case %d: ", ++tc);
        solve();
    }
    return 0;
}




Measured memory_bytes: 1024
import collections
N = int(input())
S = list(input())
cnt = 0

ans = [0]*N

for i in range(1,N):
    if S[i] == "E":
        cnt += 1
ans[0] = cnt

for i in range(1,N):
    if S[i-1] == 'E' and S[i] == 'E':
        ans[i] = ans[i-1]-1
    elif S[i-1] == "W" and S[i] == 'W':
        ans[i] = ans[i-1]+1
    else:
        ans[i] = ans[i-1]
     
print(min(ans))


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

const ll INF = 1e18;

int main()
{
	ios_base::sync_with_stdio(false);

	int n;
	cin >> n;
	vector<vector<int>> a(n, vector<int> (3));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> a[i][j];
		}
	}
	vector<vector<ll>> dp(n, vector<ll> (3));
	for (int i = 0; i < 3; i++)
	{
		dp[0][i] = a[0][i];
	}
	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			dp[i][j] = -INF;
			for (int k = 0; k < 3; k++)
			{
				if (k == j)
					continue;
				dp[i][j] = max(dp[i][j], a[i][j] + dp[i - 1][k]);
			}
		}
	}
	ll answer = 0;
	for (int i = 0; i < 3; i++)
	{
		answer = max(answer, dp[n - 1][i]);
	}
	cout << answer;

	return 0;
}

Measured memory_bytes: 14284
require 'prime'

def aux(n)
  f=Prime.prime_division(n)
  f.map{|x| [x[0]]*x[1]}.flatten
end

def main
  fh=STDIN
  #fh=File.new("x.txt", "r")
  n=  fh.gets.chomp.to_i
  puts "#{n}: #{aux(n).map(&:to_s).join(' ')}"
end

if $0 == __FILE__ then
  main
end


Measured memory_bytes: 7020
#include<iostream>
#include<stdio.h>

using namespace std;

int main(){
    double a,b,c,d,e,f;
    while(cin>>a>>b>>c>>d>>e>>f){
        double y = (a*f-c*d)/(a*e-b*d);
        double x = (c-(b*y))/a;
        if(x==0) x=0.000;
        if(y==0) y=0.000;
        printf("%.3lf %.3lf\n",x,y);
    }
    return 0;
}

Measured memory_bytes: 1236
import sys
from collections import deque
import copy


def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]),int(input_raw[1])]
    p_list = []
    input_raw = read_func().strip().split()
    for i in range(N):
        p_list.append(int(input_raw[i]))
    swap_list = {}
    for i in range(M):
        input_raw = read_func().strip().split()
        [x, y] =  [int(input_raw[0]),int(input_raw[1])]
        if x not in swap_list:
            swap_list[x] = [y]
        else:
            swap_list[x].append(y)
        if y not in swap_list:
            swap_list[y] = [x]
        else:
            swap_list[y].append(x)

    done_list = [False for i in range(N + 1)]
    done_list[0] = True

    adj_set_list = [set([]) for i in range(N + 1)]
    
    for i in range(1, N + 1):

        if done_list[i] == True:
            continue
        nd_list = deque([i])
        while 1:
            if len(nd_list) == 0:
                break
            nd = nd_list.popleft()
            #done_list[nd] = True
            adj_set_list[i].add(nd)
            adj_set_list[nd] = adj_set_list[i]
            if nd in swap_list:
                for adj in swap_list[nd]:
                    if done_list[adj] == True:
                        continue
                    done_list[adj] = True
                    nd_list.append(adj)
    count = 0
    for i in range(len(p_list)):
        if p_list[i] in adj_set_list[i + 1]:
            count += 1
    print count




if __name__ == '__main__':
    main()


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

using namespace std;

using ll = int64_t;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = INT_MAX;
constexpr ll L_INF = LLONG_MAX;

//===




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

	string s;
	cin >> s;
	int x, y;
	cin >> x >> y;

	Vi vx, vy;
	bool first = true;
	bool swc = false;
	int cnt = 0;
	int first_f = 0;
	for (const auto& si : s) {
		if (first) {
			if (si == 'T') first = false;
			else ++first_f;
			continue;
		}

		if (si == 'T') {
			if (swc && cnt > 0) vx.push_back(cnt);
			else if (!swc && cnt > 0) vy.push_back(cnt);
			cnt = 0;
			swc ^= true;
		}
		else ++cnt;
	}

	if (swc && cnt > 0) vx.push_back(cnt);
	else if (!swc && cnt > 0) vy.push_back(cnt);
	

	sort(vx.begin(), vx.end(), greater<int>());
	sort(vy.begin(), vy.end(), greater<int>());

	bool ans = true;

	int tmp;
	tmp= x - first_f;
	for (const auto& val : vx) {
		tmp = abs(tmp);
		tmp -= val;
	}
	if (tmp != 0) ans = false;

	tmp = y;
	for (const auto& val : vy) {
		tmp = abs(tmp);
		tmp -= val;
	}
	if (tmp != 0) ans = false;
	
	cout << (ans ? "Yes" : "No") << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main () {
    int h, w;

    while (true) {
        cin >> h >> w;

        if (h == 0 && w == 0) break;

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) cout << ((i + j) % 2 == 0 ? '#' : '.');
            cout << endl;
        }
        cout << endl;
    }
}


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

#define ll long long
#define ull unsigned long long
#define N 100005
#define mod 1000000007
#define boost ios_base::sync_with_stdio(false);cin.tie(0)
#define prec(n) fixed<<setprecision(n)

#define pii pair<int,int> 
#define pll pair<ll,ll> 
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define vi vector<int> 
#define vll vector<ll>
#define all(c) c.begin(),c.end()
#define tr(it,c) for( typeof(c.begin()) it = c.begin() ; it!=c.end() ; it++)

ll modulo(ll num){ return ((num%mod)+mod)%mod;} // for negative integer
ll power(ll b,ll e,ll MOD=mod){ll ans=1; while(e){if(e%2) ans=(ans*b)%MOD; b=(b*b)%MOD; e/=2;} return ans;}
ll inv(ll num,ll MOD=mod){ return power(modulo(num),mod-2,MOD); }

int main()
{
    boost;
    
    string s; int i,n,l[3*N],r[3*N] ; 
    
    cin>>n;
    cin>>s;
    s=' '+s;
    l[0]=0; r[n+1]=0;
    
    
    for(i=1;i<=n;i++)
    {
        if(s[i]=='W')  l[i]=l[i-1]+1;
        else 
        l[i]=l[i-1];
    }
    
    
    for(i=n;i>0;i--)
    {
        if(s[i]=='E') r[i]=r[i+1]+1 ; 
        else
        r[i]=r[i+1];
    }
    
    int ans = mod;
    
    for(i=1;i<=n;i++)
    {
        ans = min(ans, l[i-1] + r[i+1]);
    }
    
    cout<<ans<<endl;
    return 0;
}

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

using namespace std;

#define PI 3.14159265358979323846
#define mod 1000000007
#define ll long long
#define vi vector<int>
#define ii pair<int, int>
#define pb push_back
#define all(c) (c).begin(), (c).end()

const int N = 1e6;

int n, a[N], spf[N + 1], g;
bool vis[N + 1];

int gcd(int a, int b) {
	if (b == 0)
		return a;

	return gcd(b, a % b);
}

void sieve(int lim = N) {
	for (int i = 2; i <= lim; ++i) {
		if (spf[i] == 0) {
			for (int j = i; j <= lim; j += i)
				spf[j] = i;
		}
	}
}

vi factorize(int x) {
	vi ret;
	while (x != 1) {
		ret.pb(spf[x]);

		x /= spf[x];
	}

	return ret;
}

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

	cin >> n;
	for (int i = 0; i < n; ++i)
		scanf("%d", a + i);

	for (int i = 0; i < n; ++i)
		g = gcd(g, a[i]);
	
	if (g != 1)
		return puts("not coprime"), 0;

	sieve();
	vi v;
	for (int i = 0; i < n; ++i) {
		v = factorize(a[i]);

		for (int x : v)
			if (vis[x])
				return puts("setwise coprime"), 0;

		for (int x : v)
			vis[x] = 1;
	}

	puts("pairwise coprime");
}


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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (int i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define ALL(v) v.begin(), v.end()

const int MAX = 1e5+10;
const int MAXBIT = 62;
int N;
ll A[MAX];

ll solve() {
    ll allxor = 0;
    REP (i, N) allxor ^= A[i];
    REP (i, N) A[i] &= ~allxor;
    int rank = 0;
    REPR (i, MAXBIT) {
        int j = rank;
        while (j < N) {
            if (A[j] & (1ll<<i)) break;
            j++;
        }
        if (j == N) continue;
        swap(A[rank], A[j]);
        FOR (j, rank+1, N) {
            if (A[j] & (1ll<<i)) A[j] ^= A[rank];
        }
        rank++;
    }

    ll res = 0;
    REP (i, N) res = max(res, res^A[i]);
    return allxor + 2 * res;
}

int main() {
    cin >> N;
    REP (i, N) cin >> A[i];
    cout << solve() << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define _MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) _MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define mp make_pair
#define pb push_back
#define all(x) begin(x),end(x)
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cerr<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cerr<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

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

class SuffixArray {
public:
  const string &s;
  vector<int> sa, rank;
  int n;
  void construct_sa(){
    sa.resize(n+1);
    rank.resize(n+1);
    rep(i,n+1){
      sa[i]=i;
      rank[i] = (i<n)?s[i]:(-1);
    }
    vector<int> tmp(n+1,0);
    for(int k=1; k<=n; k*=2){
      auto comp = [&](const int i, const int j){
        if(rank[i]!=rank[j]) return rank[i]<rank[j];
        int ri = (i+k<=n)?(rank[i+k]):-1;
        int rj = (j+k<=n)?(rank[j+k]):-1;
        return ri < rj;
      };
      sort(all(sa), comp);
      tmp[sa[0]]=0;
      rep(i,1,n+1){
        tmp[sa[i]] = tmp[sa[i-1]];
        if(comp(sa[i-1], sa[i])) tmp[sa[i]]++;
      }
      swap(tmp, rank);
    }
  }
  SuffixArray(const string &str) : s(str){
    n = s.size();
    construct_sa();
  }
};


void solve(int n, ll h, string &str, int len){
  if(len == 0){
    cout << "0" << endl;
    return;
  }

  SuffixArray sa(str);
  vector<int> arr(n+1,0);
  rep(i,1,n+1) if(str[sa.sa[i]]>'0'){
    int idx = sa.sa[i];
    int d = 1;
    if(n-idx < len) d = 0;
    else {
      while(idx-d>=0 && str[idx-d]=='0') d++;
    }
    arr[i] = arr[i-1] + d;
    if(arr[i] >= h){
      cout << str.substr(idx, len) << endl;
      return;
    }
  }
  assert(false);
}

int main(void){
	int n;
	ll h;
	string str;
	scanf("%d%lld",&n,&h);
	cin >> str;
	int z=-1;
	vector<int> nonzero(n+1);
	vector<ll> cnt(n+1);
	for(int i=0;i<=n;i++){
		cnt[i]=0;
	}
	for(int i=n-1;i>=0;i--){
		if(str[i]>='1'){
			z=i;
		}
		nonzero[i]=z;
	}
	for(int i=0;i<n;i++){
		//printf("%d\n",nonzero[i]);
		if(nonzero[i]==-1)continue;
		cnt[n-nonzero[i]]++;
	}
	for(int i=n;i>1;i--){
		cnt[i-1]+=cnt[i];
	}
	ll len=0;
	for(int i=0;i<n;i++){
		if(str[i]=='0'){
			len++;
		}else{
			cnt[0]+=len*(len+1)/2LL;
			len=0;
		}
	}
	cnt[0]+=len*(len+1)/2LL;
	ll sum=0;
	for(int i=0;i<=n;i++){
		sum+=cnt[i];
		if(sum>=h){
			sum-=cnt[i];
			solve(n,h-sum,str,i);
			return 0;
		}
	}
	return 0;
}



Measured memory_bytes: 5472
#include<iostream>
#include<stdlib.h>

using namespace std;

int main(){

    int N;
    cin >> N;
    int A[N-1];
    int B[N];
    int i = 0;
    int j = 0;
    int k = 0;
    while(i != N){
        B[i] = 0;
        i++;
    }

    while(j != N-1){
        cin >> A[j];
        B[A[j]-1] = B[A[j]-1] + 1;
        j++;
    }
    while(k != N){
        cout << B[k] << endl;
        k++;
    }

    return 0;

}

Measured memory_bytes: 5160
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s,t;
    int i,j,c=0;
    while(cin>>s>>t)
    {
        int found =-1;
        found = s.find(t);
        if(found!=-1)
        {
            cout<<0<<endl;
        }
        else

        {
            int mn=10007;
            c=0;
            int l1=s.size();
            int l2=t.size();
            int k;
            if(l1==l2)
            {
                for(i=0; i<l1; i++)
                {
                    if(s[i]!=t[i])
                    {
                        c++;
                    }
                }
                cout<<c<<endl;
            }
            else
            {

                for(i=0; i<(l1-l2); i++)
                {
                    j=0;

                    for(k=i; k<l2+i; k++)
                    {
                        if(s[k]!=t[j])
                        {
                            c++;
                        }
                        j++;
                    }
                    if(c<mn)
                    {
                        mn=c;
                    }
                    c=0;
                }
                cout<<mn<<endl;
            }
        }

    }
}


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

int main() {
	int n,l[200010];
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>l[i];
	}
	for(int i=n;i>1;i-=2){
		cout<<l[i-1]<<" ";
	}
	cout<<l[0];
	for(int i=0;i<n;i+=2){
		
		if(n%2==0&&2+i<n){
					cout << " ";
			cout <<l[2+i];
		}
		else if(i+1<n&&n%2!=0){
						cout << " ";
				cout <<l[i+1];
			
		}
	}
	return 0;
}

Measured memory_bytes: 2944
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const ll inf=1000000007;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int gcd(int n,int m)
{
    if(n<m)
    {
        swap(n,m);
    }
    int r=n%m;
    while(r)
    {
        n=m;
        m=r;
        r=n%m;
    }
    return m;
}

int prime[1000005], ji=0;
int pa[1000005], a[1000005], n, p[1000005], b[1000005];

int main()
{
    pa[0]=pa[1]=1;
    for(ll i=2; i<=1000000; i++)
    {
        if(!pa[i])
        {
            prime[ji++]=i;
            for(ll j=i*i; j<=1000000; j=j+i)
            {
                pa[j]=1;
            }
        }
    }
    n=read();
    int jj=0;
    int ma=-1, flag=1;
    for(int i=0; i<n; i++)
    {
        a[jj]=read();
        b[i]=a[jj];
        if(!pa[a[jj]])
        {
            p[a[jj]]++;
            if(p[a[jj]]>1)
            {
                flag=0;
            }
        }
        else
            jj++;
    }
    if(flag)
    {
    for(int i=0; i<jj; i++)
    {
        for(int j=0; j<=ji&&prime[j]<=a[i]; j++)
        {
            if(a[i]%prime[j]==0)
            {
                if(p[prime[j]]!=0)
                {
                    flag=0;
                    j=inf;
                    i=inf;
                    break;
                }
                while(a[i]%prime[j]==0)
                {
                    p[prime[j]]++;
                    a[i]=a[i]/prime[j];
                }
                if(!pa[a[i]])
                {
                    if(p[a[i]]!=0)
                    {
                        flag=0;
                    j=inf;
                    i=inf;
                        break;
                    }
                    p[a[i]]++;
                    break;
                }
            }
        }
    }
    }
    if(flag)
    {
        printf("pairwise coprime\n");
    }
    else
    {
        int g=b[0];
        for(int i=1;i<n;i++)
        {
            g=gcd(g,b[i]);
        }
        if(g==1)
        {
            printf("setwise coprime\n");
        }
        else
        {
            printf("not coprime\n");
        }
    }
    return 0;
}


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

int main() {
  int n, l;
  cin >> n >> l;
  string s[n];
  for(int i = 0; i < n; i++) {
    cin >> s[i];
  }
  sort(s, s + n);
  for(int i = 0; i < n; i++) {
    cout << s[i];
  }
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;

public class Main
{
	public static void main(String [] Args)
	{
		Scanner in=new Scanner(System.in);		
		int n=in.nextInt();
		int [] a=new int [n];
		for(int i=0;i<n;i++)
		{
			a[i]=in.nextInt();
		}
		Arrays.sort(a);
		int ans=0;
		for(int i=0;i<n-1;i++)
		{
			for(int j=i+1;j<n;j++)
			{
				for(int k=j+1;k<n;k++)
				{
					if(a[k]<a[i]+a[j])
					{
						ans++;
					}
					else
					{
						k=n;
					}
				}
			}
		}
		System.out.println(ans);
	}
}
	

Measured memory_bytes: 26216
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
string s,t;
int ans;
int main(void){
    s="CODEFESTIVAL2016";
    cin>>t;
    for(int i=0;i<16;i++){
        if(s[i]!=t[i]){
            ans++;
        }
    }
    cout<<ans<<endl;
    
}


Measured memory_bytes: 3628
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,a,b) for(int i =(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPm(i,n) for(int i=(n)-1;i>=0;i--)
#define REP1(i,n) for(int i=1;i<=(n);i++)
typedef long long ll;

int main(){
    int N;
    cin >> N;
    ll L[87];
    L[0] = 2;
    L[1] = 1;
    FOR(i,2,N+1) L[i] = L[i-1]+L[i-2];
    cout << L[N] << endl;
    return 0;
}


Measured memory_bytes: 256
S = input()

m = [0] * len(S)

for i, s in enumerate(S):
    if s in "AGCT":
        if i == 0:
            m[i] = 1
        else:
            m[i] = m[i-1] + 1
    else:
        m[i] = 0

print(max(m))

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

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

    if ((n + 1) / 2 >= k) {
        std::cout << "YES" << std::endl;
    } else {
        std::cout << "NO" << std::endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;i++)
#define why(n,x) int n;while(cin >>n,n!=x)
#define iFOR(i,x,n)for(int i=x;i<n;i++)
#define unless(flg) if ( !(flg) )
#define read cin<<
#define echo cout<<
#define fin <<'\n'
#define __ <<" "<<
#define bash push_back
#define alles(x) x.begin(),x.end()
#define SWAP(a,b) ((a != b) && (a += b,b = a - b,a -= b))
int dx[]={1,0,-1,0,1,1,-1,-1};
int dy[]={0,-1,0,1,-1,1,-1,1};
const int INF=1 << 30;
bool inside(int x,int y,int w,int h){
  return (x>=0 && y>=0 && x<w && y<h);}
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vit;
typedef map<string,int> mstit;
typedef priority_queue<int> pqit;


int main(){
  cin.tie(0), ios::sync_with_stdio(false);
  int n;
  deque<int> deq;
  cin >>n;
  FOR(i,n){
    int a;
    cin >>a;
    if(!(i%2)){
      deq.push_back(a);
    }else{
      deq.push_front(a);
    }
  }
  FOR(i,n){
    if(!(n%2)){
      cout <<deq.front();
      deq.pop_front();
    }else{
      cout <<deq.back();
      deq.pop_back();
    }
    if(i!=n-1) cout <<" ";
  }
  cout <<"\n";
  
  return 0;
}



Measured memory_bytes: 3072
#include<bits/stdc++.h>
#define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int n,m;
set<string> s;
int main()
{
    IO
    int n,l;
    cin>>n>>l;
    vector<string> v(n);
    for(int i=0;i<n;i++)
        cin >> v[i];
    sort(v.begin(), v.end());
    for(auto x : v)
        cout<<x;
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256