akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
#define all(x) (x).begin(),(x).end()

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

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(10);
    int R;
    cin >> R;
    cout <<R*R<< "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string>
#include <vector>
using namespace std;
int main()
{
    int a[3][3];
    int n;
    vector<int> b;
    int bingo[3][3] = {
        {0,0,0},
        {0,0,0},
        {0,0,0}
    };
    for(int i = 0;i < 3;i++){
        for(int j = 0;j < 3;j++){
            cin >> a[i][j];
        }
    }

    cin >> n;

    for(int i = 0;i < n;i++){
        int in;
        cin >> in;
        b.push_back(in);
    }

    for(int k = 0;k < n;k++){
        for(int i = 0;i < 3;i++){
            for(int j = 0;j < 3;j++){
                if(b[k] == a[i][j]){
                    bingo[i][j] = 1;
                }
            }
        }
    }

    int flag = 0;
    int yes = 0;
    for(int i = 0;i < 3;i++){
        for(int j = 0;j < 3;j++){
            if(bingo[i][j] == 1){
                flag++;
            }
            if(j == 2){
                if(flag == 3){
                    yes = 1;
                }else{
                    flag = 0;
                }
            }
        }
    }
    flag = 0;
    for(int i = 0;i < 3;i++){
        for(int j = 0;j < 3;j++){
            if(bingo[j][i] == 1){
                flag++;
            }
            if(j == 2){
                if(flag == 3){
                    yes = 1;
                }else{
                    flag = 0;
                }
            }
        }
    }
   
    if(bingo[0][0] == 1 && bingo[1][1] == 1 && bingo[2][2]){yes = 1;}
    if(bingo[0][2] == 1 && bingo[1][1] == 1 && bingo[2][0]){yes = 1;}

    if(yes){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<map>
#include<queue>
using namespace std;
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; }
const long long INF = 1LL << 60;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(){
    int64_t a,b,c,k;
    cin>>a>>b>>c>>k;
    int64_t Max=0;
    Max+=min(a,k);
    k-=a;
    k-=min(b,k);
    Max-=min(c,k);
    cout<<Max<<endl;
}


Measured memory_bytes: 3644
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <vector>

const int MOD = 1e9 + 7;
const int iINF = 2147483647 / 2;
const long long int llINF = 9223372036854775807 / 2;

using namespace std;
using ll = long long int;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;

typedef pair<ll, ll> pll;
bool paircomp(const pll &a, const pll &b) {
  if (a.first == b.first)
    return a.second < b.second;
  return a.first < b.first;
}

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define RREP(i, n) for (ll i = (n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define AUTO(i, m) for (auto &i : m)
#define ALL(a) (a).begin(), (a).end()
#define MAX(vec) *std::max_element(vec.begin(), vec.end())
#define MIN(vec) *std::min_element(vec.begin(), vec.end())
#define ARGMAX(vec)                                                            \
  std::distance(vec.begin(), std::max_element(vec.begin(), vec.end()))
#define ARGMIN(vec)                                                            \
  std::distance(vec.begin(), std::min_element(vec.begin(), vec.end()))
#define REV(T) greater<T>()
#define PQ(T) priority_queue<T, vector<T>, greater<T>>
#define VVL(a, b, c) vector<vector<ll>>(a, vector<ll>(b, c))
#define VVVL(a, b, c, d)                                                       \
  vector<vector<vector<ll>>>(a, vector<vector<ll>>(b, vector<ll>(c, d)))
#define SP(a) setprecision(a)
#define SQRT(a) sqrt((long double)(a))
#define DPOW(a, b) pow((long double)(a), (long double)(b))
#define UNIQUE(vec)                                                            \
  do {                                                                         \
    sort(ALL((vec)));                                                          \
    (vec).erase(std::unique(ALL((vec))), (vec).end());                         \
  } while (0)

ll POW(ll n, ll m) {
  if (m == 0) {
    return 1;
  } else if (m % 2 == 0) {
    ll tmp = POW(n, m / 2);
    return (tmp * tmp);
  } else {
    return (n * POW(n, m - 1));
  }
}

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll N, K;
  cin >> N >> K;
  vl h(N);
  REP(i, N) cin >> h[i];
  ll ans = 0;
  REP(i, N) if (h[i] >= K) ans++;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
double dp[301][301][301];
ll n;
double fun(ll x,ll y,ll z)
{
  if(x==0 && y==0 && z==0)
    return 0;
  if(x<0||y<0||z<0)
    return 0;
  if(dp[x][y][z]>=0)
    return dp[x][y][z];
  else
  {
    ll rem=(x+y+z);
    double nume=n+x*fun(x-1,y,z)+y*fun(x+1,y-1,z)+z*(fun(x,y+1,z-1));
    if(rem!=0 && nume!=0)
    return dp[x][y][z]=nume/rem;
  }
  
}
int main()
{
  memset(dp,-1,sizeof(dp));
  ll i,x=0,y=0,z=0;
  cin>>n;
  ll a[n];
  for(i=0;i<n;i++)
    cin>>a[i];
  for(i=0;i<n;i++)
  {
    if(a[i]==1)
      x++;
    else if(a[i]==2)
      y++;
    else if(a[i]==3)
      z++;
  
  }
  ll zero=n-(x+y+z);
  cout<<fixed<<setprecision(9)<<fun(x,y,z);
}

Measured memory_bytes: 216888
#include<bits/stdc++.h>
using namespace std;
int main(){
	double a, b, c, d, e, f;
	while (cin >> a >> b >> c >> d >> e >> f) {
		double x = (c*d - a*f) / (b*d - a*e);
        double ans1 = (1000*((c - b*x) / a))/1000;
        double ans2 = (1000*x)/1000;
		cout << fixed << setprecision(3) << ans1 << " " << ans2 << endl;
	}
	return 0;
}


Measured memory_bytes: 3232
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
typedef long long ll;
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(a > b) { a=b; return 1; } return 0; }
int main()
{
  int n;cin >> n;
  vector<ll> a(n);
  rep(i,n) cin >> a[i];

  if(n % 2 == 0) {
    vector<vector<ll>> dp(n/2 + 1, vector<ll>(2, -1e+15));
    dp[0][0] = 0;
    rep(i,n/2) {
      chmax(dp[i+1][0], dp[i][0] + a[i*2]);
      chmax(dp[i+1][1], dp[i][0] + a[i*2 + 1]);
      chmax(dp[i+1][1], dp[i][1] + a[i*2 + 1]);            
    }
    cout << max(dp[n/2][0], dp[n/2][1]) << "\n";
  }
  else {
    vector<vector<ll>> dp(n/2 + 1, vector<ll>(3, -1e+15));
    dp[0][0] = 0;
    rep(i,n/2) {
      chmax(dp[i+1][0], dp[i][0] + a[i*2]);
      chmax(dp[i+1][1], dp[i][0] + a[i*2 + 1]);
      chmax(dp[i+1][1], dp[i][1] + a[i*2 + 1]);
      chmax(dp[i+1][2], dp[i][0] + a[i*2 + 2]);      
      chmax(dp[i+1][2], dp[i][1] + a[i*2 + 2]);
      chmax(dp[i+1][2], dp[i][2] + a[i*2 + 2]);      
    }
    cout << max(dp[n/2][0], max(dp[n/2][1], dp[n/2][2])) << "\n";
  }
  
  
  return 0;
}


Measured memory_bytes: 10388
s=input()
mod=10**9+7
n,a,b,c=1,0,0,0
for i in s:
  if i=="A":
    a+=n
  if i=="B":
    b+=a
  if i=="C":
    c+=b
  if i=="?":
    n,a,b,c=3*n,3*a+n,3*b+a,3*c+b
  n%=mod
  a%=mod
  b%=mod
  c%=mod
print(c)

Measured memory_bytes: 73516
#include<stdio.h>
int main(void){
   int a,b,d,r;
   double f;
   scanf("%d %d",&a,&b);
   d=a/b;
   r=a%b;
   f=(double)a/b;
   printf("%d %d %f\n",d,r,f);

    return 0;
}

Measured memory_bytes: 636
#include <iostream>
#include <cstring>
using namespace std;
int N, M, R;
int d[201][201];
int r[9];
int INF = 1 << 29;
int res = INF;
bool used[9];
void dfs(int c, int las, int dist) {
	if (c == R + 1) {
		if (res > dist) res = dist;
		return;
	}
	else {
		for (int i = 1; i <= R; ++i) {
			if (!used[i]) {
				used[i] = true;
				if (las == -1) dfs(c + 1, i, 0);
				else dfs(c + 1, i, dist + d[r[las]][r[i]]);
				used[i] = false;
			}
		}
	}
}
int main(void) {
	cin >> N >> M >> R;
	memset(used, false, 9);
	for (int i = 1; i <= R; ++i) {
		cin >> r[i];
	}
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= N; ++j) {
			if (i != j) {
				/*d[i][j] = 0;
			}
			else {*/
				d[i][j] = INF;
			}
		}
	}
	for (int i = 1; i <= M; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		if (d[a][b] > c) {
			d[a][b] = d[b][a] = c;
		}
	}
	for (int k = 1; k <= N; ++k) {
		for (int i = 1; i <= N; ++i) {
			for (int j = 1; j <= N; ++j) {
				if (d[i][j] > d[i][k] + d[k][j]) {
					d[i][j] = d[i][k] + d[k][j];
				}
			}
		}
	}
	dfs(1, -1, 0);
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 384
N=int(input())
from collections import defaultdict
dic=defaultdict(int)

for i in range(1,N+1):
  n=str(i)
  dic[(int(n[0]),int(n[-1]))]+=1
  
ans=0
for i in range(1,10):
  for j in range(1,10):
    ans+=dic[(i,j)]*dic[(j,i)]
    
print(ans)

Measured memory_bytes: 3444
#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    #define rep(i,a,b) for(int i=(a);i<=(b);i++)
    #define mem(a,x) memset((a),x,sizeof (a))
    #define lson l,mid,rt<<1
    #define rson mid+1,r,rt<<1|1
    const LL LLINF = 0x3f3f3f3f3f3f3f3f;
    const int maxn=100+10;
    char s[maxn];
    int main() {
    #ifdef _DEBUG
        freopen("data.in", "r", stdin);
    #endif
        ios::sync_with_stdio(false);
        LL k;
        while(cin>>s>>k){
            LL p=0;
            int i=0;
            int len=strlen(s);
            char c=s[i];
            p=c=='1'?1:LLINF;
            while(i<len&&p<k){
                c = s[++i];
                if(c!='1') p=LLINF;
                else {
                    p ++;
                }
            }
            cout<<c<<endl;
        }
        return 0;
    }

Measured memory_bytes: 256
int main(void)
{ int a,b,d,r;
  double f;
  scanf("%d %d" ,&a,&b);
  d = a/b;
  r = a%b;
  f = (double)a / (double)b;
        
  printf("%d %d %f\n" ,d,r,f);
  return 0;
}

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

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

    int n;
    cin >> n;
    vector<int> C(n - 1), S(n - 1), F(n - 1);
    REP(i, n - 1) cin >> C[i] >> S[i] >> F[i];

    for(int i = 0; i < n; i++){
        int cost = 0;
        for(int j = i; j < n - 1; j++){
            if(cost < S[j]) cost = S[j];
            else if(cost % F[j] == 0); //駅jの周期F[j]に合致 -> 待ち時間無し
            else cost += F[j] - cost % F[j];
            cost += C[j];
        }
        cout << cost << endl;
    }

    return 0;
}

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


// 最小公倍数を求める
int euqlid (int a, int b){
  int temp;
  temp = a % b;
  if(temp == 0)return b;
  return euqlid(b,temp);
}
ll conbination(ll a,ll b){
  ll u = 1;
  ll d = 1;
  while(b != 0){
    u *= a;
    d *= b;
    a--;
    b--;
  }
  return u / d;
}
int strtoint(char s){
  return (int(s-'0'));
}
char changeS(char alpha){
  if(0x41 <= alpha and alpha <= 0x5A)return (alpha + 0x20);
  else if(0x61 <= alpha and alpha <= 0x7A)return (alpha - 0x20);
  return alpha;
}
int fact(int n){
  if(n == 1)return 1;
  return n * fact(n-1);
  }
int ceil(int a,int b){
  // a/bの切り上げを考える
  return (a+b-1)/b;
}


int main(){ 
  int a;
  cin >> a;

  cout << a + pow(a,2) + pow(a, 3) << endl;

}

Measured memory_bytes: 4192
#include<bits/stdc++.h>
using namespace std;
int n,ma,mb;
int a[50],b[50],c[50];
typedef vector<pair<pair<int,int>,int> > vec;
int mincst1[500][500];
int mincst2[500][500];
vec aa,bb;
void dfs(int cur,int x,int y,int z,int lst,vec &ok){
	if(cur>=lst+1){
		ok.push_back(make_pair(make_pair(x,y),z));
		return;
	}
	else{
		dfs(cur+1,x,y,z,lst,ok);
		dfs(cur+1,x+a[cur],y+b[cur],z+c[cur],lst,ok);
	}
}
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>ma>>mb;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i]>>c[i];
	}
	memset(mincst1,63,sizeof(mincst1));
	memset(mincst2,63,sizeof(mincst2));
	dfs(1,0,0,0,n/2,aa);
	dfs(n/2+1,0,0,0,n,bb);
	for(int i=0;i<aa.size();i++)
	{
		mincst1[aa[i].first.first][aa[i].first.second]=min(mincst1[aa[i].first.first][aa[i].first.second],aa[i].second);
	}
	for(int i=0;i<bb.size();i++)
	{
		mincst2[bb[i].first.first][bb[i].first.second]=min(mincst2[bb[i].first.first][bb[i].first.second],bb[i].second);
	}
	int res=1e9;
	for(int i=ma;i<=400;i+=ma){
		int j=i/ma*mb;
		if(j>400)
			continue;
		for(int k=0;k<=i;k++){
			for(int l=0;l<=j;l++){
				res=min(res,mincst1[k][l]+mincst2[i-k][j-l]);
			}
		}
	}
	if(res==1e9)
		res=-1;
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 34792
#include <stdio.h>
#include <string.h>

#define KIJI 100

int main(void)
{
	int n;
	int kiji, top;
	int cal[101];
	int i, j;
	int pizza[101];
	int max;
	
	scanf("%d", &n);			//	トッピングの種類
	scanf("%d%d", &kiji, &top);	//	価格
	scanf("%d", &cal[KIJI]);	//	生地のカロリー
	for (i = 0; i < n; i++){
		scanf("%d", &cal[i]);
	}
	
	for (i = 0; i < n; i++){
		for (j = 0; j < n - 1; j++){
			if (cal[j] < cal[j + 1]){
				int tmp = cal[j];
				cal[j] = cal[j + 1];
				cal[j + 1] = tmp;
			}
		}
	}
	
	max = 0;
	for (i = 0; i < n + 1; i++){
		pizza[i] = cal[KIJI];
	}
	for (i = 0; i < n + 1; i++){
		for (j = 0; j < i; j++){
			pizza[i] += cal[j];
		}
		pizza[i] /= top * i + kiji;
		if (max < pizza[i]){
			max = pizza[i];
		}
	}
	printf("%d\n", max);
	
	return (0);
}

Measured memory_bytes: 596
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define in(n) for(int i=0;i<n;i++)
#define inj(n) for(int j=0;j<n;j++)
#define itn int
#define ll long long 
#define ull unsigned ll
#define int ll int
#define S second 
#define F first 
#define mod 1000000007
#define globalbool 2000000
#define pii pair<int,int>
using namespace std;
using namespace std::chrono;
int A[3010][3010]={0};
int cons[3010][3010]={0};//T=1,L=2,D=3
vector<char>slcs;
int lcs(string s,string t,int m,int n)
{
	for(int i=1;i<=m;i++)//first string
	{
		for(int j=0;j<=n;j++)
		{
			if(s[i-1]==t[j-1])
			{
				A[i][j]=A[i-1][j-1]+1;
				cons[i][j]=3;
			}
			else
			{
				A[i][j]=max(A[i][j-1],A[i-1][j]);
				if(A[i][j]==A[i][j-1])
				{
					cons[i][j]=2;
				}
				else
				{
					cons[i][j]=1;
				}
			}
		}
	}
	int i=m,j=n;
	while(i>0 and j>0)
	{
		if(cons[i][j]==3)
		{
			slcs.push_back(s[i-1]);
			i--;j--;
		}
		else if(cons[i][j]==2)
		{
			j--;
		}
		else if(cons[i][j]==1)
		{
			i--;
		}
	}

}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	auto start = high_resolution_clock::now();
	string s,t;
	cin>>s>>t;
	int m=s.size(),n=t.size();
	lcs(s,t,m,n);
	reverse(slcs.begin(),slcs.end());
	int sz=slcs.size();
	in(sz)
	{
		cout<<slcs[i];
	}
	cout<<endl;
	auto stop = high_resolution_clock::now();
    //auto duration = duration_cast<microseconds>(stop - start); 
  
    //cout << "Time taken by function: "
    //<< duration.count() << " microseconds" << endl;
}

Measured memory_bytes: 141568
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;

int main(){
    ll n, m; cin >> n >> m;
    if(n > m) swap(n,m);
    if(n==1){
        if(m==1){
            cout << 1 << endl;
            return 0;
        }else{
            cout << m-2 << endl;
        }
    }else{
        cout << (n-2)*(m-2) << endl;
    }
}

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

using namespace std;

#define REP(i,m) for(long long i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define INF 1000000000
#define INFL (1LL << 60)
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int
#define P pair<ll, ll>

struct point {int x, y, ind;};
struct edge {int from, to, cost;};

int p[200001];
int r[200001];

void init(int n){
  REP(i, n){
    p[i] = i;
    r[i] = 0;
  }
  return;
}

int find(int x){
  return (p[x] == x ? x : p[x] = find(p[x]));
}

void unite(int x, int y){
  x = find(x);
  y = find(y);
  if(x == y) return;
  if(r[x] < r[y]) p[x] = y;
  else{
    p[y] = x;
    if(r[x] == r[y]) r[x]++;
  }
}

bool same(int x, int y){
  return find(x) == find(y);
}

bool px(point p1, point p2){
  return p1.x < p2.x;
}

bool py(point p1, point p2){
  return p1.y < p2.y;
}

bool ec(edge e1, edge e2){
  return e1.cost < e2.cost;
}

int main(){
  int n;
  cin >> n;
  point p[n];
  REP(i, n){
    int x, y;
    cin >> x >> y;
    p[i] = {x, y, (int)i};
  }
  sort(p, p+n, px);
  vector<edge> v;
  REP(i, n-1){
    v.pb({p[i].ind, p[i+1].ind, p[i+1].x - p[i].x});
  }
  sort(p, p+n, py);
  REP(i, n-1){
    v.pb({p[i].ind, p[i+1].ind, p[i+1].y - p[i].y});
  }
  ll ans = 0;
  sort(ALL(v), ec);
  init(n);
  REP(i, v.size()){
    if(!same(v[i].from, v[i].to)){
      ans += v[i].cost;
      unite(v[i].from, v[i].to);
    }
  }
  cout << ans << endl;
	return 0;
}

Measured memory_bytes: 6132
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            prev = ((self.size[x] * (self.size[x]-1)) + (self.size[y] * (self.size[y]-1))) // 2
            self.size[x] += self.size[y]
            return ((self.size[x] * (self.size[x]-1)) // 2 - prev)
        return 0            
    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
      
n,m = map(int, input().split())
ab = list(reversed([list(map(int, input().split())) for i in range(m)]))
now = n * (n-1) // 2 
ans = [now]
U = UnionFind(n)                    
for a,b in ab[:-1]:
  minus = U.union(a-1,b-1)
  now -= minus
  ans.append(now)
ans.reverse()
for i in ans:
  print(i)

Measured memory_bytes: 104152
#include<stdio.h>
int main(){
	int huruf, hurufKecil, hurufBesar;
	
	scanf("%s", &huruf);
	
	if(huruf >= 'a' && huruf <= 'z'){		
		puts("a");		
	}
	else{					
		puts("A");		
	}
	
	return 0;
}

Measured memory_bytes: 1588
/*****************************************************
 				*	Logged in : HABIBUR RAHMAN						 *
				*	Dept	  : COMPUTER SCIENCE AND ENGINEERING	 *
				*													 *
				*	KHULNA UNIVERSITY OF ENGINEERING AND TECHNOLOGY  *
				******************************************************/


#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<string> vs;
typedef pair<ll,ll> pll;
#define fast_io 			ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(v) 				v.begin(),v.end()
#define allr(v) 			v.rbegin(),v.rend()
#define rep(i,a,b) 			for(ll i=a;i<=b;i++)
#define rep0(i,n)			for(ll i=0;i<n;i++)
#define rrep0(i, n) 		for(ll i=(ll)(n);i>0;--i)
#define rrep(i, a, b) 		for(ll i=(ll)(a);i>=(ll)(b);--i)
#define pb(z) 				push_back(z)
#define ff					first
#define ss 					second
#define caset 				int t;cin>>t;for(int tt=1;tt<=t;tt++)
#define sz(X) 				((ll)(X).size())
#define scan(X) 			scanf("%s", (X))
#define ms(v,val)			memset((v),(val),sizeof((v)))
#define ms0(X) 				memset((X), 0, sizeof((X)))
#define ms1(X) 				memset((X), -1, sizeof((X)))
#define m_p(a,b)            make_pair(a,b)
#define get_pos(c,x) 		(lower_bound(c.begin(),c.end(),x)-c.begin())
#define lcm(a,b)            (a*b)/__gcd(a,b)
#define INF9                1000000010
#define INF18               4000000000000000010
#define bpll(a)             __builtin_popcountll(a)
#define sqr(a)              ((a)*(a))
#define nl					"\n"
#define mod					1e9+7;
#define mx_el(v)			*max_element(all(v));
#define mn_el(v)			*min_element(all(v));
#define pcase(z,x)    		cout<<"Case "<<z<<": "<<x<<"\n"
const double pi = 2*acos(0) ;
#define display(v)			vi :: iterator it;for(it=(v).begin();it!=(v).end();it++){cout << *it << " " ;}cout << endl;
#define taking(n,v) 		for(ll i=0;i<(n);i++){ll inp;cin>>inp;(v).push_back(inp);}

void start(){
      #ifndef ONLINE_JUDGE 
      freopen("input.txt" , "r" , stdin) ;
      freopen("output.txt" , "w" , stdout) ;
      #endif
}
bool is(string s1,string s2){
	if(sz(s1)!=sz(s2))return false;
	rep0(i,sz(s1)){
		if(s1[i]!='.'){
			if(s1[i]!=s2[i]){
				return false;
			}
		}
	}
	return true;
}
void solve()
{
 	 ll n,cnt=0,i=1;cin>>n;
 	 while(n>0){
 	 	n-=i;
 	 	cnt++;
 	 	i++;
	  }
	  cout << cnt ;
}
int main() {
	fast_io
	//start();
    //caset{
    	//cout << "Case " << tt << ": ";
		  solve();
	//}
	
	return 0;
}

Measured memory_bytes: 3656
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpii;
typedef vector<pair<ll, ll>> vpll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vc> vvc;
typedef vector<vs> vvs;
typedef vector<vll> vvll;
typedef map<int, int> mii;
typedef set<int> si;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define arep(i, v) for (auto i : v)
#define irep(it, stl) for (auto it = stl.begin(); it != stl.end(); it++)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STLL(s) strtoll(s.c_str(), NULL, 10)
#define mp(p, q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define fi first
#define se second
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -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;
}
template <class T>
inline void dump(T& v) {
    irep(i, v) { cout << (*i) << ((i == --v.end()) ? '\n' : ' '); }
}
inline string getline() {
    string s;
    getline(cin, s);
    return s;
}
inline void yn(const bool b) { b ? fin("yes") : fin("no"); }
inline void Yn(const bool b) { b ? fin("Yes") : fin("No"); }
inline void YN(const bool b) { b ? fin("YES") : fin("NO"); }
struct io {
    io() {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
};
const int INF = INT_MAX;
constexpr ll LLINF = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr ld EPS = 1e-11;

/* --------------------   ここまでテンプレ   -------------------- */





int main() {
    
    int n,x,t;
    cin>>n>>x>>t;
    cout<<(int)ceil(double(n)/x)*t<<endl;
}


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

ll cnt(string &S) {
    int len = S.size();
    bool change[len];
    ll res = 0;
    fill(change, change + len, false);
    for(int i = 1; i < len; ++i) {
        if(S[i-1] == S[i]) {
            if(change[i-1]) continue;
            change[i] = true; ++res;
        }
    }
    return res;
}

int main() {
    ll K;
    string S;
    cin >> S;
    cin >> K;
    ll len = S.size();
    int p;
    for(p = 0; p < len && S[p] == S[len-1]; ++p);
    string S1 = S.substr(0, p);
    string S2 = S.substr(p, len - p) + S.substr(0, p);
    string S3 = S.substr(p, len - p);
    /*
    cout << S1 << endl;
    cout << S2 << endl;
    cout << S3 << endl;
    */
    bool sm = true;
    for(int i = 1; i < S.size(); ++i) if(S[i-1] != S[i]) sm = false;

    if(sm) cout << K*len/2 << endl;
    else cout << cnt(S1) + cnt(S3) + (K-1)*cnt(S2) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())
#define fi first
#define se second
#define pii pair<int, int>

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, a, b;
    cin >> n >> a >> b;
    int ans = (n - 1) * b + a - ((n - 1) * a + b) + 1;
    cout << max(ans, 0ll) << "\n"; 
}

Measured memory_bytes: 256
N = int(input())
K = [int(i) for i in input().split()]

if K.count(0) > 0:
    print(0)
else:
    ans = 1
    burst = False
    for k in K:
        ans *= k
        if ans > 10**18:
            burst = True
            break
    if burst:
        print(-1)
    else:
        print(ans)


Measured memory_bytes: 21596
#include <stdio.h>

int main() {
    int cc;
    scanf("%d", &cc);
    int AC=0, TLE=0, WA=0, RE=0;
    for(int i = 0; i < cc; i++){
   char k[100];
   scanf("%s", k);
    if(k[0] == 'A'){
        AC++;
     }
     if(k[0] == 'T'){
       TLE++;
     }
     if(k[0]== 'W'){
         WA++;
     }
     else if(k[0]== 'R'){
        RE++;
     }
   

    }

printf(" AC x %d\n WA x %d\n TLE x %d\n RE x %d\n", AC, WA, TLE, RE); 

     return 0;
}

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

int main() {
	int n;
	scanf("%d", &n);
	
	bool chk = false;
	while(n>0) {
		if(n%10==7)chk = true;
		n/=10;
	}
	puts(chk?"Yes":"No");
	
	return 0;
}

Measured memory_bytes: 3752
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

signed main() {
	int n;scanf("%d",&n);
	set<int>s;
	rep(i,n){
		int a;scanf("%d",&a);
		if(s.count(a))s.erase(a);
		else s.insert(a);
	}
	cout<<s.size()<<endl;
}


Measured memory_bytes: 4864
#include <iostream>
inline int max(int a, int b){return (a>b)? a:b;}
inline int min(int a, int b){return (a<b)? a:b;}

using namespace std;
int main(void){
    int n, m;
    cin >> n >> m;
    int h[n];
    char is_checked_bad[n];
    for(int i=0;i<n;i++){
        cin >> h[i];
        is_checked_bad[i]=0;
    }
    for(int i=0;i<m;i++){
        int ai, bi;
        cin >> ai >> bi;
        ai--; bi--; //because index starts from 0
        if(h[ai]>h[bi]){
            is_checked_bad[bi]=1;
        }else if(h[ai]<h[bi]){
            is_checked_bad[ai]=1;
        }else{
            //same height
            is_checked_bad[bi]=1;
            is_checked_bad[ai]=1;
        }
    }
    int counter=n;
    for(int i=0;i<n;i++){
        if(is_checked_bad[i]) counter--;
    }
    cout << counter << endl;
    return 0;
}

Measured memory_bytes: 4124
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>

using namespace std;

int main(){
	int n;
	cin >> n;
	vector<int> t(n + 1), v(n + 1);
	for(int i = 1; i <= n; i++){
		cin >> t[i];
	}
	for(int i = 1; i <= n; i++){
		cin >> v[i];
	}
	t.push_back(0);
	v.push_back(0);
	vector<int> l(1), r(1);
	for(int i = 1; i <= n + 1; i++){
		l.push_back(r[i - 1]);
		r.push_back(l[i] + t[i]);
	}
	vector<double> v2(1);
	for(double i = 0.5; i <= (double)r.back(); i += 0.5){
		double minv = 101.0;
		for(int j = 0; j < v.size(); j++){
			double tmp;
			if(i < l[j]){
				tmp = v[j] + l[j] - i;
			}else if(r[j] < i){
				tmp = v[j] + i - r[j];
			}else{
				tmp = v[j];
			}
			minv = min(minv, tmp);
		}
		v2.push_back(minv);
	}
	double ans = 0.0;
	for(int i = 0; i < v2.size() - 1; i++){
		ans += (v2[i] + v2[i + 1])  * 0.25;
	}
	cout << fixed << setprecision(5) << ans << endl;
	return 0;
}

Measured memory_bytes: 896
//                                                  '-.-'
   //                                         ()      __.'.__
   //                                      .-:--:-.  |_______|
   //                               ()      \____/    \=====/
   //                               /\      {====}     )___(
   //                    (\=,      //\\      )__(     /_____\
   //    __    |'-'-'|  //  .\    (    )    /____\     |   |
   //   /  \   |_____| (( \_  \    )__(      |  |      |   |
   //   \__/    |===|   ))  `\_)  /____\     |  |      |   |
   //  /____\   |   |  (/     \    |  |      |  |      |   |
   //   |  |    |   |   | _.-'|    |  |      |  |      |   |
   //   |__|    )___(    )___(    /____\    /____\    /_____\
   //  (====)  (=====)  (=====)  (======)  (======)  (=======)
   //  }===={  }====={  }====={  }======{  }======{  }======={
   // (______)(_______)(_______)(________)(________)(_________)
   //
   // Credits :- Joan G. Stark
   //|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|
   //|                      AUTHOR - KASPAROVIAN                                     |
   //|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define frr(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fr first
#define sc second
#define mk make_pair
#define endl '\n'
#define MOD 1000000007
#define in insert
#define sz(x) (ll)(x).size()
#define mem(a,b) memset(a,b,sizeof(a))
#define int long long
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pi;
typedef pair<int,pi> ppi;
typedef vector<vi> graph;
template<class T> void mxi(T & a, const T & b) { a = max(a, b); }
template<class T> void mni(T & a, const T & b) { a = min(a, b); }
ld EPS=1e-9;
int dp[2020],sm;
int go(int sum)
{
	if(sum==0)
		return 1;
	int &e=dp[sum];
	if(e==-1)
	{
		e=0;
		for(int i=3;i<=sum;i++)
		{
			e=(e+go(sum-i))%MOD;
		}
	}
	return e;
}
void solve()
{
  mem(dp,-1);
  cin>>sm;
  cout<<go(sm)<<endl;

}
signed main()
{
  fast;
  int t,tab;
  t=1;;
  tab=t;
  while(t--)
  {
    //cout<<"Case #"<<(tab-t)<<": ";
    solve();
  }
}
//APPROACHING A QUESTION
//+ Think of binary search (max of min etc also if n<=2*10^5)
//+ Think of common dp states (Even if it appears as maths but constraints are small)
//+ Check constraints
//+ Keep calm and enjoy the question
//+ Be sure to remove MOD from binpow (if needed)
//+ Try bidirectional analysis for constructive questions
//+ If given some sequence try thinking of prefix sums
//+ If constraints are too large maybe its simple maths
//+ In questions with binary operations think of bits independently and also the change pattern
//+ If two or more binary operations are given mostly there is a relation between them and an arithmatic operator

Measured memory_bytes: 3660
import java.io.*;
import java.math.BigInteger;
import java.util.*;

 
public class Main{
	/*
	 * use Integer for sorting
	 * avoid object comparison
	 * NEVER APPEND A STRING -> APPEND char by char
	 * 
	 */
	public static class FastReader {
		BufferedReader br;
		StringTokenizer root;
		
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() {
			while (root == null || !root.hasMoreTokens()) {
				try {
					root = new StringTokenizer(br.readLine());
				} catch (Exception r) {
					r.printStackTrace();
				}
			}
			return root.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());
		}
 
		double nextDouble() {
			return Double.parseDouble(next());
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception r) {
				r.printStackTrace();
			}
			return str;
		}
	}
	
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	static long mod = (long) (1e9+7);
	static long cf = 998244353;
    static final long MAX = (long) 1e8;
    public static List<Integer>[] edges;
    public static int[][] parent;
    public static long[] fac;
    public static int N = 400000+200;
    public static int x = 0;
    public static boolean[] visited;
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		
		int[] a = new int[3];
		a[sc.nextInt()-1] = 1;
		a[sc.nextInt()-1] = 1;
		for(int i=0;i<a.length;++i) 
			if(a[i] == 0)
			out.print(i+1);
		
		out.close();
	}
}

Measured memory_bytes: 22868
def main():
  n, y = map(int, input().split())
  y //= 1000
  for i in range(n + 1):
    if i * 10 > y:
      break
    for j in range(n + 1):
      if i * 10 + j * 5 > y:
        break
      k = n - i - j
      if i * 10 + j * 5 + k == y:
        print(i, j, k)
        return
  print(-1, -1, -1)

main()

Measured memory_bytes: 9184
#include <bits/stdc++.h>
using namespace std;
int main(){
  string c;
  cin >> c;
  if(c=="A") cout << "T\n";
  if(c=="T") cout << "A\n";
  if(c=="C") cout << "G\n";
  if(c=="G") cout << "C\n";
  return 0;
}


Measured memory_bytes: 256
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size
        self.size = [1] * size

    def root(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.root(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return 0

        # 代表のランクが小さい方の親を更新
        if self.rank[x] > self.rank[y]:
            self.parent[y] = x
            self.size[x] += self.size[y]
            return self.diff_combine(self.size[x], self.size[x] - self.size[y], self.size[y])
        else:
            # 代表のランクが同じだった場合は、新代表のランクを増やす
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
            self.parent[x] = y
            self.size[y] += self.size[x]
            return self.diff_combine(self.size[y], self.size[x], self.size[y] - self.size[x])

    def diff_combine(self, num1, num2, num3):
        return (num1 * (num1 - 1) // 2) - (num2 * (num2 - 1) // 2) - (num3 * (num3 - 1) // 2)

    def same(self, x, y):
        return self.root(x) == self.root(y)


def solve(n, m, graphs):
    num = n * (n - 1) // 2
    buff = [num]
    union = UnionFind(n)

    for key in range(m - 1, 0, -1):
        x, y = graphs[key]
        diff = union.unite(x-1, y-1)
        num -= diff
        buff.append(num)

    for num in reversed(buff):
        print(num)


def main():
    n, m = map(int, input().split())

    graphs = []
    for _ in range(m):
        direction = list(map(int, input().split()))
        graphs.append(direction)

    solve(n, m, graphs)


main()


Measured memory_bytes: 35884
#include<stdio.h>
int main()
{
    int n,i;
    int a[100005],c[100005];
    scanf("%d",&n);
    for(i=0; i<n; i++)
    {
        scanf("%d",&a[i]);
        c[a[i]-1]=i+1;
    }
    for(i=0; i<n; i++)
    {
        printf("%d",c[i]);
        if(i==n-1)
        {
            break;
        }
        else
        {
            printf(" ");
        }
    }
    return 0;
}


Measured memory_bytes: 1536
/*  ex4_2
    pptenshi  */

#include<stdio.h>
#include<math.h>

int main(void) {
    int len_hour_hand,    // A
        len_minute_hand,  // B
        hour,             // H
        minute;           // M
    
    double angle_hour_hand,    // 0時からの角度
                angle_minute_hand,  // 0分からの角度
                angle_hands,        // 時針と分針がなす角
                distance;           // 短点の距離

    double pi = acos(-1);  // define pi

    //input
    scanf("%d%d%d%d", 
        &len_hour_hand, 
        &len_minute_hand, 
        &hour, 
        &minute
    );

    // calculate angle    
    angle_hour_hand = 2 * pi * (hour + minute / 60.0) / 12;
    angle_minute_hand = 2 * pi * minute / 60;
    angle_hands = fabs(angle_hour_hand - angle_minute_hand);

    // calculete distance
    distance = sqrt(
            pow(len_hour_hand, 2) + 
            pow(len_minute_hand, 2) -
            2 * len_hour_hand * len_minute_hand * cos(angle_hands)
        );
    
    // output
    printf("%.15lf\n", distance);

    return 0;
}

Measured memory_bytes: 2604
N, U, V = gets.split.map(&:to_i)
edges = (N - 1).times.map { gets.split.map(&:to_i) }
graph = Array.new(N) { [] }
edges.each do |(a, b)|
  a -= 1
  b -= 1
  graph[a].push(b)
  graph[b].push(a)
end

def dfs(graph, start)
  depths = Array.new(N)
  # u, parent, depth
  queue = [[start, nil, 0]]
  while !queue.empty?
    u, parent, depth = queue.shift
    depths[u] = depth
    graph[u].each do |v|
      next if v == parent
      queue.push([v, u, depth + 1])
    end
  end
  depths
end

t_depths = dfs(graph, U - 1)
a_depths = dfs(graph, V - 1)

ans = 0
N.times do |i|
  if t_depths[i] <= a_depths[i]
    depth = a_depths[i] - 1
    ans = depth if depth > ans
  end
end
puts ans


Measured memory_bytes: 21628
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define ll long long
#define mod 1000000007
#define rep(i, n) for (int i = 0; i < n; ++i)
using Graph = vector<vector<int>>;
#define grepq priority_queue<double, std::vector<double>, std::greater<double>>
#define all(v) v.begin(), v.end()
#define PI acos(-1) 

const ll INF = 10010001010;
const int inf = 2000000000;


typedef tuple<string, int, int> TUP;

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

int main()
{
    ll Q, H, S, D;
    ll N;
    cin >> Q >> H >> S >> D >> N;
    ll ans = 0;
    if(N == 1){
        ans = min({Q * 4, H * 2, S});
    }
    else{
        S = min({Q * 4,H * 2,S});
        D = min(D,S * 2);
        if(N % 2== 0){
            ans += min(2 * S, D) * (N / 2);
        }
        else{
            ans += S;
            ans += min(2 * S, D) * (N / 2);
        }
    }
    cout << ans << endl;
}


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

int n,d,p[200010],a[200010];
vector<pair<int,pair<int,int> > > edges;

int find_set(int x)
{
	if(p[x]==x) return x;
	else return p[x]=find_set(p[x]);
}

bool unite(int x,int y)
{
	int rootx=find_set(x),rooty=find_set(y);
	if(rootx==rooty) return false;
	else{
		p[rooty]=rootx;
		return true;
	}
}

void solve(int l,int r)
{
	if(l>=r) return;
	int m=(l+r)/2;
	
	int minv1=INF,pos1=-1;
	for(int i=l;i<=m;i++){
		int val=a[i]-d*i;
		if(val<minv1){
			minv1=val;
			pos1=i;
		}
	}
	
	int minv2=INF,pos2=-1;
	for(int i=m+1;i<=r;i++){
		int val=a[i]+d*i;
		if(val<minv2){
			minv2=val;
			pos2=i;
		}
	}
	
	for(int i=l;i<=m;i++){
		edges.push_back(make_pair(minv2+a[i]-d*i,make_pair(i,pos2)));
	}
	for(int i=m+1;i<=r;i++){
		edges.push_back(make_pair(minv1+a[i]+d*i,make_pair(pos1,i)));
	}
	solve(l,m);
	solve(m+1,r);
}

signed main()
{
	ios::sync_with_stdio(false);
	cin>>n>>d;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		p[i]=i;
	}
	solve(1,n);
	int cnt=0,ans=0;
	sort(edges.begin(),edges.end());
	for(int i=0;i<edges.size()&&cnt<n-1;i++){
		if(unite(edges[i].second.first,edges[i].second.second)){
			ans+=edges[i].first;
			cnt++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 103776
using System;

namespace AtCoderABC131B
{
    class Program
    {
        static void Main(string[] args)
        {
            int ans = 0;

            string[] s = Console.ReadLine().Split(' ');

            int N = int.Parse(s[0]);
            int L = int.Parse(s[1]);

            ans = N * (L * 2 + N - 1) / 2;


            if(L >= 0)
            {
                ans -= L;
            }
            else
            {
                if(L + N  <= 0)
                {
                    ans -= L + N - 1;
                }
            }

            Console.WriteLine(ans.ToString());
        }
    }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
//#define _GLIBCXX_DEBUG //GCC5.4.1で配列の範囲外アクセスをエラーにする

//cmdで g++ test.cpp とするとコンパイルできる
//制限1秒なら10^6は余裕 10^7は多分間に合う 10^8はよほど単純でないと厳しい

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

const int MOD=1000000007; //10^9+7
const double PI=3.1415926535;

int main(){
    int N;
    cin>>N;
    int ans=0;
    int prev=0;
    int count=0;
    for(int i=0;i<N;i++){
        int now;
        cin>>now;
        if(prev>=now){
            count++;
            ans=max(ans,count);
        }else{
            count=0;
        }
        prev=now;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fastio   ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll        long long
#define yes       printf("YES\n")
#define no        printf("NO\n")
#define pb        push_back
#define srtd(x)   sort(x.begin(),x.end())
#define rvsd(x)   reverse(x.begin(),x.end())
#define scn(n)    scanf("%lld",&n)
#define scab(a,b) scanf("%lld %lld",&a,&b)
#define pn(n)     printf("%lld",n)
#define pab(a,b)  printf("%lld %lld",a,b)
#define nl        cout<<endl
#define MAX       1000005
#define PI        acos(-1.0)
#define mmst(a,b) memset(a,b,sizeof(a));
#define FOR(i,n)  for(ll i=1;i<=n;i++)
#define LOP(i,n)  for(ll i=0;i<n;i++)
//Emama_Nahid//
using namespace std;
int main()
{
    fastio;
    ll n,m,i,j,k,c=0;
    string s,p;
    cin>>s>>p;
    for(i=0;i<3;i++)
    {
        if(s[i]==p[i]) c++;
    }
    cout<<c<<endl;




    return 0;

}





Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))

# B0を決定する
# B0 = a0 + a1 + .. - (a1 + a3 + ... ) * 2
b0 = sum(a)
for i in range(1, n, 2):
    b0 -= a[i] * 2

# a0 = b0 / 2 + b1 / 2
#   <=> b1 = a0 * 2 - b0
b = [None] * n
b[0] = b0
for i in range(1, n):
    b[i] = a[i - 1] * 2 - b[i - 1]

print(' '.join(map(str, b)))

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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

typedef long long ll;
typedef pair<ll,ll> P;

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

    ll n, s, t;cin >> n >> s >> t;
    cout << "? " << s << " " << t << endl;
    ll passDist;cin >> passDist;

    vector<pair<P, ll>> v;
    for(int i = 1;i <= n;i++){
        ll a, b;
        cout << "? " << s << " " << i << endl;
        cin >> a;
        cout << "? " << i << " " << t << endl;
        cin >> b;
        if(a + b == passDist){
            v.EB(MP(a, b), i);
        }
    }

    sort(ALL(v));
    vector<int> ans;
    ll now = s;
    ll nowDist = 0;
    REP(i, v.size()){
        ll id = v[i].SE;
        ll it = v[i].FI.SE;
        cout << "? " << now << " " << id << endl;
        ll a;cin >> a;
        if(nowDist + a + it == passDist){
            ans.PB(id);
            nowDist += a;
            now = id;
        }
    }

    cout << "! ";
    REP(i, ans.size()){
        cout << ans[i] << " ";
    }
    cout << endl;

	return 0;
}



Measured memory_bytes: 4652
#include<bits/stdc++.h>
using namespace std;
int abs(int a)
{
	if(a<0)
		return -a;
	return a;
}
int min(int a,int b)
{
	if(a<=b)
		return a;
	return b;
}
int main()
{
	int n;
	cin>>n;
	vector<int> a(n),table(n,0);
	for(int i=0;i<n;i++)
		cin>>a[i];
	if(a.size()<=1)
	{
		cout<<'0';
		return 0;	
	}
	table[n-2] = abs(a[n-1]-a[n-2]);
	if(n==2)
	{
		cout<<table[n-2]<<'\n';
		return 0;
	}
	for(int i=n-3;i>=0;i-=1)
		table[i] = min(abs(a[i+1]-a[i])+table[i+1],abs(a[i+2]-a[i])+table[i+2]);
	cout<<table[0];
	return 0;
}


Measured memory_bytes: 3976
# coding: utf-8
# Your code here!
q0=int(input())
from heapq import *

low=[]
high=[]
ans=0
num=0
for _ in range(q0):
    q = [int(i) for i in input().split()]
    if q[0] == 1:
        ans+=q[2]
        num+=1
        a=q[1]
        if num==1:
            heappush(low,-a)
            df = 0
        elif num%2==1:
            centold = -low[0]
            centold2 = high[0]
            if -low[0] >= a:
                heappush(low,-a)
            else:
                c=heappushpop(high,a)
                heappush(low,-c)
            centnew = -low[0]
            if centnew < centold:
                df = 2*(centold-centnew)
            elif centnew <= centold2:
                df = 0
            else:
                df = 2*(centnew - centold2)
        else:
            centold = -low[0]
            if -low[0] > a:
                c=heappushpop(low,-a)
                heappush(high,-c)
            else:
                heappush(high,a)
            centnew = -low[0]
            if centnew < centold:
                df = (centold-centnew)
            else:
                df = (centnew - centold)
        df += abs(-low[0]-a)
#        print(low,high)        
        ans += df
            
        
        
        

    if q[0] == 2:
        print(-low[0],ans)
        



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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	int a, b, c, k;
	cin >> a >> b >> c >> k;
	if (k <= a) cout << k << "\n";
	else if (k <= a + b) cout << a << "\n";
	else cout << a - (k - a - b) << "\n";
	return 0;
}


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

int main() {
  int A, B, C;
  cin >> A >> B >> C;

  if (A == B && B == C)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3548
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(),x;
		int[] a=new int[n];
		for(x=0;x<n;x++){
		a[x] = sc.nextInt();
		}
		for(x=n-1;x>=0;x--){
		System.out.print(a[x]);
		if(x!=0){System.out.print(" ");}
		}
		System.out.println("");
	}
}

Measured memory_bytes: 19632
import java.util.*;

public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        String s=sc.next();
        int W[]=new int[n+1];
        int E[]=new int[n+1];
        for(int i=0;i<=n;i++){
            W[i]=0;
            E[i]=0;
        }
        for(int i=0;i<n;i++){
            W[i+1]=W[i];
            if(s.charAt(i)=='W') W[i+1]++;
            E[i+1]=E[i];
            if(s.charAt(i)=='E') E[i+1]++;
        }
        int ans=99999999;
        for(int i=0;i<n;i++){
            int now=W[i]+E[n]-E[i+1];
            if(ans>now) ans=now;
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 31044
#include<bits/stdc++.h>
using namespace std;
long long x,y;
int main(){
    scanf("%lld%lld",&x,&y);
    if (y==998244353){printf("%lld\n",x*2);return 0;}
    if (x%y==0)printf("-1\n");else printf("%lld\n",998244353ll*x);
}

Measured memory_bytes: 256