akhauriyash/Code-Regression huggingface dataset:
// m-solutions2020_e
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF (ll)(1e20)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    int N;
    cin >> N;
    vector<ll> X(N), Y(N), P(N);
    REP(i, N){
        cin >> X[i] >> Y[i] >> P[i];
    }

    int M2 = 1 << N;
    vector<vector<ll>> dist_x(M2, vector<ll>(N));
    vector<vector<ll>> dist_y(M2, vector<ll>(N));
    REP(m, M2){
        REP(i, N){
            ll sx = abs(X[i]);
            ll sy = abs(Y[i]);
            REP(d, N){
                if ((m >> d) & 1){
                    sx = min(sx, abs(X[i] - X[d]));
                    sy = min(sy, abs(Y[i] - Y[d]));
                }
            }
            dist_x[m][i] = sx;
            dist_y[m][i] = sy;
        }
    }

    int M3 = pow(3, N);
    vector<ll> ans(N+1, INF);
    REP(m, M3){
        int mx = 0;
        int my = 0;
        int k = 0;
        int n = m;
        REP(d, N){
            if (n % 3 == 1){
                mx += 1 << d;
                k++;
            } else if (n % 3 == 2){
                my += 1 << d;
                k++;
            }
            n /= 3;
        }

        ll sm = 0;
        REP(i, N){
            sm += P[i] * min(dist_x[mx][i], dist_y[my][i]);
        }
        ans[k] = min(ans[k], sm);
    }

    REP(i, N+1){
        print(ans[i]);
    }

    return 0;
}


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

int dp[300000];

const int inf = 1e8;

vector<vector<int>> makeCH(string S){
  int N = S.size();
  vector<vector<int>> res(N+1, vector<int>(26,N));
  // res[i][j] == Nは存在しないことを意味
  for(int i = N-1; i >= 0; i--){
    for(int j = 0; j < 26; j++){
      res[i][j] = res[i+1][j];
    }
    res[i][S[i]-'a'] = i;
  }
  return res;
}
      

int main(){
  for(int i = 0; i < 300000; i++){ dp[i] = inf;}
  string A; cin >> A;
  int n = A.size();
  
  dp[n] = 1; //自明な初期値
  
  auto ch = makeCH(A); vector<pair<char,int>> recon(n+1, {'?',n});
  
  
  for(int i = n-1; i >= 0; i--){
    for(int j = 0; j < 26; j++){
      
      if( ch[i][j] == n){ // A[i]以降、a+jが存在しない場合→一文字でいい
        if( dp[i] > 1){
          dp[i] = 1; recon[i] = {(char)(j+'a'), n};
        }
      }
      else{
        if( dp[i] > dp[ch[i][j]+1]+1){
          dp[i] = dp[ch[i][j]+1]+1; recon[i] = {(char)(j+'a'),ch[i][j]+1};
        }
      }
    }
  }
    
    int index = 0;
    string ans = "";
    while( index < n){
      auto p = recon[index];
      ans += p.first;
      index = p.second;
    }
    
    cout << ans << endl; return 0;
  }
      
        
         
  
  

        
      
      
      
  
  
  
  
  

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

const int MAXN = 2e5 + 11;
const int P = 1000000007;
int f[MAXN];
int g[MAXN];
int fac[MAXN];
int inv[MAXN];
int fInv[MAXN];
int treeSize[MAXN];
vector <int> adj[MAXN];
int n; 

inline int add(int x, int y) { x += y; x -= x >= P ? P : 0; return x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
inline void incr(int& x,int y) { x = add(x, y); }
inline int choose(int x, int y) { return mul(fac[x], mul(fInv[x - y], fInv[y])); }
inline int qPow(int a, int b)
{
    int res = 1;
    int base = a;
    while (b)
    {
        if (b & 1)
            res = 1ll * res * base % P;
        base = 1ll * base * base % P, b >>= 1;
    }
    return res;
}
inline int Inv(int a) { return qPow(a, P-2); }

void pre(int u, int fa)
{
	treeSize[u] = 1;
	f[u] = 1;
	for (int v : adj[u])
	{
		if (v == fa) continue;
		pre(v, u);
		treeSize[u] += treeSize[v];
		f[u] = mul(f[u], mul(f[v], choose(treeSize[u] - 1, treeSize[v])));
	}
}

void solve(int u, int fa)
{
	for (int v : adj[u])
	{
		if (v == fa) continue;
		g[v] = mul(g[u], mul(Inv(choose(n - 1, treeSize[v])), choose(n - 1, treeSize[v] - 1)));
		solve(v, u);
	}
}

inline void init()
{
	fac[0] = fInv[0] = 1;
	fac[1] = fInv[1] = inv[1] = 1;
	for (int i = 2;i <= n; ++i)
		fac[i] = mul(fac[i - 1], i),
		inv[i] = mul(P - P/i, inv[P%i]),
		fInv[i] = mul(fInv[i - 1], inv[i]);
}

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	cin >> n;
	init();
	for (int i = 1;i < n; ++i)
	{
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	pre(1, 0);
	g[1] = f[1];
	solve(1, 0);
	for (int i = 1;i <= n; ++i)
		cout << g[i] << '\n';
	return 0;
}

Measured memory_bytes: 18676
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<map>
#define debug(a) cout << "*" << a << "*" << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<map>
#define debug(a) cout << "*" << a << "*" << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int n;
int g[100] = {9,19,29,39,49,59,69,79,89,99,199,299,399,499,599,699,799,899,999,1099,1199,1299,1399,1499,1599,1699,1799,1899,1999,2099,2199,2299,2399,2499,2599,2699,2799,2899,2999,3099,3199,3299,3399,3499,3599,3699,3799,3899,3999,4099,4199,4299,4399,4499,4599,4699,4799,4899,4999,5099,5199,5299,5399,5499,5599,5699,5799,5899,5999,6099,6199,6299,6399,6499,6599,6699,6799,6899,6999,7099,7199,7299,7399,7499,7599,7699,7799,7899,7999,8099,8199,8299,8399,8499,8599,8699,8799,8899,8999};
int a[10] = {9, 19, 29, 39, 49, 59, 69, 79, 89}, num = 27;
ll ans[10000] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 19, 29, 39, 49, 59, 69, 79, 89, 99, 199, 299, 399, 499, 599, 699, 799, 899, 999};
int main()
{   
	for (ll i = 1099, j = 0, c = 100; i <= 109999999999; i = i * 10 + 9, j++, c *= 10)
	{
		for (int z = 0; z <= a[j]; z++)
		{
			ans[num++] = i + c * z;
		}
		for (int z = a[j] + 10; z <= 89; z += 10)
		{
			ans[num++] = i + c * z;
		}
	}
	for (ll i = 1099999999999, c = 100000000000; i <= 10999999999999; i = i * 10 + 9, c *= 10)
	{
		for (int z = 0; z <= 89; z++)
		{
			ans[num++] = i + c * z;
		}
	}
	for (ll i = 100099999999999, c = 100000000000, j = 0; j < 99; j++)
	{
		ans[num++] = i + c * g[j];
	}
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		printf("%lld\n", ans[i]);
}

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

#define pb            push_back
#define mp            make_pair
#define ins           insert
#define endl          '\n'
#define all(x)        x.begin(),x.end()
#define debug(X)      { cerr<<endl<<(#X)<<" = "<<(X)<<endl; }
//#define cerr if(0)cerr

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;


int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    ll n,b,r;
    string s;
    ll B=0,R=0;
    cin>>n>>b>>r;  // blu/red

    ll ac=0;
    if (b==0)
        cout<<0;
    else if (r==0)
        cout<<n;
    else {
        ac += b*(n/(r+b)); debug(ac);
        ll k = n%(r+b); debug(k);
        if (k!=0) {
            if (b>=k)
                ac += k;
            else
                ac += b;
        }

        cout<<ac;
    }

    cout<<endl;
    
}



Measured memory_bytes: 256
#include<bits/stdc++.h> //Mr_Mandal
#define PI_INT 3.14159265358979323846
#define PI acos(-1.0)
#define LL long long
#define N 100000007
#define MOD 10000007
#define MX numeric_limits<long long>::max();
#define MN numeric_limits<long long>::min();
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define FILL(v, n) fill(v.begin(), v.end(), n);
#define FAST_IO ios_base::sync_with_stdio(false),cin.tie(NULL)
#define PRINT(v) for(int i=0; i<v.size(); i++) cout<<v[i]<<" "; cout<<endl;
#define SCAN(v) for(int i=0; i<n; i++) { LL temp; cin>>temp; v.push_back(temp); }
#define SORT(v) sort(v.begin(), v.end());
#define VECT(v) vector<LL>v
#define SCF(f) scanf("%d", &f)
#define PNF(f) printf("%d\n", f)
#define CASEP(v) cout<<"Case "<<c<<": "<<v<<"\n"

using namespace std;

int main()
{
    LL peri, n;
    cin >> peri >> n;

    VECT(v);
    SCAN(v);
    SORT(v);

    LL ans=INT_MAX;

    for(int i=0; i<n; i++)
    {
        LL cClock;

        if(i+1<=n-1)
            cClock=v[i]+(peri-v[i+1]);
        else
            cClock=v[i]-v[0];

        LL Clock;

        if(i-1>=0)
            Clock=(peri-v[i])+v[i-1];
        else
            Clock=v[n-1]-v[0];

        ans=min(ans, min(cClock, Clock));
    }

    cout<<ans<<"\n";

    return 0;
}


Measured memory_bytes: 2420
from collections import deque
n,k = map(int,input().split())
alist = list(map(int,input().split()))
frontque = deque(alist[:k])
backque =  deque(alist[k:])

for i in range(n-k):
    back = backque.popleft()
    front = frontque.popleft()
    if front < back:
        print('Yes')
    else:
        print('No')
    frontque.append(back)


Measured memory_bytes: 32428
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
int main() {
	int a, b;
	cin >> a >> b;
	if (a * b % 2 == 0)
		cout << "Even" << "\n";
	else
		cout << "Odd" << "\n";
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define show(x) {for(auto i: x){cout << i << " ";} cout<<endl;}
#define showm(m) {for(auto i: m){cout << m.x << " ";} cout<<endl;}
typedef long long ll;
typedef pair<int, int> P;
ll gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return (x * y) / gcd(x, y); }

const int h_max = 102;
const int w_max = 102;
int h, w;
int binmap[h_max][w_max] = {0};
int lenmap[h_max][w_max] = {0};
//0/1 bfs
void bfs()
{
    deque<P> q;
    rep(i, h) rep(j, w)
    {
        lenmap[i][j] = -1;
    }
    q.push_back({0, 0});
    lenmap[0][0] = binmap[0][0];

    P wa[2] = {{0, 1}, {1, 0}};
    while (!q.empty())
    {
        P n = q.front();
        q.pop_front();
        for (int i = 0; i < 2; i++)
        {
            P next = {n.first + wa[i].first, n.second + wa[i].second};
            //cout << n.first << "," << n.second << ":" << lenmap[n.first][n.second] << "=>" << next.first << "," << next.second << endl;
            if (lenmap[next.first][next.second] == -1)
            {
                if (binmap[next.first][next.second] == binmap[n.first][n.second]){
                    lenmap[next.first][next.second] = lenmap[n.first][n.second];
                    q.push_front(next);
                } else {
                    lenmap[next.first][next.second] = lenmap[n.first][n.second] + 1;
                    q.push_back(next);
                }
            }
        }
    }
}

int main()
{
    cin >> h >> w;
    rep(i, h)
    {
        string s;
        cin >> s;
        rep(j, w)
        {
            if (s[j] == '#')
                binmap[i][j] = 1;
        }
    }

    bfs();
    cout << (lenmap[h-1][w-1]+1)/2 << endl;
}


Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <cmath>
#include <time.h>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define LINF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define PI 3.14159265
#define RAND (rand()*rand())
#define MAX(x, y) ((x) > (y) ? (x):(y)) 
#define MIN(x, y) ((x) > (y) ? (y):(x))
#define ABS(x) ((x) > 0 ? (x) : -(x))
#define CEIL(x, y) (((x) + (y) - 1)/(y))
using namespace std;
const int MAXN = 1e5 + 5;
const ll MOD = 1e9 + 7;
int N, M, K, Q, T;

ll fexp(ll b, ll e) {
	if (e == 0ll) return 1ll;
	if (e == 1ll) return b;
	ll temp = fexp(b, e / 2);
	return ((temp*temp%MOD)*fexp(b, e % 2))%MOD;
}

int main()
{
	int i, j;
	ll x, y, a, b;
	scanf("%lld%lld", &x, &y);
	ll ck = (2ll * y - x);
	if ((ck < 0) || (ck % 3ll != 0ll)) {
		printf("0");
		return 0;
	}
	b = (2ll * y - x) / 3ll;
	a = y - 2ll * b;
	if (b < 0 || a < 0) {
		printf("0");
		return 0;
	}
	ll ans = 1ll;
	ll A = 1ll;
	ll B = 1ll;
	for (ll num = 1; num <= a + b; ++num) {
		ans = ans * num % MOD;
	}
	for (ll num = 1; num <= a; ++num) {
		A = A * num % MOD;
	}
	for (ll num = 1; num <= b; ++num) {
		B = B * num % MOD;
	}
	ans = (((ans * fexp(A, MOD - 2)) % MOD) * fexp(B, MOD - 2)) % MOD;
	printf("%lld", ans);
}

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

const int maxn = 1e5+7;

struct city {
	int idx;
	int num;
	int year;
	city(int _idx = 0, int _num = 0, int _year = 0) {
		idx = _idx;
		num = _num;
		year = _year;
	}
};

bool cmp(city a, city b) {
	return a.year < b.year;
}

std::map<int, std::vector<city>> aa;
std::vector<city> ans;

bool cmp2(city a, city b) {
	return a.idx < b.idx;
}

int main(int argc, char *argv[]) { 
	int n, m; 
	std::cin >> n >> m;
	int pre, year;
	for (int i = 1; i <= m; i++) {
		std::cin >> pre >> year;
		aa[pre].push_back(city(i, 0, year));
	}
	for (auto it: aa) {
		std::sort(it.second.begin(), it.second.end(), cmp);
		int cnt = 1;
		for (auto ti: it.second) {
			ti.num = cnt;
			cnt++;
			ti.year = it.first;
			ans.push_back(ti);
		}
	}
	std::string sta = "000000000000";
	std::sort(ans.begin(), ans.end(), cmp2);
	std::string tem;
	for (auto it: ans) {
		tem = std::to_string(it.year);
		for (int i = 0; i < 6-tem.length(); i++) {
			std::cout << '0';
		}
		std::cout << tem;
		tem = std::to_string(it.num);
		for (int i = 0; i < 6-tem.length(); i++) {
			std::cout << '0';
		}
		std::cout << tem << '\n';
	}
}

Measured memory_bytes: 13684
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#include <cmath>
#include <utility> // pair make_pair
#include <algorithm>
#include <functional>
#include <iomanip>
#include <climits> // LLONG_MAX, LLONG_MIN, INT_MIN, INT_MAX
#include <assert.h>

#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,63,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define ll long long
//#define int ll
#define INF INT_MAX/10

using namespace std;
using Pi = pair<int, int>;
using Graph = vector<vector<int> >;
using WeightGraph = vector<vector<Pi> >;


int A[100100];

int main() {
  string S; cin >> S;
  char Prev;
  int R = 0;
  int L = 0;

  if (S[0] == 'R') {
    R++;
  } else {
    L++;
  }

  Prev = S[0];


  memset(A, 0, sizeof(A));

  // right の右端
  int flag1 = 0;

  // left の左端
  int flag2 = 0;
  for (int i = 1; i < S.size(); i++) {
    if (Prev == S[i]) {
      if (S[i] == 'R') R++;
      else L++;
      if (i == S.size() - 1) {
        //cout << "GOTO : " << endl;
        goto here; 
      }
      //cout << S[i] << " R is : " << R << " L is :" << L << endl;
    } else {
      if (Prev == 'R') {
        flag1 = i - 1;
        flag2 = i;
        Prev = 'L';
        L = 1;
        if (i == S.size() - 1) {
          //cout << "GOTO : " << endl;
          goto here;
        }
      } else {
      here:        
        if ((R + L) % 2 == 1) {
          if (R > L) {
            if (R % 2 == 0) {
              A[flag1] = (R+L) / 2;
              A[flag2] = (R+L) / 2 + 1;
            } else {
              A[flag1] = (R+L) / 2 + 1;
              A[flag2] = (R+L) / 2;
            }
          } else {
            if (L % 2 == 1) {
              A[flag1] = (R+L) / 2;
              A[flag2] = (R+L) / 2 + 1;
            } else {
              A[flag1] = (R+L) / 2 + 1;
              A[flag2] = (R+L) / 2;
            }
          } 
        } else {
          A[flag1] = (R+L) / 2;
          A[flag2] = (R+L) / 2;
        }
        //cout << "----------------";
        //cout << "flag1 is : " << flag1 << " flag2 is : " << flag2 << endl;
        //cout << A[flag1] << " " << A[flag2] << endl;
        //cout << S[i] << " R is : " << R << " L is :" << L << endl;
        R = 1;
        L = 0;
        Prev = 'R';
        //cout << "Reset: " << endl;
        //cout << S[i] << " R is : " << R << " L is :" << L << endl;
      }
    }
  }
  for (int i = 0; i < S.size(); i++) {
    cout << A[i] << " ";
  }

  cout << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int m[501][501];
int main()
{
  int h,w;
  while(cin >> h >> w, h){
    memset(m,0,sizeof(m));
    int x,y;
    string s;
    for(y = 1; y <= h; y++){
      cin >> s;
      for(x = 1; x <= w; x++){
	if(s[x-1] == '.') m[y][x] = m[y][x-1]+1;
      }
    }
    int ret = 0;
    for(y=1; y<=h; y++){
      for(x=1; x<=w; x++){
	if(m[y][x] != 0){
	  int j=0, k=m[y][x];
	  for(int i=y; m[i][x] != 0; i++){
	    k = min(k, m[i][x]);
	    j++;
	    ret = max(ret, j*k);
	  }
	}
      }
    }
    cout << ret << endl;
  }
  return 0;
}

Measured memory_bytes: 1908
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

def main():
    N = int(input())

    res = 0

    for i in range(1, N+1):
        n = N // i
        res += n * (2 * i + (n - 1) * i) // 2
    
    print(res)

if __name__ == '__main__':
    main()

Measured memory_bytes: 10400
a[26],i,j,f;
long long sum,div=1;
char *p,s[45];
main(){
	scanf("%s", s);
	for(p=s;*p;p++)a[*p-'a']++;
	for(i=0;i<26;i++){
		if((j=a[i])%2)
			if(f)puts("0"),exit(0);
			else f=1;
		sum+=j/=2;
		for(;j;div*=j--);
	}
	for(i=sum,sum=1;i;sum*=i--);
	printf("%lld\n", sum/div);
	exit(0);
}

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

typedef long long int lli;

vector<vector<int>> a;

int solve(int i){
    
    if(a[i].size() == 0){
        return 0;
    }
    
    vector<int> b;
    
    for(int j = 0; j < a[i].size(); j++){
        b.push_back(solve(a[i][j]));
    }
    
    sort(b.begin(),b.end());
    
    for(int j = 0; j < b.size(); j++) b[j] += b.size() - j;
    
    int tmp = 0;
    for(int j = 0; j < b.size(); j++) tmp = max(tmp,b[j]);
    
    //cout << i << " " << res << endl;
    return tmp;
}

int main(void){
    // Here your code !
    lli N;
    cin >> N;
    
    a = vector<vector<int>>(N);
    
    for(int i = 1; i < N; i++){
        int tmp = 0;
        cin >> tmp;
        tmp--;
        a[tmp].push_back(i);
    }
    
    cout << solve(0) << endl;
    
    /*
    for(int i = 0; i < N; i++){
        for(int j = 0; j < a[i].size(); j++)
                cout << a[i][j] << " ";
        cout << endl;
    }
    */
    
}


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

int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    sort(v.begin(), v.end());

    long double fin = v[0];
    for (int i = 0; i < n; i++)
    {
        fin = (float) (fin + v[i]) / 2;
    }
    printf("%0.6Lf\n", fin);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VLL;
typedef vector<string> VS;
typedef vector<PLL> VP;
#define rep(i,n) for (ll i=0; i<(ll)(n); i++)
#define repd(i,n) for (ll i=n-1; i>=0; i--)
#define rept(i,m,n) for(ll i=m; i<n; i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define PF push_front
#define PB push_back
#define SORT(V) sort((V).begin(), (V).end())
#define RVERSE(V) reverse((V).begin(), (V).end())
#define paired make_pair
#define PRINT(V) for(auto v : (V)) cout << v << " "

int main()
{
    ll N; cin >> N;
    VLL a(N);
    ll four=0;
    ll two=0;
    rep(i,N){
        cin >> a.at(i);
        if(a.at(i)%4==0){
            four++;
        }
        if(a.at(i)%4!=0 && a.at(i)%2==0){
            two++;
        }
    }
    ll none=N-four-two;
    if(two==0){
        if(none<=four+1){
            cout << "Yes" << endl;
            return 0;
        }
    }
    else{
        if(none<=four){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

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

int main(){
    int n;
    cin >> n;
    if(n<10){
        cout << n << endl;
    }else if(n<100){
        cout << 9 << endl;
    }else if(n<1000){
        cout << 9 + (n-100+1) << endl;
    }else if(n<10000){
        cout << 909 << endl;
    }else if(n<100000){
        cout << 909 + (n-10000+1) << endl;
    }else {
        cout << 90909 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
#define ll long long
#define vpll vector<pair<ll,ll> >
#define vpii vector<pair<int,int> >
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mem(a,b) memset(a , b , sizeof a );
#define M 1000000007
#define bs(a,b,x) binary_search(a,b,x)
template<typename T>
T fact(T n)
{
    // to find factorial
    return (n==1 || n==0) ? 1: n * fact(n - 1);
}
bool sortbysec(const pair<int,int> &a,
              const pair<int,int> &b)
{
    return (a.second < b.second);
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
      int n;
      cin>>n;
      int a[n];
      for(int i=0;i<n;i++) cin>>a[i];
      sort(a,a+n);
      map<int,int> m;
      for(int i=0;i<n;i++) m[a[i]]++;
      int c=0;
      for(int i=0;i<n;i++)
      {
          if(i<n-1 && a[i]==a[i+1]) continue;
          else
          {
              int x = a[i];
              int sw=1;
              for(int j=1;j*j<=x;j++)
              {
                  if(x%j==0)
                  {
                      int p=j;
                      int q=x/j;
                      
                      if(p==1)
                      {
                        if(m[x]==1 && x!=1)
                        {
                            if( binary_search(a,a+n,p) )
                            {
                              sw=0;
                              break;      
                            }
                            else
                            {
                                continue;
                            }
                        }
                        if(m[x]==1 && x==1)
                        {
                            continue;
                        }
                      }
                      
                      if( binary_search(a,a+n,p) || binary_search(a,a+n,q) )
                      {
                          sw=0;
                          break;
                      }
                  }
              }
              if(sw==1) c++;
          }
      }
      cout<<c<<endl;
    
    return 0;
}



Measured memory_bytes: 13816
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[False]*w for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if visited[i][j]:
        continue
      if field[i][j]!='#':
        continue
      q=collections.deque()
      q.append((i,j))
      b=0
      wh=0
      while q:
        y,x=q.popleft()
        if visited[y][x]:
          continue
        if field[y][x]=='#':
          b+=1
        else:
          wh+=1
        visited[y][x]=True
        for dy,dx in dd:
          ny=y+dy
          nx=x+dx
          if not (0<=ny<h and 0<=nx<w):
            continue
          if field[y][x]==field[ny][nx]:
            continue
          if visited[ny][nx]:
            continue
          q.append((ny,nx))
      ans+=b*wh
      # print(i,j,b,wh,ans)
  return ans

# main()
print(main())


Measured memory_bytes: 12220
#include <iostream>
#include <cmath>

using namespace std;

int main() {
  int N,a,v{},s{};
  cin >> N;
  while (cin >> a) {
    s += a;
    v += a * a;
  }
  int S = round((float)s/N);
  cout << v - 2*S*s + S*S*N << endl;
}


Measured memory_bytes: 512
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

use std::cmp::max;
fn main() {
    input!{
        x: i64,
        t: i64,
    }
    println!("{}", max(0, x - t));
}


Measured memory_bytes: 4352
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <tuple>
#include <utility>
#include <vector>
#define ll long long
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl
#define COYE cout<<"YES"<<endl
#define COYe cout<<"Yes"<<endl
#define COye cout<<"yes"<<endl
#define CONO cout<<"NO"<<endl
#define CONo cout<<"No"<<endl
#define COno cout<<"no"<<endl
#define FORE(i,a) for(auto &i:a)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define PB push_back
#define MP make_pair
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define EACH(V,i) for(typeof((V).begin()) i=(V).begin();i!=(V).end();++i)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MAX 5100000
using namespace std;
using Edge=pair<int,int>;
using Graph=vector<vector<int>>;
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T>inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
  int X,Y;
  cin>>X>>Y;
  if(2*X<=Y && Y<=4*X && Y%2==0) COYe;
  else CONo;
  return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <set>
#include <bitset>
#include <unordered_map>
#include <cmath>
#include <functional>

using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
template <class T>
using Vvec = vector<vector<T> >;

template <class T>
void debug(T& v)
{
    for(auto& x: v) cout << x << " ";
    cout << endl;
}

int main()
{
    int N;
    cin >> N;
    multiset<ll> st, st2;
    for(int i=0; i<(1<<N); i++){
        ll x; cin >> x;
        st.insert(x);
    }
    auto itr = st.end();
    itr--;
    st2.insert(*itr);
    st.erase(itr);

    bool ok = true;
    vector<ll> tmp;
    for(int i=0; i<N; i++){
        // debug(st);
        // debug(st2);
        if(!ok) break;
        for(auto& x: st2){
            auto itr = st.lower_bound(x);
            if(itr == st.begin()){
                ok = false; break;
            }
            itr--;
            tmp.push_back(*itr);
            st.erase(itr);
        }
        for(auto& x: tmp) st2.insert(x);
        tmp.clear();
    }

    if(ok) cout << "Yes\n";
    else cout << "No\n";
}

Measured memory_bytes: 13692
#include<bits/stdc++.h>
#define REP(n)for(ll i=0;i<n;i++)
#define MP make_pair
#define F first
#define S second
typedef long long ll;
using namespace std;
int main(){
    ll n,k,s,t,a[50];cin>>n>>k>>s>>t;
    REP(n)cin>>a[i];
    map<pair<ll,ll>,ll> dp[50];
    REP(n){
        for(ll j=k-2;j+1;j--){
            for(const auto&l:dp[j]){
                dp[j+1][MP(l.F.F&a[i],l.F.S|a[i])]+=l.S;
            }
        }
        dp[0][MP(a[i],a[i])]=1;
    }
    n=0;
    REP(k)n+=dp[i][MP(s,t)];
    cout<<n;
}

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

int main() {
  int N;
  cin >> N;
  vector<string> seat(N);
  int Left = 0;
  int Right = N;
  for (int i = 0; i < 20; i++) {
    if (i == 0) {
      cout << 0 << endl;
      cin >> seat[0];
      if (seat[0] == "Vacant") break;
    } else {
      int pivot = Left + (Right - Left) / 2;
      cout << pivot << endl;
      cin >> seat[pivot];
      if (seat[pivot] == "Vacant") break;
      if (seat[Left] == seat[pivot] && (pivot - Left) % 2 == 0) Left = pivot;
      else if (seat[Left] != seat[pivot] && (pivot - Left) % 2 != 0) Left = pivot;
      else Right = pivot;
    }
  }        
}

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

int main(void){
    int n;
    cin >> n;
    vector<int> a(n), b(n-1);
    for(auto& i : b) cin >> i;
    a.at(0) = a.at(1) = b.at(0);
    for(int i = 1; i < n-1; i++){
        if(a.at(i) > b.at(i)){
            a.at(i) = b.at(i);
            a.at(i+1) = b.at(i);
        }else{
            a.at(i+1) = b.at(i);
        }
    }
    cout << accumulate(a.begin(), a.end(), 0) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
using namespace std;
using ll = long long;
using ld = long double;
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}

const double PI=acos(-1);

int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  cout << fixed << setprecision(15);
  ld A,B,H,M;
  cin >> A >> B >> H >> M;
  ld x=M*6;
  ld y=(H*60+M)/2.0;
  if(x>y) x=x-y;
  else  x=y-x;
  if(x>180) x=360-x;
  //cout << x << endl;
  x/=180;

  cout << sqrt(A*A+B*B-2*A*B*cos(PI*x)) << endl;

  return 0;
}

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

#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define pii pair < int , int >
#define pll pair < long long, long long >

const int N = 200005;


int main()
{
    #ifdef Estb_probitie
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif

    int n;
    cin >> n;
    ld p[n + 2];

    for (int i = 0; i < n; ++i)
        cin >> p[i];

    ld dp[n + 2][n + 2] = {};

    dp[0][0] = 1 - p[0];
    dp[0][1] = p[0];
    for (int i  = 1; i < n; ++i)
    {
        for (int j = 0; j <= i; ++j)
            dp[i][j + 1] += dp[i - 1][j] * p[i],
            dp[i][j] += dp[i - 1][j] * (1 - p[i]);
    }

    ld ans = 0;
    for (int i = n / 2 + n % 2; i <= n; ++i)
       ans += dp[n - 1][i];

    cout << fixed<<setprecision(10)<<ans;
}


Measured memory_bytes: 141056
#include <bits/stdc++.h>
using namespace std;
const int MOD=998244353;
map<string, int> f,g;
int solve(string s) {
	if(s=="1") return f[s]=g[s]=2;
	if(s=="0") return f[s]=g[s]=1;
	if(f.count(s)) return f[s];
	int len=s.length();
	int ans=0;
	for(int i=1;i<len;i++){
		solve(s.substr(0,i));
		solve(s.substr(i,len-i));
		ans=(ans+1LL*g[s.substr(0,i)]*f[s.substr(i,len-i)]%MOD)%MOD;
	}
	for(int i=1;i<len;i++)if(len%i==0){
		bool f[102]={0};
		for(int j=0;j<len;j++){
			if(s[j]=='0') f[j%i]=1;
		}
		string str="";
		for(int j=0;j<i;j++){
			str+=(f[j]?'0':'1');
		}
		ans=(ans+solve(str))%MOD;
		(g[s]+=solve(str))%=MOD;
	}
	return f[s]=ans;
}
int main() {
	string s; cin>>s;
	cout<<solve(s)<<endl;
}




Measured memory_bytes: 14720
#include <stdio.h>
#pragma warning (disable:4996)
//FILE *in = fopen("input.txt", "r"), *out = fopen("output.txt", "w");
FILE *in = stdin, *out = stdout;
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
#define INF 1e18
#define NM 20005
#define MOD 1000000000
#define FOR(i,n,m) for (int i=(n);i<=(m);i++)
#define si(n) fscanf(in,"%d",&n)
#define sd(n) fscanf(in,"%lf",&n)
typedef long long int ll;
int main(){
int X,A,B;
si(X),si(A),si(B);
if (X>=A) fprintf(out,"%d",(X-A)%B);
else fprintf(out,"%d",X%B);
return 0;
}

Measured memory_bytes: 384
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int price = 700;
        for(int i = 0;i < s.length();i++){
            char ch = s.charAt(i);
            if(ch == 'o'){
                price += 100;
            }
        }
        System.out.println(price);
    }
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll i,a,b,d,ar[100005],mn=1000000000;

    cin>>a>>b;
    for(i=1;i<=a;i++)
    {
        cin>>ar[i];
    }
    sort(ar,ar+a+1);

    for(i=1;i<=a-b+1;i++)
    {

        d=abs(ar[i]-ar[i+b-1]);
        
        if(d<mn)
        mn=d;

    }

    cout<<mn<<endl;





    return 0;
}


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

int main(){
	int ans[10001];
	ans[0] = 1;
	for(int i = 1; i < 10001; i++){
		ans[i] = ans[i-1] + i;
	}
	int n;
	while(cin >> n){
		cout << ans[n] << endl;
	}
	return 0;
}

Measured memory_bytes: 1196
import java.io.*;
import java.util.*;
public class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] intervals = new int[m][2];

        for(int i = 0; i < m; i++) {
          intervals[i][0] = sc.nextInt();
          intervals[i][1] = sc.nextInt();
        }
        Arrays.sort(intervals, (it1, it2) -> it1[1] - it2[1]);

        int i = 1;
        int cnt = 1;
        int endTime = intervals[0][1];
        while(i < m) {
          while(i < m && intervals[i][0] < endTime)
            i++;
          if(i < m) {
            cnt++;
            endTime = intervals[i][1];
          }
        }
        System.out.println(cnt);
    }
}


Measured memory_bytes: 95004
#include<iostream>
using namespace std;
 
int main(){
  
  int A,B,C,D,E;
  cin>>A>>B>>C;
  D = A*C;
  E=B/A;
  if(B>=D)
    cout<<C<<endl;
  else 
    cout<<E<<endl;
  
  return 0;
}
   

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
typedef pair<int,string> pr;
int main() {
	// your code goes here
	int n;
	char c;
	string tmp;
	while(cin >> n && n!=0){
		vector<string> s;
		vector<string> words;
		vector<pr> dics;
		cin.ignore();
		for(int j=0;j<n;j++){
			getline(cin,tmp);
			s.push_back(tmp);
		}
		cin >> c;
		
		for(int i=0;i<n;i++){
			int it=0;
			string word="";
			for(int j=0;j<=s[i].size();j++){
				if(j==s[i].size() || s[i][j]==' '){
					if(word[0]==c)
					words.push_back(word);
					word="";
				}
				else
					word+=s[i][j];
			}
		}
		int sum=1;
		sort(words.begin(),words.end());
		for(int i=0;i<words.size();i++){
			if(i==words.size()-1 || words[i]!=words[i+1]){
				dics.push_back(pr(100000-sum,words[i]));
				sum=1;
			}
			else 
			sum++;
		}
		sort(dics.begin(),dics.end());
		for(int i=0;i<min((int)dics.size(),5);i++){
		cout << dics[i].second;
		if(i+1!=min((int)dics.size(),5))
		cout << " ";
		}
		if(dics.size()==0)
		cout << "NA" ;
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 1240
#include <iostream>
#include <vector>
#define REP(i, n) for(int i = 0; i < (n); i++)

using namespace std;
typedef long long ll;
//法
#define MOD 1000000007

//ａをbで割る
long long mod_div(long long a,long long b){
	if(a % b == 0)return a/b;
	long long tmp = MOD - 2,c = b,ret = 1;
	while(tmp > 0){
		if(tmp & 1){
			ret *= c;ret %= MOD;
		}
		c *= c;c %= MOD;tmp >>= 1;
	}
	return a*ret%MOD;
}

//階乗の上限
#define MAX_K 333333
vector<long long> kaijo(MAX_K);
long long combination(long long n, long long r){
    if(n < r || n < 0 || r < 0)
        return 0;
	if(kaijo[0] != 1){
		kaijo[0] = 1;
		for(long long i = 1;i < MAX_K;i++)kaijo[i] = (kaijo[i-1] * i) % MOD;
	}
    long long ret = kaijo[n];
	long long tmp = (kaijo[r] * kaijo[n-r]) % MOD;
    return mod_div(ret,tmp);
}


int main()
{
  ll H, W, A, B;
  cin >> H >> W >> A >> B;

  ll ans = 0;
  REP(i, H-A) {
    (ans += (combination(B-1+i, i) * combination(H+W-2-i-B, W-1-B))%MOD)%=MOD;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 2816
S1 = input()
S2 = list(S1)
S2.sort()

if S2[0] == S2[1]:
  if S2[1] != S2[2]:
    if S2[2] == S2[3]:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
else:
  print("No")

Measured memory_bytes: 8908
#include <bits/stdc++.h>
#include <iostream>
#include <sstream>
#include <string>
#define f first
#define s second
 
#define pb push_back
#define mp make_pair
 
#define ll long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define sz(v) int(v.size())
using namespace std;
 
const int N = (int) 4e5 + 10;
const int MAX_LEN = (int) 2e6 + 10;
const int SQRT = 400;
 
const int INF = (int) 1e9 + 7;
const ll LINF = (ll) 1e18 + 7;
 
const double PI = acos(-1);
ll const MOD = 998244353;
 
void yes(){
    cout<<"YES"<<'\n';
}
 
void no(){
    cout<<"NO"<<'\n';
}
 
ll fact(int n){
    ll ans = 1;
    for(int i=2;i<=n;i++){
        ans = (ans*i)%MOD;
    }
 
    return ans;
}
 
ll powM(int n, int x){
    if(x==0){
        return 1;
    }
    if(x==1){
        return n%MOD;
    }
 
    if(x%2==0){
        ll a = powM(n,x/2);
        return (a*a)%MOD;
    }else{
        return (n*powM(n,x-1))%MOD;
    }
}
 
ll C(int n, int k){
    return (fact(n) * powM((fact(k)*fact(n-k))%MOD,MOD-2))%MOD;
}
 
ll A(int n, int k){
    return (fact(n) * powM(fact(n-k)%MOD,MOD-2))%MOD;
}
string st(int temp){
    string str="";
    while(temp != 0){
			if(temp % 2 == 0){
				str += "0";
			}else{
				str += "1";
			}			
			temp /= 2;
		}
    return str;
}
const int nx[4] = {1, 0, -1, 0};
const int ny[4] = {0, 1, 0, -1};
 
int t,n,m,k;
char se;
void solve(){
    cin>>se;
    if (islower(se)){
        cout<<"a";

    }
    else{
        cout<<"A";
    }
   
  
}
    


int main() {
    t=1;
    // cin>>t;
    while (t--){
        solve();

    }
    return 0;
}


Measured memory_bytes: 3596
import sys
sys.setrecursionlimit(100000)
d = {0:1, 1:1, 2:2}
def countcombi(n):
    if n in d:
        return d[n]
    else:
        d[n] = countcombi(n-1)+countcombi(n-2)
        return d[n]
N, M = list(map(int,input().rstrip().split()))
a_now = 0
a_before = 0
ans = 1
for _ in range(M):
    a_now = int(input().rstrip())
    if a_now-a_before == 0 and a_before != 0:
        print(0)
        break
    ans = (ans * countcombi(a_now-a_before-1)) % 1_000_000_007
    a_before = a_now + 1
else:
    a_now = N
    ans = (ans * countcombi(a_now-a_before)) % 1_000_000_007
    print(ans)

Measured memory_bytes: 549176
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;

namespace atcorder2
{
    class Program
    {
        public static long Read()
        {
            return long.Parse(Console.ReadLine());
        }

        public static long[] Reads()
        {

            return Console.ReadLine().Split().Select(long.Parse).ToArray();
        }

        public static long d(long sx,long sy,long gx,long gy)
        {
            return Math.Abs(gx - sx) + Math.Abs(gy - sy);
        }
      



        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            var abcxy = Reads();
            if (abcxy[0] + abcxy[1] > 2 * abcxy[2])
            {
                if (abcxy[0] <= 2 * abcxy[2] && abcxy[1] <= 2 * abcxy[2])
                {
                    if (abcxy[3] > abcxy[4])
                        Console.WriteLine(2 * abcxy[2] * abcxy[4] + (abcxy[3] - abcxy[4]) * abcxy[0]);
                    else
                        Console.WriteLine(2 * abcxy[2] * abcxy[3] + (abcxy[4] - abcxy[3]) * abcxy[1]);
                }
                else if (abcxy[0] >= 2 * abcxy[2] && abcxy[1] <= 2 * abcxy[2])
                {
                    if (abcxy[3] > abcxy[4])
                        Console.WriteLine(2 * abcxy[2] * abcxy[3]);
                    else
                        Console.WriteLine(2 * abcxy[2] * abcxy[3] + (abcxy[4] - abcxy[3]) * abcxy[1]);
                }
                else if(abcxy[0] <= 2 * abcxy[2] && abcxy[1] >= 2 * abcxy[2])
                {
                    if (abcxy[3] > abcxy[4])
                        Console.WriteLine(2 * abcxy[2] * abcxy[4]+ (abcxy[3] - abcxy[4]) * abcxy[0]);
                    else
                        Console.WriteLine(2 * abcxy[2] * abcxy[4]);
                }
                else if(abcxy[0] >= 2 * abcxy[2] && abcxy[1] >= 2 * abcxy[2])
                {
                    Console.WriteLine(2 * abcxy[2] * Math.Max(abcxy[3], abcxy[4]));
                }
            }
            else
            {
                Console.WriteLine(abcxy[0] * abcxy[3] + abcxy[1] * abcxy[4]);
            }
             

            Console.Out.Flush();
        }
    }
}




Measured memory_bytes: 13396
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const LL MOD = 1000000007LL;
vector<P> v;
bool appear[100000];
int main() {
	int R, C, N;
	cin >> R >> C >> N;
	for (int i = 0; i < N; i++) {
		int x[2], y[2];
		bool ok = 1;
		for (int j = 0; j < 2; j++) {
			cin >> x[j] >> y[j];
			if (x[j] != 0 && x[j] != R&&y[j] != 0 && y[j] != C) ok = 0;
		}
		if (!ok) continue;
		for (int j = 0; j < 2; j++) {
			if (y[j] == 0) {
				v.emplace_back(x[j], i);
			}
			else if (x[j] == R) {
				v.emplace_back(R + y[j], i);
			}
			else if (y[j] == C) {
				v.emplace_back(R + C + (R - x[j]), i);
			}
			else if (x[j] == 0) {
				v.emplace_back(R + C + R + (C - y[j]), i);
			}
		}
	}
	sort(v.begin(), v.end());
	stack<int> S;
	for (int i = 0; i < v.size(); i++) {
		if (appear[v[i].second]) {
			if (S.top() != v[i].second) {
				cout << "NO" << endl;
				return 0;
			}
			S.pop();
		}
		else {
			appear[v[i].second] = 1;
			S.push(v[i].second);
		}
	}
	cout << "YES" << endl;
}

Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
int main() {
  cin.tie(0); cin.sync_with_stdio(false);
  int n;
  cin >> n;
  vector<long long> a(2 * n + 1, 0);
  for (int i = 1; i <= n; i++) {
    long long x;
    cin >> x;
    a[i] = a[i + n] = x;
  }
  for (int i = 1; i <= 2 * n; i++) {
    a[i] += a[i - 1];
  }
  auto ck = [&] (long long k) -> bool {
    for (int l = 0; l <= n; l++) {
      auto it = lower_bound(a.begin(), a.end(), a[l] + k); if (it == a.end()) continue;
      auto jt = lower_bound(a.begin(), a.end(), *it + k); if (jt == a.end()) continue;
      auto kt = lower_bound(a.begin(), a.end(), *jt + k); if (kt == a.end()) continue;
      int r = kt - a.begin();
      if (r - l <= n) return true;
    }
    return false;
  };
  constexpr long long inf = 1LL << 60;
  long long ok = 0, ng = inf, md;
  while (ng - ok > 1) {
    md = (ok + ng) >> 1;
    if (ck(md)) ok = md;
    else ng = md;
  }
  cout << ok << endl;
  return 0;
}


Measured memory_bytes: 4408
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define FAST ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


int powerModulo(int base,int power,int MOD){
    int res=1;
    while(power){
        if(power&1) res=(res*base)%MOD;
        base=(base*base)%MOD;
        power>>=1;
    }
    return res;
}

int solve(int x){
    int val=1;
    while(x){
        val++;
        x=x%__builtin_popcount(x);
    }
    return val;
}

int32_t main(){ 
    FAST
    int n;cin>>n;
    string s;cin>>s;
    reverse(s.begin(),s.end());
    
    int mod1=count(s.begin(),s.end(),'1')-1,mod2=count(s.begin(),s.end(),'1')+1;
    // cout<<mod1<<" "<<mod2<<"\n";
    int val1=0,val2=0;
    for(int i=0;i<n;i++){
        if(mod1>0) val1=(val1+(s[i]-'0')*powerModulo(2,i,mod1))%mod1;
        val2=(val2+(s[i]-'0')*powerModulo(2,i,mod2))%mod2;
        // cout<<val1<<" "<<val2<<"\n";
    }

    int mod=count(s.begin(),s.end(),'1');
    for(int i=n-1;i>=0;i--){
        int curr_mod;
        if(s[i]=='1')
            curr_mod=mod-1;
        else 
            curr_mod=mod+1;
        // cout<<s[i]<<" "<<curr_mod<<"\n";
        if(curr_mod==0){
            cout<<0<<"\n";
        }
        else if(curr_mod==mod2){
            int ans=val2+powerModulo(2,i,mod2);
            ans=(ans)%mod2;
            // cout<<ans<<"--\n";
            cout<<solve(ans)<<"\n";
        }
        else{
            int ans=val1-powerModulo(2,i,mod1);
            ans=(ans+mod1)%mod1;
            cout<<solve(ans)<<"\n";
        }
    }

    return 0;
}

Measured memory_bytes: 3788