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

// Function Macros:
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define setpre(n) cout << fixed << setprecision(n)

// Type / Class / Struct Definitions:
using namespace std;

using ll = long long;
using ull = unsigned long long;

// Constants:
const int INF = (1ll << 30) - 1;  // approx 1.07e9
const ll INFLL = 1ll << 60;       // approx 1.15e18
const int MOD = 1e9 + 7;          // 998244353
const long double EPS = 1.0e-14;

// Global Variables:

// Prototype Declarations:
int gcd(int, int);
template <class T>
inline bool chmin(T&, T);
template <class T>
inline bool chmax(T&, T);

// ================ Main Loop ================
int main() {
    int n, m, x;
    cin >> n >> m >> x;
    vector<int> c(n);
    vector<vector<int>> a(n, vector<int>(m));
    rep(i, n) {
        cin >> c[i];
        rep(j, m) {
            cin >> a[i][j];
        }
    }
    ll ans = INF;
    rep(i, 1 << n) {
        vector<int> now(m, 0);
        ll price = 0;
        int dg = i;
        for(int book = 0; dg != 0; book++) {
            if(dg % 2) {
                rep(algo, m) {
                    now[algo] += a[book][algo];
                }
                price += c[book];
            }

            dg /= 2;
        }

        //check >= x
        rep(j, m) {
            // cout << "ptn: " << i << ", algo[" << j << "]: " << now[j] << endl;
            if(now[j] < x) {
                break;
            } else if(j == m - 1) {
                // cout << "called" << endl;
                if(price < ans) {
                    // cout << ans << " " << price << endl;
                    ans = price;
                }
            }
        }
    }
    if(ans == INF) ans = -1;
    cout << ans << endl;
    return 0;
}
// ===========================================

// Functions:
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

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;
}


Measured memory_bytes: 3640
N,M,K=map(int,input().split())
MOD=10**9+7

# 組合せの総数
def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
            result%=MOD

    return result



ans_x=0
ans_y=0

for i in range(1,N):
  ans_x+=i*(N-i)
  ans_x%=MOD
for i in range(1,M):
  ans_y+=i*(M-i)
  ans_y%=MOD
ans_x*=((M**2))
ans_y*=((N**2))
ans=comb(N*M-2,K-2)
ans*=(ans_x+ans_y)
ans%=MOD
print(int(ans))

Measured memory_bytes: 11512
//ABC 155 C Poll
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    string s;
	map<string,int> count;
    
	cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s;
        count[s]++;
    }
    
    int maxv=0;
    map<string,int>::iterator it;
    
	for(it=count.begin(); it!=count.end(); it++){
        maxv = max(maxv, it->second);
    }
    
    for(it=count.begin(); it!=count.end(); it++){
       if(it->second==maxv){
          cout << it->first << endl;
       }
    }
    
	return 0;
}


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

int main() {
  ll a, b;
  char op;
  cin >> a >> op >> b;
  if(op == '+'){
    cout << a + b << endl;
  }else {
    cout << a - b << endl;
  }
  return 0;
}

Measured memory_bytes: 256
import os
import sys

for line in sys.stdin:
    v, d = [int(item) for item in line.split()]

    fib = [1,1]

    for i in xrange(v):
        fib.append((fib[-1]+fib[-2])%1001)

    fib = sorted(fib[2:])

    count = 1
    for i in xrange(len(fib)-1):
        if fib[i+1]-fib[i] >= d: count += 1

    print count

Measured memory_bytes: 4268
import java.util.*;

public class Main {
	
	public static void main(String[] args) {

		// argumentの取得
		Scanner s = new Scanner(System.in);

		int x = s.nextInt();
        int y = s.nextInt();
      
        if (x + y == 5){
          System.out.println(1);
        } else if (x + y == 4) {
          System.out.println(2);
        } else {
          System.out.println(3);
        }
           
		// 戻り値の返却
		//System.out.println(x+y);
	
	} 
}

Measured memory_bytes: 23252
import java.util.*;
import java.util.stream.*;

public class Main {

    static Scanner sc = new Scanner(System.in);
    static int mod = (int)1e9 + 7;

    public static void main(String[] args) {
        int a = sc.nextInt();
        int b = sc.nextInt()-1;
        if (b % (a - 1) == 0) {
            System.out.println(b / (a - 1));
        } else {
            System.out.println(b / (a - 1) + 1);
        }
    }

}


Measured memory_bytes: 22100
/*
  The Island Was Silent before.
  .....
  And One day again it became Silent.
*/
#include<bits/stdc++.h>
using namespace std;
 
#define endl '\n'
#define ll  long long
#define modd(a,b) ((a+2*b)%b)
#define debug(a) cout << #a << ": " << (a) << "\n"
#define ioso ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define rtt cerr << "Time: " << clock()*1.0 / CLOCKS_PER_SEC << endl;
#define ffe freopen("input.txt","r",stdin), freopen("output.txt","w",stdout);
 
int main() {
  ioso
  #ifndef ONLINE_JUDGE
  ffe
  #endif
  ll n, k; cin >> n >> k;
  int a[200010];
  int fr[200010];
  memset(fr,0,sizeof(fr));
  for(int i=1;i<=n;i++) {
    cin >> a[i];
  }
  int as=1;
  std::vector<ll> vs;
  vs.push_back(-12);
  for(int i=1;i<=n;i++) {
    if(fr[as]==0) {
      fr[as]=i;
      vs.push_back(as);
      as = a[as];

    }
    else {
      break;
    }
  }

  ll siz = vs.size();
 // cout << siz << endl;
 
  siz-=1;
  if(k<=siz) {
    cout << a[vs[k]] << endl;
    return 0;
  }

  ll numas = (siz-fr[as])+1;
//  debug(as);
//  debug(numas);
  k-= (siz-numas);
//  debug(k);
  //ll oti = siz-numas;
  ll ff = k%numas;
  if(ff==0) {ff=numas;}
 // debug(ff);
  ll ans = a[vs[ff+(siz-numas)]];
 // debug(vs[ff+(siz-numas)]);
 // cout << ff-fr[as]+1 << endl;
  cout << ans << endl;
  
  //cout << ans << endl;
}

Measured memory_bytes: 6876
#include<stdio.h>
int main(void){
    int W, H, x, y, r;
    scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);
    if (y - r < 0 || x - r<0 || y + r > H || x + r>W){
            printf("No\n");}
    else
    {
        printf("Yes\n");
     
}
 
    return 0;
}

Measured memory_bytes: 584
# -*- coding: utf-8 -*-
from collections import defaultdict
from math import sqrt,floor
num,product = map(int,input().split())
cnt = int(sqrt(product) + 2)
dd = defaultdict(int)

for i in range(2,cnt):
    if product % i == 0:
        a = 0
        while product % i == 0:
            a += 1
            product = product // i
        dd[i] = a
if product != 1:
    dd[product] =  1
ans = 1
for p,n in dd.items():
    ans *= pow(p,floor(n/num))
print(ans)

Measured memory_bytes: 9400
#include <bits/stdc++.h> 
using namespace std;
///////////////////////////////////////////
const long long int INF = INT32_MAX;
const long long int Mod = 1000000007;
const long long int mod = 100000;//10^5
using ll = long long int; //long long int は64bit
using ci = const int; using vi = vector<int>; using Vi = vector<long long int>; using pii = pair<int,int>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(int i=0;i<N;i++)
#define np nullptr
template<class T>bool chmax(T &former, const T &b) { if (former<=b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define fill(x,num) memset(x,num,sizeof(x));
typedef vector<vector<ll> > matrix;
//       cin.tie(0);ios::sync_with_stdio(false);
void cinit(){cin.tie(0);ios::sync_with_stdio(false);}
//////////////////////////^^ *Emile ^^^//////////////////////////////////////////////////////

ll n,a;

int main(){
	cin>>n>>a;
	n%=500;
	if(n<=a){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
n = int(input())
a = [int(i) for i in input().split()]
ans = []
if n % 2 == 0:
    for i in range(n-1,-1,-2):
        ans.append(a[i])
    for i in range(0,n,2):
        ans.append(a[i])
else:
    for i in range(n-1,-1,-2):
        ans.append(a[i])
    for i in range(1,n,2):
        ans.append(a[i])
print(' '.join(map(str,ans)))

Measured memory_bytes: 29760
total = input()
L = list(map(int, input().split()))
sum=0
Q=0
for i in range(int(total)):
  if i == 0:
    Q=L[i]
    sum = sum  + 1
  else:
    if Q>=L[i]:
      sum = sum  + 1
      Q=L[i]
print(sum)


Measured memory_bytes: 26792
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i =0;i<n;i++)
typedef long long int ll;
#define ALL(a) a.begin(),a.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int inf = 1<<31 - 1;
int main() {
  ll a[2],b[2],ans =-1e18;cin >> a[0]>>a[1]>>b[0]>>b[1];
  rep(i,2) rep(j,2) chmax(ans,a[i]*b[j]);
  cout << ans << endl;
}

Measured memory_bytes: 3632
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int N, M;
	cin >> N >> M;
	vector<int> L(2 * N), R(2 * N);
	for (int i = 0; i < 2 * N; ++i) {
		while (L[i] * L[i] + i * i < N * N) ++L[i];
		while (R[i] < 2 * N && R[i] * R[i] + i * i <= 4 * N * N) ++R[i];
	}
	int ans = 0;
	for (int i = 0; i <= N; ++i) {
		vector<vector<int> > dp(N + 1, vector<int>(i + 1));
		dp[N][0] = 1;
		int ptr = 2 * N, anti = 0;
		for (int j = N - 1; j >= 0; --j) {
			while (R[ptr - 1] < L[j]) {
				--ptr;
				for (int k = 0; k <= N - j - 1 && k <= i; ++k) {
					dp[j + 1][k] = 1LL * dp[j + 1][k] * max(R[ptr] - (k + anti), 0) % M;
				}
				++anti;
			}
			for (int k = 0; k <= N - j - 1 && k <= i; ++k) {
				if (k != i) dp[j][k + 1] = (dp[j][k + 1] + 1LL * dp[j + 1][k] * max(L[j] - (k + anti), 0)) % M;
				dp[j][k] = (dp[j][k] + 1LL * dp[j + 1][k] * max(R[j] - (2 * N - j + (i - k) - 1), 0)) % M;
			}
		}
		int sub = dp[0][i];
		while (ptr > N) {
			--ptr;
			sub = 1LL * sub * max(R[ptr] - (i + anti), 0) % M;
			++anti;
		}
		if (i % 2 == 0) ans = (ans + sub) % M;
		else ans = (ans - sub + M) % M;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 552
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = int(A); I < int(B); ++I)
#define FORR(I,A,B) for(ll I = int((B)-1); I >= int(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	ll N,ans=0;
	cin >> N;
	ll imos[1004][1004]={};
	FOR(i,0,N){
		ll x1,x2,y1,y2;
		cin >> x1 >> y1 >> x2 >> y2;
		x2--;y2--;
		imos[x1][y1]++;
		imos[x2+1][y2+1]++;
		imos[x1][y2+1]--;
		imos[x2+1][y1]--;
	}
	FOR(i,0,1002){
		FOR(j,0,1002){
			imos[i][j+1] += imos[i][j];
		}
	}
	FOR(j,0,1002){
		FOR(i,0,1002){
			imos[i+1][j] += imos[i][j];
		}
	}
	FOR(i,0,1002){
		FOR(j,0,1002){
			ans = max(ans,imos[i][j]);
		}
	}
	cout << ans << endl;
}


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n), b(n), c(n-1);
  rep(i,n) {
    int x;
    cin >> x;
    a[i] = --x;
  }
  rep(i,n) cin >> b[i];
  rep(i,n-1) cin >> c[i];

  int ans = 0;
  rep(i,n) {
    ans += b[a[i]];
    if (i < n-1 && a[i]+1 == a[i+1]) ans += c[a[i]];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define mem(a,b) memset(a,b,sizeof(a))
#define eb emplace_back
#define mp make_pair
using namespace std;
string s,t;
int n,ans;
bool check(){
    for(int i=0;i<s.length();i++){
        if(s[i]==t[0]){
            for(int j=i+1;j<s.length();j++){
                if(s[j]==t[1]){
                    for(int k=j+1;k<s.length();k++){
                        if(s[k]==t[2]){
                            return true;
                        }
                    }
                    return false;
                }
            }
            return false;
        }
    }
    return false;
}
int main(){
    cin>>n>>s;
    t="   ";
    for(char i='0';i<='9';i++){
        for(char j='0';j<='9';j++){
            for(char k='0';k<='9';k++){
                t[0]=i,t[1]=j,t[2]=k;
                if(check()){
                    ans++;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
using ll = long long;
int main(){
  ll n;
  cin >> n;

  ll div = 26;
  stack<char> st;
  while(n > 0){
    int rem = (n+div-1)%div;
    char next = 'a'+ rem;
    st.push(next);
    if(n == 26) break;
    n = (n-rem)/div;
  }

  while(!st.empty()){
    cout << st.top();
    st.pop();
  }
  cout << endl;
}

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

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
typedef vector<pi> vpi;
typedef vector<string> vsi;
typedef map<ll, ll> mape;
#define rep(i, a, b) for(ll i=(ll)a;i<=(ll)b;i++)
#define per(i, a, b) for(ll i=(ll)a;i>=(ll)b;i--)
#define fastio {ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);}
#define N 2100
#define MAX 10000001
#define f first
#define s second
#define pb push_back
#define mkp make_pair
#define MOD 1000000007

vi divi(MAX);

void sum(ll n)
{
    rep(i, 2, n) divi[i] *= i;
    rep(i, 2, n) divi[i] += divi[i-1];
}

int main()
{
    fastio;

    //clock_t tStart = clock();

    ll n;
    cin >> n;
    rep(i, 1, n){
        ll j = i;
        while(j <= n){
            divi[j]++;
            j += i;
        }
    }
    sum(n);
    cout << divi[n] << endl;

    //printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
    return 0;
}


Measured memory_bytes: 81232
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#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 SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
int main()
{
	while(1)
	{
		int n,m;
		bool used[510];
		memset(used,0,sizeof(used));
		used[1]=true;
		cin >> n;
		cin >> m;
		if(n==0&&m==0)break;
		vector<int> f[n+1];
		int ans=0;
		for(int i=0;i<m;i++)
		{
			int a,b;
			cin >> a >> b;
			if(a==1)
			{
				ans++;
				used[b]=true;
			}
			f[a].pb(b);
                        f[b].pb(a);
		}
		for(int i=0;i<f[1].size();i++)
		{
			for(int j=0;j<f[f[1][i]].size();j++)
			{
				if(!used[f[f[1][i]][j]])
				{
					ans++;
					used[f[f[1][i]][j]]=true;
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1360
#include<bits/stdc++.h>
using namespace std;
#include<math.h>
int dx[]={2,2,1,-1,-2,-2,1,-1};
int dy[]={1,-1,2,2,1,-1,-2,-2};
int vis[201][201];
int main()
{
    map<int,string>m;
    m[1]="Sunny";
    m[2]="Cloudy";
    m[3]="Rainy";
    string s;
    cin>>s;
    if(s==m[1])
        cout<<m[2]<<endl;
    if(s==m[2])
        cout<<m[3]<<endl;
    if(s==m[3])
        cout<<m[1]<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define scd(t) scanf("%d",&t)
#define scld(t) scanf("%ld",&t)
#define sclld(t) scanf("%lld",&t)
#define scc(t) scanf("%c",&t)
#define scs(t) scanf("%s",t)
#define scf(t) scanf("%f",&t)
#define sclf(t) scanf("%lf",&t)
#define MEM(a, b) memset(a, (b), sizeof(a))
#define ffor(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define rfor(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define rep(i, j) ffor(i, 0, j, 1)
#define rrep(i, j) rfor(i, j, 0, 1)
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define IN(A, B, C) assert( B <= A && A <= C)
#define mp make_pair
#define pb push_back
//#define f first
//#define s second
#define inf (int)1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define read(type) readInt<type>()
#define trace1(x)                     cout <<#x<<": "<<x<< endl;
#define trace2(x, y)                 cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define trace3(x, y, z)              cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define trace4(a, b, c, d)           cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
#define trace5(a, b, c, d, e)        cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<<": "<<e<<endl;
const double pi=acos(-1.0);
typedef pair<long long int,long long int> pii;
typedef long long ll;
typedef vector<long long int> vi;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef map<long long int,long long int> mpii;
typedef set<long long int> sei;
typedef multiset<long long int> msei;
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int  uint64;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    ll i,j,n,m,W;
    cin>>n>>W;
    ll w[n],v[n];
    for(i=0;i<n;i++)
        cin>>w[i]>>v[i];
    ll dp[n+1][100001];
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=100000;j++)
            dp[i][j]=LLONG_MAX-100000000000;
    }
    dp[0][0]=0;
    for(i=1;i<=n;i++)
        dp[i][0]=0;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=100000;j++)
        {
            if(j>=v[i-1])
            {
                dp[i][j]=min(dp[i][j],w[i-1]+dp[i-1][j-v[i-1]]);
                dp[i][j]=min(dp[i][j],dp[i-1][j]);
            }
            else
            dp[i][j]=dp[i-1][j];
        }
    }
    for(i=100000;i>=0;i--)
    {
        if(dp[n][i]!=LLONG_MAX && dp[n][i]<=W)
        {
            cout<<i<<endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 79232
#include<stdio.h>
#define MAX 10000
#define NIL -1
 
struct Node{int p,l,r;};
struct Node T[MAX];
int n;
 
void preParse(int u){
  if(u==NIL)return ;
  printf(" %d",u);
  preParse(T[u].l);
  preParse(T[u].r);
}
 
void inParse(int u){
  if(u==NIL)return ;
  inParse(T[u].l);
  printf(" %d",u);
  inParse(T[u].r);
}
 
void postParse(int u){
  if(u==NIL)return ;
  postParse(T[u].l);
  postParse(T[u].r);
  printf(" %d",u);
}
 
int main(){
  int i,v,l,r,root;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    T[i].p=NIL;
  }
 
  for(i=0;i<n;i++){
    scanf("%d%d%d",&v,&l,&r);
    T[v].l=l;
    T[v].r=r;
    if(l!=NIL)T[l].p=v;
    if(r!=NIL)T[r].p=v;
  }
 
  for(i=0;i<n;i++)if(T[i].p==NIL)root=i;
 
  printf("Preorder\n");
  preParse(root);
  printf("\n");
  printf("Inorder\n");
  inParse(root);
  printf("\n");
  printf("Postorder\n");
  postParse(root);
  printf("\n");
 
  return 0;
}

Measured memory_bytes: 620
n,q = map(int,input().split())
s = input()
c = [0]*n
cnt = 0
for i in range(n-1):
    cs = s[i]+s[i+1]
    if cs == 'AC':
        cnt+=1
        c[i+1]=cnt
    else:
        c[i] = cnt
        c[i+1] = cnt
for i in range(q):
    l,r = map(int,input().split())
    print(c[r-1]-c[l-1])

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

int main(){
    int d[5];
    for(size_t i = 0; i < 5; i++)
    {
        cin >> d[i];
    }

    int k;
    cin >> k;

    for(size_t i = 0; i < 5; i++)
    { 
        bool bk = false;
        for(size_t j = 0; j < 5; j++)
        {
            if (j > i && d[j] - d[i] > k) 
            {
                bk = true;
                break;
            }
        }

        if (bk) 
        {
            cout << ":(" << endl;
            break;
        }
        else if (i==4) 
        {
            cout << "Yay!" << endl;
        }       
    }
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(),(c).end()
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define iter(c) __typeof((c).begin())
#define tr(it,c) for(iter(c) it=(c).begin(); it!=(c).end(); it++)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define pr(a) cout << (a) << endl
typedef long long ll;
typedef pair<int,int> P;
const int MAX=1000000000;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int main() {
  vector<vector<int> > v;
  string s;
  int d=0;
  while(cin >> s) {
    s+=',';
    int a=0;
    vector<int> w;
    for(int i=0; i<s.size(); i++) {
      if(s[i]==',') {
	w.pb(a);
	a=0;
      } else {
	a*=10;
	a+=(int)s[i]-'0';
      }
    }
    v.pb(w);
    d=max(d,(int)w.size());
  }
  int dp[v.size()][d];
  memset(dp,0,sizeof(dp));
  dp[0][0]=v[0][0];
  for(int i=0; i<v.size()-1; i++) {
    for(int j=0; j<v[i].size(); j++) {
      if(i<v.size()/2) {
	dp[i+1][j]=max(dp[i+1][j],dp[i][j]+v[i+1][j]);
	dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+v[i+1][j+1]);
      } else {
	if(j-1>=0) dp[i+1][j-1]=max(dp[i+1][j-1],dp[i][j]+v[i+1][j-1]);
	if(j<v[i+1].size()) dp[i+1][j]=max(dp[i+1][j],dp[i][j]+v[i+1][j]);
      }
    }
  }
  pr(dp[v.size()-1][0]);
  return 0;
}


Measured memory_bytes: 1252
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  var n = sc.nextInt

  var ans = 0
  while (ans == 0) {
    if(isPrime(n))ans = n
    n += 1
  }
  println(ans)

  def isPrime(x: Int): Boolean = {
    var result = true
    if(x > 1) {
      for(i <- 2 until x) {
        if(x % i == 0) {
          result = false
        }
      }
    }else {
      result = false
    }
    result
  }
}


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

/** defines and macros */
#define ll long long
#define ull unsigned long long
#define loop(n) for(int i = 0; i < n; i++)
#define loop1(n) for(int i = 1; i <= n; i++)
#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pii>
#define vvi vector<vi>
#define vvpii vector<vii>
#define PB push_back

#define fw(fileName) freopen(fileName, "w", stdout)
#define fr(fileName) freopen(fileName, "r", stdin)
#define fc(stream) fclose(stream);

#define faster_IO_stream ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"

/*To compile and run

	g++ -o main main.cpp && ./main

*/

/*
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⢀⣀⣤⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣶⣤⣀⡀⠄⠄⠄⠄⠄⣰⣷⡀⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⠄⠄⣀⣀⣀⠄⠄⠄⠄⠄⣠⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣄⠄⠄⢠⣿⣿⣷⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠤⠒⠛⠛⠛⠛⠻⠷⣦⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⣿⣿⣿⠟⠁⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⢀⣤⣤⣶⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣡⡤⠐⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⢀⣶⣿⣿⠿⢛⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠁⠄⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⢠⣿⠟⠉⢀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠄⠄⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠘⠁⠄⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠻⣿⣿⣿⣿⣿⣿⣿⡛⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠄⠄⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⣾⣿⡿⣽⡿⢹⣿⣿⣟⣿⢻⠇⢀⢹⣿⢿⣿⣿⣿⣿⣿⣦⣙⢿⣿⢷⣈⠻⢿⣟⢿⣿⣿⣿⣿⡇⠄⠄⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⢿⡿⠁⡿⠁⢸⣿⣿⢹⡇⢸⠄⠈⠄⠻⣏⠻⣿⡿⣿⣿⣿⣌⠛⢿⡌⠙⢧⣀⠙⢳⡹⢻⣿⣿⠁⠄⠄⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⠘⡇⠄⡇⢠⣼⣿⣿⠈⡇⠘⠤⠤⠤⠤⢜⣢⣘⡻⢮⡛⢿⣿⣷⣬⡤⠤⠤⠤⠥⠤⠥⢬⣿⣧⡄⠄⠄⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⠄⠁⠄⠄⠘⢿⡏⠛⠄⠄⠄⠄⠄⠄⠄⠄⠄⠙⣿⣿⣿⡿⠋⠉⠛⠉⠄⠄⠄⠄⠄⠄⠄⢹⡿⠃⠄⠄⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠘⡇⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⡟⠁⠈⢳⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⢸⠁⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠱⡀⠄⠄⠄⠄⠄⠄⠄⠄⠄⡜⠁⠄⠄⠈⢇⠄⠄⠄⠄⠄⠄⠄⠄⠄⢀⡇⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠑⠦⢄⣀⣀⣀⣀⣀⠴⠊⠄⠄⠄⠄⠄⠄⠑⠤⢀⣀⣀⣀⡀⠠⠔⠋⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⢀⣶⣦⣄⠄⠄⠄⠄⠄⠄⠄⠄⠄⢀⣤⣶⣆⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⢸⣿⣿⣿⣿⣶⣄⣀⣀⣀⣀⣤⣾⣿⣿⣿⣿⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⢸⣿⣿⣿⣿⣿⣿⠿⠿⠿⢿⣿⣿⣿⣿⣿⣿⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠘⣿⣿⣿⣿⠟⠁⠄⠄⠄⠄⠙⢿⣿⣿⣿⡟⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠘⠟⠋⠁⠄⠄⠄⠄⠄⠄⠄⠄⠉⠛⠿⠁⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄
 */

int main() {
	faster_IO_stream

	string s;
	cin >> s;

	int res = 0;

	loop(3) if(s[i] == 'R') res++; if(s[1] == 'S' && res == 2) res--;
	cout << res << endl;

	return 0;
}


Measured memory_bytes: 3556
n, m = map(int, input().split())
*C, = map(int, input().split())
# n, m = 15, 6
# C = [1, 2, 7, 8, 12, 50]
# DP[i][j]=i種類以内でj円払う最小枚数
inf = 10**10
DP = [[inf for j in range(n+1)] for i in range(m+1)]
DP[0][0] = 0
for i in range(m):
    for j in range(n+1):
        if j < C[i]:
            DP[i+1][j] = DP[i][j]
        else:
            DP[i+1][j] = min(DP[i][j], DP[i+1][j-C[i]]+1)
print(DP[m][n])



Measured memory_bytes: 43952
#include <iostream>
typedef long long ll;
using namespace std;

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

  ll n, m; cin >> n >> m;
  if(n < m) swap(n, m);
  ll ans;
  if(n == 1 && m == 1) ans = 1;
  else if(m == 1) ans = n-2;
  else ans = (n-2)*(m-2);

  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    string s,t;
    bool can=false;
    cin>>s>>t;
    string u=s;
    s+=u;
    //cout<<s<<endl;
    for(int i=0;i<s.size();i++){
        if(s.substr(i,s.size()/2)==t) {cout<<"Yes"<<endl; return 0;}
       // cout<<s.substr(i,s.size()/2)<<endl;
    }
    cout<<"No"<<endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python
# coding: utf-8

# In[5]:


import math
from functools import reduce


# In[19]:


N = int(input())
a = list(map(int, input().split()))


# In[20]:


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

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


# In[21]:


f = 0
m = lcm_list(a)-1
for i in range(N):
    f += m%a[i]
print(f)


# In[ ]:






Measured memory_bytes: 9596
#include "bits/stdc++.h"
using namespace std;

#define ASC(vec) vec.begin(), vec.end()		// 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend()	// 降順ソート 例:sort(DESC(vec));
#define rep(i, n) for(i = 0; i < n; i++)

const int inf = (int)1e9 + 7;
const long long INF = 1LL << 60;

typedef long long ll;

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 N;
ll h[100010];

// DP テーブル
ll dp[100010];
*/

int main()
{
	int A, B; cin >> A >> B;
	if (A == B) cout << A * 2 << endl;
	else
	{
		cout << max(A, B) + (max(A, B) - 1) << endl;
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	cin>>s;
	int n,i,x=0;
	n=s.size();
	if(s[0]!='A' || s[1]=='C'|| s[n-1]=='C')
	{
		cout<<"WA"<<endl;
		return 0;
	}
	for(i=1;i<n;i++)
	{
		int a;
		a=s[i]-0;
		if(s[i]=='C')
		{
			x++;
		}
		else if(a<96)
		{
			cout<<"WA"<<endl;
		    return 0;
		}
		
		
		if(x>=2)
		{
			cout<<"WA"<<endl;
		    return 0;
		} 
		
	}
	if(x==1)
	{
		cout<<"AC"<<endl;
	}
	else
	{
		cout<<"WA"<<endl;
	}
	
}

Measured memory_bytes: 3620
#include<iostream>

using namespace std;

int main(){
int n;
cin>>n;
int arr[n];
int max=0;
for(int i=0;i<n;i++){
cin>>arr[i];
if(arr[i]>arr[max]){
max=i;}}
int sum=0;
for(int i=0;i<n;i++){
if(i==max){
sum=sum+(arr[max]/2);}
else{
sum=sum+arr[i];}}
cout<<sum;
return 0;}

Measured memory_bytes: 256
s = [ str( input() ) for x in range(3) ]
flag = 0
t = 0
while flag == 0 :
   if len( s[t] ) != 0 : 
      tnext = s[t][0]
      s[t] = s[t][1:]
      t = ord( tnext ) - ord( "a" )
   else :
      flag = 1
      print( chr( ord("A")+ t ) )

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

using namespace std;
typedef long long ll;

string S;
int cnt[30];
int st[30],idx[30];
int w[200005];
int a[200005],b[200005];
ll ans;
vector<int> v[30];

int N=262146;
int bit[262146];

ll sum(int i){
  ll ret=0;
  while(i){
    ret+=bit[i];
    i-=(i&-i);
  }
  return ret;
}

void ad(int i,int x){
  while(i<=S.size()){
    bit[i]+=x;
    i+=(i&-i);
  }
}

int main() {

cin.tie(0);
ios::sync_with_stdio(false);

cin>>S; int n=S.size();

for(int i=0; i<n; i++){
  int s=S[i]-'a';
  cnt[s]++;
}

int odd=0; 
for(int i=0; i<26; i++){
  if(cnt[i]%2) odd++;
}

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

for (int i = 0; i<n; ++i){
  int s=S[i]-'a';
  if(cnt[s]%2==0){
    if(st[s]<cnt[s]/2){
      st[s]++;
      w[i]=0;
    }else{
      w[i]=2;
    }
  }
  if(cnt[s]%2){
    if(st[s]<cnt[s]/2){
      st[s]++;
      w[i]=0;
    }
    else if(st[s]==cnt[s]/2){
      st[s]++;
      w[i]=1;
    }
    else{
      w[i]=2;
    }
  }
}

int j=0;
for (int i=0; i<n; ++i){
  int s=S[i]-'a';
  if(w[i]==0){
    a[j]=s;
    a[n-1-j]=s;
    j++;
  }
}
for (int i=0; i<n; ++i){
  int s=S[i]-'a';
  if(w[i]==1){
    a[j]=s;
    j++;
  }
}

for (int i=0; i<n; ++i){
  v[a[i]].push_back(i);
}

for(int i=0; i<n; ++i){
  int s=S[i]-'a';
  b[i]=v[s][idx[s]]+1;
  idx[s]++;
}

for(int i=0; i<n; i++){
  ans+=(i-sum(b[i]));
  ad(b[i],1);
}

cout<<ans<<endl;

}


Measured memory_bytes: 4880
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <sstream>

using namespace std;

int H, W;
string field[30];

bool check(int y, int x){
	if(y < 0 || y >= H || x < 0 || x >= W){
		return false;
	}
	return true;
}

void shoot(int y, int x, char dir){
	while(true){
		if(dir == '^'){
			y--;
		}else if(dir == 'v'){
			y++;
		}else if(dir == '<'){
			x--;
		}else if(dir == '>'){
			x++;
		}
		if(!check(y, x)){
			break;
		}
		if(field[y][x] == '*'){
			field[y][x] = '.';
			break;
		}
		if(field[y][x] == '#'){
			break;
		}
	}
}

int main(){
	
	int T;
	cin >> T;
	
	for(int loop = 0; loop < T; loop++){
		
		if(loop != 0){
			cout << endl;
		}
		
		cin >> H >> W;
		
		for(int i = 0; i < H; i++){
			cin >> field[i];
		}
		
		char dir;
		int pos_x, pos_y;
		
		for(int i = 0; i < H; i++){
			for(int j = 0; j < W; j++){
				if(field[i][j] == '^' || field[i][j] == 'v' || field[i][j] == '<' || field[i][j] == '>'){
					dir = field[i][j];
					pos_y = i;
					pos_x = j;
				}
			}
		}
		
		
		int hoge;
		cin >> hoge;
		
		string ord;
		
		cin >> ord;
		
		for(int i = 0; i < hoge; i++){
			if(ord[i] == 'U'){
				dir = '^';
				if(check(pos_y - 1, pos_x)){
					if(field[pos_y - 1][pos_x] == '.'){
						field[pos_y][pos_x] = '.';
						pos_y -= 1;
					}
				}
			}
			if(ord[i] == 'D'){
				dir = 'v';
				if(check(pos_y + 1, pos_x)){
					if(field[pos_y + 1][pos_x] == '.'){
						field[pos_y][pos_x] = '.';
						pos_y += 1;
					}
				}
			}
			if(ord[i] == 'L'){
				dir = '<';
				if(check(pos_y, pos_x - 1)){
					if(field[pos_y][pos_x - 1] == '.'){
						field[pos_y][pos_x] = '.';
						pos_x -= 1;
					}
				}
			}
			if(ord[i] == 'R'){
				dir = '>';
				if(check(pos_y, pos_x + 1)){
					if(field[pos_y][pos_x + 1] == '.'){
						field[pos_y][pos_x] = '.';
						pos_x += 1;
					}
				}
			}
			if(ord[i] == 'S'){
				shoot(pos_y, pos_x, dir);
			}
		}
		
		field[pos_y][pos_x] = dir;
		
		for(int i = 0; i < H; i++){
			cout << field[i] << endl;
		}
		
	}
	
	return 0;
}

Measured memory_bytes: 3152
#include<bits/stdc++.h>
using namespace std;
template<class T> void chmax(T&x, T y){if(x < y) x = y;} 
int N, K;
vector<int> G[100010];
int ans;

int dfs(int v, int p){
    int mx = 0;
    for(auto u : G[v]){
        chmax(mx, dfs(u, v));
    }
    if(mx == K - 1 && p > 1) mx = -1, ans++;
    return mx + 1;
}

int main(){
    cin >> N >> K;
    for(int i = 1; i <= N; i++){
        int p;
        cin >> p;
        if(i == 1) ans += (p == 1 ? 0 : 1);
        else G[p].push_back(i);
    }
    dfs(1, 0);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 10368
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]


    X,Y = LMIIS()
    MOD = 10**9 + 7



    # def cmb(n,r):  #nCr = n!/(n-r)!r!
    #     retVal = 1
    #     for i in range(n-r+1,n+1):
    #         retVal *= i
    #         retVal %= MOD
    #     div = 1
    #     for i in range(2,r+1):
    #         div *= i
    #         div %= MOD
    #     return retVal // div

    def cmb(n, r, mod):
        if ( r<0 or r>n ):
            return 0
        r = min(r, n-r)
        return g1[n] * g2[r] * g2[n-r] % mod

    mod = 10**9+7 #出力の制限
    N = 10**6
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル

    for i in range( 2, N + 1 ):
        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )



    if (X+Y) % 3 != 0:
        print(0)
    else:
        level = (X+Y) // 3 
        diff = level * 2 - X
        print(cmb(level,diff,mod))












if __name__ == '__main__':
    main()

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

using namespace std;
const int maxn = 1e5 + 5;
int n, m;
vector<int> adj[maxn];
vector<bool> visited(maxn, false);
int par[maxn], parents[maxn];
queue<int> q;

int main()
{
    int a, b;
    cin >> n >> m;
    for(int i = 0; i < n + m - 1; i++)
    {
        cin >> a >> b;
        adj[a].push_back(b);
        parents[b]++;
    }
    int root;
    for(int i = 1; i <= n; i++)
    {
        if (parents[i] == 0)
        {
            root = i;
        }
    }
    q.push(root);
    visited[root] = 1;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(auto elem : adj[u])
        {
            parents[elem]--;
            if (parents[elem] == 0)
            {
                par[elem] = u;
                q.push(elem);
            }
        }
    }
    par[root] = 0;
    for(int i = 1; i <= n; i++)
    {
        cout << par[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 7040
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
using namespace std;
const int inf=2147483647,dx[]={-1,0,1,0},dy[]={0,-1,0,1};// 上 左 下 右
const int N=100005,M=1000005,mod=1000000007;
const long long llinf=9223372036854775807ll;
int n,c,k,ans;
pair<long long,long long> t[N];
bool ok[N];
int main(){
	cin>>n>>c>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>t[i].first;
		t[i].second=t[i].first+k;
	}
	sort(t+1,t+1+n);
	for(int i=1;i<=n;i++)
	{
		if(ok[i])
			continue;
		ans++;
		for(int j=1;j<=c;j++)
		{
			int num=i+j-1;
			if(t[num].first<=t[i].second)
				ok[num]=true;
			else
				break;
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 1920
def make(n, A, M):
    if n == 0:
        A_list.append(A)
        return
    for i in range(A[-1], M+1):
        make(n-1, A+[i], M)

n, M, q = map(int, input().split())
A_list = []
for i in range(1, M+1):
    make(n, [i], M)
# print(A_list)

abcd = [list(map(int, input().split())) for _ in range(q)]
ans = 0
for i in A_list:
    tmp = 0
    for a,b,c,d in abcd:
        if i[b] - i[a] == c:
            tmp += d
    ans = max(ans, tmp)

print(ans)

Measured memory_bytes: 36808
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>
#include <map>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iterator>
#include <deque>
#include <bitset>
#include <list>
#include <queue>
#include <set>
#include <stack>
#include <functional>
#include <iterator>
#include <locale>
#include <memory>
#include <stdexcept>
#include <utility>
#include <fstream>
#include <ios>
#include <iosfwd>
#include <iomanip>
#include <istream>
#include <sstream>
#include <streambuf>
#include <complex>
#include <numeric>
#include <valarray>
#include <exception>
#include <limits>
#include <new>
#include <typeinfo>
#include <bitset>
#include <queue>
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

using namespace std;

int main() {
	long long a, b, c, ans = 0;
	cin >> a >> b >> c;
	ans = a / b;
	if (a % b != 0) {
		ans += 1;
	}
	cout << ans*c;
}

Measured memory_bytes: 3168
N = int(input())

A = [0] + [n for n in map(int, input().split())]

for i in range(N):
    A[i+1] += A[i]

A.sort()
ans = 0

cnt_list = []
temp = A[0]
cnt = 0

for i in range(N+1):
    if temp == A[i]:
        cnt += 1
    else:
        cnt_list.append(cnt)
        cnt = 1
        temp = A[i]
else:
    cnt_list.append(cnt)
for x in cnt_list:
    if x > 1:
        ans += x*(x-1) / 2

print(int(ans))


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

void quicksort(int *A, int p, int r);
int partition(int *A, int p, int r);
void swap(int *x, int *y);

int main(void)
{
    int Data[50];
    int N, K;
    int H[300000];
    int i, j;
    int max;
    int ij;
    long int sum;

    cin >> N >> K;

    for (i = 0; i < N; i++)
    {
        cin >> H[i];
    }

    quicksort(H, 0, N - 1);

    for (i = 0, sum = 0; i <= N - K - 1; i++)
    {
        sum += H[i];
    }

    cout << sum << endl;

    return 0;
}

void swap(int *x, int *y)
{
    int tmp;
    tmp = *x;
    *x = *y;
    *y = tmp;
}

void quicksort(int *A, int p, int r)
{
    int q;
    if (p < r)
    {
        q = partition(A, p, r);
        quicksort(A, p, q);
        quicksort(A, q + 1, r);
    }
}

int partition(int *A, int p, int r)
{
    int i, j, x, q;

    x = A[p];
    i = p;
    j = r;

    while (i < j)
    {
        while (A[j] > x)
        {
            j--;
        }

        while (A[i] < x)
        {
            i++;
        }

        if (i < j)
        {
            swap(&A[i], &A[j]);
            j--;
            i++;
        }
    }

    if (i == j && A[j] > x)
    {
        j = j - 1;
    }

    q = j;

    return q;
}


Measured memory_bytes: 1024
import sys
n=int(input())

l=[list(map(int,input().split())) for i in range(n)]
l.sort(key=lambda x:-x[2])

for cx in range(101):
  for cy in range(101):
    for i in range(n):
      x,y,h=l[i]
      b=h+abs(x-cx)+abs(y-cy)
      if i==0:
        if h:
          s=set()
          s.add(b)
        else:
          s={i for i in range(b+1)}
      else:
        if not s:break
        if h:
          s&=set([b])
        else:
          s&=set(range(b+1))
    if s:
      print(cx,cy,s.pop())
      sys.exit()


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

#define fast_cin() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX 1000000
#define ll long long
#define db double
#define pb push_back
#define For(i,s,e) for (ll i=(s); i<(e); i++)
#define Debug_array(a,n) for (ll i=(0); i<(n); i++) cout<<a[i]<<" "
#define Foe(i,s,e) for (ll i=(s); i<=(e); i++)
#define Fod(i,s,e) for (ll i=(s)-1; i>=(e); i--)
#define str string
#define vl vector<ll>
#define vs vector<string>

#define mapll map<ll,ll>
#define mapss map<string,string>
#define mapsl map<string,ll>
#define mapls map<ll,string>

#define pll pair<ll,ll>
#define pss pair<string,string>
#define psl pair<ll,string>
#define pls pair<string,ll>

#define minheap priority_queue<ll>
#define maxheap priority_queue<ll,vector<ll> ,greater<ll>>

#define fi first
#define se second
#define endl "\n"
#define mp make_pair
#define big_prime 15486277
#define bigger_prime 179424697
#define biggest_prime 32416188691
const ll mod=1e9 + 7;


ll takemod(ll a) {
    return ((a%mod)+mod)%mod;
}

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

ll fast_exp(ll base, ll expo) {
    ll res=1;
    while(expo>0) {
        if(expo&1) res=(res*base)%mod;
        base=(base*base)%mod;
        expo>>=1;}
    return res;
}

ll modinv(ll a) {
    return takemod(fast_exp(takemod(a), mod-2));
}
ll dp[100000][3];
ll arr[100000][3];
void dpfunc(ll index, ll n, ll k)
{
    // For(i,0,n)
    // {
    //     cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2];
    //     cout<<endl;
    // }
    if(index==n-1)
    {
        dp[index][k]=arr[index][k];
        return;
    }
    else
    {
        if(k==0)
        {
            if(dp[index+1][1]==-1)
                dpfunc(index+1,n,1);
            if(dp[index+1][2]==-1)
                dpfunc(index+1,n,2);
            dp[index][k]=arr[index][k]+max(dp[index+1][1],dp[index+1][2]);
        }
        else if(k==1)
        {
            if(dp[index+1][0]==-1)
                dpfunc(index+1,n,0);
            if(dp[index+1][2]==-1)
                dpfunc(index+1,n,2);
            dp[index][k]=arr[index][k]+max(dp[index+1][0],dp[index+1][2]);
        }
        else
        {
            if(dp[index+1][1]==-1)
                dpfunc(index+1,n,1);
            if(dp[index+1][0]==-1)
                dpfunc(index+1,n,0);
            dp[index][k]=arr[index][k]+max(dp[index+1][1],dp[index+1][0]);
        }    
    }
    return;
}
signed main() 
{
    fast_cin();
    ll n;
    cin>>n;
    For(i,0,n)
    {
        cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
    }
    memset(dp,-1,sizeof(dp));
    For(i,0,3)
    {
        dpfunc(0,n,i);
    }
    

    cout<<max(max(dp[0][0],dp[0][1]),dp[0][2])<<endl;
    return 0;
}

Measured memory_bytes: 9600
n, m, k = map(int, input().split())
mod =998244353

def cmb1(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 998244353 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

ans = 0
for x in range(k+1):
    temp = cmb1(n-1, x, mod)
    temp *= m*power(m-1, n-1-x, mod)
    ans += temp
print(ans%mod)


Measured memory_bytes: 168056
r, c = gets.split(" ").map(&:to_i)
array = Array.new(r).map{ Array.new(c) }

for i in 0..(r - 1)
  array[i] = gets.split(" ").map(&:to_i)
  array[i].push(array[i].inject(:+))
end

array = array.transpose

for i in 0..c
  array[i].push(array[i].inject(:+))
end

for i in 0..r
  puts array.transpose[i].to_s.gsub(/[\[\]\,]/, "")
end

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

#define INF 1000000000

void seikei(char *a, char *b) //aの先頭にある0を削除してbにcopy
{
    int i;
    int n = strlen(a);
    int p = 0;
    for (i = 0; i < n; i++)
    {
        if (a[i] != '0')
        {
            p = i;
            break;
        }
    }
    strncpy(b, a + p, n - p);
    b[n - p] = '\0';
}

void Lplus(char *a, char *b, int L)
{
    strcpy(b, a);
    int add = L - (int)strlen(a);
    int i;
    for (i = 0; i < add; i++)
    {
        strcat(b, "0");
    }
}

int syojyun(const void *a, const void *b)
{
    return *(char *)a - *(char *)b;
}

int koujyun(const void *a, const void *b)
{
    return *(char *)b - *(char *)a;
}

int main(void)
{
    char a[100];
    int L;
    while (scanf("%s %d", a, &L) != EOF)
    {
        if (strcmp(a, "0") == 0 && L == 0)
        {
            return 0;
        }
        int record[1 << 10];
        int i = 1;
        record[0] = atoi(a);
        int ans_i, ans_j;
        int ans;
        int status = 0;
        while (1)
        {
            if (status != 0)
            {
                break;
            }
            char big[100];
            char tmp[100];
            char small[100];
            Lplus(a, big, L);
            Lplus(a, tmp, L);
            qsort(big, L, sizeof(char), koujyun);
            qsort(tmp, L, sizeof(char), syojyun);
            seikei(tmp, small);
            // printf("big:%s\n", big);
            // printf("small:%s\n", small);
            record[i] = atoi(big) - atoi(small);

            sprintf(a, "%d", record[i]);

            int j, k;
            for (j = 0; j <= i; j++)
            {
                for (k = j + 1; k <= i; k++)
                {
                    if (record[j] == record[k])
                    {
                        ans = record[j];
                        ans_j = j;
                        ans_i = k;
                        status = 1;
                    }
                }
            }
            i++;
        }
        printf("%d %d %d\n", ans_j, ans, ans_i - ans_j);
    }
    return 0;
}


Measured memory_bytes: 2052
s = input()
t = input()

min = len(t)
for i in range(len(s) - len(t) + 1):
  a = 0
  for j in range(len(t)):
    if(s[i+j] != t[j]):
      a += 1
      if(a >= min):
        break
  if(a < min):
    min = a
print(min)


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

public class Main {
	    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int size = in.nextInt();
        ArrayList<Long> list = new ArrayList<Long>();
        for (int x = 0; x < size; x++){
        	list.add(in.nextLong());
        }
        
        long minimum = 2;
        long counter = list.get(0) - 1;
    	for (int x = 1; x < size; x++){
    		long num = list.get(x);
			
			if (num % minimum == 0){
				counter += (num / minimum) - 1;			
				list.set(x, minimum);
			} else {
				counter += (num / minimum);
				list.set(x, list.get(x) % minimum);
			}
		
    		
    		if (list.get(x) - minimum == 0 && num == minimum) {    			
    			minimum++;
    		}
    			
    	}
                
        System.out.println(counter);
        in.close();
    }
}


Measured memory_bytes: 49016
#include <bits/stdc++.h>
 
#define int         long long
#define uint        unsigned int
#define ld          long double
#define showoff     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          push_back
#define pii         pair<int,int>
#define FOR(i,a,b)  for(int i=a;i<b;++i)
#define RFOR(i,a,b) for(int i=a;i>b;--i)
#define f           first
#define se          second
#define maxn        200005
#define all(v)      v.begin(),v.end()
#define sz(x)       (int)x.size()
#define mod         1000000007
#define pqueue      priority_queue<int>
#define pdqueue     priority_queue< int,vector<int> ,greater< int >>
 
using namespace std;
 
 
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
 
int power(int a,int n)
{
    a %= mod;
    if(n == 1)return a;
    if(n == 0)return 1;
    if(n%2)return (a*(power((a*a)%mod,n/2)%mod))%mod;
    return power((a*a)%mod,n/2)%mod;
}
const int inf = (int) 1e18;
 
int inverse(int x){
    return power(x,mod-2)%mod;//little fermat....
}    


signed main()
{
    showoff;
   	int a,b;
   	cin >> a >> b;
   	cout << (a*b)/__gcd(a,b);
    return 0;
}
//*->for large size of matrix take int not long long if possible......
//*->always take maximum as inf for safer side ...#include <bits/stdc++.h>
 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

int cnt[510][510];
int N,M,Q;

int main(){
    cin>>N>>M>>Q;
    rep(i,M){
        int L,R;
        cin>>L>>R;
        cnt[L][R]++;
    }
    for(int L=1;L<N+1;L++){
        for(int R=2;R<N+1;R++){
            cnt[L][R]+=cnt[L][R-1];
        }
    }

    while(Q--){
        int p,q;
        cin>>p>>q;
        int ans=0;
        for(int L=p;L<q+1;L++) ans+=cnt[L][q];
        cout<<ans<<endl;
    }
}


 

Measured memory_bytes: 1920