akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int main() {
  int n; string now, left, right;
  cin >> n;
  cout << 0 << endl; cin >> left;
  if(left == "Vacant") return 0;
  cout << n-1 << endl; cin >> right;
  if(right == "Vacant") return 0;

  int l = 0, r = n-1;
  while(true) {
    int mid = (l + r)>>1;
    int areaL = mid - l - 1;
    int areaR = r - mid - 1;
    cout << mid << endl; cin >> now;
    if(now == "Vacant") return 0;

    if((areaL&1 && left != now) || (areaL%2==0 && left == now)) {
      r = mid;
      right = now;
      continue;
    }
    if((areaR&1 && right != now) || (areaR%2==0 && right == now)) {
      l = mid;
      left = now;
      continue;
    }
  }
  return 0;
}

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



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,k;
    cin >> n >>k;
    ll arr[n];
    for(ll i=0;i<n;i++){
        cin >> arr[i];
    }
    ll dp[n];
    dp[0]=0;
    dp[1] = abs(arr[1]-arr[0]);
    for(ll i=2;i<n;i++){
        if(k>1){
        ll j=3,mini=min(dp[i-1]+abs(arr[i]-arr[i-1]),dp[i-2]+abs(arr[i]-arr[i-2]));
        while(j<=k && i-j >=0){
            mini = min(dp[i-j]+abs(arr[i]-arr[i-j]),mini);
            j++;
        }
        dp[i] = mini;}
        else{
            dp[i] = dp[i-1] + abs(arr[i]-arr[i-1]);
        }
    }

    cout << dp[n-1];

    return 0;
}


/*for(ll i=2;i<n;i++){
        dp[i] = min(dp[i-1]+abs(arr[i]-arr[i-1]),dp[i-2]+abs(arr[i]-arr[i-2]));

    }*/


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <deque>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <iomanip>
#include <cstring>
#include <climits>
#include <cstdio>

#define nl '\n'

using namespace std;

string s;
int x, mx = 0;

int main(){

    cin >> s;

    for(int i = 0; i < s.length(); i++){
        x = 0;
        if(s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T'){
            for(int j = i; j < s.length(); j++){
                if(s[j] == 'A' || s[j] == 'C' || s[j] == 'G' || s[j] == 'T'){
                    x++;
                } else{
                    break;
                }
            }
        }
        if(x > mx){
            mx = x;
        }
    }

    cout << mx;


    
}
 
//g++ -std=c++14 comp.cpp -o c && c.exe
//g++ -std=c++14 comp.cpp -o c; ./c.exe
//g++ -std=c++14 comp.cpp && ./a.out


//Surely this is going to AC

Measured memory_bytes: 256
//#include<iostream>
//#include<algorithm>
//#include<string>
//#include <cmath>
//#include <vector>
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define REP(x,n) for(int x=0;x<n;x++)

//vector//
#define vei vector<int> 
#define velli vector<long long int> 
#define pb(x) push_back(x) // 末尾にxを加える
#define pb2 pop_back() // 末尾削除
#define all(x) (x).begin(),(x).end() //イテレーター
#define be(x) (x).begin()
//auto  auto begin = v.begin()とか

typedef pair<int,int> P;  //q(p.first,p.second)

// 順列全探索
// N!
// next_permutation
int main (){
    // 入力
    int n; cin >> n;
    vector<int> x(n);
    vector<int> y(n);
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i];
        a[i] = i;
    }

    double sum = 0; // 最後にn!で割ると答え
    double x_sa, y_sa;
    // 順列全探索
    do{
        double dist = 0;
        for(int i=0;i<n-1;i++){
            x_sa = x[a[i+1]]-x[a[i]];
            y_sa = y[a[i+1]]-y[a[i]];
            dist += sqrt(x_sa*x_sa + y_sa*y_sa);
        }
        sum += dist;
    }while(next_permutation(a.begin(),a.end()));

    // nの階上
    double kai = 1;
    for(double i=1;i<=n;i++){
        kai*=i;
    }
    
    printf("%.8f",sum/kai);
}

Measured memory_bytes: 3804
N = int(input())
A,B,C = input(),input(),input()
ans = 0
for a,b,c in zip(A,B,C):
    if a != b and b != c and c != a:
        ans += 2
    elif a == b == c:
        ans += 0
    else:
        ans += 1
print(ans)

Measured memory_bytes: 3316
from collections import deque

S = input()
Q = int(input())
L = 1
S = deque(S)

for i in range(Q):
    A = list(input().split())
    if int(A[0]) == 1:
        L = -L
    if int(A[0]) == 2:
        A[1] = 2*int(A[1]) - 3
        if L*A[1] == -1:
            S.appendleft(A[2])
        else:
            S.append(A[2])

if L == 1:
    print(''.join(S))
else:
    print(''.join(list(reversed(S))))

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

int main() {
  long int N, sum = 0, max;
  cin >> N;
  vector<long int> a(N);
  rep(i,N) cin >> a.at(i);
  max = a.at(0);
  rep(i,N-1) {
    if(max <= a.at(i+1)) max = a.at(i+1);
    else sum += (max - a.at(i+1));
  }
  cout << sum << endl;
}


Measured memory_bytes: 4732
from collections import defaultdict, deque
import sys
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())
ans = 0
seen = [[-1]*W for _ in range(H)]
vec = [[1, 0], [0, 1], [-1, 0], [0, -1]]
v2 = [[1, 1], [-1, 1], [-1, -1], [1, -1], [2, 1], [1, 2], [-1, 2], [2, -1], [-2, 1], [1, -2], [-1, -2], [-2, -1], [2, 0], [0, 2], [-2, 0], [0, -2], [2, 2], [2, -2], [-2, -2], [-2, 2]]
queue = deque()
q = deque()
queue.append([Ch-1, Cw-1])
q.append([Ch-1, Cw-1])
seen[Ch-1][Cw-1]=0

while queue:
    while queue:
        l = queue.popleft()
        q.append(l)
        h, w = l[0], l[1]
        for ll in vec:
            #コースアウト
            if h+ll[0]>=H or h+ll[0]<0 or w+ll[1]>=W or w+ll[1]<0:
                continue
            #障害物
            if S[h+ll[0]][w+ll[1]]=="#":
                continue
            #既視
            if seen[h+ll[0]][w+ll[1]]!=-1:
                continue
            queue.append([h+ll[0], w+ll[1]])
            q.append([h+ll[0], w+ll[1]])
            seen[h+ll[0]][w+ll[1]]=ans
    ans+=1
    
    while q:
        l = q.popleft()
        h, w = l[0], l[1]
        for z in v2:
            #コースアウト
            if h+z[0]>=H or h+z[0]<0 or w+z[1]>=W or w+z[1]<0:
                continue
            #障害物
            if S[h+z[0]][w+z[1]]=="#":
                continue
            #既視
            if seen[h+z[0]][w+z[1]]!=-1:
                continue
            queue.append([h+z[0], w+z[1]])
            seen[h+z[0]][w+z[1]]=ans
print(seen[Dh-1][Dw-1])

Measured memory_bytes: 98488
import java.util.Arrays;
import java.util.Scanner;

public class Main{
	static int N;
	static long[] a;
	static long[][] dp;
	static long f(int i, int j) {
		if(i == j) return ((N + i - j - 1) % 2 == 0) ? a[i] : -a[i];
		if(dp[i][j] != Long.MIN_VALUE) return dp[i][j];
		if((N + i - j - 1) % 2 == 0) {
			return dp[i][j] = Math.max(f(i + 1, j) + a[i], f(i, j - 1) + a[j]);
		}else {
			return dp[i][j] = Math.min(f(i + 1, j) - a[i], f(i, j - 1) - a[j]);
		}
	}
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()) {
			N = sc.nextInt();
			a = new long[N];
			dp = new long[N][N];
			for(int i = 0; i < N; i++) {
				a[i] = sc.nextInt();
			}
			for(int i = 0; i < N; i++)  Arrays.fill(dp[i], Long.MIN_VALUE);
			System.out.println(f(0, N - 1));
		}
	}
}

Measured memory_bytes: 131988
#include <bits/stdc++.h>
using intl = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for(intl i = 0; i < (intl)(n); i++)
#define repd(i, n) for(intl i = (intl)((n) - 1); i >= 0; i--)
#define repi(i, a, b) for(intl i = (intl)(a); i < (intl)(b); i++)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define all(x) (x).begin,(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define debug(x) cout << #x << ":" << x << endl
const intl INF = 1e9;
const intl MOD = 1e9+7;
void fp(bool flag){
    if(flag)cout << "Yes" << endl;
    else cout << "No" << endl;
}
int main(){
    ld a;
    cin >> a;
    ld b;
    cin >> b;
    ld c;
    cin >> c;
    ld as = sqrt(a);
    ld bs = sqrt(b);
    ld cs = sqrt(c);
    ld e =  1.0e-14;
    fp((as + bs + e < cs));
    return 0;
}

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include "bits/stdc++.h"

using namespace std;
typedef unsigned long long ll;
typedef int                     integer;
#define int                     long long
#define ii                      pair<int,int>
#define vii                     vector<pair<int,int>>
#define vi                      vector<int>
#define vvi                     vector<vector<int>>
#define f(a,b,c)                for(int a=b;a<c;a++)
#define s(x)                    in>>x
#define s2(x,y)                 in>>x>>y
#define s3(x,y,z)               in>>x>>y>>z
#define s4(x,y,z,w)             in>>x>>y>>z>>w
#define p(x)                    out<<x<<endl
#define p2(x,y)                 out<<x<<' '<<y<<endl
#define p3(x,y,z)               out<<x<<' '<<y<<' '<<z<<endl
#define p4(x,y,z,w)             out<<x<<' '<<y<<' '<<z<<' '<<w<<endl
#define pl(x)                   out<<x
#define pll(x)                  out<<x<<' '
#define range(v)                v.begin(),v.end()
#define rst(x)                  memset(x, -1, sizeof(x))
#define UNVISITED               -1
#define VISITED                 0
#define EXPLORED                2

#define EACH(x, a) for (auto& x: a)
template<class T> void read_v(T& x, std::istream& in) {
    in >> (x);
}
template<class A> void read_vec(vector<A>& x, std::istream& in) {
    EACH(a, x)
        read_v(a, in);
}

bool sortpairbysec(const pair<int,int> &a,const pair<int,int> &b){return (a.second < b.second);}
template <typename T>
T factmod(T a, T modulus){ int res = 1, i; for (i = 2; i <= a; i++){ res *= i; res%=modulus;} return res; }
template <typename T>
int powmod(T a,T b,int m){ int ans=1; while(b>0){if(b&1){ans*=a;ans%=m;}a*=a;a%=m;b>>=1;} return ans; }
template <typename T>
int power(T a, T b){ int ans=1; while(b>0){if(b&1){ans*=a;}a*=a;b>>=1;}return ans;}


void ssolve(std::istream& in, std::ostream& out){
    string st; s(st);
    int n = (int)st.size();
    int ans = 0;
    f(i, 0, n){
        ans += (st[i]-'0');
        ans %= 9;
    }
    if(ans%9==0){
        p("Yes");
    }else{
        p("No");
    }
}

class BMultipleOf9 {
public:
void solve(std::istream& in, std::ostream& out) {
    ios_base::sync_with_stdio(false);
    in.tie(nullptr);out.tie(nullptr);
    int t;
    int READ = 0;
    if(READ) s(t);
    else t = 1;
    while(t--){
        ssolve(in, out);
    }
}
};

integer main() {
    BMultipleOf9 solver;
    std::istream& in(std::cin);
     std::ostream& out(std::cout);
     solver.solve(in, out);
}

Measured memory_bytes: 3804
#include <iostream>
#include <string>
#include <vector>

int main(void)
{
  int N; std::cin >> N;
  int cnt = 0;
  std::vector<int> q(N);
  
  for (int i = 0; i < q.size(); i++) {
    std::cin >> q[i];
  }
  
  for (int i = 0; i < (q.size() - 2); i++){
    if (((q[i] < q[i+1]) && (q[i+1] < q[i+2])) || ((q[i] > q[i+1]) && (q[i+1] > q[i+2])) ) cnt++;
  }
  
  std::cout << cnt << std::endl;
  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0)
#define endl "\n";
#define pb push_back
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define int long long
const int MOD=1e9+7;
const int N=2e5+10;
int a[N],pre[N];
int32_t main()
{
	IOS;
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		//a[i]=0;
		cin>>a[i];
	}
	int cnt=0;
	while(cnt<k)
	{
		for(int i=1;i<=n;i++)
		{
			pre[max(1LL,i-a[i])]++;

			pre[min(n+1,i+a[i]+1)]--;
		}
		for(int i=1;i<=n;i++)
		{
			pre[i]+=pre[i-1];
		}
		for(int i=1;i<=n;i++)
		{
			a[i]=pre[i];
			pre[i]=0;

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

	}
	for(int i=1;i<=n;i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
	
}

Measured memory_bytes: 6796
/* B */

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

int main(){
	int n;
	cin >> n;
	std::vector<int> v(n);
	std::vector<int> sum(n);
	int k = 0;
	int mini = 10000;
	for (int i = 0; i < n; ++i)
	{
		cin >> v[i];
		k = k + v[i];
		sum[i] = k;
	}

	for (int i = 0; i < n-1; ++i){
			mini = min(abs(sum[n-1] - 2 * sum[i]), mini); 
	}


	cout << mini << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int a[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
int main()
{
    int K;
    scanf("%d",&K);
    printf("%d\n",a[K-1]);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp> 
// using namespace boost::multiprecision;
// #define int cpp_int
using namespace std;

#define fastio 			ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int 			long long
#define ll 				long long
#define ld 				long double
#define vi 				vector<int>
#define pii 			pair<int,int>
#define vpii 			vector< pair<int,int> >
#define uset			unordered_set
#define umap 			unordered_map
#define maxpq 			priority_queue<int>
#define minpq			priority_queue<int,vi,greater<int>()>

#define all(v) 			v.begin(),v.end()
#define part(v,s,e)		v.begin()+s,v.begin()+e
#define rev(v)			reverse(v.begin(),v.end())
#define sz(x)			(int)x.size()
#define def(v)			memset(v,-1,sizeof(v));
#define def0(v)			memset(v,0,sizeof(v));
#define minv(a)			*min_element(all(a))
#define maxv(a)			*max_element(all(a))
#define sumv(a)			accumulate(all(a),0)

#define	lb				lower_bound
#define	ub				upper_bound
#define	desc			greater<int>()
#define	pb				emplace_back
#define	mp				make_pair
#define	F				first
#define	S				second

#define	mod 			1000000007
#define	inf 			1000000000000000
#define infty			1000000000000000000LL
#define	md				998244353
#define	PI				acos(-1.0)
#define	endl 			"\n"
#define	rr				return
#define	br				cout<<"\n";

#define gcd(a,b)		__gcd(a,b)
#define lcm(a,b)		(a/(__gcd(a,b)))*b

#define setbits(x) 		__builtin_popcountll(x)
#define zerobits(x)		__builtin_ctzll(x)

#define ip(v)	 		for(auto& i:v)	cin>>i;
#define op(v) 			for(auto i:v)	cout<<i<<" ";cout<<endl;
#define deb(x) 			cout <<"Value of " #x << " : " << x << endl;



void solve()
{	

	map<int,int>m;
	int a[3];
	for(int i=0;i<3;i++)
	{
		cin>>a[i];
		m[a[i]]++;
	}

	if(m[5]==2 and m[7]==1)
	{
		cout<<"YES\n";
	}
	else
	{
		cout<<"NO\n";
	}

}	

int32_t main()
{

	fastio
	cout<<setprecision(15)<<fixed;



	int t=1;
	// cin>>t;
	
	for(int i=1;i<=t;i++)
	{
		// cout<<"Case "<<i<<" : "<<endl;
		solve();
	}
	
	#ifndef ONLINE_JUDGE	
		cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl;
	#endif

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string> 
#include <stdio.h>
using namespace std; 
#define file freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#define ll long long int
#define REPI(a, b, i, inc) for(ll i = a; i < b; i = i + inc)
#define REP(i, a, b) for(ll i = a; i < b; i++)
#define F first
#define S second
#define pb push_back
#define test ll t; cin>>t; while(t--)
#define testi ll t; cin>>t; REP(tc,1,t+1)
#define vec vector
#define veci vector<ll>
#define pi pair<ll,ll>
#define mp make_pair
#define all(v) v.begin(), v.end()
#define uset unordered_set
#define umap unordered_map

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);


int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("op.txt","w",stdout);
    #endif
	
	
    int a1,b1,c1;
    cin>>a1>>b1>>c1;
    int k1;
    cin>>k1;
    if(a1<b1 && b1<c1)
    	{cout<<"Yes"<<endl; return 0;}
    int a,b,c,k;
    a=a1;
    b=b1;
    c=c1;
    k=k1;
    while(a>=b || b>=c )
    {
    	if(a>=b)
    		{b=b*2; k--;}
      if(k<0) break;
    	if(b>=c)
    		{c=c*2; k--;}
       if(k<0) break;
    }

    if(k>=0){
    	cout<<"Yes"<<endl;
    	return 0;
    }
 a=a1;
    b=b1;
    c=c1;
    k=k1;
   
   while(a>=b || b>=c )
    {
     
    	if(b>=c)
    		{c=c*2; k--;}
    	 if(k<0) break;
    	if(a>=b)
    		{b=b*2; k--;}
       if(k<0) break;
    }
    if(k>=0){
    	cout<<"Yes"<<endl;
    }
   else
   	cout<<"No"<<endl;

    



	
	return 0;


}

Measured memory_bytes: 3632
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include<numeric>
#include<cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#define ll long long int
#define CON 100010
#define N 1500000
const long long mod=1e9+7;
const int INF=1001001001;
//const int inf=100000;
//const ll ful=1e18;
using namespace std;
//namespace mp = boost::multiprecision;
int main() 
{
	int n;
	cin>>n;
	vector<int> v(n);
	vector<int> p(n);
	vector<int> q(n);
	for(int i=0;i<n;++i)
	{
		cin>>p[i];
		v[i]=p[i];
	}
	for(int i=0;i<n;++i)
	{
		cin>>q[i];
	}
	sort(v.begin(),v.end());
	int a,b;
	int count=1;
	do
	{
		if(p==v)
		{
			a=count;
		}
		if(q==v)
		{
			b=count;
		}
		count++;
	}while(next_permutation(v.begin(),v.end()));
	int ans=abs(a-b);
	cout<<ans;
	return 0;
}

Measured memory_bytes: 3608
n=int(input())
h=list(map(int,input().split()))
DP=[0]*n
DP[0]=0
DP[1]=abs(h[0]-h[1])
for i in range(n-2):
    DP[i+2]=min(DP[i]+abs(h[i]-h[i+2]),DP[i+1]+abs(h[i+2]-h[i+1]))
print(DP[-1])

Measured memory_bytes: 20580
#include <iostream>
#include <vector>

using namespace std;

#define pb push_back
#define mp make_pair
#define ld long double
#define li long long int
int main()
{
    li a, b, c, d, e; cin >> a >> b >> c >> d >> e;
    cout << (15 - a - b - c - d - e);
}

Measured memory_bytes: 3576
#include<iostream>
using namespace std;
int main(){
    int n,a[1000],b[1000],ans=0;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i]>>b[i];
    for(int i=0;i<n;i++)
        ans=ans+b[i]-a[i]+1;
    cout<<ans;
    return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MX_N = 1e5+5;
int N, A[MX_N], P[MX_N];

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    FOR(i,1,N){
        cin >> A[i];
        P[i] = i;
    }

    sort(P+1,P+1+N,[](int a, int b){ return A[a] < A[b]; });
    int ans = 0;
    FOR(i,1,N){
        if (P[i]%2 != i%2) ++ans;
    }
    assert(ans%2 == 0);
    cout << ans/2;
}



Measured memory_bytes: 1024
from collections import Counter

n = int(input())
aa = list(map(int,input().split()))

counter = Counter(aa)
mc = counter.most_common()
mc = sorted(mc,key=lambda x:x[0],reverse=True)

first = 0
second = 0
 
for i,c in mc:  
  if c>=2:
    if first == 0:  
      first=i
      if c>=4:
        second=i
        break
    else:
      second = i
      break    
  
print(first*second)    

Measured memory_bytes: 23204
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author tatsumack
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(12)

using namespace std;

typedef pair<int, int> P;

class CDifferBy1Bit {
public:
    int N, A, B;

    int bitcount(int n) {
        int cnt = 0;
        REP(i, N) {
            if (n >> i & 1) cnt++;
        }
        return cnt;
    }

    int erase(int n, int i) {
        int up = n;
        up = up >> (i + 1);
        up = up << i;
        int low = n & ((1 << i) - 1);
        return up | low;
    }

    int push(int n, int v, int i) {
        int up = n;
        up = up >> i;
        up = up << (i + 1);
        int low = n & ((1 << i) - 1);
        return up | low | (v << i);
    }

    vector<int> f(int a, int b, int d) {
        if (d == 1) return vector<int>{a, b};

        int x, va, vb;
        REP(i, d) {
            if (((a >> i) & 1) != ((b >> i) & 1)) {
                x = i;
                va = (a >> i) & 1;
                vb = (b >> i) & 1;
                break;
            }
        }
        int na = erase(a, x);
        int nb = erase(b, x);
        int c = na ^ 1;

        auto l = f(na, c, d - 1);
        auto r = f(c, nb, d - 1);
        for (auto &n : l) {
            n = push(n, va, x);
        }
        for (auto &n : r) {
            n = push(n, vb, x);
        }

        vector<int> res;
        res.insert(res.end(), l.begin(), l.end());
        res.insert(res.end(), r.begin(), r.end());
        return res;
    }

    void solve(std::istream& cin, std::ostream& cout) {
        cin >> N >> A >> B;

        int a = bitcount(A);
        int b = bitcount(B);
        if (a % 2 == b % 2) {
            cout << "NO" << endl;
            return;
        }
        cout << "YES" << endl;

        vector<int> res = f(A, B, N);
        REP(i, res.size()) cout << res[i] << " ";
        cout << endl;
    }
};


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    std::istream& in(std::cin);
    std::ostream& out(std::cout);

    CDifferBy1Bit solver;
    solver.solve(in, out);
    return 0;
}


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

#define int long long
const double PI = 3.14159265358979323846;
typedef vector<int> vint;
typedef pair<int, int> pint;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int H, W;
int a[550][550];
signed main() {
    cin >> H >> W;
    for (int i = 0; i < H; i++)for (int j = 0; j < W; j++)cin >> a[i][j];
    vint x1, y1, x2, y2;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W - 1; j++) {
            if (a[i][j] % 2 == 1) {
                x1.push_back(j), y1.push_back(i), x2.push_back(j + 1), y2.push_back(i);
                a[i][j + 1]++;
            }
        }
    }
    for (int i = 0; i < H - 1; i++) {
        if (a[i][W - 1] % 2 == 1) {
            x1.push_back(W - 1), y1.push_back(i), x2.push_back(W - 1), y2.push_back(i + 1);
            a[i + 1][W - 1]++;
        }
    }
    cout << x1.size() << endl;
    for (int i = 0; i < x1.size(); i++)cout << y1[i]+1 << " " << x1[i]+1 << " " << y2[i]+1 << " " << x2[i]+1 << endl;
}


Measured memory_bytes: 8276
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n, k int
	fmt.Scan(&n, &k)

	nums := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&nums[i])
	}
	sort.Ints(nums)

	min := 10000000000
	for i := 0; i < n-k+1; i++ {
		if nums[i+k-1]-nums[i] < min {
			min = nums[i+k-1] - nums[i]
		}
	}

	fmt.Println(min)
}


Measured memory_bytes: 5504
x1,y1,x2,y2 = map(int,input().split())

x3 = x2 + y1 - y2
y3 = y2 + x2 - x1

x4 = x3 - (x2 - x1)
y4 = y3 + y1 - y2

print(x3,y3,x4,y4)

Measured memory_bytes: 9160
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<(n);i++)
#define loop(i,a,n) for(i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int main(void) {
  int i,j;
  string s;
  cin>>s;
  int n=s.size();
  int ans=0;
  rep(i,n)if(s[i]=='1')ans++;
  cout<<ans<<endl;

}


Measured memory_bytes: 256
// ABC060
// A - Shiritori
#include<bits/stdc++.h>

using namespace std;

int main(){
    string s1,s2,s3;
    cin >> s1 >> s2 >> s3;
    if(s1[s1.size()-1]==s2[0] && s2[s2.size()-1]==s3[0]) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll  long long
#define ull unsigned long long  
using namespace std;
#define  inf 1e18+18
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define mod 1000000007
#define  f1(i,n) for(i=1;i<=n;i++)
#define f0(i,n)  for(i=0;i<n;i++)
#define w(x)   while(x--)
const int maxn=1000001;
#define  pq priority_queue
#define  ff first
#define  ss second 
#define pb  push_back
#define lb lower_bound
int db(int n)
{
    int i=0;
    int j=0;
    while(n>0)
    {
        int r=n%10;
        n=n/10;
        j+=(1<<i)*r;
        i++;
    }
    return j;
}
ll a[maxn];
int main()
{
   
    
   
  ll int n,i,j,l=0,m,x,res=0;
   cin>>n>>x>>m;
  vector<ll>v;
  int ch=0;
  l=0;
   for (i=1;i<=min(n,(ll)50000);i++)
   {
    //cout<<x%m<<" " ;
    x=x%m;

    if(v.empty())
    v.pb(x);
   else
   {
     for(int i1=0;i1<v.size();i1++)
     {
        if(v[i1]==x)
        {
            l=i-1;
            j=i1;
            ch=1;
            break;
        }
     }   
     if(ch)
        break;
     v.pb(x);
   }
   res+=x;
   
   // x=x%m;
    x=(x*x)%m;
   }
  // cout<<l<<" "<<j<<" "<<ch;
   if(ch){
   n=n-l;
   int c=0;

   for(i=j;i<v.size();i++)
   {
    c++;
   }
   for(i=j;i<v.size();i++)
   {
       ll int p=n/c;
       res+=p*v[i];
   }
   for(i=j;i<min((ll)v.size(),j+n%c);i++)
   {
    res+=v[i];
   }
}
   cout<<res;

  

}

Measured memory_bytes: 3932
fn main() {
    proconio::input! {
    a:usize,
    mut b:[usize;a],
  }
    let mut x=0;
    let mut z=0;
    let mut v=[0;8];
    for i in 0..a {
        if b[i]<3200{
            if v[b[i]/400]==0 {z+=1;}
            v[b[i]/400]=1;
        }
        else {x+=1}
    }
    println!("{} {}",std::cmp::max(z,1),z+x)
}

Measured memory_bytes: 2080
using System;
using System.Collections.Generic;
//using System.Linq;
//using System.Numerics;

class Program {
    static void Main (string[] args) {
        var input = INP();
        int N = TOI(input[0]);
        int D = TOI(input[1]);

        int cnt = 0;
        string[] input2 = new string[2];
        for(int i = 0;i < N;i++) {
            input2 = INP();
            bool flg = D >= Math.Sqrt(Math.Pow(TOI(input2[0]),2) + Math.Pow(TOI(input2[1]),2));
            if(flg) {
                cnt++;

            }
        }

        CWL(cnt);
    }

    public static List<int> PrimeFactors (int n) {
        var tmpList = new List<int>();
        int i = 2;
        int tmp = n;

        while(i * i <= n) {
            if(tmp % i == 0) {
                tmp /= i;
                tmpList.Add(i);
            } else {
                i++;
            }
        }

        if(tmp != 1) tmpList.Add(tmp);

        return tmpList;
    }

    static string[] INP () {
        return Console.ReadLine().Split(' ');
    }

    static void CWL (string value) {
        Console.WriteLine(value);
    }

    static void CWL (int value) {
        Console.WriteLine(value);
    }

    static void CWL (long value) {
        Console.WriteLine(value);
    }

    static void CWL (float value) {
        Console.WriteLine(value);
    }

    static void CWL (double value) {
        Console.WriteLine(value);
    }

    static int TOI (string str) {
        return int.Parse(str);
    }

    static long TOL (string str) {
        return long.Parse(str);
    }

    static float TOF (string str) {
        return float.Parse(str);
    }

    static double TOD (string str) {
        return double.Parse(str);
    }

    /*static void Main (string[] args) {
        var input = INP();
        var input2 = INP();
        var input3 = INP();

        CWL("dummy");
    }*/
}


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

///Author:Refat(BSMRSTU)///

#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define pil pair<int,ll>
const int N = 1e5 + 5;
const int M = 1e9 + 7;
int Set(int N,int pos) {
    return N=N | (1<<pos);
}
int reset(int N,int pos) {
    return N= N & ~(1<<pos);
}
bool check(int N,int pos) {
    return (bool)(N & (1<<pos));
}
int main() {
    /// freopen("input.txt","r",stdin);
    /// freopen("output.txt","w",stdout);
    int a,b,c,sub,val;
    scanf("%d %d %d",&a,&b,&c);
    sub=a-b;
    val=c-sub;
    if(val<=0){
        printf("0\n");
    }
    else{
        printf("%d\n",val);
    }
    return 0;
}



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

int main()
{
    int n, m;
    cin >> n >> m;
    if(n == m){
        cout << "Yes" << endl;
    }
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>

int main(){

  int n, q;
  
  std::cin >> n;
  std::cin >> q;
  std::queue<std::string> names;
  std::queue<int> times;
  for(int i=0; i<n; i++){
    std::string n;
    int t;
    std::cin >> n >> t;
    names.push(n);
    times.push(t);
  }
  std::string n1;
  int t1;
  int sum=0;
  while(!times.empty()){
    n1 = names.front();
    t1 = times.front();
    names.pop();
    times.pop();
    
    if(q<t1){
      names.push(n1);
      times.push(t1-q);
      sum+=q;
    }else{
      std::cout << n1 << " " << sum+t1 << std::endl;
      sum+=t1;
    }
  }



  
  return 0;
}



Measured memory_bytes: 5752
s=input()
s=list(s)
flag=0
if s[0]==s[1]:
    if s[2]==s[3]:
        if s[0]!=s[2]:
            print("Yes")
            flag=1
elif s[0]==s[2]:
    if s[1]==s[3]:
        if s[0]!=s[1]:
            print("Yes")
            flag=1
elif s[0]==s[3]:
    if s[1]==s[2]:
        if s[0]!=s[1]:
            print("Yes")
            flag=1
if flag!=1:
    print("No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=(a);i<(b);i++)
#define MOD 1000000007
#define MP make_pair
#define PB push_back
typedef long long ll;

ll N, ans;

int main () {
        cin >> N;
        ans += N/11;
        N -= ans * 11;
        ans *= 2;
        if (N == 0) cout << ans << endl;
        else if (N-6 <= 0) cout << ans+1 << endl;
        else cout << ans+2 << endl;
        return 0;
}


Measured memory_bytes: 256
def resolve():
    N = int(input())
    L = []
    for i in range(N):
        s, p = input().split()
        p = int(p)
        L.append((s, p, i+1))
    L = sorted(L, key=lambda x: (x[0], -x[1]))
    for l in L:
        print(l[2])
        
resolve()

Measured memory_bytes: 3060
function Main(input) {
  input = input.split("\n");
  var T = input[0].split(" ");
  var A = input[1].split(" ");
  var B = input[2].split(" ");
  var T0 = T[0];
  var T1 = T[1];
  var A0 = A[0];
  var A1 = A[1];
  var B0 = B[0];
  var B1 = B[1];
  var Ma=T0*(A0-B0);
  var Mb=(T1*A1+Ma)-(T1*B1);
if(Math.sign(Ma)==Math.sign(Mb)){
  console.log(0);
}else if(Mb==0){
  console.log("infinity");
}else{
  Ma = Math.abs(Ma);
  Mb = Math.abs(Mb);
  if(Ma%Mb==0){
    console.log((Ma/Mb)*2);
  }else{
    console.log(Math.ceil(Ma/Mb)*2-1);
  }
}
}Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 11468
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<iostream>
#include<numeric>
#include<math.h>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>
// 追加１
#include <fstream>



using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll mod = 2019;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()



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

    vector<int> A(N);
    rep(i, N) cin >> A[i];

    map<ll, ll> counts;

    ll count = 0;

    for (int i = N - 1; i >= 0; i--)
    {
        count += counts[i + A[i]];
        counts[i - A[i]]++;
    }

    cout << count << endl;

    return 0;
}

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

#pragma GCC diagnostic warning "-Wconversion"

#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(a) begin(a), end(a)
#define has(a, b) (a.find(b) != a.end())
#define fora(i, n) for(int i = 0; i < n; i++)
#define forb(i, n) for(int i = 1; i <= n; i++)
#define forc(a, b) for(const auto &a : b)
#define ford(i, n) for(int i = n; i >= 0; i--)
#define maxval(t) numeric_limits<t>::max()
#define minval(t) numeric_limits<t>::min()
#define imin(a, b) a = min(a, b)
#define imax(a, b) a = max(a, b)

#define dbgs(x) #x << " = " << x
#define dbgs2(x, y) dbgs(x) << ", " << dbgs(y)
#define dbgs3(x, y, z) dbgs2(x, y) << ", " << dbgs(z)
#define dbgs4(w, x, y, z) dbgs3(w, x, y) << ", " << dbgs(z)

using ll = long long;

ll a[200007];
ll p1[200007], p2[200007];

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

        int N;
        cin >> N;

        fora(i, N)
        {
                cin >> a[i];
                p1[i] = a[i];
                if (i >= 1)
                        p1[i] += p1[i - 1];
        }

        ford(i, N - 1)
        {
                p2[i] = a[i];
                if (i < N - 1)
                        p2[i] += p2[i + 1];
        }

        ll mi = maxval(ll);
        for (int i = 1; i < N; i++)
        {
                ll l = (i == 0) ? 0 : p1[i - 1];
                ll r = p2[i];
                imin(mi, abs(l - r));
        }

        cout << mi << endl;
}


Measured memory_bytes: 4992
#include <cstdio>

using namespace std;

int P[200001];
int counter = 1;

int main()
{
    int N;
    bool check;
    int min;

    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &P[i]);
    }

    min = P[0];
    
    for(int i=1; i < N; i++){
        if (P[i] < min){ min = P[i]; counter++; }
    }
    printf("%d\n", counter);

    return 0;
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    ll N;
    cin >> N;
    ll ans = 0;
    rep2(i, 1, N + 1) {
        if (i % 3 != 0 && i % 5 != 0) {
            ans += i;
        }
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


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

int main(){
    using namespace std;
    unsigned long N;
    cin >> N;
    vector<pair<long, long>> uf(200000);
    for(unsigned long i = 0; i < 100000; ++i)uf[i].first = -1;
    for(unsigned long i = 100000; i < 200000; ++i)uf[i].second = -1;
    unsigned long ans{0};
    auto find = [rec = [&uf](auto func, auto i) -> decltype(i){
        if(uf[i].first + uf[i].second < 0)return i;
        else return uf[i].first = func(func, uf[i].first);
    }](auto i){return rec(rec, i);};
    auto unite = [find, &uf](auto i, auto j) -> long{
        i = find(i);
        j = find(j);
        if(i == j)return 0;
        if(uf[i].first + uf[i].second > uf[j].first + uf[j].second)swap(i, j);
        auto ret = uf[i].first * uf[j].second + uf[i].second * uf[j].first;
        uf[i].first += uf[j].first;
        uf[i].second += uf[j].second;
        uf[j].first = i;
        uf[j].second = 0;
        return ret;
    };
    for(long i = 0, x, y; i < N; ++i){
        cin >> x >> y;
        ans += unite(x + 99999, y - 1);
    }
    cout << ans - N << endl;
    return 0;
}

Measured memory_bytes: 3328
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <climits>
#define ll long long
#define MAX 25 * 1e13

using namespace std;
int MOD = 1000000007;

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> isac( n + 1 );
  vector<int> cntwa( n + 1 );

  for(int i = 0 ; i < m ; i++ ){
    int p;
    string st;
    cin >> p >> st;
    if( st == "AC" ){
      isac[p] = 1;
    }
    if( st == "WA" ){
      if( isac[p] == 0 ){
        cntwa[p] ++ ;
      }
    }
  }
 
  int cnta = 0;
  int cntp = 0;
  for(int i = 1 ; i <= n ; i++ ){
    if( isac[i] == 1 ) cnta ++;
    if( isac[i] == 1 ) cntp += cntwa[i]; 
  }
  cout << cnta << " " << cntp << endl;

  return 0;
}


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

using namespace std;

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

bool comp(ll& a, ll& b)
{
  return a > b;
}

int main(){
  ll x, y, z, k;
  cin >> x >> y >> z >> k;

  vector<ll> A(x), B(y), C(z);
  rep(i, 0, x) scanf("%lld", &A[i]);
  rep(i, 0, y) scanf("%lld", &B[i]);
  rep(i, 0, z) scanf("%lld", &C[i]);
  sort(begin(A), end(A), comp);
  sort(begin(B), end(B), comp);
  sort(begin(C), end(C), comp);

  vector<ll> res;
  rep(l, 0, x)
  {
    rep(m, 0, y)
    {
      rep(n, 0, z)
      {
        if ((l + 1) * (m + 1) * (n + 1) <= k)
        {
          res.push_back(A[l] + B[m] + C[n]);
        }
        else 
        {
          break;
        }
      }
    }
  }
  sort(begin(res), end(res), comp);

  rep(i, 0, k)
  {
    cout << res[i] << endl;
  }
}

Measured memory_bytes: 1404
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
	int n,k;
	cin >> n >> k;
	ll arr[n];
	for(int i = 0; i < n;i++)cin >> arr[i];
	sort(arr,arr+n);
	reverse(arr,arr+n);
	ll ans = (ll)1e16;
	for(int i = 0; i < n-k+1;i++){
		ans = min(ans,arr[i]-arr[i+k-1]);
	}
	cout << ans;
}

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

signed main () {
    int n;
    cin >> n;
    vector < int > a(n);
    for (int &x: a)
        cin >> x;
    sort(a.begin(), a.end());
    cout << a.back() << ' ';
    auto it = upper_bound(a.begin(), a.end(), a.back() / 2);
    if (it == a.begin() || *prev(it) < a.back() - *it) 
        cout << *it << '\n';
    else 
        cout << *prev(it) << '\n';
}


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

using Vertex = int;
using Weight = long long;
struct Edge{Vertex from, to; Weight weight;};
using Graph = vector<vector<Edge>>;

vector<Vertex> centroid(const Graph& G) {
  vector<Vertex> res;
  vector<int> size(G.size(), 1);
  function<int(Vertex, Vertex)> dfs = [&](Vertex cur, Vertex pre) {
    auto ok = true;
    for(auto e: G[cur]) if(e.to != pre) {
      size[cur] += dfs(e.to, e.from);
      if(G.size() / 2 < size[e.to]) ok = false;
    }
    if(G.size() / 2 < G.size() - size[cur]) ok = false;
    if(ok) res.emplace_back(cur);
    return size[cur];
  };
  dfs(0, 0);
  return res;
}

Weight single(const auto& G, auto root) {
  Weight res = 0;
  vector<int> size(G.size(), 1);
  function<int(Vertex, Vertex)> dfs = [&](Vertex cur, Vertex pre) {
    for(auto e: G[cur]) if(e.to != pre) {
      size[cur] += dfs(e.to, e.from);
      res += 2 * size[e.to] * e.weight;
    }
    return size[cur];
  };
  dfs(root, root);
  Weight w = 1e9;
  for(auto e: G[root]) w = min(w, e.weight);
  return res - w;
}

Weight twin(const auto& G, auto u, auto v) {
  Weight res = 0;
  vector<int> size(G.size(), 1);
  function<int(Vertex, Vertex)> dfs = [&](Vertex cur, Vertex pre) {
    for(auto e: G[cur]) if(e.to != pre) {
      size[cur] += dfs(e.to, e.from);
      res += 2 * size[e.to] * e.weight;
    }
    return size[cur];
  };
  dfs(u, v);
  dfs(v, u);
  for(auto e: G[u]) if(e.to == v) res += e.weight * (G.size() - 1);
  return res;
}

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

  Graph G(N);
  for(auto i = 1; i < N; ++i) {
    Vertex A, B; Weight C;
    cin >> A >> B >> C;
    --A; --B;
    G[A].push_back({A, B, C});
    G[B].push_back({B, A, C});
  }

  auto V = centroid(G);
  if(V.size() == 1) cout << single(G, V.front()) << endl;
  else              cout << twin(G, V.front(), V.back()) << endl;
}


Measured memory_bytes: 14968
#include<bits/stdc++.h>
using namespace std;
long long mask, mod = 1e9+7;
int n;
long long count(vector<vector<long long> > &dp,int msk, int p, vector<vector<bool> > &v){
    if(msk == mask){
      //  cout<<"dddddd "<<endl;
        return 1;
    }
    if(dp[msk][p] != -1)
        return dp[msk][p];
    long long ans=0;
    for(int a=0; a<n; a++){

        long long tt = (msk & (1<<a));
       // cout<<p<<" "<<tt<<endl;
        if(tt==0 && v[a][p]){
       //     cout<<"sdfsd "<<endl;
            ans += count(dp,(msk|(1<<a)),p+1,v);
        }
    }
    ans = ans%mod;
    dp[msk][p] = ans;
    return ans;
}

int main()
{
   cin>>n;
   std::vector<vector<bool> > v(n+1, std::vector<bool> (n+1,false));
   for(int a=0; a<n; a++){
    for(int b= 0; b<n; b++){
        int tt;
        cin>>tt;
        if(tt)
            v[a][b] = true;
    }
   }
   mask = (1<<n)-1;

   std::vector<vector<long long> > dp(mask+2, vector<long long> (n+2, -1));
   long long ans = count(dp,0,0,v);
   cout<<ans<<endl;
   return 0;
}


Measured memory_bytes: 442624
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <ctype.h>
#include <math.h>
#include <stack>
#include <string>
#include <string.h>
using namespace std;
double PI = 3.1415926535897932;
long mod = 1000000007;

const long INF = 1e9 + 1;

int main() {
  int h,a;
  cin >> h >> a;
  
  int cnt = 0;
  while(h > 0) {
    h -= a;
    cnt++;
  }
  cout << cnt << endl;
}


Measured memory_bytes: 3596
#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#include <string.h>
using namespace std;

#define ALP 26
#define OFFSET 97
char        out[100000];

int main() {
    long long   N;
    long long   q, r;
    int         cnt = 0;
    
    cin >> N;
    while ( 1 ) {
        N--;
        q = N / ALP;
        r = N % ALP;
        out[cnt] = r + OFFSET;
        cnt++;
        if ( q == 0 ) {
            break;
        }
        N = q;
    }
    
    for ( int ii = cnt - 1; ii >= 0; ii-- ) {
        cout << out[ii];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 3652
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>

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

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    int X;
    cin >> X;
    
    X = X-400;
    for(int i=1; i<=8; i++){
        if(X-i*200<0){
            cout << 8-(i-1) << endl;
         	break;
        }
    }
    
    return 0;
}


Measured memory_bytes: 3188
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    static void Main(string[] args)
    {
        string[] str = Console.ReadLine().Split(' ');
        int x = int.Parse(str[0]);
        int y = int.Parse(str[1]);

        if(x == 2 && y == 2){
            Console.WriteLine("Yes");
        }else if((x == 4 || x == 6 || x == 9 || x == 11) && (y == 4 || y == 6 || y == 9 || y == 11)){
            Console.WriteLine("Yes");
        }else if((x != 4 && x != 6 && x != 9 && x != 11 && x != 2) && (y != 4 && y != 6 && y != 9 && y != 11 && y != 2)){
            Console.WriteLine("Yes");
        }else{
            Console.WriteLine("No");
        }
    }
}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef deque<int> di;
typedef pair<int,int> pi;
#define pb push_back
#define mp make_pair
#define mh make_heap
#define pf push_front
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define INF 1000000000
#define FOR(i,a,b) for(ll i=a;i<b;i++)


int main()
{
    //freopen("contest.txt","r",stdin);
    //freopen("contest.txt","w",stdout);
    IOS
    int x;
    cin>>x;
    if(x>=30)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;


    return 0;
}


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

using namespace std;

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt=0;
    for(int i=0;i<n-2;i++){
        if(s[i]=='A' && s[i+1]=='B' && s[i+2]=='C'){
            cnt++;
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
s = {i+1 for i in range(-101,101)}
#print(s)
x, n =map(int,input().split())
 
if n == 0:
  print(x)
  exit()
  
il = list(map(int,input().split()))
 
for i in range(n):
  s.discard(il[i])
s = list(s)
s.sort()
#print(s)
 
absmin = 10000000
ans = 0
 
for i in range(len(s)):
  j = abs(x-int(s[i]))
  if j < absmin:
    ans = s[i]
    absmin = j
    if j == 0:
      break
 
print(ans)

Measured memory_bytes: 62064
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#define _USE_MATH_DEFINES
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0,1,0,-1 };
const ll dy[4] = { -1, 0, 1,0 };
const ll INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
double mysqrt(double x) {
	double l = 0, r = x;
	for (int i = 0; i < 64; ++i) {
		double m = (l + r) / 2.0;
		if (m*m < x)l = m;
		else r = m;
	}
	return l;
}
///////////////////////////////////////

ll N;
ll D[100100];
ll cnt[100100];
int main() {
	cin >> N;
	REP(i, 100100)cnt[i] = 0;
	REP(i, N) {
		cin >> D[i];
		if (i != 0 && D[i] == 0) {
			cout << 0 << endl;
			return 0;
		}
		cnt[D[i]]++;
	}
	ll ans = 1;
	ll  sum = 1;
	if (D[0] != 0)cout << 0 << endl;
	else {
		for (ll i = 1; i < N; ++i) {
			if (cnt[i] == 0) {
				ans = 0;
			}
			ll key = cnt[i];
			while (key != 0) {
				ans *= cnt[i - 1];
				ans %= 998244353;
				key--;
			}
			ans %= 998244353;
			sum += cnt[i];
			if (sum == N)break;
		}
		ans %= (ll)998244353;
		cout << ans << endl;
	}

	return 0;
}


Measured memory_bytes: 1792
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>

const int INF = 1000000009;
const long LINF = 1123456789012345678;

int n, m;
int p[100005];
std::vector<int> edge[100005];
int col[100005];
bool seen[100005];

/*
void check(int a, int b){//a.vis, b.parent
	if(!able[a].empty()){
		for(auto i = able[a].begin(); i != able[a].end(); i++){
			able[b].insert(*i);
		}
		return;
	}
	seen[a] = true;
	for(int i = 0; i < edge[a].size(); i++){
		if(seen[
		
		
		
	for(int i = 0; i < edge[a].size(); i++){
		int b = edge[a][i];
		if(seen[b] && able[b].size() > 1){
			for(auto it = able[b].begin(); it != able[b].end(); it++){
				able[a].insert(*it);
			}
		}else if(seen[b]){
			continue;
		}else{
			
			
	for(int i = 0; i < edge[a].size(); i++){
		int b = edge[a][i];
		if(seen[b]){
			
//*/
			
void check(int a, int color){
	if(col[a] == 0){
		col[a] = color;
		for(int i = 0; i < edge[a].size(); i++){
			check(edge[a][i], color);
		}
	}
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++){
		scanf("%d", &p[i]);
	}
	for(int i = 0; i < m; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	int c = 1;
	for(int i = 1; i <= n; i++){
		if(col[i] == 0){
			check(i, c);
			c++;
		}
	}
	/*
	for(int i = 1; i <= n; i++){
		printf("%d ", col[i]);
	}
	//*/
	int ans = 0;
	for(int i = 1; i <= n; i++){
		if(col[i] == col[p[i]]){
			ans++;
		}
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 9472