akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define f first 
#define s second 
#define pb push_back               
#define mp make_pair 

using namespace std;                    

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

const int N = (int)1e5 + 123, inf = 1e9, mod = 1e9 + 7;
const ll INF = 1e18;

int n;
int pre0[N], pre1[N], c0[N], c1[N], mx0[N], mx1[N];
ll dp[N][2], a[N], A, B, upd[N][2];
               
bool check0(int l, int r){
	return pre0[r - 1] - pre0[l - 1] == r - l;
}
bool check1(int l, int r){
	return pre1[r - 1] - pre1[l - 1] == r - l;
}
int main(){
	scanf("%d", &n);
	scanf("%lld%lld", &A, &B);
	for(int i = 1; i <= n; i++)
		scanf("%lld", &a[i]);
	for(int i = 1; i <= n; i++){
		ll x = a[i + 1] - a[i];
		if(x >= A)
			c0[i] = 1;
		if(x >= B)
			c1[i] = 1;                 
		pre0[i] = pre0[i - 1] + c0[i];
		pre1[i] = pre1[i - 1] + c1[i];
	}
	for(int i = n; i >= 1; i--){
		mx0[i] = i;
		if(c0[i])
			mx0[i] = mx0[i + 1];
		
		mx1[i] = i;
		if(c1[i])
			mx1[i] = mx1[i + 1];
	}
	for(int i = 2; i <= n; i++){
		dp[i][0] = check1(1, i - 1);
		dp[i][1] = check0(1, i - 1);
	}           
	ll cur0 = 0;
	ll cur1 = 0;
	for(int i = 2; i <= n; i++){
		cur0 += upd[i][0];
		cur1 += upd[i][1];                 
		dp[i][0] = (dp[i][0] + cur0) % mod;
		dp[i][1] = (dp[i][1] + cur1) % mod; 
		
		int L, R;
		L = lower_bound(a + 1, a + 1 + n, A + a[i - 1]) - a;
		if(L == i)
			L++;
		R = mx1[i] + 1;
	
		if(L <= R){
			upd[L][0] += dp[i][1];
			upd[R + 1][0] -= dp[i][1];
		}
		
		L = lower_bound(a + 1, a + 1 + n, B + a[i - 1]) - a;
		if(L == i)
			L++;
		R = mx0[i] + 1;
		
		if(L <= R){
			upd[L][1] += dp[i][0];
			upd[R + 1][1] -= dp[i][0];
		}
	}

	ll ans = 0;
	for(int i = 2; i <= n; i++){
		if(check0(i, n))    
			ans += dp[i][0];
		if(check1(i, n))    
			ans += dp[i][1];
	}
	if(check0(1, n))
		ans++;
	if(check1(1, n))
		ans++;
    printf("%lld", ans % mod);
    return 0;
}


Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
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; }
using ll = long long;
using P = pair<ll, ll>;
const long double PI = acos(-1.0L);
ll GCD(ll a, ll b) { return b?GCD(b, a%b):a; }
ll LCM(ll a, ll b) { return a/GCD(a, b)*b; }

int h, w, a, b;

int main() {
    cin >> h >> w >> a >> b;
    vector<vector<int>> smap(h, vector<int>(w, 1));
    for(int i = 0; i < b; ++i) {
        for(int j = 0; j < a; ++j) smap[i][j] = 0;
    }
    for(int i = b; i < h; ++i) {
        for(int j = a; j < w; ++j) smap[i][j] = 0;
    }

    for(int i = 0; i < h; ++i) {
        for(int j = 0; j < w; ++j) {
            cout << smap[i][j];
        }
        cout << endl;
    }
}

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

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    bool can=true;
    if(a[0]!=0)can=false;
    for(int i=1;i<n;i++){
        if(a[i]-a[i-1]>1)can=false;
    }
    int res=0;
    a.push_back(0);
    for(int i=0;i<n;i++){
        if(a[i]>=a[i+1])res+=a[i];
    }
    cout<<(can?res:-1)<<endl;
}

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

namespace Sample
{
	class Program
	{
		static void Main(string[] args)
		{
			while (true)
			{
				var array = Console.ReadLine().Split();
				var a = int.Parse(array[0]);
				var op = array[1];
				var c = int.Parse(array[2]);

				var result = 0;
				switch (op)
				{
					case "+":
						result = a + c;
						break;
					case "-":
						result = a - c;
						break;
					case "*":
						result = a * c;
						break;
					case "/":
						result = a / c;
						break;
					default:
						return;
				}
				Console.WriteLine(result);
			}
		}
	}
}



Measured memory_bytes: 16004
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int n;
ll tbl[100001];
ll k;
int main(){
  cin >> n>>k;
  while(n--){
    int a,b;
    cin >> a >> b;
    tbl[a]+=b;
  }
  ll cnt=0LL;
  for(int i=1;i<=100000;++i){
    cnt+=tbl[i];
    if(cnt>=k){
      cout << i << endl;
      break;
    }
  }
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main (){
  long long A,B;
  cin>>A>>B;
  long long AA, BB;
  AA=A,BB=B;
  long long k=1;
  long long j=0;
  while(k>0){
      j=A/B;
      k=A%B;
      A=B;
      B=k;
  }

  int count=1;
  long long E=A;
  int x=max(sqrt(AA),sqrt(BB));
  //cout<<x;
    for(int i=2;i<x;i++){
          if(E%i==0){
              while(E%i==0){
                  E=E/i;
              }
              count++;

          }
        if(E<i){
            break;
        }
    }
      	if(E>1){
			count++;
        
        
      }
  cout<<count<<endl;
  
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  int n,sum=0;
  n=N;
  while(n>0){
    sum+=n%10;
    n /=10;
  }
  string ans;
  if(N%sum == 0){
    ans ="Yes";
  }
  else{
    ans= "No";
  }
  cout << ans << endl;
}
  

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
using LL = long long;

int N;
int arr[2][123];

int main(void)
{
	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> arr[0][i];
	}
	for (int i = 0; i < N; ++i) {
		cin >> arr[1][i];
	}
	for (int i = 1; i < N; ++i) {
		arr[0][i] += arr[0][i - 1];
	}
	for (int i = N - 2; i >= 0; --i) {
		arr[1][i] += arr[1][i + 1];
	}
	int ans = 0;
	for (int i = 0; i < N; ++i) {
		int can = arr[0][i] + arr[1][i];
		ans = max(ans, can);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 384
s = input()
K = int(input())

N = len(s)

d = dict()
for i in range(N):
    for j in range(i, min(N,i+K)):
        sub = s[i:j+1]
        if d.get(sub) == None:
            d[sub] = 1

d2 = sorted(d.items())
print(d2[K-1][0])


Measured memory_bytes: 11408
//...Bismillahir Rahmanir Rahim...
// Code by    Asad Bin Saber
// 14 06 2020

#include <bits/stdc++.h>

using namespace std;

// typedefs...
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;

// constants...
const double PI = acos(-1);

// defines...
#define MP make_pair
#define PB push_back
#define si(a) scanf("%d", &a)
#define sii(a, b) scanf("%d%d", &a, &b)
#define siii(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define sl(a) scanf("%lld", &a)
#define sll(a, b) scanf("%lld%lld", &a, &b)
#define slll(a, b, c) scanf("%lld%lld%lld", &a, &b, &c)

int gcd(int a, int b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}
ll lcm(ll a, ll b)
{
    return (a*b/gcd(a, b));
}
ll comb(ll a, ll b)
{
    ll x = max(a-b, b), ans=1;

    for(ll K=a, L=1; K>=x+1; K--, L++){
        ans *= K;
        ans /= L;
    }

    return ans;
}


void bruce()
{
    cout << "\nExpected answer:\n";
    cout << "\nAnswer recieved:\n";
}

void task()
{
    //code here...

    vi ara(5);
    for(int K=0; K<5; K++) cin >> ara[K];
    for(int K=0; K<5; K++){
        if(ara[K]==0) {
            cout << K+1 << "\n";
            return;
        }
    }
}

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

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

    task();

    return 0;
}


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

int main() {
    string s;
    cin >> s;
    if(s[0] == s[1] and s[1] == s[2]) puts("Yes");
    else if(s[1] == s[2] and s[2] == s[3]) puts("Yes");
    else puts("No");
}

Measured memory_bytes: 256
# include<bits/stdc++.h>
 
using namespace std;
 
# define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, int> pdi;
typedef pair<ll, ll> pll;
 
# define S second
# define F first
# define kill(x) return(cout << x << endl, 0LL)
# define debug(x) cerr<< #x << " : " << x << endl
# define ddebug(x, y) cerr<< #x << " : " << x  << ", " << #y << " : " << y << endl
# define sz(s) (int)s.size()
# define sq(x) (x) * (x)
# define PB(x) push_back(x)
# define smax(x, y) (x) = max((x), (y))
# define smin(x, y) (x) = min((x), (y))
# define all(x) x.begin(), x.end()
# define SP fixed << setprecision(10)
# define MP make_pair
 
const int MAXN = 100 * 1000 + 10;
string a[MAXN];
 
int32_t main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
	int n;
	cin >> n;
 
	cout << 0 << endl;
	cin >> a[0];
	if (a[0] == "Vacant")
		return 0;
	a[n] = a[0];
 
	int l = 0, r = n;
	while (true)
	{
		int mid = (l + r) / 2;
		cout << mid << endl;
		cin >> a[mid];
		if (a[mid] == "Vacant")
			return 0;
 
		if (a[l] == a[r])
		{
			if ((a[mid] == a[l]) ^ ((mid - l) & 1 ^ 1))
				r = mid;
			else
				l = mid;
		}
		else
		{
			if (((mid - l) & 1 ^ 1) ^ (a[mid] == a[l]))
				r = mid;
			else
				l = mid;
		}
	}
 
	return 0;
}


Measured memory_bytes: 1620
#include<iostream>
#include<string> // for string class
using namespace std;

int main(){
        string s;
        int count=0,win;
        cin>>s;
        int k=s.size();
        for(int i=0;i<k;i++)
        {
          if(s[i]=='o')
          count++;
        }
          win=15-k;
          if(count+win>=8)
          cout<<"YES"<<endl;
          else
          cout<<"NO"<<endl;



	return 0;
}

Measured memory_bytes: 256
open Printf
open Scanf

module IntSet = Set.Make(struct type t = int let compare = compare end)

let solve n =
  let f s x = IntSet.add x s in
  let st = Array.fold_left f IntSet.empty @@ Array.init n @@ fun _ -> scanf "%d " @@ fun x -> x in
  if IntSet.cardinal st = n then "YES" else "NO"

let () =
  scanf "%d " solve |> printf "%s\n"


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

int main(){
	vector<int> coin{500, 100, 50, 10, 5, 1};
	while(1){
		int n;
		cin >> n;
		if(n == 0) break;
		n = 1000 - n;
		int ans = 0;
		for(int i=0; i<(int)coin.size(); i++){
			while(coin[i] <= n){
				n -= coin[i];
				ans++;
			}
		}
		cout << ans << endl;
	}
	return 0;
}



Measured memory_bytes: 3080
#include <iostream>
#include <cmath>

using namespace std;

int main(void){

  double l1,l2,taikaku;
  int cnt1 = 0;
  int cnt2 = 0;
  char ten;
  char tenten;

  while( cin >> l1 >> ten >> l2 >> tenten >> taikaku ){
    if( sqrt( pow( l1 , 2 ) + pow( l2 , 2 ) ) == taikaku ){
      cnt1++;
    }
    else if( l1 == l2 ){
      cnt2++;
    }
  }
  cout << cnt1 << endl << cnt2 << endl;
  return 0;
}

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

typedef long long LL;

const int N = 110;
const LL INF = 1e18;
const LL MAX_SUM_VAL = 100010;

LL wt[N], val[N];
LL f[MAX_SUM_VAL];

int main() {
	for(int i = 0 ; i < MAX_SUM_VAL ; i++) {
		f[i] = INF;
	}
	int n; cin >> n;
	LL w; cin >> w;
	LL sum_val = 0;
	for(int i = 0 ; i < n ; i++) {
		cin >> wt[i] >> val[i];
		sum_val += val[i];
	}
	
	f[0] = 0;

	for(int i = 0 ; i < n ; i++) {
		for(LL value = sum_val ; value >= val[i] ; value--) {
			f[value] = min(f[value], f[value - val[i]] + wt[i]);
		}
	}

	LL ans = 0;
	for(int i = 0 ; i < MAX_SUM_VAL ; i++) {
		if(f[i] <= w) {
			ans = i;
		}
	}
	cout << ans;
}


Measured memory_bytes: 1024
x, k, d = map(int, input().split())

def sgn(x):
    if x > 0:return 1
    if x < 0:return -1
    return 0

if x > 0:
    x_greedy = x - k * d
else:
    x_greedy = x + k * d

if sgn(x) == sgn(x_greedy):
    print(abs(x_greedy))
    exit()
x_r = x % d
x_l = x_r - d

r_parity = (abs(x - x_r) // d) % 2

if k%2 == r_parity:
    print(abs(x_r))
else:
    print(abs(x_l))

Measured memory_bytes: 9036
#include<bits/stdc++.h>
using namespace std;
int a,b;
int main()
{
cin>>a>>b;
if(a>0)cout<<"Positive";
else if(a==0||(a<0&&b>0))cout<<"Zero";
else if((abs(b)-abs(a))%2!=0)cout<<"Positive";
else cout<<"Negative";
cout<<endl;
return 0;
} 

Measured memory_bytes: 256
N, D = map(int, input().split())
XX = [list(map(int, input().split())) for _ in range(N)]
ans = 0

for i1 in range(N):
    for i2 in range(i1+1, N):
        total = 0
        for index in range(D):
            total += (XX[i1][index] - XX[i2][index])**2
        val = int(total ** (1/2))
        if total == val ** 2:
            ans += 1

print(ans)


Measured memory_bytes: 3188
#include<cstdio>
int main(){
	int n;
	scanf("%d",&n);
	int a[2*n-1][n]={};
	for(int i=0;i<n;i++){
		char s[n]={};
		scanf("%s",s);
		for(int j=0;j<n;j++){
			a[j][i]=s[j];
		}
		for(int j=n;j<2*n-1;j++){
			a[j][i]=s[j-n];
		}
	}
	long long int ans=0;
	for(int i=0;i<n;i++){
		int u=0;
		for(int j=0;j<n;j++){
			for(int k=0;k<n;k++){
				if(a[i+j][k]!=a[i+k][j])u++;
			}
		}
		if(u==0)ans+=n;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 896
#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;
int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
	int X;
	cin >> X;
    while(true){
        //偶数乗数か確認
        int x = sqrt(X);
        
        if( (x*x) == X){
            cout << X << "\n";
            break;
        }else{
        //奇数乗数か確認;X<1000
            bool f = false;

            for(int n=10;n>1;n--){
                int x = 1;
                int c = 0;
                while( x < X){
                    x*= n;
                    c++;

                }
                if(x == X && c>=3){
                    cout << X <<'\n';
                    f = true;
                    break;
                }

            }
            if (f == true) break;

            
        }
        

        X--;

    }
    
	return 0;
}

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

int main() {
    int n;
    cin >> n;
    long ans = 0;
    long prev = 0;
    for (int i = 0; i < n; i++) {
        long a;
        cin >> a;
        ans += (a + prev) / 2;
        if (prev) {
            if (a) {
                prev = (a + prev) % 2;
            } else {
                prev = 0;
            }
        } else {
            prev = a % 2;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
int main(){
    double a[1010];
    int n;
    double m=0;
    double ans=0;
    int i;
    while(scanf("%d",&n),n!=0){
        m=0;
        ans=0;
        for(i=0;i<n;i++){
            scanf("%lf",&a[i]);
            m+=a[i];
        }
        m/=(double)n;
        for(i=0;i<n;i++){
            ans+=pow(a[i]-m,2.0);
        }
        ans/=(double)n;
        printf("%lf\n",sqrt(ans));
    }
    return 0;
}


Measured memory_bytes: 2104
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset>
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<tuple>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<numeric>
#include<functional>
#include<iomanip>
#include<random>

#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define REP(i,n) for(int i = 0;i < n;i++)
#define FOR(i,a,b) for(int i = a;i < b;i++)
#define MEM(a,b) memset(a,b,sizeof(a))
#define ALL(x) (x).begin(),(x).end()
#define LMAX 9223372036854775807
#define LMIN -9223372036854775808

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ull, ull> UP;
typedef tuple<int, int, int> T;

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) {}
	void unionSet(int x, int y) {
		x = root(x), y = root(y);
		if (x != y) {
			if (data[y] < data[x])swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	int k = a % b;
	if (k == 1)return 1;
	if (k == 0)return b;
	int ans = gcd(b, k);
	return ans;
}
ll digisum(ll a) {
	int sum = 0;
	while (a) {
		sum += a % 10;
		a /= 10;
	}
	return sum;
}
ll countpow(ll a, ll b) {
	int ans = 0;
	if (b == 0)return -1;
	while (1) {
		if (a % b == 0) {
			a /= b;
			ans++;
		}
		else break;
	}
	return ans;
}


int main() {
	IOS;
	int x, y, z;
	cin >> x >> y >> z;
	x -= z;
	int ans = x / (y + z);
	cout << ans << endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>

#include <inttypes.h>
using namespace std;

int main()
{
	int32_t N;
	scanf("%d", &N);

#define MAX_N (100000)
	vector<int32_t> graph[MAX_N];
	for (int32_t i = 0; i < N - 1; i++) {
		int32_t a, b;
		scanf("%d%d", &a, &b);
		a--;
		b--;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	bool used[MAX_N];
	int32_t dist_a[MAX_N], dist_b[MAX_N];
	for (int32_t i = 0; i < N; i++) {
		dist_a[i] = dist_b[i] = numeric_limits<int32_t>::max();
		used[i] = false;
	}

	// 0 to N - 1 (distance)
	dist_a[0] = 0;
	priority_queue<int32_t, vector<int32_t>, greater<int32_t>> q;
	q.push(0);
	while (!q.empty()) {
		int32_t node = q.top(); q.pop();
		if (used[node])
			continue;

		used[node] = true;
		for (size_t i = 0; i < graph[node].size(); i++) {
			int32_t next = graph[node][i];
			if (dist_a[next] > dist_a[node] + 1) {
				dist_a[next] = dist_a[node] + 1;
				q.push(next);
			}
		}
	}

	// N - 1 to 0 (distance)
	for (int32_t i = 0; i < N; i++)
		used[i] = false;
	dist_b[N - 1] = 0;
	q.push(N - 1);
	while (!q.empty()) {
		int32_t node = q.top(); q.pop();
		if (used[node])
			continue;

		used[node] = true;
		for (size_t i = 0; i < graph[node].size(); i++) {
			int32_t next = graph[node][i];
			if (dist_b[next] > dist_b[node] + 1) {
				dist_b[next] = dist_b[node] + 1;
				q.push(next);
			}
		}
	}

	int32_t whiteCnt = 0;
	for (int32_t i = 0; i < N; i++)
		if (dist_a[i] > dist_b[i])
			whiteCnt++;

	printf("%s\n", N - whiteCnt > whiteCnt ? "Fennec" : "Snuke");

	return 0;
}

Measured memory_bytes: 6784
//#pragma GCC optimize("Os")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#ifdef rd
#define trace(...) cout<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cout<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma=strchr(names+1,',');
	cout.write(names,comma-names)<<" : "<<arg1<<" | ";
	__f(comma+1,args...);
}
#else
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
//#define int long long
typedef long long ll;
typedef float f80;
//#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(ll a, ll b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}

int mc[100005];
void solve() {
	int k;
	cin>>k;
	memset(mc,infi,sizeof(mc));
	deque<int> q;
	mc[1]=1;
	q.push_back(1);
	while(!(q.empty())) {
		int te=q.front();
		q.pop_front();
		int te1=(te*10)%k;
		if(mc[te1]>mc[te]) {
			mc[te1]=mc[te];
			q.push_front(te1);
		}
		te1=(te+1)%k;
		if(mc[te1]>1+mc[te]) {
			mc[te1]=mc[te]+1;
			q.push_back(te1);
		}
	}
	cout<<mc[0]<<endl;
}
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(10);
	int t=1;
//	cin>>t;
	fr(i,1,t)
		solve();
#ifdef rd
	cout<<endl<<endl<<endl<<endl<<"Time elapsed: "<<(double)(clock()-clk)/CLOCKS_PER_SEC<<endl;
#endif
	return 0;
}


Measured memory_bytes: 896
#include<cstring>
#include <cstdio> 
#include <iostream>
#include <cmath>
#include<algorithm>
using namespace std;
#define pi 3.1415926 
#define N 510
int main()
{
	string a,b;
	int len,i,num=0;
	cin>>a>>b;
	len=a.length();
	for(i=0;i<len;i++)
	{
		if(a[i]!=b[i])
		{
			++num;
		}
	}
	printf("%d",num);
	return 0;
}



Measured memory_bytes: 3920
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <set>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <sstream>
#include <cstdlib>
#include <ctime>
#include <cassert>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

#define MP make_pair
#define PB push_back
#define FF first
#define SS second

#define FORN(i, n) for (int i = 0; i <  (int)(n); i++)
#define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
#define FORD(i, n) for (int i = (int)(n) - 1; i >= 0; i--)

#define DEBUG(X) { cout << #X << " = " << (X) << endl; }
#define PR0(A,n) { cout << #A << " = "; FORN(_,n) cout << A[_] << ' '; cout << endl; }

#define MOD 1000000007
#define INF 2000000000

int GLL(LL& x) {
    return scanf("%lld", &x);
}

int GI(int& x) {
    return scanf("%d", &x);
}

string s; int k;

int main() {
    cin >> s >> k;

    FORN(i, s.size()) {
        if (s[i] == 'a' && i < s.size() - 1) {
            continue;
        }
        else {
            int need = (26 + 'a' - s[i]);

            if (need <= k) {
                k -= need;
                s[i] = 'a';
            }
        }

        if (i == s.size() - 1) {
            s[i] += (k % 26);
            if (s[i] > 'z') s[i] = (char)(s[i] - 26);
        }
    }

    cout << s << "\n";
    
    return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define rep(i,n) for(int i = 0; i < (int)(n);i++)
typedef long long ll;
using namespace std;
int main() {
	string s;
	cin >> s;
	bool flag = false;
	rep(i, s.size()) {
		if (s[i] == s[i + 1]) {
			flag = true;
		}
	}
	if (flag) {
		cout << "Bad" << endl;
	}
	else {
		cout << "Good" << endl;
	}

	return 0;
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,D,X,A;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>D>>X;
	FOR(i,N) {
		cin>>A;
		for(x=1;x<=D;x+=A) X++;
	}
	cout<<X<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 256
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
using namespace std;
#define ll int64_t
const long mod = 1e9 + 7;


const long LINF = 1e13;
const long LLINF = 1e18;
const long ALPHABET = 26;

template <class T>
void Swap(T& r, T& l) {
  T tmp = r;
  r = l;
  l = tmp;
}

template<typename T>
istream& operator >> (istream& is, vector<T>& vec) {
  for (T& x : vec) is >> x; //for(int i=0; i<vec.size(); i++) is >> x[i]; とかでもいい
  return is;
}


//最大公約数
int gcd( int m, int n ){
  // 引数に０がある場合は０を返す
  if ( ( 0 == m ) || ( 0 == n ) )
    return 0;
  // ユークリッドの方法
  while( m != n ){
    if ( m > n ) m = m - n;
    else         n = n - m;
  }
  return m;
}//gcd


//最小公倍数
int lcm( int m, int n ){  // 引数に０がある場合は０を返す
  if ( ( 0 == m ) || ( 0 == n ) )
    return 0;
  return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}//lcm




int main() {

  string s;

  cin >> s;

  long year = (s[0]-'0')*1000 + (s[1]-'0')*100 + (s[2]-'0')*10 +(s[3]-'0');

  long month = (s[5]-'0')*10 +(s[6]-'0');

  long day = (s[8]-'0')*10 +(s[9]-'0');

  bool ans = false;


  if (year >= 2019){
    if (month >=5)ans =true;
  }


  cout << ((ans)?  "TBD" : "Heisei" );



}




















Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCorder
{
    class Program
    {
        static void Main(string[] args)
        {
            var in1 = Console.ReadLine().Split(' ').Select(x => decimal.Parse(x.ToString())).ToList();
            var N = in1[0];
            var M = in1[1];

            var ABList = new List<AB>();
            for (int i = 0; i < N; i++)
            {
                var in2 = Console.ReadLine().Split(' ').Select(x => decimal.Parse(x.ToString())).ToList();
                ABList.Add(new AB(in2[0],in2[1]));
            }
            ABList = ABList.OrderBy(x => x.A).ToList();

            decimal ans = 0;
            decimal m = 0;
            for (int i = 0; i < N; i++)
            {
                if(ABList[i].B + m <= M)
                {
                    ans += ABList[i].A * ABList[i].B;
                    m += ABList[i].B;
                    continue;
                }

                ans += (M - m)* ABList[i].A;
                break;
            }
            Console.WriteLine(ans.ToString());
        }

        public class AB
        {
            public decimal A { get; set; }
            public decimal B { get; set; }

            public AB(decimal a , decimal b)
            {
                A = a;
                B = b;
            }
        }
    }
}

Measured memory_bytes: 30256
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdint.h>
#include<vector>
#include<deque>
#include<stack>
#include<string>
#include<cstring>
#include<time.h>
#include<iomanip>
#include<list>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<random>
#include<bitset>
#include <queue>
#include <map>


using namespace std;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ldouble = long double;


#define repi(i,a,b) for(ll i = (a); i < (b); i++)
#define rep(i, n) for(ll i = 0; i < (n); ++i)


//正剰余
long long mod(long long a, long long b)
{
	return a - (long long)std::floor((double)a / (double)b) * b;
}
ll MOD = 1000000007;
ll inf = 1e18;
vector<int> A;
vector<int> B;
vector<int> C;
vector<int> D;
int N, M, Q;
#define MMM(x)for (i[x] = 1; i[x] <= 10; ++i[x])
int main() {
	ll A, B, N;
	cin >> A >> B >> N;
	if (N >= B) cout << (A * (B - 1)) / B << endl;
	else cout << (A * N) / B << endl;
	return 0;
}


Measured memory_bytes: 3576
#include <bits/stdc++.h>
#define rep(i, n) for (rint i = 1; i <= (n); i ++)
#define re0(i, n) for (rint i = 0; i < (int) n; i ++)
#define travel(i, u) for (rint i = head[u]; i; i = e[i].nxt)
#define rint register int
using namespace std;

typedef long long lo;

template<typename tp> inline void read(tp &x) {
  x = 0; char c = getchar(); int f = 0;
  for (; c < '0' || c > '9'; f |= c == '-', c = getchar());
  for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
  if (f) x = -x;
}

int n, p, K, a[2222][2222];

int main(void) {
  read(K);
  if (K == 1) {
    cout << "1\n1\n";
    return 0;
  }
  n = K / 2;
  if (K & 1) ++p, ++n;
  if (n % 2 == 1) ++p, ++p, ++n;
  int color = 0;
  for (int i = 1; i <= n; i++) {
    if (p) {
      --p;
      ++color;
      for (int x = 1, y = i, t = 1; t <= n; ++t, ++x, y = y - 1 == 0 ? n : y - 1) {
        a[x][y] = color;
      }
    } else {
      int ta = ++color, tb = ++color;
      for (int x = 1, y = i, t = 1; t <= n; ++t, ++x, y = y - 1 == 0 ? n : y - 1) {
        a[x][y] = t & 1 ? ta : tb;
      }
    }
  }
  assert(1 <= n && n <= 500);
  assert(color == K);
  cout << n << "\n";
  rep (i, n) {
    rep (j, n)
      cout << a[i][j] << " ";
    cout << "\n";
  }
  
}


Measured memory_bytes: 6656
#include <bits/stdc++.h>
using namespace std;
long long dp[405][405][405];
long long MOD=998244353;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	string s;
	int K;
	cin>>s>>K;
	vector<int>v;
	int cnt=0;
	for(int i=0;i<s.size();i++){
		if(s[i]=='0'){
			v.push_back(cnt);
			cnt=0;
		}
		else cnt++;
		if(i+1==s.size()) v.push_back(cnt);
	}
	//for(int i:v) cout<<i<<endl;
	int n=v.size(), MAXN=400;
	memset(dp, 0, sizeof dp);
	for(int i=0;i<n;i++){
		for(int j=0;j<=MAXN;j++){
			for(int k=0;k<=MAXN;k++){
				if(j<k) continue;
				if(i==0){
					if(j==k) dp[i][j][k]=1;
					continue;
				}
				for(int a=0;a<=v[i];a++){
					if(j-a<0 || k+a>MAXN) break;
					dp[i][j][k]+=dp[i-1][j][k+a];
					//if(i==1 && j==1 && k==0) cout<<i-1<<" "<<j<<" "<<k+a<<endl;
				}
				for(int a=1;a<=k;a++){
					if(j-a<0 || k+a>MAXN) break;
					dp[i][j][k]+=dp[i-1][j-a][k-a];
					//if(i==1 && j==1 && k==0) cout<<i-1<<" "<<j-a<<" "<<k-a<<endl;
				}
				dp[i][j][k]%=MOD;
				//cout<<i<<" "<<j<<" "<<k<<": "<<dp[i][j][k]<<endl;
			}
		}
	}
	long long ans=0;
	for(int i=0;i<=min(K, MAXN);i++){
		ans=(ans+dp[n-1][i][0])%MOD;
	}
	cout<<ans;
}


Measured memory_bytes: 522568
<?php
    fscanf(STDIN, "%d %d %d", $W, $a, $b);
    $ans = 0;
    if($b + $W < $a)$ans = $a - $b - $W;
    if($a + $W < $b)$ans = $b - $a - $W;
    echo "$ans\n";
?>


Measured memory_bytes: 3576
#include<queue>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
using namespace std;




int main()
{
    int a,b;
    cin>>a>>b;
    if(b==1)
        cout<<0<<endl;
    else
        for(int i=1;i<=1000;i++)
            if(i*a-i+1>=b)
            return cout<<i<<endl,0;
    return 0;
}
///*
//
//4 6 0
//0 1 2
//1 2 2
//1 3 1
//0 2 5
//1 3 3
//0 3 4
//
//
//
//*/


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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

using namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)


const long long MOD = 1000000007;
//const long long MOD = 998244353;
const long long INF = 1LL << 60;


long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	unsigned r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a * g / b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}




const long double PI = 3.14159265359;
const int MAX_N = 100010;
int n, m;
bool graph[55][55];
bool visited[55];

void dfs(int v) {
	// 頂点vを訪れた！！
	visited[v] = true;
	rep(i, n) {
		if (!graph[v][i] || visited[i])continue;
		dfs(i);
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	VE a(m), b(m);
	rep(i, m) {
		cin >> a[i] >> b[i]; a[i]--; b[i]--;
		graph[a[i]][b[i]] = true;
		graph[b[i]][a[i]] = true;
	}
	int ans = 0;
	rep(i, m) {
		graph[a[i]][b[i]] = false; graph[b[i]][a[i]] = false;
		rep(j, n)visited[j] = false;
		dfs(0);
		bool ok = false;
		rep(j, n)if (!visited[j])ok = true;
		if (ok)ans++;
		graph[a[i]][b[i]] = true; graph[b[i]][a[i]] = true;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pi;
const int MAXN=1005;
const int MOD=1000000007;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define DEC(i,a,b) for(int i=(a);i>=(b);i--)
#define fst first
#define snd second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define db(x) cerr<<#x<<" = "<<x<<"\n"
#define LOW(v,x) (lower_bound(all(v),(x))-(v).begin())

int dx[]={-1,0,0,1},dy[]={0,-1,1,0};
int N,M;
char A[MAXN][MAXN];
int dist[MAXN][MAXN];
queue<pi>q;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>N>>M;
	FOR(i,1,N)cin>>(A[i]+1);
	memset(dist,-1,sizeof dist);
	FOR(i,1,N)FOR(j,1,M){
		if(A[i][j]=='#'){
			q.emplace(i,j);
			dist[i][j]=0;
		}
	}
	while(sz(q)){
		int x,y;tie(x,y)=q.front();q.pop();
		FOR(i,0,3){
			int nx=x+dx[i];
			int ny=y+dy[i];
			if(nx<1||nx>N)continue;
			if(ny<1||ny>M)continue;
			if(dist[nx][ny]!=-1)continue;
			dist[nx][ny]=dist[x][y]+1;
			q.emplace(nx,ny);
		}
	}
	//~ FOR(i,1,N)FOR(j,1,M)cout<<dist[i][j]<<" \n"[j==M];
	int mx=0;
	FOR(i,1,N)FOR(j,1,M)mx=max(mx,dist[i][j]);
	cout<<mx<<"\n";
}
/*
3
2 5
6 1
3 7
Ans:6

4
3 7
2 9
8 16
10 8
Ans:9
*/


Measured memory_bytes: 21556
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = 99999999;
const ll linf = 999999999999999999;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.end(), v.begin());
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

//ll ncr[100][100];
//ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

//ll npr[100][100]={};
//ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

//ll nHr(int n,int r){ret nCr(n+r-1,r);}

///////////////////////////////////////////////////////////////////////////



int main(){
	int n,l;
	cin >> n>> l;
    string s[200];
    rep(i,0,n)cin >> s[i];
    sort(s,s+n);
    rep(i,0,n)cout << s[i];
    cout << endl;
	return  0;
}

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

int main() {
  int n, p;
  cin >> n >> p;
  int a[n];
  for (int i = 0; i < n; i++) cin >> a[i];
  long dp[MAX_A * n + 1];
  fill(dp + 1, dp + MAX_A * n + 1, 0);
  dp[0] = 1;
  for (int i = 0; i < n; i++) {
    for (int j = MAX_A * n; j >= a[i]; j--) {
      dp[j] += dp[j - a[i]];
    }
  }
  long ans = 0;
  for (int i = p; i <= n * MAX_A; i += 2) {
    ans += dp[i];
  }
  cout << ans << endl;
  return 0;
}

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,m;
    cin>>n>>m;
    if(abs(n-m) > 1){
        cout<<"0\n";
        return 0;
    }
    if(n > m) swap(n,m);
    ll ans = 1;
    for(int i=1;i<=n;i++){
        ans = (ans * i) % mod;
    }
    for(int i=1;i<=m;i++){
        ans = (ans * i) % mod;
    }
    if(n == m){
        ans = (ans * 2) % mod;
    }
    cout<<ans<<"\n";
    return 0;
}




Measured memory_bytes: 256
#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[i];
                a[i] --;
        }
        int cur = 0;
        int ans = 0;
        while (cur != 1) {
                cur = a[cur];
                ans ++;
                if (ans > 101010) break;
        }
        if (ans > 101010) cout << -1 << endl;
        else cout << ans << endl;
}


Measured memory_bytes: 640
// dfmt off
T lread(T=long)(){return readln.chomp.to!T;}T[] lreads(T=long)(long n){return iota(n).map!((_)=>lread!T).array;}
T[] aryread(T=long)(){return readln.split.to!(T[]);}void arywrite(T)(T a){a.map!text.join(' ').writeln;}
void scan(L...)(ref L A){auto l=readln.split;foreach(i,T;L){A[i]=l[i].to!T;}}alias sread=()=>readln.chomp();
void dprint(L...)(lazy L A){debug{auto l=new string[](L.length);static foreach(i,a;A)l[i]=a.text;arywrite(l);}}
static immutable MOD=10^^9+7;alias PQueue(T,alias l="b<a")=BinaryHeap!(Array!T,l);import std, core.bitop;
// dfmt on

void main()
{
    auto S = sread();
    long Q = lread();
    DList!char ans;
    foreach (c; S)
        ans.insertBack(c);
    bool rev;
    foreach (_; 0 .. Q)
    {
        auto query = aryread!string();
        if (query[0] == "1")
        {
            rev = rev == false;
        }
        else
        {
            long F = query[1].to!long;
            char C = query[2][0];
            bool dir = rev == (F == 1);
            if (dir)
            {
                ans.insertBack(C);
            }
            else
            {
                ans.insertFront(C);
            }
        }
        dprint(rev, ans[]);
    }
    if (rev)
    {
        writeln(reverse(ans.array).array[]);
    }
    else
    {
        writeln(ans[]);
    }
}


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

using namespace std;

using int64 = long long;

int main() {
  int N, A, B;
  cin >> N >> A >> B;
  int v[3] = {};
  for(int i = 0; i < N; i++) {
    int x;
    cin >> x;
    if(x <= A) ++v[0];
    else if(x <= B) ++v[1];
    else ++v[2];
  }
  cout << min({v[0], v[1], v[2]}) << endl;

}

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

int main() {
    int N;
    cin >> N;
    vector<int> P(N), Q(N);
  
    for (int i = 0; i < N; i++) cin >> P.at(i), P.at(i)--;
    for (int i = 0; i < N; i++) cin >> Q.at(i), Q.at(i)--;

    vector<int> V(N);
    map<vector<int>, int> A;
    int cnt = 0;
    for (int i = 0; i < N; i++) V.at(i) = i;

    do {
        A[V] = cnt++;
    } while (next_permutation(V.begin(), V.end()));

    cout << abs(A[P] - A[Q]) << endl;
}

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

void solve()
{
    int n;
    cin >> n;
    int ans = 1000 - (n % 1000);
    if (ans == 1000)
        ans = 0;
    cout << ans;
    cout << endl;
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3616
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
#define drep(i,cc,n) for(int i=cc;i>=n;--i)
typedef long long ll;
using namespace std;
int main(){
    ll x;
    cin>>x;
    int a=0,b=0;
    int hoge=0;
    while(1){
        if(x>=500){
            x -= 500;
            a++;
        }
        else break;
    }
    while(1){
         if(x>=5){
            x -= 5;
            b++;
        }
        else break;
    }
    printf("%d\n",a*1000+b*5);
    return 0;
}

Measured memory_bytes: 888
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	string s;
	cin >> s;
	if (s.size() == 1)
	{
		cout << s;
	}
	else
	{
		int ans = (s.size() - 1) * 9;
		bool is = true;
		for (int i = 1; i < s.size(); i++)
		{
			if (s[i] != '9')
			{
				is = false;
				break;
			}
		}
		if (is == true)ans += s[0] - '0';
		else if (s[0] >= '2')ans += s[0] - '1';
		cout << ans;
	}
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<vector>
#include<utility>
#include<stack>
#include<queue>

#define FOR(i, a, b) for(int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define MOD 1000000007

using namespace std;

int main(void) {
	int n;
	int a[100001];
	int count = 0;

	cin >> n;
	FOR(i, 1, n) {
		cin >> a[i];
		if (a[i] % 2 == 1) {
			count++;
		}
	}
	if (count % 2 == 0) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

int main(void) {
	long long H, W;
	long long h, w;
	std::cin >> H >> W;
	std::cin >> h >> w;

	long long b = h * W;
	b += w * (H - h);

	std::cout << H*W - b << std::endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int main(){
  ll i,n,a[200010];
  cin >> n;
  vector<ll> x;
  for(i=0;i<n;i++){
    cin >> a[i];
    x.push_back(a[i]-i-1);
  }
  sort(x.begin(),x.end());
  ll sum=0,ans=x[n/2];
  for(i=0;i<n;i++){
    sum+=abs(x[i]-ans);
  }
  cout << sum << endl;
}

Measured memory_bytes: 6524
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;
#define ll long long
#define pb push_back

int main() {
  int a,b,c;
  cin >> a >> b >> c;

  int maxnum = max(a,max(b,c));
  int sum = maxnum*10 + a + b + c - maxnum;
  
  cout << sum << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int y;
  double a, b, x, z;
  
  cin >> a >> b ;
  
  x = (a + b)/2.0;
  y = (a + b)/2;
  z = x - y;
  
  if (z == 0.0){
    cout << y << endl;
  }
  
  else if (x - y > 0.0){
    cout << y + 1 << endl;
  }
}

Measured memory_bytes: 3676
//hi
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long int LL;
int a[20002];
int b[20002];
int p[20002];
int da[200002];
int db[200002];
int main(void){
    int n;
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;i++) a[i]=i, b[i]=n+1-i; 
    for(i=1;i<=n;i++) scanf("%d",&p[i]);
    for(i=1;i<=n;i++){
		db[p[i]]+=i;
		da[p[i]-1]-=i;
	}
	for(i=n-1;i>=1;i--) da[i]+=da[i+1], db[i]+=db[i+1];
	for(i=1;i<=n;i++) a[i]+=da[i], b[i]+=db[i];
	int ga=a[1], gb=b[1];
	if(ga<1)
		for(i=1;i<=n;i++) a[i]+=(1-ga);
	if(gb<1)
		for(i=1;i<=n;i++) b[i]+=(1-gb);
	for(i=1;i<=n;i++) printf("%d%c",a[i],i==n?'\n':' ');
	for(i=1;i<=n;i++) printf("%d%c",b[i],i==n?'\n':' ');
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h> 
using namespace std; 
long long arr[100005][3] , dp[100005][3];
int main(){
	int n ;
	cin>>n;
	for(int i = 0; i< n;  i++){
		for(int j = 0; j < 3 ; j++)
			cin>>arr[i][j];
	}
	dp[0][0] = arr[0][0];
	dp[0][1] = arr[0][1];
	dp[0][2] = arr[0][2];
	for(int i= 1 ; i < n;  i++){
		for(int curr_element = 0; curr_element < 3 ; curr_element++){
			for(int which_one = 0; which_one < 3 ; which_one++){
				if(curr_element== which_one)continue;
				long long mxn = 0;
				for(int max_dp  = 0 ; max_dp < 3 ; max_dp++){
					if(curr_element==max_dp)continue;
					mxn = max(mxn ,dp[i - 1][max_dp]);
				}
				dp[i][curr_element] = max(dp[i][curr_element] , mxn + arr[i][curr_element]);
				
			}
		}
	}
	cout<<max(dp[n-1][0] , max(dp[n-1][1] , dp[n-1][2]));
	return 0;
}  


Measured memory_bytes: 4992
N, M = map(int, input().split())

l = -1
r = N + 1
for i in range(M):
    L, R = map(int, input().split())
    l = max(l, L)
    r = min(r, R)
    
if l > r:
    print(0)
else:
    print(r - l + 1)

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

public class MainClass
{
	public const long Giri = 1000000007;
	public const long DpInf = 99999999999;
	
	public static void Main(string[] args)
	{
		var n = Console.ReadLine().ToInt();
		var k = Console.ReadLine().ToInt();
		var x = Console.ReadLine().ToInt();
		var y = Console.ReadLine().ToInt();
		
		Console.WriteLine(Math.Max(0, (n-k)*y) + Math.Min(n, k)*x);
	}

	static long GCD(long a, long b)
	{
		var v = new[] { a, b };
		while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
		return v[0];
	}
	public static string[] Input() { return Console.ReadLine().Split(); }
}

public static class Smarter
{
	public static int ToInt(this string str) { return int.Parse(str); }
	public static long ToLong(this string str) { return long.Parse(str); }
	public static int[] ToInt(this string[] str)
	{
		var r = new int[str.Length];
		for(int i = 0; i < str.Length; i++) r[i] = str[i].ToInt();
		return r;
	 }
}


Measured memory_bytes: 11220