akhauriyash/Code-Regression huggingface dataset:
/*
 * main.c
 *
 *  Created on: 2019/12/29
 *      Author: family
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAX(a,b) (a > b ? a : b)
#define MIN(a,b) (a > b ? b : a)
typedef long long int ll;

int main()
{
	int a = 0, b = 0, i = 0;
	int A = 0, B = 0, j = 0;
	scanf("%d %d", &a, &b);
	j = 1;
	for (i = 1; i <= b; i++) {
		A += a*j;
		j *= 10;
	}
	j = 1;
	for (i = 1; i <= a; i++) {
		B += b*j;
		j *= 10;
	}
	printf("%d\n", MAX(A,B));
    return 0;
}


Measured memory_bytes: 128
#include <stdio.h>
#include <algorithm>
#define N 200010
int n,a[N];
long long ans=0;
int main() {
	scanf("%d",&n);
	for(int i=0;i<n;++i) {
		scanf("%d",a+i);a[i]-=i;
	}
	std::sort(a,a+n);
	int mid=n>>1;
	for(int i=0;i<mid;++i) ans+=a[mid]-a[i];
	for(int i=mid+1;i<n;++i) ans+=a[i]-a[mid];
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e9+7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
signed main() {
    int D;
    cin >> D;
    vector<int>c(26);
    for(int i = 0; i < 26; i++) {
        cin >> c[i];
    }
    vector<vector<int>>s(D,vector<int>(26));
    for(int i = 0; i < D; i++) {
        for(int j = 0; j < 26; j++) {
            cin >> s[i][j];
        }
    }
    vector<int>t(D);
    for(int i = 0; i < D; i++) {
        t[i] = rand()%26+1;
    }
    int ans = 0;
    vector<int>Last(26);
    for(int i = 0; i < D; i++) {
        ans+=s[i][t[i]-1];
        Last[t[i]-1] = i+1;
        for(int j = 0; j < 26; j++) {
            ans-=c[j]*(i+1-Last[j]);
        }
    }
    int M = 2700000;
    vector<P>horyuu;
    int cnt = 0;
    for(int i = 0; i < M; i++) {
        int d = rand()%D+1;
        int q = rand()%26+1;
        int ord = ans;
        int X = 0;
        int Y = 0;
        int A = 0;
        int B = 0;
        ans+=s[d-1][q-1]-s[d-1][t[d-1]-1];
        for(int j = 0; j < D; j++) {
            if(t[j] == t[d-1]) {
                if(j == d-1) {
                    Y = j+1;
                }
                else {
                    X = j+1;
                }
                A = j+1;
            }
            if(t[j] == q) {
                Y = j+1;
                B = j+1;
            }
            ans-=c[t[d-1]-1]*(j+1-X)-c[t[d-1]-1]*(j+1-A);
            ans+=c[q-1]*(j+1-B)-c[q-1]*(j+1-Y);
        }
        if(ans >= ord) {
            ord = ans;
            horyuu.push_back({d,q});
            cnt++;
        }
        else {
            ans = ord;
        }
        if(cnt == 3) {
            cnt = 0;
            t[horyuu[2].first-1] = horyuu[2].second;
            horyuu = {};
        }
    }
    for(int i = 0; i < D; i++) {
        cout << t[i] << "\n";
    }
}

Measured memory_bytes: 3724
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  
  for (int i = 0; i < N; i++) {
   
    string S;
    cin >> S;
    if ( i != N-1 && S != "Y") {
      continue;
    }
    if ( S == "Y") {
      cout << "Four" << endl;
     break;
    }
    if ( i == N-1 && S != "Y") {
      cout << "Three" << endl;
    }
  }
  
}

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

int main()
{
    ll N, K;
    cin >> N >> K;
    ll sum = 0;

    for (ll i = K; i <= N + 1; i++)
    {
        ll low = (i - 1) * i / 2;
        ll high = (2 * N + 1 - i) * i / 2;
        ll add = high - low + 1;
        sum = (sum + add) % MOD;
    }

    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    cin>>n;
    long long p,q,r,s;
    p=n%1000;
    q=1000-p;
    if(q!=1000)
        cout<<q<<endl;
    else
        cout<<"0"<<endl;
}


Measured memory_bytes: 3640
#include <stdio.h>

int main( void )
{
        while( 1 ) {
                int n ;
                scanf("%d", &n);
                if( !n ) break ;
                int A=0, B=0;
                for( int i = 0 ; i < n ; i++ ) {
                        int a, b ;
                        scanf("%d %d", &a, &b);
                        if( a > b ) A+=a+b;
                        else
                        if( a < b ) B+=a+b;
                        else {
                                A+=a;
                                B+=b;
                        }
                }
                printf("%d %d\n", A, B );
        }
        return 0;
}

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

#define INF 1145141919810364364

struct root {
	int from;
	int to;
	long long cost;
};

int main() {
	int N, M;
	long long Dis[1000] = {};
	root R[2000];
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> R[i].from >> R[i].to >> R[i].cost;
		R[i].from--;
		R[i].to--;
		R[i].cost = -R[i].cost;
	}
	for (int i = 1; i < N; i++) {
		Dis[i] = INF;
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (Dis[R[j].from] == INF) continue;
			Dis[R[j].to] = min(Dis[R[j].to], Dis[R[j].from] + R[j].cost);
		}
	}
	long long ans = Dis[N - 1] * -1;
	bool check[1000] = {};
	for (int i = 0; i < M; i++) {
		if (Dis[R[i].from] == INF) continue;
		if (Dis[R[i].to] > Dis[R[i].from] + R[i].cost) check[R[i].to] = true;
		if (check[R[i].from]) check[R[i].to] = true;
	}
	if (check[N - 1]) cout << "inf";
	else cout << ans;
}

Measured memory_bytes: 256
import json
k = int(input())
# 1
# 2
# 3
# 10

# assume_valid
# list of num ??
def next_lunlun(k):
    k[0] += 1
    for i in range(len(k) - 1):
        if k[i] < 10:
            break
        k[i] -= 10
        k[i+1] += 1

    if k[-1] >= 10:
        k[-1] -= 10
        k.append(1)

    for i in range(len(k)-1, 0, -1):
        if abs(k[i] - k[i-1]) <= 1:
            continue
        elif k[i] > k[i-1]:
            k[i-1] = k[i] - 1
            for j in range(i-2, -1, -1):
                k[j] = max(k[j + 1] - 1, 0)
            break
        else:
            pivot = len(k) - 1
            for j in range(i, len(k) - 1):
                if k[j + 1] > k[j] or (k[j] < 9 and k[j+1] == k[j]):
                    pivot = j
                    break
            if pivot == len(k) - 1 and k[-1] == 9:
                for j in range(len(k)):
                    k[j] = 0
                k.append(1)
            else:
                k[pivot] += 1
                for j in range(pivot-1, -1, -1):
                    k[j] = max(k[j+1] -1 , 0)
            break

    return k

i = [0]
for idx in range(k):
    next_lunlun(i)
base = 0
for num in reversed(i):
    base *= 10
    base += num
print(base)


Measured memory_bytes: 47580
N = int(input())
if N < 105:
  print(0)
elif 105 <= N < 135:
  print(1)
elif 135 <= N < 165:
  print(2)
elif 165 <= N < 189:
  print(3)
elif 189 <= N < 195:
  print(4)
else:
  print(5)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define era(t) t.erase(unique(be(t)),t.end())
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
typedef long long ll;
using namespace std;
const ll mod=1000000007,mod9=1000000009;
template <class T>inline T lcm(T a,T b){return (a*b/__gcd(a,b));}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    ll a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    ll x=a[0],y=a[1];
    vector<ll> vx,vy;
    for(int i=1;i*i<=x;i++){
        if(x%i==0){
            vx.pb(i);
            vx.pb(x/i);
        }
    }
    for(int i=1;i*i<=y;i++){
        if(y%i==0){
            vy.pb(i);
            vy.pb(y/i);
        }
    }
    ll ans=0;
    bool maki;
    for(int i=0;i<vx.size();i++){
        if(vx[i]>ans){
        maki=false;
        for(int j=0;j<n;j++){
            if(a[j]%vx[i]){
                if(maki){
                    break;
                }
                else{
                    maki=true;
                }
            }
            if(j==n-1){
                ans=max(ans,vx[i]);
            }
        }
        }
    }
    for(int i=0;i<vy.size();i++){
        if(vy[i]>ans){
        maki=false;
        for(int j=0;j<n;j++){
            if(a[j]%vy[i]){
                if(maki){
                    j=n;
                }
                else{
                    maki=true;
                }
            }
            if(j==n-1){
                ans=max(ans,vy[i]);
            }
        }
        }
    }
    cout << ans<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <tuple>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

int main()
{
    int SX, SY, TX, TY;
    scanf("%d %d %d %d\n", &SX, &SY, &TX, &TY);
    for (int y = 0; y < TY - SY; ++y) putchar('U');
    for (int x = 0; x < TX - SX; ++x) putchar('R');
    for (int y = 0; y < TY - SY; ++y) putchar('D');
    for (int x = 0; x < TX - SX; ++x) putchar('L');
    putchar('L');
    for (int y = 0; y < TY - SY + 1; ++y) putchar('U');
    for (int x = 0; x < TX - SX + 1; ++x) putchar('R');
    putchar('D');
    putchar('R');
    for (int y = 0; y < TY - SY + 1; ++y) putchar('D');
    for (int x = 0; x < TX - SX + 1; ++x) putchar('L');
    putchar('U');
    puts("");
}


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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,a,b) for(int i=a;i<b;i++)
#define each(it,v) for(auto it : v)
#define mod 1000000007
#define All(v) (v).begin(),(v).end()
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define vpii vector<pair<int,int>>
#define vv vector<vector<int>>
template<class T> T gcd(T a,T b) {return b?gcd(b,a%b):a;}
template<class T> T lcm(T a,T b) {return a/gcd(a,b)*b; }
template<class T> bool isPrime(T num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    double sqrtNum = sqrt(num);
    for (T i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}

using namespace std;

int a,b,c;
int n,m,h,cnt,ans;
string s,t;

main()
{
        double h,a;
        cin>>h>>a;
        cout<<ceil(h/a)<<endl;
}

Measured memory_bytes: 256
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
delta = [(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1)]
for y in range(h):
    for x in range(w):
        if s[y][x] == ".":
            cnt = 0
            for dx,dy in delta:
                if 0 <= x+dx < w and 0 <= y+dy < h and s[y+dy][x+dx] == "#":
                        cnt += 1
            s[y][x] = str(cnt)
for i in s:
    print("".join(i))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
const int MAX=1e6+10;
const int modn=1e9+7;
typedef long long ll ;
using namespace std;
int main() {
    ll x,k,d;
    cin>>x>>k>>d;
    ll cnt=abs(x)/d;
    if(k<cnt){
        cout<<abs(x)-d*k;
    }else {
        ll now = abs(x) - cnt * d;
        k -= cnt;
        k %= 2;
        if (k == 0) cout << now;
        else cout << d - now;
    }
    return 0;
}

Measured memory_bytes: 3588
#include "bits/stdc++.h"

using namespace std;

template<typename T = int>
class cumulative_sum_2d {
private:
    std::vector<std::vector<T>> vec;
    std::vector<std::vector<T>> sum;
    bool invalid;
    int H, W;
public:
    cumulative_sum_2d() {invalid = true;}
    cumulative_sum_2d(const std::vector<std::vector<T>> &v) {
        init(v);
    }
    void init() {
        vec.clear();
        sum.clear();
        H = W = -1;
        invalid = true;
    }
    void init(const std::vector<std::vector<T>> &v) {
        init();
        invalid = false;
        H = v.size();
        W = v.front().size();
        std::copy(v.begin(), v.end(), std::back_inserter(vec));
        sum.resize(H + 1, std::vector<T>(W + 1, 0));
    }
    bool calc_sum() {
        if (invalid) {
            return false;
        }
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                sum[i + 1][j + 1] = vec[i][j];
            }
        }
        for (int i = 0; i < H + 1; i++) {
            for (int j = 0; j < W; j++) {
                sum[i][j + 1] += sum[i][j];
            }
        }
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W + 1; j++) {
                sum[i + 1][j] += sum[i][j];
            }
        }
        return true;
    }
    // [p1, p2)
    T get_sum(std::pair<int, int> p1, std::pair<int, int> p2) {
        if (invalid) return 0;
        int h1, w1, h2, w2;
        std::tie(h1, w1) = p1; std::tie(h2, w2) = p2;
        h2--; w2--;
        return sum[h2 + 1][w2 + 1] - sum[h2 + 1][w1] - sum[h1][w2 + 1] + sum[h1][w1];
    }
    T get_sum(int x1, int y1, int x2, int y2) {
        return this->get_sum(std::make_pair(x1, y1), std::make_pair(x2, y2));
    }
    std::vector<std::vector<T>> get_sum_vec() {return sum;}
};

const int MAX = 2e5 + 10;
int N, M, Q;
int L[MAX], R[MAX], p[MAX], q[MAX];
cumulative_sum_2d<int> sum;

void naive() {
    for (int i = 0; i < Q; i++) {
        int ans = 0;
        for (int j = 0; j < M; j++) {
            if (p[i] <= L[j] && R[j] <= q[i]) {
                ans++;
            }
        }
        cout << ans << endl;
    }
}

int main() {
    cin >> N >> M >> Q;
    vector<vector<int>> vec(N, vector<int>(N));
    for (int i = 0; i < M; i++) {
        cin >> L[i] >> R[i];
        L[i]--;R[i]--;
        vec[L[i]][R[i]]++;
    }
    for (int i = 0; i < Q; i++) {
        cin >> p[i] >> q[i];
        p[i]--;q[i]--;
    }
    //naive();
    sum.init(vec);
    sum.calc_sum();
    for (int i = 0; i < Q; i++) {
        cout << sum.get_sum(p[i], p[i], q[i] + 1, q[i] + 1) << endl;
    }
}


Measured memory_bytes: 6272
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)

void solve() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<string> s(n + 1);
  vector<int> t(n + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> s[i] >> t[i];
  }
  int sum = 0;
  string ed;
  cin >> ed;
  for (int i = n; i >= 1; --i) {
    if (s[i] == ed) break;
    sum += t[i];
  }
  cout << sum << endl;
}

int main() {
  solve();
  return 0;
}


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

using namespace std;

int main(){
vector<int> vec(3); cin >> vec[0] >> vec[1] >> vec[2];
   int cnt = 0;
  sort(vec.begin(),vec.end()); 
  
  int Z = vec[0]; int Y = vec[1]; int X = vec[2];
  
  cnt += X - Y; Z = Z + X - Y;
  if( (X - Z) % 2 == 0 ){ cnt += ( X - Z ) / 2; }
  else{
    cnt++; X++; cnt += (X - Z) / 2;} 
  cout << cnt << endl; return 0;}


Measured memory_bytes: 256
//
// Created by 宇都宮健太 on 2019-08-03.
//

#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>

using namespace std;

typedef long long ll;

int main() {
    int N, W;
    cin >> N >> W;
    auto dp = vector<ll>(100000 + 10, LONG_MAX / 2);
    dp[0] = 0;
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int w;
        ll v;
        cin >> w >> v;
        for (int j = dp.size() - 1; j >= 0; j--) {
            if (j - v >= 0) {
                dp[j] = min(dp[j - v] + w, dp[j]);
            }
            if (j < dp.size() - 1) {
                dp[j] = min(dp[j], dp[j + 1]);
            }
        }
    }
    const auto upper = upper_bound(dp.begin(), dp.end(), W);
    cout <<  (upper - dp.begin()) - 1 << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const int inf = 5000;
int main(void){
    // Your code here!
    int h,w;cin>>h>>w;
    int g = 0;
    char d[h][w];
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>d[i][j];
            if(d[i][j]=='#')g++;
        }
    }
    int t[h][w];
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++)t[i][j]=inf;
    }
    t[0][0]=0;
    queue<pair<int,int>> que;
    que.push(make_pair(0,0));
    int roty[4]={1,0,-1,0},rotx[4]={0,1,0,-1};
    while(que.size()>0){
        pair<int,int> p=que.front();
        que.pop();
        int y=p.first,x=p.second;
        if(y==h-1&&x==w-1)break;
        for(int i=0;i<4;i++){
            int ny=y+roty[i],nx=x+rotx[i];
            if(0<=ny&&ny<h&&0<=nx&&nx<w&&d[ny][nx]=='.'&&t[ny][nx]==inf){
                que.push(make_pair(ny,nx));
                t[ny][nx]=t[y][x]+1;
            }
        }
    }
    if(t[h-1][w-1]==inf){
        cout<<"-1"<<endl;
        return 0;
    }
    int res = h*w-g-1,b=t[h-1][w-1];
    res-=b;
    cout<<res<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    ll a, b, c;
    cin >> a >> b >> c;
    if (a == b) {
        cout << c << endl;
        return 0;
    } else if (b == c) {
        cout << a << endl;
        return 0;
    } else {
        cout << b << endl;
        return 0;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i=0;i<n;i++)
#define IREP(i,n) for(ll i=1;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define DEBUG(x) cerr << x << "\n"

int main(){
    int n;
    string s;
    cin >> n >> s;
    vector<int> must = {0};
    for(int i=1;i<n;i++){
        if(s[i]=='E') must[0]++;
    }
    for(int i=1;i<n;i++){
        must.push_back(must[i-1]);
        if(s[i-1]=='W') must[i]++;
        if(s[i]=='E') must[i]--;
    }
    sort(must.begin(),must.end());
    cout << must[0] << "\n";

    return 0;
}


Measured memory_bytes: 2812
n = int(input())


x = list(map(int,input().split())) 
for i in range(n-1):
    t,a = map(int,input().split())
    if x[0]%t==0 and x[1]%a==0:
        k = max(x[0]//t,x[1]//a)
    elif x[0]%t==0:
        k = max(x[0]//t,x[1]//a+1)
    elif x[1]%a==0:
        k = max(x[0]//t+1,x[1]//a)
    else:
        k = max(x[0]//t,x[1]//a)+1
    x = [t*k,a*k]

print(sum(x))


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



int main()
{


        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
   
    int t=1;
    while(t--)
    {
      long long int a,b,c;
       cin>>a>>b>>c;
       cout<<c<<" "<<a<<" "<<b<<endl; 
    }

return 0;

}

Measured memory_bytes: 256
def dfs(n):
    if n not in memo:
        ans = min(n*d, min(dfs(n//2),dfs((n+1)//2)) + a + d*(n % 2))
        if n % 3 <= 1:
            ans = min(ans, dfs(n//3) + b + d*(n % 3))
        else:
            ans = min(ans, dfs((n+2)//3) + b + d*(3 - n % 3))
        if n % 5 <= 2:
            ans = min(ans, dfs(n//5) + c + d*(n % 5))
        else:
            ans = min(ans, dfs((n+4)//5) + c + d*(5 - n % 5))
        memo[n] = ans
    return memo[n]


t = int(input())

for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    memo = {0: 0, 1: d}
    print(dfs(n))


Measured memory_bytes: 98004
N = int(input())
S = input()

black = S.count('#')
white = S.count('.')

ans = white
prev_black = 0
for i in range(N):
    if(S[i] == '.'):
        white -= 1
    else:
        prev_black += 1
    ans = min(white + prev_black, ans)

print(ans)

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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Abs(a,b) max(a,b)-min(a,b)
#define YES(condition) if(condition){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(condition) if(condition){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define Cout(x) cout<<(x)<<endl
#define POSSIBLE(condition) if(condition){cout << "POSSIBLE" << endl;}else{cout << "IMPOSSIBLE" << endl;}
#define Possible(condition) if(condition){cout << "Possible" << endl;}else{cout << "Impossible" << endl;}
#define possible(condition) if(condition){cout << "possible" << endl;}else{cout << "impossible" << endl;}
#define Size(n) (n).size()

typedef long long ll;


using namespace std;

const int INF = 1e9,MOD = 1e9 + 7,ohara = 1e6;
const ll LINF = 1e18;


long long int n,cnt=0,ans=0,a,b,c,d,cmp,cmpp,m,h,w,x,y,sum=0,pos;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl=true;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

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

      
      cin>>a>>b>>x;
      if(b%x==0)ans=1;
      else{
        b+=x-(b%x);
      }
      ans+=(b-a)/x;
      Cout(ans);

     

       
return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 

ll n,cnt,ans,a,b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

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

    cin>>s;
    rep(i,Size(s)){
        if(i%2==0){
            if(s[i]!='0')tmp++;
            if(s[i]!='1')tmpp++;
        }
        else{
            if(s[i]!='0')tmpp++;
            if(s[i]!='1')tmp++;
        }
    }
    Cout(min(tmp,tmpp));
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

struct Graph {
    struct Vertex { int n, d; };
    struct Edge { int i, n; };
    Graph(int n, int m) : v(n, { -1, -1 }), e(m), q(n), n(n), m(0) {}
    void add_edge(int i, int j) {
        e[m] = { j, v[i].n };
        v[i].n = m;
        m++;
    }
    void bfs(int i0, int i1) {
        for (int i = 0; i < n; i++) {
            v[i].d = -1;
        }
        v[i0].d = 0;

        int j0 = 0, j1 = 0;
        q[j1++] = i0;

        while (j0 < j1) {
            int i = q[j0++];
            for (int j = v[i].n; j >= 0; j = e[j].n) {
                Edge &o = e[j];
                if (v[o.i].d >= 0) continue;

                v[o.i].d = v[i].d + 1;
                if (o.i == i1) return;
                q[j1++] = o.i;
            }
        }
    }
    vector<Vertex> v;
    vector<Edge> e;
    vector<int> q;
    int n, m;
};

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

    int n, m;
    cin >> n >> m;

    Graph g(n * 3, m * 3);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;

        for (int j = 0; j < 3; j++) {
            g.add_edge(a * 3 + j, b * 3 + (j + 1) % 3);
        }
    }

    int s, t;
    cin >> s >> t;
    s--; t--;

    g.bfs(s * 3, t * 3);

    int r = g.v[t * 3].d;

    cout << (r < 0 ? -1 : r / 3) << endl;

    return 0;
}

Measured memory_bytes: 6144
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =1e5+100;
const int MOD = 1e9+7;
int fpow(int x,int p){
    int rs=1;
    while(p){
        if(p&1) rs=1LL*rs*x%MOD;
        x=1LL*x*x%MOD; p>>=1;
    }
    return rs;
}
int C(int n,int m){
    int f=1,g=1;
    for(int i=n;i>n-m;--i) f=1LL*f*i%MOD;
    for(int i=m;i>=1;--i) g=1LL*g*i%MOD;
    return 1LL*f*fpow(g,MOD-2)%MOD;
}

int n,a,b,ans;
int main(){
    scanf("%d %d %d",&n,&a,&b);
    ans=(fpow(2,n)-1+MOD)%MOD;
    ans=(ans-C(n,a)+MOD)%MOD;
    ans=(ans-C(n,b)+MOD)%MOD;
    printf("%d\n",ans);
}


Measured memory_bytes: 256
// AOJ 2412: Village
// 2017.12.8 bal4u@uu

#include <stdio.h>
#include <stdlib.h>

#define HASHSIZ 3000017
typedef struct { unsigned long long t; } HASH;
HASH hash[HASHSIZ+2], *hashend = hash+HASHSIZ;

void insert(int x, int y)
{
	unsigned long long t = ((unsigned long long)x << 32) | y;
	HASH *p = hash + (int)(t % HASHSIZ);

	while (p->t) {
		if (p->t == t) return;
		if (++p == hashend) p = hash;
	}
	p->t = t;
}

int lookup(int x, int y)
{
	unsigned long long t = ((unsigned long long)x << 32) | y;
	HASH *p = hash + (int)(t % HASHSIZ);

	while (p->t) {
		if (p->t == t) return 1;
		if (++p == hashend) p = hash;
	}
	return 0;
}

#define BASE 1000000000
int ans;
char buf[30], *p;

int getdbl()
{
	int minus = 0;
	int n = 0;

	if (*p == '-') minus = 1, p++;
	while (*p >= '0') n = 10*n + (*p++ & 0xf);
	n *= 1000;
	if (*p == '.') {
		p++;
		if (*p >= '0') n += (*p++ & 0xf) * 100;
		if (*p >= '0') n += (*p++ & 0xf) * 10;
		if (*p >= '0') n += (*p++ & 0xf);
	}
	p++;
	if (minus) n = -n;
	return n;
}

int main()
{
	int n, r, x0, y0, x, y, i, j;

	fgets(p=buf, 30, stdin);
	n = atoi(p); while (*p >= '0') p++; p++;
	r = getdbl();
	while (n--) {
		fgets(p=buf, 30, stdin);
		x0 = getdbl(), y0 = getdbl();
		if (x0 < 0) x = (x0+1)/r-1; else x = x0/r;
		if (y0 < 0) y = (y0+1)/r-1; else y = y0/r;

		for (i = x-1; i <= x+1; i++) for (j = y-1; j <= y+1; j++) {
			if (lookup(i+BASE, j+BASE)) goto next;
		}
		ans++, insert(x+BASE, y+BASE);
next:;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 25192
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

//Data Conversion
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			if(n==0)break;
			Map<String, String> map = new HashMap<String, String>();
			while(n--!=0){
				map.put(sc.next(), sc.next());
			}
			int m = sc.nextInt();
			StringBuilder sb = new StringBuilder();
			while(m--!=0){
				String s = sc.next();
				if(map.containsKey(s))sb.append(map.get(s));
				else sb.append(s);
			}
			System.out.println(sb.toString());
		}
	}
}

Measured memory_bytes: 13000
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define i_7 (ll)(1E9+7)
#define i_5 (ll)(1E9+5)
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    else return c+i_7;
}
typedef pair<int,int> i_i;
typedef pair<ll,ll> l_l;
ll inf=(ll)1E12;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll * pos,ll val){*pos=max(*pos,val);}//Max(&dp[i][j],dp[i-1][j]);
void Min(ll * pos,ll val){*pos=min(*pos,val);}
void Add(ll * pos,ll val){*pos=mod(*pos+val);}
// long double EPS=1E-8;
////////////////////////////////////////

bool comp(l_l a,l_l b){
    if(a.first<b.first)return true;
    else if(a.first==b.first&&a.second>b.second)return true;
    else return false;
}

bool comp2(l_l a,l_l b){
    if(a.second>b.second)return true;
    else return false;
}


int main() {
    ll n,k;cin>>n>>k;
    vector<l_l> a;
    rep(i,0,n-1){
        l_l aa;
        cin>>aa.first>>aa.second;
        a.pb(aa);
    }
    sort(a.begin(),a.end(),comp);
    vector<l_l>b,c;
    for(ll i=n-1;i>=0;i--){
        if(i==0){
            b.pb(a[i]);
        }else if(a[i-1].first==a[i].first){
            c.pb(a[i]);
        }else{
            b.pb(a[i]);
        }
    }
    sort(b.begin(),b.end(),comp2);sort(c.begin(),c.end(),comp2);
    ll bs=b.size(),cs=c.size();
   // rep(i,0,bs-1)cout<<b[i].first<<" "<<b[i].second<<endl;cout<<endl;
   // rep(i,0,cs-1)cout<<c[i].first<<" "<<c[i].second<<endl;cout<<endl;
    ll x[bs],y[cs];
    if(b.size()){
        x[0]=b[0].second;
        rep(i,1,bs-1)x[i]=x[i-1]+b[i].second;
    }
    if(c.size()){
        y[0]=c[0].second;
        rep(i,1,cs-1)y[i]=y[i-1]+c[i].second;
    }
    ll ans=0;
  //  rep(i,0,bs-1)cout<<x[i]<<" ";cout<<endl;
  //  rep(i,0,cs-1)cout<<y[i]<<" ";cout<<endl;
    for(ll i=1;i<=bs&&i<=k;i++){
        if(i+cs<k)continue;
        ll sum=i*i;
        if(k-i-1<0)sum+=x[i-1];
        else sum+=x[i-1]+y[k-i-1];
    //cout<<i<<" "<<sum<<endl;
        Max(&ans,sum);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 5488
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	//	"strings"
)

func main() {
	sc := NewScanner()

	n := sc.NextInt()
	if n == 0 {
		fmt.Printf("%+v\n", 0) // output for debug
		return
	}
	ans := ""
	for {
		if n == 0 {
			break
		}
		//		fmt.Printf("%d / 2 = %d..%+v\n", n, n/2, n%(-2)) // output for debug
		if n%(-2) == 0 {
			ans = "0" + ans
			n /= -2
		} else {
			ans = "1" + ans
			n -= 1
			n /= -2
		}
	}
	fmt.Printf("%v\n", ans)

}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			result = append(result, v)
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	result = append(result, v)

	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
	private static Scanner sc;

	public static void main(String[] args) throws Exception {
		sc = new Scanner(System.in);
		int[] ary = new int[5];

		for (int i = 0; i < ary.length; i++) {
			ary[i] = sc.nextInt();
		}

		int k = sc.nextInt();

		boolean yay = true;

		loop: for (int i : ary) {
			for (int j : ary) {
				if (!(i - j <= k)) {
					yay = false;
					break loop;
				}
			}
		}

		System.out.println(yay ? "Yay!" : ":(");

	}
}


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

int main(){
    int n,temp;
    cin>>n;
    int a[n];

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

    int cnt=0;
    for (int i=0; i<n-1; i++){
        for (int j=0; j<n-i-1; j++){
            if (a[j]>a[j+1]){
            temp= a[j];
            a[j]=a[j+1];
            a[j+1]=temp;
            cnt++;
           }
        }
    }

    cout<<a[0];
    for(int i=1; i<n; i++){
        cout<<" "<<a[i];
    }
    cout<<endl<<cnt<<endl;

    return 0;
}




Measured memory_bytes: 3096
# coding: utf-8
# Your code here!
N,K,S=map(int,input().split())
ans=[]
p=N-K

if S!=10**9:
    for i in range(N-K):
        ans.append(str(S+1))
    for i in range(K):
        ans.append(str(S))
else:
    for i in range(N-K):
        ans.append(str(1))
    for i in range(K):
        ans.append(str(S))
#print(ans)
#ans=' '.join(ans)

#print(len(ans))


#print(" ".join([str(n) for n in ans]))
print(*ans)

Measured memory_bytes: 55712
#include<iostream>
#include<string>

using namespace std;

int main() {
	string S, T;
	int flag = 0;
	cin >> S;
	cin >> T;

	for (int i = 0; i < S.size(); i++) {
		if (S[i] == T[i]) {
			flag++;
		}
	}

	if (S.size() + 1 == T.size() && flag==S.size()) {

		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}


	return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

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

const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
const double eps=1e-10;

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

int main(){
    int n, m; cin>>n>>m;
    int lma = 0;
    int rmi = n;
    for(int i=0; i<m; i++){
        int l, r; cin>>l>>r;
        lma = max(lma, l);
        rmi = min(rmi, r);
    }

    cout << max(rmi - lma + 1, 0) << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int MAX_N = 1e5 + 5;
const int MAX_L = 20; // ~ Log N
const long long MOD = 1e9 + 7;
const long long INF = 1e9 + 7;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;

#define LSOne(S) (S & (-S))
#define isBitSet(S, i) ((S >> i) & 1)
#define endl '\n'
#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back
#define mm(X) memset((X), 0, sizeof((X)))
#define deb(x) cout<<#x<<" "<<x<<endl;



void solve() {
	int n, k;
	cin >> n >> k;
	int a[n];
	rep(i, 0, n) cin >> a[i];
	int dp[n];
	dp[n - 1] = 0;
	for (int i = n - 2; i >= 0; i--) {
		int temp = INT_MAX;
		for (int j = i + 1; j < n && j <= i + k; j++) {
			temp = min(abs(a[i] - a[j]) + dp[j], temp);
		}
		dp[i] = temp;
	}
	cout << dp[0];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	// int tc; cin >> tc;
	// for (int t = 1; t <= tc; t++) {
	//cout << "Case #" << t  << ": ";
	solve();
	// }
}

Measured memory_bytes: 4360
import java.util.Scanner;

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

    int N = scanner.nextInt();
    double[] p = new double[N + 1];
    for (int i = 1; i <= N; i++) p[i] = scanner.nextDouble();

    double[][] dp = new double[N + 1][N + 1];
    dp[0][0] = 1.d;
    for (int i = 1; i <= N; i++) {
      for (int j = 0; j <= i; j++) {
        dp[i][j] = dp[i - 1][j] * (1 - p[i]);
        if (j > 0) dp[i][j] += dp[i - 1][j - 1] * p[i];
      }
    }
    double res = 0.d;
    for (int i = N / 2 + 1; i <= N; i++) res += dp[N][i];
    System.out.println(res);
  }
}


Measured memory_bytes: 123932
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a); i<ll(b); i++)
#define rer(i,a,b) for(ll i=ll(a)-1; i>=ll(b); i--)

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
__int128_t ppow(__int128_t x, ll y){
    if(y==0) return 1;
    __int128_t res=ppow(x*x, y/2);
    if(y%2==1) res=res*x;
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    for(;;){
        ll n;
        cin>>n;
        if(n==0) break;
        int keta=2;
        __int128_t res=0;
        while(res+36*(ppow(2,keta)-2)+9*(ppow(2,keta-1)-1)<n){
            res+=36*(ppow(2,keta)-2)+9*(ppow(2,keta-1)-1);
            keta++;
        }
        int cur=1;
        while(res+9*(ppow(2,keta-1)-1)<n){
            res+=9*(ppow(2,keta-1)-1);
            cur++;
        }
        bool t=false;
        cout<<cur;
        int nex;
        vector<int> ans;
        rep(i,0,keta-1){
            if(t){
                if(cur>nex) swap(cur, nex);
                n=n-res-1;
                rer(j,keta-i-1,0){
                    if(n&(ll(1)<<j)) cout<<nex;
                    else cout<<cur;
                }
                break;
            }
            else{
                nex=0;
                while(nex<10){
                    if(cur!=nex){
                        if(res+ppow(2,keta-i-2)<n){
                            nex++;
                            res+=ppow(2,keta-i-2);
                        }
                        else break;
                    }
                    else{
                        if(res+9*(ppow(2,keta-i-2)-1)<n){
                            nex++;
                            res+=9*(ppow(2,keta-i-2)-1);
                        }
                        else break;
                    }
                }
                if(cur!=nex) t=true;
                cout<<nex;
            }
        }
        cout<<"\n";
    }
}


Measured memory_bytes: 3180
def match(x, y):
    return x == y or x == '?' or y == '?'


def check(s, t):
    ANS = [1] * (10 ** 5)
    S = len(s); T = len(t)
    for i in range(S):
        for j in range(T):
            if not match(s[i], t[j]):
                ANS[i - j + 50000] = 0
    return ANS


def solve(a, b, c):
    lenA = len(a)
    lenB = len(b)
    lenC = len(c)

    AB = check(a, b)
    AC = check(a, c)
    BC = check(b, c)

    ans = lenA + lenB + lenC
    for i in range(-lenB, lenA + lenB + 1):
        for j in range(-lenC, lenA + lenC + 1):
            if AB[i + 50000] and AC[j + 50000] and BC[j - i + 50000]:
                L = min(0, min(i, j))
                R = max(lenA, max(lenB + i, lenC + j))
                ans = min(ans, R - L)

    return ans


a = input()
b = input()
c = input()


ans = min(solve(a, b, c), min(solve(b, c, a), solve(c, a, b)))

print(ans)


Measured memory_bytes: 58460
n = int(input())

mx = [0, 0]
for i in range(1, n+1):
    j = i
    cnt = 0
    while j % 2 == 0:
        cnt += 1
        j = j // 2
    if mx[0] < cnt:
        mx[0] = cnt
        mx[1] = i

print(mx[1] if mx[0] != 0 else 1)

Measured memory_bytes: 38384
// AGC  C

#include <bits/stdc++.h>

using namespace std;

#define ge getchar()
#define Re read()

inline int read() {
	int x = 0, ch;
	while(!isdigit(ch = ge)) ;
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = ge;
	return x;
}

const int MAXN = 200100;
const int MAXV = 1000100;
const int mod = 998244353;

inline void Add(int&x, int y) { x += y, x -= x >= mod ? mod : 0; }
inline int Mod(int x) { return x >= mod ? x - mod : x; }

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

int a_1[MAXV + 1];
int a_2[MAXV + 1];
int f_d[MAXV + 1];

int tot;
int pri[MAXV + 1];
int miu[MAXV + 1];
int inv[MAXV + 1];
int chk[MAXV + 1];
int F[MAXV + 1];

inline int init(int mx) {
	inv[1] = 1, miu[1] = 1;
	for(int i = 2; i <= mx; i++) {
		inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
		if(!chk[i]) pri[++tot] = i, miu[i] = mod - 1;
		for(int j = 1; j <= tot; j++) {
			if(i * pri[j] > mx) break;
			chk[i * pri[j]] = 1;
			if(i % pri[j] == 0) break;
			miu[i * pri[j]] = mod - miu[i];
		}
	}
	for(int i = 1; i <= mx; i++) {
		for(int j = i << 1; j <= mx; j += i)
			Add(a_1[i], a_1[j]), Add(a_2[i], a_2[j]);
		f_d[i] = 1LL * (1LL * a_1[i] * a_1[i] - a_2[i] + mod) % mod * inv[2] % mod;
	}
}

int main() {
	int n = Re, N = 0;
	for(int i = 1; i <= n; i++) {
		int v = Re;
		chkmax(N, v); Add(a_1[v], v);
		Add(a_2[v], 1LL * v * v % mod);
	} init(N); int res = 0;
	for(int d = 1; d <= N; d++) {
		for(int T = d, t = 1; T <= N; T += d, ++t) {
			Add(res, 1LL * inv[d] * miu[t] % mod * f_d[T] % mod);
		}
	} printf("%d\n", res);
	return 0;
}

Measured memory_bytes: 27520
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);

	int N=in();
	ll W=in<ll>();
	vector<pair<ll,ll>> P(N);
	REP(i,N){
		P[i].first=in<ll>();
		P[i].second=in<ll>();
	}

	ll H=N/2;
	ll PH=1LL<<H;
	vector<pair<ll,ll>> S(PH);
	REP(i,PH){
		ll v=i;
		ll val=0,weight=0,index=0;
		while(v){
			if(v&1){
				weight += P[index].second;
				val += P[index].first;
			}
			v>>=1LL;
			index++;
		}
		S[i]=make_pair(val,weight);
	}
	sort(ALL(S),[](pair<ll,ll>& l,pair<ll,ll>& r){return l.second==r.second?l.first<r.first:l.second<r.second;});
	vector<pair<ll,ll>> R;
	R.emplace_back(S[0]);
	ll current = R[0].first;
	for(int i=1;i<PH;i++){
		if(S[i].first>current){
			R.emplace_back(S[i]);
			current = S[i].first;
		}
	}

	ll ans=0;
	ll F=1LL<<(N-H);
	REP(i,F){
		ll v=i;
		ll val=0,weight=0,index=0;
		while(v){
			if(v&1){
				weight += P[H+index].second;
				val += P[H+index].first;
			}
			v>>=1LL;
			index++;
		}
		auto res = upper_bound(ALL(R),make_pair(0,W-weight),PAIRCOMP(second,<));
		if(res!=R.begin()){
			ans = max(ans,(res-1)->first+val);
		}
	}
	out(ans);
	return 0;
}


Measured memory_bytes: 19352
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <iomanip>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;


#define rep(i,n) for (int i=0; i<(n); i++)
const int INF =2*1e5+5;
const ll BIG = 1e9+7;
const double PI = 3.141592653589793;

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> accept(n);
    vector<int> wa(n);
    int wa_sum=0, ac_sum=0;
    rep(i,m) {
        int pi;
        string result;
        cin >> pi >> result;
        pi--;
        if(result=="AC"){
            if(accept[pi]==0){
                accept[pi] = 1;
                wa_sum += wa[pi];
                ac_sum++;
            }else{
                continue;
            }
        }
        else{
            if(accept[pi]==0){
                wa[pi]++;
            }else{
                continue;
            }            
        }
    }
    cout << ac_sum << " " << wa_sum << endl;
    return 0;
}

Measured memory_bytes: 4048
import sys
input = sys.stdin.readline
N = int(input())
even = [2, 10, 3, 9, 4, 8, 6, 12]
odd = [6, 2, 10, 3, 9, 4, 8, 12]
if N == 3:
  print("2 5 63")
  exit(0)
res = []
for i in range(N):
  x = i % 8
  y = i // 8
  if N % 2:
    res.append(odd[x] + 12 * y)
  else:
    res.append(even[x] + 12 * y)
print(*res)

Measured memory_bytes: 41456
#include <iostream>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <list>
#include <math.h>
#include <map>
using namespace std;
#define REP(i, k, n) for(int i = k;i < n; i++)
#define rep(i, n) REP(i,0,n)
#define ll long long int
int dx[4] = {0,-1,1,0};
int dy[4] = {-1,0,0,1};
#define eps 10e-6
#define mod 1000000007
int _par[100001];;
int _rank[100001];
void init(int n) {
	for (int i = 0; i < n; i++) {
		_par[i] = i;
		_rank[i] = 0;
	}
}

int find(int x) {
	if (_par[x] == x) {
		return x;
	} else {
		return _par[x] = find(_par[x]);
	}
}

void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return;
	if (_rank[x] < _rank[y]) {
		_par[x] = y;
	} else {
		_par[y] = x;
		if (_rank[x] == _rank[y])_rank[x]++;
	}
}
bool same(int x, int y) {
	return find(x) == find(y);
}

int main(void){
	int N, M;
	cin >> N >> M;
	init(N);
	int p[100001];
	rep(i,N){
		cin >> p[i+1];
	}
	rep(i,M){
		int x,y;
		cin >> x >> y;
		unite(p[x],p[y]);
	}
	int ans = N;
	for(int i = 1; i <= N; i++){
		if(!same(p[i], p[p[i]])){
			ans--;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 1408
#include <algorithm>
#include<stdio.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stack>
#include <queue>
#include <deque>     
#include<map>
#include <set>
#include<math.h>
using namespace std;
#define int long long
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define Rep(i,n) for(ll i=1;i<=n;++i)
#define loop(i,m,n) for(ll i=m;i<n;++i)
#define ggr getchar(); getchar();return 0;
#define pie 3.141592653589793238462643383279
#define elif else if
#define P pair<ll,ll>
#define prique priority_queue<ll>
#define all(a)  (a).begin(),(a).end()
const int mod = 1000000007;
const int mod2 = 998244353;
int bin(int bina) {
	int ans = 0;
	for (int i = 0; bina > 0; i++)
	{
		ans = ans + (bina % 2) * pow(10, i);
		bina = bina / 2;
	}
	return ans;
}
bool prime(int n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x,y)* mod_pow(kai(y,y), mod - 2, mod) % mod;
}
int per(int n, int r) {
	r = n - r;
	int sum = 1;
	int i;
	for (i = n; i >= r + 1; i--)sum *= i;
	return sum;
}
struct UnionFind {
	vector<int> par;

	UnionFind(int n) : par(n, -1) { }

	int root(int x) {
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}

	bool issame(int x, int y) {
		return root(x) == root(y);
	}

	bool merge(int x, int y) {
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x) {
		return -par[root(x)];
	}
};

signed main() {
	int N, A, B;
	cin >> N >> A >> B;

	if (A == 0 && B == 0) {
		cout << 0 << endl;
		return 0;
	}

	int x = N / (A + B);
	int y = N % (A + B);

	if (y >= A) {
		cout << (x + 1) * A << endl;
	}
	else if (y < A) {
		cout << x * A + y << endl;
	}
}


Measured memory_bytes: 256
N, M, X, Y = map(int, input().split())

x_list = list(map(int, input().split()))
y_list = list(map(int, input().split()))

x_max = max(x_list)
y_min = min(y_list)

for Z in range(X+1,Y+1):
    if x_max < Z <= y_min:
        print('No War')
        break

else:
    print('War')


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

bool get(string a,int p,string b,int k){
if (k>=b.size()) return 1;
for (int i=p+1;i<a.size();++i){
  if (a[i]==b[k]) return get(a,i,b,k+1);
  }return 0;
}

int main(){
string a;cin>>a;
puts(get(a,-1,"CF",0)?"Yes":"No");
}

Measured memory_bytes: 256
# B
import math
H,W = map(int,input().split())
ans = 0
if (H == 1 or W == 1):
    ans = 1
else:
    if (H % 2 == 0):
        ans = W * (H // 2)
    else:
        ans = W * (H // 2) + math.ceil(W / 2)
print(ans)

Measured memory_bytes: 38384
#include <iostream>

using namespace std;

int main() {
  int n, l, s = 0;
  int taste[200], tmp[200];
  cin >> n >> l;
  for (int i = 0; i < n; i++) {
    taste[i] = l + i;
    s += taste[i];
    tmp[i] = taste[i];
    if (taste[i] < 0) {
      taste[i] = -(l + i - 1);
    }
  }
  int ans = 0;
  for (int i = 1; i < n; i++) {
    if (taste[i] < taste[i - 1]){
      ans = i;
    }
  }
  cout << s - tmp[ans] << 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>;

int main() {
    int n, ans = 0;
    cin >> n;
    vector<int> d(n);
    rep(i, n) cin >> d[i];
    sort(d.begin(), d.end());
    cout << d[n / 2] - d[n / 2 - 1] << endl;
    return 0;
}


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

int main() {
  int N, K, X, Y;
  cin >> N >> K >> X >> Y;
  if (N <= K) {
    cout << N * X << endl;
  }
  else {
    cout << K * X + (N - K) * Y << endl;
  }
} 

Measured memory_bytes: 256