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

long long int N, M, u, v, s, bdp[101010], us[101010], num[101010], f = true, S, T, A;
vector<pair<long long, long long>> edges[101010];
vector<long long> lop;

long long int bdfs(int n, int F){
    if(bdp[n] != -1){
        if(bdp[n] != F){
            f = false;
            A = n;
            return n;
        }else{
            return -1;
        }
    }
    bdp[n] = F;
    for(auto e : edges[n]){
        long long a = bdfs(e.first, !F);
        if(a != -1){
            if(a == A){
                S += e.second;
                return n == A ? 0 : -a - 1;
            }else if(a == -A - 1) {
                S += e.second;
                T += e.second;
                return n == A ? 0 : -a - 1;
            }else{
                return 0;
            }
        }
    }
    return -1;
}

int main(){
    scanf("%lld%lld", &N, &M);
    for(int i = 0; i < M; ++i){
        scanf("%lld%lld%lld", &u, &v, &s);
        edges[u].emplace_back(v, s);
        edges[v].emplace_back(u, s);
    }
    fill(bdp, bdp + 101010, -1);
    bdfs(1, 0);
    if(f){
        long long int m1 = 1, m2 = 922337204885477570;
        fill(num, num + 101010, -1);
        stack<pair<long long, long long>> s;
        s.emplace(1, 1);
        while(!s.empty()){
            auto t = s.top();
            s.pop();
            if(num[t.first] != -1){
                if(num[t.first] != t.second){
                    f = false;
                    break;
                }else{
                    continue;
                }
            }
            num[t.first] = t.second;
            (bdp[t.first] ? m2 : m1) = min((bdp[t.first] ? m2 : m1), t.second);
            for(auto e : edges[t.first])s.emplace(e.first, e.second - t.second);
        }
        if(!f)return 0 & puts("0");
        printf("%lld\n", max(0LL, m1 + m2 - 1));
    }else{
        fill(num, num + 101010, -1);
        f = true;
        stack<pair<long long, long long>> s;
        if(S & 1)return 0 & puts("0");
        s.emplace(A, S / 2 - T);
        while(!s.empty()){
            auto t = s.top();
            s.pop();
            if(num[t.first] != -1){
                if(num[t.first] != t.second){
                    f = false;
                    break;
                }else{
                    continue;
                }
            }
            if(t.second <= 0)return 0 & puts("0");
            num[t.first] = t.second;
            for(auto e : edges[t.first])s.emplace(e.first, e.second - t.second);
        }
        puts(f ? "1" : "0");
    }
    return 0;
}

Measured memory_bytes: 15744
#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

int main() {
  	long long int N, K;
  	cin >> N >> K;
  	long long int A[N];
  	for (int i = 0; i < N; i++) cin >> A[i];
  
  	bool flag = false;
  	long long int res = 0;
  	while (flag == false){
        long long int plus[N];
        long long int minus[N];
      	for (int i = 0; i < N; i++){
          	plus[i] = 0;
          	minus[i] = 0;
        }
      	for (int i = 0; i < N; i++){
          	if (i <= A[i]) plus[0]++;
          	else plus[i - A[i]]++;
          	if (N - i <= A[i]) minus[N - 1]++;
          	else minus[i + A[i]]++;
        }
      	long long int count = 0;
      	for (int i = 0; i < N; i++){
          	count += plus[i];
          	A[i] = count;
          	count -= minus[i];
        }
      	bool flag2 = false;
      	for (int i = 0; i < N; i++){
          	if (A[i] != N) flag2 = true;
        }
      	if (flag2 == false) flag = true;
      	res++;
      	if (res == K) flag = true;
    }
  
  	for (int i = 0; i < N; i++){
      	cout << A[i] << endl;
    }
}

Measured memory_bytes: 8320
#include<bits/stdc++.h>
using namespace std;
int main(){
  string A,B;
  cin>>A>>B;
  string C=A;
  string D=B;
  reverse(C.begin(),C.end());
  reverse(D.begin(),D.end());
  if(A==D&&B==C){
    cout<<"YES"<<endl;
  }
  else{
    cout<<"NO"<<endl;
  }
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
int n;
int parent[20][100001];
vector<int> G[100001];
int depth[100001];

void init(){
	for(int k=0;k+1<20;k++){
		for(int v=1;v<=n;v++){
			if(parent[k][v]<0)parent[k+1][v]=-1;
			else parent[k+1][v]=parent[k][parent[k][v]];
		}
	}
}

int lca(int u,int v){
	if(depth[u]>depth[v])swap(u,v);
	for(int k=0;k<20;k++){
		if((depth[v]-depth[u])>>k & 1){
			v=parent[k][v];
		}
		if(u==v)return u;
	}
	for(int k=19;k>=0;k--){
		if(parent[k][u]!=parent[k][v]){
			u=parent[k][u];
			v=parent[k][v];
		}
	}
	return parent[0][u];
}

vector<int> route;
ll bfs(){
	init();
	queue<int> que;
	que.push(1);
	while(que.size()){
		int q=que.front();
		que.pop();
		route.push_back(q);
		for(int i=0;i<G[q].size();i++){
			int next=G[q][i];
			if(depth[next]>depth[q])que.push(next);
		}
	}
	ll res=depth[route[0]];
	for(int i=0;i<route.size()-1;i++){
		res+=(ll)depth[route[i]]+depth[route[i+1]]-depth[lca(route[i],route[i+1])]*2;
	}
	return res;
}

int dfs(int v,int d){
	depth[v]=d;
	for(int i=0;i<G[v].size();i++){
		if(depth[G[v][i]]==-1)dfs(G[v][i],d+1);
	}
}

int main(void){
	scanf("%d",&n);
	parent[0][1]=-1;
	for(int i=2;i<=n;i++){
		scanf("%d",&parent[0][i]);
		G[parent[0][i]].push_back(i);
	}
	memset(depth,-1,sizeof(depth));
	dfs(1,0);
	printf("%lld\n",bfs());
	return 0;
}

Measured memory_bytes: 18320
N, K = gets.split.map(&:to_i)
A = gets.split.map(&:to_i).sort.reverse
F = gets.split.map(&:to_i).sort

def f(t)
  cnt = 0

  A.zip(F).each do |a, f|
    if a * f > t
      b = t / f
      cnt += a - b
    end
  end

  cnt <= K
end

if f(0)
  puts 0
  exit
end

ok = A.max * F.max
ng = 0

while (ok - ng).abs > 1
  mid = (ok + ng) / 2

  if f(mid)
    ok = mid
  else
    ng = mid
  end
end

puts ok


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

int main() {
	char a, b;
	scanf("%c %c", &a, &b);
	if (a == 'H'){
		printf("%c\n", b);
	}else {
		if (b == 'H')
			printf("D\n");
		else
			printf("H\n");
	}
	return 0;
}

Measured memory_bytes: 256
a, b, m = map(int, input().split())

refrigerator = list(map(int, input().split()))
oven = list(map(int, input().split()))
coupon = [list(map(int, input().split())) for i in range(m)]

normal = min(refrigerator) + min(oven)
ans = normal

tmp = 0


for i in range(m):
  tmp = refrigerator[coupon[i][0]-1]+oven[coupon[i][1]-1]-coupon[i][2]
  if ans > tmp:
    ans = tmp

print(ans)

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

int main(){
  int a [] = {0 , 1 , 3 , 1 , 2 , 1 , 2 , 1 , 1 , 2 , 1 , 2 , 1};
 int c,b;
  cin>>c>>b;
    if(a[c]==a[b]){
cout<<"Yes"<<endl;
  }
    else{
   cout<<"No"<<endl;
    }
  }
 



Measured memory_bytes: 256
A, B, Q = map(int, input().split())
s = [int(input()) for _ in range(A)]
t = [int(input()) for _ in range(B)]
x = [int(input()) for _ in range(Q)]
INF = 10 ** 18


def bsearch(n, arr):
    l = 0
    r = len(arr)
    m = (l + r) // 2
    while l != m:
        if n <= arr[m]:
            r = m
        else:
            l = m
        m = (l + r) // 2
    return l


s = [-INF] + s + [INF]
t = [-INF] + t + [INF]

for i, x_i in enumerate(x):
    sa = bsearch(x_i, s)
    ta = bsearch(x_i, t)
    lmin = INF
    for si in range(sa, sa + 2):
        for ti in range(ta, ta + 2):
            l = min(abs(x_i - s[si]) + abs(s[si] - t[ti]), abs(x_i - t[ti]) + abs(t[ti] - s[si]))
            lmin = min(l, lmin)
    print(lmin)

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

int main(){

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

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

int main() {
  int N;
  cin >> N;
  vector<int> A(N),T(N);
  vector<int> exact(N, -1), max_h(N, 1 << 30);
  for(int &a: A) cin >> a;
  for(int &t: T) cin >> t;
  bool ok = true;
  for(int k = 0; k < 2; k++) {
    for(int i = 0; i < A.size(); i++) {
      if(i == 0 || A[i] > A[i - 1]) {
        if(exact[i] == -1) {
          exact[i] = A[i];
        }
        if(exact[i] != A[i]) ok = false;
      }else {
        if(exact[i] != -1) 
          if(A[i] < exact[i]) ok = false;
        max_h[i] = min(max_h[i], A[i]);
      }
    }
    reverse(exact.begin(), exact.end());
    reverse(max_h.begin(), max_h.end());
    reverse(T.begin(), T.end());
    swap(A,T);
  }
  if(ok == false) {
    cout << 0 << endl;
  } else {
    long long answer = 1;
    for(int i = 0; i < N; i++) {
      if(exact[i] != -1) continue;
      answer = answer * max_h[i] % 1000000007;
    }
    cout << answer << endl;
  }
}

Measured memory_bytes: 1792
/**********************************************
 *Author*        :coderdz
 *Created Time*  : 2018/5/5 14:23:12

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

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
#define IO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,n) for(int i=1;i<=n;i++)
#define m(a,b) memset(a,b,sizeof(a))
#define c(a) cout<<a<<endl;
typedef pair<int, int> PII;
typedef long long ll;
const int MAXN=1e5+10;

inline void OPEN(string s){
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

int main(){
    IO;
    int a,b,c,k;
    cin>>a>>b>>c>>k;
    if (a>b) swap(a,b);
    if (b>c) swap(b,c);
    for(int i=1;i<=k;i++)
    	c*=2;
    c(a+b+c)
    return 0;
}

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

using namespace std;

multiset<int> ms;

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

  cin >> q;
  while(q--) {
    int a, x;
    cin >> a >> x;
    if (a == 0) {
      ms.insert(x);
      cout << ms.size() << endl;
    }
    else if (a == 1) {
      cout << ms.count(x) << endl;
    }
    else if (a == 2) {
      ms.erase(x);
    }
    else if (a == 3) {
      int y;
      cin >> y;
      auto aa = ms.lower_bound(x);
      auto bb = ms.upper_bound(y);
      for(auto it = aa; it != bb; it++) {
        cout << *it << endl;
      }
    }
  }
  return 0;
}



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

int main(){
  ll h;
  ll ans=0;
  ll count=0;
  std::cin >> h;
  auto cal=[&](){
    while (h/2>0) {
      count++;
      h/=2;
      ans +=pow(2,count);
    }
  };
  cal();
  cout << ans+1  << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>

using namespace std;

int main() {
  int N, A, B;
  scanf("%d %d %d", &N, &A, &B);
  if ((B - A) % 2 == 0) {
    printf("Alice");
  } else {
    printf("Borys");
  }
  return 0;
}


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

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 n, a;
	cin >> n;
	vector<int> arr;
	for(int i = 0; i < n; i++) {
		cin >> a;
		arr.push_back(a);
	}
	int cnt = 0;
	for(int i = 0; i < n; i++) {
		int x = arr[i];
		for(int j = i + 1; j < n; j++) {
			int y = arr[j];
			if(y != x) {
				for(int k = j + 1; k < n; k++) {
					int z = arr[k];
					if(z != x && z != y && x + y > z && x + z > y && y + z > x) {
						cnt += 1;
					}
				}
			}
		}
	}
	cout << cnt;
	return 0;
}

Measured memory_bytes: 3676
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>

using namespace std;

#define sz(x) (int) x.size()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end())
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x)) 
#define y1 aksjdaskdjksjfksdjf
#define left kdnvldvoiwejifejg
#define right lkdsjflksdjfdjfk
#define prev asdasfsadjkjsdfjs
#define tm aklsjdasjdasjdkdjjf
#define lcm hddalkwjeidjjhasda
#define random_shuffle asdasdd

int a, b;

string toString(int a) {
  string res = "";
  while (a) {
    res.append(1, '0' + a % 10);
    a /= 10;
  }
  reverse(all(res));
  return res;
}

int toInt(string s) {
  int res = 0;
  for (int i = 0; i < sz(s); i++) {
    res = res * 10 + s[i] - '0';
  }
  return res;
}

int main() { 

  cin >> a >> b;
  int c = toInt(toString(a) + toString(b));

  for (int i = 1; i * i <= c; i++) {
    if (i * i == c) {
      puts("Yes");
      return 0;
    }
  }

  puts("No");

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<x<<endl
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;
const ll LINF = LLONG_MAX;
const int INF = INT_MAX;
const double PI=acos(-1);
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
	string s,t; cin>>s>>t;
	ll ans=0;
	rep(i,0,s.size()){
		if(s[i]!=t[i]) ans++;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3844
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int top, S[1000];

void push(int x){
	top++;
	S[top] = x;
}

int pop(){
	top--;
	return S[top+1];
}

int main(void){
	int a, b;
	top =0;
	char s[100];
	
	while (scanf("%s", s) != EOF){
		if(s[0] == '+'){
			a=pop();
			b =pop();
			push(a+b);
		}
		else if(s[0] == '-'){
			
			b =pop();
			a=pop();
			push(a-b);
		}
		else if(s[0] == '*'){
			a=pop();
			b =pop();
			push(a*b);
		}else{
			push(atoi(s));
		}
	}
	
	printf("%d\n", pop());
	
	return 0;

}


Measured memory_bytes: 2076
#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>
#include <climits>

using namespace std;

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

int d[105];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &d[i]);
    }

    int total = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            total += d[i] * d[j];
        }
    }
    printf("%d\n", total);
    return 0;
}



Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned int uint;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

bool sta[5050];

int tot = -1, lx, ly, head[5050], n, a[5050];

struct in
{
    int to, ne;
}ter[10010];

inline void build(int f, int l)
{
    ter[++ tot] = (in){l, head[f]}, head[f] = tot;
    ter[++ tot] = (in){f, head[l]}, head[l] = tot;
}

void dfs(int no, int f)
{
    sta[no] = 0;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(to == f)
            continue;
        dfs(to, no);
        if(a[no] > a[to] && (!sta[to]))
        {
            sta[no] = 1; break;
        }
    }
}

int main()
{
    re(n), memset(head, -1, sizeof(head));
    for(ri i = 1; i <= n; re(a[i ++]));
    for(ri i = 1; i < n; i ++)
        re(lx), re(ly), build(lx, ly);
    for(ri i = 1; i <= n; i ++)
    {
        dfs(i, 0);
        if(sta[i])
            printf("%d ", i);
    }
}

Measured memory_bytes: 512
#include <iostream>
#include <cstring>

using namespace std;


int main()
{
	int N, Y;
	int i, j, k;
	bool flag = false;

	cin >> N >> Y;

	for (i = 0; i <= N; i++)
	{
		for (j = 0; j <= (N - i); j++)
		{
			k = N - i - j;
			if (10000 * i + 5000 * j + 1000 * k == Y)
			{
				flag = true;
				break;
			}
		}
		if (flag == true)
			break;
	}

	if (flag == true)
	{
		cout << i << " " << j << " " << k << endl;
	}
	else
	{
		cout << "-1 -1 -1" << endl;
	}

	return 0;
}

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

int main() {
	int s, m, h;
	cin >> s;
	m = s / 60;
	s = s % 60;
	h = m / 60;
	m = m % 60;
	cout << h << ':' << m << ':' << s << endl;
}


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

#define ll long long int
const int sz=1e5+100;
const ll mod=1e9+7;

ll fact[sz];

ll Bigmod(ll a,ll pr)
{
    if(pr==0) return 1ll;
    else if(pr==1) return a;
    ll x=Bigmod(a,pr/2);
    x=(x * x)%mod;
    if(pr & 1ll) x=(x * a)%mod;
    return x;
}

ll NCK(ll n,ll k)
{
    if(k>n) return 0;
    if(k==0 || k==n) return 1;
    ll temp=(fact[k] * fact[n-k])%mod;
    temp = (fact[n] * Bigmod(temp,mod-2))%mod;
    return temp;
}

int main()
{
    ll a,p,q,i,j,k,n,m,x,y;

    fact[0]=fact[1]=1;
    for(i=2;i<sz;i++) fact[i]=(fact[i-1] * i) % mod;

    cin>>n>>k;
    ll ara[n];
    for(i=0;i<n;i++) cin>>ara[i];

    sort(ara,ara+n);

    ll big=0, small=0;
    ll last=0;
    for(i=k-1,j=n-k;i<n;i++,j--){
        ll tot=NCK(max(i-1,0ll),max(k-2,0ll));
        last=(last + tot) %mod;
        big=( big + (last * ara[i])%mod) %mod;
        small=(small + (last * ara[j])%mod ) %mod;
    }

    ll ans=(((big-small)%mod)+mod)%mod;

    cout<<ans<<'\n';
}


Measured memory_bytes: 5196
#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(int i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define si(x)	scanf("%d",&x)
#define sl(x)	scanf("%lld",&x)
#define ss(s)	scanf("%s",s)
#define pi(x)	printf("%d\n",x)
#define pl(x)	printf("%lld\n",x)
#define ps(s)	printf("%s\n",s)
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define wi(t) int t;cin>>t;while(t--)
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pl>		vpl;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int mpow(int base, int exp); 
void ipgraph(int n, int m);
void dfs(int u, int par);

const int mod = 1000000007;
const int N = 3e5, M = N;
//=======================

vi g[N];
int a[N];

void solve()
    {
   ll int z,x,y;
   cin>>x>>y>>z;
   vl ar(x);
   fo(i,x) cin>>ar[i];
   double diff=10e9;
   ll int ans=-1;
   for(int i=0;i<x;i++)
   {  
      double  k=y-ar[i]*0.006;
       if(abs(k-z)<diff)
       {
           diff=abs(k-z);
           ans=i;
       }
      
   }
   cout<<ans+1<<endl;
   
  
  
  
    }

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());

   // wi(t)
    {
      solve();
    }

    return 0;
}

int mpow(int base, int exp) {
  base %= mod;
  int result = 1;
  while (exp > 0) {
    if (exp & 1) result = ((ll)result * base) % mod;
    base = ((ll)base * base) % mod;
    exp >>= 1;
  }
  return result;
}

void ipgraph(int n, int m){
	int i, u, v;
	while(m--){
		cin>>u>>v;
    u--, v--;
		g[u].pb(v);
		g[v].pb(u);
	}
}

void dfs(int u, int par){
	for(int v:g[u]){
		if (v == par) continue;
		dfs(v, u);
	}
}







Measured memory_bytes: 10608
#include <iostream>
#include <algorithm>

using namespace std;

long long lcm(long long a, long long b)
{
	return a / __gcd(a, b) * b;
}

int main()
{
	long long A, B;
	cin >> A >> B;
	cout << lcm(A, B) << endl;

	return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <array>
#include <algorithm>
#include <iterator>
#include <cstdint>

int main()
{
	typedef std::array<std::uint16_t, 100> DataArray;
	DataArray datas;
	datas.fill(0);

	std::uint16_t max_occurence = 0;
	std::uint16_t num;
	while (std::cin >> num) {
		max_occurence = std::max(max_occurence, ++datas[num - 1]);
	}

	for (DataArray::const_iterator pos =
			std::find(datas.cbegin(), datas.cend(), max_occurence);
		 pos != datas.end();
		 pos = std::find(pos, datas.cend(), max_occurence)) {
			std::cout << std::distance(datas.cbegin(), ++pos) << std::endl;
	}

	return 0;
}

Measured memory_bytes: 1160
import java.util.*;
public class Main {
    public static void main(String[] args){

		Scanner sc = new Scanner(System.in);

		String alpha = sc.next();
      
      if(alpha.equals(alpha.toUpperCase())){
        System.out.println("A");     
      }else{
         System.out.println("a");
      }
      
		
		
    }
}

Measured memory_bytes: 35668
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {

	static Scanner scan = new Scanner(System.in);
	static PrintWriter out = new PrintWriter(System.out);

	public static void main(String[] args) {
		while(true){
			int n = si();
			if(n==0) break;

			char[] num = Integer.toOctalString(n).toCharArray();
			for (int i = 0; i<num.length ; i++) {
				if(num[i]>='4') num[i]++;
				if(num[i]>='6') num[i]++;
				out.print(num[i]);
			}
			out.println();
		}
		out.flush();
	}

	static int si() {
		return Integer.parseInt(scan.next());
	}
}

Measured memory_bytes: 37380
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rep(i,b) FOR(i,0,b)
#define INF mugen
#define dump(x) cerr<<#x<<"="<<x<<endl
#define all(a) (a).begin(),(a).end()
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<vii> viii;
typedef pair<int,int> P;
template <class T> void chmin(T & a, T const & b) { if (b < a) a = b; }
template <class T> void chmax(T & a, T const & b) { if (b > a) a = b; }
template <typename T>
string to_string(const T &n){ostringstream stm;stm << n;return stm.str();}
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
using ll = long long;
const ll mod = LLONG_MAX;
 
int n,a,b,c,d;
signed main(){
    cin>>n>>a>>b>>c>>d;
    a--;b--;c--;d--;
    string s;
    cin>>s;
    bool flag0=true,flag1=true;

    if(a>b){
        swap(a,b);
        swap(c,d);
    }

    for(int i=b;i<d-1;i++){
        if(s[i]=='#'&&s[i+1]=='#'){
            flag0=false;
        }
    }

    s[d]='#';

    //cout<<s<<endl;

    for(int i=a;i<c-1;i++){
        if(s[i]=='#'&&s[i+1]=='#'){
            if(i!=d&&i+1!=d){
                cout<<"No"<<endl;
                return 0;
            }
            flag1=false;
        }
    }

    //dump(flag1);
    s[d]='.';
    for(int i=b;i<d;i++){
        if(s.substr(i-1,3)=="...")flag1=true;
    }

  

    
    if(!flag0||!flag1)cout<<"No"<<endl;
    else cout<<"Yes"<<endl;




 
}

/*
15 1 3 15 13
.#.#.#.#..#....

15 1 2 15 13
...#.#.#.#.#...

15 1 3 15 12
.#.#.#.#..#....

15 1 3 15 13
...#.#.#.#...#.
*/

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

int prime[1299710];
int max_n = 1299711;
int main(){
  prime[0] = prime[1] = 1;
  for(int i = 0; i * i <= max_n; i++){
    if(!prime[i]){
      for(int j = i; i * j < max_n; j++){
        prime[i * j] = 1;
      }
    }
  }
  int n;
  while(cin >> n, n){
    int left, right;
    left = right = n;
    while(prime[left] && left >= 2) left--;
    while(prime[right]) right++;
    cout << right - left << endl;
  }
  return 0;
}



Measured memory_bytes: 8168
N = gets.to_i
ABC = readlines.map { |abc| abc.split.map(&:to_i) }
happy = []

N.times do |i|
  if i == 0
    happy << ABC[0]
  else
    tmp_a = happy[i - 1][1, 2].max + ABC[i][0]
    tmp_b = [happy[i - 1][0], happy[i - 1][2]].max + ABC[i][1]
    tmp_c = happy[i - 1][0, 2].max + ABC[i][2]
    happy << [tmp_a, tmp_b, tmp_c]
  end
end

puts happy[-1].max

Measured memory_bytes: 27132
#include <iostream>
#include <string>
using namespace std;
int main(void){
    // Your code here!
    string str;
    cin >> str;

    if(str == "SUN")
            cout << 7<< endl;
    else if(str == "MON")
            cout << 6<< endl;
    else if(str== "TUE")
            cout <<5 << endl;
    else if(str == "WED")
            cout << 4<< endl;
    else if(str == "THU")
            cout << 3<< endl;
    else if(str == "FRI")
            cout << 2<< endl;
    else if(str == "SAT")
            cout << 1<< endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <cmath>
#include <numeric>
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <list>
#include <unordered_map>
#include <tuple>
#include <complex>


#define FOR(i, a, b)		for(int i = (int)(a); i < (int)(b); ++i)
#define FORE(i, a, b)		for(int i = (int)(a); i <= (int)(b); ++i)
#define REP(i, n)			FOR(i, 0, n)
#define REPE(i, n)			FORE(i, 0, n)
#define ALL(x)				(x).begin(),(x).end()
#define DEBUG_DC(x)			cout << #x << ": " << x << endl
#define ANS_DC(x)			cout <<  x << endl
#define V_TYPE				int
#define INF					1e4+1

using namespace std;
typedef long long ll;
typedef vector<V_TYPE> vdef;
typedef vector<vdef> vvdef;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T>inline T mygcd(T a, T b) { return b ? mygcd(b, a%b) : a; }
template<typename T>inline T mylcm(T a, T b) { return a * b / mygcd(a, b); }


int main()
{

	string s;
	cin >> s;

	int MM[2] = { 0,0 };

	if (s[0] == '0')
	{
		if (s[1] != '0') MM[0] = 1;
	}
	else if (s[0] == '1')
	{
		if (s[1] == '0' || s[1] == '1' || s[1] == '2') MM[0] = 1;
	}

	if (s[2] == '0')
	{
		if (s[3] != '0') MM[1] = 1;
	}
	else if (s[2] == '1')
	{
		if (s[3] == '0' || s[3] == '1' || s[3] == '2') MM[1] = 1;
	}

	string ans;
	if (MM[0] == 1 && MM[1] == 1) ans = "AMBIGUOUS";
	else if (MM[0] == 1 && MM[1] == 0) ans = "MMYY";
	else if (MM[0] == 0 && MM[1] == 1) ans = "YYMM";
	else if (MM[0] == 0 && MM[1] == 0) ans = "NA";

	ANS_DC(ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) ((int)(a).size())
#define FIN ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb push_back
#define fore(i,a,b) for(int i = a; i < b; i++)
using namespace std;
typedef long long ll;

ll A[4] = {};

int main(){
  fore(x,0,4) cin >> A[x];
  fore(x,1,4) A[x] = min(A[x],2*A[x-1]);
  ll N; cin >> N; N *= 4;

  ll ans = (N/8LL) * A[3];
  N %= 8;
  ans += (N/4)*A[2];
  N %= 4;
  ans += (N/2)*A[1];
  N %= 2;
  ans += N * A[0];
  cout << ans << "\n";
}


Measured memory_bytes: 256
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		if (n == 0) {
			System.out.println(0);
			return;
		}

		PriorityQueue<Long> q = new PriorityQueue<>((a, b) -> Long.compare(b, a));
		for (int i = 0; i < n; i++) {
			q.offer(sc.nextLong());
		}

		while (m-- > 0) {
			q.offer(q.poll() / 2);
		}

		long answer = 0;
		while (!q.isEmpty()) {
			answer += q.poll();
		}

		System.out.println(answer);
	}
}


Measured memory_bytes: 63348
n,k = map(int,input().split())
l = [1,1]
for i in range(2,2000):
    l.append(l[i-1]*i)
def f(i):
    global n,k,l
    if i == 1:
        return n-k+1
    elif i - 1 > n - k :
        return 0
    else:
        tiri = l[k-1]//(l[i-1]*l[k-i])
        aka = n - k
        aka = aka - i + 1
        akatiri = l[i + aka ] // (l[aka] * l[i])
        #print(tiri,akatiri)
        return tiri * akatiri
for i in range(1,k+1):
    print(f(i)%(10**9 + 7))


Measured memory_bytes: 44272
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<deque>
#include<queue>
#include<stack>
using namespace std;
#define int long long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define dup(x,y) (((x)+(y)-1)/(y))
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
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; }
typedef pair<int, int>P;
const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const int INF = 1e18;
const long double PI = (acos(-1));


signed main() {
	int A, B, K;
	cin >> A >> B >> K;
	rep(i, K) {
		if (i % 2 == 0) {
			if (A & 1)A--;
			B += A / 2;
			A /= 2;
		}
		else {
			if (B & 1)B--;
			A += B / 2;
			B /= 2;
		}
	}
	cout << A << " " << B << endl;
}

Measured memory_bytes: 3564
if __name__ == "__main__":
    n = int(input())
    a = [0]
    a.extend(list(map(int, input().split())))
    a.append(0)

    all = 0
    for i in range(1, n+2):
        all += abs(a[i] - a[i-1])

    for i in range(n):
        tmp = all - abs(a[i+1] - a[i]) + abs(a[i+2] - a[i]) - abs(a[i+2] - a[i+1])
        print(tmp)


Measured memory_bytes: 13920
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;



int main(void) {
    cin.tie(0); ios::sync_with_stdio(false);
    ll n,m;
    while(cin >> n >> m,n){
        vector<ll> a(n); for(auto& in:a) cin >> in;
        ll ans = -1;
        for(int i = 0 ; i < n;i++){
            for(int j = i+1; j < n;j++){
                if(a[i] + a[j] <= m) ans = max(ans,a[i]+a[j]);
            }
        }
        
        if(ans == -1) cout << "NONE" << endl;
        else cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 3132
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let t1: u64 = sc.read();
    let t2: u64 = sc.read();
    let a1: u64 = sc.read();
    let a2: u64 = sc.read();
    let b1: u64 = sc.read();
    let b2: u64 = sc.read();

    let sum_a = t1 * a1 + t2 * a2;
    let sum_b = t1 * b1 + t2 * b2;
    if sum_a == sum_b {
        println!("infinity");
        return;
    }

    let ((a1, a2), (b1, b2)) = if sum_a > sum_b {
        ((b1, b2), (a1, a2))
    } else {
        ((a1, a2), (b1, b2))
    };

    if a1 < b1 {
        println!("0");
        return;
    }

    assert!(a1 > b1);
    assert!(a2 < b2);
    let (a1, b1) = (a1 - b1, 0);
    let (a2, b2) = (0, b2 - a2);
    let d1 = (a1 - b1) * t1;
    let d2 = (b2 - a2) * t2;
    assert!(d2 > d1);
    let d = d2 - d1;

    if d > d1 {
        println!("1");
        return;
    }
    assert!(d1 >= d);
    if d1 % d == 0 {
        let x = d1 / d;
        println!("{}", 2 * x);
    } else {
        let x = (d1 + d - 1) / d;
        assert!(x > 0);
        println!("{}", 2 * x - 1);
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: std::ops::Deref<Target = str>>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


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

ll w, h, x, y;
int can;
int main(){
  cin >> w >> h >> x >> y;
  if(x == (double)w/2 && y == (double)h/2) can = 1;
  printf("%.9lf ", w*(double)h/2.0);
  printf("%d", can);
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int main()
{
    long long a;
    cin >> a;
    long long ls = a / 11;
    long long lss = a % 11;
    long long ans = ls*2;
    if (ls * 11 != a)
    {
        if (lss > 6)
            ans+=2;
        else
            ans++;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
 
#define se second
#define sz(x) (int)(x.size())
#define ll long long
#define rep(i,x,y) for(int i = x; i <= y; ++i)
#define repr(i,x,y) for(int i = x; i >= y; --i)
#define pb push_back
#define mp make_pair
#define fi first
#define ull unsigned ll
 
#define pi 3.14159265358979
 
 
using namespace std;
 
const int N = (int)(1e6) + 322;
const ll INF = 2e18 + 17;
const int inf = 2e9;
const int mod = 1000000007;
const double eps = 1e-9;
 
int gcd(int a, int b) { return b ? gcd (b, a % b) : a; }
 
int nbr_bits(int a){
	return log2(a)+1;
}
 
 
int fastpow(int a, int n, int mod) {
    if(n==0)
    	return 1;
    if(n%2==0){
    	int res = fastpow(a,n/2,mod);
    	res*=res;
    	res%=mod;
    	return res;
	}
	int res = (fastpow(a,n-1,mod)*a)%mod;
	return res;
    
}
 
// ---------------------------------------------------
int p[N];
 
int find(int u){
	if(p[u]==u) return u;
	return p[u] = find(p[u]);
}
 

 
 
signed main()
{
 
	ios_base::sync_with_stdio(false);
	
	int n, m, ans = -1;
	cin >> n >> m;
	
	rep(i, 1, n) p[i] = i;
	
	while(m--){
	
	  int a, b;
	  cin >> a >> b;
	  
	  a = find(a);
	  b = find(b);
	  if(a != b) p[a] = b;
	  
	}
	
	 rep(i, 1, n){
	    
	    if( p[i] == i){
	      ans++;
		 }
	    
    }
	
	cout << ans << endl;
	
	
	
	return 0;
}

Measured memory_bytes: 3980
package main

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

func main() {
	sc.Split(bufio.ScanWords)
	a, b, c, k := nextInt(), nextInt(), nextInt(), nextInt()
	var i int
	var r int
	for j := 1; j <= a && i < k; j++{
		r += 1
		i++
	}
	for x := 1; x <= b && i < k; x++{
		r += 0
		i++
	}
	for y := 1; y <= c && i < k; y++{
		r += -1
		i++
	}
	fmt.Println(r)
}

// =================================
// I/O util
// =================================

var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

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

int main(void) {
	int n, c,p,number = 0,ans;
	cin >> n >> c;
	for (int i = 0; i < c; i++) {
		cin >> p;
		number += p;
	}
	ans = number / (n + 1);
	if (number % (n + 1))ans++;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3080
#include <iostream>

 

using namespace std;

 

int main()
{
   int a, b,i;
   
   for(i=1;i<=3000;i++)
   {
       cin >> a >> b;
   
       if(a==0 && b==0){
       break;
   }
   
   if(a>b){
   a=a+b;
   b=a-b;
   a=a-b;
   }
   
   

 

   cout << a << " " << b << endl;}
}


Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<ll,ll> P;
void extended_euclid(ll x,ll y,ll *c,ll *a,ll *b){
  ll a0,a1,a2,b0,b1,b2,r0,r1,r2,q;r0=x;r1=y;a0=1;a1=0;b0=0;b1=1;
  while(r1>0){q=r0/r1;r2=r0%r1;a2=a0-q*a1;b2=b0-q*b1;r0=r1;r1=r2;a0=a1;a1=a2;b0=b1;b1=b2;}
  *c=r0;*a=a0;*b=b0;
}

ll get_inv(ll n, ll p){
  ll a,b,c;
  extended_euclid(n,p,&c,&a,&b);
  if(a<p) a+=p;
  return a%p;
}

ll fact[2000100],fact_inv[2000100];

void init() {
  fact[0]=1;
  REP(i,1,2000100) fact[i]=fact[i-1]*i%MAX;
  fact_inv[2000050]=get_inv(fact[2000050],MAX);
  rrep(i,2000050)fact_inv[i]=fact_inv[i+1]*(i+1)%MAX;
}

ll nCr(ll N,ll K){
  if(K<0||K>N)return 0;
  return fact[N]*fact_inv[K]%MAX*fact_inv[N-K]%MAX;
}

void Main() {
  ll n,m;
  cin >> n >> m;
  ll a[n];
  rep(i,n) R a[i];
  sort(a,a+n);
  init();
  ll s1=0,s2=0,c=0;
  rep(i,n) {
    c+=nCr(i-1,m-2);
    c%=MAX;
  }
  rep(i,n) {
    s1+=(a[i]+MAX)%MAX*c%MAX;
    s1%=MAX;
    s2+=(a[n-1-i]+MAX)%MAX*c%MAX;
    s2%=MAX;
    c-=nCr(n-i-2,m-2);
    c+=MAX;
    c%=MAX;
  }
  pr((s2-s1+MAX)%MAX);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 32256
N = int(input())
T, A = map(int, input().split())
H_list = []
H_list = list(map(int, input().split()))
kion = lambda k: T - k * 0.006
min = 1000
ans = 0
diff = 0
for i in range(N):
  H_list[i] = kion(H_list[i])
  diff = abs(H_list[i] - A)
  if min > diff:
    min = diff
    ans = i
print(ans+1)

Measured memory_bytes: 3064
#include<iostream>

using namespace std;
typedef unsigned long long ll;

ll L,A,B,M;
ll ten;

struct mll {
    long long x;
    mll(long long x):x(x%M){}
    mll& operator+=(const mll a) {
        (x+=a.x) %= M;
        return *this;
    }
    mll& operator-=(const mll a) {
        (x+=M-a.x) %= M;
        return *this;
    }
    mll& operator*=(const mll a) {
        (x*=a.x) %= M;
        return *this;
    }
    mll& operator/=(const mll a) {
        (x/=a.x) %= M;
        return *this;
    }
    mll& operator%=(const mll a) {
        (x%=a.x) %= M;
        return *this;
    }
    mll operator+(const mll a) {
        mll res(*this);
        return res+=a;
    }
    mll operator-(const mll a) {
        mll res(*this);
        return res-=a;
    }
    mll operator*(const mll a) {
        mll res(*this);
        return res*=a;
    }
    mll operator/(const mll a) {
        mll res(*this);
        return res/=a;
    }
    mll operator%(const mll a) {
        mll res(*this);
        return res%=a;
    }
};


mll pow_(ll a, ll b) {
    if(b == 0) return mll(1);
    if(b%2 == 1) {
        return pow_(a,b-1)*mll(a);
    } else {
        mll c = pow_(a,b/2);
        return c*c;
    }
}

mll f(ll n) {
    if(n==0) return mll(0);

    if(n%2) {    
        return f(n-1) + pow_(ten, n-1);   
    } else {
        return f(n/2)*(pow_(ten, n/2) + mll(1));
    }
}

mll g(ll n) {
    if(n==0) return mll(0);
    if(n%2) {
        return g(n-1)*mll(ten) + mll(n-1);
    } else {
        return g(n/2)*(pow_(ten, n/2)+mll(1)) + f(n/2)*mll(n/2);
    }
}


int main() {
    cin>>L>>A>>B>>M;

    ll last = A+B*(L-1);
    mll ans = 0;
    ten = 1;
    for(int k=1;k<=18;k++) {
        ll l = ten, r = ten*10-1;
        if(last < l || A > r) {
            ten*=10;
            continue;
        }
        ll a,curlast,n;
        if(A>=l) a = A;
        else {
            a = (l-A+B-1)/B*B+A;
        }

        if(a>r) {
            ten*=10;
            continue;
        }

        if(last <= r) curlast = last;
        else {
            curlast = (r-a)/B*B+a;
        }
        n = (curlast-a)/B+1;
        
        ten*=10;
        ans*=pow_(ten, n);
        ans+=mll(a)*f(n) + mll(B)*g(n);
    }

    cout<<ans.x;
    
}


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

using namespace std;

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define EPS 1e-14

#define all(v) v.begin(),v.end()
#define INF
#define mp make_pair
#define pb

#define fi first
#define se second


typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

typedef long long ll;
int s[30*2+10][30*2+10];
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int main(){
	int t=0;
	while(1){
		//cout<<++t<<endl;
		rep(y,70){
			rep(x,70){
				s[y][x]=-1;
			}
		}
		int w,h;
		cin >> w >> h;
		//cout << w << " " << h << endl;
	
		if(w==0) break;
		rep(y,h*2+1){
			rep(x,w*2+1){
				if(y==0||x==0||y==h*2||x==w*2){
					s[y][x] = -1;
				}else if(x%2==0 && y%2==0){
					s[y][x] = -1;
				}else if((x+y)%2==0){
					s[y][x] = 0;
				}else{
					cin >> s[y][x];
					if(s[y][x]==1) s[y][x]=-1;
				}
			}
		}
		// rep(y,60){
		// 	rep(x,60){
		// 		printf("%c ",(s[y][x]==-1)? '#':' ');
		// 	}
		// 	cout << endl;
		// }
		// cout << endl;

		queue<pii> que;
		que.push(mp(1,1));
		while(!que.empty()){
			int x = que.front().fi;
			int y = que.front().se;
			//cout<<"@ "<<x<<" "<<y<<endl;
			//s[y][x] = dist.front();
			if(y == h*2-1 &&x == w*2-1){
				break;
			}
			int d = s[y][x];
			rep(i,4){
				int nx = x + dx[i];
				int ny = y + dy[i];
				if( nx>=0 && ny>=0 &&
					nx<w*2+1  && ny<h*2+1  &&
					s[ny][nx]==0){
					s[ny][nx] = d+1;
					que.push(mp(nx,ny));
				}
			}
			que.pop();
		}
		// rep(y,60){
		// 	rep(x,60){
		// 		printf("%2d ",s[y][x]);
		// 	}
		// 	cout << endl;
		// }
		//cout << endl;
		if(s[h*2-1][w*2-1]==0){
			cout << 0 << endl;
		}else{
			cout << s[h*2-1][w*2-1]/2+1 << endl;
		}
		//cout<<"fin"<<endl;
	}
	return 0;
}

Measured memory_bytes: 3084
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stdlib.h>
#include <map>
#include <cmath>
#define MOD_P 1000000007
#define PI 3.14159265358979
#define ll long long
using namespace std;

double distance(pair<int, int> p1, pair<int, int> p2)
{
	double dis = 0;
	dis += (p1.first - p2.first) * (p1.first - p2.first);
	dis += (p1.second - p2.second) * (p1.second - p2.second);

	return sqrt(dis);
}

int main()
{
	int n;
	cin >> n;
	double sum = 0;
	int per = 0;

	vector<int> turn(n);
	vector<pair<int, int>> point(n);

	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		point[i].first = x;
		point[i].second = y;
		turn[i] = i;
	}

	do {
		for (int i = 1; i < n; i++) {
			sum += distance(point[turn[i]], point[turn[i - 1]]);
		}
		//printf("\n");
		per++;
	} while (next_permutation(turn.begin(), turn.end()));

	printf("%.12f", sum / per);

	return 0;
}



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

#define SZ(x) (int)((x).size())
#define xx first
#define yy second

const int N = 2e5 + 1;

int a[N];

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);
    ll ans = a[n - 1];
    for (int i = n - 2, j = n - 2; j; i--)
        for (int k = 2; k && j; k--, j--)
            ans += a[i];
    cout << ans << '\n';
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // int _; cin >> _; while (_--)
    solve();
    return 0;
}


Measured memory_bytes: 4424
_,m=map(int,input().split())
ta=[list(map(int,input().split()))+[i] for i in range(m)]
a=sorted(ta)
ans=[-1]*m
j=0
for i in range(m):
    if j!=a[i][0]:
        j=a[i][0]
        k=1
    p=str(a[i][0]).zfill(6)+str(k).zfill(6)
    ans[a[i][2]]=p
    k+=1

a.sort()
for i in range(m):
    print(ans[i])


Measured memory_bytes: 81240
#include <stdio.h>

int main(){
	int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
	
	int hasil1 = a+b;
	int hasil2 = b+c;
	int hasil3 = c+a;
	
	if(hasil1<=hasil2 && hasil1<=hasil3){
		printf("%d\n",hasil1);
	}else if(hasil2<=hasil1 && hasil2<=hasil3){
		printf("%d\n",hasil2);
	}else if(hasil3<=hasil1 && hasil3<=hasil2){
		printf("%d\n",hasil3);
	}
	
	return 0;
}

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

using namespace std;
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define ll long long
#define DBG 1
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define loop(n) rep(loop, (0), (n))
#define all(c) begin(c), end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
using pii = pair<int, int>;
// template<class T> ostream &operator<<(ostream &os,T &t){dump(t);return os;}
template <typename T, typename S>istream &operator>>(istream &is, pair<T, S> &p) { is >> p.first >> p.second; return is; }
//template <typename T, typename S>ostream &operator<<(ostream &os, pair<T, S> &p) {os << p.first << " " << p.second;return os;}

template <typename T> void printvv(const vector<vector<T>> &v) {
	cerr << endl;
	rep(i, 0, v.size()) rep(j, 0, v[i].size()) {
		if (typeid(v[i][j]).name() == typeid(INF).name() and v[i][j] == INF) {
			cerr << "INF";
		}
		else
			cerr << v[i][j];
		cerr << (j == v[i].size() - 1 ? '\n' : ' ');
	}
	cerr << endl;
}

#ifndef _DEBUG
#define printvv(...)
#endif
void YES(bool f) { cout << (f ? "YES" : "NO") << endl; }
void Yes(bool f) { cout << (f ? "Yes" : "No") << endl; }
template <class T, class U>bool chmin(T& a, U b) { if (a > b) { a = b; return true; }return false; }
template <class T, class U>bool chmax(T& a, U b) { if (a < b) { a = b; return true; }return false; }

signed main(signed argc, char *argv[]) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(12);

	int a, b; cin >> a >> b;

	cout << max({ a + b,a - b,a*b }) << endl;

	return 0;
}


Measured memory_bytes: 256