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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define _GLIBCXX_DEBUG
#define fi first
#define se second

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vd = vector<double>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vvd = vector<vd>;
using vvvi = vector<vvi>;
using vvvll = vector<vvll>;
using vvvd = vector<vvd>;

const double pi=acos(-1);
const ll MOD=1e9+7;
const ll INF=(1LL<<60);

int main() {
    int n;
    cin>>n;
    ll a[n],b[n];
    rep(i,n)cin>>a[i];
    rep(i,n)cin>>b[i];
    ll now=0;
    rep(i,n){
        if (a[i]==b[i])continue;
        else if (a[i]<b[i])now+=(b[i]-a[i])/2;
        else{
            now-=a[i]-b[i];
        }
    }
    if (now<0){
        cout<<"No"<<endl;
        return 0;
    }
    cout<<"Yes"<<endl;

    return 0;
}

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

#define rep(X,N) for(ll X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define MODN 1000000007
#define ALL(V) (V).begin(),(V).end()
#define INT_MAX_HALF (INT_MAX / 2)
#define EPS (1e-10)

using namespace std;
typedef long long ll;

class ModInt{
public:
    long long n;
    int p;

    ModInt(){
    }

    //値と割る値を受け取って、オブジェクトを返す
    ModInt(long long _n, int _p){
        p = _p;
        n = _n % _p;

        //負の値を受け取ったときには正の値に戻す
        if(n < 0){
            n += p;
        }
    }

    ModInt operator+(ModInt a){

        ModInt tmp = ModInt(*this);

        tmp.n += a.n;

        if(tmp.n > tmp.p){
            tmp.n -= tmp.p;
        }
        
        return tmp;
    }

    ModInt operator-(ModInt a){

        ModInt tmp = ModInt(*this);

        tmp.n -= a.n;

        if(tmp.n < 0){
            tmp.n += tmp.p;
        }

        return tmp;
    }

    ModInt operator*(ModInt a){

        ModInt tmp = ModInt(*this);

        tmp.n = (tmp.n * a.n) % tmp.p;

        return tmp;
    }

    int modpow(int b, int k){
        if(k == 0){
            return 1;
        }else if(k % 2 == 1){
            long long tmp = b;
            tmp = tmp * modpow(b, k - 1) % p;
            
            return tmp;
        }else{
            long long tmp = modpow(b, k / 2);
            return tmp * tmp % p;
        }
    }

    int modinv(int b){
        return modpow(b, p - 2);
    }

    ModInt operator/(ModInt a){

        ModInt tmp = ModInt(*this);

        tmp.n = tmp.n * modinv(a.n) % tmp.p;
        return tmp;
    }
};

int main(){

    int n;
    cin >> n;

    if(n != 3){

        vector<vector<ModInt>> dp(n, vector<ModInt>(256, ModInt(0, MODN)));

        rep(i, 64){

            if(i != 9 && i != 6 && i != 33){ //"AGC"-> 9 "ACG"-> "GAC"
                dp[2][i] = ModInt(1, MODN);
            }
        }

        for(int i = 2; i < n - 1; i++){
            rep(j, 256){
                int tmp = (j * 4) % 256;

                rep(k, 4){
                    dp[i + 1][tmp + k] = dp[i + 1][tmp + k] + dp[i][j];
                }
            }

            rep(j, 4){
                //*AGC, *ACG, *GAC
                dp[i + 1][64 * j + 9] = ModInt(0, MODN);
                dp[i + 1][64 * j + 6] = ModInt(0, MODN);
                dp[i + 1][64 * j + 33] = ModInt(0, MODN);

                //A*GC, AG*C
                dp[i + 1][16 * j + 9] = ModInt(0, MODN);
                dp[i + 1][4 * j + 33] = ModInt(0, MODN);
            }
        }

        ModInt ans = ModInt(0, MODN);

        rep(i, 256){
            ans = ans + dp[n - 1][i];
        }

        cout << ans.n << endl;

    }else{
        cout << 61 << endl;
    }

    return 0;
}


Measured memory_bytes: 640
#include <iostream>

int main(){
  int N;
  int A[100010];
  std::cin >> N;
  A[0] = 0;
  for(int i=1;i<=N;i++){
    std::cin >> A[i];
  }
  A[N+1] = 0;

  long int sumDist=0;

  for(int i=0; i<=N; i++){
    sumDist += std::abs(A[i] - A[i+1]);
  }

  for(int i=1;i<=N; i++){
    std::cout << sumDist
      - std::abs(A[i-1] - A[i])
      - std::abs(A[i] - A[i+1])
      + std::abs(A[i-1] - A[i+1])
              << std::endl;
  }

  return 0;
}


Measured memory_bytes: 1664
#include <iostream>
#include <string>
#include <sstream>
using namespace std;

string convert(int a, int b, string str) {
    for (int i = 0; i < (int)str.length(); ++i) {
        if (str[i] != ' ')
            str[i] = char((a * (str[i] - 'a') + b) % 26 + 'a');
    }
    return str;
}


int main(void) {
    int n;
    string str;
    cin >> n;
    getline(cin, str);
    for (int i = 0; i < n; ++i) {
        bool flag = false;
        string str;
        getline(cin, str);
        for (int a = 0; a < 26; ++a) {
            for(int b = 0; b < 26; ++b) {
                string str2;
                stringstream ss;
                ss << convert(a, b, str);
                while (!ss.eof()) {
                    ss >> str2;
                    if (str2 == "this" || str2 == "that") {
                        cout << convert(a, b, str) << endl;
                        flag = true;
                        break;
                    }
                }
                if (flag)
                    break;
            }
            if (flag)
                break;
        }
    }
    return 0;
}



Measured memory_bytes: 3108
# -*- coding: utf-8 -*-

N = int(input())
As = list(map(int, input().split()))
b = []
i = len(As) - 1
while i >= 0:
    b.append(As[i])
    i -= 2

i = len(As) % 2
while i<len(As):
    b.append((As[i]))
    i += 2

print(*b)


Measured memory_bytes: 26356
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream> 
#include<map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
using namespace std;
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)
#define LONG_INF 100000000000000
long long counter[200000][2] = {};
int main() {
	long long n, k;
	cin >> n >> k;
	REP(i, n) {
		long long tmp;
		cin >> tmp;
		counter[i + 1][0] = tmp + counter[i][0];
		counter[i + 1][1] = max(counter[i][1], counter[i][1] + tmp);
	}
	long long ans = 0;
	for (int i = 1;i <= 1+n - k;++i) {
		long long pre_ans;
		pre_ans= counter[i-1][1];
		pre_ans += counter[n][1] - counter[i+k-1][1];
		pre_ans += max((long long)0, counter[i + k-1][0] - counter[i - 1][0]);
		ans = max(ans, pre_ans);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define mp make_pair
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong
#define INF llong(1e17)
template<class T> bool chmax(T &a,  T b) {if(a<b){a=b; return 1;} return 0;}
template<class T> bool chmin(T &a,  T b) {if(a>b){a=b; return 1;} return 0;}
void myprint(int* A,int A_num){
   REP(i,A_num) cout << A[i] << " ";
   cout << endl;
}

signed main(){
    int n;
    cin >> n;
    int h[n], a[n + 1],basyo[n+1];
    basyo[0] = 0;
    REP(i,n){
        cin >> h[i];
        basyo[h[i]]  = i + 1;
    }
    REP(i,n) cin >> a[i + 1];

    int dp[n+1];
    dp[0] = 0;
    
    int backet[n+1];
    REP(i,n+1) backet[i] = - INF;
    backet[0] = 0;
    int root_n = 1;
    while(root_n * root_n < n) root_n ++;
    int backet_max[root_n + 2];
    REP(i,root_n + 2) backet_max[i] = - INF;
    backet_max[0] = 0;
    
    FOR(i,1,n+1){
        int ma = - INF;
        int backet_max_id = basyo[i] / root_n;
        REP(j,backet_max_id) chmax(ma,backet_max[j]);
        FOR(j , backet_max_id * root_n , basyo[i]) chmax(ma,backet[j]);
        dp[i] = ma + a[basyo[i]];
        backet[basyo[i]] = dp[i];
        chmax(backet_max[backet_max_id], dp[i]);

    }

    int ans = - INF;
    FOR(i,1,n+1) chmax(ans,dp[i]);
    cout << ans << endl;

}

Measured memory_bytes: 8064
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        while(N-- != 0) {
        	BigInteger b = sc.nextBigInteger().add(sc.nextBigInteger());
        	System.out.println(b.toString().length()>80?"overflow":b.toString());
        }
	}	
}



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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)

int main(){
  int64_t N;
  cin >> N;

  vector<string> S(N);
  for(int64_t i=0; i<N; i++) cin >> S.at(i);

  sort(S.begin(), S.end());

  int64_t ans = 0;
  string last = S.at(0);

  for(int64_t i=1; i<N; i++){
    if(S.at(i)!=last){ans++; last = S.at(i);}
  }

  cout << ans+1;
}

Measured memory_bytes: 9596
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
int a[25252],b[25252],p[25252],q[25252];
int main()
{
	int n;
	cin>>n;
	rep(i,n) cin>>p[i];
	rep(i,n){
		p[i]--;q[p[i]]=i;
	}
	a[0]=1;b[0]=1000000000;
	rep(i,n-1){
		int d=q[i+1]-q[i];
		if(d>0) b[i+1]=b[i]-1,a[i+1]=a[i]+d+1;
		else a[i+1]=a[i]+1,b[i+1]=b[i]-1+d;
	}
	rep(i,n){
		cout<<a[i];
		if(i<n-1) cout<<' ';else cout<<endl;
	}
	rep(i,n){
		cout<<b[i];
		if(i<n-1) cout<<' ';else cout<<endl;
	}
}


Measured memory_bytes: 896
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <numeric>//accumulateを使うためにインクルード

using namespace std;

int main(){
    vector<int> v(3);
    cin >> v[0] >> v[1] >> v[2];
    sort(v.begin(), v.end());
    cout << v[0]+v[1] << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
int mfour=0,mtwo=0,mone=0,n=0;
using namespace std;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int t;
		scanf("%d",&t);
		if(t%4==0)
		{
			mfour++;
		}
		else if(t%2==0)
		{
			mtwo++;
		}
		else
		{
			mone++;
		}
	} 
	if(mfour>=mone)
	{
		printf("Yes");
	}
	else if(mtwo==0&&(mfour+1==mone))
	{
		printf("Yes");
	}
	else
	{
		printf("No");			
	}
	return 0;
}

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


#define li          long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define pb          push_back
#define sz(v)       ((li)(v).size())
#define bgn(v)      ((v).begin())
#define eend(v)     ((v).end())
#define allof(v)    (v).begin(), (v).end()
#define dodp(v,n)       memset(v,(li)n,sizeof(v))
#define bit(n)      (1ll<<(li)(n))
#define mp(a,b)     make_pair(a,b)
#define rin rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)     idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)       idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)        idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)   for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)      idp p2((x).F, (x).S)
#define dump(x,n)   idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)  idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)    idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)   idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)   rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)   rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;

inline bool check(string s) {
    return (s[0] != s[1] && s[1] != s[2] && s[2] != s[3]);
}

int main() {
    string s;
    cin >> s;
    cout << (check(s) ? "Good" : "Bad") << endl;

    return 0;
}

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

int cnt[100007];

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

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

    int ans = 0;
    for (int i = 0; i <= 1e5; i++) {
        ans = max(ans, cnt[i] + cnt[i+1] + cnt[i+2]);
    }

    cout << ans;
}


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

int main(){
  int n;
  cin >> n;
  
  int error_count = 0;
  vector<int> p(n);
  vector<int> ti(2);
  vector<int> tp(2);
  
  for(int i=0; i<n; i++){
    cin >> p.at(i);
    
    if(p.at(i) != (i+1)){
      error_count++;
      if(error_count < 3){
        ti.at(error_count-1) = i+1;
        tp.at(error_count-1) = p.at(i);
      }
      else{
        break;
      }
    }
  }

  
  if(error_count == 0){
    cout << "YES" << endl;
  }
  else if(error_count == 2){
    if(ti.at(0) == tp.at(1) && 
       ti.at(1) == tp.at(0)){
      cout << "YES" << endl;
    }
    else{
      cout << "NO" << endl;
    }
  }
  else{
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

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

    vector<int> a(n);
    rep(i, n) {
        cin >> a[i];
    }

    deque<int> d;
    rep(i, n) {
        int p = lower_bound(d.begin(), d.end(), a[i]) - d.begin();
        if(p == 0) {
            d.push_front(a[i]);
        }
        else {
            d[p-1] = a[i];
        }
    }

    int ans = d.size();

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

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> T;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
int N;
ll L[100100],R[100100];
int main(){
	cin >> N;
	for(int i=0;i<N;i++){
		cin >> L[i] >> R[i];
	}
	sort(L,L+N);
	reverse(L,L+N);
	sort(R,R+N);
	int r = 0;
	ll now = 0ll;
	ll ans = 0ll;
	for(int l=0;l<=N;l++){
		if(l>0)now += 2ll*L[l-1];
		while(r<l-1){
			now += -2ll*R[r];
			r++;
		}
		while(r<l+1&&r<N){
			if(R[r]<0){
				now += -2*R[r];
				r++;
			}else{
				break;
			}
		}
		ans = max(ans,now);
	}
	cout << ans << endl;
	return 0;
}

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

int n;
int a[1000005];
int dp[100005];

int minCost(int i){
   if(i>=n-1)
   return 0;
   
   if(dp[i]!=-1)
   return dp[i];
   
   int ret=0;
   if(i<n-2)
   ret=min(abs(a[i+1]-a[i])+minCost(i+1),abs(a[i+2]-a[i])+minCost(i+2));
   else
   if(i<n-1)
   ret=abs(a[i+1]-a[i])+minCost(i+1);
   return dp[i]=ret;	
}

int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	memset(dp,-1,sizeof(dp));
	cout<<minCost(0)<<endl;
}

Measured memory_bytes: 2560
#include <iostream>
#include <string>
using namespace std;
int main(){
	string in;
	while (cin >> in)
	{
		int a = 0, b = 0;
		for (int i = 0; i < in.length() - 2; i++){
			if (in.substr(i, 3) == "JOI")a++;
			if (in.substr(i, 3) == "IOI")b++;
		}
		cout << a << endl << b << endl;
	}
}

Measured memory_bytes: 1212
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>

#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define bit(n,k) (((ll)n>>(ll)k)&1) /*nのk bit目*/
#define pb push_back
#define eb emplace_back
#define SZ(x) ((ll)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const long long INF= 1e+18+1;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
//const ll MOD=998244353LL;
//const ll MOD=1777777777LL;
//const ll MAX_V=114514LL;
//const ll MAX = 500010LL;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
vl dx={0,0,1,-1};
vl dy={1,-1,0,0};

//素因数分解O(√n)
map<ll,ll>prime_factor(ll n){
  map<ll,ll>res;
  for(ll i=2;i*i<=n;i++){
    while(n%i==0){
      res[i]++;
      n/=i;
    }
  }
  if(n!=1)res[n]=1;
  return res;
}

const ll MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];
//finvが階乗の逆元

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll modpow(ll a, ll n, ll mod) {
  
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}



int main(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  cout << fixed << setprecision(10);
  /*--------------------------------*/
  ll a;cin>>a;
  cout<<a+a*a+a*a*a<<endl;
}

Measured memory_bytes: 3620
#include<iostream>
    #include<stdio.h>
    //#include <bits/stdc++.h>
    #include<vector>
    #include<float.h>
    #include<iomanip>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<math.h>
    #include<cmath>
    #include<sstream>
    #include<set>
    #include<map>
    #include<queue>
    #include<cassert>
    #include<cmath>
    #include<cstdint>
    #include<numeric>
    #include<array>
     
    #define INF 1e9
    #define rep(i,n)for(int i=0;(i)<(int)(n);i++)
    #define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
    #define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
    #define vec(type,n) vector<type>(n)
    #define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
    #define ALL(a)  (a).begin(),(a).end()
    #define chmin(a, b) a = min(a, b)
    #define chmax(a, b) a = max(a, b)
    #define Vl vector<ll>
     
    using namespace std;
    using ll = long long;
    using Graph = vector<vector<ll>>;
    using P = pair<ll, ll>;
     
const ll MOD = 1e9 + 7;
const ll ZER = 0;

int main(){
    vector<int> v(4);
    rep(i, 4)cin >> v[i];
    sort(ALL(v));
    vector<int> w = {1, 4, 7, 9};
    if(v == w)cout << "YES" << endl;
    else cout << "NO" << endl;
}


Measured memory_bytes: 3556
#include <bits/stdc++.h>
using namespace std;
int main() 
{
	int n;
	cin>>n;
	int k;
	cin>>k;
	vector<int> height;
	for(int i=0;i<n;i++)
	{
	    int x;
	    cin>>x;
	    height.push_back(x);
	}
	int dp[n+1]={0};
	dp[1]=abs(height[0]-height[1]);
    for(int i=2;i<n;i++)
    {
        dp[i]=INT_MAX;
        for(int j=1;j<=k && i-j>=0;j++)
        {
            dp[i]=min(dp[i],dp[i-j]+abs(height[i]-height[i-j]));
            
        }
        //cout<<endl;
    }
    //for(int i=0;i<n;i++)
    cout<<dp[n-1]<<endl;
    //cout<<dp[1];
	return 0;
}

Measured memory_bytes: 1144
S=input()
E=[]
O=[]
for i in range(len(S)):
  if i%2==0:
    E.append(int(S[i]))
  else:
    O.append(int(S[i]))
a=E.count(0)
b=E.count(1)
c=O.count(0)
d=O.count(1)
print(min(a+d,b+c))

Measured memory_bytes: 4052
import sys

input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)
ans = []
n = sum(A)
for value in A:
    if value * 4 * M < n:
        break
    else:
        ans.append(value)

if len(ans) >= M:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
n = int(input())
strings_list = [list(input()) for i in range(n)]
counter = 0
dict = {}

for strings in strings_list:
    strings = "".join(sorted(strings))
    if strings in dict.keys():
        counter += dict[strings]
        dict[strings] += 1
    else:
        dict[strings] = 1
print(counter)


Measured memory_bytes: 39040
#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

const int MAX_N = 705;

int sign (int x) {
  return x / abs(x);
}

int conn [MAX_N][MAX_N];
vector<int> adj [MAX_N];

int part [MAX_N];
int swing [MAX_N];
bool fail;
void dfs (int vertex, int color) {
  part[vertex] = color;
  swing[abs(color)] += sign(color);
  
  for (int nxt : adj[vertex]) {
    if (part[nxt] == 0) {
      dfs(nxt, -color);
    } else if (part[nxt] == color) {
      fail = 1;
    }
  }
}

int dp [2 * MAX_N + 1][MAX_N];

int& dpAt (int i, int j) {
  return dp[i + MAX_N][j];
}

int edges (int x) {
  return x * (x - 1) / 2;
}

int main () {
  int vertexc, edgec;
  cin >> vertexc >> edgec;

  for (int i = 0; i < edgec; i++) {
    int u, v;
    cin >> u >> v;

    conn[u][v] = 1;
    conn[v][u] = 1;
  }

  for (int i = 1; i <= vertexc; i++) {
    for (int j = i + 1; j <= vertexc; j++) {
      if (conn[i][j] == 0) {
        adj[i].push_back(j);
        adj[j].push_back(i);
      }
    }
  }

  int curPart = 1;
  for (int i = 1; i <= vertexc; i++) {
    if (part[i] == 0) {
      dfs(i, curPart);
      curPart++;
    }
  }

  if (fail) {
    cout << -1 << endl;
    return 0;
  }

  dpAt(0, 0) = 1;
  for (int i = 1; i < curPart; i++) {
    for (int j = -MAX_N; j < MAX_N; j++) {
      if (dpAt(j, i - 1)) {
        dpAt(j + swing[i], i) = 1;
        dpAt(j - swing[i], i) = 1;
      }
    }
  }

  int finalSwing = MAX_N + 5;
  for (int i = -MAX_N; i < MAX_N; i++) {
    if (dpAt(i, curPart - 1)) {
      finalSwing = min(finalSwing, abs(i));
    }
  }

  int parta = (vertexc - finalSwing) / 2;
  int partb = (vertexc + finalSwing) / 2;

  cout << edges(parta) + edges(partb) << endl;
}


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

int main() {
	int N = 0;
	int sum = 0;
	cin >> N;
	string s = to_string(N);
	for (int i = 0; i < s.length(); i++) {
		sum = sum + (s[i] - '0');
	}
	if (N % sum == 0) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

}

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

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll; typedef pair<ll, ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename A,size_t N,typename T>void Fill(A(&array)[N],const T &val){fill((T*)array, (T*)(array+N), val);}
const int inf = INT_MAX / 2; const ll INF = LLONG_MAX / 2;
//template end



int main(){
    int n; scanf("%d",&n);
    vector<int> a; set<int> used;
    rep(i,0,n){
        int p;scanf("%d",&p);
        bool f=p>0; p=abs(p);
        if((f&&used.count(p))||(!f&&(a.empty()||a.back()!=p))){
            printf("%d\n",i+1); return 0;
        }
        if(f){
            a.push_back(p); used.insert(p);
        }
        else{
            a.pop_back(); used.erase(p);
        }
    }
    printf("OK\n");
    return 0;
}


Measured memory_bytes: 3304
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stdio.h>
using namespace std;
#define ll long long int

void ans ( bool ok ) {
  if ( ok == true ) cout << "Yes" << endl;
  else cout << "No" << endl;  
}

int main() {
  int n;
  cin >> n;
  vector < string > w(n);
  for ( int i = 0; i < n; ++i ) {
    cin >> w[i];  
  }
  bool ok = true;
  for ( int i = 0; i < n; ++ i ) {
    if ( i == 0 ) continue;
    int n = w[i - 1].length();
    if ( w[i - 1][n - 1] != w[i][0] ) ok = false;
    //cout << "お尻の文字は" << w[i - 1][n - 1] << endl;
    //cout << "頭の文字は" << w[i][0] << endl;
  }
  //cout << ok << endl;
  for ( int i = 0; i < n; ++i ) {
    for ( int j = 0; j < n; ++j ) {
      if ( i == j ) continue;
      if( w[i] == w[j] ) 
      {
        ok = false;  
        //cout << "w[" << i << "] = " << w[i] << endl;
        //cout << "w[" << j << "] = " << w[j] << endl;
      }
    } 
  }
  ans( ok );
  return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_map>
#include <map>
#define rep(i, a) for (int i = 0; i < (a); i++)
using namespace std;

int main(){
    long long int l, k;
    long long int x, y, z;
    vector<long long int> a, b, c, d, e;
    
    cin >> x >> y >> z >> k;
    
    long long int i, j;
    
    for(i = 0; i < x; i++){
        cin >> l;
        a.push_back(l);
    }
    
    for(i = 0; i < y; i++){
        cin >> l;
        b.push_back(l);
    }
    
    for(i = 0; i < z; i++){
        cin >> l;
        c.push_back(l);
    }
    
    sort(a.begin(), a.end(), greater<long long int>());
    sort(b.begin(), b.end(), greater<long long int>());
    sort(c.begin(), c.end(), greater<long long int>());
    
    for(i = 0; i < x; i++){
        for(j = 0; j < y; j++){
            d.push_back(a[i] + b[j]);
        }
    }
    sort(d.begin(), d.end(), greater<long long int>());
    
    if(x*y < k){
        for(i = 0; i < z; i++){
            for(j = 0; j < x*y; j++){
                e.push_back(d[j] + c[i]);
            }
        }
    }else{
        for(i = 0; i < z; i++){
            for(j = 0; j < k; j++){
                e.push_back(d[j] + c[i]);
            }
        }
    }
    
    sort(e.begin(), e.end(), greater<long long int>());
    
    for(i = 0; i < k; i++){
        cout << e[i] << endl;
    }
}



Measured memory_bytes: 43128
#include <bits/stdc++.h>
using namespace std;
int main(void){
    
    long long n;
    long long a[200009]={};
    long long s=0;
    long long m=0;
    long long ans=9999999999;
    
    cin >> n;
    
    for(int i=1; i<=n; i++){
        
        cin >> a[i];
        s += a[i];
        
    }
    
    for(int i=1; i<=n-1; i++){
        
        m += a[i];
        ans = min(ans, abs(s-m*2));
        
    }
    
    cout << ans << endl;
    
    return 0;
    
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
typedef long long ll;
//****************************************
// Graph template
//****************************************

// status of edge
template <typename X>
struct Edge{
  int from;
  int to;
  X cost;

  Edge() = default;

  Edge(int from, int to, X cost) : from(from), to(to), cost(cost) {}
};

// status of node
template <typename X>
struct Node{ 
  int idx;
  vector<Edge<X>> edge;
  int a;
  X b;
  
  Node() = default;

  explicit Node(int idx) : idx(idx) {}
};

template <typename X>
class Graph{
private:
  int n; // number of node
  int m; // number of edge
  vector<Node<X>> node; 
  X x;
  bool f, flag;
  
  void Init_Node() {
    rep(i,n) node.emplace_back(i);
  }
public:
  explicit Graph(int n) : n(n) {
    Init_Node();
  }

  // edges have no-weight 
  Graph(int n, int m, vector<int> from, vector<int> to) : n(n), m(m) {
    Init_Node();
    rep(i,m) {
      add_edge(from[i], to[i]);
      add_edge(to[i], from[i]);      
    }
  }  

  // edges have weight
  Graph(int n, int m, vector<int> from, vector<int> to, vector<X> cost) : n(n), m(m) {
    Init_Node();
    rep(i,m) {
      add_edge(from[i], to[i], cost[i]);
      add_edge(to[i], from[i], cost[i]);      
    }
  }

  void add_edge(int from, int to, X cost = 1) {
    node[from].edge.emplace_back(from, to, cost);
  }

  void DFS(int v, int na, X nb) {
    node[v].a = na;
    node[v].b = nb;
    for(auto next: node[v].edge) {
      int w = next.to;
      X c = next.cost;
      if(node[w].a == 0) DFS(w, -na, c - nb);
      else if(node[w].a == na) {
	if((c - node[v].b - node[w].b) % 2 == 1) f = false;
	else {
	  if(na == 1) {
	    X y = (c - node[v].b - node[w].b) / 2;
	    if(flag && x != y) f = false;
	    else x = y;
	  }
	  else {
	    X y = -(c - node[v].b - node[w].b) / 2;
	    if(flag && x != y) f = false;
	    else x = y;
	  }
	}
	flag = true;
      }
      else {
	if(node[v].b + node[w].b != c) f = false;
      }
    }
  }

  void Solve() {
    rep(i,n) node[i].a = 0;
    f = true;
    flag = false;
    DFS(0, 1, 0);
    //    rep(i,n) cout << i << ":" << node[i].a << ":" << node[i].b << "\n";
    if(f) {
      ll pmin = 2e+9+10, mmin = 2e+9+10;
      rep(i,n) {
	if(node[i].a == 1) chmin(pmin, (ll)node[i].b);
	else chmin(mmin, (ll)node[i].b);
      }
      //      cout << pmin << ":" << mmin << "\n";
      if(flag) {
	if(max((ll)1, 1 - pmin) <= x && x <= mmin - 1) cout << 1 << "\n";
	else cout << 0 << "\n";
      }
      else {
	int res = max((ll)0, mmin - max((ll)1, 1 - pmin));
	cout << res << "\n";
      }
    }
    else {
      cout << 0 << "\n";
    }
  }
  
};


int main()
{
  int n,m; cin >> n >> m;
  vector<int> u(m), v(m);
  vector<ll> s(m);
  rep(i,m) {
    cin >> u[i] >> v[i] >> s[i];
    u[i]--; v[i]--;
  }

  Graph<ll> gp(n, m, u, v, s);
  gp.Solve();
  return 0;
}


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

int num_digits(long long x)
{
    int c = 0;
    while(x > 0)
    {
        c++;
        x /= 10;
    }
    return c;
}

int main(int argc, char *argv[])
{
    long long n;
    cin >> n;

    int min_f = 100000000;
    for(long long i = 1; i * i <= n; ++i)
    {
        if(n % i != 0)
        {
            continue;
        }

        long long a = i;
        long long b = n / i;

        int f = max(num_digits(a), num_digits(b));

        min_f = min(f, min_f);
    }

    cout << min_f << endl;
}


Measured memory_bytes: 256
import java.util.*;
import java.math.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int a = sc.nextInt();
    int b = sc.nextInt();
    String[] s = sc.next().split("");
    
    int clear = 0;
    int gclear = 0;
    
    for(int i = 0;i < n;i++){
      if(s[i].equals("a") && clear < a+b){
        System.out.println("Yes");
        clear++;
      }else if(s[i].equals("b") && clear < a+b & ++gclear <= b){
        System.out.println("Yes");
        clear++;
      }else{
        System.out.println("No");
      }
      
      
    }
    
    
    
  }
}

Measured memory_bytes: 61816
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;
import java.util.Random;
import java.util.Scanner;
 


public class Main {
	private static Scanner sc = new Scanner(System.in);
	//result = Math.pow(num1, num3)
	//StringBuffer str = new StringBuffer(hoge1);
	//String hoge2 = str.reverse().toString();
	//map.containsKey(A)

	//Map<String, Integer> map = new HashMap<String, Integer>(n);
	/*for ( キーのデータ型 key : マップの名前.keySet() ) {
		データのデータ型 data = マップの名前.get( key );
		
		// keyやdataを使った処理;
	}*/
	//int i = Integer.parseInt(s);
	//Queue<String> qq=new ArrayDeque<>(); //add,poll,peek
	//Deque<String> qq=new ArrayDeque<>();//push,pop,peek
	//ArrayList<String> cc = new ArrayList<>(n);
	//Collections.sort(list);
	//Array.sort(list);   cc.contains(tmp)
	//Arrays.asList(c).contains("a")
	//list.set(1,"walk");//1 1 2 3 5
	static long mod =1000000007;
	//static 	ArrayList<Integer> cc = new ArrayList<>(100);
	
	
	public static void main(String[] args) {
		//int N=sc.nextInt();for(int i=0;i<N;i++) {}
		//int a[]=new int[N];
		//Ae2+Be2=Ce2
		//StringBuffer str = new StringBuffer(hoge1);
		//for(int i=0;i<N;i++) {}
		
		//int N=sc.nextInt();for(int i=0;i<N;i++) {}
		int N=sc.nextInt();
		int M=sc.nextInt();
		
		
		
		for(int i=0;i<M;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			
			if(!map.containsKey(a)) {
				map.put(a, new ArrayList<Integer>());
			}
			if(!map.containsKey(b)) {
				map.put(b, new ArrayList<Integer>());
			}
			map.get(a).add(b);
			map.get(b).add(a);
		}
		
		
		int v[]=new int[N];
		Queue<Integer> qq=new ArrayDeque<>(); 
		
		qq.add(1);
		while(qq.peek()!=null) {
			int t=qq.poll();
			ArrayList<Integer> cc=map.get(t);
			for(int i:cc) {
				if(v[i-1]==0) {
					v[i-1]=t;
					qq.add(i);
					
				}
			}
		}
		p("Yes");
		for(int i=1;i<N;i++) {
				p(v[i]);
		}
		
		
	}
	public static Map<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>(20001);	
		
	//static int ans=10000009;
	
		
	
	
	
	public static long lcm(long a, long b) {
        return a / gcd(a, b) * b;
	}
	
	public static long gcd(long a, long b) {
        return b == 0 ? a: gcd(b, a % b);
	}

	


	
	static void p(String ans) {System.out.println(ans);};
	static void p(int ans) {System.out.println(ans);};
	static void p() {System.out.println();};
	static void p(long ans) {System.out.println(ans);};
	static void p(double ans) {System.out.println(ans);};
	
}
	


Measured memory_bytes: 88524
program main
  implicit none
  integer(8) :: n, i, res
  read *, n
  res = 0
  do i = 1, n
    if (mod(i, 3) == 0) cycle
    if (mod(i, 5) == 0) cycle
    res = res + i
  end do
  print "(i0)", res
end program main


Measured memory_bytes: 2876
#include <bits/stdc++.h>
#define int long long
#define ALL(v) (v).begin(),(v).end()
#define Vi vector<int>
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repeq(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define repreq(i,a,b) for(int i=a;i>=b;i++)
#define leng(n) (int)(log10(n)+1)
#define INF 9000000000000000000
#define MOD 1000000007
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm


signed main(){
  int n,m;
  cin >> n >> m;
  int one = 0;
  one += (n-m)*100;
  one += m*1900;
  
  rep(i,0,m) one *= 2;
  
  cout << one << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        
		                
        if((A+B)%2==0){
        	System.out.println((A+B)/2);
        }else {
        	System.out.println("IMPOSSIBLE");
        }
			
			

	}

}


Measured memory_bytes: 21844
n,m=map(int,input().split())

x=list(map(int,input().split()))
y=list(map(int,input().split()))

X=[]
for i in range(1,len(x)):
    X.append(x[i]-x[i-1])
    
Y=[]
for j in range(1,len(y)):
    Y.append(y[j]-y[j-1])

A=len(X)
for a in range(int((len(X)+1)/2)):
    X[a]*=A
    if X[a]==X[len(X)-1-a]:
        pass
    else:
        X[len(X)-1-a]*=A
    A=A+len(X)-2*(a+1)
    
SX=sum(X)

B=len(Y)
for b in range(int((len(Y)+1)/2)):
    Y[b]*=B
    if Y[b]==Y[len(Y)-1-b]:
        pass
    else:
        Y[len(Y)-1-b]*=B
    B=B+len(Y)-2*(b+1)
    
SY=sum(Y)

print((SX*SY)%(10**9+7))

Measured memory_bytes: 20348
s = ""
dat = []
n = int(input())
for _ in range(n):
    dat.append(input())
for i in range(26):
    tch = chr(ord("a") + i)
    num = 99999
    for j in range(len(dat)):
        num = min(num, dat[j].count(tch))
    s += tch * num
print(s)


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

map<ll, int> prime_factor(ll n) {
    map<ll, int> ret;
    for (ll i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1)
        ret[n] = 1;
    return ret;
}

int main() {
    ll n, P;
    cin >> n >> P;

    map<ll, int> mp = prime_factor(P);

    ll ans = 1;
    for (auto &p : mp) {
        rep(i, p.second / n)
            ans *= p.first;
    }
    cout << ans << endl;

    return 0;
}

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

Measured memory_bytes: 572
#include<stdio.h>

int f[50];

int fib(int n){
  if(n == 0 || n == 1) return f[n] = 1;
  if(f[n] != -1) return f[n];
  return f[n] = fib(n - 1) + fib(n - 2);
}

int main(){
  int n, i;
  for(i = 0; i < 50; i++) f[i] = -1;

  scanf("%d",&n);
  printf("%d\n",fib(n));

  return 0;
}

Measured memory_bytes: 596
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
//#define int long long
int N, M;
vector<vector<int> > to;
vector<int> used;
void aa(vector<int> &path) {
	int c = 0;
	bool f;
	while (true) {
		f = true;
		
		for (auto x : to[c]) {
		
			if (used[x] == 0) {
				used[x] = 1;
				path.push_back(x);
				c = x;
				f = false;
				break;
			}
		}
		if (f) {
			break;
		}
	}
}
signed main() {
	
	
	cin >> N >> M;
	to.resize(N);
	used.resize(N, 0);
	int a, b;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		a--;
		b--;
		to[a].push_back(b);
		to[b].push_back(a);
		
	}
	used[0] = 1;
	vector<int> path1; 
	vector<int> path2;
	aa(path1);
	aa(path2);
	cout << ((int)path1.size() + 1 + (int)path2.size() )<< endl;
	for (int i = (int)path1.size() - 1; i >= 0; i--) {
	
		if (i != (int)path1.size() - 1) {
			cout << " ";
		}
		cout << (path1[i] + 1);
	}
	cout <<" 1";
	for (int i = 0; i < (int)path2.size(); i++) {
		
			cout << " ";
		
		cout << (path2[i] + 1);
	}
	return 0;
}

Measured memory_bytes: 7160
//10^7 in 1.5 s


#include<bits/stdc++.h>

using namespace std;

#define ll long long

vector<ll> ans;

void seive(ll int n)
{
    vector <bool> fahad(n+1,true);

    fahad[0]=fahad[1]=false;

    for(ll int i=4;i<=n;i+=2)
        fahad[i]=false;

    ll int s = sqrt(n)+1;

    for(ll int i=3;i<=s;i+=2)
    {
        if(fahad[i]==true)
        {
            for(ll int j=i*i;j<=n;j+=i)
            {
                fahad[j]=false;
            }
        }

    }

    ans.push_back(2);

    for(ll int i=3;i<=n;i+=2)
    {
        if(fahad[i]==true)
            ans.push_back(i);
    }

}

int main(void)
{
    seive(1000000);

    ll int n;
    cin >> n;


    ll to=0;

    for(int i=0;i<ans.size();i++)
    {
        if(ans[i]>=n)
        {
            to = ans[i];
            break;
        }
    }
    cout << to << endl;

    return 0;
}


Measured memory_bytes: 1528
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;
const double pi = 3.14159265358979323846;
#define rep(i,n) for(ll i=0;i<n;i++)

int main(){
	int n;cin>>n;
	int d[n];
	map<int,ll> mp;//長さごとに数える
	rep(i,n){
		cin>>d[i];
		mp[d[i]]++;
	}

	if(d[0]!=0||mp[0]>1||(mp[0]>0&&d[0]!=0)){
		cout<<0<<"\n";
		return 0;
	}
	ll ans=1,mod=998244353;
	for(int i=1;i<n;i++){
		ans=(ans*mp[d[i]-1])%mod;//iに隣接して1に最も近いものの種類をかけていけば解になる
	}
	cout<<ans<<"\n";

}

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

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

    int x, y, a, b, c;
    static int p[100000], q[100000], r[100000];
    cin >> x >> y >> a >> b >> c;
    for(int i=0;i<a;++i) cin >> p[i];
    for(int i=0;i<b;++i) cin >> q[i];
    for(int i=0;i<c;++i) cin >> r[i];
    sort(p, p+a, greater<int>());
    sort(q, q+b, greater<int>());
    sort(r, r+c, greater<int>());

    vector<int64_t> cand, csum, rsum;
    cand.reserve(x+y);
    csum.reserve(x+y+1);
    rsum.reserve(c+1);
    for(int i=0;i<x;++i) cand.push_back(p[i]);
    for(int i=0;i<y;++i) cand.push_back(q[i]);
    sort(cand.begin(), cand.end(), greater<int>());
    csum.push_back(0);
    for(int ca: cand) csum.emplace_back(csum.back() + ca);
    rsum.push_back(0);
    for(int i=0;i<c;++i) rsum.emplace_back(rsum.back() + r[i]);

    int64_t ans = 0;
    for(int i=0;i<=min(c, x+y);++i){
        ans = max(ans, csum[x+y-i]+rsum[i]);
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;

#define INF (INT_MAX/2-1)
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

struct UF{
  vector<int>rank,pars;
  UF(int n){
    rank.resize(n,0);
    pars.resize(n);
    for(int i=0;i<n;i++)pars[i]=i;
  }
  int root(int x){
    if(pars[x]==x)return x;
    else return pars[x]=root(pars[x]);
  }
  bool same(int x,int y){
    return root(x)==root(y);
  }
  void unite(int x,int y){
    x=root(x);
    y=root(y);
    if(x==y)return;
    if(rank[x]>rank[y]){
      pars[y]=x;
    }
    else{
      pars[x]=y;
      if(pars[x]==pars[y])rank[x]++;
    }
  }
};

int main(){
  int N,M;
  cin>>N>>M;
  UF uf(N+M);
  for(int i=0;i<N;i++){
    int k;
    cin>>k;
    for(int j=0;j<k;j++){
      int l;
      cin>>l;
      uf.unite(i,l+N-1);
    }
  }
  bool ok=true;
  for(int i=0;i<N;i++){
    if(!uf.same(i,1))ok=false;
  }
  if(ok)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  return 0;
}



Measured memory_bytes: 1792
using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static int Main(string[] args) {
        List<int> list = new List<int>();

        while (true) {
            string v = Console.ReadLine();
            if (v == "0") { break; }

            int total = 0;
            for (int i = 0; i < v.Length; i++) {
                total += int.Parse(v.Substring(i, 1));
            }

            list.Add(total);
        }

        for (int i = 0; i < list.Count; i++) {
            Console.WriteLine(list[i]);
        }

        return 0;
    }
}


Measured memory_bytes: 15956
import math
a = list(map(int,input().split()))

m = 0
h = a[0]
w = a[1]

'''
for hi in range(h):
    for wi in range(w):
        if (hi+1 + wi+1) % 2 == 0:
            m += 1
'''
if h == 1 or w == 1:
    print(1)
else:
    m = math.ceil(w/2) * math.ceil(h/2) + math.floor(w/2) * math.floor(h/2)
    print(m)



Measured memory_bytes: 3060
# -*- coding: utf-8 -*-
"""
D - 756
https://atcoder.jp/contests/abc114/tasks/abc114_d

"""
import sys


from collections import Counter

def prime_factor(N):
    factors = Counter()
    for i in range(2, int(N**0.5)+1):
        while N % i == 0:
            factors[i] += 1
            N //= i
    if N != 1:
        factors[N] = 1
    return factors


def solve(n):
    d = Counter()
    for i in range(2, n+1):
        x = prime_factor(i)
        d += x
    t3 = [v for k, v in d.items() if v >= 2]
    t5 = [v for k, v in d.items() if v >= 4]
    t15 = [v for k, v in d.items() if v >= 14]
    t25 = [v for k, v in d.items() if v >= 24]
    t75 = [v for k, v in d.items() if v >= 74]
    ans = len(t75) + len(t25)*(len(t3)-1) + len(t15)*(len(t5)-1)+len(t5)*(len(t5)-1)*(len(t3)-2) // 2
    return ans


def main(args):
    n = int(input())
    ans = solve(n)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


Measured memory_bytes: 3564
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] A = new int[n];
		for(int i = 0; i < n; i++) {
			A[i] = sc.nextInt();
		}
		part(A, 0, A.length - 1);
	}

	public static void part(int[] A, int p, int r) {
		int x = A[r]; //基準値
		int i = p - 1;
		for(int j = p; j < r; j++) {
			if(A[j] <= x) {
				i++;
				int tmp = A[i];
				A[i] = A[j];
				A[j] = tmp;
			}
		}
		int temp = A[i + 1];
		A[i + 1] = A[r];
		A[r] = temp;
		
		for(int y = 0; y <= r; y++) {
			if(A[y] == x && y == r) {
				System.out.print("[" + A[y] + "]\n");
			}else if(y == i + 1){
				System.out.print("[" + x + "] ");
			}else if(y == r) {
				System.out.print(A[y] + "\n");
			}else {
				System.out.print(A[y] + " ");
			}
		}
	}
}




Measured memory_bytes: 69100
N, T = map(int, input().split())
ct = []
maniau = []
for i in range(N):
    c, t = map(int, input().split())
    if t <= T:
        maniau.append(c)
        
if len(maniau) == 0:
    print('TLE')
else:
    print(min(maniau))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long

#define _CRT_SECURE_NO_DEPRECATE
const int N = 33003;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
const ll mod =  1e9+7;
using namespace std;

int main(){
double a,b,h;
cin>>a>>b>>h;
double ans=0.0;
ans=((a+b)*h)/2;
cout<<setprecision(10)<<ans;
}

Measured memory_bytes: 256
#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<ll,ll>;
//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define inf 2147483647 //int値の最大値
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define CST(x) cout<<fixed<<setprecision(x)//小数点以下の桁数指定
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int gcd(int a, int b) {
    if (b==0) return a;
    else return gcd(b, a%b);
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
int two(int n){
	ll ans=1;
	rep(i,n){
		ans*=2;
	}
	return ans;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

    int n,x;
    cin>>n>>x;
    vector<int> m(n);

    rep(i,n)cin>>m.at(i);

    int min =m.at(0);
    int sum =0;

    rep(i,n){
        if(min>m.at(i))min =m.at(i);

        sum +=m.at(i);
    }
    int cnt=(x-sum)/min;

    cout<<cnt +m.size()<<endl;
    
  


}

Measured memory_bytes: 3636