akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>

typedef struct{
  int left;
  int right;
  int parent;
}node;

int main(){
  node T[100000];
  int d,n,i,j,k,id,num,c,cnt,p;

  scanf("%d",&n);
 for(i=0;i<n;i++){
   T[i].right = T[i].left = T[i].parent = -1;
 }
  for(i=0;i<n;i++){
    scanf("%d%d",&id,&k);
    
    for(j=0;j<k;j++){
      scanf("%d",&c);
      T[c].parent = id;
      if(j == 0) T[id].left = c;
      else T[p].right = c;
      p = c;
    }
  }
  for(i=0;i<n;i++){
    cnt = 0;
    p = T[i].parent;
    // printf("%d\n",p);
    while(p != -1){
      p = T[p].parent;
  cnt++;
    }
    
      printf("node %d: parent = %d, depth = %d, ",i,T[i].parent,cnt);

      if(T[i].parent == -1)printf("root, [");
      else if(T[i].left == -1)printf("leaf, [");
      else printf("internal node, [");

      p = T[i].left;
      if(p != -1){
	printf("%d",p);
	while(T[p].right != -1){
	  printf(", %d",T[p].right);
	  p = T[p].right;
	}
      }
      
      printf("]\n");
    
  }
    return 0;
  }



/*
根付き木

与えられた根付き木 T
の各節点 u

について、以下の情報を出力するプログラムを作成してください。

    u

の節点番号
u
の親の節点番号
u
の深さ
u
の節点の種類（根、内部節点または葉）
u

    の子のリスト

ここでは、与えられる木は n
個の節点を持ち、それぞれ 0 から n−1

の番号が割り当てられているものとします。
入力

入力の最初の行に、節点の個数 n
が与えられます。続く n

行目に、各節点の情報が次の形式で１行に与えられます。

id
k c1 c2 ... ck

id
は節点の番号、k は次数を表します。c1 c2 ...ck は 1 番目の子の節点番号、... k

番目の子の節点番号を示します。
出力

次の形式で節点の情報を出力してください。節点の情報はその番号が小さい順に出力してください。

node id
: parent = p, depth = d, type, [c1...ck

]

p
は親の番号を示します。ただし、親を持たない場合は -1 とします。d

は節点の深さを示します。

type

は根、内部節点、葉をそれぞれあらわす root、internal node、leaf の文字列のいずれかです。ただし、根が葉や内部節点の条件に該当する場合は root とします。

c1
...ck

は子のリストです。順序木とみなし入力された順に出力してください。カンマ空白区切りに注意してください。出力例にて出力形式を確認してください。
制約

    1≤n≤100,000

節点の深さは 20 を超えない。
任意の２つの節点間には必ず経路が存在する。
*/



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

// ??????: http://tubo28.me/algorithm/union-find/
struct UnionFind {
    vector<int> parent;
    int set_num;

    UnionFind(int n) {
        parent.resize(n, -1);
        set_num = n;
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);

        if (x != y) {
            // ????´???°????°?????????????
            // big < small
            if (size(x) < size(y)) swap(x, y);
            parent[x] += parent[y];
            parent[y] = x;
            set_num--;
        }
    }

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

    int find(int x) {
        if (parent[x] < 0) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    int size(int x) {
        return -parent[find(x)];
    }

    int size() {
        return set_num;
    }
};

int main() {
    int n, q;
    cin >> n >> q;
    UnionFind uf(n);

    for (int i = 0; i < q; i++) {
        int com, x, y;
        cin >> com >> x >> y;
        if (com == 0) {
            uf.unite(x, y);
        } else {
            cout << (uf.is_same(x, y) ? 1 : 0) << endl;
        }
    }
    return 0;
}

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

using namespace std;
typedef long long ll;

const int MN = 220;
const ll MD = 1e9+7;

int n;
string s[MN];
ll dp[MN][MN];

ll solve(int i, int j) {
    if (i == 0) {
        if (j == 0) return 1;
        return 0;
    }
    if (dp[i][j] != -1) return dp[i][j];
    ll &res = dp[i][j];
    if (s[i] == "-") {
        res = solve(i-1, j);
    } else if (s[i] == "U") {
        res = (solve(i-1, j-1)+j*solve(i-1, j)) % MD;
    } else {
        res = ((j+1)*(j+1)*solve(i-1, j+1) + j*solve(i-1, j)) % MD;
    }
    return res;
}

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

Measured memory_bytes: 1604
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
const int N = 1e5 + 10 , M = 5e5+10 ,  MOD = 1e9+7;
const int OO = 0x3f3f3f3f;
const double EPS = 1e-3;
 
#define clr(arr,val) memset(arr , val , sizeof (arr))
#define loop(i,n) for(int i = 0;i < int(n);i++)
#define rloop(i,n) for(int i = int(n)-1;i >= 0;i--)
#define range(i,a,b) for(int i = int(a);i <= int(b);i++)
#define ALL(v) ((v).begin()) , ((v).end())
#define SZ(v)  ((int)((v).size()))
typedef pair <int,int> pii ;
typedef vector < pii > vii ;
typedef vector < int > vi;
int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
//int dx[6]={2,1,-1,-2,-1,1};int dy[6]={0,1,1,0,-1,-1}; //Hexagonal Direction
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
 




int n;



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

    

    cin >> n;
    vector < int > a(n);

    int sum = 0;
    for(auto &x : a){
        cin >> x;
        sum += x;
    }
    int  mn = sum , now = 0;
    loop(i , n){
        now += a[i];
        mn = min(mn , abs(now - abs(sum-now)));
        
    }

    cout << mn << "\n";
    

    
 
    
    return 0;
}


Measured memory_bytes: 256
t=int(input())
for k in range(t):
    n,k=map(int,input().split())
    house=list(map(int,input().split()))
    div=[]
    for i in range(n-1):
        div.append(house[i+1]-house[i])
    div.sort()
    answer=sum(div[:n-k])
    if(n>k):
        print(answer)
    else:
        print(0)


Measured memory_bytes: 21296
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define int ll
#define double long double
#define YES {cout<<"YES"<<'\n';}
#define NO {cout<<"NO"<<'\n';}
#define Yes {cout<<"Yes"<<'\n';}
#define No {cout<<"No"<<'\n';}
#define yes {cout<<"yes"<<'\n';}
#define no {cout<<"no"<<'\n';}
void YN(bool flg){cout<<(flg?"YES":"NO")<<'\n';}
void Yn(bool flg){cout<<(flg?"Yes":"No")<<'\n';}
void yn(bool flg){cout<<(flg?"yes":"no")<<'\n';}
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
#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 out(n) {cout << n << '\n';}
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<VI> VVI;
const int MOD = 1000000007;
const long long INF = 10e10;
const double PI = acos(-1.0);
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
int ABS(int a) {if(a<0) a = -a; return a;}
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>U COUNT(const T& a, const U& v) { return count(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }
int POW(int a, int n) { int r = 1; while (n > 0) { if (n & 1)r *= a; a *= a; n /= 2; }return r; }
int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*素因数分解*/map< int, int >prime_factor(int n){map< int, int > ret;for(int i = 2; i * i <= n; i++) {while(n % i == 0) {ret[i]++;n /= i;}}if(n != 1) ret[n] = 1;return ret;}
/*約数の個数*/int divisor_number(int n){auto p = prime_factor(n); int res = 1; for(auto x:p)res*=(x.second+1); return res;}
/*約数列挙*/vector<int> divisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------ライブラリとか----------------



signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(15);

    int a,b,c; cin >> a >> b >> c;
    out(min(a*b,c));

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define maxn 100050
#define LL long long 
using namespace std;
LL a[maxn];
LL sum[maxn];
int main(){
//	freopen("input.txt","r",stdin);
	int n;
	scanf("%d",&n);
	LL cnt1=0,cnt2=0;
	memset(sum,0,sizeof(sum));
	for(int i=0;i<n;i++){
		scanf("%lld",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	LL lazy1=0,lazy2=0;
	for(int i=0;i<n;i++)
	{
		LL sum1=sum[i];
		sum1+=lazy1;
		if(i%2==0&&sum1<=0){
			lazy1+=1-sum1;
			cnt1+=1-sum1;
		}
		if(i%2==1&&sum1>=0){
			lazy1-=1+sum1;
			cnt1+=sum1+1;
		}
	}
	for(int i=0;i<n;i++)
	{
		LL sum2=sum[i];
		sum2+=lazy2;
		if(i%2==0&&sum2>=0){
			lazy2-=1+sum2;
			cnt2+=sum2+1;
		}
		if(i%2==1&&sum2<=0){
			lazy2+=1-sum2;
			cnt2+=1-sum2;
		}
	}
	printf("%lld\n",min(cnt1,cnt2));
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>

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

	std::vector<int> vec(n);
	for (auto&& e : vec)
		std::cin >> e;

	std::sort(vec.begin(), vec.end());

	int sum = std::accumulate(vec.begin(), vec.end(), 0);
	if (sum % 10 != 0) {
		std::cout << sum << std::endl;
		return 0;
	}

	for (auto&& e : vec) {
		if (e % 10 != 0) {
			std::cout << sum - e << std::endl;
			return 0;
		}
	}

	std::cout << 0 << std::endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define re register
#define ull unsigned ll
using namespace std;
inline ll read(){
	ll s=0,t=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*t;
}
const int N=2005;
const int P=1e9+7;
int n,m,Num1,Num2,Ans,rk[N],f[N],sz[N];
ll Lim,Minn,c[N];
struct edge{int x,y,v;}p[N];
bool cmp(int x,int y){return p[x].v<p[y].v;}
int Pow(int k){
	int res=1,x=2;
	while(k){
		if(k&1)res=1ll*res*x%P;
		x=1ll*x*x%P,k>>=1;
	}return res;
}
int Get(int x){return f[x]==x?x:f[x]=Get(f[x]);}
int Merge(int k){
	int x=Get(p[k].x),y=Get(p[k].y);
	if(x==y)return 0;
	if(sz[x]<sz[y])swap(x,y);
	return f[y]=x,sz[x]+=sz[y],p[k].v;
}
ll Calc(int k){
	for(int i=1;i<=n;i++)f[i]=i,sz[i]=1;
	ll res=Merge(k);
	for(int i=1;i<=m;i++)if(rk[i]^k)res+=Merge(rk[i]);
	return res;
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read(),m=read(),Lim=read();
	for(int i=1;i<=m;i++)rk[i]=i,p[i]=(edge){read(),read(),read()};
	sort(rk+1,rk+m+1,cmp),Minn=Calc(0);
	for(int i=1;i<=m;i++)c[i]=Calc(i),Num1+=(c[i]<Lim),Num2+=(c[i]==Lim);
	if(Minn>Lim)Ans=0;
	else if(Minn==Lim){
		Ans=1ll*(Pow(n-1)-2)*Pow(m-n+1)%P;
		Ans=(Ans+2ll*(Pow(Num2-n+1)-1)%P*Pow(m-Num2)%P)%P;
	}
	else Ans=2ll*(Pow(Num2)-1)%P*Pow(m-Num1-Num2)%P;
	printf("%d",Ans);
	return 0;
}

Measured memory_bytes: 3824
def add_mult(i, count, N, K):
    if count > N:
        return i
    am1 = add_mult(i*2, count + 1, N, K)
    am2 = add_mult(i+K, count + 1, N, K)
    return min(am1, am2)
    
def main():
    N = int(input())
    K = int(input())
    print(add_mult(1, 1, N, K))
main()


Measured memory_bytes: 3188
#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

long long num[100005];
long long mn[100005];

int main() {
  long long n, i, j, k;
  scanf(" %lld %lld", &n, &k);
  for(i=0; i<n; i++) mn[i] = 1000000000;
  mn[0] = 0;
  for(i=0; i<n; i++){
    scanf(" %lld", &num[i]);
    for(j=1; j<=k; j++){
      if(i-j>=0) mn[i] = min(mn[i], abs(num[i]-num[i-j])+mn[i-j]);
    }
  }
  printf("%lld\n", mn[n-1]);
}

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

using namespace std;

int main() {
    long long n;
    cin>>n;
    long long a[n],i,k=0,s=0;
    for(i=1;i<=n;i++)
    cin>>a[i];
    for(i=1;i<=n;i++)
    {
        if(a[i]<0)
        {a[i]=0-a[i];k++;}
    }
    if(k%2==0){
        for(i=1;i<=n;i++)
        s=s+a[i];
    }
    else {
        sort(a+1,a+n+1);
        for(i=2;i<=n;i++){
            s=s+a[i];
        }
        s=s-a[1];
    }
    cout<<s;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <time.h>
#include <stdio.h>
#include <vector>
#define int long long
using namespace std;
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
int mypow(int x, int y) {
	if (y == 0)return 1;
	if (y % 2)return mypow(x, y - 1)*x;
	else return mypow(x, y / 2)*mypow(x, y / 2);
}
int Max(int x, int y) {
	if (x > y)return x;
	else return y;
}
int Min(int x, int y) {
	if (x < y)return x;
	else return y;
}
int kai(int x) {
	int cnt = 1;
	if (x == 0)return 1;
	cnt = kai(x - 1);
	return x * cnt;
}
inline void shoki()
{
	srand((unsigned int)time(NULL));
}

/*Library End!*/

signed main() {
	int a, b, k;
	cin >> a >> b >> k;
	for (int i = 0; i < k; i++) {
		if (i % 2 == 1) {
			b /= 2;
			a +=b;
		}
		if(i%2==0){
			a /= 2;
			b+=a;
		}
	}
	cout << a <<" "<< b << endl;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}
ll factorial(ll n) {
  if (n == 1) {
    return 1;
  }
  ll ans = factorial(n-1);
  return ans*n;
}
ll gcd(ll a, ll b) {
  if (a < b) {
    ll tmp = a;
    a = b;
    b = tmp;
  }
  ll r = a%b;
  while(r != 0) {
    a = b;
    b = r;
    r = a%b;
  }
  return b;
}
ll lcm(ll a, ll b) {
  return (a/gcd(a, b))*b;
}

int main() {
    ll a, b, c;
    cin >> a >> b >> c;
    if (a<b && b<c) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 3112
#include <stdio.h>
    #include<stdlib.h>
         
       int main(void)
       {
             long int X, Y;
             scanf("%ld %ld",&X,&Y);

             char ret;
             if(abs(X-Y) <= 1){
             	printf("Brown");
             }
             else{
                printf("Alice");
             }
         
             return 0;
       }

Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long li;
#define rep(i,n) for(int i=0;i<(n);i++)
#define df 0
template<class T> void print(const T& t){ cout << t << "\n"; }
template<class T, class... Ts> void print(const T& t, const Ts&... ts) { cout << t; if (sizeof...(ts)) cout << " "; print(ts...); }
// Container コンテナ型, map以外
template< template<class ...> class Ctn,class T>
std::ostream& operator<<(std::ostream& os,const Ctn<T>& v){
  // ここでストリームに obj を書き込みます。
  auto itr=v.begin();
  while(itr!=v.end()){
    if(itr!=v.begin())cout << " ";
    cout << *(itr++);
  }
  return os;
}

int f(int a,int t,vector<int>& tim, vector<int>& del){
  vector<int> dp(t,0);
  int n=tim.size();
  rep(i,n){    // add del[i]
    if(i==a) continue;
    rep(j,t){
      int k=t-j-1;
      if(k<tim[i]) break;
      dp[k]=max(dp[k],dp[k-tim[i]]+del[i]);
    }
  }
  int ans=0;
  rep(i,t) if(ans<dp[i]) ans=dp[i];
  return ans;
}

int main(){
  int n,t; cin >>n >>t;
  vector<pair<int,int>> v(n);
  rep(i,n){
    int a,b; cin >>a >>b;
    v[i]={a,b};
  }
  sort(v.begin(),v.end());
  int ans=0;
  vector<int> dp(t,0);
  rep(i,n){    // add v[i]
    int m=0;
    rep(j,t) if(m<dp[j]) m=dp[j];
    m+=v[i].second;

    if(ans<m) ans=m;
    
    rep(j,t){
      int k=t-j-1;
      if(k<v[i].first) break;
      dp[k]=max(dp[k],dp[k-v[i].first]+v[i].second);
    }
    if(df)print(dp);
  }

  print(ans);
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;

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

int main(){
    int N;
    cin >> N;
    vector<ll> x(N);
    vector<ll> x_sorted(N);
    rep(i, N) cin >> x[i];
    rep(i, N) x_sorted[i] = x[i];
    sort(x_sorted.begin(), x_sorted.end());
    ll line_num = x_sorted[N/2];
    rep(i, N){
        if(x[i] < line_num) cout << x_sorted[N/2] << endl;
        else cout << x_sorted[N/2-1] << endl;
    }
    return 0;
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
    #include <cmath>
    using namespace std;
     
    int main() {
      int N;
      cin >> N;
      vector<int> H(N);
      
      for (int i = 0; i < N; i++){
        cin >> H.at(i);
      }
      int cnt = 0;
      int score = 0;
      
      for (int i = 0; i < N - 1; i++){
        if (H.at(i) >= H.at(i + 1)) {
          cnt++;
        }
        else {
          if (score <= cnt) {
            score = cnt;
          }
            cnt = 0;
        }
      }
      
      if (score <= cnt) {
        score = cnt;
      }
      cout << score;
    }

Measured memory_bytes: 640
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define ll long long
#define INF (1 << 30)
#define INFLL (1LL << 60)

#define FOR(i,a,b) for(ll i = (a);i<(b);i++)
#define REP(i,a) FOR(i,0,(a))
#define MP make_pair

int n, a[100010];

int main() {
	cin >> n;
	REP(i, n){
		cin >> a[i];
	}
	sort(a, a + n);
	bool flag = true;
	if(n % 2 == 0){
		for(int i = 1;i < n;i += 2){
			if(a[i] != a[i - 1]) flag = false;
			if(a[i] != i) flag = false;
		}
	}else{
		if(a[0] != 0) flag = false;
		for(int i = 1;i < n;i += 2){
			if(a[i] != a[i + 1]) flag = false;
			if(a[i] != i + 1) flag = false;
		}
	}

	if(flag){
		ll ans = 1;
		for(int i = 0;i < n / 2;i++){
			ans *= 2;
			ans %= 1000000007;
		}
		cout << ans << endl;
	}else{
		cout << 0 << endl;
	}
	return 0;
}

Measured memory_bytes: 768
if __name__ == "__main__":
    a = '1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51'
    k = list(a.split(', '))
    i = int(input())
    print(k[i-1])

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

int n,mem[1000000];
int count;
int now=2;

//?´???°??????0
int main(){
	mem[1]=1;
	for(int i=2;i<=(int)sqrt(1000000.0)+1;i++){
		if(mem[i]==0){
			for(int j=2*i;j<=1000000;j+=i){
				mem[j]=1;
			}
		}
	}
	while(cin>>n){
		count=0;
		for(int i=1;i<n+1;i++){
			if(mem[i]==0) count++;	
		}
		cout<<count<<endl;
	}
	return 0;
}

Measured memory_bytes: 6888
#include <iostream>
#include <vector>
//#include <string>
#include <algorithm>
//#include <math.h>
//#include <queue>
//#include <stack>
//#include <iomanip>

// sometimes used
//#include <set>
//#include <map>
//#include <numeric>
//#include <list>
//#include <deque>
//#include <unordered_map>

typedef long long LL;
//typedef long double LD;
using namespace std;
 
//#define MOD 1000000007
#define MAX 10010000000
//#define NIL -1
//#define INFTY 1000000000000000000

int main(){
    LL n;
    LL k;
    cin >> n >> k;
    vector<LL> p(n);
    vector<LL> c(n);
    vector<LL> is_visit(n);
    for(LL i=0; i<n; i++){
        cin >> p[i];
        p[i]--;
    }
    for(LL i=0; i<n; i++){
        cin >> c[i];
    }

    LL max_ans=-1*MAX;
    LL ans;
    LL idx;
    LL loop_sum;
    LL loop_cnt;
    //cout << loop_sum << endl;
    if(k<2*n){
        for(LL i=0; i<n; i++){
            idx=i;
            ans=0;
            idx=p[idx];
            ans+=c[idx];
            max_ans=max(max_ans,ans);
            for(LL j=1; j<k; j++){
                idx=p[idx];
                ans+=c[idx];
                max_ans=max(max_ans,ans);
            }
        }
    }else{
        for(LL i=0; i<n; i++){
            for(LL j=0; j<n; j++){
                is_visit[j]=0;
            }
            idx=i;
            is_visit[idx]++;
            loop_sum=0;
            loop_cnt=0;
            idx=p[idx];
            while(is_visit[idx]!=2){
                if(is_visit[idx]==1){
                    loop_cnt++;
                    loop_sum+=c[idx];
                }
                //cout << is_visit[idx] << endl;
                is_visit[idx]++;
                idx=p[idx];
            }
            //cout << loop_cnt << endl;
            if(loop_sum<0){
                idx=i;
                ans=0;
                idx=p[idx];
                ans+=c[idx];
                max_ans=max(max_ans,ans);
                for(LL j=1; j<2*n; j++){
                    idx=p[idx];
                    ans+=c[idx];
                    max_ans=max(max_ans,ans);
                }
            }else{
                LL num_loop=(k-2*n)/loop_cnt;
                LL res_k=(k-2*n)%loop_cnt+n;
                idx=i;
                ans=0;
                idx=p[idx];
                ans+=c[idx];
                max_ans=max(max_ans,ans);
                //cout << res_k << " " << num_loop << " " << loop_cnt << " " << res_k+loop_cnt*num_loop+2*n << endl;
                for(LL j=1; j<res_k; j++){
                    idx=p[idx];
                    ans+=c[idx];
                    max_ans=max(max_ans,ans);
                }
                ans+=loop_sum*num_loop;
                max_ans=max(max_ans,ans);
                for(LL j=0; j<n; j++){
                    idx=p[idx];
                    ans+=c[idx];
                    max_ans=max(max_ans,ans);
                }
            }
        }
    }

    cout << max_ans << endl;

    return 0;
}


Measured memory_bytes: 3712
#include<stdio.h>
int main(void){
	int n,r;
	int i,j;
	int num[50];
	int p,c;
	int temp[50];
	
	while(1){
		scanf("%d %d",&n,&r);
		
		if(n==0&&r==0){
			break;
		}
		for(i=0;i<n;i++){
			num[i]=n-i;
		}
		
		for(i=0;i<r;i++){
			scanf("%d %d",&p,&c);
			for(j=0;j<c;j++){
				temp[j]=num[p+j-1];
			}

			for(j=0;j<p-1;j++){
				temp[c+j]=num[j];
			}

			for(j=0;j<n-p-c+1;j++){
				temp[p+c+j-1]=num[p+c+j-1];
			}

			for(j=0;j<n;j++){
				num[j]=temp[j];
			}
		}
		printf("%d\n",num[0]);
			}
	return 0;
}

Measured memory_bytes: 600
#include <stdio.h>
#include <iostream>

using namespace std;



int main(void){
   int N = 0,val =0,ans = 0;
   bool finish = 0;
   cin >> N;
    int di[N] = {0};
   for(int i = 0;i < N;i++){
    cin >> di[i];
   }
   while(finish == 0){
    for ( int i =0;i < (N - (val + 1));i ++){
        ans += di[val] * di[val + i + 1];
    }
    if(val == (N - 1))finish = 1;
    val ++;
   }
   cout << ans;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define _repargs(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _repargs(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p = 0) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template
bool same(vector<ll> &A){
    rep(i, A.size()){
        if(A[i] != A[0]) return false;
    }
    return true;
}

ll comb[51][51];
void calc(){
    rep(i, 51) comb[i][0] = 1, comb[i][i] = 1;
    rep(i, 1, 51){
        rep(j, 1, i){
            comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
    int N, A, B;
    cin >> N >> A >> B;
    vector<ll> V(N);
    rep(i, N) cin >> V[i];
    calc();
    
    sort(all(V));
    reverse(all(V));
    ll sum = 0;
    rep(i, A) sum += V[i];
    double ret = (double)sum / A;
    output(ret, 10);
    if(V[0] == V[A - 1]){
        int count = 0;
        rep(i, N){
            if(V[A - 1] == V[i]) count++;
        }
        ll ans = 0;
        rep(i, A, B + 1){
            ans += comb[count][i];
        }
        output(ans);
    }
    else{
        int c = 0, count = 0;
        rep(i, A){
            if(V[A - 1] == V[i]) c++;
        }
        rep(i, N){
            if(V[A - 1] == V[i]) count++;
        }
        output(comb[count][c]);
    }
    
    
    
    
    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys

def get_num():
    return int(input())


def get_nums(n):
    res = [0 for _ in range(n)]
    for i in range(n):
        res[i] = int(input())
    return res


def get_numbers():
    return map(int, input().split())


n = get_num()
a = list(reversed(list(get_numbers())))
b = list(reversed(list(get_numbers())))

ans = 0
for i in range(n):
    cost = min(a[i], b[i])
    a[i] -= cost
    b[i] -= cost
    ans += cost

    cost = min(a[i + 1], b[i])
    a[i + 1] -= cost
    ans += cost

print(ans)

Measured memory_bytes: 83940
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>

#include<stack>
#include<queue>
#include<time.h>
#include<set>
#include<map>
#include <iomanip>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>b;i--)
#define vint vector<int> 
#define vvint vector<vint>
#define ct(a) cout<<a<<endl
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll mod = 1e9 + 7;



string S;

ll N, k, ans = 1;
ll a[100005];
ll beki[40];
bool flag = true;
map<int, int> mp;

int main() {

	cin >> N;
	FOR(i, 0, N) {
		cin >> a[i];
		mp[a[i]]++;
	}
	sort(a, a + N);
	reverse(a, a + N);
	if (a[0] == 0) {
		cout << "Yes" << endl;
	}
	else if (N % 3 != 0) {
		cout << "No" << endl;

	}else if (mp[0] == N / 3 && mp[a[0]] == N * 2 / 3) {
		cout << "Yes" << endl;
	}
	else {

		int knd = 0;
		int ans = 0;
		for (auto ite = mp.begin(); ite != mp.end(); ite++) {
			if (ite->first == 0)continue;
			knd++;
			ans ^= ite->first;
			if (ite->second != N / 3) {
				ans = 1;
				

			}
		}
		if (knd==3&&ans == 0)cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	
	
	return 0;
}


Measured memory_bytes: 4480
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#define rep(i,n) for (int i = 0; i < n; ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int a, b, c; cin >> a >> b >> c;
  cout << max({a, b, c}) - min({a, b, c}) << endl;
  return 0;
}

Measured memory_bytes: 3188
if __name__ == '__main__':
    N = int(input())
    A = [int(i) for i in input().split()]

    flag = 'flat'

    counter = 1

    for i in range(1, N):
        old = A[i-1]
        new = A[i]

        if flag == 'inc':
            if old <= new:
                continue
            else:
                counter += 1
                flag = 'flat'

        elif flag == 'dec':
            if old >= new:
                continue
            else:
                counter += 1
                flag = 'flat'
        else:
            if old < new:
                flag = 'inc'
            elif old > new:
                flag = 'dec'
            else:
                continue

    print(counter)


Measured memory_bytes: 14224
f :: Int -> Bool
f n
	| odd n          = True
	| n `mod` 3 == 0 = True
	| n `mod` 5 == 0 = True
	| otherwise      = False

main = do
	n <- getLine
	lista <- (map read . words) <$> getLine
	if and $ map f lista
		then putStrLn "APPROVED"
		else putStrLn "DENIED"

Measured memory_bytes: 892
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <string>
#include <cmath>
#include <complex>
#include <numeric>
#include <cassert>

#include <vector>
#include <array>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>

#define int64 long long
#define uint64 unsigned long long
using namespace std;

int main()
{
	int64 aa, bb;
	cin >> aa >> bb;
	cout << aa * bb / gcd(aa, bb) << endl;
	return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#define llint long long

using namespace std;
typedef pair<llint, llint> P;

llint n;
llint a[305][305];

int main(void)
{
	cin >> n;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			cin >> a[i][j];
		}
	}
	llint ans = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(i >= j) continue;
			bool flag = true;
			for(int k = 1; k <= n; k++){
				if(i == k || j == k) continue;
				if(a[i][k] + a[k][j] < a[i][j]){
					cout << -1 << endl;
					return 0;
				}
				if(a[i][k] + a[k][j] == a[i][j]) flag = false;
			}
			if(flag) ans += a[i][j];
		}
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int n;
    long long int k;
    std::cin >> n >> k;
    std::vector<std::pair<int, int>> v(n);
    for (int i = 0; i < n; i++) {
        int a, b;
        std::cin >> a >> b;
        v[i] = {a, b};
    }
    std::sort(v.begin(), v.end());
    for (auto x : v) {
        k -= x.second;
        if (k <= 0) {
            std::cout << x.first << std::endl;
            break;
        }
    }
}

Measured memory_bytes: 1024
#include<stdio.h>
 
int main()
{
	int A, B;
	scanf("%d %d", &A, &B);
	int sum = A + B + 1;
	char str[sum];
	scanf("%s", &str);
	int ctr = 0;
	for(int i = 0; i < sum; i++){
		if(i == A){
			if(str[i] != '-'){
				printf("No\n");
				return 0;
			}
		}else{
			if(str[i] >= '0' && str[i] <= '9'){
				++ctr;
			}
		}
	}
	if(ctr == A+B){
		printf("Yes\n");
	}else{
		printf("No\n");
	}
}

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

x3 = N[1] - N[3] + N[2]
x4 = N[1] - N[3] + N[0]
y3 = N[2] - N[0] + N[3]
y4 = N[2] - N[0] + N[1]

print(x3, y3, x4, y4)

Measured memory_bytes: 3060
s=input()
l=len(s)
a,b="", ""
for i in range(l):
  if i %2==0:
    a += "1"
    b += "0"
  else:
    a += "0"
    b += "1"
diff_a, diff_b = 0, 0
for i in range(l):
  if a[i] != s[i]:
    diff_a += 1
  if b[i] != s[i]:
    diff_b += 1
print(min(diff_a, diff_b))

Measured memory_bytes: 9284
eng=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','x','y','z']

sentence=input()
sentence= sentence.lower()

for i in eng:
  if not i in sorted(list(set(sorted(sentence)))):
    print(i)
    break
else:
    print('None')

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

typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;

int gcd_pair(int a, int b)
{
  int r;
  int tmp;

  if (a < b)
  {
    tmp = a;
    a = b;
    b = tmp;
  }
  r = a % b;
  while (r != 0)
  {
    a = b;
    b = r;
    r = a % b;
  }
  return (b);
}

int gcd(int *num, int c)
{
  int last_index;

  last_index = c - 1;
  if (last_index != 0)
  {
    for (int i = 0; i < last_index; i++)
    {
      if (num[i] != 0 && num[i + 1] != 0)
        num[i + 1] = gcd_pair(num[i], num[i + 1]);
      else
        break;
    }
  }
  return (num[last_index]);
}

int main(void) {
  int scan; // scanf result
  int answer; // to output 
  int k; // to input 
  int a;
  int b;
  int c;
  int *list;

  scan = scanf("%d", &k);
  answer = 0;
  list = (int *)malloc(sizeof(int) * 3);
  a = 1;
  while (a <= k) {
    b = 1;
    while (b <= k) {
      c = 1;
      while (c <= k) {
        list[0] = a;
        list[1] = b;
        list[2] = c;
        answer += gcd(list, 3);
        c++;
      }
      b++;
    }
    a++;
  }
  printf("%d", answer);
  return (0);
}


Measured memory_bytes: 1732
#include"iostream"
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
#include<list>
#include<map>
#include<string>
#include<algorithm> 
#include <queue> 
#include <sstream>
#include <fstream>
#include<cmath>
#define INF 1000000000
#define LL long long
using namespace std;

vector<LL> v;
vector<LL> vv;
long long N, M, ans, A[100000];
string s;

LL gcd(LL a, LL b) {
	if (b == 0)return a;
	return gcd(b, a%b);
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 1; i < N; i++) {
		ans = gcd(A[i], A[i - 1]);
		A[i] = ans;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define BIG 1000000010
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
typedef long long int ll;
#define N 300000

int prime[N];

void eratosthenes(){
  rep(i,N) prime[i]=1;
  prime[0]=prime[1]=0;
  rep(i,N){
    if(prime[i]){
      for(int j=i+i;j<N;j+=i) prime[j]=0;
    }
  }
}

int main(){
  int n,p;
  int a[100000];
  int b1,b2;
  eratosthenes();
  while(1){
    cin>>n>>p;
    if(n==-1 && p==-1) break;
    vector<int> P;
    rep(i,N){
      if(prime[i] && i>n) P.push_back(i);
    }
    int c=0;
    b1=b2=0;
    int f;
    f=P.size();
    rep(i,min(p,f)){
      repi(j,i,min(p,f)+i){
	a[c]=P[i]+P[j];
	c++;
      }
    }
    sort(a,a+c-1);
    cout<<a[p-1]<<endl;
  }
  return 0;
}










Measured memory_bytes: 4416
/*Function Template*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int mod = 1000000007;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define ALL(a)  (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);


ll Len(ll n) {
  ll s=0;
  while(n!=0) s++, n/=10;
  return s;
}


ll Sint(ll n) {
  ll m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(ll i=s-1;i>=0;i--) m+=n/((ll)pow(10,i))-(n/((ll)pow(10,i+1)))*10;
  return m;
}


ll Svec(vector<ll> v){
  ll n=0;
  for(ll i=0;i<v.size();i++) n+=v[i];
  return n;
}


ll GCD(ll a,ll b){
  ll r,tmp;
/*自然数 a > b を確認・入替*/
  if(a<b){
    tmp=a,a=b,b=tmp;
  }
/*ユークリッドの互除法*/
  r=a%b;
  while(r!=0){
    a=b,b=r,r=a%b;
  }
  return b;
}


ll LCM(ll a,ll b){
  ll c=a,d=b,r,tmp;
/*自然数 a > b を確認・入替*/
  if(a<b){
    tmp=a,a=b,b=tmp;
  }
/*ユークリッドの互除法*/
  r=a%b;
  while(r!=0){
    a=b,b=r,r=a%b;
  }
  return c/b*d;
}


ll Factorial(ll n){
  ll m=1;
  while(n>=1) m*=n,n--;
  return m;
}

vector<pair<char,ll>> runlength(string s,vector<pair<char,ll>> p){
  ll x=1;
  if(s.size()==1){
    p.push_back(pair<char,ll>(s[0],1));
    return p;
  }
  for(ll i=0;i<s.size()-1;i++){
    if(s[i]==s[i+1]){
      x++;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[i],x));
      }
    }else{
      p.push_back(pair<char,ll>(s[i],x));
      x=1;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[s.size()-1],x));
      }
    }
  }
  return p;
}



/*↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓*/
int main() {
  IOS;
  string s,t;
  cin>>s>>t;
  vector<ll> v1(26,0),v2(26,0);
  rep(i,s.size()){
    ll si=s[i]-'a';
    ll ti=t[i]-'a';
    v1[si]++;
    v2[ti]++;
    if(v1[si]!=v2[ti]){
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;
}

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

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        v.push_back(x);
    }


    int current_min = INT_MAX;
    int max_profit = INT_MIN;
    for (int i = 0; i < v.size(); i++) {
        if (max_profit < (v[i] - current_min)) max_profit = (v[i] - current_min);
        if (current_min > v[i]) current_min = v[i];
    }

    cout << max_profit << endl;
    return 0;
}



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

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt = 0;
    string abc = "ABC";
    for (int i = 0; i < n; i++){
        bool flag = true;
        for (int j = 0; j < 3; j++){
            if (i + j >= n) {
                flag = false;
                break;
            }
            if (s[i + j] != abc[j]) flag = false;
        }
        if (flag) cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
long long b[65000],m,w;
int main(void)
{
    int n,i,a;
	while(1){
	    scanf("%d",&n);
		if(n==0) break;
		w=0;
		for(i=0;i<n;i++){
		    scanf("%d",&a);
			w+=a;
		}
		for(i=1;i<n;i++){
		    scanf("%lld",&b[i]);
		}
		sort(b+1,b+n);
		m=w*n;
		for(i=n-1;i>0;i--){
		    w=w+b[i];
			if(m<w*i){
			    m=w*i;
			}
		}
		printf("%lld\n",m);
	}
	return 0;
}

Measured memory_bytes: 3312
house_info = [[[0 for i in xrange(10)]for j in xrange(3)]for k in xrange(4)]

n = input()

for i in xrange(n):
    b,f,r,v=map(int,raw_input().split())
    house_info[b-1][f-1][r-1] += v
    
for i in xrange(4):
    for j in xrange(3):
        result = " " + " ".join(map(str,house_info[i][j]))
        print result
    if i < 3:
        print "####################"

Measured memory_bytes: 6452
#include <iostream>
#include <set>

using namespace std;

string s;
set<int> pos [200];

void update (int idx, char val) {
  pos[s[idx - 1]].erase(idx);
  s[idx - 1] = val;
  pos[s[idx - 1]].insert(idx);
}

int cnt (int l, int r) {
  int ans = 0;
  for (char c = 'a'; c <= 'z'; c++) {
    auto lb = pos[c].lower_bound(l);
    if (lb != pos[c].end() && *lb <= r) {
      ans++;
    }
  }
  return ans;
}

int main () {
  ios::sync_with_stdio(false);

  int n, q;
  cin >> n;

  cin >> s;

  for (int i = 0; i < n; i++) {
    pos[s[i]].insert(i + 1);
  }
  
  cin >> q;
  for (int i = 0; i < q; i++) {
    int t;
    cin >> t;
    if (t == 1) {
      int idx;
      char val;
      cin >> idx >> val;
      update(idx, val);
    } else {
      int l, r;
      cin >> l >> r;
      cout << cnt(l, r) << '\n';
    }
  }
}


Measured memory_bytes: 24220
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
    
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


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

#if gcd(*A) % 2 != 0:
    #print(0)
    #exit(0)

#sisu_2 = factorization(A[0])[0][1] 
sisu_2 = min([factorization(A[i])[0][1] for i in range(min(100,N))])

#lcm_a = lcm(*A)
#lcm_a_half = lcm_a // 2
lcm_a = lcm(*A) // 2
'''
l = []
sisu_a0 = 0
for i in range(N):
    sisu = 0
    while A[i]%2==0:
        A[i] //= 2
        sisu += 1
    
    if sisu_a0==0:
        sisu_a0 = sisu
    else:
        if sisu_a0!=sisu:
            print(0)
            exit()
'''
if (lcm_a % (2**sisu_2) == 0) or lcm_a > M:
#factorization(lcm_a)[0][1] != sisu_2 or lcm_a_half > M:
#if lcm_a > M:
    print(0)
    exit(0)
else:
    print(int((M-lcm_a) // (lcm_a*2) + 1))

Measured memory_bytes: 16308
n, m = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(m)]

A.sort(key=lambda a:a[1])
ans = 0
last = 0

for a, b in A:
    if a >= last:
        ans += 1
        last = b

print(ans)

Measured memory_bytes: 22832
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

int main() {
	int n;
  	cin >> n;
  	cout << 1+(n-1)/2 << endl;
    return 0;
}



Measured memory_bytes: 256
def main():
    N = int(input())
    x = list(map(int, input().split()))
    x = sorted([(x[i], i) for i in range(N)])
    ans = [0] * N
    for i in range(N//2):
        ans[x[i][1]] = x[N//2][0]
    for i in range(N//2, N):
        ans[x[i][1]] = x[N//2 - 1][0]
    for i in range(N):
        print(ans[i])

if __name__ == "__main__":
    main()

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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<pii> ab(n);
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    ab[i] = pii(a, b);
  }
  sort(ab.begin(), ab.end(), [](pii a, pii b) { return a.second < b.second; });
  // bool ans = true;
  int sum = 0;
  for (int i = 0; i < n; i++) {
    sum += ab[i].first;
    if (sum > ab[i].second) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  // for (auto e : a_sum) {
  //   printf("%d ", e);
  // }
  // printf("\n");
  // bool ans = true;
  // for (int i = 0; i < n; i++) {
  //   ab[i].second - ab[i].first;
  // }
  return 0;
}


Measured memory_bytes: 1920
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;

#define pb push_back

bool bd[3000][3000];

template <typename X> int index(vector<X> v, X key) {
    return lower_bound(v.begin(), v.end(), key) - v.begin();
}

int main() {
    long long w, h;
    while (cin >> w >> h, h) {
        int n;
        cin >> n;

        vector<long long> xs(1, 0), ys(1, 0);
        xs.pb(w);
        ys.pb(h);

        vector<long long> x1(n), y1(n), x2(n), y2(n);
        for (int i=0; i<n; ++i) {
            cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
            xs.pb(max(x1[i]-1, 0LL));
            xs.pb(x1[i]);
            xs.pb(max(x2[i]-1, 0LL));
            xs.pb(x2[i]);
            ys.pb(max(y1[i]-1, 0LL));
            ys.pb(y1[i]);
            ys.pb(max(y2[i]-1, 0LL));
            ys.pb(y2[i]);
        }

        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());

        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());

        memset(bd, false, sizeof bd);
        int X1, Y1, X2, Y2;
        for (int i=0; i<n; ++i) {
            Y1 = index(ys, y1[i]);
            Y2 = index(ys, y2[i]);
            for (int j=Y1; j<Y2; ++j) {
                X1 = index(xs, x1[i]);
                X2 = index(xs, x2[i]);
                for (int k=X1; k<X2; ++k) {
                    bd[j][k] = true;
                }
            }
        }

        int H = index(ys, h);
        int W = index(xs, w);
        int res = 0;

        for (int i=0; i<H; ++i) {
            for (int j=0; j<W; ++j) {
                if ( ! bd[i][j]) {
                    res ++;

                    queue<pair<int,int> > q;
                    q.push(make_pair(i, j));
                    while ( ! q.empty()) {
                        int ny = q.front().first;
                        int nx = q.front().second;
                        q.pop();
                        if ( ! bd[ny][nx] && 0 <= nx && nx < W && 0 <= ny && ny < H) {
                            bd[ny][nx] = true;
                            q.push(make_pair(ny, nx+1));
                            q.push(make_pair(ny, nx-1));
                            q.push(make_pair(ny+1, nx));
                            q.push(make_pair(ny-1, nx));
                        }
                    }
                }
            }
        }

        cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 11888
import copy


class Line:
    def __init__(self, a, b):
        self.a = a
        self.b = b


def generate_patterns(remains, current_pattern, patterns):
    if len(remains) == 0:
        patterns.append(current_pattern)
        return
    for remain in remains:
        _current_pattern = copy.copy(current_pattern)
        _current_pattern.append(remain)
        _remains = copy.copy(remains)
        _remains.remove(remain)
        generate_patterns(_remains, _current_pattern, patterns)
    return patterns


N, M = map(int, input().split())
lines = []
for _ in range(M):
    a, b = map(int, input().split())
    lines.append(Line(a, b))

m = {}
for i in range(1, N+1):
    m[i] = {}
    for j in range(1, N+1):
        m[i][j] = False

for line in lines:
    m[line.a][line.b] = True
    m[line.b][line.a] = True

remains = []
for i in range(2, N+1):
    remains.append(i)
patterns = generate_patterns(remains, [1], [])

cnt = 0
for pattern in patterns:
    countable = True
    for i in range(len(pattern)-1):
        current = pattern[i]
        next = pattern[i+1]
        if not(m[current][next]):
            countable = False
            break
    if countable:
        cnt += 1

print(cnt)


Measured memory_bytes: 4332
import Data.List
  ( sortBy )
import qualified Data.ByteString.Char8 as C
import Data.Maybe ( fromJust )

readInts :: IO [Int]
readInts = map (fst . fromJust . C.readInt) . C.words <$> C.getLine

main :: IO ()
main = do
  [_,k] <- readInts 
  ls    <- readInts 
  print $ maxSnuke k ls

maxSnuke
  :: Int -> [Int] -> Int
maxSnuke k = sum . take k . sortBy (flip compare)

Measured memory_bytes: 508
//{{{
#include<algorithm>
#include<cmath>
#include<fstream>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<random>
#include<set>
#include<sstream>
#include<sys/time.h>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printw) FUNC(printwe) FUNC(printb) FUNC(printbe) FUNC(printd) FUNC(printde) FUNC(printdu);
#endif
template <class S, class T>
istream& operator >> (istream& in, pair<S, T>& p){ return in >> p.first >> p.second; }
template <class T>
istream& operator >> (istream& in, vector<T>& v){ for(auto& e : v){ in >> e; } return in; }
//}}}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s; cin >> s;
    cout << (stoi(s.substr(5, 2)) >= 5 ? "TBD" : "Heisei") << '\n';
}


Measured memory_bytes: 764