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

#define ll long long
#define mp make_pair
#define pb push_back
#define loop(i, n)      for(int i = 0 ; i < n ; ++i)
#define rloop(i, n)     for(int i = int(n)-1 ; i >= 0 ; --i)
#define loopOne(i, n)   for(int i = 1 ; i <= n; ++i)
#define range(i, a, b)  for(int i = int(a) ; i <= int(b) ; ++i)
#define sz(x)   int(x.size())

void GO(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
const ll N = 1e5+100, OO = 1e9;
int mx = -OO, mn = OO;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int a[N], b[N], c[N], n, memo[N][4];

int Solve(int idx, int prev){
    // 0 for a, 1 for b, 2 for c
    if(idx == n)    return 0;
    if(memo[idx][prev] != -1)   return memo[idx][prev];

    int res = -OO;
    if(prev == 0){  // The previous one was 'A'
        memo[idx][prev] = max(b[idx] + Solve(idx+1, 1), c[idx] + Solve(idx+1, 2));
    }else if(prev == 1){  // The previous one was 'b'
        memo[idx][prev] = max(a[idx] + Solve(idx+1, 0), c[idx] + Solve(idx+1, 2));
    }else if(prev == 2){  // The previous one was 'c'
        memo[idx][prev] = max(b[idx] + Solve(idx+1, 1), a[idx] + Solve(idx+1, 0));
    }else{
        memo[idx][prev] = max(max(a[idx] + Solve(idx+1, 0), b[idx] + Solve(idx+1, 1)), c[idx] + Solve(idx+1, 2));
    }
    return memo[idx][prev];
}
int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    GO();
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        scanf("%d %d %d", a+i, b+i, c+i);
    }
    memset(memo, -1, sizeof(memo));
    printf("%d", Solve(0, 3));
    return 0;
}

Measured memory_bytes: 12820
#include <bits/stdc++.h>
#include <algorithm>
#include <math.h>
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define INF 999999999
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

using llong = long long;
using namespace std;

int main(){
    int r;
    cin >> r;
    cout << 3*r*r << endl;
}

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

int main(int n) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x = i;
        if (x%3 == 0) {
            cout << " " << i;
        }
        else {
            while (x != 0) {
                if (x%10 == 3) {
                    cout << " " << i;
                    break;
                }
                x /= 10;
            }
        }
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 3108
#include <iostream>
#include <string.h>

using namespace std;

int main()
{
    int n, b;
    cin>>n;
    string s[n];
    char a[20];
    int v[n];
    for(int i=0; i<n; i++){
        cin>>a;
        v[i]=strlen(a);
        s[i]=a;
    }
    for(int i=1; i<n; i++){
        for(int j=0; j<i; j++){
            if(s[i]==s[j]){
                cout<<"No";
                return 0;
            }
        }
        if(s[i][0]!=s[i-1][v[i-1]-1]){
            cout<<"No";
            return 0;
        }
    }
    cout<<"Yes";

    return 0;
}


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

typedef long long i64;
#define rep(i,s,e) for(int i = (s);i <= (e);i++)

int n;

i64 a[100010];
i64 b[100010];

int main()
{
	cin >> n;
	rep(i,1,n) cin >> a[i] >> b[i];

	reverse(a + 1,a + n + 1);
	reverse(b + 1,b + n + 1);

	i64 sum = 0;

	rep(i,1,n)
	{
		i64 cou = (b[i] - ((a[i] + sum) % b[i])) % b[i];
		sum += cou;
	}

	cout << sum << endl;
	return 0;
}
	

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
string s;
int a[100010],n,vis[100010],ans[100010];
int main()
{
	cin>>s;
	n=s.size();
	for(int i=0;i<n;++i) {
		if(s[i]=='L') a[i+1]=-1;
		else a[i+1]=1;
	}
	for(int i=1;i<n;++i)
		if(a[i]==1&&a[i+1]==-1) {
			ans[i]=ans[i+1]=1;
			int pos=i-1;
			while(a[pos]==1) {
				ans[i+(i-pos)%2]++;
				pos--;
			}
			pos=i+2;
			while(a[pos]==-1) {
				ans[i+1-(pos-(i+1))%2]++;
				pos++;
			}
		}
	for(int i=1;i<=n;++i) printf("%d ",ans[i]);
	return 0;
}

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

using namespace std;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}

const int maxn = 1e5 + 50;

char s[maxn] , t[maxn];
int lens , lent , s1[maxn] , s2[maxn];

int main( int argc , char * argv[] ){
	scanf( "%s%s" , s + 1 , t + 1 );
	lens = strlen( s + 1 ) , lent = strlen( t + 1 );
	for(int i = 1 ; i <= lens ; ++ i)
		s1[i] = s1[i - 1] + ( s[i] == 'A' );
	for(int i = 1 ; i <= lent ; ++ i)
		s2[i] = s2[i - 1] + ( t[i] == 'A' );
	int Q;
	scanf( "%d" , & Q );
	while( Q -- ){
		int l1 = read() , r1 = read() , l2 = read() , r2 = read();
		int a = s1[r1] - s1[l1 - 1] , b = (r1 - l1 + 1) - a;
		int c = s2[r2] - s2[l2 - 1] , d = (r2 - l2 + 1) - c;
		if( ( c + 2 * d - a - 2 * b ) % 3 == 0 || ( 2 * c + d - 2 * a - b ) % 3 == 0 )
			puts( "YES" );
		else
			puts( "NO" );
	}
    return 0;
}

Measured memory_bytes: 1536
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<cmath>

#define REP(i,n) for (int i = 0; (i) < (n); ++ (i))
#define FOR(i,n) for (int i = 1; (i) <= (n); ++ (i))
#define dump(x)  cout << #x << " = " << (x) << endl;
#define pb push_back
#define int long long

const int INF = 1e18;
const int MOD = 1e9+7;
//const lint LINF = 1e18;
const double eps = 0.000000001;//もとの値の10^(-16)まで

using namespace std;

//typedef pair<int, int> P;
//priority_queue< P, vector<P>, greater<P> > q;//ダイクストラの時、greaterで小さい順
//cout << fixed << setprecision(10) << ans << endl;

int extgcd(int a, int b, int &x, int &y) {
    int g = a;
    x = 1;
    y = 0;
    if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
    return g;
}

int mod_fact(int n,int p,int& e){
  e = 0;
  if(n==0) return 1;
  int res = mod_fact(n/p,p,e);
  e += n/p;
  if(n/p%2 != 0){
    //n!(mod p)を求める
    int t = 1;
    for(int i=1;i<=n;i++){
      t *= i;
      t %= p;
    }
    //ここまで
    return res*(p-t)%p;
  }
  //n!(mod p)を求める
  int t2=1;
  for(int i=1;i<=n;i++){
    t2 *= i;
    t2 %= p;
  }
  //ここまで
  return res * t2%p;
}

int mod_inverse(int a,int m){
  int x,y;
  extgcd(a,m,x,y);
  return (m+x%m) %m;
}

int mod_comb(int n,int k,int p){
  if(n<0||k<0||n<k) return 0;
  int e1,e2,e3;
  int a1 = mod_fact(n,p,e1),a2 = mod_fact(k,p,e2),a3 = mod_fact(n-k,p,e3);
  if(e1>e2+e3) return 0;
  return a1 * mod_inverse(a2*a3%p,p)%p;
}



signed main(){

    int x,y;
    cin >> x >> y;
    if((x+y)%3!=0){
        cout << 0 << endl;
        return 0;
    }
    int z = (x+y)/3;
    int z2 = min(x,y) - z;
    if(z2<0){
        cout << 0 << endl;
        return 0;
    }
    int ans;
    ans = mod_comb(z,z2,MOD)%MOD;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n,p,q,t,x;
    string s,ss;
    vector<ll>v;
    deque<ll>dq;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        v.push_back(x);
    }
    sort(v.begin(),v.end(),greater<int>());
    t=0;
    t+=v[0]/2;
    for(int i=1;i<n;i++)
    {
        t+=v[i];
    }
    cout<<t<<endl;
}





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

int main() {
  int N;
  cin>>N;
  vector<int> vec(N);
  for (int i = 0; i < N; i++) {
  cin >> vec.at(i);
  } 

  int ans=0;
  
  for(int i=0;i<N;i=i+2){
    if(vec.at(i) % 2 != 0) ans++;
  }
  
  cout << ans << endl;
}


Measured memory_bytes: 3636
from math import *
l2,angle2 = map(int,raw_input().split(","))
x_now = 0
y_now = l2
angle_now = 0
while True:
    l1 = l2
    angle1 = angle2
    if l1==0 and angle1==0:
        break
    l2,angle2 = map(int,raw_input().split(","))
    angle_now += angle1
    rad = radians(angle_now)
    x = l2*sin(rad)
    y = l2*cos(rad)
    x_now += x
    y_now += y
print int(x_now)
print int(y_now)

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

using namespace std;

int main(){
  int N, M;
  cin >> N >> M;
  
  vector<vector<char>> I(N, vector<char>(N,'x'));
  vector<vector<char>> P(M, vector<char>(M,'x'));
  
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++) cin >> I[i][j];
  }
  
  for(int i = 0; i < M; i++){
    for(int j = 0; j < M; j++) cin >> P[i][j];
  }
  bool f = false;
  for(int sx = 0; sx < N-M+1; sx++){
    for(int sy = 0; sy < N-M+1; sy++){
      f = true;
      for(int i = 0; i < M; i++){
        for(int j = 0; j < M;j++){
          if(I[sx+i][sy+j] != P[i][j]){
            f = false;
          }
        }
      }
      if(f) break;
    }
    if(f)break;
  }
  if(f) cout << "Yes";
  else cout << "No";
}


Measured memory_bytes: 256
#![allow(non_snake_case)]
use std::io;

fn main() {
    let sin = io::stdin();
    let mut cnt = 1;
    loop {
        let mut buf = String::new();
        sin.read_line(&mut buf).ok();
        let x: i32 = buf.trim().parse().unwrap();
        if x == 0 {
            break;
        }
        println!("Case {}: {}", cnt, x);
        cnt += 1;
    }
}



Measured memory_bytes: 5040
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

ll hpow(ll x,ll y){
    ll ans=1;
    ll i=x;
    if(y==0)return 1;
    while(y>0){
        if(y%2==1){
            ans=(ans*i)%i_7;
        }
        i=(i*i)%i_7;
        y=y/2;
        
    }
    return ans;
}

string l;
ll n;

ll hoge(ll i){
    if(i==n){
        return 1;
    }
    if(l[i]=='0'){
        return hoge(i+1);
    }
    return (2*hoge(i+1)+hpow(3,n-1-i))%i_7;
    
}

int main(){
    cin>>l;
    n=l.size();
    ll ans=hoge(0);
    cout<<ans<<endl;
    
    return 0;
}


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

int main(){
	int N,A;
	int right,left;
	double K;
	int index_min,ans;
	vector<int> v;
	cin >> N >> K;

	for(int i=0; i<N; i++){
		cin >> A;
		v.push_back(A);
		if(A == 1) index_min = i+1;
	}
	if(N == K){
		cout << "1" << endl;
		return 0;
	}
	right = ceil((index_min-1)/(K-1));
	left = ceil((N-index_min)/(K-1));
	ans = right + left;
	for(int i=1; i<K-1; i++){
		if(index_min-i-1 <= 0) right = 0;
		else right = ceil((index_min-i-1)/(K-1));

		if(N-index_min-(K-1-i) <= 0) left = 0;
		else left = ceil((N-index_min-(K-1-i))/(K-1));
		ans = min(ans, right + left + 1);
	}
	cout << ans << endl;

}


Measured memory_bytes: 892
#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>

#define rep(i,n) for(int i=0;i<n;i++)
#define llint long long int
#define vvint vector<vector<int>>
#define vint vector<int>

using namespace std;

int main() {
	int a;
	cin >> a;
	vint t(a,0);
	int cnt=0;
	rep(i, a) {
		cin >> t[i];
		cnt += t[i];
	}
	int b;
	cin >> b;
	rep(i, b) {
		int p, x;
		cin >> p >> x;
		cout << cnt - t[p - 1] + x << endl;
	}
	return 0;
}

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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define ALL(x) x.begin(),x.end()
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

typedef long long ll;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }


void compute() {

}

int main() {
  int n;
  cin >> n;
  double sum = 0;
  double a;
  rep(i,n) {
    cin >> a;
    sum += ( 1.0 / a );
  }
  sum = 1.0 / sum;
  printf("%.10f\n",sum);
  compute();
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,z;
int cost[30005];
int submask[30005];
int dp[5000][3001];
int solve(int mask,int index)
{
    if(index==m)
    {
        if(mask==pow(2,n)-1)
        return 0;
        else
        return 1000000000;
    }
    if(dp[mask][index]!=-1)
    return dp[mask][index];
    int ans=min(solve(mask,index+1),solve(mask|submask[index],index+1)+cost[index]);
    return dp[mask][index]=ans;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        cin>>x>>y;
        cost[i]=x;
        submask[i]=0;
        while(y--)
        {
            cin>>z;
            submask[i]+=(1<<(z-1));
        }
    }
    memset(dp,-1,sizeof dp);
    int ans=solve(0,0);
    if(ans==1000000000)
    cout<<-1<<'\n';
    else
    cout<<ans<<'\n';
}

Measured memory_bytes: 58880
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Program
{
    string Solve(int R, int G, int B)
    {
        return (R * 100 + G * 10 + B) % 4 == 0 ? "YES" : "NO";
    }

    static void Main()
    {
        var NX = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        Console.WriteLine(new Program().Solve(NX[0], NX[1], NX[2]));
    }
}

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

int main() {
	int a,b,c,rect=0,diamond=0;
	while (scanf("%d,%d,%d",&a,&b,&c) != EOF)
	{
		if (a*a+b*b == c*c)
			rect++;
		if (a==b)
			diamond++;
	}
	cout << rect << endl << diamond << endl;
	return 0;
}

Measured memory_bytes: 0
import sys
input=sys.stdin.readline
M,D=map(int,input().split())
if D<=19:
    print(0)
else:
    count=0
    for m in range(1,M+1):
        for d in range(20,D+1):
            d1=d%10
            d10=d//10
            if d1>=2 and d10>=2 and d1*d10==m:
                count+=1
    print(count)
    




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

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if(a == b && b == c && a%2 == 0) cout << -1 << endl;
    else {
        int ans = 0;
        while(a%2 == 0 && b%2 == 0 && c%2 == 0){
            int d = a;
            int e = b;
            int f = c;
            a = (e+f)/2;
            b = (f+d)/2;
            c = (d+e)/2;
            ans++;
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 256
from collections import*
from heapq import*
(n,m),a,*q=[[*map(int,o.split())]for o in open(0)]
t=[-1]*n
def r(x):
 while t[x]>=0:x=t[x]
 return x
def u(x,y):
 x,y=r(x),r(y)
 if x!=y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
d=defaultdict(list)
for x,y in q:u(x,y)
i=c=0;b=[]
for v in a:d[r(i)]+=v,;i+=1
if(k:=(n+~m)*2)<1:exit(print(0))
for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1
print(k>len(b)and'Impossible'or c+sum(sorted(b)[:k]))

Measured memory_bytes: 35604
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log,pi #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    R=I()
    print(pi*R*2)
if __name__ == '__main__':
    main()

Measured memory_bytes: 78108
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <numeric>
#include <algorithm>
using namespace std;
int K, X;
int main() {
	cin >> K >> X;
	for (int i = X - (K - 1);i <= X + (K - 1);i++) {
		cout << i << " ";
	}
	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <cstdio>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;

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

typedef long long ll;

const int Inf = 100100100;
const double EPS = 1e-9;

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

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

int bitCount(long bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    if (a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0) {
      cout << "Possible" << '\n';
    } else {
      cout << "Impossible" << '\n';
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define tam 310000
#define se second
#define fi first
#define forr(i,p,n) for(ll i=p;i<n;i++)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
ll mult(ll a,ll b, ll p=MOD){return ((a%p)*(b%p))%p;}
ll add(ll a, ll b, ll p=MOD){return (a%p + b%p)%p;}
typedef pair<ll,ll> ii;
ll fact[tam];
ll factinv[tam];
ll calc(ll n,ll m)
{
    
    return mult(mult(fact[n+m-2],factinv[n-1]),factinv[m-1]);
}
ll pot(ll base,ll exp)
{
    ll res=1LL,x=base%MOD;
    while(exp>0)
    {
        if (exp&1LL)
            res=mult(res,x);
        x=mult(x,x);
        exp/=2LL;
    }
    return res;
}
int main()
{
    ll tot,totinv;
    fact[0]=factinv[0]=tot=totinv=1;
    forr(i,1,tam)
    {
        tot=mult(tot,i);
        totinv=mult(totinv,pot(i,MOD-2));
        fact[i]=tot;
        factinv[i]=totinv;   
    }

    ll N,M,A,B;
    cin>>N>>M>>A>>B;
    ll resp=calc(N,M);
    //cout<<resp<<endl;
    forr(i,0,B)
    {
        resp-=mult(calc(N-A,i+1),calc(A,M-i));
        //cout<<endl;
        //cout<<mult(calc(N-A,i+1),calc(A,M-i))<<endl;
        resp%=MOD;
        resp+=MOD;
        resp%=MOD;
    }
    cout<<resp<<endl;
}   

Measured memory_bytes: 5120
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    const ll inf = LONG_LONG_MAX / 2 - 1;
    ll n;
    cin >> n;
    vector<vector<ll>> dp(n + 1, vector<ll>(3, 0));
    rep(i, n) {
        vector<ll> v(3);
        rep(j, 3) cin >> v[j];
        rep(j, 3) {
            rep(k, 3) {
                if (j == k) continue;
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][k] + v[j]);
            }
        }
    }
    ll ans = 0;
    rep(i, 3) ans = max(ans, dp[n][i]);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 5760
#include <iostream>

using namespace std;

#define INPUT_MIN 0
#define INPUT_MAX 100

int main()
{
	int a = 0, b = 0, c = 0;
	
	cin >> a;
	cin >> b;
	cin >> c;
	
	if( (INPUT_MIN > a) || (INPUT_MAX < a) )
	{
		return 1;
	}
	
	if( (INPUT_MIN > b) || (INPUT_MAX < b) )
	{
		return 1;
	}
	
	if( (INPUT_MIN > c) || (INPUT_MAX < c) )
	{
		return 1;
	}
	
	if(a >= c)
	{
		cout << "No" << endl;
	}
	else if( (a >= b) || (c <= b) )
	{
		cout << "No" << endl;
	}
	else
	{
		cout << "Yes" << endl;
	}
	
	return 0;
}


Measured memory_bytes: 3092
read N
read W
W=($W)

sum=$(echo ${W[@]} | tr ' ' "\n" | awk '{sum+=$1} END {print sum}')

ans=1000000

for ((i=0; i<$N; i++)); do
    left=${W[@]:0:$i}
    X=$(echo ${left[@]} | tr ' ' "\n" | awk '{sum+=$1} END {print sum}')
    Y=$((sum-X))
    
    V=$(perl -E "print abs($X-$Y)")
    if [ $V -lt $ans ]; then
        ans=$V
    fi
done

echo $ans


Measured memory_bytes: 992
#include<bits/stdc++.h>
#define int long long
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(a) a.size()
#define re return 
#define MP make_pair
#define pb push_back
#define pii pair<int,int>
#define se second
#define fi first
using namespace std;

signed main(){
	ios_base::sync_with_stdio(0);
	int n;
	cin>>n;
	vector<int> a(n);
	for(int i=0;i<n;i++) cin>>a[i];
	sort(all(a));
	cout<<a[n/2]-a[n/2-1]; 
	re 0;
}

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

void check(int g[9][9],bool f[9][9],int y,int x){
	for(int i=0; i<9; ++i){
		if(i!=y&&g[y][x]==g[i][x]){
			f[y][x]=false;
			f[i][x]=false;
			return;
		}
		if(i!=x&&g[y][x]==g[y][i]){
			f[y][x]=false;
			f[y][i]=false;
			return;
		}
	}
	int dy,dx;
	if(y<3) dy=0;
	else if(y<6) dy=3;
	else dy=6;
	if(x<3) dx=0;
	else if(x<6) dx=3;
	else dx=6;
	for(int i=0; i<3; ++i){
		for(int j=0; j<3; ++j){
			if(!(i+dy==y&&j+dx==x)&&g[y][x]==g[dy+i][dx+j]){
				f[y][x]=false;
				f[dy+i][dx+j]=false;
				return;
			}
		}
	}
}

int main(){
	int N;
	cin >> N;
	for(int i=0; i<N; ++i){
		int grids[9][9];
		bool ok[9][9];
		for(int j=0; j<9; ++j){
			for(int k=0; k<9; ++k){
				cin >> grids[j][k];
				ok[k][j]=true;
			}
		}
		for(int j=0; j<9; ++j){
			for(int k=0; k<9; ++k){
				if(ok[j][k]) check(grids,ok,j,k);
				if(!ok[j][k]) cout << '*';
				else cout << ' ';
				cout << grids[j][k];
				if(k==8) cout << endl;
			}
		}
		if(i!=N-1) cout << endl;
	}
	return 0;
}

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

int main() {
    string Ca, Cb;
    cin >> Ca >> Cb;
    if (Ca.at(0)==Cb.at(2) && Ca.at(2)==Cb.at(0) && Ca.at(1)==Cb.at(1)) cout << "YES\n";
    else cout <<"NO\n";
}

Measured memory_bytes: 256
use std::io::Read;

fn run() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let s = it.next().unwrap();
    let t = it.next().unwrap();
    let ans = s.chars().zip(t.chars()).filter(|&(a, b)| a == b).count();
    println!("{}", ans);
}

fn main() {
    run();
}

Measured memory_bytes: 4352
R,G,B,N=map(int,input().split())
ans=0
rr=N//R+1
gg=N//G+1
bb=N//B+1
for r in range(rr):
    for g in range(gg):
        if (N-R*r-G*g)%B==0 and N-R*r-G*g>=0:
            ans+=1
        elif N-R*r-G*g<0:
            pass
print(ans)

Measured memory_bytes: 40684
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctype.h>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define lengthof(x) (sizeof(x) / sizeof(*(x)))
#define FILL(ptr, value) FILL_((ptr), sizeof(ptr)/sizeof(value), (value))
template <typename T>
void FILL_(void * ptr, size_t size, T value){
  std::fill((T*)ptr, (T*)ptr+size, value);
}
//4方向ベクトル→↑←↓
int dx[] ={1,0,-1,0};
int dy[] ={0,-1,0,1};
typedef pair<int,int> P;
const int INF =100000000;
int n;
int d[110][110];
int main()
{
  int r,k;
  while(cin>>n){
    for(int i = 0;i < 110;i++){
      for(int j = 0;j <110;j++){
	d[i][j]= INF;
      }
    }
    for(int i = 1;i <=n;i++){
      cin>>r>>k;
      for(int j = 0;j < k;j++){
	int x;
	cin>>x;
	d[r][x] = 1;
      }
    }
    for(int k = 1;k <=n;k++){
      for(int i = 1;i <=n;i++){
	for(int j = 1;j <=n;j++){
	  d[i][j] =min(d[i][j],d[i][k]+d[k][j]);
	}
      }
    }
    int p;
    cin>>p;
    int s1,d1,v1;
    for(int i = 0;i <p;i++){
      cin>>s1>>d1>>v1;
      if(d[s1][d1]+1<=v1){
	cout <<d[s1][d1]+1<<endl;
      }else{
	cout <<"NA"<<endl;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 1212
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

const (
	initialBufSize = 100000
	maxBufSize     = 10000000
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, initialBufSize), maxBufSize)
	defer wt.Flush()

	n := nextInt()
	l := nextInts(n)
	sort.Sort(sort.IntSlice(l))

	less := func(i, j, k int) bool {
		return l[i]+l[j] > l[k]
	}
	ok := func(i, j, k int) bool {
		return less(i, j, k) && less(j, k, i) && less(k, i, j)
	}

	ans := 0
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if l[i] == l[j] {
				continue
			}
			for k := j + 1; k < n; k++ {
				if l[j] == l[k] {
					continue
				}
				if ok(i, j, k) {
					ans++
				}
			}
		}
	}

	puts(ans)
}


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


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

//C++14 (GCC 5.4.1)
int main() {
    int N,Q;
    cin >>N>>Q;
    string S;
    cin >>S;

    vector<int> l(Q),r(Q);
    rep(i,Q) cin >> l[i]>>r[i];
    vector<int> howAC(N,0);
    //-----------------------------------
    rep(i,N-1){
        if(S[i]=='A' && S[i+1]=='C'){
            howAC[i+1]=howAC[i]+1;
        }else{
            howAC[i+1]=howAC[i];
        }
    }
    int ans=0;
    rep(i,Q){
        cout<<howAC[r[i]-1] - howAC[l[i]-1]<<endl;
    }

    return (0);
}

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

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

int H,W;
char S[50][50];

int di[] = {1,0,-1,0};
int dj[] = {0,1,0,-1};

int search(int si, int sj, int ti, int tj){
    int d[50][50];
    memset(d,-1,sizeof(d));
    queue<P> que;
    que.push(P(si,sj));
    d[si][sj] = 0;
    while(que.size()){
        P p = que.front(); que.pop();
        //cout << d[p.first][p.second] << " " << si << " " << sj << endl;
        for (int i = 0;i < 4;i++){
            int ni = p.first+di[i];
            int nj = p.second+dj[i];
            //cout << ni << " " << nj << S[ni][nj] << " " << d[ni][nj] << endl;
            if(S[ni][nj] != '#' && d[ni][nj] == -1){
                //cout << 'A' << endl;
                que.push(P(ni,nj));
                d[ni][nj] = d[p.first][p.second]+1;
            }
        }
    }
    return d[ti][tj];
}

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

    cin >> H >> W;

    for (int i = 0;i < 50;i++){
        for (int j = 0;j < 50;j++){
            S[i][j] = '#';
        }
    }

    for (int i = 0;i < H;i++){
        for (int j = 0;j < W;j++){
            cin >> S[i+1][j+1];
        }
    }

    int ans = 0;

    for (int si = 1;si <= H;si++){
        for (int sj = 1;sj <= W;sj++){
            for (int ti = 1;ti <= H;ti++){
                for (int tj = 1;tj <= W;tj++){
                    if(S[si][sj] != '#' && S[ti][tj] != '#')
                        ans = max(search(si,sj,ti,tj),ans);
                }
            }
        }
    }

    cout << ans << endl;

    return 0;

}

Measured memory_bytes: 256
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
ll dp[2001][2001],n,a,ans;
vector<P> v;
int main(void){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a;
        v.push_back({a,i});
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    for(int i=0;i<n;i++){
        dp[i+1][0]=dp[i][0]+v[i].first*abs(v[i].second-i);
        dp[0][i+1]=dp[0][i]+v[i].first*abs(n-v[i].second-1-i);
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<n;j++){
            if(i+j>n)continue;
            dp[i][j]=max(dp[i-1][j]+v[i+j-1].first*abs(v[i+j-1].second-i+1),dp[i][j-1]+v[i+j-1].first*abs(n-v[i+j-1].second-1-j+1));
        }
    }
    for(int i=0;i<=n;i++){
        ans=max(ans,dp[i][n-i]);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 26328
#include<stdio.h>
int main()
{
    int n,m,i,j,sum=0,c;
    scanf("%d", &n);
    int a[n];
    for(i=0;i<n;i++)
    {
        scanf("%d", &a[i]);
    }
    scanf("%d", &m);
    int b[m][2];
    for(i=0;i<m;i++)
    {
        scanf("%d %d", &b[i][0],&b[i][1]);
    }
    for(i=0;i<m;i++)
    {
        sum=0;
        for(j=0;j+1<b[i][0];j++)
        {
            sum=sum+a[j];
        }
        sum=sum+b[i][1];
        for(j=b[i][0];j<n;j++)
        {
            sum=sum+a[j];
        }
        printf("%d\n", sum);
    }
    return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<climits>
using namespace std;
#define ll long long
int main() {
  ll N=0;cin>>N;
  ll VAL=0;cin>>VAL;
  ll V=0;
  vector<vector<ll>> inp(N,vector<ll>(2));
  for(ll i=0;i<N;i++) {
  	cin>>inp[i][0]>>inp[i][1];
    V+=inp[i][1];
  }
  vector<ll> dp(V+1,INT_MAX);
  dp[0]=0;
  for(ll i=0;i<N;i++) {
    for(ll j=V-inp[i][1];j>=0;j--) {
    	dp[j+inp[i][1]]=min(dp[j+inp[i][1]],dp[j]+inp[i][0]);
    }
  }
  //for(ll i=0;i<N;i++){for(ll j=0;j<=VAL;j++)cout<<dp[i][j]<<" ";cout<<endl;}
  //for(int i=0;i<V;i++) cout<<dp[i]<<" ";
  //cout<<endl;
  for(ll i=V;i>=0;i--) {
  	if(dp[i]<=VAL) {cout<<i<<endl;break;}
  }
  return 0;
}

Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Text.RegularExpressions;

namespace CODEFEST2016C {
    class Program {

        static void Main(string[] args) {
            var hw = Console.ReadLine();
            var H = int.Parse(hw.Split(' ')[0]);
            var W = int.Parse(hw.Split(' ')[1]);
            var preLastMark = -1;
            var FIELD = new List<string>();

            for(int i = 0; i < H; i++) {
                FIELD.Add(Console.ReadLine());
            }
            foreach(var NowLine in FIELD) {
                var firstMark = NowLine.IndexOf('#');
                int j = firstMark;
                if(j < NowLine.Length - 1) {
                    while(NowLine[j + 1] == '#') {
                        j++;
                        if(NowLine.Length - 1 == j) {
                            break;
                        }
                    }
                }

                //左戻り
                if(firstMark < preLastMark) {
                    Console.WriteLine("Impossible");
                    return;
                }

                preLastMark = NowLine.LastIndexOf('#');

                //上戻り
                if(j != preLastMark) {
                    Console.WriteLine("Impossible");
                    return;
                }
            }

            Console.WriteLine("Possible");
        }

        static int Minny(int a, int b) {
            if(a < b)
                return a;
            else
                return b;
        }
    }
}


Measured memory_bytes: 2776
#include<iostream>
#include<algorithm>
using namespace std;
//白'.',黒'#'
int main(){
  int h, w;
  char a[100][100];
  int check_g[100] = {0},check_r[100] = {0};
  cin >> h >> w;
  
  for(int i=0;i < h;i++){
    for(int j=0;j < w;j++){
      cin >> a[i][j];
      if(a[i][j] == '.'){
        check_g[i]++;
        check_r[j]++; 
      }
    }
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
     if((check_g[i] != w) && (check_r[j] != h)){
       cout << a[i][j];
     }
    }
    if(check_g[i] != w)
      cout << endl;
  }
}


Measured memory_bytes: 256
a,b = gets.split.map(&:to_i)
if (a>=3 && b>=3)
	puts (a-2)*(b-2)
elsif (a == 2 || b == 2)
	puts 0
elsif (a == 1 && b == 1)
	puts 1
else
	puts [a,b].max - 2
end


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

typedef long long ll;
typedef double dd;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;

const int mx=1e6+11;
const double PI = acos(-1);
#define MOD 1000000007


#define nl '\n'
#define pb push_back
#define F first
#define S second
#define I insert
#define mp make_pair

#define sz(x) x.size()
#define tt int t; cin>>t; while(t--)
#define lo(i,a,b) for(int i=a;i<b;i++)
#define be(a) (a).begin(),(a).end()
#define rbe(a) (a).rbegin(),(a).rend()
#define mem(a,b) memset(a,b,sizeof(a))

#define su ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define frac cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);

#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
void faltu () {            cerr << endl;}
template < typename T, typename ... hello>void faltu( T arg, const hello &... rest) {cerr << arg << ' ';faltu(rest...);}


int main()
{
   su;
   map<int,int>mp;
   int n,m,k,a,cnt=0;
   cin>>n>>m;
   lo(i,0,n)
   {
     cin>>k;
     while(k--)
     {
       cin>>a;
       mp[a]++;
     }
   }
   lo(i,0,m+1)
   {
     if(mp[i]==n)
      cnt++;
   }
   cout<<cnt<<nl;
   return 0;
}


Measured memory_bytes: 3660
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define pi 3.141592653589793238
#define int long long
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


signed main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);  
  cout.tie(0);   

  #ifndef ONLINE_JUDGE
      if(fopen("INPUT.txt","r"))
      {
      freopen ("INPUT.txt" , "r" , stdin);
      freopen ("OUTPUT.txt" , "w" , stdout);
      }
  #endif  

  int n,k,q;
  cin>>n>>k>>q;
  int a[n+2]={0};
  for(int i=1;i<=n;i++)
  {
    cin>>a[i];
  }
  int res=1e17;
  for(int i=1;i<=n;i++)
  {
    int mm=a[i];
    vector<vector<int> >temp;
    vector<int>z;
    for(int j=1;j<=n+1;j++)
    {
      if(a[j]>=mm)
      {
        z.push_back(a[j]);
      }
      else
      {
        if(z.size()>0)
        {
          temp.push_back(z);
          z.clear();
        }
      }
    }

    int l=a[i],r=1e9;
    int mn=1e10;
    while(l<=r)
    {
      int mid=l+(r-l)/2;
      int cnt=0;
      for(auto t:temp)
      {
        int tot=t.size();
        int count=0;
        for(auto j:t)
        {
          count+=(j>mid);
        }
        if(tot>=k)
        {
          tot-=k-1;
          count-=min(count,k-1);
          cnt+=(tot-count);
        }
      }
      if(cnt>=q)
      {
        mn=min(mn,mid);
        r=mid-1;
      }
      else
      {
        l=mid+1;
      }
    }
    if(mn!=1e10)
    {
      res=min(res,mn-a[i]);
    }
  }
  cout<<res;

}

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

int main(){
 	map<string, int> sheet;
 	map<string, int>::iterator it;
 	string aux;
 	int n, maxvote=0;

 	cin >> n;

 	while(n--){
        cin >> aux;
        sheet[aux]++;
 	}

 	for(it=sheet.begin();it!=sheet.end();it++){
        maxvote = max(maxvote, it->second);
 	}

 	for(it=sheet.begin();it!=sheet.end();it++){
        if(it->second == maxvote) cout << it->first << endl;
 	}
}


Measured memory_bytes: 25216
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = 1000000007

ans = 0
for i in range(n):
    cnt,tmp = 0,0
    for j in range(i+1, n):
        if a[i] > a[j] : cnt+=1
    for j in range(0, n):
        if a[i] > a[j] : tmp+=1
    ans += (2*cnt + (k-1)*tmp)*k//2
    ans %= mod

print(ans)

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

class HLDecomposition {
	vector<vector<int>> g;
	vector<int> vid, head, heavy, parent, depth, inv;
	int dfs(int curr, int prev) {
		parent[curr] = prev;
		int sub = 1, max_sub = 0;
		for (int next : g[curr]) if (next != prev) {
			depth[next] = depth[curr] + 1;
			int sub_next = dfs(next, curr);
			sub += sub_next;
			if (max_sub < sub_next) max_sub = sub_next, heavy[curr] = next;
		}
		return sub;
	}
	void bfs() {
		int k = 0;
		queue<int> q({ 0 });
		while (!q.empty()) {
			int h = q.front(); q.pop();
			for (int i = h; i != -1; i = heavy[i]) {
				vid[i] = k++;
				inv[vid[i]] = i;
				head[i] = h;
				for (int j : g[i]) if (j != parent[i] && j != heavy[i]) q.push(j);
			}
		}
	}
public:
	HLDecomposition(int n)
		: g(n), vid(n, -1), head(n), heavy(n, -1), parent(n), depth(n), inv(n) {}

	void add(int u, int v) {
		g[u].push_back(v);
		g[v].push_back(u);
	}
	void build() {
		dfs(0, -1);
		bfs();
	}
	int lca(int u, int v) {
		if (vid[u] > vid[v]) swap(u, v);
		if (head[u] == head[v]) return u;
		return lca(u, parent[head[v]]);
	}
};

int main()
{
	cin.sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n;
	HLDecomposition hl(n);
	for (int i = 0, k; i < n; i++) {
		cin >> k;
		for (int j = 0, c; j < k; j++) {
			cin >> c;
			if (c > i) hl.add(i, c);
		}
	}
	hl.build();
	cin >> q;
	for (int i = 0, u, v; i < q; i++) {
		cin >> u >> v;
		printf("%d\n", hl.lca(u, v));
	}
	return 0;
}

Measured memory_bytes: 14620
#include<iostream>
#include<utility>
#include<algorithm>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

int main(){
	int n,m;
	long long ans=0;
	cin>>n>>m;
	pll enedri[n];
	rep(i,n)cin>>enedri[i].first>>enedri[i].second;
	sort(enedri,enedri+n);
	rep(i,n){
		if(enedri[i].second>m){
			ans+=enedri[i].first*m;
			m=0;
		}else{
			ans+=enedri[i].first*enedri[i].second;
			m-=enedri[i].second;
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

using namespace std;

int main() {
  int A, B;
  cin >> A >> B;
  for (int i = 0; i < 1010; i++) {
    int C = i * 0.08, D = i * 0.1;
    if (A == C && B == D) {
      cout << i << endl;
      return 0;
    }
  }
  cout << -1 << endl;
}

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


typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

#define pb push_back
#define mp make_pair
#define snd second
#define fst first
#define debug printf("--%d--\n",__LINE__)
#define ll long long int

int main(void){
	int n;
	cin >> n;
	int a[n];
	for(int i=0;i<n;i++){
		cin >> a[i]; a[i]--;
	}
	int ret = 0;
	for(int i=0;i<n;i++){
		if (i < a[i] && a[a[i]]==i) ret++;
	}
	cout << ret << endl;
	
	
	
	return 0;
}


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

// repetition
#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

// container util
#define all(x) (x).begin(), (x).end()

// typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

// const value
// const ll MOD = 1e9 + 7;
// const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
// const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

// conversion
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
inline ll toLL(string s) {
  ll v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T> inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) {
  return a < b && (a = b, true);
}

template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) {
  return a > b && (a = b, true);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  int ans = n * (n - 1) / 2 + m * (m - 1) / 2;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace AtCoder
{
    class Program
    {
        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        private static CompareInfo ci = new System.Globalization.CultureInfo("ja-JP").CompareInfo;
        private static int Compare(string a, string b) { return ci.Compare(a, b, System.Globalization.CompareOptions.Ordinal); }

        static bool Solve(string S)
        {
            if (S.Length % 2 == 0)
            {
                for (int i = 0; i < S.Length; i += 2)
                {
                    if (S[i + 0] != 'h' || S[i + 1] != 'i') { return false; }
                }
                return true;
            }
            else
            {
                return false;
            }
        }

        static void Main(string[] args)
        {
            string S = Read();
            Console.WriteLine(Solve(S) ? "Yes" : "No");
        }
    }
}


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

int ans(int A, int B, int C)
{
    int tA,tB,tC;
    int ans = 0;
    vector<int> equalCheckV(3);
    vector<int> equalCheckV2(3);
    while(A%2==0 && B%2==0 && C%2==0)
    {
        //cout << "debug A:" << A << " B:" << B << " C:" << C << endl;

        equalCheckV.clear();
        equalCheckV2.clear();
        
        tA = A;
        tB = B;
        tC = C;
        
        A = (tB+tC)/2;
        B = (tA+tC)/2;       
        C = (tA+tB)/2;
        
        equalCheckV = {A,B,C};
        equalCheckV2 = {tA,tB,tC};

        sort(equalCheckV.begin(), equalCheckV.end());
        sort(equalCheckV2.begin(), equalCheckV2.end());

        if( equalCheckV.at(0) == equalCheckV2.at(0) 
        && equalCheckV.at(1) == equalCheckV2.at(1)
        && equalCheckV.at(2) == equalCheckV2.at(2) )
        {
            return -1;
        }
        ++ans;
        //cout << "debug A:" << A << " B:" << B << " C:" << C << endl;
    }
    return ans;
}

int main()
{
    int A,B,C;
    while(cin >> A >> B >> C)
    {
        cout << ans(A,B,C) << endl;
    }
}

Measured memory_bytes: 256
S = gets.chomp.chars
T = gets.chomp.chars

if T.size > S.size
  puts 'UNRESTORABLE'
  exit 0
end

def fill(s)
  s.map { |ch| ch == '?' ? 'a' : ch }.join('')
end

(S.size - T.size).downto(0) do |i|
  is_ok = true
  T.size.times do |j|
    s = S[i + j]
    t = T[j]
    next if s == '?'
    if s != t
      is_ok = false
      break
    end
  end
  if is_ok
    ans = (i == 0 ? '' : fill(S[0..(i - 1)])) \
      + T.join('') \
      + (i + T.size == S.size ? '' : fill(S[(i + T.size)..-1]))
    puts ans
    exit 0
  end
end
puts 'UNRESTORABLE'

Measured memory_bytes: 1788
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define Q int t; scanf("%d", &t); for(int q=1; q<=t; q++)
typedef long long int lli;
typedef pair<int, int> pi;
typedef pair<int, pi> node;
#define oset tree<pi, null_type,greater<pi>, rb_tree_tag,tree_order_statistics_node_update>


int main()
{
    lli n;
    cin >> n;
    n--;
    lli a[n+1], b[n];
    for(auto &x: b) cin >> x;
    lli ans = 0;
    ans += b[0];
    for(int i=0; i<n-1; i++){
        ans += min(b[i], b[i+1]);
    }
    ans += b[n-1];

    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 3612
n , k = map(int, input().split())
a = list(map(int,input().split()))
v = [0]*(n+1)
v[1]=1
v2=[1]
i=0
step=1

while True:
    if v[a[i]]!=0:
        loop=step-v[a[i]]+1
        loopstart=v[a[i]]
        break
    else:
        step+=1
        v[a[i]]=step
        v2.append(a[i])
        i=a[i]-1
ans = (k-loopstart+2)%loop
if ans ==0:
    ans+=loop
if k<loopstart:
    print(v2[k])
    exit()
v2=v2[loopstart-1:]
print(v2[ans-1])


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

int main() {
  ll n,x,ans=1e9;
  cin>>n>>x;
  vector<ll> d(n);
  for(ll i=0; i<n; i++) {
    ll a; cin>>a;
    d[i] = abs(x - a);
    ans = min(d[i],ans);
  }
  for(ll i=0; i<n; i++){
    ans = __gcd(ans,d[i]);
  }
  cout<<ans;
}

Measured memory_bytes: 1024
function Main(input) {
  input = input.replace(/\n/g, ' ');
  input = input.split(" ");
  var A = Number(input[0]);
  input.shift();
  var all=input[0];
  for(var i=1;i<A;i++){
    all^=Number(input[i]);
  }
  var ans = "";
  for(var i=0;i<A;i++){
    ans+=all^Number(input[i]);
    ans+=" ";
  }
  console.log(ans);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 78260