akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <cstdio>
#include <cstdlib>

#ifdef _MSC_VER
#include <Windows.h>
#else
#include <unistd.h>
#endif

using namespace std;

//conversion
//------------------------------------------
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();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef long long LL;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))



int main(){
    int K,T;cin>>K>>T;
    int a[103];
    int maxi=0;
    int sum=0;
    REP(i,T){
        cin>>a[i];
        maxi=max(maxi,a[i]);
        sum+=a[i];
    }
    sum-=maxi;
    cout<<max(0,maxi-sum-1)<<endl;
    return 0;
}

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

const int mod = 1000000007;
// const int mod = 998244353;

struct mint
{
    ll x;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint &operator+=(const mint m)
    {
        if((x += m.x) >= mod) x -= mod;
        return *this;
    }
    mint &operator-=(const mint m)
    {
        if((x += mod - m.x) >= mod) x -= mod;
        return *this;
    }
    mint &operator*=(const mint m)
    {
        (x *= m.x) %= mod;
        return *this;
    }
    mint operator+(const mint m) const
    {
        return mint(*this) += m;
    }
    mint operator-(const mint m) const
    {
        return mint(*this) -= m;
    }
    mint operator*(const mint m) const
    {
        return mint(*this) *= m;
    }
    mint pow(ll n) const
    {
        if(!n) return 1;
        mint m = pow(n>>1);
        m *= m;
        if(n & 1) m *= *this;
        return m;
    }
    mint inv() const { return pow(mod-2);}
    mint &operator/=(const mint m) { return *this *= m.inv();}
    mint operator/(const mint m) const { return mint(*this) /= m;}
};
istream &operator>>(istream &is, mint &m) { return is >> m.x;}
ostream &operator<<(ostream &os, const mint &m) { return os << m.x;}

struct combination
{
    vector<mint> fact, ifact;
    combination(int n) : fact(n+1), ifact(n+1)
    {
        assert(n < mod);
        fact.at(0) = 1;
        for(int i=1; i<=n; i++)
        {
            fact.at(i) = fact.at(i-1) * i;
        }
        ifact.at(n) = fact.at(n).inv();
        for(int i=n; i>=1; i--)
        {
            ifact.at(i-1) = ifact.at(i) * i;
        }
    }
    mint operator()(int n, int k)
    {
        if(k < 0 || k > n) return 0;
        return fact.at(n) * ifact.at(k) * ifact.at(n-k);
    }
};

struct permutation
{
    vector<mint> fact, ifact;
    permutation(int n) : fact(n+1), ifact(n+1)
    {
        assert(n < mod);
        fact.at(0) = 1;
        for(int i=1; i<=n; i++)
        {
            fact.at(i) = fact.at(i-1) * i;
        }
        ifact.at(n) = fact.at(n).inv();
        for(int i=n; i>=1; i--)
        {
            ifact.at(i-1) = ifact.at(i) * i;
        }
    }
    mint operator()(int n, int k)
    {
        if(k < 0 || k > n) return 0;
        return fact.at(n) * ifact.at(n-k);
    }

};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M;
    cin >> N >> M;

    combination comb(N);
    permutation perm(M);
    mint ans = 0;
    for(int i=0; i<=N; i++)
    {
        ans += comb(N, i) * (i%2==0 ? 1 : -1) * perm(M, i) * perm(M-i, N-i) * perm(M-i, N-i);
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 18716
import sys

input = sys.stdin.readline


def main():
    A, B, C, D = map(int, input().split())

    if A + B > C + D:
        ans = "Left"
    elif A + B == C + D:
        ans = "Balanced"
    else:
        ans = "Right"

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
#include <iostream>
#include <algorithm>
#define FOR(i,a,b) for(int i=a;i<b;i++)
using namespace std;
int main(){
    int n,k; cin>>n>>k;
    long int ans=0;
    if(k==0){
        FOR(b,k+1,n+1){
            ans+=(n/b)*(b-k)+max(0,n%b-k+1)-1;
        }
    }else{
        FOR(b,k+1,n+1){
            ans+=(n/b)*(b-k)+max(0,n%b-k+1);
        }
    }
    cout<<ans<<endl;
}


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

int main(){
  int n;
  cin >> n;
  
  int hund, ten, one, ans;
  for (int i=n ; ; i++){
    hund = i/100;
    ten = (i-hund*100)/10;
    one = i-hund*100-ten*10;
    if (hund == ten && ten == one){
      ans = i;
      break;
    }
  }
  
  cout << ans << endl;
}

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

bool between(int l, int r, int x) {
  return (l<=x && x<=r);
}

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> L(M), R(M);
  for (int i=0; i<M; i++) {
    cin >> L.at(i) >> R.at(i);
  }
  // 各ゲートすべてに共通して含まれる数字の個数が答え
  int l=L.at(0), r=R.at(0);
  int answer = 0;
  bool possible = true;
  for (int i=0; i<M-1; i++) {
    if (L.at(i+1)<=l && between(l, r, R.at(i+1))) {
      r = R.at(i+1);
    }
    else if (between(l, r, L.at(i+1)) && r<=R.at(i+1)) {
      l = L.at(i+1);
    }
    else if (between(l, r, L.at(i+1)) && between(l, r, R.at(i+1))) {
      l = L.at(i+1);
      r = R.at(i+1);
    }
    else if (R.at(i+1)<l || r<L.at(i+1)) {
      possible = false;
      break;
    }
  }
  if (possible) {
    answer = r-l+1;
  }
  cout << answer << endl;
}

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

#define MOD 1000000007

long long kai[100010];

void init(){
    kai[0] = 1;
    for(int i = 1;i < 100010;i++){
        kai[i] = kai[i-1] * i % MOD;
    }
    return;
}

long long pow_mod(long long n, long long m){
    long long ans = 1;
    while(m > 0){
        if(m & 1) ans = ans * n % MOD;
        n = n*n % MOD;
        m >>= 1;
    }
    return ans;
}

long long combi(int n, int r){
    return kai[n] * pow_mod(kai[n-r], MOD-2) % MOD * pow_mod(kai[r], MOD-2) % MOD;
}

int main(){
    int n;

    init();

    cin >> n;
    n++;

    int cnt[100010];
    memset(cnt, -1, sizeof(cnt));

    int select;

    int a[100010];

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

    for(int i = 0;i < n;i++){
        if(cnt[a[i]] == -1){
            cnt[a[i]] = i;
        }else{
            select = cnt[a[i]] + n-i-1;
            break;
        }
    }

    for(int i = 1;i <= n;i++){
        long long ans = MOD + combi(n, i);
        if(select >= i-1){
            ans -= combi(select, i-1);
        }
        ans %= MOD;
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 2816
#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < (int)(n); i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
using ll = long long;

int main() {
    int n, m, d; cin >> n >> m >> d;

    cout << fixed << setprecision(15);
    if (d == 0) {
        cout << (double)(m - 1) / n << endl;
    } else {
        cout << (double)(m - 1) * 2 * (n - d) / n / n << endl;
    }
    return 0;
}

Measured memory_bytes: 256
<?php
// Your code here!
$input = fgets(STDIN);
$number_array = explode(' ', $input);
$sum = $number_array[0] + $number_array[1];
$substruction = $number_array[0] - $number_array[1];
$square = $number_array[0] * $number_array[1];

echo max($sum, $substruction, $square);
?>


Measured memory_bytes: 3828
/*版权所有，拷贝必究！*/
/*若想获得，请联系许希泉*/
#include<bits/stdc++.h>
#pragma GCC optimize("O999")
const int INF = 0x3f3f3f3f;
int maxn=5000005;
using namespace std;

bool is_pal(string a)
{
    string s=a;
    reverse(s.begin(),s.end());
    if(s==a)
    return true;
    else
    return false;
}
bool is_prime(int n)
{
    if(n==1)
	return false;
    if(n==2||n==3)
	return true;
    if(n%6!=1&&n%6!=5)
	return false;
    for(register int i=5;i*i<=n;i+=6)
    if(n%i==0||n%(i+2)==0)
	return false;
    return true;
}
int main()
{
 	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	string s1,s2,s;
    int k,a,b,n,m,x,y,p,mut=1,sum=0,maxv=0,minv=1E5;
    cin>>k;
    cin>>a>>b;
    for(int i=a;i<=b;i++)
    {
    	if(i%k==0)
    	{
    		cout<<"OK";
    		return 0;
		}
	}
    cout<<"NG";
    return 0;
}


Measured memory_bytes: 3640
#include <iostream>
#include <complex>
#include <vector>
#include <cstdio>
#define X real()
#define Y imag()
#define EPS (1e-10)
#define EQ(a, b) (abs((a) - (b)) < EPS) // 二つのスカラーが等しいかどうか
#define EQV(a, b) (EQ((a).X, (b).X) && EQ((a).Y, (b).Y)) // 二つのベクトルが等しいかどうか
using namespace std;

typedef complex<double> Point; // 点
typedef Point Vector; // ベクトル

struct Segment{ // 線分
  Point p1, p2;
  Segment(){};
  Segment(Point p1, Point p2) : p1(p1), p2(p2) {}; // p1,p2をセット
};

typedef Segment Line; // 直線

typedef vector<Point> Polygon; // 多角形

double dotproduct(Vector a, Vector b) // 内積
{
  return real((conj(a) * b));
}

double crossproduct(Vector a, Vector b) // 外積
{
  return imag(conj(a) * b);
}

double dist(Point p1, Point p2) // 二点間の距離
{
  return abs(p1 - p2);
}

Point project(Line l, Point p) // 射影
{
  double r = dotproduct(p - l.p1, l.p2 - l.p1) / norm(l.p2 - l.p1);
  return l.p1 + (l.p2 - l.p1) * r;
}

Point reflect(Line l, Point p) // 反射
{
  return p + (project(l, p) - p) * 2.0;
}

bool isOrthogonal(Line l1, Line l2)
{
  return EQ(dotproduct(l1.p1 - l1.p2, l2.p1 - l2.p2), 0.0);
}

bool isParallel(Line l1, Line l2)
{
  return EQ(crossproduct(l1.p1 - l1.p2, l2.p1 - l2.p2), 0.0);
}

//-------Counter-Clockwise---------
const int COUNTER_CLOCKWISE = +1;
const int CLOCKWISE = -1;
const int ONLINE_BACK = +2;
const int ONLINE_FRONT = -2;
const int ON_SEGMENT = 0;

int ccw(Point a, Point b, Point c){
  Point x = b - a;
  Point y = c - a;
  if(crossproduct(x, y) > EPS)
    return COUNTER_CLOCKWISE;
  if(crossproduct(x, y) < -EPS)
    return CLOCKWISE;
  if(dotproduct(x, y) < -EPS)
    return ONLINE_BACK;
  if(norm(x) < norm(y))
    return ONLINE_FRONT;
  return ON_SEGMENT;
}

int main()
{
  Point a, b, c;
  cin >> a.X >> a.Y >> b.X >> b.Y;
  int n;
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> c.X >> c.Y;
    int x = ccw(a, b, c);
    if(x == COUNTER_CLOCKWISE)
      cout << "COUNTER_CLOCKWISE" << endl;
    else if(x == CLOCKWISE)
      cout << "CLOCKWISE" << endl;
    else if(x == ONLINE_BACK)
      cout << "ONLINE_BACK" << endl;
    else if(x == ONLINE_FRONT)
      cout << "ONLINE_FRONT" << endl;
    else
      cout << "ON_SEGMENT" << endl;
  }
}

Measured memory_bytes: 1248
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;

int main() {
    int n; cin >> n;
    int rtn = 0;
    for (int i = 1; i <= n; ++i) {
        int dig = log10(i) + 1;
//        cout << dig << endl;
        if (dig % 2 != 0) ++rtn;
    }
    cout << rtn << endl;
}


Measured memory_bytes: 3880
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
#include <string>
#include <set>
#include <map>
using namespace std;

int main()
{
	int32_t N;
	scanf("%d", &N);

	vector<int32_t> B(N - 1);
	for (int32_t i = 0; i < N - 1; i++) {
		scanf("%d", &B[i]);
	}
	vector<int32_t> A(N, 1000000);
	for (int32_t i = 0; i < N - 1; i++) {
		if (A[i] > B[i])
			A[i] = B[i];
		A[i + 1] = B[i];
	}

	int32_t res = 0;
	for (int32_t i = 0; i < N; i++)
		res += A[i];

	printf("%d\n", res);

	return 0;
}


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

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> a(n+1);
  vector<int> b(n+1);
  a[0]=0;
  b[0]=0;
  for(int i=1;i<n+1;i++){
    cin >> a[i];
    b[i]=a[i];
  }
  int cnt=0;
  for(int i=n;i>=1;i--){
    int sum=0;
    for(int j=i;j<=n;j+=i){
      sum+=b[j];
    }
    b[i]=sum%2;
    if(b[i]){
      cnt++;
    }
  }
  cout << cnt << endl;
  for(int i=1;i<n+1;i++){
    if(b[i]){
      cout << i << endl;
    }
  }
}


Measured memory_bytes: 2432
#include <bits/stdc++.h>
using namespace std;
long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
    long double a,b;
    cin>>a>>b;
    long double res=a*b;
    long long ans=floor(res);
    cout<<ans<<endl;
    

    



    return 0;
}

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

int main() {
 long long int k,a,b,i,ans;

  scanf("%ld %ld %ld",&k,&a,&b);

  if(a>=b-2 || k-a<=0)
    ans=1+k;
  else {
    if( (k-a)%2==0)
      ans=(k-a)/2*b - (k-a-2)/2*a + 1;
    
    else ans=(k-a+1)/2*b - (k-a-1)/2*a;
    }
  printf("%ld",ans);
  
}

Measured memory_bytes: 128
n = int(input())
a = list(map(int,input().split()))
left = []
right = []
if n % 2 == 0:
    for i in range(1,n+1):
        if i % 2 == 0:
            left.append(a[i-1])
        else:
            right.append(a[i-1])
else:
    for i in range(1,n+1):
        if i % 2 != 0:
            left.append(a[i-1])
        else:
            right.append(a[i-1])
left.reverse()
for i in left:
    print(i,end=' ')
for i in right:
    print(i,end=' ')

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

int main(){
    int N;
    cin >> N;
    vector<int> d(N);
    for(int i=0; i<N; i++){
        cin >> d.at(i);
    }

    sort(d.begin(),d.end());
    cout << d.at(N/2)-d.at(N/2-1) << endl;
}

Measured memory_bytes: 640
#!/usr/bin/env python3
import sys
import math

MOD = 10**9+7  # type: int

def combi_count(n, r):
    x = 1
    y = 1
    for i in range(1, r+1):
        x = x * (n-i) % MOD
        y = y * i % MOD

    # nCr = n!/((n-r)!*r!) = (n!/(n-r)!) / r! 
    #     :=                 (    x    ) / y

    # x / y            % MOD
    # x * y^(-1)       % MOD
    # x * y**(MOD - 2) % MOD (from フェルマー定理)

    return x * pow(y, MOD-2, MOD) % MOD

def solve(X: int, Y: int):
    a = int((2*Y - X)/3)
    b = int((2*X - Y)/3)
    if ( ((2*Y - X)%3 != 0) and ((2*X - Y)%3 != 0) )  or ((a<0) or (b<0)):
        ans = 0
    else:
        ans = combi_count(a+b+1, min(a, b))
    print(ans)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    X, Y = map(int, input().split())
    solve(X, Y)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define mod 1000000007
#define pb push_back
#define pi pair<int,int>
#define vi vector<int>
#define vpi vector< pi >
const int N=200010;
ll a[N];
int main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	map<ll,ll>m;
	m[0ll]=1ll;
	ll res=0;
	for(int i=1;i<=n;i++)
	{
		a[i]+=a[i-1];
		if(m.find(a[i])!=m.end())
		{
			//cout<<i<<" "<<a[i]<<"\n";
			res+=m[a[i]];
		}
		if(m.find(a[i])!=m.end())
			m[a[i]]+=1;
		else
			m[a[i]]=1ll;
	}
	cout<<res;
	return 0;
}

Measured memory_bytes: 15872
#include <stdio.h>

int main(void) {
int a,b;
scanf("%5d",&a);
scanf("%5d",&b);
 if(a>b){
   printf("a > b\n",a,b);
 }
 if(a<b){
   printf("a < b\n",a,b);
 }
 if(a==b){
   printf("a == b\n",a,b);
 }
}


Measured memory_bytes: 2596
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int main(){
    int n,q; cin >> n >> q;
    queue<pair<string,int>> que;
    for(int i =0; i < n; ++i){
        string s; int x;
        cin >> s >> x;
        que.push(make_pair(s,x));
    }
    long long time = 0;
    while(!que.empty()){
        string s = que.front().first;
        int x = que.front().second;
        que.pop();
        time += min(q,x);
        x = max(0, x-q);
        if(x == 0){
            cout << s << " " << time << endl;
        }
        else{
            que.push(make_pair(s,x));
        }
    }
    return 0;
}


Measured memory_bytes: 6296
#include<iostream>
#include<vector>
#include<string>
#include<cmath>

using namespace std;

typedef long long ll;

int main(){
ll X,Y; cin >> X >> Y;
  ll i = 0;
  ll a = X;
  while( a * (ll) pow(2.0,i) <= Y){ i++;}
  
  cout <<  i   <<  endl; return 0;}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define MAXN 200009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int s[2][MAXN<<2],cnt[MAXN<<2],pw[2][MAXN],arr[MAXN];
int modi[]={INF,INF+2};
int mod(int t,ll x){
	return (x%modi[t]);	
}
void upd(int p,int v,int nd,int x,int y){
	if(x==y){
		s[0][nd]=mod(0,x*v);
		s[1][nd]=mod(1,x*v);
		cnt[nd]=v;
		return;	
	}		
	int mid=(x+y)>>1;
	if(p<=mid)
		upd(p,v,nd<<1,x,mid);
	else
		upd(p,v,nd<<1|1,mid+1,y);
	for(int j=0;j<2;j++)
		s[j][nd]=mod(j,s[j][nd<<1]*1LL*pw[j][cnt[nd<<1|1]]+s[j][nd<<1|1]);		
	cnt[nd]=cnt[nd<<1]+cnt[nd<<1|1];
}
int pre[2][MAXN],suf[2][MAXN];
ll cof[]={701,703};
int main(){	
    //freopen("file.in", "r", stdin);
    int n,k;
    scanf("%d%d",&n,&k);
    pw[0][0]=pw[1][0]=1;
    for(int i=1;i<=n;i++)
    	for(int j=0;j<2;j++)
    		pw[j][i]=mod(j,pw[j][i-1]*cof[j]);
    for(int i=1;i<=n;i++)
    	scanf("%d",arr+i),arr[i]++;
	for(int i=1;i<=n;i++)
		for(int j=0;j<2;j++)
			pre[j][i]=mod(j,pre[j][i-1]*cof[j]+arr[i]);
	for(int i=n;i>=1;i--)
		for(int j=0;j<2;j++)
			suf[j][i]=mod(j,suf[j][i+1]+mod(j,pw[j][n-i]*1LL*arr[i]));
	for(int i=1;i<=k;i++)
		upd(arr[i],1,1,1,n);
	vector<PII>v;	
	for(int i=1;i+k<=n+1;i++){
		PII tmp=mp(mod(0,pre[0][i-1]*1LL*pw[0][k]+s[0][1]),mod(1,pre[1][i-1]*1LL*pw[1][k]+s[1][1]));
		tmp=mp(mod(0,tmp.ff*1LL*pw[0][n-i-k+1]+suf[0][i+k]),mod(1,tmp.ss*1LL*pw[1][n-i-k+1]+suf[1][i+k]));
		v.pb(tmp);
		upd(arr[i+k],1,1,1,n);
		upd(arr[i],0,1,1,n);
	}
	sort(all(v));
	v.erase(unique(all(v)),v.end());
	printf("%d\n",v.size());
	return 0;
}


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

ll N;
vector<vector<ll>> to;
ll M;
vector<pair<ll,ll>> P;

ll sum = 0LL;

ll num = 0LL; map<pair<ll,ll>,ll> mp;

vector<vector<ll>>edges; //edges[x][y]で、xとyの間に含まれる辺を全てbitで管理

ll p2(ll a){  //2のa乗
  if( a == 0 ){ return 1LL;}
  else if (a == 1){ return 2LL;}
  else{
    if( a % 2 == 0 ){ 
      return p2(a/2)*p2(a/2);
    }
    else{
      return p2((a-1)/2)*p2((a-1)/2)*2LL;
    }
  }
}
      

void dfs(ll par,ll pos){
  //0起点のdfsで、辺にナンバリングしていく
  if(par != -1LL ){
    //一番初め par == -1の場合は記録しようがない
    
    mp[{par,pos}] = num; 
    mp[{pos,par}] = num; 
    //向きなしで記録する
    num++; //木だから、同じ辺を二回更新することはないはず
  }
 
  for(auto v : to[pos]){
    if(v == par){ continue;}
    
    dfs(pos,v);
  }
  
  return;
}

void ddfs(ll par, ll pos, ll start,ll val){
  
  ll res = val;
  
  if( par != -1 ){ res |= (1LL << mp[{par,pos}]);}
  
  if( par != -1 ){ 
    //par == -1の時、pos == startだから、同じ点同士を結ぶ辺を記録することになり無意味
 
    edges[start][pos] |= res;
    edges[pos][start] |= res; //こちらも向きなしで記録する
    
  }
   
  for(auto u : to[pos]){
    if( u == par ){ continue;}
    
    ddfs(pos,u,start,res); //startは変化なし
  
  }
  
  return ;
}

  
signed main(void){ 
  
  cin >> N;
  to.resize(N);
  edges = vector<vector<ll>> (N,vector<ll>(N));
  
  for(ll i = 1; i < N; i++){
    ll a,b; cin >> a >> b; a--; b--;
    to[a].push_back(b); to[b].push_back(a);
  }
  
  dfs(-1LL,0LL);
  //ここまでOK
  
  for(ll i = 0LL; i < N; i++){ 
    ddfs(-1LL,i,i,0LL);
  }
  
  //ここまでOK
  
  cin >> M; P.resize(M); //条件を列挙する
  
  for(ll i = 0LL; i < M; i++){
    ll u,v; cin >> u >> v; u--; v--;
    //uとvの間は少なくとも一つは黒で塗る必要がある
    P[i] = {u,v};
  }
   
  for(ll bit = 1LL; bit < (1LL << M); bit++){
    //立ったbit全ての積を取って、包除原理を適用 i = 0,,,M-1はそれぞれの条件を使うか表す
    
    ll value = 0LL;
    bool even = true;
    
    for(ll i = 0; i < M; i++){
      if( (bit >> i) & 1LL ){  // P[i].firstとP[i].secondを結ぶ辺全てを記録
        even = !even;
        //i番目の条件に含まれている辺全てを追加
        value |= edges[P[i].first][P[i].second];
        
      }
    }
    //valueに含まれているbit全てを白で塗る必要がある
    
    ll p = 0LL;
    
    for(int i = 0LL; i <= N; i++){ //valueはNケタぐらいまではいく
      if( (value >> i) & 1LL ){ p++;}
    }
    
    ll res = 0LL;
    
    if(!even){
      res += p2(N-1LL-p);
    }
    else{
      res -= p2(N-1LL-p);
    }
    
    sum += res;
    
  }
  
  cout << p2(N-1LL)-sum << endl;
  
  return 0;
}
    

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

int main() {
    int n;
    ll tt;
    cin >> n >> tt;
    ll t[n];
    for (int i  = 0; i < n; i++) {
        cin >> t[i];
    }
    ll ans = 0;
    ll st = 0;
    for (int i = 1; i < n; i++) {
        if (t[i] <= t[i - 1] + tt) {
            continue;
        } else {
            ans += t[i - 1] + tt - st;
            st = t[i];
        }
    }
    ans += t[n - 1] + tt - st;


    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<LL,LL>
#define x first
#define y second
#define pi acos(-1)
#define sqr(x) ((x)*(x))
#define pdd pair<double,double>
#define MEMS(x) memset(x,-1,sizeof(x))
#define MEM(x) memset(x,0,sizeof(x))
#define less Less
#define EPS 1e-4
#define arg ARG
#define cpdd const pdd
#define rank Rank
#define KK 500
#define MXN 200005
vector<int> v[100005],rv[100005];
int vis[100005];
LL cnt=0;
vector<int> stk;
void dfs(int x){
    if(vis[x])return;
    vis[x]=1;
    cnt++;
    stk.pb(x);
    for(auto it:v[x]){
        dfs(it);
    }
    for(auto it:rv[x]){
        dfs(it);
    }
}
void dfs2(int x,int step){
    if(vis[x]&(1<<step))return ;
    vis[x]|=(1<<step);
    for(auto it:v[x]){
        dfs2(it,(step+1)%3);
    }
    for(auto it:rv[x]){
        dfs2(it,(step+2)%3);
    }
}
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    pii p[100005];
    for(int i = 0;i<m;i++){
        int x=i+1,y=(i+1)%n+1;
        scanf("%d %d",&x,&y);
        v[x].pb(y);
        rv[y].pb(x);
    }
    LL ans=0;
    for(int i = 1;i<=n;i++){
        if(!vis[i]){
            cnt=0;
            stk.clear();
            dfs(i);
            for(auto it:stk)
            vis[it]=0;
            dfs2(i,0);
            int ok=0;
            for(auto it:stk){
                if(__builtin_popcount(vis[it])!=1){
                    ok=1;
                    ans+=cnt*cnt;
                    assert(__builtin_popcount(vis[it])!=0);
                    break;
                }
            }
            if(!ok){
                LL tot[3]={0,0,0};
                for(auto it:stk){
                    if(vis[it]==1)tot[0]++;
                    if(vis[it]==2)tot[1]++;
                    if(vis[it]==4)tot[2]++;
                }
                if(tot[0]&&tot[1]&&tot[2])
                ans+=tot[0]*tot[1]+tot[1]*tot[2]+tot[2]*tot[0];
                else{
                    for(auto it:stk){
                        ans+=v[it].size();
                    }
                }
            }
        }
    }
    printf("%lld\n",ans);
}
/*

b[i]*K!/(i)!*(K-i)!
*/

Measured memory_bytes: 26108
// https://atcoder.jp/contests/agc033/tasks/agc033_b

#include "algorithm"
#include "cmath"
#include "functional"
#include "iomanip"
#include "iostream"
#include "map"
#include "numeric"
#include "queue"
#include "set"
#include "string"
#include "vector"
#define rep(i, to) for (ll i = 0; i < (to); ++i)
#define rep1(i, to) for (ll i = 1; i <= (to); ++i)
#define repf(i, from, to) for (ll i = from; i < (to); ++i)
#define repr(i, from) for (ll i = from - 1; i >= 0; --i)
#define all(vec) vec.begin(), vec.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
template <typename T>
using V = vector<T>;
using VL = V<ll>;
using VVL = V<VL>;
template <typename T, typename U>
using P = pair<T, U>;
using PL = P<ll, ll>;
using VPL = V<PL>;
template <typename T>
inline bool chmax(T& a, T b);
template <typename T>
inline bool chmin(T& a, T b);
void print_ints(vector<ll> v);
template <typename T>
void drop(T a);

const ll INF = 1e18;

void solve() {
  ll H, W, N, sr, sc;
  string S, T;
  cin >> H >> W >> N >> sr >> sc >> S >> T;

  // 1 次元の問題に帰着
  // コマが残れば return される
  auto solve_one_dim = [](ll start, ll limit, VL ss, VL ts) {
    // [l, r] にコマがあれば ok
    ll l = 1;
    ll r = limit;

    repr(i, ts.size()) {
      ll t = ts[i];
      if (t == 1) l = max(l - 1, 1ll);
      if (t == -1) r = min(r + 1, limit);

      ll s = ss[i];
      if (s == 1) r -= 1;
      if (s == -1) l += 1;

      if (r < l) drop("NO");
    }

    if (!(l <= start && start <= r)) drop("NO");
  };

  VL ss_w(N), ts_w(N), ss_h(N), ts_h(N);

  auto fill = [N](VL& w, VL& h, string& str) {
    rep(i, N) {
      char ch = str[i];
      if (ch == 'R') w[i] = 1, h[i] = 0;
      if (ch == 'L') w[i] = -1, h[i] = 0;
      if (ch == 'U') w[i] = 0, h[i] = -1;
      if (ch == 'D') w[i] = 0, h[i] = 1;
    }
  };

  fill(ss_w, ss_h, S);
  fill(ts_w, ts_h, T);

  solve_one_dim(sr, H, ss_h, ts_h);
  solve_one_dim(sc, W, ss_w, ts_w);

  cout << "YES" << endl;
}

struct exit_exception : public std::exception {
  const char* what() const throw() { return "Exited"; }
};

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

  try {
    solve();
  } catch (exit_exception& e) {
  }

  return 0;
}
#endif

template <typename T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <typename T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

void print_ints(vector<ll> v) {
  rep(i, v.size()) {
    if (i > 0) {
      cout << " ";
    }

    cout << v[i];
  }

  cout << endl;
}

template <typename T>
void drop(T res) {
  cout << res << endl;
  throw exit_exception();
}


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

using namespace std;
     
int main(void){
  char input[4];
  string judge = "No";

  cin >> input[0] >> input[1] >> input[2] >> input[3];
  
  char hantei1 = 0;
  char hantei2 = 0;
  int count_char1 = 0;
  int count_char2 = 0;

  for (int i=0; i<4; i++) {
    if (hantei1 == 0 || hantei1 == input[i]) {
      hantei1 = input[i];
      count_char1 += 1;
    } else if (hantei2 == 0 || hantei2 == input[i]) {
      hantei2 = input[i];
      count_char2 += 1; 
    } else {
      cout << "No";
      return 0;
    }
  }
  
  if (count_char1 == 2 && count_char2 == 2) {
    cout << "Yes";
    return 0;
  }
  
  cout << "No";
  
  return 0;
}

Measured memory_bytes: 256
H,N = list(map(int,input().split()))

a = [0]*N
b = [0]*N

for i in range(N):
	a[i],b[i] = list(map(int,input().split()))

inf = float("inf")
dp = [inf]*(H+1)
dp[0] = 0
dp[1] = min(b)

for h in range(1,H+1):
	for n in range(N):
		h_temp = h-a[n]
		if h_temp <= 0:
			dp[h] = min(dp[h],b[n])
		else:
			dp[h] = min(dp[h],dp[h_temp]+b[n])
print(dp[H])


Measured memory_bytes: 42732
#include "bits/stdc++.h"
typedef long long ll;
using namespace std;

int main() {
    int k, x;
    cin >> k >> x;
    
    int minimum = x - (k - 1);
    int maximum = x + (k - 1);
    for (int i = minimum; i <= maximum; i++) {
        if (i != minimum) cout << " ";
        cout << i;
    }
    cout << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;
int a[1005],b[1005],to[10005];
bool vis[1005];
int main () {
	int n,ans=0;
	scanf ("%d",&n);
	for (int i=0;i<n;i++) {
		scanf ("%d",&a[i]);
		b[i]=a[i];
	}
	sort (b,b+n);
	for (int i=0;i<n;i++) {
		to[b[i]]=i;
	}
	for (int i=0;i<n;i++) {
		if (vis[i]) continue;
		int pos=i,sum=0,mn=1e4+7,cnt=0;
		while (!vis[pos]) {
			vis[pos]=true;
			sum+=a[pos];
			mn=min(mn,a[pos]);
			cnt++;
			pos=to[a[pos]];
		}
		ans+=min(sum+(cnt-2)*mn,sum+mn+(cnt+1)*b[0]);
	}
	printf ("%d\n",ans);
    return 0;
}


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

int main(void){
  int i,a=0,z=0,len,ans;
  char str[200001];
  scanf("%s",str);
  len=strlen(str);
  for(i=0;i<len;i++){
    if(str[i]=='A'){
      a=i;
      break;
    }
  }
    //printf("%d\n",a);
  for(i=len;i>0;i--){
    if(str[i]=='Z'){
      z=i;
      break;
    }
  }
  ans=z-a+1;
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <functional>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <cmath>
#include <cstdio>

using namespace std;

typedef long long ll;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)

ll f(ll n)
{
    ll c = n / 2 + 1;
    if (n % 2 == 0) c--;
    ll ans;
    if (c % 2 == 0) ans = 0;
    else ans = 1;
    if (n % 2 == 0) ans = ans ^ n;
    return ans;
}

int main(int argc, char **argv)
{
    ll A, B;
    cin >> A >> B;

    if (A == 0)
        cout << f(B) << endl;
    else {
        cout << (f(B) ^ f(A - 1)) << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
void main()
{
int n,c,i,j,s=0;
scanf("%d",&n);
scanf("%d",&c);
  i=0;
  j=n;
while(i<=n && j>=0)
{
	s = 2*i+4*j;
  	if(s==c){
      printf("Yes");
  	break;
      
    }
  i++;
  j--;
}
if(i>n)
  printf("No");
}


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


int main(){
    int x,y,z;
    cin >> x >> y >> z;
    x -= z;
    cout << x/(y+z) << endl;
}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int 
const int MOD = 1e9+7;
const int MAXN = 2e5+5;

int32_t main()
{
   
    IOS
    int n;
    cin>>n;
    vector<int>dp(3);
    for(int d=0;d<n;d++){
        vector<int>ndp(3,0);
        vector<int>c(3);
        for(int i=0;i<3;i++){
            cin>>c[i];
        }
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                if(i!=j)
                ndp[j]=max(ndp[j],c[j]+dp[i]);
            }
        }
        dp=ndp;
    }
    cout<<max({dp[0],dp[1],dp[2]});
    return 0;
}
        

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vvi vector<vi>
#define DBG_N(hoge) cerr<<" "<<(hoge)<<endl;
#define DBG cerr<<"!"<<endl;
#define BITLE(n) (1LL<<((ll)n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))
#define ALL(a) (a).begin(),(a).end()
using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n;cin>>n;
  vi A(n);
  for(auto &a:A)cin>>a;
  ll ans=0;
  for(int i=0;i<n;i++)
    for(int j=i+1;j<n;j++)
      ans+=A[i]*A[j];
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAX 55

int p_judge(int x) {
    int i=2;
    while(x>=i*i) {
        if(x%i==0)
            return 0;
        i++;
    }
    return 1;
}

int main(void) {
    int n, i, j=0, k;
    int a[MAX];
    scanf("%d", &n);
    
    for(i=11; i<=55555; i+=10) {
        if(p_judge(i)==1) {
            a[j] = i;
            j++;
            if(j==n) {
                for(k=0; k<n; k++) {
                    printf("%d ", a[k]);
                }
                return 0;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        Scanner stdIn = new Scanner(System.in);
        
        int a = stdIn.nextInt();
        int b = stdIn.nextInt();
        //int num[] = new int[3];
        //String s = stdIn.next();
        //char c[] = s.toCharArray();
        //boolean flag = true;
        
        if(a <= b){
            System.out.println(a);
        }else{
            System.out.println(a - 1);
        }
        
        
        //System.out.println();
        //System.out.print();
    }
}


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

typedef long long int ll ;

ll gcd(ll aaa,ll bbb) {
    if(bbb==0) {
        return aaa;
    }
    return gcd(bbb,aaa%bbb);
}

ll lcm(ll m,ll n)
{
    if ( ( 0 == m ) || ( 0 == n ) )
        return 0;

    return ((m / gcd(m, n)) * n);
}

int main() {

	long N,K;
	cin >> N >> K;
	long a[N],b[N],s=0;
	pair<long,long>p[N];
	for(long i = 0; i < N; i++) {
		cin >> a[i] >> b[i];
		p[i] = make_pair(a[i],b[i]);
	}
	sort(p,p+N);
	
	for(long i = 0; i < N; i++) {
		s += p[i].second;
		if(s >= K) {
			cout << p[i].first << endl;
			return 0;
		}
	}

	return 0;
}


Measured memory_bytes: 3328
using System;

namespace AtCoder
{
    internal class Program
    {
        private static void Main()
        {
            var k = new[] {"AC", "WA", "TLE", "RE"};
            var c = new[] {0, 0, 0, 0};
            var n = int.Parse(Console.ReadLine() ?? "");
            for (var i = 0; i < n; i++)
            {
                var v = Console.ReadLine() ?? "";
                for (var j = 0; j < k.Length; j++) if (v == k[j]) c[j]++;
            }
            for (var i = 0; i < k.Length; i++) Console.WriteLine($"{k[i]} x {c[i]}");
        }
    }
}


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

#include <algorithm>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;

long long mod = 1000000007;

long long modpow(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return (t * t) % mod;
    } else {
        return (modpow(m, n - 1) * m) % mod;
    }
}
int power(long long x, long long y, long long p) {
    long long res = 1;  // Initialize result

    x = x % p;  // Update x if it is more than or
                // equal to p

    while (y > 0) {
        // If y is odd, multiply x with result
        if (y & 1) res = (res * x) % p;

        // y must be even now
        y = y >> 1;  // y = y/2
        x = (x * x) % p;
    }
    return res;
}

long long modInverse(long long n, long long p) { return power(n, p - 2, p); }

long long nCrModPFermat(long long n, long long r, long long p) {
    if (r == 0) return 1;
    long long fac[n + 1];
    fac[0] = 1;
    for (long long i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % p;

    return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p;
}

void yes() {
    cout << "Yes" << endl;
    exit(0);
}
void no() {
    cout << "No" << endl;
    exit(0);
}
#define REP(i, n) for (long long i = 0; i < (n); i++)

signed main() {
    long long n, a, b;
    cin >> a;
    double pi = 3.141592653589793238;
    cout << 2 * a * pi << endl;
}

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

const int INF = 1001001001;
vector<int> to[100005];      //インデックスに対応する部屋が隣接している部屋

int main() {
    int n,m;
    cin >> n >> m;
    for(int i = 0;i < m;i++){
        int a,b;
        cin >> a >> b;
        --a; --b;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    queue<int> q;
    vector<int> dist(n,INF);
    vector<int> pre(n,-1);
    dist[0] = 0;
    q.push(0);
    while(!q.empty()){
        int v = q.front(); q.pop();
        for(int u : to[v]){
            if (dist[u] != INF) continue;
            dist[u] = dist[v] + 1;
            pre[u] = v;
            q.push(u);
        }
    }
    cout << "Yes" << endl;
    for(int i = 0;i < n;i++){
        if(i == 0) continue;
        int ans = pre[i];
        ++ans;
        cout << ans << endl;
    }
}

Measured memory_bytes: 10728
//
// Created by swift on 2020/8/6.
//
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct edge{
    int s,t;
}e[200001];
vector<int>v[1001];
int vis[1001],a[1001][1001],b[1001][1001];
void dfs1(int now,int st){
    vis[now]=1;
    a[st][now]=1;
    for(int i=0;i<v[now].size();i++){
        if(!vis[v[now][i]]){
            dfs1(v[now][i],st);
        }
    }
}
int col[1001];
void dfs2(int now,int st,int type,int c){
    if(type==0){
        col[now]=c;
    }
    else{
        b[st][now]=(col[now]!=c);
    }
    vis[now]=1;
    for(int i=0;i<v[now].size();i++){
        if(!vis[v[now][i]])
        dfs2(v[now][i],st,type,c);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&e[i].s,&e[i].t);
        v[e[i].s].push_back(e[i].t);
    }
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        dfs1(i,i);
    }
    for(int i=1;i<=n;i++){
        memset(col,0,sizeof(col));
        memset(vis,0,sizeof(vis));
        vis[i]=1;
        for(int j=0;j<v[i].size();j++){
            if(!vis[v[i][j]]){
                dfs2(v[i][j],i,0,j+1);
            }
        }
        memset(vis,0,sizeof(vis));
        vis[i]=1;
        for(int j=v[i].size()-1;j>=0;j--){
            if(!vis[v[i][j]]){
                dfs2(v[i][j],i,1,j+1);
            }
        }
    }
    /*for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            cout<<a[i][j]<<" ";
            if(j==n)cout<<endl;
        }
    cout<<endl;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            cout<<b[i][j]<<" ";
            if(j==n)cout<<endl;
        }*/
    for(int i=1;i<=m;i++){
        if(a[e[i].t][e[i].s]^b[e[i].s][e[i].t]){
            puts("diff");
        }
        else{
            puts("same");
        }
    }
    return 0;
}


Measured memory_bytes: 14508
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;
int main() {
  string S;
  cin >> S;
  bool alpha[26];
  for (int i = 0; i < 26; i++) {
    alpha[i] = false;
  }
  if (S == "zyxwvutsrqponmlkjihgfedcba") {
    cout << -1 << endl;
    return 0;
  }
  if (S.size() != 26) {
    for (int i = 0; i < S.size(); i++) {
      alpha[S[i] - 'a'] = true;
    }
    for (int i = 0; i < 26; i++) {
      if (!alpha[i]) {
        S += 'a' + i;
        break;
      }
    }
    cout << S << endl;
  } else {
    int end;
    for (int i = 25; i >= 1; i--) {
      if (S[i-1] < S[i]) {
        end = i;
        break;
      }
    }
    S = S.substr(0,end);
    for (int i = 0; i < S.size() - 1; i++) {
      alpha[S[i] - 'a'] = true;
    }
    for (int i = 0; i < 26; i++) {
      if (S[S.size() - 1] < 'a' + i && !alpha[i]) {
        S[S.size() - 1] = 'a' + i;
        break;
      }
    }
    cout << S << endl;
  }
  return 0;
}

Measured memory_bytes: 256
<?php
    class Answer
    {
        private $sequence;
        private $sequence_len;
        
        public function __construct()
        {
            while(1){
                $line = FGETS(STDIN);
                if($line == false){
                    break;
                }
                $line = trim($line);
                $lines[] = $line;
            }
            $this->sequence_len = $lines[0];
            $this->sequence = $lines[1];
        }
        
        
        public function insertSort()
        {
            echo $this->sequence. "\n";
            $seq = explode(' ',$this->sequence);
            
            for($i = 1; $i < $this->sequence_len; $i++){
                $v = $seq[$i];
                $j = $i - 1;
                while($j >= 0 && $seq[$j] > $v){
                    $seq[$j+1] = $seq[$j];
                    $j--;
                     $seq[$j+1] = $v;
                }
                echo implode(" ", $seq) . "\n";
            }
        }
    }
    $answer = new Answer;
    $answer->insertSort();


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

class point {
public:
	int x, y;
	point() {}
	point(int a, int b) { x = a; y = b; }
	point operator +( point p ) { return point( x + p.x, y + p.y ); }
	point operator -( point p ) { return point( x - p.x, y - p.y ); }
	point operator *( int a ) { return point( x * a, y * a ); }
	point operator /( int a ) { return point( x / a, y / a ); }
};

int dot( point a, point b ) { return a.x * b.x + a.y * b.y; }
int cross( point a, point b ) { return a.x * b.y - a.y * b.x; }

int main()
{
	int n;
	cin >> n;
	vector<point> g( n );
	for( int i = 0; i < n; i++ ) {
		cin >> g[i].x >> g[i].y;
	}

	int q;
	cin >> q;
	for( int i = 0; i < q; i++ ) {
		point p;
		cin >> p.x >> p.y;
		bool x = false;
		int ans = 0;
		for( int j = 0; j < n; j++ ) {
			point a = g[j] - p;
			point b = g[(j + 1) % n] - p;
			if( dot( a, b ) <= 0 && cross( a, b ) == 0 ) { ans = 1; break; }
			if( a.y > b.y ) swap( a, b );
			if( a.y <= 0 && b.y > 0 && cross( a, b ) > 0 ) x = !x;
		}
		if( ans == 0 && x ) ans = 2;
		cout << ans << endl;
	}
}



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

if (a <= 0 and b >= 0) or (a==0) or (b==0):
  print("Zero")
elif (a > 0) or (b<0 and (b-a)%2==1):
  print("Positive")
elif (b<0 and (b-a)%2==0):
  print("Negative")

Measured memory_bytes: 9124
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)) {
			while(sc.hasNext()) {
				ArrayList<int[]> list = new ArrayList<int[]>();
				
				int N = sc.nextInt();
				int M = sc.nextInt();
				if(N + M == 0) break;
				boolean[][] log = new boolean[M+1][1261];
				
				int r = sc.nextInt();
				while(r-- != 0) {
					int t = sc.nextInt();
					int n = sc.nextInt();
					int m = sc.nextInt();
					int s = sc.nextInt();
					if(s == 1) {
						list.add(new int[] {n, m, t});
					}
					else {
						int st = -1;
						for(int i=0; i<list.size(); i++) {
							int[] h = list.get(i);
							if(h[0] == n && h[1] == m) {
								st = h[2];
								list.remove(i);
								break;
							}
						}
						for(int i=st; i<t; i++) {
							log[m][i] = true;
						}
					}
				}
				
				int q = sc.nextInt();
				while(q-- != 0) {
					int sec = 0;
					int ts = sc.nextInt();
					int te = sc.nextInt();
					int m = sc.nextInt();
					for(int i=ts; i<te; i++) {
						if(log[m][i]) sec++;
					}
					System.out.println(sec);
				}
			}
		}
	}
}


Measured memory_bytes: 118856
#include<bits/stdc++.h>
#define pb push_back
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair <int,int> PAIR;
const int N = 1e5 + 7;
const double pi = acos(-1);
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const ll inf = 0x3f3f3f3f;

int main(){	
	int x;
	cin >> x;
	if(x >= 30)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3600
// 失敗するからこそ そこから立ち向かって行く強さがあってそんな強さが本当の強さだと私は思うから
// ぜったいあきらめない
#include<bits/stdc++.h>
using namespace std;

#if defined(DAIJOBU)
#include "/home/ichigo/debug.hpp"
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define deb(x...)
#endif
#define FIO {ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);}
	

int main(){
	FIO
	
	string s;
	while(cin >> s && s != "-"){
		int m;
		cin >> m;
		while(m--){
			int h;
			cin >> h;
			rotate(s.begin(), s.begin() + h, s.end());
		}
		cout << s << '\n';
	}
	return 0;
}



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

#define CK(N, A, B) (A <= N && N < B)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define RREP(i, a, b) for (int i = (b - 1); a <= i; i--)
#define F first
#define S second
#define ll long long

const int INF = 1e9;
const long long LLINF = 1e18;

using namespace std;

/*==================================================*/

/*==================================================*/

int N , M, K;

int main() {
    cin>>N>>M>>K;
    REP(i,0,N+1){
        REP(j,0,M+1){
            if((M-j)*i + (N-i)*j == K){
                cout<<"Yes"<<endl;
                return 0;
            }
        }
    }
    cout<<"No"<<endl;
    return 0;
}


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

using namespace std;
typedef long long ll;
#define rep(i,j,n) for (ll i = j; i < (n); i++)
#define CLR(mat,f) memset(mat, f, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const int INF = 1000000;
const double PI=3.14159265359;

int main(){

  ll n;cin>>n;
  ll a[n];rep(i,0,n)cin>>a[i];
  sort(a,a+n);

  vector<ll>s(n+1,0);
  rep(i,0,n)s[i+1]=s[i]+a[i];

  ll num=0;
  rep(i,1,n){
    if(s[i]*2<a[i])num=i;
  }

  out(n-num);


  return 0;
}


Measured memory_bytes: 1792
// </> : towhid1zaman

#include "bits/stdc++.h"
using namespace std;
typedef unsigned long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair< int, int > pii;
typedef pair< pii, int > ppi;
#define fill(a,b) memset(a,b,sizeof(a))
#define all(v) (v).begin(),(v).end()
#define sp(k) cout<<setprecision(k)<<fixed;
#define rep(i,a) for(int i=0;i<a;i++)
#define rep1(i,a,b) for(int i=(a);i<=(b);++i)
#define irep(i,b,a) for(int i=(b);i>=(a);--i)
#define minv(v) *min_element(all(v))
#define maxv(v) *max_element(all(v))
#define unq(v) sort(all(v)),(v).erase(unique(all(v)),(v).end())
#define _ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
#define sqr(a) ((a)*(a))
#define sz(a) int(a.size())
#define ff first
#define ss second
#define pb push_back

const double pi = acos(-1.0);
const int mod = 1000000007; // (int)1e9+7
const int inf = 0x3f3f3f3f;// (int)3e18;
const int maxn = 2000100;



int main(){
        _
        ll Lucas[100]{};
        Lucas[0] = 2;
        Lucas[1] = 1;
        for(int i = 2; i<=87; i++){
            Lucas[i] = Lucas[i-1] + Lucas[i-2];
        }
        ll n; cin >> n;
        cout<<Lucas[n]<<endl;

return 0;
}



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

using namespace std;
using ll = long long;

int main() {
    ll H, N;
    cin >> H >> N;
    vector<int> a(N);
    for(int i = 0; i < N; i++) cin >> a.at(i);
    ll total = std::accumulate(a.begin(), a.end(), 0ll);
    if (total >= H) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
const int INF = 1001001001;
const int MOD = 1000000007;
typedef long long ll;


int main(){
    string S;
    cin >> S;
    int n = S.size();
    vector<ll> a(n + 1, 0);
    ll cnt = 0;
    for(int i = 0; i < n; i++){
        if(S[i] == '<'){
            cnt++;
            a[i + 1] = cnt;
        }else if(S[i] == '>'){
            cnt = 0;
        }else{
            cout << "error" << endl;
        }
    }
//    // debug
//    rep(i, n + 1){
//        if(i) cout << " ";
//        cout << a[i];
//    }
//    cout << endl;

    cnt = 0;
    for(int i = n - 1; i >= 0; i--){
        if(S[i] == '>'){
            cnt++;
            a[i] = max(a[i], cnt);
        }else if(S[i] == '<'){
            cnt = 0;
        }else{
            cout << "error" << endl;
        }
    }

//    // debug
//    rep(i, n + 1){
//        if(i) cout << " ";
//        cout << a[i];
//    }
//    cout << endl;
    ll ans = 0;
    for(int i = 0; i <= n; i++){
        ans += a[i];
    }
    cout << ans << endl;
    return 0;


}


Measured memory_bytes: 4740