akhauriyash/Code-Regression huggingface dataset:
import sys
input = lambda: sys.stdin.readline().rstrip()

mod = 1000000007
X,Y = map(int, input().split())


def combination(n, r, mod):
    r = min(r, n-r)

    numer = 1
    denom = 1

    for i in range(r):
        numer = numer * (n-i) % mod
        denom = denom * (r-i) % mod

    return numer * pow(denom, mod-2, mod) % mod


m_n = (X+Y) // 3
m = X - m_n
n = Y - m_n

if (X+Y) % 3 != 0 or m < 0 or n < 0:
    print(0)
    exit()

    
print(combination(m_n, m, mod))

Measured memory_bytes: 38512
mod = 10**9+7

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

s = int(input())
if s==1 or s==2:
    print(0)
    exit()

pk_num = s//3-1
ans = 1
for i in range(pk_num):
    pk = (i+2)*3
    g = s - pk
    b = i+2
    ans += cmb(g+b-1,b-1)
    ans %=  mod
print(ans)

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

#define ASC(vec) vec.begin(), vec.end()		// 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend()	// 降順ソート 例:sort(DESC(vec));
#define rep(i, n) for(int i = 0; i < n; i++)
#define Rep(i, n) for(int i = 1; i < n; i++)
#define In(vec) rep(i, n) cin>>vec[i];
#define ANS(s) cout << s << endl
#define inc(a, b) cin >> a >> b;

const int mod = 1000000007;
const int inf = (int)1e9 + 7;
const long long INF = 1LL << 60;

using ii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vd = vector<double>;
using vb = vector<bool>;
using vl = vector<ll>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vii = vector<pair<int, int>>;

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

ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
ll LCM(ll a, ll b) { return (a * b) / GCD(a, b); }
int round_int(int a, int b) { return (a + (b - 1)) / b; }


// 4,8方向に探索する際に用いる配列
int dx[4] = { 0,  0, 1, -1 };
int dy[4] = { 1, -1, 0,  0 };
//int dx[8] = { 1, 0, -1,  0, 1, -1, -1,  1 };
//int dy[8] = { 0, 1,  0, -1, 1,  1, -1, -1 };

constexpr auto MAX = 100010;

// ────────────────────────────────────────────────────

int main() {
	string s, t, u; cin >> s >> t >> u;
	if (s.back() == t.front() && t.back() == u.front()) {
		ANS("YES");
	}
	else {
		ANS("NO");
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
const long long INFLL = 1LL << 60;
const int INFINT = 1 << 30;
const long long MOD = 1e9 + 7;

vector<vector<int>> G(101, vector<int>(0));
vector<int> c(101, 0);
vector<int> d(101, 0);
vector<int> f(101, 0);

template <class T> void vecout(T V) {
    auto t = V.begin();
    *t++;
    while(t != V.end()) {
        cout << " " << *t++;
        // if(t != V.end()) cout << " ";
    }
    cout << endl;
};

int t = 0;
void dfs(int i) {
    if(c[i]) return;
    c[i] = 1;
    d[i] = ++t;
    for(auto e : G[i])
        dfs(e);
    f[i] = ++t;
}

class node {
  public:
    int dist = -1;
    vector<int> nex;
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, u, k, a;
    cin >> n;
    vector<node> Node(n + 1);
    queue<int> Q;
    rep(i, n) {
        cin >> u >> k;
        rep(j, k) {
            cin >> a;
            Node.at(u).nex.push_back(a);
        }
    }
    Node[1].dist = 0;
    Q.push(1);

    while(!Q.empty()) {
        int v = Q.front();
        Q.pop();
        for(auto e : Node[v].nex) {
            if(Node[e].dist > -1) continue;
            Node[e].dist = Node[v].dist + 1;
            Q.push(e);
        }
    }

    rep(i, 1, n + 1) cout << i << " " << Node[i].dist << "\n";
}



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

int main(){

    int N,M;
    cin >> N >> M;

    //0だとOK　１だと壊れてる
    int a[N+1]={0};
    for(int i=0;i<M;i++){
        int temp;
        cin >> temp;
        a[temp]=1;
    }

    long long int s[N+1];

    s[0]=1;
    
    if(a[1]==1)s[1]=0;
    else s[1]=1;

    long long int mod = 1000000007;
    for(int i=2;i<=N;i++){
        if(a[i]!=1){
            s[i]=(s[i-1]+s[i-2])%mod;
        }else{
            s[i]=0;
        }
    }

    cout << s[N]%mod << endl;

    return 0;
}

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

using ll = long long;
#define double long double
#define rep(i, n) for (long long i = 0; i < (n); ++i)
#define repr(i, a, b) for (auto i = (a); i < (b); ++i)
#define itr(x, c) for (auto&& x : (c))
#define updatemax(t, v) ((t) = std::max((t), (v)))
#define updatemin(t, v) ((t) = std::min((t), (v)))
#define endl _endl
const char _endl = (cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout.precision(16), '\n');

int main() {
  ll n, m;
  cin >> n >> m;
  cout << (n - 1) * (m - 1) << endl;
}


Measured memory_bytes: 3528
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define all(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main(){
    const long long P=1000000007LL;
    long long n,m;
    cin>>n>>m;
    vector<long long> x(n),y(m);
    rep(i,n){
        cin>>x[i];
    }
    rep(i,m){
        cin>>y[i];
    }
    long long xSum=0,ySum=0;
    //xについての総和
    rep(i,n){
        xSum+=(n-2*i-1)*x[n-i-1];
        xSum=xSum%P;
    }
    //yについての総和
    rep(i,m){
        ySum+=(m-2*i-1)*y[m-i-1];
        ySum=ySum%P;
    }
    //
    long long ans=0;
    ans=(xSum*ySum)%P;
    while(ans<0){
        ans=ans+P;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <stack>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std;

int main(){
	int n,index;
	cin>>n;
	cin.ignore();
	vector<string> s(n);
	for(int i=0;i<n ; ++i){
		getline(cin,s[i]);
		while(s[i].find("Hoshino",0)!=string::npos){
			index=s[i].find("Hoshino",0);
			s[i].replace(index , 7 , "Hoshina");
		}
	}
	for(int i=0;i<n;++i){
		cout << s[i] << endl;
	}
	return 0; 
}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, N) for(int i = 0; i < N; i++)
#define rep2(i, N, a, b) for(int i = a; i < N; i += b)
typedef long long ll;

int main(){
	vector<int> N(3);
	rep(i, 3) cin >> N.at(i);
	sort(N.begin(), N.end());

	int ans = 0;
	ans = N.at(2) - N.at(1) + (N.at(1) - N.at(0)) / 2;
	if ((N.at(1) - N.at(0)) % 2) ans += 2;
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	int cs; scanf("%d", &cs);
	while(cs--){
		int x = 0; scanf("%x", &x);
		int n = x >> 7 & (1 << 24) - 1;
		double m = (x & (1 << 7) - 1) / (double)(1 << 7);
		
		if(x & 1 << 31) cout << "-";
		cout << n << ".";
		if(m == 0) cout << 0 << endl;
		else{
			while(m != 0){
				m *= 10;
				int k = (int)m;
				cout << k;
				m -= k;
			}
			cout << endl;
		}
		//dbg(n, m);
	}
	return 0;
}


Measured memory_bytes: 3320
import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
R,S,P = map(int,readline().split())
T = list(readline().rstrip())

P = {"r":P,"s":R,"p":S}
ans = 0
for i in range(len(T)):
  if i < K:
    ans += P[T[i]]
    continue
  if T[i] == T[i - K]:
    T[i] = "x"
  else:
    ans += P[T[i]]
print(ans)

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

using namespace std;

int main()
{
    int n;
    cin>>n;
    int a,b,c;
    a=n%10;
    b=n/100;
    c=(n/10)%10;
    if(a==7||b==7||c==7)
        cout<<"Yes";
    else
        cout<<"No";
    return 0;
}


Measured memory_bytes: 3636
n, k, q = map(int, input().split())

# それぞれの参加者の正解数を管理するリスト(i番目の参加者の正解数 = ans_num_list[i])
ans_num_list = [0] * n
for i in range(q):
    ans_num_list[int(input()) - 1] += 1

# 必要正解数
required_ans_num = q - k + 1

for i in range(n):
    if ans_num_list[i] >= required_ans_num:
        print('Yes')
    else:
        print('No')


Measured memory_bytes: 4680
#include <iostream>
using namespace std;
int main(){
    int size[100];

    int i;
    int j;
    while(cin >> j){
        for(i=0;i<j;i++){
            cin >> size[i];
        }

        for(i = j-1;i>0;i--){
            cout << size[i];
            cout << " ";
        }
        cout << size[0] << endl;
    }
    return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cctype>
#include<map>
#include<cstring>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,b) for (int (i)=a;(i)<(b);(i)++)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long int;

const int inf = 1001001000;
const long long int Inf = 1001001001001001000;



void print(vector<vector<int>> a){
	for (int i = 0; i < a.size(); i++)
	{
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<vector<long long int>> a){
	for (int i=0;i<a.size();i++){
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(vector<long long int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(set<int> a){
	for (auto x:a)
		cout << x << " ";
	cout << endl;
}




int main() {
	string s;
	string t;
	cin >> s >> t;
	vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
	rep(i,s.size()){
		rep(j,t.size()){
			if(s[i] == t[j]){
				dp[i + 1][j + 1] = max({dp[i + 1][j], dp[i][j + 1], dp[i][j] + 1});
			} else {
				dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
			}
		}
	}
	string ans = "";
	int i = s.size();
	int j = t.size();
	while(0 < i && 0 < i){
		if (dp[i][j] == dp[i-1][j]){
			i--;
		} else if (dp[i][j] == dp[i][j-1]){
			j--;
		} else {
			i--;
			j--;
			ans = s[i] + ans;
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 35584
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <cstdarg>
#include <sys/time.h>
#include <fstream>
//#include "cout.h"

using namespace std;

#define SZ(x) ((int)x.size())
#define MSET(x,a) memset(x, a, (int)sizeof(x))
#define PB push_back
#define VI vector < int >
#define PII pair < int, int >
#define LL long long
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(), (v).end()
#define FIT(it,v) for (__typeof((v).begin()) it = (v).begin(); it != (v).end(); it++)
#define OUT(A) cout << #A << " = "<< (A) << endl
#define OUT2(A, B) cout << "(" << #A << ", " << #B << ") = (" << (A) << ", "<< (B) << ")" << endl
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }

#define present(c, e) ((c).find((e)) != (c).end())
#define cpresent(c, e) (find(ALL(c), (e)) != (c).end())

int n;
int a[100010];

map<int, int> m1, m0;
VI v0, v1;

void init() {

}

void input() {

}

int sol(map<int, int> m0, map<int, int> m1) {
  int res = 0;
  int m0max = 0;
  int m0key;
  for(auto x : m0) {
    if (x.second > m0max){
      m0max = x.second;
      m0key = x.first;
    }
  }
  for(auto x : m0) {
    if (x.first != m0key) res += x.second;
  }

  int m1max = 0;
  int m1key;
  for(auto x : m1) {
    if (x.second > m1max && x.first != m0key){
      m1max = x.second;
      m1key = x.first;
    }
  }
  for(auto x : m1) {
    if (x.first != m1key) res += x.second;
  }

  // cout << "m0key: " << m0key << endl;
  //   cout << "m0max: " << m0max << endl;
  //     cout << "m1key: " << m1key << endl;
  //       cout << "m1max: " << m1max << endl;
  //         cout << "res: " << res << endl;

  return res;
}

void solve() {
  cin >> n;
  REP(i, n) cin >> a[i];

  for(int i=0; i<n; i+=2) m0[a[i]]++;
  for(int i=1; i<n; i+=2) m1[a[i]]++;
  // for(auto x : m0) cout << x.first << " " << x.second << endl;
  // for(auto x : m1) cout << x.first << " " << x.second << endl;
  for(auto x : m0) v0.push_back(x.second);
  for(auto x : m1) v1.push_back(x.second);

  cout << min(sol(m0, m1), sol(m1,m0)) << endl;
}

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


Measured memory_bytes: 15100
a, b, c, x, y = [int(x) for x in input().split()]

ans1 = 2 * min(x, y) * c
if x >= y:
  ans1 += (x - y) * a
else:
  ans1 += (y - x) * b

ans2 = x * a + y * b

ans3 = 2 * max(x, y) * c

print(min(ans1, ans2, ans3))

Measured memory_bytes: 38256
n, w = list(map(int, input().split(' ')))
items = [list(map(int, input().split(' '))) for i in range(n)]

table = [[0 for j in range(n+1)] for i in range(w+1)]

for i in range(1, w+1):
    for j in range(1, n+1):
        v, w = items[j-1]
        if i - w < 0:
            table[i][j] = table[i][j-1]
        else:
            new_val = table[i-w][j] + v
            table[i][j] = new_val if new_val > table[i][j-1] else table[i][j-1]

print(table[-1][-1])


Measured memory_bytes: 16920
#include<bits/stdc++.h>
typedef long long int ll;
#define PI 3.14159265358979323846264338327950L
using namespace std;
void solve()
{
    string s,t;
    cin >> s >> t;
    int flag=0;
    for(int i=0;i<s.length();++i)
    {
        if(s[i]!=t[i])
        flag=1;
    }
    if(flag==1)
    cout << "No" << endl;
    else
    cout << "Yes" << endl;
 }

int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    /*int t;
    cin >> t;
    while(t--)
    {
         solve();  
    }
   */ solve();
    return 0;
}





Measured memory_bytes: 3532
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define req(i,n) for(int i = 1;i <=n;i++)
#define pai 3.14159265358979323846
const int INF = 1001001001;
typedef long long ll;
int A[3][3], N;
bool punched[3][3];
bool ok[3][3];
using Graph = vector<vector<int>>;
vector<vector<int>> field;
vector<bool> seen;

const int MOD = 1000000007;
typedef pair<int,int> P;

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

}

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

//素数判定
bool is_prime(long long N) {
    if (N == 1) return false;
    for (long long i = 2; i * i <= N; ++i) {
        if (N % i == 0) return false;
    }
    return true;
}




#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


   
long long rec(long long N) {
    if (N==1) return 1;
    else  return rec(N/2)*2+1;
}

int main() {
    long long N;
    cin >> N;
    cout << rec(N) << endl;
}



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

int main(){
  ll h,w;
  cin >> h >> w;
  vector<string>s(h);
  for(int i=0; i<h; i++) cin >> s[i];
  vector<vector<ll>>dp(h,vector<ll>(w));
  
  if(s[0][0]=='#')dp[0][0]++;
  
  for(int i=1; i<h; i++){
    dp[i][0]=dp[i-1][0];
    if(s[i][0]=='#' && s[i-1][0]=='.')dp[i][0]++;
  }
    for(int i=1; i<w; i++){
    dp[0][i]=dp[0][i-1];
    if(s[0][i]=='#' && s[0][i-1]=='.')dp[0][i]++;
  }
  
  for(int i=1; i<h; i++){
    for(int j=1; j<w; j++){
      ll x=0,y=0;
      if(s[i][j]=='#' && s[i-1][j]=='.')x++;
      if(s[i][j]=='#' && s[i][j-1]=='.')y++;
      dp[i][j]=min(dp[i-1][j]+x,dp[i][j-1]+y);
    }
  }
  
  cout << dp[h-1][w-1] << endl;
  
}
       
        
      
  
    


Measured memory_bytes: 3696
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX 100005

using namespace std;

int n,x;
int a[MAX],b[MAX],c[MAX];
int i;
int flag=1,cou=0,k;

int gcd(int a,int b)
{
    return (a%b?gcd(b,(a%b)):b);
}

int main()
{
    scanf("%d%d",&n,&x);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    b[0]=x;
    sort(b,b+n+1);
    for(i=1;i<=n;i++)
    {
        c[i]=b[i]-b[i-1];
    }
    k=c[1];
    for(i=2;i<=n;i++)
    k=gcd(k,c[i]);
    printf("%d\n",k);
    return 0;
}


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

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Unstoppable solver = new Unstoppable();
	//	int t=in.nextInt();
	//	while(t-->0)
        solver.solve(in, out);
        out.close();
    }
 
    static class Unstoppable {
        public void solve(InputReader in, PrintWriter out) {
          String s=in.next();
          if(s.charAt(2)==s.charAt(3)&&s.charAt(4)==s.charAt(5)&&s.length()==6) out.println("Yes");
          else out.println("No");
        }
 
    }

 
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
 
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
 
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        public long nextLong(){
            return Long.parseLong(next());
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
 
    }
}
 

Measured memory_bytes: 21460
/**
     **author : _KMS_
     **created : 30-03-2020
**/
#include<bits/stdc++.h>
using namespace std;
const long long M =2e5+10,MOD=1e9+7;
typedef long long ll;
string p,s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    cout<<(n+1)/2<<"\n";

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

ll A[100010];
int main() {
	ll n,a,b;
	cin>>n>>a>>b;
	for(int i=0;i<n;i++){
		cin>>A[i];
	}
	ll ans=0;
	for(int i=1;i<n;i++){
		ll dx=A[i]-A[i-1];
		if(dx*a<=b){
			ans+=dx*a;
		}
		else{
			ans+=b;
		}
	}
	cout << ans;
	// your code goes here
	return 0;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<fstream>
#include<stdlib.h>
#include<set>
#include<climits>
#include<cmath>  
#include<memory.h> 
#include<sstream>
#include<time.h>
#include<iomanip>
using namespace std;
const unsigned long long BIGEST=1000000000000000000+1000000000000000000;
const long long BIGER=1000000000000000000;
const int BIG=1000000000;
const long long MOD=1004535809;
const long long LMOD=154590409516822759;
//const long long LMOD=1000000007;
#define Fi first
#define Se second
#define P2 pair
#define Pii pair<int,int>
#define Pll pair<long long,long long>
#define Cb make_pair
#define ll long long
#define Ull unsigned long long
#define Sf scanf
#define Pf printf
#define Pb push_back
#define Psh push
#define Stc stack
#define Vct vector
#define Ret return
#define Re0 return 0
#define Sz size
#define Is insert
#define Que queue
#define Emp empty
#define Fro front
#define Rv reverse
#define Er erase
#define Bg begin
#define Srt sort
#define Pq priority_queue
#define Ins insert
#define Ite iterator
#define Cou count
#define Cot continue
#define Beg begin
int main()
{
	int n;
	Sf("%d",&n);
	int t=0,g=0;
	for(int i=1;i<=n;i++)
	{
		Sf("%d",&t);
		if(t==g+1)g++;
	}
	Pf("%d",(g==0)?-1:n-g);
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;
typedef pair <int, int> P;
typedef pair <int, P> PP;

const int INF = 2147483647;

struct LazySegmentTree {
private:
    int n;
    vector <int> node, lazy;
    vector <bool> lazyFlag;

public:
    LazySegmentTree(vector <int> v) {
        int sz = v.size();
        n = 1;
        while (n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, 0);
        lazyFlag.resize(2*n-1, false);
        for (int i = 0; i < sz; i++) node[i+n-1] = v[i];
        for (int i = n-2; i >= 0; i--) node[i] = min(node[2*i+1], node[2*i+2]);
    }

    void lazyEvaluate(int k, int l, int r) {
        if (lazyFlag[k]) {
            node[k] = lazy[k];
            if (r - l > 1) {
                lazy[k*2+1] = lazy[2*k+2] = lazy[k];
                lazyFlag[k*2+1] = lazyFlag[k*2+2] = true;
            }
            lazyFlag[k] = false;
        }
    }

    void update(int a, int b, int val, int k=0, int l=0, int r=-1) {
        if (r < 0) r = n;
        lazyEvaluate(k, l, r);
        if (b <= l || r <= a) return;
        if (a <= l && r <= b) {
            lazy[k] = val;
            lazyFlag[k] = true;
            lazyEvaluate(k, l, r);
        } else {
            update(a, b, val, 2*k+1, l, (l+r)/2);
            update(a, b, val, 2*k+2, (l+r)/2, r);
            node[k] = min(node[2*k+1], node[2*k+2]);
        }
    }

    int find(int a, int b, int k=0, int l=0, int r=-1) {
        if (r < 0) r = n;
        lazyEvaluate(k, l, r);
        if (r <= a || b <= l) return INF;
        if (a <= l && r <= b) return node[k];
        int vl = find(a, b, 2*k+1, l, (l+r)/2);
        int vr = find(a, b, 2*k+2, (l+r)/2, r);
        return min(vl, vr);
    }
};


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

    int n, Q;
    cin >> n >> Q;

    vector <PP> vec(n);
    for (int i = 0; i < n; i++) {
        int s, t, x;
        cin >> s >> t >> x;
        vec[i] = PP(x, P(s, t));
    }

    sort(vec.begin(), vec.end(), greater<PP>());

    vector <int> D(Q+1, -INF);
    for (int i = 1; i <= Q; i++) cin >> D[i];

    vector <int> v(Q+1, -1);
    LazySegmentTree seg(v);

    for (int i = 0; i < n; i++) {
        int l = vec[i].second.first - vec[i].first;
        int r = vec[i].second.second - vec[i].first;

        int idx1 = lower_bound(D.begin(), D.end(), l) - D.begin();
        int idx2 = lower_bound(D.begin(), D.end(), r) - D.begin();

        seg.update(idx1, idx2, vec[i].first);
    }

    for (int q = 1; q <= Q; q++) {
        cout << seg.find(q, q+1) << "\n";
    }

    return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<pdd> vdd;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mem(a,b) memset(a, b, sizeof(a) )
#define all(x) (x).begin(),(x).end()
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
    int x;cin>>x;
    if(x==3||x==5||x==7)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef vector<pair<ll,ll>> vp;
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
#define all(v) v.begin() , v.end()
#define inputv(v,n) rep(i,n){\
    ll x;\
    cin>>x;\
    v.push_back(x);\
    }
const ll INF=99999999999999;
const ll MOD=1000000007;
 
int main() {
  ll n;
  cin >> n;
  vl a;
  inputv(a,n);
  sort(a.begin(),a.end());
  ll ans=0;
  rep(i,n){
    if(i%2 == 0){
      ans += a[n-i-1];
    } else {
      ans -= a[n-i-1];
    }
  }
  cout << ans;
 return 0;
}


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

template<class T,class U> inline void chmax(T&a,U b){if(a<b)a=b;}

int main(int argc, char *argv[])
{
	int n,m,q;
	scanf("%d %d %d", &n,&m,&q);
	int a[q], b[q], c[q], d[q];
	for (int i = 0; i < q; i++) {
		scanf("%d %d %d %d", &a[i],&b[i],&c[i],&d[i]);
		a[i]--;b[i]--;
	}
	int A[n];
	for (int i = 0; i < n; i++) {
		A[i] = 1;
	}
	int ans = 0;
	auto dfs = [&](auto&& dfs, int v) -> void{
		while (A[v] <= m) {
			if (v == n-1) {
				int tmp = 0;
				for (int i = 0; i < q; i++) {
					tmp += A[b[i]] - A[a[i]] == c[i] ? d[i] : 0;
				}
				chmax(ans,tmp);
			}
			else {
				if (A[v+1] < A[v]) {
					A[v+1] = A[v];
				}
				dfs(dfs, v+1);
			}
			A[v]++;
		}
		A[v] = 1;
		return;
	};
	dfs(dfs, 0);
	printf("%d",ans);
	return 0;
}


Measured memory_bytes: 3204
# ABC052D - Walk and Teleport (ARC067D)
def main():
    # choose A * dist(i, j) or B greedily
    N, A, B, *X = map(int, open(0).read().split())
    ans = sum(min(A * (j - i), B) for i, j in zip(X, X[1:]))
    print(ans)


if __name__ == "__main__":
    main()

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

using namespace std;

typedef long long ll;

const ll max_n=100010;
ll n,c[max_n];
vector<pair<ll,ll> > t[max_n];

void dfs(ll v,ll previous=-1){
	for (auto it: t[v]){
		ll u=it.first;
		ll w=it.second%2;
		if (u!=previous){
			c[u]=c[v]^w;
			dfs(u,v);
		}
	}
}

int main()
{
	cin>>n;
	for (int i=0;i<n-1;++i){
		ll u,v,w;
		cin>>u>>v>>w;
		t[u].push_back({v,w});
		t[v].push_back({u,w}); 
	}
	
	dfs(1);
	for (int i=1;i<=n;++i)
	    cout<<c[i]<<endl;
}

Measured memory_bytes: 10240
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define sc second
#define fr first
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rRep(i,a,b) for(int i=a;i>=b;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ll INF=1000000011;
constexpr ll MOD2=998244353;
constexpr ll LINF = 1001002003004005006ll;
constexpr ld EPS=10e-8;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
    for(auto i=begin(v); i != end(v); ++i){
        if(i !=begin(v)) os << ' ';
        os << *i;
    }
    return os;
}

int main(){
  ll N,C=0;
  string S;
  cin >> N >> S;
  rep(i,S.size()){
    if(S[i]=='R'){
      C++;
    }
  }
  cout << (C>N/2 ? "Yes" : "No") << endl;
}

Measured memory_bytes: 384
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    string a;
    cin>>a;
    int l,r;
    for(int i=0;i<a.size();i++)
    {
        if(a[i]=='A')
        {
            l=i;
            break;
        }
    } 
    for(int i=a.size()-1;i>=0;i--)
    {
        if(a[i]=='Z')
        {
            r=i;
            break;
        }
    }
    cout<<r-l+1<<endl;
}

Measured memory_bytes: 640
#include <iostream>
using namespace std;
 
int main() {
  
  int n;
  
  cin >> n;
  n %= 10;
  switch(n) {
    case 3:
      cout << "bon" << endl;
      break;
    case 0: 
    case 1: 
    case 6: 
    case 8:
  		cout << "pon" << endl;
     	break;
    default:
      	cout << "hon" << endl;
  }
  
  return 0;
}

Measured memory_bytes: 3628
<?php

fscanf(STDIN, '%d', $N);
$h = array_map('intVal', explode(' ', trim(fgets(STDIN))));

$dp = [];
$dp[1] = 0;
$dp[2] = abs($h[1] - $h[0]);

for ($i = 3; $i <= $N; ++$i) {
    $dp[$i] = min($dp[$i-1] + abs($h[$i-1] - $h[$i-2]), $dp[$i-2] + abs($h[$i-1] - $h[$i-3]));
}

echo $dp[$N];


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

#define d(x) cerr << #x ":" << x << endl;
#define dd(x, y) cerr << "(" #x "," #y "):(" << x << "," << y << ")" << endl
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define dump(v)                  \
    cerr << #v ":[ ";            \
    for (auto macro_vi : v) {    \
        cerr << macro_vi << " "; \
    }                            \
    cerr << "]" << endl;
#define ddump(v)                           \
    cerr << #v ":" << endl;                \
    for (auto macro_row : v) {             \
        cerr << "[";                       \
        for (auto macro__vi : macro_row) { \
            cerr << macro__vi << " ";      \
        }                                  \
        cerr << "]" << endl;               \
    }
using lint       = long long;
const int INF    = 1e9;
const lint LINF  = 1e18;
const double EPS = 1e-10;

const int D = 9;
int N;

set<int> se;

void dfs(string& S) {
    if (S.size() == D) {
        string result = S;
        reverse(all(result));

        bool ok1 = false, ok2 = false, ok3 = false;
        for (auto c : result) {
            if (c == '7') ok1 = true;
            if (c == '5') ok2 = true;
            if (c == '3') ok3 = true;
        }
        int n753 = stoi(result);
        if (n753 <= N && ok1 && ok2 && ok3) { se.insert(n753); }
        return;
    }

    if (S.size() > 0 && S.back() == '0') {
        S.push_back('0');
        dfs(S);
        S.pop_back();
        return;
    } else {
        char nxt[4] = {'0', '7', '5', '3'};
        for (int k = 0; k < 4; k++) {
            S.push_back(nxt[k]);
            dfs(S);
            S.pop_back();
        }
    }
    return;
}

int main() {
    cin >> N;

    string S = "";
    dfs(S);

    cout << se.size() << endl;
    return 0;
}

Measured memory_bytes: 4804
#include <stdio.h>
   
int main(){
 int i,j,h,w;
 while(1){
  scanf("%d %d",&h,&w);
  if(h==0 && w==0){break;}
  for(i=0;i<h;i++){
   for(j=0;j<w;j++){
    if(((i+j)%2)==0){
     printf("#");
    }else{
     printf(".");
    }
   }
   printf("\n");
  }
 printf("\n");
 }
 return 0;
}

Measured memory_bytes: 572
#include <bits/stdc++.h>
using namespace std;
int main(){
    int X, Y, a, b;
    cin >> X >> Y;
    a = (4*X - Y) / 2;
    b = X - a;
    if (a + b == X && 2*a + 4*b == Y && a >= 0 && b >= 0) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

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

int main(){
    int N,X,Y;
    cin >> N >> X >> Y;
    --X, --Y;
    vector<vector<int>> dist(N,vector<int>(N,-1));
    for(int s = 0; s < N; s++){
        queue<int> que;
        que.push(s);
        dist[s][s] = 0;
        while(!que.empty()){
            auto v = que.front(); que.pop();
            vector<int> nvs;
            if(v > 0) nvs.push_back(v-1);
            if(v < N - 1) nvs.push_back(v+1);
            if(v == X) nvs.push_back(Y);
            if(v == Y) nvs.push_back(X);
            for(auto nv:nvs){
                if(dist[s][nv] == -1){
                    dist[s][nv] = dist[s][v] + 1;
                    que.push(nv);
                }
            }
        }
    }
    vector<int> res(N,0);
    for(int i = 0; i < N; i++){
        for(int j = i + 1; j < N; j++) res[dist[i][j]]++;
    }
    for(int d = 1; d < N; d++) cout << res[d] << endl;
    
    
    
    
    
    
}




Measured memory_bytes: 19072
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cmath>

using namespace std;
using ll = long long;
using ull = unsigned long long;

constexpr ll LLINF {1001002003004005006};//ll = 9*LLINF
constexpr int INTINF {1000000000};//int = 2*INTINF

#define  rep(i,n)   for(int i = 0; i < (n); ++i)
#define rrep(i,n)   for(int i = 1; i <= (n); ++i)
#define drep(i,n)   for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for(int i = s; i < t;  ++i)

template<typename T>
void maxs(T& x, T&& y) {
  x=std::max(x,y);
}
template<typename T>
void maxs(T& x, T& y) {
  x=std::max(x,y);
}

template<typename T>
void mins(T& x, T&& y) {
  x=std::min(x,y);
}
template<typename T>
void mins(T& x, T& y) {
  x=std::min(x,y);
}

int main() {
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  double T, X;
  cin >> T >> X;
  cout <<std::fixed<< T/X << '\n';
}


Measured memory_bytes: 256
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;

using lint = long long;
using P = pair<int, int>;
using LLP = pair<long long, long long>;

#define REP(i, x, n) for(int i = (x), i##_len = (int)(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = (int)(n) ; i < i##_len ; ++i)
#define reps(i, n) for(int i = 1, i##_len = (int)(n) ; i <= i##_len ; ++i)
#define rrep(i, n) for(int i = (int)(n) - 1 ; i >= 0 ; --i)
#define rreps(i, n) for(int i = (int)(n) ; i > 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())
#define REVERSE(x) reverse((x).begin(), (x).end())
#define TWINS(x) cout << ((x) ? "Yay!" : ":(") << '\n'
#define endl '\n'

constexpr int IINF = (1 << 30) - 1;
constexpr long long LLINF = 1LL << 61;
constexpr double EPS = 1e-10;

constexpr int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
constexpr int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};

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

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

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

    int n, m;
    while(cin >> n >> m, n){
        vector<int> p(n);
        int ans = 0;
        rep(i, n){
            cin >> p[i];
            ans += p[i];
        }

        SORT_INV(p);
        for(int i = m - 1 ; i < n ; i += m){
            ans -= p[i];
        }

        cout << ans << endl;
    }

    cout << flush;

    return 0;
}


Measured memory_bytes: 3016
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P std::pair<int,int>
#define PiP std::pair<int,std::pair<int,int>>
#define all(v) v.begin(),v.end()
#define mkp std::make_pair
#define prique(T) std::priority_queue<T,vector<T>,greater<T>>
using namespace std;
template<class T> inline void chmax(T& a, T b) { a = std::max(a, b); }
template<class T> inline void chmin(T& a, T b) { a = std::min(a, b); }

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return x != 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 / gcd(x, y) * 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 get_rand(int MIN, int MAX) {
	std::random_device rnd;
	std::mt19937 mt32(rnd());
	std::uniform_int_distribution<int>engine(MIN, MAX);
	return engine(mt32);
}
/*--------Library Zone!--------*/

int n;
string s;
int le[15], ri[15];
signed main() {
	cin >> n >> s;
	rep(i, 15)le[i] = -1;
	rep(i, n) {
		if (le[s[i] - '0'] == -1) {
			le[s[i] - '0'] = i;
		}
		ri[s[i] - '0'] = i;
	}
	int ans = 0;
	rep(i, 10)rep(j, 10) {
		if (le[i] == -1 || ri[j] == 0)continue;
		bool b[10];
		rep(k, 10)b[k] = false;
		for (int k = le[i] + 1; k < ri[j]; k++) {
			b[s[k] - '0'] = true;
		}
		rep(k, 10)ans += b[k];
	}
	cout << ans << endl;
}


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

long long l;
long long n, m, p;
vector<int> v;

int main(){
//	cin.tie(0);
//	ios::sync_with_stdio(false);
	cin >> l;
	long long t = l;
	while(t > 0){
		if(t % 2 == 1){
			++p;
			v.push_back(n);
		}
		++n;
		t /= 2;
	}
	--p;
	v.pop_back();
	m = p + 2*(n-1);
	cout << n << " " << m << "\n";
	t = 1;
	for(int i=1; i<n; ++i){
		cout << i << " " << i+1 << " " << 0 << "\n";
		cout << i << " " << i+1 << " " << t << "\n";
		t *= 2;
	}
	reverse(v.begin(), v.end());
	for(int i=0; i<v.size(); ++i){
		cout << v[i]+1 << " " << n << " " << t << "\n";
		long long s = 1;
		for(int j=0; j<v[i]; ++j) s *= 2;
		t += s;
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define inf 1e18
#define int long long
int n,k;
int a[1000001];
int b[1000001];
bool judge(int x)
{
	int tot=0;
	for(int i=1;i<=n;i++)
		tot+=max(0ll,a[i]-x/b[i]);
	return tot<=k;
}
signed main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)
		scanf("%lld",&b[i]);
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	reverse(b+1,b+n+1);
	int l=-1,r=1e18;
	while(l+1<r)
	{
		int mid=(l+r)/2;
		if(judge(mid))
			r=mid;
		else
			l=mid;
	}
	printf("%lld",r);
	return 0;
}
/*
1 2 3
4 2 1
*/

Measured memory_bytes: 5888
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <iomanip>
#include <functional>
#include <queue>
#include <stack>
#include <map>
#include <vector>
#include <cmath>
#include <cctype>
#include <cstdio>
#define ll long long
#define INF 1000000000000000001
#define MOD 1000000007
using namespace std;


int main(){
    string s;
    int n,k;
    cin >> n >> k >> s;
    s[k-1]+='a'-'A';
    cout<<s<<endl;
    return 0;
}





Measured memory_bytes: 256
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
	char c=getchar();bool f=0;x=0;
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	if(f) x=-x;return x;
}
template<class t,class ...A> inline void read(t &x,A &...a){
	read(x);read(a...);
}
template<class t> inline void write(t x){
	if(x<0) putchar('-'),write(-x);
	else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const char sigma[]={"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"};
const int L=128;
int len,cnt[70];

int query(const string &s){
    cout<<"? "<<s<<endl; 
    int result;
    cin>>result;
    return result;
}

bool check(const string &s){
    return query(s)==len-s.size();
}

string merge(int l,int r){
    if(l==r) return string(cnt[l],sigma[l]);
    int mid=l+r>>1;
    string a=merge(l,mid),b=merge(mid+1,r),res;
    int i=0,j=0;
    while(i<a.size()&&j<b.size()){
        if(check(res+a[i]+b.substr(j))) res+=a[i++];
        else res+=b[j++];
    }
    while(i<a.size()) res+=a[i++];
    while(j<b.size()) res+=b[j++];
    return res;
}
int main()
{
    for(int i=0;i<62;i++) cnt[i]=L-query(string(L,sigma[i])),len+=cnt[i];
    string ans=merge(0,62);
    cout<<"! "<<ans<<endl;
    return 0;
}

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

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(lol i=0;i<lol(n);i++)
#define REPD(i,n) for(lol i=n-1;i>=0;i--)
#define FOR(i,a,b) for(lol i=a;i<=lol(b);i++)
#define FORD(i,a,b) for(lol i=a;i>=lol(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() //sortなどの引数を省略したい
#define SIZE(x) lol(x.size()) //sizeをsize_tからllに直しておく
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//最大値最小値
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; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main()
{
    lol result{0};
    int x; cin >> x;
    lol n; cin >> n;
    vector<int> a(n);
    REP(i, n)
    {
        cin >> a[i];
    }
    sort(ALL(a));
    REP(i, 100)
    {
        if(find(ALL(a), x - i) == a.end())
        {
            cout << x - i << endl;
            break;
        }
        else if(find(ALL(a), x + i) == a.end())
        {
            cout << x + i << endl;
            break;
        }
    }

    //cout << result << endl;
    return 0;
}

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

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

int A,B,C;
/*

string hoge(map<string,int> M) {
	if(M.size()==1) {
		string s="";
		while(M.begin()->second--) s+=M.begin()->first;
		return s;
	}
	string s=M.begin()->first;
	string t=M.rbegin()->first;
	int a=M.begin()->second;
	int b=rM.begin()->second;
	
	if(a<=b) {
	}
	
	
}
*/

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>C;
	vector<string> V;
	FOR(i,A) V.push_back("a");
	FOR(i,B) V.push_back("b");
	FOR(i,C) V.push_back("c");
	
	while(V.size()>1) {
		sort(ALL(V));
		V[0]+=V.back();
		V.pop_back();
	}
	
	cout<<V[0]<<endl;
	/*
	map<string,int> M;
	if(A) M["a"]=A;
	if(B) M["b"]=B;
	if(C) M["c"]=C;
	
	cout<<hoge(M)<<endl;
	*/
}


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


Measured memory_bytes: 256
#include<stdio.h>

int main(){
	long long int a,b,c,d,x;
	scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
   if(b > 0 && d > 0){
   	if(b * d > a * c){
   	   x = b * d;}
	   else{
	   	x = a * c;
	   }
   }
   else if(b < 0 && c > 0){
   	   x = b * c;
   }
   else if(a > 0 && d < 0){
   	x = a * d;
   }
   else{
   	x = a * c;
   }
   printf("%lld",x);
}

Measured memory_bytes: 1732
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
#define pb push_back
#define endl "\n"
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)

signed main(){
	fast;
	int n;
	cin>>n;
	int a[n],cnt=0;
	for(int i=0;i<n;i++){
		cin>>a[i];
		if(a[i]!=i+1) cnt++;
	}
	if(cnt==0 or cnt==2) cout<<"YES";
	else cout<<"NO";
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <map>
#include <utility>
#include <set>

using namespace std;

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

char s[105];

int main() {
    int n;
    scanf("%d", &n);
    scanf("%s", s);
    bool result = false;
    if (n % 2 == 0) {
        int m = n / 2;
        result = true;
        for (int i = 0; i < m; ++i) {
            if (s[i] != s[m + i]) {
                result = false;
                break;
            }
        }
    }

    printf("%s\n", result ? "Yes" : "No");
    return 0;
}



Measured memory_bytes: 256