akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
// statics
using namespace std;
using int64 = int_fast64_t;
using PAIR = pair<int64, int64>;
constexpr int INF = 1 << 30;
constexpr int64 LINF = 1LL << 60;
constexpr int MOD = 1e9 + 7;
constexpr int MAX_N = 3e5 + 1;

// init/input
#define int int64
#define INIT ios::sync_with_stdio(false);cin.tie(0);
#define VAR(type, ...) type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T &t) {cin>>t;}
template<typename First, typename...Rest> void MACRO_VAR_Scan(First &first, Rest&...rest) {cin>>first;MACRO_VAR_Scan(rest...);}
#define VEC(type, c, n) vector<type> c(n);for(auto &&i:c)cin>>i;

// out
#define OUT(dist) cout<<(dist);
#define FOUT(n, dist) cout<<fixed<<setprecision(n)<<(dist);
#define SP cout<<" ";
#define BR cout<<endl;
#define zero(n) cout<<setfill('0')<<right<<setw(n)
#define debug(x) cerr<<#x<<":"<< (x);BR;

// utility
#define ALL(a) (a).begin(), (a).end()
#define EACH(i, a) for(auto &&i:(a))
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=0;--i)
#define REP(i, n) for(int i=0;i<(n);++i)
#define RREP(i, n) for(int i=(n)-1;i>=0;--i)

int fact[MAX_N];
int ifact[MAX_N];

int power(int x, int n) {
	int res = 1LL;
	while (n > 0) {
		if (n & 1) (res *= x) %= MOD;
		(x *= x) %= MOD;
		n >>= 1;
	}
	return res % MOD;
}

int inv(int x) {
	return power(x, MOD - 2);
}

int nCr(int n, int r) {
	if (n < 0 || r < 0 || r > n) return 0;
	if (r > n / 2) r = n - r;
	return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
}

void init_fact() {
  fact[0] = ifact[0] = 1;
	for (int i=1; i<MAX_N; ++i) {
		(fact[i] = fact[i - 1] * i) %= MOD;
		ifact[i] = inv(fact[i]);
	}
}

struct Eratosthenes {
  vector< bool > prime;
  Eratosthenes(int _size) {
    init(_size);
  }

  void init(int n) {
    prime.resize(n + 1);
    for(int i = 0; i < prime.size(); ++i) prime[i] = true;
    prime[0] = prime[1] = false;
    for(int i = 2; i*i < n; i++) {
      if (prime[i]) {
        for (int j = 0; i * (j + 2) < n; j++) {
					prime[i * (j + 2)] = false;
				}
      }
    }
  }

	map< int, int > prime_factorize(int n) {
		map< int, int > res;
		for (int i=2; i*i<=n; ++i) {
			if (!prime[i]) continue;
			if (n % i != 0) continue;
			int num = 0;
			while (n % i == 0) {
				res[i]++;  n /= i;
			}
		}
		if (n != 1) res[n]++;
		return res;
	}
};

signed main() {
  INIT;
	init_fact();
	VAR(int, n, m);

	Eratosthenes e(MAX_N);
	map< int, int > mp = e.prime_factorize(m);

	int ans = 1;
	EACH(mi, mp) {
		(ans *= nCr(mi.second + n - 1, n - 1)) %= MOD;
	}

	OUT(ans)BR;
  return 0;
}




Measured memory_bytes: 4992
#include "bits/stdc++.h"
#define YES "YES"
#define NO "NO"
#define Yes "Yes"
#define No "No"
#define DEFAULT LL ans=solve();\
 	if(ans==NONE){\
 	}else{\
 		cout << ans << endl;\
 	}
#define YESNO three(solve(),(OUT(YES),1),(OUT(NO),0))
#define YesNo three(solve(),OUT(Yes),OUT(No))
#define ECHO OUT(solve())
#define three(A,B,C) ((A)?(B):(C))
#define FOR(i,a,b)  for(LL i=(a);i< (LL)(b);i++)
#define EFOR(i,a,b) for(LL i=(a);i<=(LL)(b);i++)
#define RFOR(i,a,b) for(LL i=(b-1);i>=(LL)(a);i--)
#define REP(i,b) FOR(i,zero,b)
#define rep REP
#define EREP(i,b) EFOR(i,zero,b)
#define RREP(i,b) RFOR(i,zero,b)
#define ALL(c) c.begin(),c.end()
#define UNIQUE(c) sort(ALL(c));c.erase(unique(ALL(c)),c.end())
#define MAX(c) (*max_element(ALL(c)))
#define MIN(c) (*min_element(ALL(c)))
#define MP make_pair
#define FI first
#define SE second
#define SI(x) (LL(x.size()))
#define PB push_back
#define DEBUG(a) OUT(a)
#define DEBUG2(a,b) OUT2(a,b)
#define cat cout << __LINE__ << endl
#define OUT(a) cout << (a) << endl
#define OUT2(a,b) cout << (a) <<" "<<(b) << endl
#define zero 0LL
#define all ALL
#define pb emplace_back
#define eb pb
#define int long long
using namespace std;
template<typename T> inline void maximize(T &a, T b) { a = max(a, b); }
template<typename T> inline void minimize(T &a, T b) { a = min(a, b); }
template<typename T> inline bool middle(T a, T b, T c) { return b <= a && a <= c; }
template<class T> inline bool MX(T &l, const T &r) { return l < r ? l = r, 1 : 0; }
template<class T> inline bool MN(T &l, const T &r) { return l > r ? l = r, 1 : 0; }
typedef int LL;
typedef double ld;
typedef int ut;
typedef vector<ut> VI;
typedef vector<VI> VII;
typedef pair<ut, ut> pr;
typedef pair<ut, pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef tuple<int, int, int, int> tapu;
typedef vector<tapu> Vtapu;
typedef priority_queue<pr, Vpr > PQ;
inline void outputVI(VI x) { REP(i, SI(x)) { cout << three(i, " ", "") << x[i]; }OUT(""); }
const int SIZE1 = 5e5 + 1000;
const int SIZE2 = 5010;
const int SIZE3 = 430;
const int SIZE = SIZE1;
const int MAPSIZE = 40;
const LL p998 = 998244353;
const LL p107 = 1000000007;
const LL p = p107;
const LL INF = 1LL << 60;
const long double EPS = 1e-7;
const LL NONE=-2;
#define endl "\n"
ut N, M,K,  Q, D, H, W;
VI edges[SIZE];
LL vals[SIZE], answer = zero;
//LL A[SIZE],B[SIZE],C[SIZE];
LL solve(){
	string s;
	cin >> s;
	s[0]++;
	cout << s << endl;
	return NONE;
}
 signed main() {
 
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	LL T=1;

	REP(i,T){
		DEFAULT;

	}
	
//	YesNo;
//	YESNO;
//	three(solve(),OUT("First"),OUT("Second"));
	//cin >> N;
	return 0;
 
}


Measured memory_bytes: 13824
#include<bits/stdc++.h>
using namespace std;
int rec(int num,int sum);
int memo[1005][1005];
#define MOD 1000000007
string t,b;
int ans;
int main(){
    cin>>t>>b;
    memset(memo,-1,sizeof(memo));
    cout<<rec(0,0)<<'\n';
    return 0;
}

int rec(int tc,int bc){
    if(memo[tc][bc] != -1)return memo[tc][bc];
    if(bc == b.size())return 1;//bの探索が最後まで
    if(tc == t.size())return 0;//tの探索が最後まで

    if(t[tc]==b[bc]){
        return memo[tc][bc]=(rec(tc+1,bc+1)%MOD+rec(tc+1,bc)%MOD)%MOD;
    }else{
        return memo[tc][bc]=rec(tc+1,bc)%MOD;
    }
}


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

 using namespace std;

 int main() {
   int H, N;
   cin >> H >> N;
   vector<int> A(N);
   int sum = 0;
   string ans = "No";
   for (int i = 0; i < N; i++) {
     cin >> A.at(i);
     sum += A.at(i);
     if (sum >= H) {
       ans = "Yes";
       break;
     }
   }
   cout << ans << endl;
}


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

int main() {
    int N,M;
    cin >> N >> M;
    vector<int> A(N);
    rep(i,N) cin >> A.at(i);
    int sum = accumulate(all(A),0);
    double limit = sum/((double)4*M);
    sort(all(A));
    auto it = lower_bound(all(A), limit);
    //cout << A.end()-it << endl;
    //cout << limit;
    if(A.end()-it<M) cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
typedef struct{
    int num;
    int wa1;
    int wa2;
} data;
int main(){
    int n,i,num,walk;
    while(1){
        scanf("%d",&n);
        if(n == 0){
            break;
        }
        data kanja[n];
        for(i=0;i<n;i++){
            scanf("%d %d %d",&kanja[i].num,&kanja[i].wa1,&kanja[i].wa2);
            if(i == 0){
                num = kanja[i].num;
                walk = kanja[i].wa1 + kanja[i].wa2;
            }
            else if(walk < kanja[i].wa1 + kanja[i].wa2){
                num = kanja[i].num;
                walk = kanja[i].wa1 + kanja[i].wa2;
            }
        }
        printf("%d %d\n",num,walk);
    }
    return (0);
}

Measured memory_bytes: 716
package main
import (
	"fmt"
)
/*
func main() {
	ary := []int{}
	for y := 1; y <= 9; y++ {
		for x := 1; x <= 9; x++ {
			ary = append(ary, x*y)
		}
	}
	s := ""
	for _, a := range ary {
		s += fmt.Sprintf("%d,", a)
	}
	fmt.Println(s)
}
*/

func main() {
	var i int
	fmt.Scanf("%d", &i)
	for _, x := range []int{1,2,3,4,5,6,7,8,9,2,4,6,8,10,12,14,16,18,3,6,9,12,15,18,21,24,27,4,8,12,16,20,24,28,32,36,5,10,15,20,25,30,35,40,45,6,12,18,24,30,36,42,48,54,7,14,21,28,35,42,49,56,63,8,16,24,32,40,48,56,64,72,9,18,27,36,45,54,63,72,81} {
		if i == x {
			fmt.Println("Yes")
			return
		}
	}
	fmt.Println("No")
}



Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using vi = vector<i64>;
using vvi = vector<vi>;

int main() {
    i64 n, p;
    cin >> n >> p;
    map<i64, int> cnt;
    while (p > 1) {
        int ok = 0;
        for (i64 i = 2; i * i <= p; i++) {
            if (p % i == 0) {
                while (p % i == 0) {
                    p /= i;
                    cnt[i]++;
                }
                ok = 1;
                break;
            }
        }
        if (!ok) {
            cnt[p]++;
            p = 1;
        }
    }

    i64 ret = 1;
    for (auto &p : cnt) {
        while (p.second >= n) {
            ret *= p.first;
            p.second -= n;
        }
    }
    cout << ret << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
#define ll long long
#define ull unsigned long long
#define ii pair<int,int>
#define iii pair <int,ii>
#define iil pair<ll,ll>
#define iiil pair<ll,iil>
#define max3(a,b,c) max(a, max(b,c))
#define min3(a,b,c) min(a, min(b,c))
#define s(v) sort(v.begin(),v.end())
#define r(v) reverse(v.begin(),v.end())
#define pf printf
#define sf scanf
#define MIN INT_MIN
#define MAX INT_MAX
#define Accepted 0
#define GCD(x,y)  __gcd(x, y)
#define endl "\n"
#define sz  size()
using namespace std;

const int maxn = 1e6 + 69;
int vis[maxn];
int cnt;
vector<int> graph[maxn];

void DFS(int i){
    cnt++;
    vis [i] = 1;

    for(int j=0;j<graph[i].sz;j++){
        int r = graph[i][j];
            if(!vis[r]){
                DFS(r);
            }
    }
}

void solve(){
    int n,m;    cin >> n >> m;
    int ans = -1;

    while(m--){
        int x,y;
        cin >> x >> y;
        graph[x].pb(y);
        graph[y].pb(x);
    }

    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            cnt = 0;
            DFS(i);
            ans = max(ans,cnt);
        }
    }
        cout << ans << endl;
}


int main(){
    //fast
    //int tst;    cin>>tst;
    //int cs = 1;

    //while(tst--){
    //  cout << "Case "<<cs++<<": ";
        solve();
    //}


    return Accepted;
}


Measured memory_bytes: 43340
#include<bits/stdc++.h>
using namespace std;
#define intt long long int
#define intu unsigned long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
//#define mp make_pair
#define ff first
#define ss second
#define fast_io ios::sync_with_stdio(0);cin.tie(NULL);std::cout.tie(NULL);
# define PI           3.14159265358979323846 
#define all(a) a.begin(),a.end()
#define for0(i, n) for (int i = 0; i < n; i++)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define loop(i,a,b) for (int i = a; i < b; i++)
#define bloop(i,a,b) for (int i = a ; i>=b;i--)
#define tc(t) int t; cin >> t; while (t--)
int mod = 1000000007;
intt gcd(intt a, intt b) {return b ? gcd(b, a % b) : a;}
intt lcm(intt a, intt b) {return a * b / gcd(a, b); }
intt bpow(intt a,intt b) 
{
  intt res = 1;
  while (b > 0) {
    if (b & 1)res = ((res%mod) * (a%mod))%mod;
      a = ((a%mod) * (a%mod))%mod;
      b >>= 1;
  }
  return res;
}
intt fact(intt n) { 
   if ((n==0)||(n==1))
      return 1; 
   else
      return n*fact(n-1);
}
void go()
{
#ifndef ONLINE_JUDGE
  freopen("inn.txt","r",stdin);
  freopen("o.txt","w",stdout);
  #endif
}
///////////U L R D
int dx[4]={0,-1,1,0};
int dy[4]={1,0,0,-1};

template <typename T1, typename T2>
struct less_second {
    typedef pair<T1, T2> type;
    bool operator ()(type const& a, type const& b) const {
        return a.second > b.second;
    }
};

int solve(vi v,int k)
{
  int n=v.size();
  vi ans(n,INT_MAX);
  ans[0]=0;
  
  for(int i=0;i<n;i++)
  {
    for(int j=i+1;j<i+k+1 && j<n;j++)
    {
       ans[j]=min(ans[j],ans[i]+abs(v[i]-v[j]));   
    }
  }
  return ans[n-1];
}

int main()
{
  go();
  fast_io
  int n,k;cin>>n>>k;
  vi v(n);
  for0(i,n)
  {
    cin>>v[i];
  }
  int ans=0;
  ans=solve(v,k);
  cout << ans <<"\n";
}



/*

arr : 0 20 min(30,50)

*/










Measured memory_bytes: 4520
#include<bits/stdc++.h>
using namespace std;
int n,k,a[550],b[550],sum,ans=1;
bool solve(int x)
{
	int tot=0,ad=0;
	for(int i=1;i<=n;i++)
	{
		int rr=a[i]/x;
		b[i]=a[i]-rr*x;
		tot+=b[i];
		ad+=rr;
	}
	int nd=sum/x-ad;
	sort(b+1,b+n+1);
	for(int i=n;i>n-nd;i--)
	tot+=x-2*b[i];
	return tot/2<=k;
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum+=a[i];
	int sss=sqrt(sum);
	for(int i=1;i<=sss;i++)
	{
		if(sum%i!=0)continue;
		if(sum/i>ans)if(solve(sum/i))ans=sum/i;
		if(i>ans)if(solve(i))ans=i;
	}
	cout<<ans;
}

Measured memory_bytes: 256
import java.util.*;

class Main {
        public static void main(String args[]) {
                try (Scanner sc = new Scanner(System.in)) {
                        String S = sc.next();
                        boolean f = true;
                        for (int i = 0; i <= (S.length()-1) / 2; i++) {
                                switch (S.charAt(i)) {
                                        case 'b':{
                                                if (S.charAt(S.length() - i - 1) != 'd') {
                                                        f = false;
                                                }
                                                break;
                                        }
                                        case 'd':{
                                                if (S.charAt(S.length() - i - 1) != 'b') {
                                                        f = false;
                                                }
                                                break;
                                        }
                                        case 'q':{
                                                if (S.charAt(S.length() - i - 1) != 'p') {
                                                        f = false;
                                                }
                                                break;
                                        }
                                        case 'p':{
                                                if (S.charAt(S.length() - i - 1) != 'q') {
                                                        f = false;
                                                }
                                                break;
                                        }
                                }
                        }
                        if (f) {
                                System.out.println("Yes");
                        } else {
                                System.out.println("No");
                        }
                }
        }
}

Measured memory_bytes: 13852
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b;
	scanf("%d%d",&a,&b);
	if(a==1)
	   a=14;
	if(b==1)
	   b=14;   
	if(a>b)
	   printf("Alice");
	if(a<b)
	   printf("Bob");
	if(a==b)
	   printf("Draw");
	return 0;   
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define fr(i,a,b) for(ll i=a; i<b; i++)
#define fr1(i,a,b) for(ll i=a; i>=b; i--)
#define ll long long int
#define ld long double
#define vi vector<ll>
#define vii vector <pair<ll,ll> >
#define viii vector <pair<ll,pair<ll,ll> > >
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define mp(i,j) make_pair(i,j)
#define fi first
#define se second
#define input(a,n) fr(i,0,n)cin>>a[i]
#define output(a,n) fr(i,0,n)cout<<a[i]<<endl
#define dbg cout<<"hurr"<<endl;
#define dbg2 cout<<"hurr2"<<endl;
#define md 1000000007
#define inf 999999999999999999
#define sp << " " <<
#define endl "\n"
#define pi 3.14159265358979323846
#define fixd(x) cout << fixed << setprecision(x);
#define sz size()
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
bool compare(pair<pair<ll,ll>,ll> p1,pair<pair<ll,ll>,ll>p2){
return p1.fi.fi<p2.fi.fi;
}
void solve(){
 ll a;
 cin>>a;
 cout<<a+(a*a)+(a*a*a)<<endl;
}
int main()
{   fast;
    ll t=1;
   //cin>>t;
    fr(zz,1,t+1){
    solve();
    }
}


Measured memory_bytes: 3608
#include<stdio.h>
int main(){
	int counta=0,countb=0,countc=0;
	int N;int num[100000];
	scanf("%d",&N);
	for(int i=0;i<N;i++){
		scanf("%d",&num[i]);
		if(num[i]%4==0)
			counta++;
		else if(num[i]%2==0)
			countb++;
		else
			countc++;
	}
	if(counta==countc-1&&counta+countc==N)
		printf("Yes\n");
	else if(counta>=countc)
		printf("Yes\n");
	else
		printf("No\n");
	return 0;
	
}

Measured memory_bytes: 512
import java.util.Scanner;

public class Main {
	public static Scanner sc = new Scanner(System.in);
	public static void main(String[] args){
		int a = sc.nextInt();
		int b = sc.nextInt();
		int dmp = Math.max(a+b, a-b);
		System.out.println(Math.max(dmp,a*b));
	}
}


Measured memory_bytes: 23636
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;

using ll = long long;

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

int main()
{
    int K;
    cin >> K;
    ll ans = 0;
    for (int i = 1; i <= K; i++) {
        for (int j = 1; j <= K; j++) {
            int gcdij = gcd(i, j);
            for (int k = 1; k <= K; k++) {
                ans += gcd(k, gcdij);
            }
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3620
#include <stdio.h>

int main (int argc, const char * argv[]) {
    int moto[30],yoko1[30],yoko2[30],kekka[30];
	int w,n;
	int i=0,l=0,k;
	
	scanf("%d",&w);
	scanf("%d",&n);
	
	for(i=0;i<n;i++){
		scanf("%d,%d",&yoko1[i],&yoko2[i]);
	}
	
	for(i=0;i<w;i++){
		moto[i]=i+1;
		for(l=0;l<n;l++){
			if(moto[i]==yoko1[l]){
				moto[i]=yoko2[l];
			}else if(moto[i]==yoko2[l]){
				moto[i]=yoko1[l];
			}
		}
		k=moto[i]-1;
		kekka[k]=i+1;
	}
	
	for(i=0;i<w;i++){
		printf("%d\n",kekka[i]);
	}
	
				
	
	
    return 0;
}

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

int main() {
  int a,b;
  cin >> a >> b;
  string answer;
  if(a * b % 2 == 0){
    answer = "Even";
  }
  else {
    answer = "Odd";
  }
  
  cout << answer << endl;
  return 0;
}

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

using namespace std;
typedef long long ll;

ll N,mod=(ll)1e9+7;
map<ll, ll>f;

ll rec(ll n){
    if(f[n]) return f[n];
    return f[n]=(rec(n/2)+rec((n-1)/2)+rec((n-2)/2))%mod;
}

int main(void){
    cin>>N;
    f[0]=1; f[1]=2;
    cout<<rec(N)%mod;
    return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<map>
#include <bits/stdc++.h>
#include<cmath>
#define mod 1000000007
#define ll long long 
using namespace std;

int main() {

  ll ans=0;
  string s1,s2;
  cin>>s1>>s2;
  for(ll i=0;i<s1.length();i++)
  {
  	if(s1[i]!=s2[i])
  	{
  		ans++;
	  }
  }
  cout<<ans<<endl;
	return 0;
}

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

using namespace std;


namespace XDYIMCMI0LY {

  const int N = 700 + 5;
  
  int n;
  int m;
  int g[N][N];

  int vis[N];
  int col[N];
  int cnt[2];

  void dfs(int u, int nw) {
    vis[u] = 1;
    col[u] = nw;
    cnt[nw]++;
    for (int i = 1; i <= n; ++i) {
      if (g[u][i] && !vis[i]) {
        dfs(i, nw ^ 1);
      } else if (g[u][i]) {
        if (col[i] == col[u]) {
          puts("-1");
          exit(0);
        }
      }
    }
  }

  bool dp[N][N][N];
  
  int main() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; ++i) {
      cin >> u >> v;
      g[u][v] = g[v][u] = 1;
    }
    for (int i = 1; i <= n; ++i) {
      for (int j = i + 1; j <= n; ++j) {
        g[i][j] ^= 1;
        g[j][i] ^= 1;
      }
    }
    memset(col, -1, sizeof(col));
    vector<pair<int, int> > v;
    v.push_back(make_pair(0, 0));
    for (int i = 1; i <= n; ++i) {
      if (!vis[i]) {
        cnt[0] = cnt[1] = 0;
        dfs(i, 0);
        v.push_back(make_pair(cnt[0], cnt[1]));
      }
    }
    m = n;
    n = v.size();
    dp[0][0][0] = 1;
    for (int i = 1; i < n; ++i) {
      int x = v[i].first;
      int y = v[i].second;
      for (int j = 0; j <= m; ++j) {
        for (int k = 0; k <= m; ++k) {
          if (j - x >= 0 && k - y >= 0) {
            dp[i][j][k] |= dp[i - 1][j - x][k - y];
          }
          if (j - y >= 0 && k - x >= 0) {
            dp[i][j][k] |= dp[i - 1][j - y][k - x];
          }
        }
      }
    }
    int ans = 1e9;
    for (int i = 0; i <= m; ++i) {
      for (int j = 0; j <= m; ++j) {
        if (dp[n - 1][i][j]) {
          ans = min(ans, i * (i - 1) / 2 + j * (j - 1) / 2);
        }
      }
    }
    cout << ans << endl;
    return 0;
    
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  XDYIMCMI0LY::main();
  return 0;
}


Measured memory_bytes: 341888
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll one = 1;
const ll INF = 9223372036854775807; //10^18
const int inINF = 2147483647; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int main(){
    int x;
    cin >> x;
    printf("%d\n", 1-x);
}

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

int main(){
  int H,W;
  cin >> H >> W;
  char a[H][W];
  for (int i=0; i < H; i++){
    cin >> a[i];
  }
  char b[H+2][W+2];
  for (int i=0; i < H+2; i++){
    for (int j=0; j < W+2; j++){
      b[i][j]='#';
    }
  }
  for (int i=0; i < H; i++){
    for (int j=0; j < W; j++){
      b[i+1][j+1] = a[i][j];
    }
  }
  for (int i=0; i < H+2; i++){
    for (int j=0; j < W+2; j++){
      cout << b[i][j];
    }
    cout << endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main() {
#ifndef ONLINE_JUDGE
	freopen("input.in", "r", stdin);
	freopen("out.o", "w", stdout);
#endif

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll x, k, d;
	cin >> x >> k >> d;
	if (x < 0)x = -x;
	if (x / d >= k)cout << x - k*d;
	else {
		ll a = x / d, ans;
		k -= a;
		if (k % 2 == 0) {
			ans = x % d;
		}
		else {
			ans = d - x % d;
		}
		cout << ans;
	}
}

Measured memory_bytes: 3660
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <time.h>
#define int long long
#define endl '\n'
#define INF 1000000000000000000
#define EPS 1e-10
#define all(a) a.begin(),a.end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define fi first
#define se second
#define pb push_back
#define double long double
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
template<class T, class S> bool chmax(T &a, const S &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class S> bool chmin(T &a, const S &b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll n, ll m) { return (m ? gcd(m, n%m) : n); }
ll lcm(ll n, ll m) { return n / gcd(n, m)*m; }

template<class T>
class segtree {
	int n;
	vector<T> data;
	T def;
	function<T(T, T)> operation;
	function<T(T, T)> update;
	T _query(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l) return def;
		if (a <= l && r <= b) return data[k];
		T c1 = _query(a, b, 2 * k + 1, l, (l + r) / 2);
		T c2 = _query(a, b, 2 * k + 2, (l + r) / 2, r);
		return operation(c1, c2);
	}
public:
	segtree(size_t _n, T _def, function<T(T, T)> _operation, function<T(T, T)> _update)
		:def(_def), operation(_operation), update(_update) {
		n = 1;
		while (n < _n) {
			n *= 2;
		}
		data = vector<T>(2 * n - 1, def);
	}
	void change(int i, T x) {
		i += n - 1;
		data[i] = update(data[i], x);
		while (i > 0) {
			i = (i - 1) / 2;
			data[i] = operation(data[i * 2 + 1], data[i * 2 + 2]);
		}
	}
	T query(int a, int b) {
		return _query(a, b, 0, 0, n);
	}
	T operator[](int i) {
		return data[i + n - 1];
	}
};

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	//modcalc();

	int n;
	string s;
	cin >> n >> s;
	vector<segtree<int>> seg(26, segtree<int>(n, 0, [](int a, int b) {return a + b; }, [](int a, int b) {return a + b; }));
	rep(i, n) seg[s[i] - 'a'].change(i, 1);
	int q; cin >> q;
	rep(_, q) {
		int type;
		cin >> type;
		if (type == 1) {
			int m;  char c;
			cin >> m >> c;
			m--;
			seg[c - 'a'].change(m, 1);
			seg[s[m] - 'a'].change(m, -1);
			s[m] = c;
		}
		else if (type == 2) {
			int l, r;
			cin >> l >> r;
			l--; r--;
			int ans = 0;
			rep(i, 26) {
				if (seg[i].query(l, r + 1)) ans++;
			}
			cout << ans << endl;
		}
	}
}

Measured memory_bytes: 222108
N=int(input())
A1=list(map(int,input().split()))
A2=list(map(int,input().split()))

def sumA2(x):
    sum=0
    for i in range(x,N):
        sum += A2[i]
    return sum

#1,N-iスタートの最大値を保存する配列
max=[]
for i in range(N):
    if i == 0:
        max.append(A1[N-1]+A2[N-1])
    else:
        if max[i-1] + A1[N-1-i] >= sumA2(N-1-i) + A1[N-1-i]:
            max.append(max[i-1]+A1[N-1-i])
        else:
            max.append(sumA2(N-1-i) + A1[N-1-i])
print(max[N-1])


Measured memory_bytes: 3064
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int[][] A = new int[3][3];
        boolean[][] isExisted = new boolean[3][3];


        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                A[i][j] = sc.nextInt();

        int N = sc.nextInt();
        int[] b = new int[N];

        for (int i = 0; i < N; i++) {
            b[i] = sc.nextInt();
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    if (b[i] == A[j][k]) {
                        isExisted[j][k] = true;
                    }
                }
            }
        }

        for (int i = 0; i < 3; i++) {
            if (isExisted[i][0] && isExisted[i][1] && isExisted[i][2]) {
                System.out.println("Yes");
                return;
            }
        }

        for (int i = 0; i < 3; i++) {
            if (isExisted[0][i] && isExisted[1][i] && isExisted[2][i]) {
                System.out.println("Yes");
                return;
            }
        }

        if (isExisted[0][0] && isExisted[1][1] && isExisted[2][2]) {
            System.out.println("Yes");
            return;
        }

        if (isExisted[0][2] && isExisted[1][1] && isExisted[2][0]) {
            System.out.println("Yes");
            return;
        }

        System.out.println("No");
    }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N, M;
    cin >> N >> M;
    int s[M], t[M];
    vector<int> adj[N];
    for (int i = 0; i < M; i++) {
        cin >> s[i] >> t[i];
        adj[s[i]].push_back(t[i]);
    }
    int indeg[N]{};
    int flag[N]{};
    
    int dp[N]{};
    fill(dp, dp + N, -1);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < adj[i].size(); j++) {
            int u = adj[i][j];
            indeg[u]++;
        }
    }
    deque<int> q;
    vector<int> id;
    for (int i = 0; i < N; i++) {
        if (indeg[i] == 0 && flag[i] == 0) {
            q.push_back(i);
            while (!q.empty()) {
                int u = q.front();
                id.push_back(u);
                q.pop_front();
                flag[u] = 1;
                for (int j = 0; j < adj[u].size(); j++) {
                    int v = adj[u][j];
                    indeg[v]--;
                    if (indeg[v] == 0 && flag[v] == 0) {
                        flag[v] = 1;
                        q.push_back(v);
                    }
                }
            }
        }
    }
    
    for (int i : id) {
        cout << i << "\n";
    }
    return 0;
}


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

int main()
{
    char s[100];
    int i, n, j, cnt=0;
    cin >> s;

    n=strlen(s);

    for(i=0, j=n-1; i<(n/2); i++, j--)
    {
        if(s[i]==s[j]) continue;
        else cnt++;
    }

    cout << cnt << endl;

    return 0;
}


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

#define int         long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;
int get(string s){
    int cnt=0;
    rep(i,1,sz(s)){
        if(s[i-1]==s[i]){
            cnt++;
            i++;
        }
    }
    return cnt;
}
string s;
int k;
void solve(){
    cin>>s>>k;
    int f=-1;
    rep(i,1,sz(s)){
        if(s[i]!=s[i-1]){
            f=i;
            break;
        }
    }
    if(f==-1){
        cout<<sz(s)*k/2<<endl;
        return;
    }
    string g1,g2;
    rep(i,f,sz(s)) g1+=s[i];
    rep(i,0,f) g2+=s[i];
    int d=get(g1+g2);
    int ans=(k-1)*d+get(g1)+get(g2);
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 256
// 2017/05/27 Tazoe

#include <iostream>
#include <string>
using namespace std;

class Proc{
public:
	string nam;
	int tim;
	Proc(){  nam = "";  tim = 0;  }
};

Proc Q[100001];


class Queue{
private:
	int fp;			// ??????????????????
	int rp;			// ????°?????????????
public:
	Queue()			{  fp = 0;  rp = 0;  }
	int next(int p) const	{  return (p+1)%100001;  }
	bool isFull() const	{  return (next(rp)==fp);  }
	bool isEmpty() const	{  return (rp==fp);  }
	void push(Proc d);
	Proc front();
        void pop();
};

void Queue::push(Proc d)
{
	if(isFull())
		return;		// ??????

	Q[rp] = d;
	rp = next(rp);		// ?????\??????????????????????????????
}

Proc Queue::front()
{
	if(isEmpty()){
		Proc er;
		er.tim = -1;
		return er;	// ??°??????????????????
	}

	return Q[fp];		// ??????????????????
}

void Queue::pop()
{
	if(isEmpty())
		return;		// ???

	fp = next(fp);		// ?????\?????????????????????????????????
}


int main()
{
	Queue que;

	int n, q;
	cin >> n >> q;

	for(int i=0; i<n; i++){
		Proc p;
		cin >> p.nam >> p.tim;

		que.push(p);
	}

	int total_tim = 0;

	while(!que.isEmpty()){
		Proc p = que.front();  que.pop();

		if(p.tim<=q){
			total_tim += p.tim;

			cout << p.nam << ' ' << total_tim << endl;
		}
		else{
			total_tim += q;
			p.tim -= q;

			que.push(p);
		}
	}

	return 0;
}

Measured memory_bytes: 6932
import bisect
while 1:
    try:
        n,m=map(float,input().split())
        m500=[35.5,37.5,40,43,50,55,70]
        m1000=[71,77,83,89,105,116,148]
        r1=bisect.bisect_left(m500,n+0.001)
        r2=bisect.bisect_left(m1000,m+0.001)
        rank=["AAA","AA","A","B","C","D","E","NA"]
        print(rank[max(r1,r2)])
    except:break


Measured memory_bytes: 5612
#include <bits/stdc++.h>
using namespace std;
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; }
const ll INF = 1LL << 60;
const int MAX = 1000000010;
const ll MOD = 1000000007;

int main() {
    ll N, M, K; cin >> N >> M >> K;
    vector<ll> A(N + 1);
    vector<ll> B(M + 1);
    for (int i = 1; i <= N; i++) {
        scanf("%lld", &A[i]);
    }
    for (int i = 1; i <= M; i++) {
        scanf("%lld", &B[i]);
    }
    A[0] = 0;
    B[0] = 0;
    vector<ll> sumA(N + 1);
    vector<ll> sumB(M + 1);
    sumA[0] = 0;
    sumB[0] = 0;
    for (int i = 1; i <= N; i++) {
        sumA[i] = sumA[i - 1] + A[i];
    }
    for (int j = 1; j <= M; j++) {
        sumB[j] = sumB[j - 1] + B[j];
    }
    
    int ans = 0;
    int a, b;
    for (int i = 0; i <= N; i++) {
        ll sum = sumA[i];
        ll rem = K - sum;
        if (rem > 0) {
            auto itr = upper_bound(sumB.begin(), sumB.end(), rem);
            int cnt = i + distance(sumB.begin(), itr) - 1;
            if(chmax(ans, cnt)) {
                a = distance(sumB.begin(), itr);
                b = i;
            }
        } else if (rem == 0) {
            chmax(ans, i);
            break;
        } else {
            chmax(ans, i - 1);
            break;
        }
    }

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

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

int main() {
	
	int n, m, x; cin >> n >> m >> x;
	int l = 0;
	int r = 0;
	for (int i = 0; i < m; i++) {
		int a;  cin >> a;
		if (a < x) l++;
		else r++;
	}
	cout << min(l, r) << endl;
	return 0;
}

Measured memory_bytes: 3596
#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 debug = 0;

ll count(ll mon){
    if(debug){
        cout << "count..." << mon << endl;
    }
    if(mon > 1)
        return 1+2 * count(floor(mon / 2.0));
    else 
        return 1;
}

int main()
{
    ll h;
    cin >> h;
    ll ans = count(h);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
typedef long long ll;
ll a, b, c, d, g, l, s1, s2;
ll gcd(ll p, ll q) {
	if(q==0) return p;
	return gcd(q, p%q);
}

int main() {
	cin>>a>>b>>c>>d;
	a--;
	g = gcd(c, d);
	l = c / g * d;
	s1 = b - b/c - b/d + b/l;
	s2 = a - a/c - a/d + a/l;
	cout<<s1 - s2;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;

//flagを使ったバブルソート
int bubbleSort(int A[],int N){
  int sw = 0;
  bool flag = 1;
  for(int i = 0;flag;i++){
    flag = 0;
    for(int j = N - 1;j >= i +1;j--){
      if(A[j] < A[j - 1]){
        //隣接要素を交換する
        swap(A[j],A[j - 1]);
        flag = 1;
        sw++;
      }
    }
  }
  return sw;
}

int main(){
  int A[100],N,sw;
  cin >> N;
  for(int i = 0;i < N;i++){
    cin >> A[i];
  }
  sw = bubbleSort(A,N);

  for(int i = 0;i < N;i++){
    if(i){
      cout << " ";
    }
    cout << A[i];
  }
  cout << endl;
  cout << sw << endl;

  return 0;
}



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

#define MAX 200000
#define INF 2000000000

int L[MAX / 2 + 2],R[MAX / 2 + 2];

long long merge(int a[],int n,int left,int mid,int right)
{
    int i,j,k;
    long long count = 0;

    int n1 = mid - left;
    int n2 = right - mid;

    for (i = 0; i < n1; ++i)
    {
        L[i] = a[left + i];
    }

    for (i = 0; i < n2; ++i)
    {
        R[i] = a[mid + i];
    }

    L[n1] = R[n2] = INF;
    i = j = 0;

    for(k = left;k < right;k++)
    {
        if (L[i] <= R[j])
            a[k] = L[i++];

        else
        {
            a[k] = R[j++];
            count += n1 - i;
        }
    }

    return count;
}

long long mergeSort(int a[],int n,int left,int right)
{
    int mid;
    long long v1,v2,v3;

    if(left + 1 < right)
    {
        mid = (left + right)/2;
        v1 = mergeSort(a,n,left,mid);
        v2 = mergeSort(a,n,mid,right);
        v3 = merge(a,n,left,mid,right);

        return v1 + v2 + v3;
    }

    else
        return 0;
}



int main()
{
    int a[MAX],n,i;

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

    long long Ans = mergeSort(a,n,0,n);
    cout << Ans << endl;

    return 0;
}


Measured memory_bytes: 4652
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std; long long a[1000010] = { 0 };
int main()
{
	int n;
	cin >> n;
	int b;
	for (int i = 1; i < n; i++) {
		cin >> b;
		a[b]++;
	}
	for (int i = 1; i <= n; i++) cout << a[i] << endl;

	/*int n, m;
	cin >> n >> m;
	long long sum = 0;
	for (int i = 0; i < m; i++) {
		cin >> a[i]; sum += a[i];
	}
	if (sum > n) cout << -1;
	else
	{
		cout <<n - sum;
	}*/
}

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

#define mp(a,b) make_pair((a),(b))
#define pii pair<int,int>
//#define pdd pair<double,double>
#define pll pair<LL,LL>
#define pb(x) push_back(x)
#define x first
#define y second
#define sqr(x) ((x)*(x))
#define EPS 1e-6
#define mii map<int,int>
#define MEM(x) memset(x,0,sizeof(x))
#define MEMS(x) memset(x,-1,sizeof(x))
#define pi 3.14159265359
#define INF 0x7fffffff
#define next Next
#define N 200005
using namespace std;
typedef long long LL;
int main(){
	int n;
	scanf("%d",&n);
	int a[100005];
	for(int i=0;i<n;i++)
	scanf("%d",&a[i]);
	reverse(a,a+n);
	LL Min=2,Max=2;
	for(int i=0;i<n;i++){
		Min=((Min-1)/a[i]+1)*a[i];
		Max=(Max/a[i])*a[i]+a[i]-1;
	}
	if(Min>Max)
	printf("-1\n");
	else
	printf("%lld %lld\n",Min,Max);
}

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

void dfs(string s, char mx){
    if(s.length() == N){
        cout << s <<endl;
    }else{
        for (char c = 'a'; c <= mx; c++) {
            dfs(s+c, ((c==mx) ? (c+1) : mx));
        }
    }
}

int main() {
    cin >> N;
    dfs("",'a');
    return 0;
}

Measured memory_bytes: 1536
#include<iostream>
using namespace std;
#define MAX 100000

int parent(int i){return i / 2;}
int left(int i){return 2 * i;}
int right(int i){return 2 * i + 1;}

int main(){
    int H,i,A[MAX+1];
    
    cin >> H;
    for(i=1; i<=H; i++)cin >> A[i];
    
    for( i=1; i<=H; i++){
        cout << "node " << i << ": key = " << A[i] << ", ";
        if(parent(i)>=1) cout << "parent key = " << A[parent(i)] << ", ";
        if(left(i)<= H )cout << "left key = " << A[left(i)] << ", ";
        if(right(i)<= H )cout << "right key = " << A[right(i)] << ", ";
        cout << endl;
    }
    
    return 0;
}    


Measured memory_bytes: 3112
#include <stdio.h>

int main() {
    int M,D,d1,d10,ans = 0;
    scanf("%d%d",&M,&D);
    d1 = D%10;
    d10 = D/10;
    for (int i = 4; i<=M ; i++) {
        for (int k = 2; k <= d10; k++) {
            if (k == d10) {
                for (int r = 2; r<=d1; r++) {
                    if (i == k*r) {
                        ans++;
                    }
                }
            }else{
                for (int r = 2; r<=9; r++) {
                    if (i == k*r) {
                        ans++;
                    }
                }
            }
        }
    }
    
    printf("%d",ans);
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,x=0,sum=0,a;
	cin>>n;
	for(int i=1;i<=n;i++)
	 cin>>a,sum+=a,x=max(x,a);
	sum-=x/2;
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 256
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.trim()).split("\n0,0\n");
var inputA=Arr[0].split("\n");
var inputB=Arr[1].split("\n").map(Number);

var obj={};
var s=[];

inputA.forEach(function(v){
var arr=v.split(",").map(Number);
obj[arr[0]]=arr[1];
s.push(arr[1]);
});

s.sort(function(a,b){return b-a;});

var s0=s[0];
var t=[s0];
for(var i=1;i<s.length;i++){
if(s0==s[i])continue;
s0=s[i];
t.push(s[i]);
}

inputB.forEach(function(v){
console.log(t.indexOf(obj[v])+1);
});

Measured memory_bytes: 7644
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
#ifndef MAX
#define MAX 400000
#endif

//Range Update Query+Range Sum Query
template<class T>
class RUQ_RSQ {
public:
	int n;
	T dat[MAX], lazy[MAX], ZERO, DEFAULT;
	void init(int n_, T d = INT_MAX, T t = 0) {
		DEFAULT = d;
		ZERO = T();
		n = 1; while (n < n_)n <<= 1;
		for (int i = 0; i < 2 * n - 1; i++) {
			dat[i] = t; lazy[i] = DEFAULT;
		}
	}
	inline void push(int k, int s) {
		if (lazy[k] == DEFAULT)return;
		dat[k] = lazy[k] * s;
		if (k < n - 1) {
			lazy[k * 2 + 1] = lazy[k];
			lazy[k * 2 + 2] = lazy[k];
		}
		lazy[k] = DEFAULT;
	}
	inline void update_node(int k) {
		dat[k] = dat[k * 2 + 1] + dat[k * 2 + 2];
	}
	inline void update(int a, int b, T x, int k, int l, int r) {
		push(k, r - l);
		if (r <= a || b <= l)return;
		if (a <= l&&r <= b) {
			lazy[k] = x; push(k, r - l); return;
		}
		update(a, b, x, k * 2 + 1, l, (l + r) / 2);
		update(a, b, x, k * 2 + 2, (l + r) / 2, r);
		update_node(k);
	}
	inline T query(int a, int b, int k, int l, int r) {
		push(k, r - l);
		if (r <= a || b <= l)return ZERO;
		if (a <= l&&r <= b)return dat[k];
		T lb = query(a, b, k * 2 + 1, l, (l + r) / 2);
		T rb = query(a, b, k * 2 + 2, (l + r) / 2, r);
		update_node(k);
		return lb + rb;
	}
	inline void update(int a, int b, T x) {
		update(a, b, x, 0, 0, n);
	}
	inline void update(int a, T x) {
		update(a, a + 1, x);
	}
	inline T query(int a, int b) {
		return query(a, b, 0, 0, n);
	}
	inline T query(int a) {
		return query(a, a + 1);
	}
};
RUQ_RSQ<int>seg;
int main() {
	int n, q; scanf("%d%d", &n, &q);
	seg.init(n, INT_MAX, INT_MAX);
	rep(i, q) {
		int a; scanf("%d", &a);
		if (a == 0) {
			int s, t, x; scanf("%d%d%d", &s, &t, &x); t++;
			seg.update(s, t, x);
		}
		else {
			int t; scanf("%d", &t);
			printf("%d\n", seg.query(t));
		}
	}
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)

using namespace std;
using ll = long long;

struct Dinic {
  struct edge { int v; long long c; };
  vector<edge> es;
  vector<vector<int>> g;
  vector<int> dist;
  vector<int> index;

  Dinic(int n) : g(n), dist(n), index(n) {}

  int add(int u, int v, long long c) {
    g[u].push_back(es.size());
    g[v].push_back(es.size() + 1);
    es.push_back(edge{v, c});
    es.push_back(edge{u, 0});
    return es.size() - 2;
  }

  long long calc(int s, int t) {
    long long ans = 0;
    while (bfs(s, t)) {
      for (;;) {
        long long d = dfs(s, t, 1e18);
        if (d == 0) break;
        ans += d;
      }
    }
    return ans;
  }

  bool bfs(int s, int t) {
    fill(dist.begin(), dist.end(), -1);
    fill(index.begin(), index.end(), 0);
    queue<int> q;
    q.push(t);
    dist[t] = 0;
    while (!q.empty()) {
      int u = q.front(); q.pop();
      for (int i : g[u]) {
        int v = es[i].v;
        if (es[i ^ 1].c > 0 && dist[v] == -1) {
          dist[v] = dist[u] + 1;
          q.push(v);
        }
      }
    }
    return dist[s] != -1;
  }

  long long dfs(int u, int t, long long f) {
    if (u == t) return f;
    for (int &it = index[u]; it < g[u].size(); it++) {
      int i = g[u][it];
      int v = es[i].v;
      if (es[i].c > 0 && dist[v] < dist[u]) {
        long long d = dfs(v, t, min(f, es[i].c));
        if (d > 0) {
          es[i ^ 0].c -= d;
          es[i ^ 1].c += d;
          return d;
        }
      }
    }
    return 0;
  }
};

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int N, M; cin >> N >> M;
  vector<vector<int>> A(N, vector<int>(M)); rep(i, N) rep(j, M) cin >> A[i][j], A[i][j]--;
  int s = 2*N, t = 2*N+1;
  vector<vector<int>> B(N, vector<int>(M));
  vector<vector<int>> E(N, vector<int>(M));
  rep(k, M) {
    Dinic mf(2*N+2);
    rep(i, N) mf.add(s, i, 1), mf.add(i + N, t, 1);
    rep(i, N) rep(j, M) {
      if (A[i][j] != -1) {
        E[i][j] = mf.add(i, N + A[i][j] / M, 1);
      }
    }
    assert(mf.calc(s, t) == N);
    rep(i, N) rep(j, M) {
      if (A[i][j] != -1 && mf.es[E[i][j]].c == 0) {
        B[i][k] = A[i][j];
        A[i][j] = -1;
      }
    }
  }
  vector<vector<int>> C(N, vector<int>(M));
  rep(j, M) {
    vector<int> v(N);
    rep(i, N) v[i] = B[i][j];
    sort(v.begin(), v.end());
    rep(i, N) C[i][j] = v[i];
  }
  rep(i, N) rep(j, M) cout << B[i][j]+1 << (j == M - 1 ? '\n' : ' ');
  rep(i, N) rep(j, M) cout << C[i][j]+1 << (j == M - 1 ? '\n' : ' ');
}

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

#define ll     long long
#define fr     first
#define sec    second
#define rep(i,n)  for(i=0;i<n;i++)
#define vi     vector <int>
#define vc     vector <char>
#define vl     vector <ll>
#define vb     vector <bool>
#define pb     push_back
#define M      1000000007
#define ios    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define open   freopen("input.txt","r",stdin);
#define close  freopen("output.txt","w",stdout);
#define M_PI   3.14159265358979323846
#define pp     pair<int,int>
#define nn 100003
#define MM 1000000000
#define MN 1000000000000000000
int main()
{
    ios;
    ll k,a,b;
    cin>>k>>a>>b;
    ll q=a/k;
    q+=1;
    if(a%k==0)
        cout<<"OK";
    else if(q*k<=b)
        cout<<"OK";
    else
        cout<<"NG";
    return 0;
}


Measured memory_bytes: 3652
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>

using namespace std;

int main() {

	string S, T, U;
	int A,B;

	cin >> S >> T;
	cin >> A >> B;
	cin >> U;

	if (U ==S) {
		A--;
	}
	else {
		B--;
	}
	cout << A << " " << B;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

int main(){
  string s;
  cin >> s;
  if(s.size() < 4){
    cout << "No" << endl;
    return 0;
  }
  string t = "YAKI";
  string ss = s.substr(0, 4);
  if(t == ss) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3600
def distance(x1, x2):
    sum = 0
    for i in range(len(x1)):
        sum += (x1[i] - x2[i])**2
    return sum**(1/2)

n,d = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]

cnt = 0
for i in range(len(x)-1):
    for j in range(i+1, len(x)):
        d = distance(x[i], x[j])
        if d == int(d):
            cnt+=1
print(cnt)


Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}


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

  int n,k;
  cin>>n>>k;
  int ans=0;
  rep(i,n){
    int h;
    cin>>h;
    if(h>=k) ans++;
  }

  cout<<ans<<endl;


}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define cyes cout<<"YES"<<endl
#define cno cout<<"NO"<<endl
#define sp <<" "<<
#define CST(x) cout<<fixed<<setprecision(x)
#define PI 3.14159265359
#define MOD 1000000007
using namespace std;
using ll = long long;
using ld = long double;
using Graph = vector<vector<int>>;
using que_a = priority_queue<int, vector<int>, greater<int> >;
using que_d = priority_queue<int>;
using pint = pair<int,int>;

int main(){

    int n; cin >> n;
    vector<int> vec;
    rep(i,n){
        int a; cin >> a;
        if(a == 0){
            int b; cin >> b;
            vec.push_back(b);
        }
        else if(a == 2) vec.pop_back();
        else{
            int b; cin >> b;
            cout << vec.at(b) << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3808