akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define RREP(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
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; }
//const ll INF = 1LL << 60;
//const int INF = 1001001001;

int main(void){
    int n;
    cin >> n;
    int ans=0;
    for(int i=1;i<=n;i++){
        if((int)floor(log10(i)+1)%2==1)ans++;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 3952
#include<iostream>
#include<cstdio>
#include<algorithm>

typedef long long ll;
using namespace std;


ll mod = 1000000007;
ll H, W;
ll fac[200000];
ll A, B;


long long pow_(long long a, long long x){
    if(x == 0){
        return 1;
    }
    if(x == 1){
        return a % mod;
    }
    if(x % 2 == 0){
        return pow_(a*a%mod, x/2);
    }else{
        return pow_(a*a%mod, x/2) * a % mod;
    }
}

long long inv(long long n){
    return pow_(n, mod - 2);
}



long long C(long long n, long long r){
    return fac[n] * inv(fac[r]) % mod * inv(fac[n-r]) % mod;
}



int main(){
    cin >> H >> W >> A >> B;
    fac[0] = 1;
    for(int i = 1; i < H+W; i++){
        fac[i] = fac[i-1] * i % mod;
    }

    ll ans = 0;
    for(int w1 = B; w1 < W; w1++){
        ans += C((H-A-1)+ w1, w1) * C((A-1) + (W-w1-1), A-1);
        ans %= mod;
    }
    cout << ans << endl;
    
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(i,a,n) for(int i=a;i<n;i++)
#define ps(x) cout<<x<<" "
#define pn(x) cout<<x<<"\n"
#define sz(a) int((a).size())
#define pb push_back
typedef vector< int > vi;
typedef pair< int,int > pairs;

int main()
{
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    while(1)
    {
        c=c-b;
        if(c<=0){pn("Yes");return 0;}
        a=a-d;
        if(a<=0){pn("No");return 0;}
    }
    
}

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

int main(){
  int N;
  cin >> N;
  vector<double> vec(N);
  for(int i=0;i<N;i++){
    cin >> vec[i];
  }
  sort(vec.begin(),vec.end());
  double ans=0;
  for(int j=0;j<N-1;j++){
    vec[j+1]=(vec[j]+vec[j+1])/2;
    vec[j]=0;
    sort(vec.begin(),vec.end());
  }
  cout << setprecision(20) << vec[N-1] << endl;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var list [5]int
	fmt.Scan(&list[0], &list[1], &list[2], &list[3], &list[4]) // スペース区切りなのでそのままScanで取れる

	// 0を代入したポジションを返す
	pos := func(arr [5]int, e int) int {
		for i, v := range arr {
			if v == e { return i + 1 }
		}
		return -1
	}(list, 0)

	fmt.Println(pos)
}


Measured memory_bytes: 1768
N = int(input())
S = ["0"] * N
for i in range(N) :
    S[i] = input()
M = int(input())
T = ["0"] * M
for i in range(M) :
    T[i] = input()
count = -100
for i in range(N) :
    a = 0
    for j in range(N) :
        if S[j] == S[i] :
            a += 1
    for k in T :
        if S[i] == k :
            a -= 1
    count = max(a,count)
if count<= 0 :
    count = 0
print(count)

Measured memory_bytes: 3064
#include <stdio.h>
int main() {
  int a, b, c, d, T, A;
  scanf("%d %d %d %d", &a, &b, &c, &d);
  T = (a + d - 1) / d;
  A = (c + b - 1) / b;
  if (T >= A) {
    printf("Yes");
  } else {
    printf("No");
  }

  return 0;
}


Measured memory_bytes: 1692
def min(a, b)
   (a < b) ? a : b
end

n = gets.chomp.to_i

tmp = gets.chomp
b_nums = tmp.split(" ")
b_nums.map! do |b|
  b.to_i
end

result = b_nums[0] + b_nums[-1]

idx = 1
while idx < n-1 do
  result += min(b_nums[idx-1], b_nums[idx])
  idx += 1
end

puts result



Measured memory_bytes: 3836
def extgcd(a,b):
  r=[1,0,a]
  w=[0,1,b]
  while w[2]!=1:
    q=r[2]//w[2]
    r2=w
    w2=[r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
    r=r2
    w=w2
  return [w[0],w[1]]
def mod_inv(a,m):
  x=extgcd(a,m)[0]
  return (m+x%m)%m

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
l=[0,1]
for i in range(2,n+1):
  l.append((l[-1]+mod_inv(i,mod))%mod)
ans=0
for i in range(n):
  ans+=a[i]*((l[n-i]-l[0]+mod)%mod)
  ans+=a[i]*((l[i+1]-l[1]+mod)%mod)
  ans%=mod
for i in range(1,n+1):
  ans*=i
  ans%=mod
print(ans)

Measured memory_bytes: 63384
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v)   (v).begin(),(v).end()
#define debug(x) cerr<<#x<<": "<<(x)<<endl
#define INF      (int)1e9
#define EPS      (double)1e-9
#define MOD      ((int)1e9+7)
using namespace std;
typedef long long     llong;
typedef vector<int>   vi;
typedef vector<vi >   vvi;
typedef vector<vvi >  vvvi;
typedef pair<int,int> pii;
template<class Type> void line(const Type &a){int cnt=0;for(const auto &elem:a){if(cnt++)cout<<' ';cout<<elem;}cout<<endl;}

int main(){
	int n;
	string s;
	cin>>n>>s;
	
	map<char,llong> mp;
	REP(i,n) mp[s[i]]++;
	
	llong ans=mp['R']*mp['G']*mp['B'];
	REP(i,n){
		int l=1;
		while(0<=i-l and i+l<n){
			if(s[i-l]!=s[i] and s[i]!=s[i+l] and s[i+l]!=s[i-l]) ans--;
			l++;
		}
	}
	
	cout<<ans<<endl;
}

Measured memory_bytes: 3636
#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;
#define ll long long



int main() {
  int n, k;
  cin >> n >> k;
  int min = 1;

  for(int i=0; i<n; ++i) {
    if(min*2 > min+k) {
      min += k;
    }else {
      min *= 2;
    }
  }

  cout << min << endl;

  return 0;
}


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

int main(){
    ll N, A, B;
    cin >> N >> A >> B;
    if ((B - A)%2 == 0) cout << (B-A)/2 << endl;
    else {
        ll T = (A-1) + 1 + (B-A-1)/2;
        ll U = (N-B) + 1 + (N-(A+(N-B)+1)+1)/2;
        cout << min(T, U) << endl;
    }
    return 0;
}


Measured memory_bytes: 764
/**
 *      purpose : ABC 115 B
 *      author  : kyomukyomupurin
 *      created : 2018-12-08 21:12:21
**/

#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
using pii = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define print(x) cout << (x) << '\n'
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define fi first
#define se second

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(__null);
    
    int n; cin >> n;
    int p[n];
    rep(i, n) cin >> p[i];
    sort(p, p + n);
    print(accumulate(p, p + n - 1, int()) + p[n - 1] / 2);
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
const long long mod = 1e9 + 7ll ;
const int MAX = 5000 ;

long long modpower(long long a , long long b)
{
    if(b == 0)
        return 1ll ;
    long long x = modpower(a , b / 2ll) ;
    x = (x * x) % mod ;
    if(b & 1)
        return (x * a) % mod ;
    return (x % mod) ;
}
 
struct combination
{
    vector<long long>fact , inv ;
    combination(int sz) : fact(sz + 1) , inv(sz + 1)
    {
        fact[0] = 1ll ;
        inv[0] = 1ll ;
        for(long long i = 1 ; i <= sz ; ++i)
            fact[i] = (fact[i-1] * i) % mod ;
        inv[sz] = modpower(fact[sz] , mod - 2ll) ;
		for(long long i = sz-1; i >= 1; --i)
		    inv[i] = (inv[i+1] * (i+1)) % mod;
    }
    long long choose(int n , int k) const
    {
        if(k < 0 || n < k)
            return 0 ;
        return ((((fact[n] * inv[k]) % mod) * inv[n - k]) % mod) ;
    }
};

int n , k ;
combination comb(MAX) ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>k ;
    int g = n-k ;
    for(int i = 0 ; i <= k-1; ++i)
    {
        if(g < i)
        {
            cout<<0<<"\n" ;
            continue ;
        }
        long long x = comb.choose(k-1 , i) % mod ;
        long long y = comb.choose(i+2+g-i-1 , g-i) % mod ;
        x = (x * y) % mod ;
        cout<<x<<"\n" ;
    }
    return 0 ;
}		


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=100000000000000000;


int main() {
    set<int> s;
    rep(i,9){
        rep(j,9){
            s.insert((i+1)*(j+1));
        }
    }
    int n;
    cin >> n;
    if (s.find(n)!=s.end()) cout << "Yes" << endl;
    else cout << "No" << endl;
}


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

#define pq priority_queue
#define mp make_pair
#define cauto const auto &

#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

#define clr(ar, val) memset(ar, val, sizeof(ar))

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;
}

template <class T = int> T in() {
    T x;
    cin >> x;
    return (x);
}

template <class T> void print(T &x) {
    cout << x << '\n';
    return;
}

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

typedef long long int64;
typedef long long lint;
typedef long long lli;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;

typedef pair<int, int> pint;
typedef pair<long, long> plong;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<ll, ll> pll;

const int iinf = 1 << 29;
const long long linf = 1ll << 61;

int main() {
    ll n, m;
    cin >> n >> m;
    if (n == 1 && m == 1) {
        cout << 1 << endl;
        return 0;
    }
    if (n == 1) {
        cout << m - 2 << endl;
        return 0;
    }
    if (m == 1) {
        cout << n - 2 << endl;
        return 0;
    }
    cout << (n - 2) * (m - 2) << endl;
    return 0;
}


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

long long dp[105][100005];

int main() {
	int n, w,wi,vi;
	cin>>n>>w;;
	for (int i=1 ; i<=n; i++){
		cin>>wi>>vi;
		for (int p=0; p<=w; p++){
			if (wi<=p) dp[i][p] = max(dp[i-1][p], vi+dp[i-1][p-wi]);
			else dp[i][p]=dp[i-1][p];
			
		}
	}
	cout<<dp[n][w];
	
	return 0;
}

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

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_map>
#include <map>

#define INF 10e9
#define rep(i, a) for (int i = 0; i < (a); i++)
using namespace std;

int main(){
    long long int n, m, R;
    cin >> n >> m >> R;
    vector<long long int> r(R);

    long long int i, j, k;
    long long int rr;
    for(i = 0; i < R; i++){
        cin >> rr;
        r[i] = rr-1;
    }
    sort(r.begin(), r.end());

    long long int dist[n][n];
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            if(i == j){
                dist[i][j] = 0;
            }else{
                dist[i][j] = INF;
            }
        }
    }

    long long int a, b, c;
    for(i = 0; i < m; i++){
        cin >> a >> b >> c;
        dist[a-1][b-1] = c;
        dist[b-1][a-1] = c;
    }

    for(k = 0; k < n; k++){
        for(i = 0; i < n; i++){
            for(j = 0; j < n; j++){
                if(dist[i][k] != INF && dist[k][j] != INF){
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    long long int ans = INF;
    long long int count;
    do{
        count = 0;
        for(i = 0; i < R-1; i++){
            count += dist[r[i]][r[i+1]];
        }
        ans = min(ans, count);
    }while(next_permutation(r.begin(), r.end()));

    cout << ans << endl;
}






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

using namespace std;

int main() {
  string s, t;
  cin >> s >> t;
  vector<vector<int>> c(s.size() + 1, vector<int>(t.size() + 1, 0));
  for (int i = 1; i <= s.size(); i++) {
    for (int j = 1; j <= t.size(); j++) {
      if (s[i - 1] == t[j - 1]) {
        c[i][j] = c[i - 1][j - 1] + 1;
      } else if (c[i - 1][j] >= c[i][j - 1]) {
        c[i][j] = c[i - 1][j];
      }  else {
        c[i][j] = c[i][j - 1];
      }
    }
  }
  string r;
  for (int i = s.size(), j = t.size(); i > 0 && j > 0;) {
    if (s[i - 1] == t[j - 1]) {
      r.push_back(s[i - 1]);
      i--; j--;
    } else if (c[i - 1][j] >= c[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }
  for (int i = 0, j = r.size() - 1; i <= j; i++, j--) {
    swap(r[i], r[j]);
  }
  printf("%s\n", r.c_str());
  return 0;
}

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

int main() {
	string a, b;
	cin >> a >> b;
	if (a.length()>b.length()){
		cout << "GREATER" << endl;
	}
	else if (a.length()<b.length()){
		cout << "LESS" << endl;
	}
	else {
		for (int i=0; i<a.length(); i++){
			if (a[i]>b[i]){
				cout << "GREATER" << endl;
				return 0;
			}
			else if (a[i]<b[i]){
				cout << "LESS" << endl;
				return 0;
			}
			else{ 
				cout << "EQUAL" << endl;
				return 0;
			}
		}
	}
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void) {
    int num,s=0,temp,i,j,max,min;
    while (scanf("%d",&num)!=EOF&&num!=0) {
        for (i=0; i<num; i++) {
            s=0;
            for (j=0; j<5; j++) {
                scanf("%d",&temp);
                s+=temp;
            }
            if (i==0) {
                max=s,min=s;
            } else if (s>max) {
                max=s;
            } else if (s<min) {
                min=s;
            }
        }
        printf("%d %d\n",max,min);
    }
    return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <vector>
using namespace std;
int main(){
    long long n;
    vector<long long> c(5);
    cin >> n;
    for(int i = 0; i < 5; i++)
    {
        cin >> c[i];
    }
    long long mi = c[0];
    for(int i = 1; i < 5; i++)
    {
        mi = min(mi, c[i]);
    }
    long long ans = 0;
    if (n%mi == 0) {
        ans = 5 + n/mi - 1;
    }
    else
    {
        ans = 5 + n/mi;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main()
{
        int a,b;
        char m,n;
        char c;
        scanf("%d",&a);
        scanf("%c",&m);
        scanf("%c",&c);
        scanf("%c",&n);
        scanf("%d",&b);
        if(c == '+' )
                printf("%d",a+b);
        else
                printf("%d",a-b);
        return 0;
}


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


template <typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v){
    if(!v.empty()) {
        out << '[';
        std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
        out << "\b\b]";
    }
    return out;
}

template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &p) {
    out << "[" << p.first << ", " << p.second << "]";
    return out;
}
//---------

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, a, b;
    cin >> n >> a >> b;
    string s;
    cin >> s;
    
    int kokunai = 0;
    int kaigai = 0;
    rep(i, 0, n){
        // cout << s[i];
        // cout << " sum = " << kokunai + kaigai;
        if(s[i] == 'a' && (kokunai + kaigai) < a + b){
            kokunai++;
            cout << "Yes" << endl;
        }else if((kokunai + kaigai) < (a + b) && kaigai < b && s[i] == 'b'){
            kaigai++;
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }


    
}

Measured memory_bytes: 848
n,m=map(int,input().split())
p=list(map(int,input().split()))

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

num=[i for i in range(n)]
for _ in range(m):
    x,y=map(int,input().split())
    unite(num[x-1],num[y-1])

ans=0
for i in range(n):
    if same(num[i],num[p[i]-1]):
        ans+=1
print(ans)

Measured memory_bytes: 14008
using System;
using System.Linq;
using System.Collections.Generic;
using System.Text;

namespace Program
{
    public class AGC019A
    {
        static class Console_
        {
            private static Queue<string> param = new Queue<string>();
            public static int NextInt() => int.Parse(NextString());
            public static long NextLong() => long.Parse(NextString());
            public static string NextString()
            {
                if (param.Count == 0) foreach (var item in Console.ReadLine().Split(' ')) param.Enqueue(item);
                return param.Dequeue();
            }
        }
        static public void Main(string[] args)
        {
            var Q = (ulong)Console_.NextInt();
            var H = (ulong)Console_.NextInt();
            var S = (ulong)Console_.NextInt();
            var D = (ulong)Console_.NextInt();
            var N = (ulong)Console_.NextLong() * 4;

            var sortdic = new SortedDictionary<ulong, ulong>();
            sortdic[Q * 8] = 1;
            sortdic[H * 4] = 2;
            sortdic[S * 2] = 4;
            sortdic[D] = 8;

            var sum = (ulong)0;
            foreach (var item in sortdic)
            {
                sum += (N / item.Value) * item.Key / (8 / item.Value);
                N %= item.Value;
            }

            Console.WriteLine(sum);
        }
    }
}


Measured memory_bytes: 11604
#include<stdio.h>
#include<stdlib.h>
typedef long long ll;
int main(void){
    int N;
    scanf("%d",&N);
    char S[1][10000];
    scanf("%s",S[0]);
    int length=0;
    for(int i=0;i<10000;i++){
        if(S[0][i] == '\0'){
            break;
        }
        length++;
    }//printf("%d\n",length);
    //printf("%s\n",S[0]);
    for(int i=0;i<length;i++){
        S[0][i] = 'A' + (S[0][i] - 'A' + N)%26;
    }
    printf("%s\n",S[0]);
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const ll mod = 998244353;
const int DEG = 30;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
int main(){
	ll r, d, x;
	cin >> r >> d >> x;
	for(int i = 1; i <= 10; i++){
		x = r * x - d;
		cout << x << endl;
	}
	return 0;
}

Measured memory_bytes: 256
// 競プロ.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//
#include "bits/stdc++.h"
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
using Graph = vector < vector<int>>;
using ll = long long;
const int INF = 1001001001;


int main() {
	int h1, m1, h2, m2; cin >> h1 >> m1 >> h2 >> m2;
	int k;
	cin >> k;
	int time1 = h1 * 60 + m1;
	int time2 = h2 * 60 + m2;
	cout << time2 - time1 - k << endl;
	return 0;
}


Measured memory_bytes: 3596
import math
n,m=map(int,input().split())

if abs(n-m)>=2:
    ans=0
else:
    nn=math.factorial(n)
    mm=math.factorial(m)
    ans = nn*mm
print(0 if ans==0 else ans%(10**9+7) if nn !=mm else (ans*2)%(10**9+7))

Measured memory_bytes: 5184
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <set>

inline int getInt(){ int s; scanf("%d", &s); return s; }

using namespace std;

// A => BB => AAAA => A
// A => BB => AAB => BBAB => AABAB

// AAA =>
// AA => B
// AB =>
// AAB => BB => A

// X..ABAB BABA..Y => X..ABAAABA..Y => X..ABBA...Y

const int m = 320;
//const int m = 3;
char s[100000 + 10000];
char t[100000 + 10000];
char sm[10000];
char tm[10000];
const char a = 'A';
const char b = 'B';
const char e = '.';

char merge(char p, char q){
  if(p == e) return q;
  if(q == e) return p;
  if(p == q) return p == a ? b : a;
  return e;
}

void prepare(char *src, char *dst){
  char cur = e;
  for(int i = 0; src[i] != '\0'; i++){
    const char c = src[i];
    cur = merge(cur, c);
    if((i + 1) % m == 0){
      dst[i / m] = cur;
      cur = e;
    }
  }
}

char encode(char *src, char *memo, int p, int q){
  char cur = e;
  for(; p % m != 0 && p <= q; p++) cur = merge(cur, src[p]);
  for(; p + m <= q; p += m) cur = merge(cur, memo[p / m]);
  for(; p <= q; p++) cur = merge(cur, src[p]);
  return cur;
}

int main(){
  scanf("%s%s", s, t);
  prepare(s, sm);
  prepare(t, tm);

  const int q = getInt();
  REP(i,q){
    const int a = getInt() - 1;
    const int b = getInt() - 1;
    const int c = getInt() - 1;
    const int d = getInt() - 1;

    puts(encode(s, sm, a, b) == encode(t, tm, c, d) ? "YES" : "NO");
  }

  return 0;
}


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

int main()
{
    long long N, K;
    vector<long long> H;
    //priority_queue<int> H;
    long long res = 0;
    long long t;

    cin >> N >> K;
    rep(i, N)
    {
        cin >> t;
        H.push_back(t);
    }

    sort(H.begin(), H.end());
    //res = accumulate(A.begin(), A.end(), 0);
    if (K >= N)
    {
        res = 0;
    }
    else
    {
        res = accumulate(H.begin(), H.end() - K, 0LL);
    }

    //res += accumulate(H.begin(), H.end(), 0);
    cout << res;

    return 0;
}

Measured memory_bytes: 2420
import java.util.Scanner;

    public class Main{
        public void solve(){
        Scanner sc = new Scanner(System.in);
        int a,b,seki,syu;
		a=sc.nextInt();
		b=sc.nextInt();
		seki = a*b;
		syu = (a*2)+(b*2);
		System.out.println(seki+" "+syu);
        }
    public static void main(String[]args){
    Main obj = new Main();
    obj.solve();
    }
    }

Measured memory_bytes: 17156
h, w, k = map(int, input().split())
MOD = 10**9 + 7

dp = [[0]*w for i in range(h+1)]
dp[0][0] = 1

# print(dp[0])
for i in range(1, h+1):
    if w == 1:
        dp[i][0] = dp[i-1][0]
        continue

    for bits in range(1<<(w-1)):
        if bits & (bits>>1) != 0:
            continue
        # print(bits, ''.join([str((bits>>j)&1) for j in range(w-1)]))

        for j in range(w-1):
            if (bits>>j) & 1 == 1:
                dp[i][j+1] += dp[i-1][j]
                dp[i][j+1] %= MOD
                dp[i][j] += dp[i-1][j+1]
                dp[i][j] %= MOD
            else:
                if j == 0 or (bits>>(j-1)) & 1 == 0:
                    dp[i][j] += dp[i-1][j]
                    dp[i][j] %= MOD

                if j == w-2:
                    dp[i][w-1] += dp[i-1][w-1]
                    dp[i][w-1] %= MOD
    # print(i, dp[i])

print(dp[h][k-1])


Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <map>
#include <utility>
#include <vector>
#include <cstdio>
#include <iomanip>
#include <cmath>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i <= n; i++) 

int main() {
    string S;
    cin >> S;
    
    int N = (int)(S.length());
    int count = 0;
    for (int i = 0; i < N; i++) {
        if (i%2==0) {
            if (S[i]=='1')
            ++count;
        } else {
            if (S[i]=='0')
            ++count;
        }
    }
    cout << min(N-count, count) << endl;
    
    return 0;

}

Measured memory_bytes: 512
n, t = [int(e) for e in input().split()]

arr = []
for _ in range(n):
    arr.append([int(e) for e in input().split()])

arr = sorted(arr, key=lambda x: x[0])

for k,i in enumerate(arr):
    if i[1] <= t:
        print(i[0])
        break
    if k == len(arr)-1:
        print('TLE')


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

#define ll 				long long
#define vi 				vector<ll>
#define vvi				vector<vector<ll>>
#define mii 			map<ll,ll>
#define rev(a); 		reverse(a.begin(), a.end());
#define sortv(a); 		sort(a.begin(), a.end());
#define sortd(a); 		sort(a.begin(), a.end(), greater<int>());
#define FOR(i,a,b) 		for (int i = (a); i < (b); i++)
#define ROF(i,a,b) 		for (int i = (b)-1; i >= (a); i--)
#define pb 				push_back
#define mp 				make_pair
#define printv(a);		FOR(_Q,0,(int)(a).size()) cout<<(a)[_Q]<<" "; cout<<'\n';

ll MOD = 1000000007;
ll INF = LLONG_MAX;

/*****************************************************************************/


void solve() {
	
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	double r;cin>>r;
	cout<<fixed<<setprecision(15)<<2*r*3.14159265358979323846;
}

Measured memory_bytes: 3800
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t=sc.nextInt();
		System.out.print(kaesu(t));

	}

	static int kaesu(int a) {
		return((a+1)/2)*(a/2);
	}

}


Measured memory_bytes: 21332
def divisor(N):
    div = []
    for i in range(1, int(N ** 0.5 + 1)):
        if N % i == 0:
            div.append(i)
            if i * i != N:
                div.append(N // i)
    return sorted(div)


N = int(input())
print(min([d + N // d - 2 for d in divisor(N)]))


Measured memory_bytes: 3552
import sys
input=sys.stdin.readline
from itertools import accumulate
n=int(input())
A=[0]+list(accumulate(map(int,input().split())))
DP=[[0]*n for _ in range(n)]
for d in range(1,n):
    for i in range(n-d):
        j=i+d
        tmp=float('inf')
        for k in range(i,j):
            tmp=min(tmp,DP[i][k]+DP[k+1][j])
        DP[i][j]=tmp+A[j+1]-A[i]
print(DP[0][n-1])

Measured memory_bytes: 45420
#include <bits/stdc++.h>
using namespace std;
int main(){
int N, i, j; cin >> N; int ans[N+1]={};
for(i=1;i<=N;i++){
ans[i]=100000;
for(j=1;j<=i;j*=6){ ans[i]=min(ans[i],ans[i-j]+1); }
for(j=9;j<=i;j*=9){ ans[i]=min(ans[i],ans[i-j]+1); }
}
cout << ans[N] << "\n";
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

    private static final int MAX_N = 44;
    private static int[] d = new int[MAX_N+1];

    private static int q;
    private static String stringA;
    private static String stringB;

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        int q = scanner.nextInt();

        for (int i = 0; i < q; i++) {
            stringA = scanner.next();
            stringB = scanner.next();

            System.out.println(lcs(stringA, stringB));
        }

    }

    private static int lcs(String X, String Y) {

        int m = X.length();
        int n = Y.length();

        X = " " + X;
        Y = " " + Y;

        int[][] d = new int[m+1][n+1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <=n; j++) {
                if(X.charAt(i) == Y.charAt(j)){
                    d[i][j] = d[i-1][j-1] + 1;
                }
                else {
                    d[i][j] = Math.max(d[i-1][j], d[i][j-1]);
                }
            }
        }

        return d[m][n];
    }


}

Measured memory_bytes: 65316
using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
		string[] input = Console.ReadLine().Split();
		int a = int.Parse(input[0]);
		int b = int.Parse(input[1]);

		int[] nums = new int [] { a + b, a - b, a * b };

		Console.WriteLine(nums.Max());
	}
}


Measured memory_bytes: 13268
#include <stdio.h>
#define max(x, y) ((x)<(y) ? (y) : (x))
#define min(x, y) ((x)>(y) ? (y) : (x))
#define sqr(x) ((x)*(x))

int main(){
  int n;  scanf("%d", &n);
  int a[105] = {0};
  int mini = 200, maxi = -200;
  for(int i=1; i<=n; i++){
    scanf("%d", a+i);
    mini = min(mini, a[i]);
    maxi = max(maxi, a[i]);
  }

  long ans = 100000000;
  for(int i=mini; i<=maxi; i++){
    long sum = 0;
    for(int j=1; j<=n; j++)
      sum = sum + (long)(sqr(a[j]-i));
    ans = min(ans, sum);
    if(!ans)  break;
  }

  printf("%ld\n", ans);

  return 0;
}


Measured memory_bytes: 1692
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll, ll>;

int root[200002];
int vsz[200002], esz[200002];
int n, h, w;
int get_root(int x)
{
    return root[x] = (root[x] == x ? x : get_root(root[x]));
}
int merge(int x, int y)
{
    x = get_root(x);
    y = get_root(y);
    if(x != y && vsz[x] + vsz[y] >= esz[x] + esz[y] + 1)
    {
        root[y] = x;
        vsz[x] += vsz[y];
        esz[x] += esz[y] + 1;
        return 1;
    }
    if(x == y && vsz[x] > esz[x])
    {
        esz[x]++;
        return 1;
    }
    return 0;
}
struct edge{
    int x, a, b;
};

vector<edge> v;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> h >> w;
    for(int i=1;i<=h+w;i++)
        root[i] = i, vsz[i] = 1;
    for(int i=0;i<n;i++)
    {
        int x,a,b;
        cin >> a >> b >> x;
        v.push_back({x, a, h+b});
    }
    sort(v.begin(), v.end(), [] (edge& A, edge& B){
        return A.x > B.x;
    });

    ll ans = 0;
    for(edge& e : v)
    {
        if(merge(e.a, e.b))
        {
            ans += e.x;
        }
    }
    cout << ans;
}

Measured memory_bytes: 4340
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;

int main(){
	int x,a,b;
	cin >> x >> a >>b;
	if (abs(x - a) < abs(x- b)){
		cout << 'A' <<endl;
	}
	else{
		cout << 'B' << endl;
	}
	return 0;
}

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

fn main() {
    let mut input = String::new();
    stdin().read_line(&mut input).expect("hoge");
    let input = input.trim();

    match input {
        "Sunny"  => println!("Cloudy"),
        "Cloudy" => println!("Rainy"),
        "Rainy"  => println!("Sunny"),
        _ => (),
    }
}


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

typedef long long ll;
const int MAX_N = 100000;

int main() {
  int N;
  ll s[MAX_N];
  std::cin >> N;
  for(int i = 0; i < N; ++i) {
    std::cin >> s[i];
  }

  ll ans = 0;
  for(int C = 1; C < N - 1; ++C) {
    ll dp = 0;
    for(int k = 1; (ll) k * C < N - 1; ++k) {
      int A = N - 1 - k * C;
      int B = A - C;
      if(B <= 0) continue;
      if(A % C == 0 and k * C >= A) continue;
      dp += s[N - 1 - k * C] + s[k * C];
      ans = std::max(ans, dp);
    }
  }
  std::cout << ans << std::endl;
}

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

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

int main(){
	int a;cin>>a;
	cout<<a+a*a+a*a*a<<endl;
}

Measured memory_bytes: 3624
#include<iostream>
#include<tuple>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
tuple<int, int, int>x[5050];
vector<int>R[101];
int n, m;
int main() {
	while (true) {
		cin >> n >> m; if (n == 0)break;
		for (int i = 0; i < m; i++) {
			cin >> get<1>(x[i]) >> get<2>(x[i]) >> get<0>(x[i]);
		}
		sort(x, x + m); int maxn = 1000000000;
		for (int i = 0; i < m; i++) {
			int E = get<1>(x[i]); bool used[101];
			for (int j = 0; j < 101; j++) {
				used[j] = false; R[j].clear();
			}
			used[E] = true; queue<int>Q;
			int sum = 1;
			for (int j = i; j < m; j++) {
				int F = get<1>(x[j]), G = get<2>(x[j]); R[F].push_back(G); R[G].push_back(F);
				if (used[F] == 1 && used[G] == 0) {
					Q.push(F);
					while (!Q.empty()) {
						int to = Q.front(); Q.pop();
						for (int k = 0; k < R[to].size(); k++) {
							if (used[R[to][k]] == 0) {
								used[R[to][k]] = 1; sum++; Q.push(R[to][k]);
							}
						}
					}
				}
				if (used[G] == 1 && used[F] == 0) {
					Q.push(G);
					while (!Q.empty()) {
						int to = Q.front(); Q.pop();
						for (int k = 0; k < R[to].size(); k++) {
							if (used[R[to][k]] == 0) {
								used[R[to][k]] = 1; sum++; Q.push(R[to][k]);
							}
						}
					}
				}
				if (sum == n) { maxn = min(maxn, get<0>(x[j]) - get<0>(x[i])); break; }
			}
		}
		if (maxn == 1000000000)maxn = -1;
		cout << maxn << endl;
	}
	return 0;
}

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

class UnionFindTree {
private:
    vector<int> parent;
    vector<int> count;

public:
    UnionFindTree(int n) : parent(n), count(n, 1) {
        // 最初は全てを根として初期化
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int get_root(const int x) {
        // データxが属する木の根を取得する
        if (parent[x] == x) return x;
        // 取得したものは直接木の根をつなぐ(経路圧縮)
        return parent[x] = get_root(parent[x]);
    }
    void unite(const int x, const int y) {
        // xとyの木を併合する
        int rx = get_root(x);
        int ry = get_root(y);
        // 元から同じ木に属している場合は何もしない
        if (rx == ry) return;
        // xの属する木をyの属する木につける
        parent[rx] = ry;
        count[ry] += count[rx];
        count[rx] = 0;
    }
    bool is_same_root(const int x, const int y) {
        return get_root(x) == get_root(y);
    }
    int get_size(const int x) { return count[get_root(x)]; }
    void print() {
        for (auto elm : parent) cout << elm << " ";
        cout << endl;
        for (auto elm : count) cout << elm << " ";
        cout << endl;
    }
};

int main() {
    int n, m, ans = 0;
    cin >> n >> m;
    UnionFindTree tree(n);
    for (auto i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        if (not tree.is_same_root(--a, --b))
            tree.unite(a, b);
    }
    for (auto i = 1; i < n; i++) {
        if (not tree.is_same_root(0, i)) {
            tree.unite(0, i);
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4088
n=int(input())
L=list(map(int,input().split()))

count = 0
for i in range(n-2):
    if L[i]<L[i+1] and L[i+1]<L[i+2]:
        count += 1
    if L[i]>L[i+1] and L[i+1]>L[i+2]:
        count += 1
print(count)

Measured memory_bytes: 3060
import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush

def main():
    n = int(input())
    S = input()

    l_dict = {}
    r_dict = {}
    L = S[:n]
    R = S[n:]
    for i in range(2**n):
        lr, lb, rr, rb = '', '', '', ''
        for j in range(n):
            if (i>>j) & 1:
                lr += L[j]
                rr += R[j]
            else:
                lb += L[j]
                rb += R[j]
        rr = rr[::-1]
        rb = rb[::-1]

        if l_dict.get((lr,lb)):
            l_dict[(lr,lb)] += 1
        else:
            l_dict[(lr,lb)] = 1
        if r_dict.get((rb,rr)):
            r_dict[(rb,rr)] += 1
        else:
            r_dict[(rb,rr)] = 1
    ans = 0
    for k, v in l_dict.items():
        if k in r_dict:
            ans += v*r_dict[k]
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 197216
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i=0;i<n;++i){
    cin >> a.at(i);
  }
  reverse(a.begin(),a.end());
  for(int i=0;i<n-1;++i){
    cout << a.at(i) << " ";
  }
  cout << a.at(n-1) << endl;
}


Measured memory_bytes: 3116
N=int(input())
a=[int(i) for i in input().split()]
ans=0
while True:
  f=0
  for i in range(N):
    if a[i]>=N:
      d=a[i]//N
      ans+=d
      a[i]%=N
      for j in range(N):
        if i!=j:
          a[j]+=d
    else:
      f+=1
  if f==N:
    break
print(ans)
      
  
        

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

int main() {
	int n,m;
	cin>>n>>m;
	int a = n*(n-1);
	int b = m*(m-1);
	int a1 = a/2;
	int b1 = b/2;
	int ans = a1+b1;
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
 
int main()
{
    int N, M, p;
    cin >> N >> M >> p;
 
    int d[10001];
    d[0] = p;
 
    for(int i=1; i<=M; i++){
        cin >> d[i];
    }
 
    sort(d, d+M+1);
 
    int c_min = N-1;
 
    for(int i=0; i<M+1; i++){
        int c1 = ((d[i]+N-p)%N)*2+(p+N-d[(i+1)%(M+1)])%N;
        c_min = min(c_min, c1);
 
        int c2 = ((p+N-d[i])%N)*2+(d[(i-1+M+1)%(M+1)]+N-p)%N;
        c_min = min(c_min, c2);
    }
 
    cout << c_min*100 << endl;
 
    return 0;
}

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

const int inf = 1e9;
const ll linf = 1e18;

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

    string s, t; cin >> s >> t;

    int ns = s.length(), nt = t.length();

    int dp[ns + 1][nt + 1] = {};

    for (int i = 0; i < ns; i++) {
        for (int j = 0; j < nt; j++) {
            if (s[i] == t[j]) dp[i + 1][j + 1] = max({dp[i][j] + 1, dp[i + 1][j], dp[i][j + 1]});
            else dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
        }
    }

    int n = dp[ns][nt];
    string ans(n, '.');
    int i = ns, j = nt, k = n;
    while (k) {
        if (s[i - 1] == t[j - 1]) {
            ans[k - 1] = s[i - 1];
            i--, j--, k--;
        } else {
            if (dp[i - 1][j] > dp[i][j - 1]) i--;
            else j--;
        }
    }
    cout << ans << endl;
    return 0;
}

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

typedef long long ll;

int cou;
int m;
ll g[1000000];

int setg(int n){
    int ret=0;
    bool flg=true;
    for(int i=2;i<1000000;i++){
        g[i]=3*g[i-1]+1;
        if(g[i]>=n&&flg){
            ret=i-1;
            flg=false;
            break;
        }
    }
    return ret;
}

void insertsort(vector<int> &v,int n, int h){
    for(int i=0;i<h;i++){

        for(int j=i+h;j<n;j+=h){
            for(int k=j;k>=h;k-=h){
                if(v[k]<v[k-h])swap(v[k],v[k-h]);
                else break;
                cou++;
            }
        }

    }
}

void shell(vector<int> &v,int n){
    cou=0;
    for(int i=m;i>=1;i--){
        insertsort(v,n,g[i]);
    }
}

int main(){
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> vc(n);
    for(int i=0;i<n;i++)cin >> vc[i];

    g[1]=1;
    m=setg(n);
    shell(vc,n);

    cout << m << endl;
    for(int i=m;i>=1;i--)cout << g[i] << (i!=1?" ":"\n");
    cout << cou << endl;
    for(int i=0;i<n;i++){
        cout << vc[i] << endl;
    }

}



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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define llbidx(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y) // 二要素間の距離
// #define M_PI 3.14159265358979323846 // CFでは定義しておく必要あり
#define deg2rad(deg) ((((double)deg)/((double)360)*2*M_PI))
#define rad2deg(rad) ((((double)rad)/(double)2/M_PI)*(double)360)
#define Find(set, element) set.find(element) != set.end()
#define Decimal(x) printf("%.10f\n", x) // 小数点を10桁まで表示
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << "\n";
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define endl "\n"
// gcj print用
#define Case(x) printf("Case #%d: ", x);

typedef pair<int, int> PI;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<int>>> vvvl;
typedef vector<PI> vpi;
typedef vector<vector<PI>> vvpi;
typedef vector<vector<vector<PI>>> vvvpi;
typedef vector<PLL> vpl;
typedef vector<vector<PLL>> vvpl;
typedef vector<vector<vector<PLL>>> vvvpl;

int POWINT(int x, int n) {
  int ret = 1;
  while (n > 0) {
    if (n & 1) ret *= x;
    x *= x;
    n >>= 1;
  }
  return ret;
};

ll POWLL(ll x, int n) {
  ll ret = 1;
  while (n > 0) {
    if (n & 1) ret *= x;
    x *= x;
    n >>= 1;
  }
  return ret;
};

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

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

void print() {
  cout << endl;
};

template <class T>
void print(vector<T> &vec) {
  for (auto& a : vec) {
    cout << a;
    if (&a != &vec.back()) cout << " ";
  }
  cout << endl;
};

template <class T>
void print(vector<T> &vec, ll k){
   ll n = vec.size();
   k = min(k, n);
   rep(i, 0, k-1) cout << vec[i] << " ";
   cout << vec[k-1] << endl;
};

template <class T>
void print(vector<vector<T>> &df) {
  for (auto& vec : df) {
    print(vec);
  }
};

template<class T, class U>
void print(pair<T,U> &p){
  cout << p.first << " " << p.second << "\n";
};

const ll LINF = 1e18+7;

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

  string s;
  cin >> s;
  ll k; cin >> k;

  ll tmp = LINF;
  char ch;
  for (ll i = 0; i < s.size(); i++) {
    if (s[i] != '1') {
      tmp = i;
      ch = s[i];
      break;
    }
  }

  if (tmp >= k) {
    cout << 1 << endl;
  } else {
    cout << ch << endl;
  }

  return 0;
};


Measured memory_bytes: 256
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define FASTIO
#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

const ll MOD = 1e9 + 7;

ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}

ll n;
int q;
vector<ll> vv;
vector<pair<ll, ll>> go;
ull nx[100];
ll ml[100];
ll ans = 0;
ll all[100];

void run(int x, ull msk, ll d) {
	if (x == vv.size() - 1) {
		ans = (ans + d) % MOD;
		return;
	}
	msk |= nx[x];
	if ((msk >> x) & 1)
		msk ^= (1ull << x);
	if ((msk >> (x + 1)) & 1) {
		return run(x + 1, msk, (d * (ml[x] + 1)) % MOD);
	}
	if (msk == 0)
		return run(x + 1, msk, (d * all[x]) % MOD);
	int y = __builtin_ctzll(msk);
	{
		ull tmp = nx[y];
		nx[y] |= (msk ^ (1ull << y));
		run(x + 1, 0, d * ml[x] % MOD);
		nx[y] = tmp;
	}
	run(x + 1, msk, d);
}

int main() {
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	cin >> n >> q;
	vv.push_back(0);
	vv.push_back(n);
	for (int i = 0; i < q; ++i) {
		ll l, r;
		cin >> l >> r;
		--l;
		vv.push_back(l);
		vv.push_back(r);
		go.emplace_back(l, r);
	}
	sort(ALL(vv));
	vv.resize(unique(ALL(vv)) - vv.begin());
	while (true) {
		int fl = 0;
		for (int i = 0; i < go.size(); ++i)
			for (int j = 0; j < go.size(); ++j) {
				if (go[i].first == -1 || go[j].second == -1)
					continue;
				if (i != j) {
					if (go[i] == go[j]) {
						go[j] = make_pair(-1, -1);
						fl = 1;
					}
					else if (go[i].first == go[j].first && go[i].second > go[j].second) {
						go[i].first = go[j].second;
						fl = 1;
					}
					else if (go[i].second == go[j].second && go[i].first < go[j].first) {
						go[i].second = go[j].first;
						fl = 1;
					}
				}
			}
		if (!fl)
			break;
	}
	vector<pair<ll, ll>> tmp;
	for (auto p: go)
		if (p.first != -1)
			tmp.push_back(p);
	go = tmp;
	for (int i = 0; i < vv.size(); ++i)
		nx[i] = 0;
	for (auto p: go) {
		int l = lower_bound(ALL(vv), p.first) - vv.begin();
		int r = lower_bound(ALL(vv), p.second) - vv.begin();
		nx[l] |= (1ull << r);
	}
	for (int i = 0; i + 1 < vv.size(); ++i) {
		ml[i] = (pw(10, vv[i + 1] - vv[i]) + MOD - 1) * pw(9, MOD - 2) % MOD;
		all[i] = pw(10, vv[i + 1] - vv[i]);
	}
	run(0, 0, 1);
	cout << ans << "\n";
	return 0;
}




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

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

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

const int MN = 100010;

int N, M;
int a[MN];
vi vec[MN];
vi g[MN];
bool vis[MN];

void dfs(int v, int k)
{
	vis[v] = 1;
	vec[k].pb(a[v]);

	for (int to : g[v]) {
		if (!vis[to]) {
			dfs(to, k);
		}
	}
}

int main() {
	cin >> N >> M;
	rep(i, N) cin >> a[i];

	rep(i, M) {
		int a, b;
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}

	if (M == N-1) {
		puts("0");
		return 0;
	}

	int now = 0;

	rep(i, N) {
		if (!vis[i]) {
			dfs(i, now++);
		}
	}

	rep(i, now) {
		sort(ALL(vec[i]));
	}

	int zan = N-1-M;
	ll ret = 0;

	rep(i, now) ret += vec[i][0];

	multiset<int> ss;

	int t = zan * 2 - now;

	rep(i, now) {
		for (int j = 1; j < vec[i].size(); ++j) {
			if (j >= zan) {
				break;
			}
			if (ss.size() < t) {
				ss.insert(vec[i][j]);
				ret += vec[i][j];
			} else if (*ss.rbegin() > vec[i][j]) {
				auto it = ss.end(); --it;
				ret -= *it;
				ss.erase(it);
				ret += vec[i][j];
				ss.insert(vec[i][j]);
			}
		}
	}

	if (ss.size() < t) {
		puts("Impossible");
	} else cout << ret << endl;

	return 0;
}

Measured memory_bytes: 11520
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char* argv[])
{
	int N,X,i;
	cin>>N>>X;
	vector<int> L(N);
	vector<int> D(N+1);
	for (i=0;i<N;i++){
		cin>>L[i];
	}
	for (i=1;i<=N;i++){
		D[i]=D[i-1]+L[i-1];
	}
	int ans=0;
	for (i=0;i<=N;i++){
		if (D[i]<=X){
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

int main(){
  int d, g;
  cin >> d >> g;
  pair<int,int> a[11];
  for (int i = 1; i <= d; i++) {
    cin >> a[i].first >> a[i].second;
  }
  int ans = 1000;
  for (int bit = 0; bit < (1 << d); bit++) {
    int bt = bit;
    int score = 0;
    int cnt = 0;
    bool used[11] = {};
    for (int i = 1; i <= d; i++) {
      if (bt&1) {
        score += a[i].first * i * 100 + a[i].second;
        cnt += a[i].first;
        used[i] = 1;
      }
      bt >>= 1;
    }
    if (score < g) {
      for (int i = d; i >= 1; i--) {
        if (!used[i]) {
          int nn = (g - score + i * 100 - 1) / (i * 100);
          if (nn >= a[i].first) break;
          score += nn * i * 100;
          cnt += nn;
          break;
        }
      }
    }
    if (score >= g && cnt < ans) ans = cnt;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define MAX_C 1000000001

int main() {
  int n, m;
  cin >> n >> m;
  int sum = 0;
  for (int i = 0; i < m; i++) {
    int t;
    cin >> t;
    sum += t;
  }

  cout << ((sum <= n) ? n - sum : -1) << endl;
}

Measured memory_bytes: 3624