akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream> 
#include<unordered_map>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
typedef vector<int> vi;
typedef vector<ll> vl;

const int inf = numeric_limits<int>::max() >> 2;
const ll linf = numeric_limits<ll>::max() >> 2;
const ull ulinf = numeric_limits<ull>::max() >> 2;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define umap(i,j) unordered_map<i,j>
#define P(p) cout<<(p)<<endl
#define PS(p) cout<<(p)<< " "
#define IN cin >> 
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i = (m-1); i >= (int)(n); i--)
#define inrep(n,a) for(int i = 0; i < (int)(n); i++)cin >> a[i];
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.end(), v.begin());
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - a) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}

//ll ncr[100][100];
//ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

//ll npr[100][100]={};
//ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

//ll nHr(int n,int r){ret nCr(n+r-1,r);}

///////////////////////////////////////////////////////////////////////////

ll n;
set<string> s;

void dfs(string t,int f){
    if(f > 0 && stoll(t) > n)return;
    
    if(f == 7){
	s.it(t);
    }

    dfs(t + "3",f | 0x01);
    dfs(t + "5",f | 0x02);
    dfs(t + "7",f | 0x04);

    return;
}
int main(){
    
    cin >> n;

    dfs("",0);
    P(sz(s));
    return  0;
}


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

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


Measured memory_bytes: 256
s = list(input())
t = []
ans = 10**9 + 10

if s.count(s[0]) == len(s):
    print(0)
    exit()

for i in set(s):
    c = i
    j = 0
    n = s
    t = []
    while j >= 0:
        for k in range(1, len(n)):
            if c == n[k-1] and c != n[k]:
                t.append(c)
            elif c != n[k-1] and c == n[k]:
                t.append(c)
            elif c != n[k-1] != n[k]:
                t.append(n[k-1])
            else:
                t.append(n[k])
        if t.count(c) == len(t):
            cnt = j + 1
            if cnt < ans:
                ans = cnt
            break
        else:
            n = t
            t = []
        j += 1

print(ans)

Measured memory_bytes: 3064
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars};
#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
	input! {
		a: usize,
		mut b: usize,
		mut c: usize,
		k: usize,
	}

	for _i in 0..k {
		if a >= b {
			b *= 2;
		}
		else if b >= c {
			c *= 2;
		}
		if a < b && b < c {
			println!("Yes");
			return;
		}
	}
	println!("No");
}



Measured memory_bytes: 2100
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(sc.hasNext()){
			int n = sc.nextInt();
			int q = sc.nextInt();
			int[] sum = new int[n+1];	
			
			int a, v;
			int pans = Integer.MAX_VALUE;
			int max = 0;
			for(int i=0;i<q;i++){
				a = sc.nextInt();
				v = sc.nextInt();
				sum[a] += v;
				
				if(pans==a){
					max = 0;
					for(int j=1;j<=n;j++) max = Math.max(max, sum[j]); 
	                for(int j=1;j<=n;j++){
	                    if(sum[j]==max){
	                    	pans = j;
	                        System.out.println(pans + " " + max);
	                        break;
	                    }
	                }	
				}else{
				
					if(max>sum[a]){
						System.out.println(pans + " " + max);
					}else if(max<sum[a]){
						max = sum[a];
						pans = a;
						System.out.println(pans + " " + max);
					}else if(max==sum[a]){
						if(pans<a){
							System.out.println(pans + " " + max);
						}else{
							pans = a;
							System.out.println(pans + " " + max);
						}
					}
					
				}
			}
		}
	}	
}

Measured memory_bytes: 75464
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<string>
#include<cstdlib>
//#include<cmath>
using namespace std;

int main(void)
{
	string s;
	int a,b,m;
	stack<int>A;
	while (cin >> s) {
		switch (static_cast<char>(s[0])) {
			case '+':a = A.top(); A.pop(); b = A.top(); A.pop(); m = a + b; A.push(m); break;
			case '-':a = A.top(); A.pop(); b = A.top(); A.pop(); m = b - a; A.push(m); break;
			case '*':a = A.top(); A.pop(); b = A.top(); A.pop(); m = a * b; A.push(m); break;
			default:A.push(atoi(s.c_str()));
		}
	}
	cout << A.top() << endl;
	return 0;
}


Measured memory_bytes: 3180
/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2020.08.17 01:44:21
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;


struct Dinic {
private:
    struct edge {
        int to;
        ll cap;
        int rev;
        bool isrev;
        int idx;
    };
    vector< vector< edge > > graph;
    vector< int > min_cost, iter;
    bool bfs(int s, int t) {
        min_cost.assign(graph.size(), -1);
        queue< int > que;
        min_cost[s] = 0;
        que.push(s);
        while (!que.empty() && min_cost[t] == -1) {
            int p = que.front();
            que.pop();
            for (auto &e : graph[p]) {
                if (e.cap > 0 && min_cost[e.to] == -1) {
                    min_cost[e.to] = min_cost[p] + 1;
                    que.push(e.to);
                }
            }
        }
        return min_cost[t] != -1;
    }
    ll dfs(int idx, const int t, ll flow) {
        if (idx == t) return flow;
        for (int &i = iter[idx]; i < graph[idx].size(); i++) {
            edge &e = graph[idx][i];
            if (e.cap > 0 && min_cost[idx] < min_cost[e.to]) {
                ll d = dfs(e.to, t, min(flow, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    graph[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
public:
    Dinic(int V) : graph(V) {}
    
    void add_edge(int from, int to, ll cap, int idx = -1) {
        graph[from].push_back({to, cap, (int)graph[to].size(), false, idx});
        graph[to].push_back({from, 0, (int)graph[from].size() - 1, true, idx});
    }
    
    ll max_flow(int s, int t) {
        ll flow = 0;
        while (bfs(s, t)) {
            iter.assign(graph.size(), 0);
            ll f = 0;
            while ((f = dfs(s, t, 1e9 + 6)) > 0) flow += f;
        }
        return flow;
    }
    void output() {
        for (int i = 0; i < graph.size(); i++) {
            for (auto &e : graph[i]) {
                if (e.isrev) continue;
                auto &rev_e = graph[e.to][e.rev];
                cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl;
            }
        }
    }
};
int main() {
    int h,w;cin >> h >> w;
    vector<string> s(h);
    Dinic g(h+w+2);
    for (int i = 0; i < h; i++) {
        cin >> s[i];
        for (int j = 0; j < w; j++) {
            if (s[i][j] == 'S') {
                g.add_edge(h+w,i,h*w+1);
                g.add_edge(h+w,h+j,h*w+1);
            }
            else if (s[i][j] == 'T') {
                g.add_edge(i,h+w+1,h*w+1);
                g.add_edge(h+j,h+w+1,h*w+1);
            }
            else if (s[i][j] == 'o') {
                g.add_edge(i,h+j,1);
                g.add_edge(h+j,i,1);
            }
        }
    }
    auto ans = g.max_flow(h+w,h+w+1);
    if (ans >= h*w+1) cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5088
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<pair<ll, ll>>> vvpll;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e13;
const ll MAX_N = 100010;

int main() {
    ll n, K;
    cin >> n >> K;

    vl a(n);
    rep(i, n) {
        cin >> a[i];
    }
    vl f(n);
    rep(i, n) {
        cin >> f[i];
    }
    sort(all(a));
    sort(rall(f));

    // メンバーをa[i]の昇順に、食べ物をf[i]の降順にソートし、メンバーiに食べ物iを割り当てる(この割り当て方を割り当てCと呼ぶ)のが最適であることを示す
    // ある二人のメンバーx,yの修行前の消化コストをA[x],A[y]、修行後の消化コストをB[x],B[y]、担当する食べ物の食べにくさをF[x],F[y]とおく
    // A[x] < A[y] かつ F[x] < F[y] が成り立つと仮定する
    // B[x] < B[y] のとき二人の担当する食べ物を入れ替えることで何も損することなく二人の担当をswapできる
    // B[x] >= B[y] のとき二人の担当する食べ物と修行後のコストを入れ替えることで何も損することなく二人の担当をswapできる
    // このswapを繰り返すと割り当てCになるので示された
    // 割り当てCのもとで判定問題「チーム全体の成績をx以下にできるか？」を二分探索で解く
    // メンバーiがx秒以下で完食するには担当する食べ物の食べにくさはf[i]なので、消化コストがfloor(x/f[i])以下になればよい
    // なので ( sum_{0 <= i < n} max(0, a[i] - floor(x/f[i])) ) <= K のときチーム全体の成績をx以下にできる

    ll left = -1;
    ll right = INF;
    while(right - left > 1) {
        ll mid = (left + right)/2;
        ll x = mid;
        ll y = 0;
        rep(i, n) {
            y += max(0LL, a[i] - x/f[i]);
        }
        if(y <= K) {
            right = mid;
        }
        else {
            left = mid;
        }
    }

    // チーム全体の成績はright以上なのでrightが答え
    out(right);
    re0;
}

Measured memory_bytes: 3328
#include <cstdio>
#include <climits>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <string>
#include <cstdio>
#include <climits>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
#define rep(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
long long MOD = 1000000007;
long long INF = 1000000000000000;

typedef long long ll;
typedef unsigned long long ull;

int main(void) {
  int n;
  string s, t;
  cin >> n;
  cin >> s >> t;
  rep(i, n) cout << s[i] << t[i];
  cout << endl;
}


Measured memory_bytes: 256
s = input()
ans = 'Yes'
for i in range(len(s)):

    if (i +1) % 2 == 0:
        if s[i] != 'L' and s[i] != 'U' and s[i] != 'D':
            ans = 'No'
            break
    else:
        if  s[i] != 'R' and s[i] != 'U' and s[i] != 'D':
            ans = 'No'
            break
print(ans)

Measured memory_bytes: 3060
import scala.io.StdIn

object Main extends App {
  val n = StdIn.readLine.toInt
  val s = StdIn.readLine
  val res = for {
    i <- 1 until s.length()
  } yield {
    val ar = s.toArray.splitAt(i)
    (ar._1 intersect ar._2).distinct.length
  }
  println(res.max)
}

Measured memory_bytes: 27416
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
	static void Main()
	{
		string[] input = Console.ReadLine().Split(' ');
		long a = long.Parse(input[0]);
		long b = long.Parse(input[1]);
    bool plus = false;
    long plusNum = 1;
    long answer = 0;

    if(b%4==1 || b%4==2)
    {
      plus = true;
    }
    if(((a-1)%4==1 || (a-1)%4==2) && a!=0)
    {
      plus = !plus;
    }
    if(plus) answer += 1;


    for(int i = 0; i < 45; i++)
    {
      plus = false;
      plusNum *= 2;
      if(b%(plusNum*2)>=plusNum && b%2==0) plus = true;
      if((a-1)%(plusNum*2)>=plusNum && (a-1)%2==0 && a!=0) plus = !plus;
      if(plus) answer += plusNum;
    }

		Console.WriteLine(answer);
	}
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define rrep(i, a, b) for (int i = a; i >= (b); i--)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <class T>
inline bool chmin(T& a, T b) {
   if (a > b) {
      a = b;
      return true;
   }
   return false;
}
template <class T>
inline bool chmax(T& a, T b) {
   if (a < b) {
      a = b;
      return true;
   }
   return false;
}
void hr() {
   cerr << "--------------" << endl;
}
const int INF = 1001001001;
const int MOD = 1000000007;
// const int MOD = 998244353;
struct edge {
   int to, cost;
};
int d[100005];
int main() {
   cin.tie(0);
   ios_base::sync_with_stdio(0);

   int V, E, s;
   cin >> V >> E >> s;
   vector<edge> G[V];
   rep(i, 0, E) {
      int u, v, dd;
      cin >> u >> v >> dd;
      G[u].push_back({v, dd});
   }

   priority_queue<P, vector<P>, greater<P>> que;
   fill(d, d + V, INF);
   d[s] = 0;
   que.push(P(d[s], s));
   while (!que.empty()) {
      P p = que.top();
      que.pop();
      int v = p.second;
      if (d[v] < p.first) continue;
      rep(i, 0, G[v].size()) {
         edge e = G[v][i];
         if (d[e.to] > d[v] + e.cost) {
            d[e.to] = d[v] + e.cost;
            que.push(P(d[e.to], e.to));
         }
      }
   }
   rep(i, 0, V) {
      if (d[i] == INF) {
         cout << "INF" << endl;
         continue;
      }
      cout << d[i] << endl;
   }
   return 0;
}


Measured memory_bytes: 12820
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define pcnt __builtin_popcount
#define show(x) cout<<#x<<" = "<<x<<endl;
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define fi first
#define se second
#define rng(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define sz(x) (int)(x).size()
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef set<int> si;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
typedef set<ll> sl;
typedef __int128_t lll;
typedef pair<lll,lll> plll;
typedef vector<lll> vlll;
template<typename T>string join(vector<T>&v)
{stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename A, size_t N, typename T>void Fill(A (&array)[N], const T&v)
{fill((T*)array,(T*)(array+N),v);}
template<typename T> T gcd(T a,T b){if(a>b)swap(a,b);for(;a>0;b%=a,swap(a,b));return b;}
ll modpow(lll a,lll n,ll m){if(a==0)return a;lll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
void dout(double d){printf("%.12f\n",d);}

const int iinf = 1e9;
const ll linf = 1e18;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-10;
ll n;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n;
  ll m = 0, s = 0, ans = 0, a = 1;
  FOR(i, 0, 17){
    ll c = n % (a*10) / a;
    s += c;
    if(c > 0) maxs(m, c + 9*i - s - 1);
    a *= 10;
    ans += c;
  }
  cout << ans + m << endl;
  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define endl "\n"
#define sz(x) ((ll)(x).size())
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define prt(x) cout << (x)
#define prtl(x) cout << (x) << endl
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define rrep(i,a,b) for(ll i=a; i>b; i--)
#define mp(a, b) make_pair(a, b)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define debug(v) cout << #v<< ": " << v <<endl;
using namespace std;
using vi = vector<int>;
using vll = vector<long long int>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vc = vector<char>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long int>>;
using vvc = vector<vector<char>>;
using ll = long long int;
using P = pair<long long int, long long int>;
using Map = map<long long int, long long int>;
ll INF = 1LL<<60;
ll M = 1000000007;

int main(){
    ll h, w; cin >> h >> w;
    vc g(h*w);
    map<char, ll> m;
    rep(i, 0, h*w){
        cin >> g[i];
        m[g[i]]++;
    }
    if(h%2 == 0&&w%2 == 0){
        bool b = true;
        for(auto x: m){
            if(x.second%4 != 0){
                b = false;
            }
        }
        if(b){
            prtl("Yes");
        }else{
            prtl("No");
        }
    }else if(h%2 == 1&&w%2 == 1){
        bool b = true;
        ll c = 0, cc = 0;
        for(auto x: m){
            if(x.second%2 != 0){
                c++;
                if(c > 1){
                    b = false;
                    break;
                }
                m[x.first]--;
            }
            if(x.second % 2 == 0&&x.second%4 != 0){
                cc++;
            }else{
                continue;
            }
        }
        if(b){
            if(cc <= (h+w-2)/2&&((h+w-2)/2-cc)%2 == 0){
                b = true;
            }else{
                b = false;
            }
        }
        if(b){
            prtl("Yes");
        }else{
            prtl("No");
        }
    }else{
        bool b = true;
        ll c = 0, cc = 0;
        for(auto x: m){
            if(x.second%2 != 0){
                b = false;
                break;
            }
            if(x.second % 2 == 0&&x.second%4 != 0){
                cc++;
            }else{
                continue;
            }
        }
        //prtl(cc);
        if(b){
            ll j;
            if(h%2 == 1){
                j = w;
            }else{
                j = h;
            }
            if(cc <= j/2&&(j/2-cc)%2 == 0){
                b = true;
            }else{
                b = false;
            }
        }
        if(b){
            prtl("Yes");
        }else{
            prtl("No");
        }
    }
}



Measured memory_bytes: 3620
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
using ll = long long;
using ld = long double;
using namespace std;
//const int INF = 7+(1e+9);
ll GCD(ll x, ll y)
{
    if (y == 0)
    {
        return x;
    }
    else
    {
        return GCD(y, x % y);
    }
}
ll LCM(ll x, ll y)
{
    return x / GCD(x, y) * y;
}
struct UnionFind
{
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    vector<ll> size;
    UnionFind(int N) : par(N)
    { //最初は全てが根であるとして初期化
        for (int i = 0; i < N; i++){
            par[i] = i;
            size.push_back(1);
        }
    }

    int root(int x)
    { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x)
            return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y)
    {                     // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry)
            return;   //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
        size[ry]+=size[rx];
       // cout<<size[rx]<<endl;
    }

    bool same(int x, int y)
    { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};
long long modinv(long long a, long long m)
{
    long long b = m, u = 1, v = 0;
    while (b)
    {
        long long t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0)
        u += m;
    return u;
}
ll MOD = 1e9 + 7;

int main()
{
    ll n,m;
    cin>>n>>m;
    UnionFind tree(n);
    vector<pair<ll,ll>> vec(m);
    for(int i=0;i<m;i++){
        ll a,b;
        cin>>a>>b;
        a--;
        b--;
        vec[i]=make_pair(a,b);
    }
    vector<ll> reg(m);
    ll sum=(n-1)*n/2;
    for(int i=m-1;i>=0;i--){
        reg[i]=sum;
        ll x=vec[i].first;ll y=vec[i].second;
        if(!tree.same(x,y)){
            sum-=tree.size[tree.root(x)]*tree.size[tree.root(y)];
            tree.unite(x,y);
        }
    }
    for(int i=0;i<reg.size();i++){
        cout<<reg[i]<<endl;
    }
 //   cout<<tree.size[tree.root(1)]<<endl;
}


Measured memory_bytes: 4980
#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
  int n,a,mini,ans=-(1<<30);
  scanf("%d %d",&n,&mini);
  for(int i=0;i<n-1;i++){
    scanf("%d",&a);
    if(a-mini>ans)ans=a-mini;
    if(mini>a)mini=a;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3240
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<numeric>
#include<limits>
#include <cstdint>
#include<stack>
#include<queue>
using namespace std;
#define ll long long int
#define rep(N) for(ll i=0;i<N;i++)
#define rep2(N1,N2) for(ll i=0;i<N1;i++)for(ll j=0;j<N2;j++)
#define rep3(N1,N2,N3)for(ll i=0;i<N1;i++)for(ll j=0;j<N2;j++)for(ll k=0;k<N3;k++)
#define For(i,N) for(ll i=0;i<N;i++)

void yn(bool b) {
	if (b)printf("yes\n");
	else printf("no\n");
}

void Yn(bool b) {
	if (b)printf("Yes\n");
	else printf("No\n");
}

void YN(bool b) {
	if (b)printf("YES\n");
	else printf("NO\n");
}

int ctoi(char c) {
	return c - '0';
}

ll kai(ll x) {
	ll a = 1;
	if (x <= 0)
		return 1;
	else {
		for (ll i = 0; i < x; i++)
			a = a * (i + 1);
		return a;
	}
}

ll rui(ll x, ll y) {
	ll a = 1;
	for (ll i = 0; i < y; i++)
		a = a * x;
	return a;
}
const int nmax = 150;
int cccc[nmax][nmax];
ll comb(ll n, ll k) {
	if (n < k) {
		cout << "error n<k" << endl;
		return -1;
	}
	if (cccc[n][k] > 0)return cccc[n][k];
	if (k == 0 || n == k)return 1;
	return cccc[n][k] = comb(n - 1, k - 1) + comb(n - 1, k);
}

ll keta(ll a) {
	ll i = 1;
	while (1) {
		if (a < pow((ll)10, i))
			return i;
		i++;
	}
}
vector<ll> v;
ll n, m;
//m進数全探索
ll inc(ll a = n - 1) {
	if (a == 0 && v[0] == m) {
		v[0] = -1;
		return v[0];
	}
	if (v[a] == m) {
		v[a] = 0;
		inc(a - 1);
		return v[a];
	}
	else {
		++v[a];
		return v[a];
	}
}

ll mod = 1000000007;

ll modkai(ll a) {
	ll ret = 1;
	rep(a) {
		ret *= (i + 1);
		ret %= mod;
	}
	return ret;
}

ll modpowl(ll a, ll b) {
	if (b == 0) {

		return 1;
	}
	if (b == 1) {

		return a;
	}
	if (b >= 2) {
		if (b % 2 == 0) {
			ll c = modpowl((a*a) % mod, b / 2);
			c = c % mod;

			return c;
		}
		else {
			ll c = (modpowl((a*a) % mod, b / 2) % mod)*a;
			c = c % mod;

			return c;
		}
	}
}
const int MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod%i] * (mod / i) % mod;
		finv[i] = finv[i - 1] * inv[i] % mod;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}

ll llpow(ll a, ll b) {
	if (b == 0) {

		return 1;
	}
	if (b == 1) {

		return a;
	}
	if (b >= 2) {
		if (b % 2 == 0) {
			ll c = llpow((a*a), b / 2);
			c = c;

			return c;
		}
		else {
			ll c = (llpow((a*a), b / 2))*a;
			c = c;

			return c;
		}
	}
}
std::vector<ll> Eratosthenes(ll N)
{
	std::vector<bool> is_prime(N + 1);
	for (ll i = 0; i <= N; i++)
	{
		is_prime[i] = true;
	}
	std::vector<ll> P;
	for (ll i = 2; i <= N; i++)
	{
		if (is_prime[i])
		{
			for (ll j = 2 * i; j <= N; j += i)
			{
				is_prime[j] = false;
			}
			P.emplace_back(i);
		}
	}
	return P;
}

int main() {
	cout.precision(20);
	string S;
	cin >> S;
	rep(S.size()) {
		if (S[i] == '?')S[i] = 'D';
	}
	cout << S;
}

Measured memory_bytes: 3856
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
const ll maxn=1e5+100;
ll a[maxn];
void solve(){
	ios::sync_with_stdio(false);
	cin >> n;
	for (ll i=1;i<=n;i++) cin >> a[i];
	ll left=0,ans=0;
	for (ll i=1;i<=n;i++){
		if (a[i]>=left){
			a[i]-=left;
			ans+=left;
		}
		ans+=a[i]/2;
		left=a[i]%2;
	}
	cout << ans;
}
int main(){
//	freopen("1.in","r",stdin);
	solve();
	return 0;
}
/*
4
4 0 3 2
8
2 0 1 6 0 8 2 1
*/

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

using namespace std;

#define REP(i, n) for(int i = 0; i < (n); i++)
#define SREP(i, s) for(int i = 0; i < (s.length()); i++)
#define SORT(v, n) sort(v, v+n);
#define GSORT(v, n) sort(v, v+n, greater<int>())

int main(){
	int n;
	int s=0;
	int t=0;
	cin >> n;
	int w[n];
	REP(i,n) cin >> w[i];
	int mins = 1000;
	REP(i,n){
		s+=w[i];
	}
	REP(i,n){
		REP(j,i){
			t+=w[j];
		}
		mins=min(mins,abs(t-(s-t)));
		t=0;
	}
	cout << mins << endl;


}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    long a, b;
    long g, l;
    long r, s, t;

    while (scanf("%ld %ld", &a, &b) != EOF) {
        r = a > b ? a : b;
        s = a < b ? a : b;
        while (r % s != 0) {
            t = r;
            r = s;
            s = t % r;
        }
        g = s;
        l = a * (b / g);
        printf("%ld %ld\n", g, l);
    }

    return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
const int M=2e3+10;
typedef struct{
	int now;
	int bat[M];
}player;
player a[M];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n-1;j++){
			scanf("%d",&a[i].bat[j]);
		}
		a[i].now=1;
	}
	int num=n*(n-1)/2;
	bool flag=0;
	int ans=0;
	int i=0;
	while(i<num){
		flag=0;
		bool used[M]={0};
		for(int j=1;j<=n;j++){
			if(a[j].now!=n&&used[j]==0){
				int t1=a[j].bat[a[j].now];
				if(a[t1].now!=n&&used[t1]==0){
					int t2=a[t1].bat[a[t1].now];
					if(t2==j){
						a[t1].now++;
						a[j].now++;
						used[t1]=1;
						used[j]=1;
						flag=1;
						i++;
					}
				}
			}
		}
		ans++;
		if(flag==0){
			break;
		}
	}
	if(flag){
		printf("%d\n",ans);
	}else{
		printf("-1\n");
	}
}


Measured memory_bytes: 8448
// When you are hungry for something and you're determined and you're focused 
// and you're committed to something it's hard to surrender, isn't it?

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ll long long 
#define int ll
#define mod 1000000007
#define mod1 1000000006
#define modi 998244353
#define setbit(x) __builtin_popcount(x)
#define fff(i,n) for(int i=0;i<n;i++)
#define ff first
#define ss second
#define pb push_back
vector<ll> vi[300005];
int color[100005];
ll pa[500005];
ll si[500005];
#define pb push_back
bool visi[1000005]={false};
bool is[100005];
ll fac[10000001];
ll prime[400005];
ll bit[100005];
const long double eps = 1.0e-14;      // allowable error
#define fio ios_base::sync_with_stdio(false); cin.tie(NULL);
 
 
void fact(){
    fac[0]=1;
    for(int i=1;i<=10000000;i++){
        fac[i]=(fac[i-1]*i)%mod;
    }
    return ;
}
void sieve(){
    prime[0]=0;
    prime[1]=0;
    for(int i=2;i<400005;i++){
        prime[i]=1;
    }
    for(int i=2;i*i<400005;i++){
        if(prime[i]==1){
            for(int j=i*i;j<400005;j+=i){
                prime[j]=0;
            }
        }
    }
    
}
 
ll power(ll n , ll p ){
    if(p==0)
        return 1;
    
    ll res = power((n*n)%mod,p/2);
    if(p%2==1)
        res = (n*res)%mod;
    
    return res;
}
 
 
void upd(ll i,ll val,ll n) {
    for(;i<=n;i+=i&(-i))
        bit[i]+=val;
}
 
ll qry(ll i) {
    ll sum=0;
    for(;i>0;i-=i&(-i))
        sum+=bit[i];
    return sum;
}
 
 
ll fin(ll u) {
    if(pa[u]==u)
        return u;
    return fin(pa[u]);
}
 
void uni(ll u,ll v) {
    ll p1=fin(u);
    ll p2=fin(v);
    if(p1==p2)
        return;
    if(si[p1]<si[p2])
        swap(p1,p2);
    si[p1]+=si[p2];
    pa[p2]=p1;
    return;
}
 
int32_t main() {
    fio
    
    int n;
    cin >> n;
    map<string,int> m;
    string a[n];
    fff(i,n) {
        string s;cin >> s;
        a[i]=s;
        sort(all(s));
        m[s]++;
    }
    
    int ans=0;
    
    fff(i,n) {
        string s=a[i];
        sort(all(s));
        if(m[s]>0) {
            int t=m[s];
            int x = (t*(t-1))/2;
            ans+=x;
            m[s]=0;
        }
    }
    cout << ans;
    
	return 0;
    
}

Measured memory_bytes: 25344
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<complex>
#include<cfloat>
#include<cassert>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()
#define EPS (1e-10)
using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef complex<double> P;

#define PI (3.1415926535)
#define EPS (1e-10)

int main(){
  int n; cin>>n;
  while(n-->0){
    double x1,x2,x3,x4,y1,y2,y3,y4;
    cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
    double xx1 = x1 - x2;
    double yy1 = y1 - y2;
    double xx2 = x3 - x4;
    double yy2 = y3 - y4;
    if(xx1 == 0 && xx2 == 0){
      cout << "YES" << endl;
      continue;
    }
    double r = xx1 / xx2;
    yy2 *= r;
    if(abs(yy1-yy2) < EPS)
      cout << "YES" << endl;
    else
      cout << "NO" << endl;
  }
  
  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a[4];
  for(int i=0;i<3;i++){
    cin>>a[i];
  }
  sort(a,a+3);
  if(a[0]==5&&a[1]==5&&a[2]==7)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  return(0);
}

Measured memory_bytes: 764
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

import static java.lang.Integer.parseInt;

/**
 * Hamming Distance
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		String[] words;

		int N, D;
		char[] X;

		N = parseInt(br.readLine());
		X = br.readLine().toCharArray();
		D = parseInt(br.readLine());

		char[] ans = Arrays.copyOf(X, N);

		for (int i = 0; i < N; i++) {
			if (D == 0) break;
			if (X[i] == '0') {
				ans[i] = '1';
				D--;
			}
		}

		for (int i = N - 1; i >= 0; i--) {
			if (D == 0) break;
			if (X[i] == '1') {
				ans[i] = '0';
				D--;
			}
		}

		System.out.println(String.valueOf(ans));

	} //end main
}

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

int main() {
	string s; cin >> s;
	char now = s[0];
	int ans = 0;
	for (int i = 1; i < s.size(); i++) if (now != s[i]) {
		ans++, now = s[i];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 512
/*  ex7_1
    supercomputerjoi    */

#include <stdio.h>

typedef struct point{
    int x_elem;
    int y_elem;
}point;

point move(point coor, int x, int y);

int main(){

    point coor1, coor2, coor3, coor4;
    
    // input x1 y1
    scanf("%d %d", &coor1.x_elem, &coor1.y_elem);
    // input x2 y2
    scanf("%d %d", &coor2.x_elem, &coor2.y_elem);

    // calculate x3 y3
    coor3 = move(coor2, coor1.y_elem - coor2.y_elem, coor2.x_elem - coor1.x_elem);

    // calculate x4 y4
    coor4 = move(coor3, coor2.y_elem - coor3.y_elem, coor3.x_elem - coor2.x_elem);

    // output answer
    printf("%d %d %d %d\n", coor3.x_elem, coor3.y_elem, coor4.x_elem, coor4.y_elem);

    return 0;
}

point move(point coor, int x, int y){

    // add x_elem x
    coor.x_elem += x;
    // add y_elem y
    coor.y_elem += y;

    return coor;
}

Measured memory_bytes: 1708
N = int(input())
Alist=list(map(int, input().split()))
numdic = {}
for i in Alist:
    if i in numdic:
        numdic[i] += 1
    else:
        numdic[i] = 1
Apple = 0
for i in numdic.values():
    Apple += i*(i-1)//2
for i in Alist:
    tmp = Apple
    tmp -= (numdic[i]-1)
    print(tmp)

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


#define li          long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define pb          push_back
#define sz(v)       ((li)(v).size())
#define bgn(v)      ((v).begin())
#define eend(v)     ((v).end())
#define allof(v)    (v).begin(), (v).end()
#define dodp(v,n)       memset(v,(li)n,sizeof(v))
#define bit(n)      (1ll<<(li)(n))
#define mp(a,b)     make_pair(a,b)
#define rin rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)     idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)       idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)        idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)   for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)      idp p2((x).F, (x).S)
#define dump(x,n)   idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)  idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)    idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)   idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)   rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)   rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;

li a[303030];

li l[101010], r[101010];

int main() {
    li n;
    cin >> n;
    rep(i, 3 * n) {
        cin >> a[i];
    }
    priority_queue<li> pq_l, pq_r;
    li sum_l = 0;
    li sum_r = 0;
    rin{
        pq_l.push(-a[i]);
        sum_l += a[i];
        pq_r.push(a[2 * n + i]);
        sum_r += a[2 * n + i];
    }

    l[0] = sum_l;
    r[0] = sum_r;
    rin {
        li mi = -pq_l.top();
        if (mi < a[n + i]) {
            sum_l = sum_l - mi + a[n + i];
            pq_l.pop();
            pq_l.push(-a[n + i]);
        }
        l[i + 1] = sum_l;
    }

    rin{
        li ma = pq_r.top();
        li now = a[2 * n - 1 - i];
        if (ma > now) {
            sum_r = sum_r - ma + now;
            pq_r.pop();
            pq_r.push(now);
        }
        r[i + 1] = sum_r;
    }
    li res = -INF;
    rep(i, n + 1) {
        //p4(i, n - i, l[i], r[n - i]);
        res = max(res, l[i] - r[n - i]);
    }
    cout << res << endl;


    return 0;
}

Measured memory_bytes: 5996
void main() {
    int x = readln.chomp.to!int;
    writeln(x < 1200 ? "ABC" : "ARC");
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.container;
import std.typecons;
import std.ascii;
import std.uni;

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

int main(){
  long long a;
  string b;
  static int keta[3];
  
  cin >> a >> b;
  for(int i=0;i<b.size();i++){
    if(i==0)keta[0]=b[i]-'0';
    if(i==2)keta[1]=b[i]-'0';
    if(i==3)keta[2]=b[i]-'0';
  }
  // rep(i, 3)cout << "[" << b[i] << "]";
  long long ans = a*100*keta[0]+a*10*keta[1]+a*keta[2];
  cout << ans/100;

  return 0;
}


Measured memory_bytes: 3580
#include <stdio.h>

int main(void){
    int num[100]={0};
    int num2[100]={0};
    int i=0,j;
    int a=0;
    while(scanf("%d",&num[i])!=EOF){
        i++;
    }
    for(i=0;i<100;i++){
        for(j=0;j<100;j++){
            if(num[j]==i){
                num2[i]++;
            }
        }
        if(num2[i]>a){
            a=num2[i];
        }
    }
    for(i=0;i<100;i++){
        if(num2[i]==a){
            printf("%d\n",i);
        }
    }
    return 0;
}

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

using namespace std;
#define rep(x, n)          for (int x = 0; x < n; x++)
#define REP(x, a, b)       for (int x = a; x <= b; x++)
#define all(container)     (container).begin(), container.end()
#define rall(container)    (container).rbegin(), container.rend()
#define sz(container)      (int) (container).size()
#define pb                 push_back
#define eb                 emplace_back

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

#ifdef LOCAL_DEFINE
    #include "DEBUG.hpp"
#else
    #define dmp(...) 0
#endif
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

int main(void) {
    int n;
    scanf("%d",&n);
    int las=n%10;
    if(las==2||las==4||las==5||las==7||las==9)
        puts("hon");
    else if (las==0||las==1||las==6||las==8)
        puts("pon");
    else 
        puts("bon");
    return 0;
}

Measured memory_bytes: 3760
n, k = map(int,input().split())
al = list(map(int,input().split()))
dics = {}
 
for i in range(n):
    if al[i] in dics:
        dics[al[i]] = dics[al[i]] + 1
    else:
        dics.update({al[i]:1})
        
counts = len(dics.values())
kesu = 0
sortv = list(sorted(list((dics.values()))))

i = counts
j = 0
while i > k:
    kesu = kesu + sortv[j]
    i = i - 1
    j = j + 1
print(kesu)


Measured memory_bytes: 32288
#include<bits/stdc++.h>
using namespace std;
long long a[200005],sum[200005];
int main(){
	long long n,ans=1e17;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	for(int i=1;i<n;i++){
		ans=min(ans,abs(sum[n]-2*sum[i]));
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3328
package main

import (
	"fmt"
)

const MOD = 1000000007
const HW = 200000

type INT int64

var fac [HW + 1]INT
var inv [HW + 1]INT

//var H, W, A, B INT = 1, 1, 1, 1

func init() {
	fac[0] = 1
	inv[0] = 1
	for i := INT(1); i <= HW; i++ {
		fac[i] = fac[i-1] * i % MOD
		_, x, _ := extEuclid(fac[i], MOD)
		inv[i] = mod(x)
	}
}

func main() {
	solve()
}

func solve() {
    H, W, A, B := input()
	var res INT
	for i := B; i < W; i++ {
		res += comb(i+H-A-1, i) * comb(A-1+W-i-1, W-i-1) % MOD
		res %= MOD
	}
	fmt.Println(res)
}

func input() (H, W, A, B INT) {
	fmt.Scan(&H, &W, &A, &B)
	return H, W, A, B
}


func extEuclid(a, b INT) (d INT, x INT, y INT) {
	if b == 0 {
		return a, 1, 0
	}
	var s, t INT
	d, s, t = extEuclid(b, a%b)
	x, y = t, s-(a/b)*t
	return d, x, y
}

func mod(a INT) INT {
	return (a%MOD + MOD) % MOD
}

func comb(n, k INT) INT {
	if n < 0 || n < k {
		return 0
	}
	return fac[n] * (inv[n-k] * inv[k] % MOD) % MOD
}


Measured memory_bytes: 3584
import java.io.*;
import java.util.*;
class Main{
	static final long MOD = 1_000_000_007; // 10^9+7
    static final int MAX = 2_147_483_646; // intMax 
    static final int INF = 1_000_000_000; // 10^9  
    public static void main(String[] args) throws Exception {
		hayami saori = new hayami();
		String[] s = saori.nextHayami().split("");
		int count = 0;
		for(int i = 0;i < s.length;i++){
			if(s[i].equals("o"))count++;
		}
		if(15-s.length+count >= 8){
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}

		saori.close();
    }
}

class hayami implements Closeable {
	private final InputStream in = System.in;
	private final byte[] hayami = new byte[1024];
	private int Hayami = 0;
	private int saori = 0;
	private boolean HayamiSaori() {
		if (Hayami < saori) {
			return true;
		}else{
			Hayami = 0;
			try {
				saori = in.read(hayami);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (saori <= 0) {
				return false;
			}
		}
		return true;
	}
	private int SaoriHayami() { 
		if (HayamiSaori()) {
            return hayami[Hayami++];
         }else{
             return -1;
         }
	}
	private static boolean hayami_saori(int hayami) { 
		return 33 <= hayami && hayami <= 126;
	}
	public boolean hayamisaori() { 
		while(HayamiSaori() && !hayami_saori(hayami[Hayami])) Hayami++; return HayamiSaori();
	}
	public String nextHayami() {
		if (!hayamisaori()) throw new NoSuchElementException();
		StringBuilder hayamin = new StringBuilder();
		int saori = SaoriHayami();
		while(hayami_saori(saori)) {
			hayamin.appendCodePoint(saori);
			saori = SaoriHayami();
		}
		return hayamin.toString();
	}
	public long saorihayami() {//nextLong
		if (!hayamisaori()) throw new NoSuchElementException();
		long hayami = 0;
		boolean misao = false;
		int saori = SaoriHayami();
		if (saori == '-') {
			misao = true;
			saori = SaoriHayami();
		}
		if (saori < '0' || '9' < saori) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= saori && saori <= '9') {
				hayami *= 10;
				hayami += saori - '0';
			}else if(saori == -1 || !hayami_saori(saori)){
				return misao ? -hayami : hayami;
			}else{
				throw new NumberFormatException();
			}
			saori = SaoriHayami();
		}
	}
	public int saori_hayami() {//nextInt
		long hayami = saorihayami();
		if (hayami < Integer.MIN_VALUE || hayami > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) hayami;
	}
	public double Hayamin() { //nextDouble
		return Double.parseDouble(nextHayami());
	}
	public void close() {
		try {
			in.close();
		} catch (IOException e) {
		}
    }
    
}

Measured memory_bytes: 21332
#include <bits/stdc++.h>
#include <math.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1001001001;
const int mINF = -1001001001;


int main() {
int n,l;
cin >> n >> l;
int m[n];
REP(i,n) cin >> m[i];
int count = 1;
int sum = 0;
REP(i,n) {
  sum += m[i];
  if(sum<=l) {
    count++;
  } else {
    break;
  }
}
cout << count << endl;
return 0;
}


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

using namespace std ; 

const int N = 1e6 +  7 ; 

long long n , ans ; 

int main(){
    ios_base::sync_with_stdio(0) ; 
    cin.tie(0) ; 
    //freopen("in.in" , "r" , stdin) ; 
    cin>>n ; 
    for(int i = 1 ; i <=n;i++){
        for(int j = 1 ;j <=n ;j++){
            for(int k = 1 ; k<= n;k++){
                int x = __gcd(i , __gcd(j , k)) ;
                ans+=x ; 
            }
        }
    }
    cout<<ans ; 
    return 0 ; 
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define pb push_back
#define deb(x) cout<<#x<<" "<<x<<endl;
#define deb2(x, y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<endl;
#define deb3(x, y, z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<endl;
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
template<class T, class U> inline void add_self(T &a, U b){a += b;if (a >= mod) a -= mod;if (a < 0) a += mod;}
template<class T, class U> inline void min_self(T &x, U y) { if (y < x) x = y; }
template<class T, class U> inline void max_self(T &x, U y) { if (y > x) x = y; }

template <typename T>void print(T v, bool show_index = false){int w = 2;if(show_index){for(int i=0; i<v.size(); i++)cout<<setw(w)<<i<<" ";cout<<endl;}for(auto i= v.begin(); i!=v.end(); i++)cout<<setw(w)<<*i<<" ";cout<<endl;}
template <typename T>void print_vv(T v){if(v.size()==0) {cout<<"Empty"<<endl; return;} int w = 3;cout<<setw(w)<<" ";for(int j=0; j<v[0].size(); j++)cout<<setw(w)<<j<<" ";cout<<endl;for(auto i= 0; i<v.size(); i++){cout<<i<<" {";for(auto j = 0; j!=v[i].size(); j++){cout<<setw(w)<<v[i][j]<<",";}cout<<"},"<<endl;}cout<<endl;}
template <class T, class U> void print_m(map<T,U> m, int w=3){if(m.empty()){cout<<"Empty"<<endl; return;}for(auto x: m)cout<<"("<<x.first<<": "<<x.second<<"),"<<endl;cout<<endl;}

int main(){
    int n,k;
    while(cin>>n>>k){
        vi dp(k+1); 
        vi a(n);
        forn(i,n) cin>>a[i];

        fore(stone,1,k+1){
            for(auto x: a){
                if(stone-x>=0 && !dp[stone-x]){
                    dp[stone] = 1;
                }
            }   
        }
        cout<<(dp[k] ? "First" : "Second")<<endl;
    }
    
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	
	int n, t; cin >> n >> t;
	vi h(n);
	rep(i, n) cin >> h[i];
	
	ll start = 0, interval = 0, count = inf;
	rep(i, n){
		start += h[i];
		interval = max(interval, (ll)h[i]);
		
		ll nct = (t - start) / interval + 1;
		if(start > t) nct = 0;
		
		count = min(count, nct);
		cout << count + 1 << endl;
	}
	return 0;
}

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

using namespace std;

int main ()
{
    std::locale loc;
  string a, b, c;
  cin >> a >> b >> c;
  char ar[10];
 for(int i=0;i<a.size();i++)
 {
     ar[i]=a[i];ar[i+1]=b[i];ar[i+2]=c[i];break;
 }
 cout<<toupper(ar[0],loc)<<toupper(ar[1],loc)<<toupper(ar[2],loc);
 
  return 0;
}


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

int main(){
  string S;
  cin >> S;
  string answer;
  for(int i=0;i<S.size();i++){
    if(S.at(i)!='B'){
      answer += S.at(i);
    }
    int N = answer.size();
    if(N>0){
      if(S.at(i)=='B'){
        answer.erase(answer.begin()+(N-1));
      }
    }
  }
  cout << answer << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>

int main(void)
{
 char str1[3];
 char str2[] = "9";

 scanf("%s",str1);

 if(strstr(str1,str2)!=NULL)
 {
   printf("Yes\n");
 }
 else
 {
  printf("No\n");
 }

return 0;
}

Measured memory_bytes: 128