akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define all(x) (x).begin(),(x).end()
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
using Graph = vector<vector<int>>;
double nCk(int n, int k) {
double res=1.0;
for(int i=0; i<n; i++){
res*=0.5;}
for(int i=0; i<k; i++){
res*=(double)(n-i);
res/=(double)(k-i);
}
return res;}
struct edge{ll to, cost;};
typedef pair<ll,ll> P;
struct graph{
  ll V;
  vector<vector<edge> > G;
  vector<ll> d;

  graph(ll n){
    init(n);
  }

  void init(ll n){
    V = n;
    G.resize(V);
    d.resize(V);
    rep(i,V){
      d[i] = INF;
    }
  }

  void add_edge(ll s, ll t, ll cost){
    edge e;
    e.to = t, e.cost = cost;
    G[s].push_back(e);
  }

  void dijkstra(ll s){
    rep(i,V){
      d[i] = INF;
    }
    d[s] = 0;
    priority_queue<P,vector<P>, greater<P> > que;
    que.push(P(0,s));
    while(!que.empty()){
      P p = que.top(); que.pop();
      ll v = p.second;
      if(d[v]<p.first) continue;
      for(auto e : G[v]){
        if(d[e.to]>d[v]+e.cost){
          d[e.to] = d[v]+e.cost;
          que.push(P(d[e.to],e.to));
        }
      }
    }
  }
};
class UnionFind
{
public:
  int par[100005];
  int depth[100005];
  int nGroup[100005];
 
  UnionFind(int n) {
    init(n);
  }
 
  void init(int n) {
    for(int i=0; i<n; i++) {
      par[i] = i;
      depth[i] = 0;
      nGroup[i] = 1;
    }
  }
 
  int root(int x) {
    if(par[x] == x) {
      return x;
    } else {
      return par[x] = root(par[x]);
    }
  }
 
  bool same(int x, int y) {
    return root(x) == root(y);
  }
 
  void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if(x == y) return;
 
    if(depth[x] < depth[y]) {
      par[x] = y;
      nGroup[y] += nGroup[x];
      nGroup[x] = 0;
    } else {
      par[y] = x;
      nGroup[x] += nGroup[y];
      nGroup[y] = 0;
      if(depth[x] == depth[y])
        depth[x]++;
    }
  }
};
const ll MAX = 510000;
ll 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;
    }
}

// 二項係数計算
ll COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
} 
int main() {
ll n; cin>>n;
string s; cin>>s;
ll ca = 0;
rep(i,10){
rep(j,10){
rep(k,10){
string t = "";
string l = "";
l = to_string(i);
t +=l;
l = to_string(j);
t +=l;
l = to_string(k);
t +=l;
//cout << t << endl;
ll q = 0;
rep(i,n){
if(t.at(q)==s.at(i)){
q++;}
if(q==3){
ca++;
break;}
}
}}}
cout << ca << endl;}


Measured memory_bytes: 3680
require 'prime'
require 'set'
require 'tsort'
include Math
def max(a,b);              a > b ? a : b                              end
def min(a,b);              a < b ?  a : b                             end
def swap(a,b);             a, b = b, a                                end
def gif;                   gets.to_i                                  end
def gff;                   gets.to_f                                  end
def gsf;                   gets.chomp                                 end
def gi;                    gets.split.map(&:to_i)                     end
def gf;                    gets.split.map(&:to_f)                     end
def gs;                    gets.chomp.split.map(&:to_s)               end
def gc;                    gets.chomp.split('')                       end
def pr(num);               num.prime_division                         end
def digit(num);            num.to_s.length                            end
def array(s,ini=nil);      Array.new(s){ini}                          end
def darray(s1,s2,ini=nil); Array.new(s1){Array.new(s2){ini}}          end
def rep(num);              num.times{|i|yield(i)}                     end
def repl(st,en,n=1);       st.step(en,n){|i|yield(i)}                 end


r,g,b = gi
num = r*100+g*10+b
puts num % 4 == 0 ? "YES" : "NO"


Measured memory_bytes: 2300
#include<stdio.h>
int main(){
    int k1,k2,h1,h2,a,b,c,d;
    scanf("%d %d\n%d %d\n %d %d %d %d\n",&h1,&h2,&k1,&k2,&a,&b,&c,&d);
    int hiro,ken;
    hiro=h1*a+h2*b+(h1/10)*c+(h2/20)*d;
    ken=k1*a+k2*b+(k1/10)*c+(k2/20)*d;
    if(hiro<ken){
        printf("kenjiro\n");
    }else if(hiro==ken){
        printf("even\n");
    }else{
        printf("hiroshi\n");
    }
    return 0;
}


Measured memory_bytes: 2684
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e9;
#define Fast    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sz      300005

string s,p;

int main(){
    Fast;
    int a,b,c, i,j,k, n,m,t, cs=1;

    cin>>s>>p;
    for(i=0; i<s.size(); i++){
        if(s[i]!=p[i]){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;



    return 0;
}



Measured memory_bytes: 3584
import java.util.*;
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] daikeihen = new int[3];
        daikeihen[0] = sc.nextInt();
        daikeihen[1] = sc.nextInt();
        daikeihen[2] = sc.nextInt();
        System.out.println((daikeihen[0] + daikeihen[1]) * daikeihen[2] / 2);
    }
}

Measured memory_bytes: 21332
#include <cstdio>
#include <cstring>
#include <algorithm>
#define REP(i, x, y) for(int i = (int)x; i <= (int)y; i ++)
using namespace std;
const int N = 100005;

int n, a[N];

int main(){
	scanf("%d", &n);
	REP(i, 1, n << 1) scanf("%d", a + i);
	sort(a + 1, a + 2 * n + 1);
	int ans = 0;
	for(int i = 2 * n - 1; i >= 1; i -= 2) ans += a[i];
	printf("%d\n", ans);
}

Measured memory_bytes: 128
#include<stdio.h>

int popu[5][4][11];

int main(void){
    int i,j,k,b,f,r,v,n;

    scanf("%d",&n);

    for(i = 0;i < n;i++){
        scanf("%d %d %d %d",&b,&f,&r,&v);
        popu[b][f][r] += v;
    }

    for(i = 1;i <= 4;i++){
        for(j = 1;j <= 3;j++){
            for(k = 1;k <= 10;k++)
                printf(" %d",popu[i][j][k]);
            printf("\n");
        }
        if(i < 4)
            printf("####################\n");
    }
    return 0;
}

Measured memory_bytes: 612
#include<bits/stdc++.h>
#define int long long
#define open(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
char ch;bool fs;void re(int& x)
{
	while(ch=getchar(),ch<'!');
	if(ch=='-')fs=1,x=0;else fs=0,x=ch-48;
	while(ch=getchar(),ch>'!')x=x*10+ch-48;
	if(fs)x=-x;
}
using namespace std;
int a,b,c;
main()
{
	re(a),re(b),re(c);
	if(a%2==0 || b%2==0 || c%2==0)return puts("0"),0;
	if(a>b)swap(a,b);
	if(a>c)swap(a,c);
	if(b>c)swap(b,c);
	printf("%lld\n",a*b);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// マクロ
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
// 型エイリアス
using ll = long long;
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using vvs = vector<vs>;

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

bool IsPrime(ll x) {
    if(x <2) return false;
    if(x == 2) return true;
    if(x % 2 == 0) return false;

    int sq = sqrt(x);
    for(int i = 3; i <= sq; i++) {
        if(x % i == 0) return false;
    }
    return true;
}

int main() {
    ll a,b ;
    cin >> a >> b;
    ll gcdab = gcd(a,b);
    int x = sqrt(gcdab); 
    vector<ll> div;
    for(int i = 1; i <= x; i++) {
        if(gcdab % i == 0) {
            div.push_back(i);
            div.push_back(gcdab / i);
        }
    }
    ll ans = 1;
    for(int i = 0; i < div.size(); i++) {
        if(IsPrime(div[i])) ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 384
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <numeric>
#include <functional>
#include <sstream>
#include <iostream>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cfloat>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cctype>
#include <cstdio>
#include <cassert>
using namespace std;

#define EPS 1e-12
#define ull unsigned long long
#define ll long long
#define VI vector<ll>
#define PII pair<ll, ll> 
#define VVI vector<vector<ll> >
#define VVVI vector<vector<vector<ll>>>
#define VVVVI vector<vector<vector<vector<ll>>>>
#define REP(i,n) for(ll i=0,_n=(n);(i)<(ll)_n;++i)
#define REPR(i,n) for(ll i=(ll)(n)-1;0<=(i);--i)
#define RANGE(i,a,b) for(ll i=(ll)a,_b=(ll)(b);(i)<_b;++i)
#define RANGER(i,a,b) for(ll i=(ll)(b)-1,_a=(ll)(a);(_a)<=i;--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define ALLR(c) (c).rbegin(), (c).rend()
#define PB push_back
#define MP(a, b) make_pair(a, b)
#define POPCOUNT __builtin_popcount
#define POPCOUNTLL __builtin_popcountll
#define CLEAR(table, v) memset(table, v, sizeof(table));
#define UNIFORM_DOUBLE(a, b) (((b-a)*(double)rand()/RAND_MAX)+a) // [a, b) 
#define UNIFORM_LL(a, b) (ll)UNIFORM_DOUBLE(a, b) // [a, b) 
#define IN(v, lo, hi) ((lo)<=(v) && (v)<(hi))
#define DD(v) cout<<#v<<": "<<v<<endl
#define FI first
#define SE second
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const map<T0, T1>& v) { for( typename map<T0, T1>::const_iterator p = v.begin(); p!=v.end(); p++ ){os << p->first << ": " << p->second << " ";} return os; }
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const pair<T0, T1>& v) { os << v.first << ": " << v.second << " "; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << " "; } return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const set<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const deque<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<vector<T> >& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << endl; } return os; }
template<typename T>void maxUpdate(T& a, T b) {a = max(a, b);}
template<typename T>void minUpdate(T& a, T b) {a = min(a, b);}
string YN(bool v) { return v ? "Yes":"No"; }

#define INF (1LL<<60)

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll N,T;
	while(cin>>N>>T) {
		VI t(N);
		REP(i, N) cin>>t[i];
		ll ans=0;
		REP(i, N) {
			ans+=min(T, (i+1<N?t[i+1]:INF)-t[i]);
		}
		
		cout<<ans<<endl;
	}
	
	return 0;
}


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

#define mp make_pair
#define eb emplace_back
#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#ifdef ONPC
mt19937 rnd(228);
#else
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#endif


const int MAXN = 100;
//#define int long long
const int INF = 1e9;

signed main()
{
    #ifdef FILEIO
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
    #endif

    ios_base::sync_with_stdio(0);
    cin.tie(0);

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

    map<int, int> m;

    auto get = [&](int x){
      if (!m.count(x)) return 0;
      return m[x];
    };

    auto add = [&](int x){
      if (!m.count(x)) m[x] = 0;
      m[x]++;
    };

    ll ans = 0;
    for (int i = 0; i < n; i++){
      ans += (ll)get(i - a[i]);
      add(a[i] + i);
    }

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 13328
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <map>
#include <string>
#include <cstring>
using namespace std;

int main() {
	vector<char>S(3), T(3);
	int ans = 0;
	for (int i = 0; i < 3; i++) {
		cin >> S.at(i);
	}
	for (int i = 0; i < 3; i++) {
		cin >> T.at(i);
	}
	for (int i = 0; i < 3; i++) {
		if (S.at(i) == T.at(i)) ans++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<complex>
#define INF 2147483647
#define llINF 9223372036854775807
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long

using namespace std;
int main(){
  ll a,b,c;string s,s2;
  cin>>a>>b;
  c=1;
  if(a%b==0)
    cout<<"-1"<<endl;
  else{
    bool flag=true;
    while(c<=1e18){
      c*=a;
      if(c%b!=0){
	cout<<c<<endl;
	flag=false;
	break;
      }
    }
    if(flag)
      cout<<"-1"<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i=0; i<(ll)n; i++)
#define REPR(i, n) for(ll i=(ll)n-1; i>=0; i--)
#define FOR(i, m, n) for(ll i=(ll)m; i<(ll)n; i++)
#define FORR(i, m, n) for(ll i=(ll)m-1; i>=(ll)n; i--)
#define ALL(x) (x).begin(), (x).end()
#define ASC(v) sort(ALL(v));
#define DESC(v) sort(ALL(v), greater<int>());
#define UNIQ(a) sort(ALL(a));(a).resize(unique(ALL(a)) - a.begin());
#define PRINTD(x, d) cout << fixed << setprecision(d) << x << "\n";
#define DEBUG(x) cout<<#x<<": "<<x<<"\n"
const double PI = acos(-1);
ll lcm(ll a, ll b) { return a / __gcd(a, b) * b; }
bool isprime(int x){ int i; if(x<2)return 0; else if(x==2) return 1; if(x%2==0) return 0; for(i=3; i*i<=x; i+=2) if(x%i==0) return 0; return 1; }
int digsum(int n) { int r=0; while(n>0) { r+=n%10; n/=10; } return r; }
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
void rcmb(ll *x,ll s,ll r,function<void(ll *)>f){if(r==0){f(x);}else{if(s<0)return;rcmb(x,s-1,r,f);x[r-1]=s;rcmb(x,s-1,r-1,f);}}
void cmb(ll n,ll k,function<void(ll *)>f){ll x[k];rcmb(x,n-1,k,f);}
void prm(ll n,function<void(ll *)>f){ll x[n];for(ll i=0;i<n;i++)x[i]=i;do{f(x);}while(next_permutation(x,x+n));}
void prm(ll n,ll k,function<void(ll *)>f){cmb(n,k,[&](ll *c){prm(k,[&](ll *p){ll x[k];for(ll i=0;i<k;i++){x[i]=c[p[i]];}f(x);});});}
// prm(4, 2, [](ll *x){ cout << x[0] << "," << x[1] << "\n"; });


void solve(double T, double X){
	double res = T/X;
	PRINTD(res, 10);
}

int main(){
	double T, X;
	cin >> T >> X;
    solve(T, X);
    return 0;
}


Measured memory_bytes: 256
//答案错误 
#include<stdio.h>
int main()
{
	double n,m,x,y;
	while(~scanf("%lf%lf%lf%lf",&n,&m,&x,&y)){
		printf("%lf ",n*m/2);
		if(x==n/2&&y==m/2){
			printf("1\n");
		}else{
			printf("0\n");
		}
	}
}

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

using namespace std;
using ll = long long;

ll powll(ll base,ll exp) {
	ll res = 1;
	while(exp>0){
		if(exp & 1)res = res * base;
		base = base * base;
		exp >>= 1;
	}
	return res;
}

int main()
{
	vector<ll> que = {1};
	for(int i = 2; i < 40; i++) {
		for(int j = 2; j < 10; j++) {
			que.push_back(powll(i, j));
		}
	}
	sort(que.begin(), que.end());
	ll x; cin >> x;
	cout << *(upper_bound(que.begin(), que.end(), x)  - 1) << endl;	

}

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

using namespace std;

int main() {
	int N;
	cin >> N;
	vector<int> h(N);
	for (int i = 0; i < N; ++i) { cin >> h[i]; }

	int res = 0;
	while (true) {
		int x = 0;
		for (int i = 0; i < N; ++i) {
			if (h[i] > h[x]) { x = i; }
		}
		if (h[x] == 0) { break; }

		for (int i = x + 1; i < N; ++i) {
			if (h[i] != h[x]) { break; }
			--h[i];
		}
		--h[x];
		++res;
	}

	cout << res << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
    int n ;
    cin >> n ;
    int max = -10000000 ;
    int min = 10000000 ;
    long sum = 0;
    int k ;
    for(int i = 1;i<=n;i++){
        cin >> k ;
        if(max < k){
            max = k;
        }
        if(min > k){
            min = k;
        }
        sum += k ;
    }
    cout << min << " " << max << " " << sum << endl;
}


Measured memory_bytes: 3116
n = int(input())
rec = []
flag = True
t = input()
pre = t[-1]
rec.append(t)
for i in range(1, n):
    s = input()
    if s in rec:
        flag = False
    elif s[0] != pre:
        flag = False
    else:
        rec.append(s)
        pre = s[-1]

if flag:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;

int main(){
	int N,W;
	cin>>N>>W;
	lli w[100],v[100];
	rep(i,N)cin>>w[i]>>v[i];
	vector<lli>wp[4];
	lli wb=w[0];
	rep(i,N){
		wp[w[i]-wb].push_back(v[i]);
	}
	int ln[4];
	rep(i,4){
		sort(wp[i].begin(),wp[i].end(),greater<int>());
		ln[i]=(int)wp[i].size();
	}
	lli sum[4][111];
	sum[0][0]=sum[1][0]=sum[2][0]=sum[3][0]=0;
	rep(j,4)rep1(i,ln[j])sum[j][i]=sum[j][i-1]+wp[j][i-1];
	lli ans=0;
	rep(i0,ln[0]+1)rep(i1,ln[1]+1)rep(i2,ln[2]+1)rep(i3,ln[3]+1){
		if(i0*wb+i1*(wb+1)+i2*(wb+2)+i3*(wb+3)>W)continue;
		ans=max(ans,sum[0][i0]+sum[1][i1]+sum[2][i2]+sum[3][i3]);
	}
	cout<<ans;
}

Measured memory_bytes: 256
# coding: utf-8

n, q = map(int, input().split())
s = input()

t = [0]*(n+1)
for i in range(n):
    if s[i:i+2] == 'AC':
        t[i+1] = t[i] + 1
    else:
        t[i+1] = t[i]

for i in range(q):
    l,r = (map(int, input().split()))
    ans = t[r-1] - t[l-1]
    print(ans)


Measured memory_bytes: 6060
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <stack>
#include <math.h>
#include <string.h>
#include <map>
#include <bitset>
#define Z class
#define ln cout<<'\n'
#define ll long long
#define rep(i, n) for(int i = 0; i < (n); ++i)
//ASCII a=97, A=65
// int H[N]; rep(i,N) scanf("%d", &H[i]);
// int max_x = *std::max_element(x.begin(), x.end());
// int min_y = *std::min_element(y.begin(), y.end());
// sort(vec.begin(), vec.end()); std::greater<>()
// reverse(vec.begin(), vec.end());
// scanf("%s",s);
// printf("%d\n",end-start+1);
// ceil (a + (b - 1)) / b

using namespace std;
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;}
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}

int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
const long long INF = 1LL << 60;


int main(){

    int N, M; cin >> N >> M;
    int L, R;
    int maxL = 0;
    int minR = 1000000;
    rep (i, M) {
        cin >> L >> R;
        if (L > maxL) maxL = L;
        if (R < minR) minR = R;
    }
    
    if (maxL > minR) {
        cout << 0 << endl;
    } else {
        cout << minR - maxL + 1 << endl;
    }
}


Measured memory_bytes: 256
n=int(input())
A=list(map(int,input().split()))
a=sum(A)
a=a**2
b=0

for j in range(n):
  b+=A[j]**2
if a-b<0:
  c=a-b
  while c<=0:
    c+=mod
  
  ans=c//2
  ans=ans%(10**9+7)
 
else:
  ans=(a-b)//2
  ans=ans%(10**9+7)
 
print(ans)

Measured memory_bytes: 31316
#include<bits/stdc++.h>
#define int long long
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
#define mod 1e9
int32_t main() {
	int n;
	string s;
	cin>>n>>s;
	int ans=0,cur=0;
	for(auto c:s)
	{
		if(c=='I')
			cur++;
		else cur--;
		ans=max(ans,cur);
	}	
	cout<<ans<<"\n";
		
}
						

Measured memory_bytes: 384
#define    ll           long long
#define    dn           double
#define    mp           make_pair
#define    pb           push_back
#define    se           second
#define    fi           first
#define    mod          1000000007
#define    sob(v)       v.begin(),v.end()
#define    sobr(v)      v.rbegin(),v.rend()
#define    fr(i,a,b)    for(int i=a;i<=b;++i)
#define    frr(i,a,b)   for(int i=a;i>=b;--i)
#define    pi           acos(-1.00)
#define    check        cout<<"*"<<endl
#define    ffix(x)      cout<<fixed<<setprecision(x)
#define    fast         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)

#include<bits/stdc++.h>
#include<string.h>
using namespace std;

typedef vector<int> vi;
typedef map<int,int> mii;
typedef pair<int,int> pii;
typedef pair<int,vi> pp;

int dr[8]= {0,0,-1,1,-1,-1,+1,+1};
int dc[8]= {-1,1,0,0,-1,+1,-1,+1};

const int N=1000005;

inline void normal(ll &a){if(a>mod) a%=mod; (a<0) && (a+=mod);}
inline ll mod_mul(ll a,ll b){normal(a),normal(b); return (a*b)%mod;}
inline ll mod_add(ll a,ll b){normal(a),normal(b); return (a+b)%mod;}
inline ll mod_sub(ll a,ll b){normal(a),normal(b); a-=b; normal(a); return a;}
inline ll mod_pow(ll a,ll b){ll r=1; while(b>0){if(b&1)r=mod_mul(r,a); a=mod_mul(a,a); b>>=1;} return r;}
inline ll mod_inverse(ll a){return mod_pow(a,mod-2);}
inline ll mod_div(ll a,ll b){return mod_mul(a,mod_inverse(b));}

int main()
{
    int n;
    cin>>n;
    ll a[n+1];
    fr(i,1,n)cin>>a[i];
    ll pre[n+1],ans=0;
    pre[n]=a[n];
    frr(i,n-1,1)
    {
        pre[i]=(pre[i+1]+a[i])%mod;
        ans=(ans+a[i]*pre[i+1]%mod)%mod;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 6700
#include <stdio.h>

int main()
{
    int n,v[20],c[20],d = 0;
    scanf("%d",&n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d",&v[i]);
    }
    for (int i = 0; i < n; i++)
    {
        scanf("%d",&c[i]);
        if(v[i] - c[i] > 0)d += v[i] - c[i];
    }

    printf("%d",d);
}

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpll = vector<pll>;
struct Edge {
	ll to;
	ll cost;
};
using Graph = vector<vector<Edge>>;

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define ALL(a) (a).begin(), (a).end()
/***** define constant start *******/
const ll MOD = 1000000007;
const double PI = 2.0 * asin(1.0);
const ll INF = 1L<<60;
string abc = "abcdefghijklmnopqrstuvwxyz";
string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ll MAX = (ll)pow(10,7);
/****** define constant end ********/
/****** define variable start ******/
/******* define variable end *******/
map<ll, ll> m;

ll a, b, c, d;
ll saiki(ll n){
	if(n == 0) return 0;
	if(n == 1) return d;
	if(m[n]) return m[n];
	ll l2 = (n / 2) * 2;
	ll r2 = ((n+1)/2) * 2;
	ll l3 = (n / 3) * 3;
	ll r3 = ((n+2)/3) * 3;
	ll l5 = (n / 5) * 5;
	ll r5 = ((n+4)/5) * 5;
	ll res = INF;
	if(n < res / d) res = n * d;
	res = min(res, abs(l2 - n) * d + a + saiki(l2/2));
	res = min(res, abs(r2 - n) * d + a + saiki(r2/2));
	res = min(res, abs(l3 - n) * d + b + saiki(l3/3));
	res = min(res, abs(r3 - n) * d + b + saiki(r3/3));
	res = min(res, abs(l5 - n) * d + c + saiki(l5/5));
	res = min(res, abs(r5 - n) * d + c + saiki(r5/5));

	m[n] = res;
	return res;
}
int solve() {
	ll t;
	cin >> t;
	REP(time, t){
		ll n;
		cin >> n >> a >> b >> c >> d;
		// n and f(n)
		m.clear();
		cout << saiki(n) << endl;
	}

	return 0;
}

int main() {
	//clock_t start = clock();
	cout << std::fixed << std::setprecision(10);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int end_solve = solve();
	/*
	clock_t end = clock();
	const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC *
	1000.0; printf("time %lf[ms]\n", time);
	*/

	return end_solve;
}


Measured memory_bytes: 4416
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1000000010
#define EPS 1e-9
#define F first
#define S second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define lp(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"

typedef pair<int,int> PII;
typedef pair<int,string> PIS;
typedef pair<string,int> PSI;


signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  int a[3][3];
  rep(i,3) rep(j,3) cin>>a[i][j];
  int n;
  cin>>n;
  rep(i,n){
    int b;
    cin>>b;
    rep(j,3){
      rep(k,3){
	if(a[j][k]==b) a[j][k]=0;
      }
    }
  }
  /* rep(i,3){
    rep(j,3){
      cout<<a[i][j]<<" ";
    }
    cout<<endl;
    }*/
  rep(i,3){
    int cnt=0;
    rep(j,3){
      if(a[i][j]==0) cnt++;
    }
    if(cnt==3){cout<<"Yes"<<endl;return 0;}
  }
  rep(i,3){
    int cnt=0;
    rep(j,3){
      if(a[j][i]==0) cnt++;
    }
    if(cnt==3){cout<<"Yes"<<endl;return 0;}
  }
  int cnt=0,cnt2=0;
  rep(i,3){
    
    if(a[i][i]==0) cnt++;
    if(a[2-i][i]==0) cnt2++;
    if(cnt==3 || cnt2==3){cout<<"Yes"<<endl;return 0;}
  }
  cout<<"No"<<endl;
  return 0;
}


Measured memory_bytes: 256
use std::io;
use std::str::FromStr;

fn main() {
    let s = getline();
    let k = read();
    let ss : Vec<char> = s.chars().collect();
    for i in 0..(std::cmp::min(k, s.len())) {
        if ss[i] != '1' {
            println!("{}", ss[i]);
            return
        }
    }
    println!("{}", 1);
}



#[allow(dead_code)]
fn getline() -> String {
    let mut ln = String::new();
    io::stdin().read_line(&mut ln).ok();
    ln.trim().to_string()
}

#[allow(dead_code)]
fn read<T>() -> T where T : FromStr {
    let mut ln = String::new();
    io::stdin().read_line(&mut ln).ok();
    ln.trim().parse().ok().unwrap()
}

#[allow(dead_code)]
fn reads<T>() -> Vec<T> where T : FromStr {
    let mut ln = String::new();
    io::stdin().read_line(&mut ln).ok();
    ln.trim().split_whitespace().map(|x| x.parse().ok().unwrap()).collect()
}



Measured memory_bytes: 4352
#include <bit>
#include <bitset>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <iomanip>

typedef long double ld;
typedef long long ll;

using namespace std;


/* TEMPLATE ENDS HERE */

#define MAXN (1 << 12)
#define INF (1 << 30)

ll n, k, q;
ll a[MAXN];

bool ok(ll d) {
	for (int i = 0; i < n; i++) {
		ll curl = a[i];
		ll curr = a[i] + d;
		ll ii = 0;
		ll cnt = 0;
		while (ii < n) {
			ll jj = ii;
			ll cntint = 0;
			ll cntlarge = 0;
			while ((jj < n) && (a[jj] >= curl)) {
				if (a[jj] <= curr) {
					cntint++;
				} else {
					cntlarge++;
				}
				jj++;
			}
			ll cntleft = max(0LL, k - 1 - cntlarge);
			ll cur = max(cntint - cntleft, 0LL);
			cnt += cur;
			ii = jj + 1;
		}
		if (cnt < q) {
			continue;
		}
		return true;
	}
	return false;
}

int main() {
	cout << fixed << setprecision(12);	
	cin >> n >> k >> q;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	ll l = -1;
	ll r = INF;
	while (r - l > 1) {
		ll m = (l + r) / 2;
		if (!ok(m)) {
			l = m;
		} else {
			r = m;
		}
	}
	cout << r << endl;
	return 0;
}


ll MOD = ((ll)1e9 + 7);

struct mod {
	ll x;

	mod(ll tx = 0) {
		x = tx;
		x %= MOD;
	}
	
	mod& operator=(const ll & tx) {
		x = tx % MOD;
		return *this;
	}
	
	mod& operator=(const mod & m2) {
		x = m2.x;
		return *this;
	}

	mod operator+(const mod& m2) const {
		return mod((x + m2.x) % MOD);
	}

	mod& operator+=(const mod& m2) {
		x += m2.x;
		x %= MOD;
		return *this;
	}

	mod operator-(const mod & m2) const {
		return mod((x - m2.x + MOD) % MOD);
	}

	mod& operator-=(const mod & m2) {
		x -= m2.x;
		x = (x + MOD) % MOD;
		return *this;
	}

	mod operator*(const mod & m2) const {
		return mod((x * m2.x) % MOD);
	}

	mod& operator*=(const mod & m2) {
		x *= m2.x;
		x %= MOD;
		return *this;
	}

	mod mypow(ll k) const {
		mod ret = 1;
		mod cur = x;
		while (k) {
			if (k & 1) {
				ret *= cur;
			}
			cur *= cur;
			k >>= 1;
		}
		return ret;
	}

	mod inv() const {
		return mypow(MOD - 2);
	}

	mod operator/(const mod & m2) const {
		return (*this) * m2.inv();
	}

	mod& operator/=(const mod & m2) {
		x *= m2.inv().x;
		x %= MOD;
		return *this;
	}

	bool operator<(const mod & m2) const {
		return x < m2.x;
	}
};

ostream &operator<<(ostream & os, const mod & m) {
	return os << m.x;
}



Measured memory_bytes: 3652
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <set>
#include <queue>
#define mod 1000000007
#define ten5 100005
#define PI 3.1415926
using namespace std;

int num[201];

int main()
{
    //int m,n,o=0,i,j,k;
    long long int sum=0,sum2=0,n1=0,n2=0,n3;
    double ans=0.0,half;
    long long int m,n,o,i,j,k=1,now=1;
    long long int a,a1,a2,a3,a4;
    //float f,g,h;
    //char now,pre;
    string s,s1;
    priority_queue<int> pq;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>m;
        pq.push(m);
    }
    for(i=0;i<n;i++)
    {
        if(i%2==0) sum+=pq.top();
        else sum-=pq.top();
        pq.pop();
    }
    cout<<sum;
    return 0;
}



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


int main() {
	long long N, M;
	cin >> N >> M;
	pair<long long, long long> a[N];
	for(int i = 0; i < N; i++){
		cin >> a[i].first >> a[i].second;
	}
	sort(a, a + N);
	long long i = 0;
	long long ans = 0;
	while(M > 0){
		if(a[i].second < M){
			ans += a[i].first * a[i].second;
			M -= a[i].second;
			i++;
		}
		else{
			ans += a[i].first * M;
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;
using Int = long long int;
using UInt = unsigned long long int;
using VI = vector<unsigned long long int>;

int main(void) {
    string s;
    cin >> s;
    s[3] = '8';
    cout << s << endl;
    return 0;
}


Measured memory_bytes: 3592
/* Filename: ABC046A.java
 * Author: Mushiyo
 */

import java.util.Scanner;

public class Main{

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

		while (input.hasNext()) {
			boolean[] hasColor = new boolean[100 + 1];
			
			for(int i = 0; i < 3; ++i){
				hasColor[input.nextInt()] = true;
			}
			
			int colorCount = 0;
			for(int i = 0; i < hasColor.length; ++i){
				if(hasColor[i]){
					++colorCount;
				}
			}
			
			System.out.println(colorCount);
		}
	}

}


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

using namespace std;

bool attached(int x1, int y1, int x2, int y2, int R, int C){
  return (x1 == 0 || x1 == R || y1 == 0 || y1 == C) && (x2 == 0 || x2 == R || y2 == 0 || y2 == C);
}

int main(){
  int R, C, N;
  cin >> R >> C >> N;
  
  priority_queue<pair<int, int>> pq;
  vector<int> x1(N), y1(N), x2(N), y2(N);
  for(int i = 0; i < N; i++){
    cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
    if(attached(x1[i], y1[i], x2[i], y2[i], R, C)){
      if(x1[i] == 0){
        pq.push({y1[i], i});
      }else if(y1[i] == C){
        pq.push({C + x1[i], i});
      }else if(x1[i] == R){
        pq.push({R + C + C - y1[i], i});
      }else{
        pq.push({R + C + C + R - x1[i], i});
      }
      
      if(x2[i] == 0){
        pq.push({y2[i], i});
      }else if(y2[i] == C){
        pq.push({C + x2[i], i});
      }else if(x2[i] == R){
        pq.push({R + C + C - y2[i], i});
      }else{
        pq.push({R + C + C + R - x2[i], i});
      }
    }
  }
  
  
  stack<int> s;
  while(pq.size()){
    auto [c, num] = pq.top();
    pq.pop();
    
    if(s.size() && s.top() == num){
      s.pop();
    }else{
      s.push(num);
    }
  }
  
  puts(s.empty() ? "YES" : "NO");
  
  return 0;
}

Measured memory_bytes: 6884
#include <stdio.h>
#include <iostream>
#include <vector>
#include <assert.h>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <string>
#include <sstream>
#include <memory.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>
#include <functional>
#include <algorithm>
using namespace std;
typedef long long ll;
int main()
{
	int n;
	scanf("%d", &n);
	vector<int> h(n);
	for (auto &x : h)
		cin >> x;
	vector<int> dp(n);
	dp[n - 2] = abs(h[n - 2] - h[n - 1]);
	for (int i = n - 3; i >= 0; --i)
		dp[i] = min(dp[i + 1] + abs(h[i] - h[i + 1]), dp[i + 2] + abs(h[i] - h[i + 2]));
	printf("%d\n", dp[0]);
	return 0;
}

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

int dfs(int h, int w, vector<vector<int>> &field, vector<vector<int>> &flag) {
    flag[h][w] = 1;
    int dh[] = {-1, -1, 0, 1, 1, 1, 0, -1};
    int dw[] = {0, 1, 1, 1, 0, -1, -1, -1};
    
    for (int i = 0; i < 8; i++) {
        int nh = h + dh[i];
        int nw = w + dw[i];
        if (field[nh][nw] == 1 && flag[nh][nw] == 0) {
            dfs(nh, nw, field, flag);
        }
    }
    return 0;
}


int solve(int H, int W) {
    vector<vector<int>> field(H+2, vector<int>(W+2));
    for (int h = 1; h <= H; h++) {
        for (int w = 1; w <= W; w++) {
            cin >> field[h][w];
        }
    }
    
    int ret = 0;
    vector<vector<int>> flag(H+2, vector<int>(W+2));
    for (int h = 1; h <= H; h++) {
        for (int w = 1; w <= W; w++) {
            if (field[h][w] == 1 && flag[h][w] == 0) {
                dfs(h, w, field, flag);
                ret++;
            }
        }
    }
    return ret;
}

int main(void){
    int h, w;
    vector<int> ans;
    while (1) {
        cin >> w >> h;
        if (!h && !w) break;
        ans.push_back(solve(h, w));
    }
    for (auto &i : ans) {
        cout << i << endl;
    }
    
}



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

int main() {
    int64_t N, K;
    cin >> N >> K;
    vector<int64_t> H(N);
    for (int64_t& h : H) {
        cin >> h;
    }

    sort(H.begin(), H.end(), greater<int64_t>());

    int64_t ans = 0;
    for (int64_t i = 0; i < N; i++) {
        if (i < K) {
            continue;
        }
        ans += H[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
// C++ 14
#include <bits/stdc++.h>
using namespace std;
template <typename T>  ostream& operator<<(ostream& os, const vector<T>& v)  {  os << "[";  for (int i = 0; i < v.size(); ++i) {  os << v[i];  if (i != v.size() - 1)  os << ", ";  }  os << "]";  return os;  }
template <typename T> void print(T v, string s = "\n") { cout << v << s; }
template <typename T> void in(T& v) { cin >> v; }
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)

/*
最大増加幅を記録する
すでにある最大増加幅の場合はcnt + 1する
*/
int main() {
  ll n, t; in(n),in(t);
  vector<ll> A(n);
  loop(i,0,n) in(A[i]);
  set<ll> S;
  ll max_d = 0;
  for (auto &&a: A) {
    S.insert(a);
    max_d = max(max_d, a - *S.begin());
  }
  int cnt = 0;
  S.clear();
  for (auto &&a: A) {
    if (S.count(a-max_d)) {
      cnt++;
    }
    S.insert(a);
  }
  print(cnt);
  return 0;
}


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

//{{{
#if ((_WIN32 || __WIN32__) && __cplusplus < 201103L)
#define lld I64d
#else
#define lld lld
#endif
using namespace std;
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset(a, b, sizeof(a))
#ifdef LOCAL
#include "prettyprint.hpp"
#endif
// clang-format off
void _print() { cerr << "]\033[0m\n"; }
template <typename T> void __print(T x) { cerr << x; }
template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
#ifdef LOCAL
#define debug(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m["; _print(x)
#define debug_arr(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m" << (x) << "\033[0m\n"
#else
#define debug(x...)
#define debug_arr(x...)
#endif
// clang-format on
//}}}

int T;

const int mod = 1e9 + 7;
const int N = 1e4 + 10;
const int K = 110;

int n;
int main()
{
#ifdef LOCAL
    freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
#endif

    while (cin >> n)
    {
        if (n >= 30)
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}


Measured memory_bytes: 3628
import collections

d = {}
n = int(input())
ans = 0
for i in range(n):
    st = list(input())
    st.sort()
    s = ''.join(st)
    m = d.get(s,False)
    if m:
        ans += m
        d[s] = m+1
    else:
        d[s] = 1 
    
print(ans)

Measured memory_bytes: 18192
#include<bits/stdc++.h>
#define taskname "A"
#define pb push_back
#define mp make_pair
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int logn = log2(maxn) + 1;
int x  , y , z;
struct ob{
    int a , b , c;
}a[maxn];
ll lef[maxn] , rig[maxn];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen(taskname".inp", "r")) {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    cin >> x >> y >> z;
    ll res = 0;
    for(int i = 1 ; i <= x + y + z ; ++i){
        cin >> a[i].a >> a[i].b >> a[i].c;
        a[i].a -= a[i].c;
        a[i].b -= a[i].c;
        res += a[i].c;
    }
    sort(a + 1 , a + x + y + z + 1 , [&](const ob & x , const ob & y){
        return x.a - x.b > y.a - y.b;
         });
    priority_queue<int,vector<int>,greater<int>> q;
    for(int i = 1 ; i <= x + y + z ; ++i){
        lef[i] = lef[i - 1] + a[i].a;
        q.push(a[i].a);
        if(q.size() > x){
            lef[i] -= q.top();q.pop();
        }
    }
    while(q.size())q.pop();
    for(int i = x + y + z ; i >= 1 ; --i){
        rig[i] = rig[i + 1] + a[i].b;
        q.push(a[i].b);
        if(q.size() > y){
            rig[i] -= q.top();q.pop();
        }
    }
    ll res1 = -1e18;
    for(int i = x ; i <= x + z ; ++i){
        res1 = max(res1 , lef[i] + rig[i + 1]);
    }
    cout << res1 + res;
}



Measured memory_bytes: 3448
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
pair<long long,long long> p[maxn];
long long f[maxn];
long long s[maxn];
long long total;
long long ans[maxn];
long long find(long long x)
{
	return f[x]==x?x:f[x]=find(f[x]);
}
int main()
{
    long long n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
	{
        f[i]=i;
        s[i]=1;
    }
    for(int i=0;i<m;i++)
	{
    	cin>>p[i].first>>p[i].second;
    }
    total=1LL*n*(n-1)/2;
    for(int i=m-1;i>=0;i--)
	{
        ans[i]=total;
        int x=find(p[i].first);
		int y=find(p[i].second);
        if(x!=y)
		{
            f[y]=x;
            total-=s[x]*s[y];
            s[x]+=s[y];
        }
    }
    for(int i=0;i<m;i++)
    {
    	cout<<ans[i]<<endl;
	}
    return 0;
}

Measured memory_bytes: 5248
#include <bits/stdc++.h>
#include <iostream>
#include <functional>
#include <vector>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <math.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define rep1(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define per1(i,a,n) for (int i=a;i>n;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define endl "\n"
#define pi 3.14159265358979323846264338327950288419716939937510
#define IOS cin.sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll mod=1000000007;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
ll qpow(ll a,ll b){ll s=1;while(b>0){if(b%2==1){s=s*a;}a=a*a;b=b>>1;}return s;}
ll qpowmod(ll a, ll b, ll c){ll res, t;res=1;t=a%c;while(b){if(b & 1){res=res*t%c;}t=t*t%c;b>>=1;}return res;}
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;}
inline long long read(){long long k=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}return k*f;}
inline void write(long long x){if(x<0)x=-x,putchar('-');if(x>9)write(x/10);putchar(x%10+'0');}
// head
double n;
int main()
{
    //IOS;
    cin>>n;
    if((ll)n%2==0)
    {
        cout<<"0.5000000000"<<endl;
    }
    else
    {
        n=0.5+0.5/n;
        printf("%.10f\n",n);
    }
    return 0;
}
/*

*/


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define PRINT(v) for (auto x : (v)) cout <<x <<" " ; cout <<endl;
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using mat = vector<vector<ll>>;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
const int inf = 1001001001;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
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;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}
void hey(){ cout <<"hey" <<endl; }

template<class T> struct edge { int to; T cost;};


int main() {
  int N; cin >>N;
  int K; cin >>K;
  vector<int> h(N); rep(i, N) cin >>h[i];
  vector<int> dp(N, inf);
  dp[0] = 0;
  for (int i=0; i<N; i++){
    for (int j=1; j<=K; j++){
      if (i+j >= N) break;
      chmin(dp[i+j], dp[i] + abs(h[i] - h[i+j]));
    }
  }
  int res = dp[N-1];
  cout <<res <<endl;
}


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

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define ALL(v) v.begin(),v.end()
#define FOR(i, j, k) for(ll i=j;i<k;i++)
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cout<<v[i]<<" "

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<ll, ll> P;
typedef long double ld;
struct Edge{ll from, to, cost;};
struct node{ll cost, to;
  bool friend operator>(node a, node b){
    return a.cost>b.cost;
  }
};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

ll modpow(ll a, ll n, ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

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

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}


/**************************************
** A main function starts from here  **
***************************************/
int main(){
  ll N;
  map<ll, ll> num;
  cin >> N;
  rep(i, N){
    ll tmp;
    cin >> tmp;
    num[tmp]++;
  }
  ll ans = num.size();
  ll cur=0;
  for(auto in : num){
    cur += (in.second%2==0?1:0);
  }
  cout << ans - cur%2 <<endl;

  return 0;
}


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

int main()
{
  typedef long long ll;
  ll N, K;
  cin >> N >> K;
  ll min = 0;
  if (0 != N)
  {
    if (N < K)
    {
      auto min1 = N;
      auto min2 = K - N;
      min = std::min(min1, min2);
    }
    else
    {
      auto min1 = N - (N/K)*K;
      auto min2 = abs(N - (N/K + 1)*K);
      min = std::min(min1, min2);
    }
  }
  cout << min;
  return 0;
}


Measured memory_bytes: 256
#include <ios>
#include <iomanip>
#include <iostream>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>

using namespace std;
typedef long long int ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e9)
#define PI (acos(-1))
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl

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; }
typedef pair <ll,ll> P;

int main()
{
    ll N;
    cin >> N;
    bool flag = false;
    for(int i = 0; i <= 25; i++) {
        for(int j = 0; j <= 15; j++) {
            if (i*4 + j*7 == N) flag = true;
        }
    }
    if(flag) yes;
    else no;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main ()
{
    int N,n,f=0,i;
    char s[1000] ;

    scanf("%d\n",&N) ;
    scanf("%s",&s) ;

    if(N%2!=0){
        printf("No\n") ;
    }
    else{
        n=N/2 ;

        for( i=0;i<n;i++){
            if(s[i]==s[i+n]){
               f=0;
            }
            else{
                f=1 ;
                break ;
            }
        }
        if(f==0){
            printf("Yes\n") ;
        }
        else{
            printf("No\n") ;
        }
    }

    return 0 ;
}


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

const int dx[] = { -1,0,1,0 }, dy[] = { 0,-1,0,1 };
const int INF = 1001001;

int main() {
	int h, w; cin >> h >> w;
	vector<string>maze(h); 
	for (int i = 0; i < h; i++)cin >> maze[i];

	int maxNum = 0;
	for (int sx = 0; sx < h; sx++) {
		for (int sy = 0; sy < w; sy++) {
			if (maze[sx][sy] == '#')continue;

			queue<pair<int, int>>q;
			vector<vector<int>>ans(h, vector<int>(w, INF));
			q.push({ sx,sy }); ans[sx][sy] = 0;
			while (!q.empty()) {
				int x = q.front().first, y = q.front().second;
				q.pop();
				for (int i = 0; i < 4; i++) {
					int nx = x + dx[i], ny = y + dy[i];
					if (nx < 0 || nx >= h || ny < 0 || ny >= w || ans[nx][ny] != INF)continue;
					if (maze[nx][ny] == '#')continue;
					q.push({ nx,ny });
					ans[nx][ny] = ans[x][y] + 1;
				}
			}
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if(maze[i][j]!='#')
					maxNum = max(maxNum, ans[i][j]);
				}
			}
		}
	}
	cout << maxNum << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<sstream>
#include<queue>
#include<set>
#include<map>
#include<stack>
#define i64 long long
#define vi32 vector<int>
#define vi64 vector<long long>
#define  ii pair<int,int>
const long long mod = 1000000007LL, inf = 1e9, linf = 1e18;
using namespace std;
#define pb push_back
#define mp make_pair
#define N 100005	
using namespace std;

int n, k;

int f[100];
int getleft(int k, int id)
{
	int res = 0;
	vi32 t;
	for (int i = 1; i <= k && i <= id; i++)
	{
		res += f[i];
		t.pb(f[i]);
	}
	sort(t.begin(), t.end());
	int ans = res;
	int ll = t.size();
	if (ll < k)
	{
		int i = 0;
		while (i<t.size()&&t[i] < 0 && ll < k)
		{
			ll++;
			ans -= t[i++];
		}
	}
	return max(res, ans);
}
int getright(int k, int id)
{
	int res = 0;
	vi32 t;
	for (int i = n; i >=n-k+1 && i >= id; i--)
	{
		res += f[i];
		t.pb(f[i]);
	}
	sort(t.begin(), t.end());
	int ans = res;
	int ll = t.size();
	if (ll < k)
	{
		int i = 0;
		while (i<t.size()&&t[i] < 0 && ll < k)
		{
			ll++;
			ans -= t[i++];
		}
	}
	return max(res, ans);
}

int main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i++)cin >> f[i];
	
	
	int ans = 0;


	for (int i = 1; i <= n; i++)
	{
		for (int j = i + 1; j <= n+1; j++)
		{
			for (int p = 0; p <= k; p++)
				ans = max(ans, getleft(p, i) + getright(k - p, j));
		}
	}
	cout << ans;

}



Measured memory_bytes: 256