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

using namespace std;
#define MOD 1000000007
#define pi 3.1415926535897932384626433832795028841971693993751058209749445923078164062
const int INF = 1e9;
#define ll long long
#define pb push_back
#define pf push_front
#define mp make_pair
#define mt make_tuple
#define ub upper_bound
#define lb lower_bound
#define popb pop_back()
#define popf pop_front()
#define ff first
#define ss second
#define vl vector<ll>
#define vi vector<int>
#define vs vector<string>
#define vll vector< pair<ll,ll> >
#define vii vector< pair<int,int> >
#define viii vector< tuple <int,int,int> >
#define vlll vector< tuple <ll,ll,ll> >
#define vvl vector<vector<ll>>
#define vv vector<vector<int>>
#define all(v) v.begin(),v.end()
#define sqrt sqrtl
#define cbrt cbrtl
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mapcl map<char,ll>
#define mapci map<char,int>
#define mapll map<ll,ll>
#define mapii map<int,int>
#define seti set<int>
ifstream fin("input.txt");
ofstream fout("output.txt");
#define FOR(i, l, r) for (int i = int(l); i < int(r); ++i)
#define print(a)       for(auto x : a) cout << x << " "; cout << "\n"
#define print1(a)      for(auto x : a) cout << x.ff << " " << x.ss << "\n"
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << "\n"


ll fast_exp(ll base, ll exp) {ll res=1;while(exp>0) {if(exp%2==1) res=(res*base)%MOD;base=(base*base)%MOD;exp/=2;}return res%MOD;}
int gcd(int a,int b){while (a&&b)a>b?a%=b:b%=a;return a+b;}
int val(char c){if (c >= '0' && c <= '9')return (int)c - '0';else return (int)c - 'A' + 10;}
ll pows(int a , int b){ll res=1;for(int i=0; i<b; ++i){res*=a;}return res;}
ll logx(ll base, ll num){int cnt=0;while(num!=1){num/=base; ++cnt;}return cnt;}
ll divisibles(ll a, ll b, ll m){if(a%m==0)return (b/m)-(a/m)+1;else return (b/m)-(a/m);}// in [a,b]
string bitstring(int n, int size){string s;while(n){s+=(n%2)+'0';n/=2;}while(s.size()<size){s+='0';}reverse(all(s));return s;}
// dsu start

vi root(200001,0);
vi size(200001,1);
int find(int x){while(x!=root[x])x = root[x];return x;}
bool same(int a,int b){return find(a)==find(b);}
void unite(int a, int b){a = find(a);b = find(b);if(size[a]<size[b])swap(a,b);size[a] += size[b];root[b] = a;}

// dsu end
vi vis(200001,0);
vi adj[200001];

int main()
{	
    std::ios::sync_with_stdio(false);
    //string bitstring = std::bitset< 3 >( 7 ).to_string(); <bits> (num)
    //srand(time(0));
    //cin.tie(NULL);
    //cout.tie(NULL);
 	ll n,m;
 	cin>>n>>m;
 	vii vec1,vec2;

 	for(int i=0; i<n; ++i)
 	{
 		int a,b;
 		cin>>a>>b;
 		vec1.pb(mp(a,b));
 	}   
 	for(int i=0; i<m; ++i)
 	{
 		int a,b;
 		cin>>a>>b;
 		vec2.pb(mp(a,b));
 	}   
 	for(int i=0; i<n; ++i)
 	{
 		int sx = vec1[i].ff;
 		int sy = vec1[i].ss;
 		int idx = -1;
 		int dis = INF;
 		for(int j=0; j<m; ++j)
 		{
 			int dx = vec2[j].ff;
 			int dy = vec2[j].ss;
 			int x = abs(sx-dx) + abs(sy-dy);
 			if(x<dis)
 			{
 				dis = x;
 				idx = j;
 			}
 		}
 		cout<<idx+1<<"\n";
 	}   
}

Measured memory_bytes: 7296
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()

int main() {
  //
  int n, a, b, c, d;
  cin >> n >> a >> b >> c >> d;
  a--;
  b--;
  c--;
  d--;
  string s;
  cin >> s;

  for (int i = a; i < c; i++) {
    if (s[i] == '#' && s[i + 1] == '#') {
      cout << "No" << endl;
      return 0;
    }
  }
  for (int i = b; i < d; i++) {
    if (s[i] == '#' && s[i + 1] == '#') {
      cout << "No" << endl;
      return 0;
    }
  }

  if (d < c) {
    bool three = false;
    for (int i = b - 1; i <= d - 1; i++) {
      if (s[i] == '.' && s[i + 1] == '.' && s[i + 2] == '.') {
        three = true;
        break;
      }
    }
    if (!three) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}


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

using namespace std;

int seq[500];
int main (){
	int n;
	int soma = 0;
	
	cin >> n;
	
	int i;
	long double media = 0, dif = 999999;
	
	for(i = 0; i < n; i++){
		cin >> seq[i];
		soma += seq[i];
	}
	media = soma;
	media = media/n;
	int ind = 0;
	for(i = 0; i < n; i++){
		if( abs(seq[i] - media) < dif){
			dif = abs(seq[i] - media); 
			ind = i;
		}
	}
	
	cout << ind << endl;
}


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

int N;
const int maxN=10;
vector<int> Ps(maxN);
vector<int> Qs(maxN);

int num;
int perm[maxN];
bool used[maxN];
int pnum,qnum;

bool check(vector<int> V){
    bool c=true;
    /*
    for(int i=0;i<N;i++){
        cout << perm[i] << ' ';
    }
    cout << endl;
    */
    for(int i=0;i<N;i++){
        if(perm[i]!=V[i]) c=false;
    }
    return c;
}

void permutation(int pos,int n){
    if(pos==n){
        num++;
        if(check(Ps)) pnum=num;
        if(check(Qs)) qnum=num;
    }
    for(int i=1;i<=n;i++){
        if(!used[i]){
            perm[pos]=i;
            used[i]=true;
            permutation(pos+1,n);
            used[i]=false;
        }
    }

}

int main(){
    cin >> N;
    for(int i=0;i<N;i++) cin >> Ps[i];
    for(int i=0;i<N;i++) cin >> Qs[i];
    num=0;
    permutation(0,N);
    //cout << num << endl;
    //cout << pnum << qnum << endl;
    cout << abs(pnum-qnum) << endl;
    return 0;

}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
/*
using ll = long long;
using P = pair<int, int>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
*/
int fib[50];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    fib[0] = 1;
    fib[1] = 1;
    for(int i = 2; i <= n; i++){
        fib[i] = fib[i-1] + fib[i-2];
    }
    cout << fib[n] << endl;
    return 0;
}


Measured memory_bytes: 3204
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

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

Measured memory_bytes: 256
# https://atcoder.jp/contests/abc075/tasks/abc075_c?lang=ja
# unionfind or 深さ優先探索


class UnionFind:
    def __init__(self, n):
        self.n = n
        # 各要素の親要素の番号を格納するリスト
        # 根がルートの時は、グループの要素数を格納　最初は全て根で要素数1
        self.parents = [-1] * n

    # 再帰 groupの根を返す
    # 経路圧縮あり
    def find(self, x):
        # 0より小さい場合は根
        if self.parents[x] < 0:
            # indexを返す
            return x
        else:
            # 根になるまで親を辿る
            # 経路圧縮 根のindexが全ての親に再帰的につく
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # groupを併合
    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)

        # 最初から統合されている
        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x
        # 根のグループ数を追加 xの方グループの要素数が多い前提なので多い方に寄せる
        self.parents[x] += self.parents[y]
        # 親(根)のindexを入れる
        self.parents[y] = x

    # 根が同じか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 全ての根の要素を返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())


n, m = map(int, input().split())

edge = []
for _ in range(m):
    a, b = map(int, input().split())
    edge.append((a - 1, b - 1))

ans = 0
for i in range(m):
    uf = UnionFind(n)
    for j, (a, b) in enumerate(edge):
        if i == j:
            continue
        uf.union(a, b)
    if uf.group_count() == 1:
        ans += 1

print(m - ans)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int n,ans,a[50000];
int main(){
  while(cin>>n&&n){
    ans=1e9;
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    for(int i=1;i<n;i++)ans=min(ans,a[i]-a[i-1]);
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 3068
h, w = map(int, input().split())
mat = []
mat.append("."*(w+2))
for i in range(h):
  s = input()
  mat.append("."+s+".")
mat.append("."*(w+2))

for x in range(1,w+1):
  for y in range(1, h+1):
    if mat[y][x] == "#" and mat[y-1][x] == "." and mat[y+1][x] == "." and mat[y][x-1] == "." and mat[y][x+1] == ".":
      print("No")
      exit()
print("Yes")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define codefor int test;cin>>test;while(test--)
#define vec_input(v) for(auto it=v.begin();it!=v.end();it++){cin>>*it;}
#define vec_output(v) for(auto it=v.begin();it!=v.end();it++){if(it!=v.begin())cout<<" ";cout<<*it;}cout<<endl;
#define vec_debug(v) for(auto it=v.begin();it!=v.end();it++){cerr<<*it<<" ";}cerr<<endl;
#define yn(ans) cout<<(ans?"Yes":"No")<<endl
#define YN(ans) cout<<(ans?"YES":"NO")<<endl
#define umap unordered_map
#define uset unordered_set
using namespace std;
using ll = long long;

int main(){
    int n;
    cin>>n;
    if(n%1000==0)cout<<0<<endl;
    else cout<<1000-(n%1000)<<endl;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m, x = 0;

    cin >> n;
    m = n;

    while(n!=0){
        x += n % 10;
        n /= 10;
    }
    
    if(m%x==0)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

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

long long N;
vector<long long>s;

int main(){
	cin >> N;
	for(long long i = 0; i < N; i++){
		long long tmp;
		cin >> tmp;
		s.push_back(tmp);
	}
	sort(s.begin(), s.end());
	long long sumi = 0;
	long long pos = -1;
	for(long long i = s.size() - 1; i >= 0; i--){
		if(s[i] % 10 != 0){
			pos = i;
		}
		sumi += s[i];
	}

	if(pos == -1){
		cout << 0 << endl;
	}else{
		if(sumi % 10 == 0){
			cout << sumi - s[pos] << endl;
		}else{
			cout << sumi << endl;
		}
	}
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use std::io::{stdout, Write, BufWriter};
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use proconio::marker::{Isize1, Usize1, Bytes, Chars};

#[proconio::fastout]
fn main() {
    proconio::input!{
        s: String,
    }
    if s == String::from("ABC") {
        println!("ARC");
    } else { println!("ABC"); }
}


Measured memory_bytes: 2156
#include <iostream>
using namespace std;
#define REP(i,n) for(int i=0; i< int(n); (i)++)

int main()
{
    char a[6]={0};
    cin >> a;
    REP(i,5)
    {
        if(a[i]=='A' && a[i+1]=='C')
        {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
import std.stdio, std.string, std.conv, std.algorithm, std.range;

void main() {
    auto tmp = readln.split.to!(int[]);
    auto K = tmp[0], S = tmp[1];
    iota(K+1).map!(x => max(0, min(S-x, K) - max(0, S - K - x) + 1)).sum.writeln;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P  = pair<int, int>;
int main() {
    int n;
    cin >> n;
    for (int i = 0, j = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        if (a == b)
            ++j;
        else
            j = 0;
        if (j >= 3) return cout << "Yes", 0;
    }
    cout << "No";
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define mod 1000000007
#define pb push_back
#define VJ ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mp make_pair()
#define vi(x) vector<int>x
#define vl vector<long long int>
#define vc vector<char>
#define max 100001 
using namespace std;
// 
void solve(){
	string num;cin>>num;
	int ans=0;
	for(int i=0;i<num.length();i++){
		ans+=(int)num[i]-48;
	}
	// cout<<ans;
	if(ans%9==0) cout<<"Yes";
	else cout<<"No";

}

int main(){
	 #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
	 #endif
	VJ
	solve();
	return 0;
}


Measured memory_bytes: 3752
<?php
/**
 * ABC127
 * C - Prison
 */

// $s = trim(fgets(STDIN));
// fscanf(STDIN, "%d %d", $a, $b);
// $n = array_map('intval', explode(' ', trim(fgets(STDIN))));

fscanf(STDIN, "%d %d", $n, $m);

$l = [];
$r = [];

for ($i = 0; $i < $m; $i++) {
    fscanf(STDIN, "%d %d", $l[$i], $r[$i]);
}

$maxL = 1;
$minR = $n;

for ($i = 0; $i < $m; $i++) {
    if ($maxL < $l[$i]) {
        $maxL = $l[$i];
    }
    if ($minR > $r[$i]) {
        $minR = $r[$i];
    }
    if ($minR < $maxL) {
        echo 0, PHP_EOL;
        return;
    }
}

$result = $minR - $maxL + 1;
if ($result < 0) {
    $result = 0;
}

echo $result, PHP_EOL;


Measured memory_bytes: 15988
#include <bits/stdc++.h>
using namespace std;
#define pr(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define all(v) (v).begin(), (v).end()
#define int long long
#define sz(v) (int)(v).size()
#define mod 1000000007 // ((a- b)% mod+ mod)% mod

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}

void solve() {
        int a, b, c; cin >> a>> b>> c;
        if (a< 0) a*= -1;
        int wh= a/ c;
        if (a== 0|| wh== 0) {
                if (b& 1) cout << c-a;
                else cout << a;
                return;
        }
        if (b<= wh) {
                cout << (a - (b* c))<< "\n";
        } else {
               int ans=  abs(a- (wh* c));
               b-= wh;
               if (b%2== 0) {
                        cout << ans;
               } else cout << abs(ans- c);
        }
}

int32_t main(){
ios::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL);
        int T= 1;
        //cin >> T;
        while ( T-- ) {
                solve();
        }
return 0;
}


Measured memory_bytes: 3664
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define ff first
#define ar array
#define ss second
#define ll long long int
#define mem(x) memset(x,0,sizeof(x))
#define setbits(x)  __builtin_popcount(x)
#define ull unsigned long long int
#define all(c) (c).begin(),(c).end()
#define debug(x) cout<<#x<<" :: "<<x<<endl;
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define db double
#define endl "\n"
#define  fbo(x) find_by_order(x)
#define  ook(x) order_of_key(x)
 
using namespace __gnu_pbds;
using namespace std;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair<ll,ll > iil;
typedef pair<ll,int> li;
typedef pair<int,int> ii;
typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update>
    os1;
typedef tree<int, null_type, greater<int>, rb_tree_tag,
            tree_order_statistics_node_update>
    os2;

inline void fast()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
const ll pi=31;
const ll MOD[2] = {1187278649, 1149736019};//for double hashing
const ll mod=(ll)(1e9)+7;
ll pmod(ll x,ll n){
  ll r=1;
  while(n>0)
  {
    if(n&1LL)
      r=(r*x)%mod;
    x=(x*x)%mod;
    n=n/2;
    n%=mod;
  }
  return r;
}
ll pMod(ll x,ll n,ll mod)
{ ll r=1;
  while(n>0)
  {
    if(n&1LL)
      r=(r*x)%mod;
    x=(x*x)%mod;
    n=n/2;
    n%=mod;
  }
  return r;
 
}
 
//think recursively also;
const int mxn=2e5;
int n,m,c=0;
bool vis[mxn+1];
vector<int>adj[mxn+1];
void dfs(int u,int p)
{  c+=1;
   vis[u]=1;
   for(auto it:adj[u])
   {
     if(vis[it])
      continue;
    dfs(it,u);
   }
}
void solve()
{ 
  cin>>n>>m;
  for(int i=1;i<=m;i++)
  {
    int a,b;
    cin>>a>>b;
    adj[a].pb(b);
    adj[b].pb(a);
  }
  int mx=0;
  for(int i=1;i<=n;i++){
     if(!vis[i])
     {
      c=0;
      dfs(i,0);
      mx=max(mx,c);
     }
  }
  cout<<mx<<endl;

}
int main()
{
  fast();
   // int t;
   // cin>>t;
   // for(int casee=1;casee<=t;casee++)
  {//cout<<"Case #"<<casee<<": ";
    solve();
  }
 
 
 
}

Measured memory_bytes: 24140
n, m = map(int, input().split())
shima1 = []
shimaN = []

for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        shima1.append(b)
    if b == n:
        shimaN.append(a)

if len(set(shima1) & set(shimaN)) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Measured memory_bytes: 21848
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 200005;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
vector<vector<int> > G(MAX, vector<int>());
int N, M;
/* function */
void bfs() {
    vector<int> visited(MAX, -1);

    visited[0] = 0;
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int from = q.front();
        q.pop();
        if (visited[from] >= 2) continue;
        for (int to : G[from]) {
            if (visited[to] != NIL) continue;
            visited[to] = visited[from] + 1;
            q.push(to);
        }
    }

    cout << ((visited[N-1] == 1 || visited[N-1] == 2) ? "POSSIBLE" : "IMPOSSIBLE") << '\n';
}
/* main */
int main(){
    cin >> N >> M;
    int a, b;
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    bfs();
}


Measured memory_bytes: 13168
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    String S = sc.next();
    StringBuilder SS = new StringBuilder(S);
    String s = String.valueOf(S.charAt(K-1)).toLowerCase();
    System.out.println(SS.replace(K-1,K,s).toString());
  }
}

Measured memory_bytes: 20820
# B - Palace

N = int(input())
T, A = map(int, input().split())
H = list(int(x) for x in input().split())

ans = 0
d = 10**18
temp = [0] * N
for i in range(N):
    temp[i] = T - H[i] * 0.006
    if d > abs(temp[i] - A):
        ans = i + 1
        d = abs(temp[i] - A)

print(ans)

Measured memory_bytes: 3064
## coding: UTF-8
from itertools import product
import sys

N, M, X = map(int,input().split())
lc = [list(map(int, input().split())) for _ in range(N)]

#print(N, M, X, lc)

combi = list(product('YN', repeat = N))
#print(combi)


able = 'No'
ans = sys.maxsize
#print(ans)

for i in range(len(combi)):
    #print(combi[i])
    money = 0
    lx = [0] * M
    for j in range(N):
        #print(combi[i][j])
        if(combi[i][j] == 'Y'):
            money += lc[j][0]
            for k in range(M):
                lx[k] += lc[j][k+1]
    #print(money, lx)
    if(min(lx) >= X):
        #print('OK')
        able = 'Yes'
        ans = min(ans, money)
    #print(able, ans)

if(able == 'No'):
    print(-1)
else:
    print(ans)

'''
for i in range(len(combi)):
    print(combi[i])
    money = 0
    lx = [0] * M
    for j in range(M):
        if(combi[i][j] == 'Y'):
            money += lc[i][0]
            for k in range(M):
                lx[k] += lc[i][k+1]
            print(money, lx)
'''



Measured memory_bytes: 69184
"use strict";
function Main(input) {
    let cin = new Inputer(input);
    let N = cin.getInt(), S = cin.getStr(), K = cin.getInt();
    let ans = "", Ch = S.charAt(K-1);
    for (let n = 0; n < N; n++) {
        ans += (Ch == S.charAt(n) ? Ch : "*");
    }
    console.log(ans);
}
class Inputer{constructor(t){this.cnt=0,this.items=t.split(/\n|\s/)}getInt(){return this.items[this.cnt++]-0}getIntArray(t){let r=new Array(t);for(let e=0;e<t;e++)r[e]=this.getInt();return r}getStr(){return this.items[this.cnt++]}getStrArray(t){let r=new Array(t);for(let e=0;e<t;e++)r[e]=this.getStr();return r}}
if (typeof window == "undefined") Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
#include<bits/stdc++.h>
    using namespace std;
    #define itn int
    #define int long long
    #define mod 1000000007
    #define fi first
    #define se second
    #define be begin()
    #define en end()
    #define re reverse
    #define Set setprecision
    #define NO cout<<"NO\n"
    #define YES cout<<"YES\n"
    #define No cout<<"No\n"
    #define Yes cout<<"Yes\n"
    const int INFi=2147483647;
    const long long INFl=9223372036854775807LL;
    template<typename T> T abs(T a,T b){
    return max(a,b)-min(a,b);
    }
    template<typename T> T lcm(T a,T b){//最小公倍数
    return (a*b)/gcd(a,b);
    }
    int gcd(int a,int b){//最大公約数
    int c=a%b;
    while(true){
    if(c==0) break;
    a=b;
    b=c;
    c=a%b;
    }
    return b;
    }
    bool IsPrime(int num){
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;
    double sqrtNum = sqrt(num);
    for(int i=3;i<=sqrtNum;i+=2){
    if(num%i==0){
    return false;
    }
    }
    return true;
    }
    signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b;
    //string a,b;
    cin>>a>>b;
    if(a<10){
    cout<<b+100*(10-a);
    }
    else cout<<b;
    cout<<"\n";
    }


Measured memory_bytes: 256
#include<cstdio>
#include<string>
#include<cstring>
#include<utility>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
#include<vector>
#include<iostream>
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define inf 0x7fffffff
using namespace std;
const ll mod=1e9+7;
ll dp[110][4][4][4];
bool check(int x,int y,int z,int w)//agct
{
	if((y==0&&z==1&&w==2)||(y==0&&z==2&&w==1)||(y==1&&z==0&&w==2)||(x==0&&z==1&&w==2)||(x==0&&y==1&&w==2))
	{
		return 0;
	}
	return 1;
}
int main()
{
	int i,j,k,n,m,x,y,z;
	scanf("%d",&n);
	for(i=0;i<4;i++)
		for(j=0;j<4;j++)
			for(k=0;k<4;k++)
				if((i==0&&j==1&&k==2)||(i==0&&j==2&&k==1)||(i==1&&j==0&&k==2))
					dp[3][i][j][k]=0;
				else
					dp[3][i][j][k]=1;
	for(i=4;i<=n;i++)
		for(x=0;x<4;x++)
			for(y=0;y<4;y++)
				for(z=0;z<4;z++)
					for(j=0;j<4;j++)
						if(check(x,y,z,j))
						{
							dp[i][y][z][j]+=dp[i-1][x][y][z];
							dp[i][y][z][j]%=mod;
						}
	ll sum=0;
	for(i=0;i<4;i++)
		for(j=0;j<4;j++)
			for(k=0;k<4;k++)
			{
				sum+=dp[n][i][j][k];
				sum%=mod;
			}
	printf("%lld",sum);
	return 0;
}

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

int main(){
	int n,cnt;
	cin>>n;
	cnt=0;
	for(int i=1;i<=n;i++){
		int a;
		cin>>a;
		if(i%2==1 and a%2==1){
			cnt++;
		}
	}
	cout<<cnt<<endl;
}

Measured memory_bytes: 3560
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N, A, B;
  cin >> N >> A >> B;
  if(A+B-1 > N || A*B < N) cout << -1 << endl;
  else {
    ll rem = N-(A+B-1);
    vector<ll> v;
    auto build = [&]() {
      rep(i, A) rrep(j, B) {
        if(i != 0 && j != B-1 && rem == 0) {
          REP(k, i+1, A) v.push_back(B*k+j);
          return;
        }
        v.push_back(B*i+j);
        if(i != 0 && j != B-1) rem--;
      }
    };
    build();

    /* 座標圧縮 */
    vector<ll> u;
    rep(i, v.size()) u.push_back(v[i]);
    sort(all(u));
    vector<ll> ans;
    rep(i, v.size()) {
      ans.push_back(lower_bound(all(u), v[i])-begin(u)+1);
    }
    rep(i, N) {
      if(i) cout << ' ';
      cout << ans[i];
    }
    cout << "\n";
  }
  return 0;
}


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

int main(){
  long long n, a, b, c, d; cin >> n >> a >> b >> c >> d;
  string s; cin >> s;
  for(int i = a; i < c; i++){
    if(s.at(i) == '#' & s.at(i - 1) == '#'){
      cout << "No";
      return 0;
    }
  }
  for(int i = b; i < d; i++){
    if(s.at(i) == '#' & s.at(i - 1) == '#'){
      cout << "No";
      return 0;
    }
  }
  if(c > d){
    for(int i = b - 1; i < d; i++){
      if(s.at(i - 1) == '.' & s.at(i) == '.' & s.at(i + 1) == '.'){
        cout << "Yes";
        return 0;
      }
    }
    cout << "No";
    return 0;
  }
  cout << "Yes";
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define pt(sth) cout << sth << "\n"
#define chmax(a, b) {if(a<b) a=b;}
#define chmin(a, b) {if(a>b) a=b;}
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=1e9+7;

/*
 for(i=0; i<N; i++)
   cin >> a[i];
*/




int main(void) {
  ll i, j, k;
  ll N, M;
  cin >> N >> M;
  P ca[MAX];
  
  priority_queue<ll> q;
  for(i=0; i<N; i++) {
    ll a;
    cin >> a;
    q.push(a);
  }
  
  for(i=0; i<M; i++)
    cin >> ca[i].second >> ca[i].first;
  sort(ca, ca+M);
  reverse(ca, ca+M);
  
  ll r=N;
  for(i=0; i<M; i++) {
    ll t=min(r, ca[i].second);
    r-=t;
    
    for(j=0; j<t; j++) q.push(ca[i].first);
    
    if(r==0) break;
  }
  
  ll ans=0;
  for(i=0; i<N; i++) {
    ans+=q.top(); q.pop();
  }
  
  pt(ans);
}



Measured memory_bytes: 3956
#include <bits/stdc++.h>
using namespace std;
// types
typedef long long ll; 
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
// IO
#define fo(i, n) for (int i = 0; i < n; i++)
#define fo1(i, n) for (int i = 1; i <= n; i++)
#define sc(n) scanf("%d", &n) 
#define sca(a, n) fo(i, n) sc(a[i])
#define pd(a) printf("%d ", a)
#define pld(a) printf("%d\n", a)
#define pda(a, n) fo(i, n) pd(a[i])
#define pl printf("\n")
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b) 
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
// math
const ll mod = 1e9+7;
template<typename T> T gcf(T a, T b) {return (b == 0) ? a : gcf(b, a%b);} 
template<typename T> T lcm(T a, T b) {return (a*b)/gcf(a, b);}
template<typename T> T sumTo(T x) {return x * (x+1) / 2;}
template<typename T> T sumSquaresTo(T x) {return x * (x+1) * (2*x+1) / 6;}
template<typename T> T ceilDiv(T n, T d) {return (n+d-1)/d;}

double sq(double a) {return a*a;}

double distBet(pii a, pii b) {
    double ans = sq((double) (a.first-b.first)) + sq((double) (a.second-b.second));
    return sqrt(ans);
}

void solve() {
    int n; 
    cin >> n;
    pii p[n];
    fo(i, n) {
        int x, y; cin >> x >> y;
        p[i] = mp(x, y);
    }
    double sumPaths = 0;
    fo(i, n) {
        for(int j = i+1; j < n; j++) {
            sumPaths += distBet(p[i], p[j]);
        }
    }
    printf("%.10f", sumPaths *  2 / n);
}

int main() {
    int t = 1;
    //scanf("%d", &t);
    while (t--) {
        solve();
    }
    return 0;
}

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

typedef long long ll;
const ll INF = 1010000000000000017LL;
const ll MOD = 1000000007LL;

#define REP(i, n) for(ll i = 0 ; i < n; i++)

//#define DEBUG(fmt, ...)
#define DEBUG(fmt, ...) fprintf(stderr, fmt "\n", ##__VA_ARGS__)

int main(){
    std::cout<<std::fixed<<std::setprecision(10);

    ll N;
    cin >> N;
    vector<ll> a(N+1);
    vector<ll> h(N+1);
    vector<ll> M;

    REP(i,N){ cin >> a[i+1];};

    for(int i = N; i > 0; i-- ){
       ll j = i+i;
       ll count = 0;
       while( j <= N ){
            count = (count + h[j])%2;
            j+=i;
       }
       h[i] = (count + a[i])%2;
       if( h[i] == 1 ){
            M.push_back(i);
       }
    }

    cout << M.size() << endl;
    REP(i, M.size()){
        cout << M[i] << " ";
    }
    cout << endl;
}


Measured memory_bytes: 4980
a=list(input())
b=list(input())
c=list(input())
s=a.pop(0)
w=''
while True:
    if(s=='a'):
        if(len(a)==0):
            w='A'
            break
        s=a.pop(0)
    elif(s=='b'):
        if(len(b)==0):
            w='B'
            break
        s=b.pop(0)
    else:
        if(len(c)==0):
            w='C'
            break
        s=c.pop(0)
print(w)


Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    long N,cnt=0,max=0;
    cin >> N;
    vector<string>S(N);
    vector<long>c(N);
    for(int i=0;i<N;i++){
        cin >> S[i];
    }
    sort(S.begin(),S.end());
    for(int i=0;i<N;i++){
        if(i==0){
            c[i]=1;
        }else if(S[i] == S[i-1]){
            c[i]=c[i-1]+1;
        }else{
            c[i]=1;
            if(max < c[i-1]){
                max = c[i-1];
            }
        }
    }
    if(max < c[N-1]){
        max=c[N-1];
    }
    for(int i=0 ; i<N ;i++){
        if(c[i]==max){
            cout << S[i] << endl;
        }
    }
}

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

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef pair<int,int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define EXIST(m,v) (m).find((v)) != (m).end()
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

#define en "\n"

constexpr double EPS = 1e-9;
constexpr double PI  = 3.1415926535897932;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL<<60;
constexpr long long MOD = 1000000007; // 998244353;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

void Main(){
    ll X,K,D; cin >> X >> K >> D;
    X = abs(X);

    ll n = min(K,X/D);
    ll ans1 = X - n*D, ans2 = LINF;
    K -= n;
    ll ans = ans1;
    if(K){
        ans2 = abs(ans1-D); K--;
        if(K%2) ans = ans1;
        else ans = ans2;
    }
    cout << ans << en;
    return;
}

int main(void){
    cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);cout<<fixed<<setprecision(15);
    int t=1; //cin>>t;
    REP(_,t) Main();
    return 0;
}

Measured memory_bytes: 3640
#include<stdio.h>

#define MAX 1000000

int parent(int);
int left(int);
int right(int);
void maxHeapify(int);
void buildMaxHeap(void);

int H,A[MAX+1];

int main(){
  int i;

  scanf("%d",&H);
  for(i=1;i<=H; i++) scanf("%d",&A[i]);

for(i=H/2;i>=1;i--) maxHeapify(i);
//buildMaxHeap();

for(i=1;i<=H;i++){
  printf(" %d",A[i]);
}
    printf("\n");

  return 0;
}

int parent(int x){
  return x/2;
}

int left(int x){
  return 2*x;
}

int right(int x){
  return 2*x+1;
}

void maxHeapify(int i){
  int l,r,largest,temp;

  l=left(i);
  r=right(i);

  if(l<=H && A[l]>A[i]) largest = l;
  else largest = i;
  if(r<=H && A[r] > A[largest]) largest = r;

  if(largest != i){
    temp = A[i];
    A[i] = A[largest];
    A[largest] = temp;
    maxHeapify(largest);
  }
}

void buildMaxHeap(void){
int i;
  for(i=H/2;i>1;i--) maxHeapify(i);
}



Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define rep(i,n) for(long long i=0; i<n; i++)
#define Rep(i,n) for(long long i=1; i<n; i++)
#define ll long long
#include <math.h>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <queue>
#include <set>
#include <vector>


using namespace std;
#define PI acos(-1)

int main(){
    string s;
    cin>>s;
    
    if(s[2]==s[3]&&s[4]==s[5]){
        cout<<"Yes"<<endl;
        return 0;
        
    }
    
    
    cout<<"No"<<endl;
}



Measured memory_bytes: 3592
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int N, M, Q;
int dp[500][500][2];
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> M >> Q;
  rep(i, M) {
    int l, r;
    cin >> l >> r;
    l--, r--;
    dp[l][r][0]++;
  }
  for (int len=1; len<=N; len++) {
    rep(l, N) {
      int r = l+len-1;
      if (r >= N) break;
      rep(k, 2) {
        if (l > 0 && k == 0) dp[l-1][r][k] += dp[l][r][k];
        if (r+1 < N) dp[l][r+1][1] += dp[l][r][k];
      }
    }
  }
  rep(i, Q) {
    int p, q;
    cin >> p>>q;
    p--,q--;
    cout<<dp[p][q][0]+dp[p][q][1]<<"\n";
  }
  return 0;
}


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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()
#define int ll

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

  int W,H;
  cin>>W>>H;
  priority_queue<int,vector<int>,greater<int>>p,q;
  for(int i=0;i<W;i++){
    int x;cin>>x;
    p.push(x);
  }
  for(int i=0;i<H;i++){
    int x;cin>>x;
    q.push(x);
  }
  p.push(INF);
  q.push(INF);
  int a=W+1;
  int b=H+1;
  int ans=0;
  for(int i=0;i<H+W;i++){
    int x=p.top();
    int y=q.top();
    if(x==INF&&y==INF)break;
    if(x<y)ans+=x*b,a--,p.pop();
    else ans+=y*a,b--,q.pop();
  }
  cout<<ans<<endl;
  return 0;
}


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

int main() {
    string s;
    cin >> s;

    string s2 = "";
    for (int i = 0; i < s.size(); i++) {
        if (i % 2 == 0) {
            s2.push_back('g');
        }
        else {
            s2.push_back('p');
        }
    }

    int ans = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'g' && s2[i] == 'p') {
            ans++;
        }
        else if (s[i] == 'p' && s2[i] == 'g') {
            ans--;
        }
    }

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

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

using namespace std;

#define REP(i, N) for (int i = 0; i < (int)N; i++)
#define LOOP(i, N) for (int i = 1; i <= (int)N; i++)
#define RREP(i, N) for (int i =(int)N-1; i >= 0; i--)
#define RLOOP(i, N) for (int i =(int)N; i > 0; i--)
#define FOR(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define INF (1 << 30)
#define LLINF (1LL << 62)
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

typedef long long ll;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;

int main(){
  string s;
  cin>>s;
  ll sum=0;
  int n=s.size()-1;
  for(int bit=0;bit<(1<<n);bit++){//(1<<n)は2^n
    vector<int> v;
    for(int i=0;i<n;i++){
      if(bit &(1<<i)){
        v.push_back(i);
      }
    }
    int i=0;
    if(v.empty()){
      ll num = atoll(s.c_str());
      //cout<<num<<endl;
      sum+=num;
    }else{
      for(auto itr=v.begin();itr!=v.end();itr++){
        string t=s;
        string tmp;
        for(int j=i;j<=*itr;j++){
          tmp+=t[j];
          i++;
        }
        ll num = atoll(tmp.c_str());
        //cout<<num<<endl;
        sum+=num;
      }
      string ss=s.substr(i);
      ll k=atoll(ss.c_str());
      //cout<<k<<endl;
      sum+=k;
    }
  }
  cout<<sum<<endl;
}


Measured memory_bytes: 256
def main():
    q = int(input())

    state = 0
    flag  = 1

    for _ in range(q):

        param = input().split()
        c = int(param[0])
        if len(param) >= 2:
            param[1] = int(param[1])

        if c == 0:
            if state & (flag << (param[1])) :
                print("1")
            else:
                print("0")

        elif c == 1:
            state = state | (flag << (param[1] ))

        elif c == 2:
            state = state & (~(flag << (param[1] )) & 0xffffffffffffffff)
            
        elif c == 3:
            state = state ^ (flag << (param[1] ))

        elif c == 4:
            if state & 0xffffffffffffffff == 0xffffffffffffffff:
                print("1")
            else:
                print("0")
            
        elif c == 5:
            if (state & 0xffffffffffffffff) != 0:
                print("1")
            else:
                print("0")

        elif c == 6:
            if (state & 0xffffffffffffffff) == 0:
                print("1")
            else:
                print("0")

        elif c == 7:
            print(format(state, "064b").count("1"))

        elif c == 8:
            print(int(state))

main()


Measured memory_bytes: 5640
#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
   int x[2];
   while(1){
      cin >> x[0] >> x[1];
      if (x[0] == 0 && x[1] == 0) break;
      sort(x,x+2);
      cout << x[0] << " " << x[1] <<endl;
   }
   return 0;
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
int A[201010];
int is[1010101];
int out[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		is[A[i]]++;
	}
	
	for(i=1000000;i>=1;i--) {
		for(j=2*i;j<=1000000;j+=i) is[j]+=is[i];
	}
	
	int ret=0;
	FOR(i,N) {
		if(is[A[i]]==1) ret++;
	}
	cout<<ret<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 8348
#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
int main(void){
 
  int CNT = 0;
  string s;
  while( cin >> s ){
 
    int N = s.size();
    int cnt = 0;
    if( N == 1 ){
      CNT++;
      // cout << "OK" << endl;
      continue;
    }
    int x = 0;
    int y = N - 1;
    while(1){
 
      if( x >= N/2 )break;
      
      if( s[x] == s[y] ){
    cnt++;
    x++;
    y--;
      }
      else{
    break;
      }
    }
     
    if( cnt == N/2 ){
      CNT++;
      // cout << "ok" << endl;
    }
  }
  cout << CNT << endl;
  return 0;
}

Measured memory_bytes: 3132
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

struct UF{
    int n;
    //正だったらその頂点の親,負だったら根で連結成分の個数
    vector<int> d;
    UF() {}
    UF(int N):n(N), d(N,-1){}
    int root(int v){
        if(d[v]<0) return v;
        return d[v]=root(d[v]);
    }
    bool unite(int X,int Y){
        X=root(X); Y=root(Y);
        if(X==Y) return false;
        if(size(X) < size(Y)) swap(X,Y);
        d[X]+=d[Y];
        d[Y]=X;
        return true;
    }
    ll size(int v){ return -d[root(v)]; }
    bool same(int X,int Y){ return root(X)==root(Y); }
};

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

    UF uf(n);
    vector<ll> ans(m);
    ll now = (ll)n*(n-1)/2;
    for(int i=m-1; i>=0; --i){
        ans[i] = now;
        if(!uf.same(a[i],b[i])){
            ll sub = uf.size(a[i])*uf.size(b[i]);
            uf.unite(a[i],b[i]);
            now -= sub;
        }
    }

    rep(i,m) cout << ans[i] << "\n";
    return 0;
}


Measured memory_bytes: 3328
package main

import (
	"fmt"
	"strings"
)

func main() {
	var a, b, c string
	fmt.Scan(&a, &b, &c)

	A := strings.Split(a, "")
	B := strings.Split(b, "")
	C := strings.Split(c, "")

	ans := exec(A, B, C)
	fmt.Println(ans)
}

func exec(A, B, C []string) string {
	target := "a"
	pa, pb, pc := 0, 0, 0

	for {
		if target == "a" {
			if pa == len(A) {
				return "A"
			}
			target = A[pa]
			pa++
		} else if target == "b" {
			if pb == len(B) {
				return "B"
			}
			target = B[pb]
			pb++
		} else if target == "c" {
			if pc == len(C) {
				return "C"
			}
			target = C[pc]
			pc++
		}
	}
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }

#define Sq(x) (x)*(x)
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Unique(a) a.erase(unique(Range(a)), a.end())
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) { for(const auto &e : xs) cout << e << " "; cout << "\n"; }
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")
#define vc vector
#define Mini(a, x) a = min(a, x)
#define Maxi(a, x) a = max(a, x)

// constexpr int MOD = 1e9+7;

int main(void){
    Cin(int, a, b, c, d);
    Cout(max(0, c-(a-b)));
}

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<P> VP;
typedef vector<vector<ll>> VV;
typedef vector<vector<int>> VVi;

#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
const ll INF=1e18+18;
const ll MAX=100005;
const ll MOD=1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define REPM(i, mp) for (auto i = mp.begin(); i != mp.end(); ++i)
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbgmap(mp) cerr << #mp << ":"<<endl; for (auto i = mp.begin(); i != mp.end(); ++i) { cerr << i->first <<":"<<i->second << endl;}
#define dbgarr(n,m,arr) rep(i,n){rep(j,m){cerr<<arr[i][j]<<" ";}cerr<<endl;}
#define dbgdp(n,arr) rep(i,n){cerr<<arr[i]<<" ";}cerr<<endl;
#define Uniq(v) v.erase(unique(v.begin(), v.end()), v.end())
#define fi first
#define se second

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }

template<typename T1, typename T2>
ostream &operator<<(ostream &s, const pair<T1, T2> &p) { return s<<"("<<p.first<<", "<<p.second<<")"; }

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len=v.size();
    for(int i=0; i<len; ++i) {
        s<<v[i];
        if(i<len-1) s<<"	";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<std::setprecision(10);

    ll n,m,r;
    cin>>n>>m>>r;
    ll ans=INF;
    Vec place(r);
    rep(i,r){
        cin>>place[i];
        place[i]--;
    };
    VV g(n,Vec(n,INF));
    rep(i,m){
        ll a,b,c;
        cin>>a>>b>>c;
        a--;b--;
        g[a][b] = g[b][a] = c;
    }

    rep(k,n)rep(j,n)rep(i,j){
        g[i][j] = g[j][i] = min(g[i][j],g[i][k]+g[k][j]);
    }
    sort(ALL(place));
    do{
        ll dis = 0;
        rep(i,r-1){
            dis += g[place[i]][place[i+1]];
        }
        chmin(ans,dis);
    }while (next_permutation(ALL(place)));
    cout<<ans<<endl;
    return  0;
}


Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#define REP(i,n) for(int i = 0;i < (n);i++)
#define pb push_back
using namespace std;
const int INF = 1e9;
typedef long long ll;

int main(){
  int n,m,l;
  string s;
  int a,b;
  cin >> l >> m >> n;
  a = l;
  b = m;
  if(a == b){
    cout << n << endl;
  }
  else{
    if(l == n){
      cout << m << endl;
    }
    else{
      cout << l << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
inline void read(int &x) {
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
ll l,r,res,mx=62;
int main() {
	scanf("%lld%lld",&l,&r);if(l==r){puts("1");return 0;}
	while(mx&&(l>>mx&1)==(r>>mx&1))mx--;
	ll all=(1LL<<mx+1)-1;l&=all;r&=all;
	ll qaq=r;per(i,mx-1,0)if(qaq>>i&1){rep(j,0,i)qaq|=1LL<<j;break;}
	ll a=l&((1LL<<mx)-1),b=qaq&((1LL<<mx)-1);
	if(b>=a)printf("%lld",all-l+1);
	else printf("%lld",all-l+1-(a-b-1));
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,c) for(int i=0;i<c;++i)
int main(){
  char s[10];
  scanf("%s",s);
  sort(s,s+4);
  if(s[0]==s[1]&&s[1]!=s[2]&&s[2]==s[3]){
      cout << "Yes" << endl;
  }else{
      cout << "No" << endl;
  } 
 return 0;
}

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


ll D;
vector<ll> C(3, 0);
vector<ll> k = { 2, 3, 5 };
map<ll, ll> M; // メモ。(n, cost)

ll loop(ll n) {
	if (M[n] != 0) return M[n];
	ll c = 1e18;
	if (n < c / D) c = n * D;
	for (int i = 0; i < 3; i++) {
		if (n < k[i]) {
			c = min(c, n * D);
//			cout << n << "," << k[i] << "," << n * D << "," << c << endl;
		}
		else {
			ll x = n % k[i];
			ll y = n / k[i];
			if (x == 0) {
				c = min(c, loop(y) + C[i]);
			}
			else {
				c = min(c, min(loop(y) + C[i] + x * D, loop(y + 1) + C[i] + (k[i] - x) * D));
			}
		}
	}
	M[n] = c;
	return c;
}

int main() {
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		M.clear();
		// testcase
		ll N;
		cin >> N >> C[0] >> C[1] >> C[2] >> D; // C = (A,B,C)
		cout << loop(N) << endl;
	}

//	for (auto it = M.begin(); it != M.end(); it++) {
//		cout << it->first << "," << it->second << endl;
//	}


	return(0);
}


Measured memory_bytes: 4284