akhauriyash/Code-Regression huggingface dataset:
/*/ Author: KaySeeKay /*/

#include<bits/stdc++.h>
using namespace std;	

/*/---------------------------Defines-----------------------------------------/*/

#pragma GCC optimize("Ofast") 
#define int long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back 
#define eb emplace_back
#define fn for(int i =0 ;i <n;i++)	
#define fn1 for( int i =1;i<=n;	i++)
#define fm for(int j =0 ;j <m;j++)
#define fm1 for(int j =1;j<=m;j++)
#define fi first
#define se second
#define endl '\n'
#define PI  3.14159265358979323846
#define MOD 1000000007
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
const int N = 2e6+5;	
const int INF = 1e18L;
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
/*/-----------------------------Debug begins----------------------------------/*/
vector<string> split(const string& s, char c) {
    vector<string> v; stringstream ss(s); string x;
    while (getline(ss, x, c)) v.emplace_back(x); return move(v);
}
template<typename T, typename... Args>
inline string arrStr(T arr, int n) {
    stringstream s; s << "[";
    for(int i = 0; i < n - 1; i++) s << arr[i] << ",";
    s << arr[n - 1] << "]";
    return s.str();
}
#define trace(args...) {__trace_begin(__LINE__); __trace(split(#args, ',').begin(), args);}
inline void __trace_begin(int line) { cerr << "#" << line << ": "; }
template<typename T> inline void __trace_out_var(vector<T> val) { cerr << arrStr(val, val.size()); }
template<typename T> inline void __trace_out_var(T* val) { cerr << arrStr(val, 10); }
template<typename T> inline void __trace_out_var(T val) { cerr << val; }
inline void __trace(vector<string>::iterator it) { cerr << endl; }
 
template<typename T, typename... Args>
inline void __trace(vector<string>::iterator it, T a, Args... args) {
    cerr << it->substr((*it)[0] == ' ', it->length()) << "=";
    __trace_out_var(a);
    cerr << "; ";
    __trace(++it, args...);
}
/*/-----------------------------Code begins----------------------------------/*/
int ar[N];
int dp[N];
inline int add(int x, int y, int mod) {
   if (y >= mod) y %= mod;
   if (x >= mod) x %= mod;
   x  += y;
   return (x >= mod ? x - mod : x);
}
signed main(){
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
	IOS;
	int T=1;
	// cin >> T;
	while(T--){
		int n;
		cin >> n;
		vector<int>v;
		dp[0]=1;	
		for(int i=3;i<=n;i++){
			v.pb(i);
		}
		int m =v.size();
		for(int j =1;j<=n;j++){
			for(int  i =0 ;i<m;i++){
				if(j-v[i]>=0)
				dp[j] = add(dp[j],dp[j-v[i]],MOD);
			}
		}
		cout << dp[n];	
	
	}
	return 0;
}

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

bool binarySearch(int key,int n,int A[]) {
  int left=0;
  int right=n;
  while (left<right) {
    int mid=(left+right)/2;
    if (key==A[mid]) {
      return true;
    }
    if (key>A[mid]) {
      left=mid+1;
    } else if (key<A[mid]) {
      right=mid;
    }
  }
  return false;
}
int main() {
  int n;
  cin>>n;
  int A[n];
  for (int i=0; i<n; i++) {
    cin>>A[i];
  }
  int q;
  cin>>q;
  int k;
  int ans=0;
  for (int i=0; i<q; i++) {
    cin>>k;
    if (binarySearch(k,n,A)) {
      ans++;
    }
  }
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 3480
#include <iostream> // cout, endl, cin
#include <cmath> //sqrt pow
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
 
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  int n;
  cin >> n;
  vi w(n + 1);
  rep(i, n) cin >> w[i + 1];
  rep(i, n) w[i + 1] += w[i];
  int ans = 10000;
  rep(i, n){
    ans = min(abs(w[i + 1] - (w[n] - w[i + 1])), ans);
  }
  cout << ans << endl;
}

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

int main(){
  long long   n,at=-1;
  cin>>n;
  for(long long i=1;i<=n;i++){
    if(i*i<=n){
      at=max(at,i*i);
    }
  }
  cout<<at<<endl;
}
      


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
typedef long long int ll;
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define EREP(i,n) for (int i=1;i<=(n);i++)
#define EVEL 1

#ifndef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define TF(f) f ? cout<<"true  " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {X;}
#define TF(f) {f;}
#define END {}
#endif
const int MOD = 1000000007;
const int INF = 1000000;
#define NMAX 5000
#define MAX 10

ll sum[NMAX + 1], temp, buff = 0;
int N, K, ans = 0;
int A[100010];
int count = 0;
bool dp[NMAX + 10][NMAX + 10], dp1[NMAX + 10][NMAX + 10];
bool vis[NMAX + 10][NMAX + 10], vis1[NMAX + 10][NMAX + 10];
int low = 0, high, mid;

bool dfs(ll x, ll y) {
	//    DEB(x)DEB(y)END
	if (y<0)return false;
	if (y == 0) { return true; }
	if (vis[x][y]) {
		return dp[x][y];
	}
	else vis[x][y] = true;
	if (x == N) { dp[x][y] = false;/*DEB(dp[x][y])DEB(x)DEB(y)END*/ return dp[x][y]; }

	if (dfs(x + 1, y) || dfs(x + 1, y - A[x])) {
		dp[x][y] = true;
	}
	else dp[x][y] = false;
	//DEB(dp[x][y])DEB(x)DEB(y)END
	return dp[x][y];
}
bool front(ll x, ll y) {
	if (y<0)return false;
	if (x<0) {
		//DEB(dp1[x][y])DEB(x)DEB(y)END
		if (x == -1 && y == 0)return true;
		else return false;
	}
	if (vis1[x][y]) {
		return dp1[x][y];
	}
	else vis1[x][y] = true;
	if (y == 0) {
		dp1[x][y] = true; //DEB(dp1[x][y])DEB(x)DEB(y)END
		return dp1[x][y];
	}


	if (front(x - 1, y) || front(x - 1, y - A[x])) {
		dp1[x][y] = true;
	}
	else dp1[x][y] = false;
	//DEB(dp1[x][y])DEB(x)DEB(y)END
	return dp1[x][y];
}


int main() {
	ios_base::sync_with_stdio(false);
	cin >> N >> K;
	ans = N;
	REP(i, N) { cin >> A[i]; }
	sort(A, A + N);
	low = -1;
	high = N;
	while (low + 1 != high) {
		ll i = (high + low) / 2;
		DEB(high)DEB(i)DEB(low)END
			bool m = false;
		FOR(j, 0, K + 1) {
			if (j<0)j = 0;
			//if(front(i,j)) m=true;
			FOR(k, K - A[i] - j, K + 1) {
				if (k<0)k = 0;
				if (j + k >= K)break;
				DEB(i)DEB(j)DEB(k)
					TF(front(i, j))
					TF(dfs(i, k))
					TF(dfs(i, k) && front(i, j))
					END
					if (dfs(i + 1, k) && front(i - 1, j)) {

						m = true;
						break;
					}
			}
			if (m)break;
		}
		if (m) { high = i; }
		else { low = i; }


	}


	cout << low + 1 << endl;
}
//ABC056 AtCoDeer

Measured memory_bytes: 78208
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;


ll p[51] = {0};
ll b[51] = {0};
ll ans = 0;

ll func(ll eat,ll level){
	if(level==0) return 1;
	if(eat<=level) return 0;
	ll res = 0;
	if(eat==(b[level]+1)/2){
		res++;
		res += func(eat-2,level-1);
	}
	else if(eat>(b[level]+1)/2){
		res++;
		res += p[level-1];
		res += func(eat-b[level-1]-2,level-1);
	}else{
		res += func(eat-1,level-1);
	}
	return res;
}

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

	p[0] = 1;
	b[0] = 1;
	for(int i = 1; i <= 50; i++){
		p[i] = 2*p[i-1] + 1;
		b[i] = 2*b[i-1] + 3;
	}
	// for(int i = 0; i <= n; i++){
	// 	cout << p[i] << " " << b[i] << endl;
	// }

	ans = func(x,n);
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
data = require("fs").readFileSync("/dev/stdin", "utf8").split(/\r?\n/g)[1];

data = data.split(/ /g).map(d => parseInt(d));

count = 0;
flag = false;

while ('jota') {
  data = data.map(d => {
    if (d & 1) flag = true;
    return d >> 1;
  });
  
  if (flag) break;
  count++;
}

console.log(count);

Measured memory_bytes: 7500
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    token.parse().ok().unwrap()
}

fn main() {
    let h = input::<usize>();
    let w = input::<usize>();
    let k = input::<usize>();
    const MOD: usize = 1000000007;

    let mut dp = vec![vec![0; w + 1]; h + 1];
    dp[0][1] = 1;
    for i in 0..h {
        for j in 1..w + 1 {
            for k in 0..1 << (w - 1) {
                if w > 1 {
                    let mut ok = true;
                    for l in 0..w - 2 {
                        if k & (1 << l) > 0 && k & (1 << (l + 1)) > 0 {
                            ok = false;
                        }
                    }
                    if !ok {
                        continue;
                    }
                }

                if j > 1 && k & (1 << (j - 2)) > 0 {
                    dp[i + 1][j - 1] += dp[i][j];
                    dp[i + 1][j - 1] %= MOD;
                } else if j < w && k & (1 << j - 1) > 0 {
                    dp[i + 1][j + 1] += dp[i][j];
                    dp[i + 1][j + 1] %= MOD;
                } else {
                    dp[i + 1][j] += dp[i][j];
                    dp[i + 1][j] %= MOD;
                }
            }
        }
    }
    let ans = dp[h][k];
    println!("{}", ans);
}


Measured memory_bytes: 4352
# numpyでかいてもTLEした。
# pypyでlistでかくととおる？

#import numpy as np
N,M = list(map(int, input().split()))
S = list(map(int, input().split()))
T = list(map(int, input().split()))
mod = int(1e9+7)
"""
dp[i][j] : S の i 文字目までと T の j 文字目までを考慮し、
この 2 文字 (S[i] と T[j]）をペアにするときの場合の数とすると、

dp[i][j] = (sum(dp[1:i-1][1:j-1]) + 1 if S[i] == T[j] else 0)
このsumの部分をどうもとめるか。

最終的な答えはsum(dp[:][:])。

2-D cumsumをつかう
i,j = 0のときにきをつけて
DS[i][j] = DS[i-1][j] + DS[i][j-1] - DS[i-1][j-1] + dp[i][j]
"""

dp = [[ 0 for _ in range(M)] for _ in range(N)]
DS = [[ 0 for _ in range(M+1)] for _ in range(N+1)]

for i in range(N):
  for j in range(M):
    if S[i] != T[j]:
      dp[i][j] = 0
    else:
      dp[i][j] += 1
      dp[i][j] += DS[i-1][j-1]
      dp[i][j] %= mod
    DS[i][j] = DS[i-1][j] + DS[i][j-1] - DS[i-1][j-1] + dp[i][j]
    DS[i][j] %= mod
print(DS[-2][-2]+1)
#print(dp)
#print(DS)


Measured memory_bytes: 139452
//In the Name of God
//Ya Ali

#include<bits/stdc++.h>

#define int long long

#define err(A) cout<<#A<<" = "<<(A)<<endl

using namespace std;

const int maxn=512;

int W,H,w,h;

int a[maxn][maxn];
int s=0;

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

  cin>>W>>H;
  cin>>w>>h;

  if(w*h==1)
    {
      cout<<"No"<<endl;
      return 0;
    }

  int x=(1000000000-1)/(w*h-1);
  
  for(int i=0;i<W;i++)
    for(int j=0;j<H;j++)
      {
	if(i%w==w-1 and j%h==h-1)
	  a[i][j]=-(w*h*x-x+1);
	else
	  a[i][j]=+x;
	s+=a[i][j];
      }

  if(s<=0)
    {
      cout<<"No"<<endl;
      return 0;
    }

  cout<<"Yes"<<endl;
  for(int i=0;i<W;cout<<endl,i++)
    for(int j=0;j<H;j++)
      cout<<a[i][j]<<" ";
  
  return 0;
}


Measured memory_bytes: 4992
C=[]
while True:
    try:
        B=input()
        B=B.lower()
        C.append(B)
    except EOFError:
        break
    A="".join(C)
print('a',':',A.count('a'))
print('b',':',A.count('b'))
print('c',':',A.count('c'))
print('d',':',A.count('d'))
print('e',':',A.count('e'))
print('f',':',A.count('f'))
print('g',':',A.count('g'))
print('h',':',A.count('h'))
print('i',':',A.count('i'))
print('j',':',A.count('j'))
print('k',':',A.count('k'))
print('l',':',A.count('l'))
print('m',':',A.count('m'))
print('n',':',A.count('n'))
print('o',':',A.count('o'))
print('p',':',A.count('p'))
print('q',':',A.count('q'))
print('r',':',A.count('r'))
print('s',':',A.count('s'))
print('t',':',A.count('t'))
print('u',':',A.count('u'))
print('v',':',A.count('v'))
print('w',':',A.count('w'))
print('x',':',A.count('x'))
print('y',':',A.count('y'))
print('z',':',A.count('z'))


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

int main(){
    vector<int> w(10), k(10);
    for(int i = 0; i < 10; i++) cin >> w[i];
    for(int i = 0; i < 10; i++) cin >> k[i];
    sort(w.begin(), w.end());
    sort(k.begin(), k.end());
    cout << w[9]+w[8]+w[7] << " "
        << k[9]+k[8]+k[7] << endl;
    return 0;
}


Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vi = vector<int>;
using vvi = vector<vi>;
#define ote(x) cout<<(x)<<endl
#define all(x) (x).begin(),(x).end()
#define rp(i,s,e) for(int i=(s);i<(e);++i)

int main(){
	int N; cin>>N;
	vi L(N),R(N);
	rp(i,0,N)cin>>L[i]>>R[i];
	ll ans = 0;
	rp(i,0,N){
		ans += R[i]-L[i]+1;
	}
	ote(ans);
}


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


int main(void) 
{
    int n, m;
    cin >> n >> m;

    vector<int> graph[n];

    rep(i,m){
        int a, b;
        cin >> a >> b;
        --a; --b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    queue<int> que;
    vector<int> ans (n, -1);
    que.push(0);
    while(!que.empty()){
        int a = que.front(); que.pop();

       // cout << a << endl;
        for(int b : graph[a])
        {
            if(ans[b] == -1) 
            {
                ans[b] = a;
                que.push(b);
            }
        }
    }

    rep(i,n-1) if(ans[i+1] == -1)
    {
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
    rep(i,n-1) cout << ans[i+1]+1 << endl;
}

Measured memory_bytes: 10168
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int N, X, R;
    cin >> N >> X >> R;
    vector<int> a;
    a.push_back(N);
    a.push_back(X);
    a.push_back(R);
    sort(a.begin(), a.end());
    cout << a[0]+a[1];
}


Measured memory_bytes: 256
N = int(input())
red = []
for _ in range(N):
    a, b = map(int, input().split())
    red.append((b, a))
red.sort()
blue = []
for _ in range(N):
    c, d = map(int, input().split())
    blue.append((c, d))
blue.sort()
ans = 0
for c, d in blue:
    for i in range(N - 1, -1, -1):
        if red[i][1] < c and red[i][0] < d:
            ans += 1
            red[i] = (300, 300)
            break
print(ans)

Measured memory_bytes: 3064
m = list(map(int,input().split(" ")))
n = m[0]
x = m[1]
l = list(map(int,input().split(" ")))

#d1 = 0, d2 = 0 +3, d3 = 3+4
d = 0
d_count = 1
for i in range(n):
    d = d + l[i]
    # print(d)
    if d <= x:
        d_count += 1
        # print(d_count)
    else:
        exit
    exit

print(d_count)

Measured memory_bytes: 3064
import java.util.Scanner;

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

		int N = input.nextInt();
		int M = input.nextInt();
		int X = input.nextInt();

		int minCost = -1;

		int[][] bookList = new int[N][M + 1];

		//参考書リストの作成
		for(int i = 0; i < N; i++) {
			for(int m = 0; m <= M ;m++) {

				int n = input.nextInt();
				bookList[i][m] = n;

			}
		}
		input.close();

		for(int bit = 0; bit < (1 << N); bit++) {
			int[] buyList = new int[M +1];
			int flag = 0;

			for(int i =0;i < N; ++i ) {
				if((1 & bit >> i) == 1) {

					for(int m = 0; m < M + 1; m++) {

						buyList[m] = buyList[m] + bookList[i][m];
						//System.out.println(buyList[m]);

					}
				}
			}
			for(int m =1; m < M + 1; m++) {

				if(buyList[m] < X) {

					flag = 1;

				}

			}
			//System.out.println(buyList[0]);

			if(((minCost > 0) & (buyList[0] < minCost) & flag == 0) | ((minCost == -1) & flag == 0) ) {
				minCost = buyList[0];
			}
		}

		System.out.println(minCost);

	}
}


Measured memory_bytes: 37416
#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <algorithm>
#include<iomanip>
using namespace std;
using ll=long long;

const ll INF=1000000000000000000;
const ll MAX_V=1005;

struct edge {
    ll to;
    double cost;
};

// <最短距離, 頂点の番号>
using P = pair<double, ll>;

ll V;
vector<edge> G[MAX_V];
double d[MAX_V];

void dijkstra(ll s) {
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d, d+V, INF);
    d[s] = 0;
    que.push(P(0, s));

    while (!que.empty()) {
        P p = que.top();
        que.pop();
        ll v = p.second;
        if (d[v] < p.first) continue;

        for (ll i=0; i<G[v].size(); ++i) {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}

ll points[MAX_V][3];
int main() {
    cin >> points[0][0] >> points[0][1] >> points[1][0] >> points[1][1];
    cin >> V;
    V+=2;
    for (ll i=2; i<V; ++i) {
        cin >> points[i][0] >> points[i][1] >> points[i][2];
    }
    for (ll i=0; i<V; ++i) {
        for (ll j=i+1; j<V; ++j) {
            double cost=sqrt((points[i][0]-points[j][0])*(points[i][0]-points[j][0])+
                (points[i][1]-points[j][1])*(points[i][1]-points[j][1]));
            cost=max(0.0,cost-points[i][2]-points[j][2]);
            edge e1 = {j, cost};
            G[i].push_back(e1);
            edge e2 = {i, cost};
            G[j].push_back(e2);
        }
    }
    dijkstra(0);
    cout << setprecision(16) << d[1] << endl;
}

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

int main() {
  int n,k;
  cin >> n >> k;
  vector<int>a(n);
  rep(i,0,n) cin >> a[i];
  sort(a.begin(),a.end());
  vector<int>c;
  int v = a[0],cnt = 1,s = 0;
  rep(i,1,n){
    if(a[i] == v) cnt++;
    else{
      c.push_back(cnt);
      s++;
      v = a[i];
      cnt = 1;
    }
  }
  c.push_back(cnt);
  s++;
  sort(c.begin(),c.end());
  int ans = 0,pos = 0;
  while(1){
    if(s <= k){
      cout << ans << endl;
      return 0;
    }
    ans += c[pos];
    pos++;
    s--;
  }
}

Measured memory_bytes: 4984
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1e9+7;
const int INF=1e9;
const ll LINF=(ll)1e18;

int main(){
    int n,k;
    cin>>n>>k;
    double p[n+1];
    for(int i=0;i<n;i++){
        cin>>p[i+1];
        p[i+1]=p[i+1]/2+0.5;
        p[i+1]+=p[i];
    }
    double ans=-INF;
    for(int i=k;i<=n;i++){
        ans=max(ans,p[i]-p[i-k]);
    }
    cout<<fixed<<setprecision(10)<<ans<<endl;
}


Measured memory_bytes: 1792
#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

typedef long long ll;
//typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector<vector<int>> mat;
//typedef unsigned int uint;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

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

	int A[5];
	int K;
	rep(i, 0, 5)
	{
		cin >> A[i];
	}
	cin >> K;

	rep(i, 0, 4)
	{
		if (A[4] - A[i] > K)
		{
			cout << ":(" << endl;
			return 0;
		}
	}

	cout << "Yay!" << endl;

	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define sync ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ll long long int
#define mod 1000000007
using namespace std;
vector<ll> prime,sfac;
vector<ll>ps;
void sieve(ll n)
{
	prime.assign(n+1,1);
	sfac.assign(n+1,1);    
    for (int p=2; p*p<=n; p++) 
    {         
        if (prime[p] == 1) 
        { 	sfac[p]=p;  			  
            for (int i=p*p; i<=n; i += p) 
              {  prime[i] = 0; sfac[i]=p;}
        } 
    } 
	for(ll i=2;i<=n;i++)
	{
		if(prime[i])
			ps.push_back(i);
	}
}
ll gcd(ll a, ll b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
ll power(ll x, ll y) 
{ 
    ll res = 1;    
    while (y > 0) 
    { 
        ll k=y&1LL;
        if (k) 
            res = res*x;      
        y = y>>1LL;
        x = x*x;  
    } 
    return res; 
}
 
int isPrime(ll n) 
{ 
    if (n <= 1)  return 0; 
    if (n <= 3)  return 1; 
    if (n%2 == 0 || n%3 == 0) 
        return 0;   
    for (ll i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return 0;  
    return 1; 
} 
void debug(ll a[],ll n)
{
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
}
void input(ll a[],ll n)
{
    for(int i=0;i<n;i++)
        cin>>a[i];
}
int main()
{
    ll tt;
    cin>>tt;
    map<string,int>m;
    while(tt--)
    {
        string s;
        cin>>s;
        m[s]++;
    }
    cout<<"AC x "<<m["AC"]<<endl;
    cout<<"WA x "<<m["WA"]<<endl;   
    cout<<"TLE x "<<m["TLE"]<<endl;   
    cout<<"RE x "<<m["RE"]<<endl;       
}

 

Measured memory_bytes: 3632
n = int(input())
x = list(input())

def popcount(n):
    bin_n = bin(n)[2:]
    count = 0
    for i in bin_n:
        count += int(i)
    return count

cnt = 0
for i in range(n):
    if x[i] == '1':
        cnt += 1

plus = [0 for i in range(n)] # 2^index を cnt+1 で割った時のあまり
minus = [0 for i in range(n)] # 2^index を cnt-1 で割った時のあまり
if cnt == 0:
    plus[0] = 0
else:
    plus[0] = 1
if cnt != 1:
    minus[0] = 1
for i in range(1, n):
    plus[i] = (plus[i-1]*2) % (cnt+1)
    if cnt != 1:
        minus[i] = (minus[i-1]*2) % (cnt-1)

origin = int(''.join(x), base=2)
amariplus = origin % (cnt+1)
if cnt != 1:
    amariminus = origin % (cnt-1)

for i in range(n):
    if x[i] == '0':
        amari = (amariplus + plus[n-i-1]) % (cnt+1)
    else:
        if cnt != 1:
            amari = (amariminus - minus[n-i-1]) % (cnt-1)
        else:
            print(0)
            continue
    ans = 1
    while amari != 0:
        ans += 1
        amari = amari % popcount(amari)
    print(ans)

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

// エイリアス
using  ll = long signed long;
using ull = long unsigned long;
using  ld = long double;
using   P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;

// 汎用マクロ
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOREACH(i,q) for (auto &i : q)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
#define SZ(x) ((int)(x).size())
template <class T>inline bool chmin(T &a, const T b) {if (a > b) { a = b; return true;} return false;}
template <class T>inline bool chmax(T &a, const T b) {if (a < b) { a = b; return true;} return false;}
template <class T>inline void line_out(const vector<T> vec) {int n = SZ(vec); rep(i, n) { cout << vec[i]; if(i < n-1) cout << " ";}cout << endl;}
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 28;
const ll INF64 = 1ll << 55;
const int mod = 1000000007;
//const int mod = 998244353;
struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

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

int main()
{
  int n; cin >> n;
  vector<int> x(n);
  rep(i, n) cin >> x[i];

  int ans = INF;

  for(int p = 1; p <= 100; ++p) {
    int tmp = 0;
    rep(i, n) tmp += (x[i]-p)*(x[i]-p);
    chmin(ans, tmp);
  }
  cout << ans << endl;
}


Measured memory_bytes: 3620
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
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; }
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long int ll;
typedef long double ld;
const ll INF=(1LL<<62);
const ld pi=acosl((ld)-1);
// const ll mod = 1000000007;
const ll mod = 1234567;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
#define endn "\n"

bool check(vector<string>s){
    rep(i,s.size())rep(j,s[i].size()){
        if(s[i][j]!=s[j][i])return false;
    }
    return true;
}

void add(vector<string>&s){ 
    auto cs=vector<string>(all(s));
    rep(i,(int)s.size()-1){
        s[i+1]=cs[i];
    }
    s[0]=cs.back();
}

bool solve(){
    ll n;cin>>n;
    vector<string>s(n);
    rep(i,n)cin>>s[i];
    ll ans=0;
    rep(i,n){
        ans+=check(s);
        add(s);
    }
    ans*=n;
    cout<<ans<<endl;

    return false;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<fixed<<setprecision(30);
    solve();
}


Measured memory_bytes: 512
#include<stdio.h>

int c[10];

int main()
{
    int i,j;
    int a,flag,ff;
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=8;i++) c[i]=0;
        flag=0;
        ff=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a);
            if(a>=1&&a<=399) c[1]=1;
            if(a>=400&&a<=799) c[2]=1;
            if(a>=800&&a<=1199) c[3]=1;
            if(a>=1200&&a<=1599) c[4]=1;
            if(a>=1600&&a<=1999) c[5]=1;
            if(a>=2000&&a<=2399) c[6]=1;
            if(a>=2400&&a<=2799) c[7]=1;
            if(a>=2800&&a<=3199) c[8]=1;
            if(a>=3200) flag++;
        }
        for(i=1;i<=8;i++) if(c[i]==1) ff++;
        flag=flag+ff;
        if(ff==0) ff=1;
        printf("%d %d\n",ff,flag);
    }
}


Measured memory_bytes: 128
#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; }
#define ll long long
#define MOD (ll)1e9+7

const ll INF= 1LL << 60;

//入力
int H,W;
vector<string> a;

//dp
ll dp[1010][1010];

void add(ll& a,ll b){
  a+=b;
  if(a>=MOD) a-=MOD;
}
 
int main(){
  cin>> H >> W;
  
  for(int i=0;i<H;i++){
    string as;
    cin>>as;
    a.push_back(as);
  }
  for(int i=0;i<H;i++)
    for(int j=0;j<W;j++)
      dp[i][j]=0;
  
  dp[0][0]=1;
  
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(a[i][j]=='#'){
         dp[i][j]=0;
      }else{
       	 if(j+1<W) if(a[i][j+1]=='.') add(dp[i][j+1],dp[i][j]);
         if(i+1<H) if(a[i+1][j]=='.') add(dp[i+1][j],dp[i][j]);
         
       }
    }
  }

  
  cout << dp[H-1][W-1] << endl;
}

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

int main(){
  int a[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int b;
  cin >> b;
  cout << a[b-1] << endl;
  return 0;
}

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

void Main()
{
  int N,M;
  cin >> N >> M;
  vector<vector<int>> s(M);
  vector<int> p(M);
  rep(i,M) {
    int k;
    cin >> k;
    rep(j,k) {
      int sjk;
      cin >> sjk; sjk--;
      s[i].push_back(sjk);
    }
  }
  rep(i,M) {cin >> p[i];}
  
  int pattern = 0;
  rep(bit, 1<<N) {
    bool allLight = true;
    for (int m = 0; m < M; m++) {
      int onSwitch = 0;
      for (int i = 0; i < s[m].size(); i++) {
        if (bit & (1<<s[m][i])) { // 1==電気ON, 0==電気OFF
		  onSwitch++;
        }
      }
      if (onSwitch % 2 != p[m]) {allLight = false; break;}
    }
    if (allLight) pattern++;
  }
  cout << pattern << endl;
}

int main()
{
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  Main();
  return 0;
}

Measured memory_bytes: 256
x,k,d=map(int,input().split())
x=abs(x)
syou=x//d
if k<=syou:
  print(x-k*d)
else:
  k=k-syou
  x=x%d
  if k%2==0:
    print(x)
  else:
    print(abs(x-d))

Measured memory_bytes: 9036
#include<stdio.h>

int main(void)
{
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    int min;
    int max;
    min=a[0];
    max = a[1]-min;
    for(int i=1;i<n;i++)
    {
        if(max<a[i]-min)
        {
            max = a[i]-min;
        }
        if(min>a[i])
        {
            min=a[i];
        }
    }
    printf("%d\n",max);
    return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;

ll eq_count(string s) {
  ll cnt = 0;
  for (ll i = 0; i < s.size()-1; i++) {
    if (s[i] == s[i+1]) {
      cnt++;
      i++;
    }
  }
  return cnt;
}

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

  ll cnt = eq_count(s);
  ll ecnt = eq_count(s+s) - cnt;
  ll ocnt = eq_count(s+s+s) - ecnt - cnt;

  if (k == 1) {
    cout << cnt << endl;
  }
  else if (k == 2) {
    cout << ecnt+cnt << endl;
  } else if (k == 3) {
    cout << ecnt+ocnt+cnt << endl;
  } else {
    ll en = k/2;
    ll on = k - en - 1;
    cout << en*ecnt + on*ocnt + cnt << endl;
  }
  
  return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
#include<algorithm>
using namespace std;

int main()
{
    int ar[4],i;
    for (i=0;i<4;++i){
        scanf("%d",&ar[i]);
    }
    sort(ar,ar+4);
    if(ar[0]==1 && ar[1]==4 && ar[2]==7 && ar[3]==9)printf ("YES\n");
    else printf ("NO\n");
    return 0;
}


Measured memory_bytes: 128
#include <cmath>
#include <queue>
#include <cstdio>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 200010
#define ll long long
using namespace std;
inline int read() 
{ 
    int x=0,f=1;char ch=getchar(); 
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 
    return x*f; 
}
int n,m;
bool one_get[N],get_n[N];
int main()
{
	n=read(),m=read();
	for(int i=1;i<=m;i++)
	{
		int a=read(),b=read();
		if(a==1)one_get[b]=1;
		if(b==n)get_n[a]=1;	
	}
	for(int i=1;i<=n;i++)
	{
		if(one_get[i]&&get_n[i])
		{
			puts("POSSIBLE");
			return 0;
		}
	}
	puts("IMPOSSIBLE");
	return 0;
}

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

int main(){
  int N,i;
  string s,t,ss,st;
  cin>>N>>s>>t;
  for(i=N;i>0;i--){
    ss=s.substr(N-i,i);
    st=t.substr(0,i);
    if(ss==st) break;
  }
  cout<<(N-i)*2+i<<endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main
{
	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		int a=sc.nextInt();
		int b=sc.nextInt();
		int c=sc.nextInt();
		if(a<=b)
		{
			if(c<=b/a)
			{	
				System.out.println(c);
			}
			else
			{
				System.out.println(b/a);
			}
		}
		else
		{
			System.out.println("0");
		}
	}
}

Measured memory_bytes: 23892
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100010
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,a[N],b[N],pa[N],pb[N],pos[N],vis[N];
bool Solve(){
	for(int i=1;i<=n;++i){
		pa[i]=pb[i]=i;
	}
	sort(pa+1,pa+n+1,[&](int i,int j){return a[i]<a[j];});
	sort(pb+1,pb+n+1,[&](int i,int j){return b[i]<b[j];});
	for(int i=1;i<=n;++i){
		if(a[pa[i]]>b[pb[i]])return false;
	}
	for(int i=1;i<n;++i){
		if(a[pa[i+1]]<=b[pb[i]])return true;
	}
	for(int i=1;i<=n;++i){
		pos[pa[i]]=pb[i];
	}
	int cnt=0,u=n;
	while(!vis[u]){
		vis[u]=1;
		u=pos[u];
		++cnt;
	}
	return cnt<n;
}
int main(){
	n=read();
	for(int i=1;i<=n;++i){
		a[i]=read();
	}
	for(int i=1;i<=n;++i){
		b[i]=read();
	}
	printf(Solve()?"Yes\n":"No\n");
	return 0;
}


Measured memory_bytes: 5960
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

/*----------macros----------*/

//output================
#define endl '\n'
#define fcout cout << fixed << setprecision(15)

//typedef===============
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;

//const number==========
constexpr ll INF9   = (ll)1e9 + 1;
constexpr ll INF18  = (ll)1e18 + 1;
constexpr ll MOD    = 1000000007;
constexpr ld PI     = 3.141592653589793L;

//member================
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second

//others================
#define all(x)          (x).begin(), (x).end()
#define rall(x)         (x).rbegin(), (x).rend()
#define rep(i, n)       for(int i = 0; (i) < (int)(n); (i)++)
#define rrep(i, n)      for(int i = n - 1; (i) >= 0 ; (i)--)
#define For(i, a, b)    for(int i = (a); (i) < (int)(b) ; (i)++)
#define CtoI(c)         int((c)) - int('0')

//functions=============
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

//vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
//vector<int> dx2 = { 1,1,0,-1,-1,-1,0,1 }, dy2 = { 0,1,1,1,0,-1,-1,-1 };



/*--------additional--------*/



/*----------main------------*/

int main() {
/*----------fastio----------*/
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
/*----------solve-----------*/

    int n; cin >> n;
    set<int> s;
    rep(i, n){
        ll a; cin >> a;
        s.insert(a);
    }

    if((int)s.size() == n) cout << "YES" << endl;
    else cout << "NO" << endl;

return 0;
}

Measured memory_bytes: 12940
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ff first
#define ss second
#define eb emplace_back
#define MP make_pair
#define pb push_back
#define pf push_front
#define ins insert
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define mset(m,v) memset(m,v,sizeof(m))
#define tr(c,it) for(auto it=c.begin();it!=c.end();it++)
#define fr(i,n) for(lli i=0;i<(n);i++)
#define inc(i,a,b) for(lli i=a;i<=b;i++)
#define dec(i,a,b) for(lli i=a;i>=b;i--)
#define fr2(i,n) for(int i=0;i<(n);i++)
#define inc2(i,a,b) for(int i=a;i<=b;i++)
#define dec2(i,a,b) for(int i=a;i>=b;i--)
#define ymin(a,b)  (a=min((a),(b)))
#define ymax(a,b)  (a=max((a),(b)))
#define sz(x) (lli)(x).size()
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr<< *it << " = " << a << endl;
	err(++it, args...);
}

typedef long long int lli;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<lli,lli> plli;
typedef vector<lli> vlli;
typedef vector<int> vi;
//typedef  vector<vector<lli> >ncr(1001,vector<lli>(1001,0))
typedef vector<plli> vplli;
long long MOD=1000000007;
#define addm(x,y) (x+y>=MOD? (x+y-MOD):(x+y))
lli dp[10010][2][2][101];
string L,R;
lli d;
lli getans(lli lev,lli tlo,lli thi,lli rem)
{
	if(lev>=R.length())
	{
		if(rem==0)
			return 1;
		else
			return 0;
	}
	if(dp[lev][tlo][thi][rem]!=-1)
		return dp[lev][tlo][thi][rem];
	lli blo=0;
	lli bhi=9;
	if(tlo)
		blo=L[lev]-'0';
	if(thi)
	{
		bhi=R[lev]-'0';
	}
	lli ans=0;
	for(lli i=blo;i<=bhi;i++)
	{
		lli ntlo=tlo;
		lli nthi=thi;
		if(i>L[lev]-'0')
			ntlo=0;
		if(i<R[lev]-'0')
			nthi=0;
		ans+=getans(lev+1,ntlo,nthi,(rem+i)%d);
		ans=ans%MOD;
	}
	return dp[lev][tlo][thi][rem]=ans;
}
void solve()
{
	L="1";
	cin>>R>>d;
	//reverse(all(R));
	
	reverse(all(L));

	//R=to_string(r);
	lli l1=L.length();
	lli l2=R.length();
	while(l1<l2)
	{
		L+='0';
		l1++;


	}

	reverse(all(L));
	//reverse(all(R));
	//cout<<L<<" "<<R<<endl;
	mset(dp,-1);
	//cout<<r.size()<<endl;
	lli p=getans(0,1,1,0);
	// for(lli i=0;i<2;i++)
	// {
	// 	for(lli j=0;j<2;j++)
	// 	{
	// 		for(lli k=0;k<2;k++)
	// 		{
	// 			for(lli ii=0;ii<d;ii++)
	// 			{
	// 				cout<<i<<" "<<j<<" "<<k<<" "<<ii<<" ";
	// 				cout<<dp[i][j][k][ii]<<endl;
	// 			}
	// 		}
	// 	}
	// }
	cout<<p<<endl;
}
int main()
{
	// 	#ifndef ONLINE_JUDGE
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	// #endif
	IOS
	// clock_t start,end;
	// start=clock();
	// int t;
	// cin>>t;
	// for(int i=1;i<=t;i++)
	// {
	// 	cout<<"Case #"<<i<<": ";
	// 	solve();

	// }
	
	
	// end=clock();
	
	// double time_taken=double(end-start)/double(CLOCKS_PER_SEC);
	// cout<<fixed<<setprecision(10)<<time_taken<<" sec"<<endl;
	
	solve();
}


Measured memory_bytes: 36056
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
use {
    proconio::{marker::*, *},
    std::{cmp::*, collections::*, mem::*},
};
fn main() {
    input! {//
        h:usize,
        w:usize,
        s:[[String;w];h],
    }

    for i in 0..h {
        for j in 0..w {
            if s[i][j] == "snuke" {
                println!("{}{}", ('A' as u8 + j as u8) as char, i + 1);
                return;
            }
        }
    }
}


Measured memory_bytes: 2192
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iterator>
#include<sstream>
#include<iomanip>
#include<map>
#include<queue>

#define rep(i, n) for (ll i = 0; i < n; i++) 
#define rrep(i, n) for(ll i = n-1; i>=0; i--)
#define range(i, n, m) for (ll i = n; i < m; i++) 
#define rrange(i, n, m) for (ll i = n - 1; i => m; i--) 
#define MOD 1000000007
//#define MOD 998244353

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

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

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

	string S;
	cin >> S;


	bool flgYM = false;
	bool flgMY = false;

	if (S[0] == '0' && S[1] != '0') {
		flgMY = true;
	}else if (S[0] == '1' && (S[1] == '0' || S[1] == '1' || S[1] == '2')) {
		flgMY = true;
	}

	if (S[2] == '0' && S[3] != '0') {
		flgYM = true;
	}else if (S[2] == '1' && (S[3] == '0' || S[3] == '1' || S[3] == '2')) {
		flgYM = true;
	}

	if (flgMY && flgYM) {
		cout << "AMBIGUOUS" << endl;
	}
	else if (flgMY) {
		cout << "MMYY" << endl;
	}
	else if (flgYM) {
		cout << "YYMM" << endl;
	}
	else {
		cout << "NA" << endl;
	}



	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
const double EPS=1e-10;
struct point{
	double x,y;
	point(const point&a):x(a.x),y(a.y){}
	point(const double&x=0,const double&y=0):x(x),y(y){}
	point operator+(const point&p)const{return point(x+p.x,y+p.y);}
	point operator-(const point&p)const{return point(x-p.x,y-p.y);}
	point operator*(const double&k)const{return point(x*k,y*k);}
	point operator/(const double&k)const{return point(x/k,y/k);}
	double norm(){return x*x+y*y;}
	double abs(){return sqrt(norm());}
	void operator=(const point&a){
		x=a.x,y=a.y;
	}
	bool operator<(const point&p)const{
		return x!=p.x?x<p.x:y<p.y;
	}
	bool operator==(const point&p)const{
		return fabs(x-p.x)<EPS&&fabs(y-p.y)<EPS;
	}
	friend double dot(const point&a,const point&b){
		return a.x*b.x+a.y*b.y;
	}
	friend double cross(const point&a,const point&b){
		return a.x*b.y-a.y*b.x;
	}
};
typedef point vector;
struct segment{
	point p1,p2;
	segment(const double&a,const double&b,const double&c,const double&d){
		p1.x=a,p1.y=b,p2.x=c,p2.y=d;
	}
	segment(const point&a, const point&b):p1(a),p2(b){}
	point get_vec()const{return point(p2.x-p1.x,p2.y-p1.y);}
};
bool orthogonal(const vector&a,const vector&b){
	return fabs(dot(a,b))<EPS;
}
bool orthogonal(const point&a,const point&b,const point&c,const point&d){
	return fabs(dot(a-b,c-d))<EPS;
}
bool orthogonal(const segment&a,const segment&b){
	return fabs(dot(a.get_vec(),b.get_vec()))<EPS;
}
bool parallel(const vector&a,const vector&b){
	return fabs(cross(a,b))<EPS;
}
bool parallel(const point&a,const point&b,const point&c,const point&d){
	return fabs(cross(a-b,c-d))<EPS;
}
bool parallel(const segment&a,const segment&b){
	return fabs(cross(a.get_vec(),b.get_vec()))<EPS;
}
point project(const segment&s,const point&p){
	vector base=s.get_vec();
	double r=dot(p-s.p1,base)/base.norm();
	return s.p1+base*r;
}
point reflect(const segment&s,const point&p){
	return p+(project(s,p)-p)*2.0;
}
int ccw(const point&a,const point&b,const point&c){
	vector t1=b-a;
	vector t2=c-a;
	if(cross(t1,t2)>EPS) return 1;
	if(cross(t1,t2)<-EPS) return -1;
	if(dot(t1,t2)<-EPS) return -2;
	if(t1.norm()<t2.norm()) return 2;
	return 0;
}
bool intersect(const point&a,const point&b,const point&c,const point&d){
	return ((ccw(a,b,c)*ccw(a,b,d))<=0&&(ccw(c,d,a)*ccw(c,d,b))<=0);
}
bool intersect(const segment&a,const segment&b){
	return intersect(a.p1,a.p2,b.p1,b.p2);
}
int main(){
	double a,b,c,d;
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a>>b>>c>>d;
		segment s1(a,b,c,d);
		cin>>a>>b>>c>>d;
		segment s2(a,b,c,d);
		if(intersect(s1,s2)) cout<<1<<endl;
		else cout<<0<<endl;
	}
	return 0;
}



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

using ll = long long;

int main(void){
  vector<int> stairs;
  int input;
  do{
    cin >> input;
    if(input!=0) stairs.push_back(input);
  }while(input!=0);

  rep(i,stairs.size()){
    int max_step = stairs[i];
    vector<int> dp(max_step+1,-10);
    if(max_step<=4){
      cout << "1" << endl;
      continue;
    }
    
    dp.at(max_step) = 1;
    dp[max_step-1] = 1;
    dp[max_step-2] = 2;
    dp[max_step-3] = 4;
    for(int j=max_step-2;j>=0;j--){
      if(j+3<=max_step) dp.at(j) = dp.at(j+1)+dp.at(j+2)+dp.at(j+3);
    }
    ll day = dp[0]/10;
    ll ans;
    if(day%365==0) ans = day/365;
    else ans = day/365+1;
    cout << ans << endl;
  }
  
  return 0;
}



Measured memory_bytes: 3152
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,d,temp;
  cin>>n>>d;
  d=2*d;
  temp=(int)(n/(d+1));
  if((n%(d+1))!=0)
    temp++;
  cout<<temp<<endl;
  return 0;
}

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

# [終点，始点]のリスト
coordinate = [[i[0] + i[1], max(i[0] - i[1], 0), ] for i in R]
coordinate.sort()

ans = 0
end_point = 0

for i in range(N):
    if end_point <= coordinate[i][1]:
        ans += 1
        end_point = coordinate[i][0]

print(ans)

Measured memory_bytes: 41440
N = gets.split('').map(&:to_i)

ans = N.inject(:+)
N.length.times do |i|
    next if N[i] == 0
    result = N[0, i].inject(0, :+)
    result += N[i] - 1
    result += 9 * (N.length - 2 - i)
    ans = result if ans < result
end
puts ans


Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int sum = 0;
  int data[6];
  for(int i = 0;i < 6;i++) {
    cin >> data[i];
    sum += data[i];
  }
  cout << sum - *min_element(data,data + 4) - *min_element(data + 4,data + 6) << endl;
  return 0;
}

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N; cin >> N;
  set<int> seen;
  bool b = true;
  for(int i =  0; i < N; i++){
    int v; cin >> v;
    if(seen.count(v) != 0) b = false;
    seen.insert(v);
  }
  if(b) cout << "YES" << endl;
  else cout << "NO"<< endl;
}


Measured memory_bytes: 9600
#include <stdio.h>

int main(void) {
  int i;
  char str[10000];

  fgets(str, sizeof(str), stdin);

  for (i = 0; str[i] != '\0'; i++)
    if ('a' <= str[i] && str[i] <= 'z')
      str[i] += 'A' - 'a';

  printf("%s", str);

  return 0;
}

Measured memory_bytes: 524
// abc161_c.cc
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
	ll n, k;
	set<ll> seen;
	cin >> n >> k;
	ll ans = LLONG_MAX;
	while (n >= 0 && seen.count(n) == 0) {
		ans = min(ans, n);
		seen.insert(n);
		if (n > k)
			n = n % k;
		else
			n = abs(n - k);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256