akhauriyash/Code-Regression huggingface dataset:
h,w=map(int,input().split())
a=[]
for i in range(h):
    t=list(map(int,input().split()))
    a.append(t)
b=[]
def e(i,j):
    if i+1<h and a[i+1][j]%2==1:
        a[i][j]-=1
        a[i+1][j]+=1
        b.append([i+1,j+1,i+2,j+1])
        
    elif j+1<w and a[i][j+1]%2==1:
        a[i][j]-=1
        a[i][j+1]+=1
        b.append([i+1,j+1,i+1,j+2])
        
    elif i-1>=0 and a[i-1][j]%2==1:
        a[i][j]-=1
        a[i-1][j]+=1
        b.append([i+1,j+1,i,j+1])
        
    elif j-1>=0 and a[i][j-1]%2==1:
        a[i][j]-=1
        a[i][j-1]+=1
        b.append([i+1,j+1,i+1,j])
        
    elif i+1<h:
        a[i][j]-=1
        a[i+1][j]+=1
        b.append([i+1,j+1,i+2,j+1])
        
    elif j+1<w:
        a[i][j]-=1
        a[i][j+1]+=1
        b.append([i+1,j+1,i+1,j+2])
        
for i in range(h):
    for j in range(w):
        if a[i][j]%2==1:
            e(i,j)
print(len(b))
for i in range(len(b)):
    print(b[i][0],end=' ')
    print(b[i][1],end=' ')
    print(b[i][2],end=' ')
    print(b[i][3])

Measured memory_bytes: 30204
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>

typedef unsigned long long ULLONG;
typedef long long LLONG;
static const LLONG MOD_NUM = 998244353; //1000000007;

template<class _T> static void get(_T& a) {
	std::cin >> a;
}
template<class _T> static void get(_T& a, _T& b) {
	std::cin >> a >> b;
}
template<class _T> static void get(_T& a, _T& b, _T& c) {
	std::cin >> a >> b >> c;
}

static void A();

int main()
{
	A();
	fflush(stdout);
	return 0;
}

static void A()
{
	int N, M;
	get(N);

	std::vector<LLONG> ti(N);
	LLONG sum = 0;
	for (int i = 0; i < N; i++) {
		get(ti[i]);
		sum += ti[i];
	}

	get(M);
	std::vector<std::pair<LLONG, LLONG>> pi(M);
	for (int i = 0; i < M; i++) {
		get(pi[i].first, pi[i].second);
	}

	for (int i = 0; i < M; i++) {
		printf("%lld\n", sum - ti[pi[i].first - 1] + pi[i].second);
	}
}


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

int main(){
  long long N,M=1000000000,f;
  cin>>N;
  f=N%M?1:0;
  printf("0 0 %lld 1 %lld %lld\n",M,M*f-N%M,N/M+f);
  return 0;
}

Measured memory_bytes: 256
import numpy as np
def main():
    n,m,c = list(map(int,input().split(' ')))
    b = list(map(int,input().split(' ')))
    cnt = 0
    b_array = np.array(b)
    for i in range(n):
        a_array = np.array(list(map(int,input().split(' '))))
        if np.sum(a_array*b_array) + c >0:
            cnt +=1
    print(cnt)

if __name__ == '__main__':
    main()

Measured memory_bytes: 12500
// Copyright [2020] <unknown>
#include <bits/stdc++.h>
using namespace std;
// #define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define dbg(x...) { cerr << "\033[32;1m" << #x << " -> "; err(x); }
void err() { cerr << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif

#define sz(x) ((int)x.size())

typedef long long LL;

LL n;

int check(LL n) {
    int ans = 0;
    for (int i=2; i<=n; ++i) {
        LL tn = n;
        while (tn % i == 0)
            tn /= i;
        ans += (tn % i == 1);
    }
    return ans;
}

vector<LL> dfac(LL n) {
    vector<LL> res;
    for (LL i=2; i*i<=n; ++i) {
        if (n % i == 0) {
            res.push_back(i);
            if (i*i!=n)
                res.push_back(n/i);
        }
    }
    sort(res.begin(), res.end());
    return res;
}
LL solve(LL n) {
    if (n == 2)
        return 1;
    auto d1 = dfac(n), d2 = dfac(n-1);
    int ans = sz(d2)+1;
    for (LL x : d1) {

        LL tn = n;
        while (tn % x == 0)
            tn /= x;
        ans += tn % x == 1;
    }
    return ans+1;
}
int main(int argc, char const *argv[]) {
    // code
    // dbg(check(6), check(3141));
    // for (int i=1000; i<=2000; ++i)
    //     if (solve(i) != check(i)) {
    //         dbg(i);
    //         return 0;
    //     }
    LL n;
    cin >> n;
    cout << solve(n) << endl;
    // if (n == 2) {
    //     puts("1");
    // }
    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
string str;
long long ans=0,res=0;
int main()
{
    cin>>str;
    for(int state=0;state<(1<<(str.length()-1));state++)
    {
        for(int i=0;i<str.length();i++)
        {
            res=res*10+str[i]-'0';
            if((state>>i)&1)
                ans+=res, 
                res=0;
        }
        ans+=res,
        res=0;
    }
    cout<<ans<<endl;
    return 0;
}

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

#define FLASH ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
#define MAX 1e9
#define MIN -1e9
#define mod 1000000007
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define mxn 300005
using namespace std;

int main()
{
    FLASH
    map<ll,int> mp;
    for(ll i = 1; i <= 200; i++)
    {
        for(ll j = 1; j <= 200; j++)
        {
            for(ll k = 1; k <= 200; k++)
            {
                ll ans = (i * i) + (j * j) + (k * k) + i * j + j * k + k * i;
                mp[ans]++;
            }
        }
    }
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cout << mp[i] << '\n' ;
    }
    return 0;
}


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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair

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 (b<a) { a=b; return 1; } return 0; }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


i64 gcd(i64 a, i64 b) {
    if (a < b) swap(a, b);

    i64 t;
    while(b > 0) {
        t = a % b;
        a = b;
        b = t;
    }

    return a;
}

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

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

    for (i64 h = 1; h <= 3500; h++) {
        for (i64 n = 1; n <= 3500; n++) {
            i64 l = lcm(lcm(N, h), n);
            i64 numerator = 4 * l / N - l / h - l / n;
            if (numerator <= 0 || l % numerator > 0) continue;
            cout << h << " " << n << " " << (l / numerator) << endl;
            return 0;
        }
    }

    return 0;
}

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

int main(int argc, const char * argv[]) {
    // insert code here...
    int n;
    int A;
    int B;
    int allNum = 0;
    
    cin >> n;
    cin >> A;
    cin >> B;
    
    for(int i = 0; i < n; i++){
        int a;
        int b;
        cin >> a >> b;
        if(a >= A && b >= B){
            allNum ++;
        }
    }
    cout << allNum << endl;
    return 0;
}


Measured memory_bytes: 256
no_ans = 'UNRESTORABLE'
a_z = 'abcdefghijklmnopqrstuvwxyz'


def brute_force(s, t, i):
    if i == len(s):
        strs = ''.join(s)
        if strs.find(t) > -1:
            return strs
        else:
            return no_ans

    if s[i] != '?':
        return brute_force(s, t, i + 1)

    for j in range(len(a_z)):
        s[i] = a_z[j]
        ans = brute_force(s, t, i + 1)
        if ans != no_ans:
            return ans
    s[i] = '?'
    return no_ans


def algo(s, t):
    start = len(s) - len(t)
    for i in range(len(s) - len(t), -1, -1):
        ok = True
        for j in range(len(t)):
            ok = s[i + j] == '?' or s[i + j] == t[j]
            if not ok:
                break
        if ok:
            ans = s[:i] + t + s[i + len(t):]
            return ans.replace('?', 'a')
    return no_ans


if __name__ == '__main__':
    s = input()
    t = input()
    # bf = brute_force(list(s), t, 0)
    # print(bf)
    al = algo(s, t)
    print(al)


Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main(){
    int i,n,mx=1000000000000000000,sum=0;
    cin>>n;
    
    int a[n+2];
    int ans[n+2];
    for(i=0;i<=n;i++){
        cin>>a[i];
    }
    if(!n){if(a[0]==1){cout<<"1";return 0;}
    cout<<"-1";
        return 0;}
    int cnt[n+1];
    cnt[0]=1;
    ans[0]=1;
    cnt[0]-=a[0];
    if(cnt[0]<0){cout<<"-1";return 0;}
    for(i=1;i<=n;i++){
        cnt[i]=2*cnt[i-1]-a[i];
        cnt[i]=min(cnt[i],mx);
        if(cnt[i]<0){cout<<"-1";return 0;}
    }
    ans[n]=a[n];
    for(i=n;i>0;i--){
        if(cnt[i-1]>=ans[i]){
            ans[i-1]=ans[i]+a[i-1];
            continue;
        }
        ans[i-1]=cnt[i-1]+a[i-1];
        //cout<<i-1<<" "<<cnt[i-1]<<" "<<a[i-1]<<endl;
    }
for(i=0;i<=n;i++){//cout<<ans[i]<<" ";
    sum+=ans[i];}
cout<<sum;
    return 0;
}

Measured memory_bytes: 5980
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ll a,b,n;
cin>>a>>b>>n;
if(b>n)
{
    ll ans=(a*n)/b;
    cout<<ans;
}
else{
     ll ans=(a*(b-1))/b;
    cout<<ans;
}
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < n; i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
typedef long long ll;

int main() {
    int a, b, c; cin >> a >> b >> c;
    set<int> s;
    s.insert(a);
    s.insert(b);
    s.insert(c);
    if (s.size() == 2) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

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

int main() {
    string s;
    cin >> s;
    string t;
    for(int i=0;i<s.size()-8;i++){
        t += s.at(i);
    }
    cout << t << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cstring>
#include <utility>
#include <numeric>

using namespace std;

int main(){

    string S;
    cin >> S;
    int K;
    cin >> K;

    string t = S;
    long long firstCnt = 0;
    long long lastCnt = 0;
    long long link = 0;
    long long inner = 0;

    int temp = 0;
    char firstC = S[0];
    for(int i = 0; i < (int)S.size(); i++){
        if(S[i] == firstC){
            firstCnt++;
        }
        else{
            firstC = '!';
            if(S[i - 1] == S[i]){
                temp++;
            }
            else{
                inner += temp / 2;
                temp = 1;
            }
        }
    }
    lastCnt = temp;

    if(firstCnt == (int)S.size()){
        cout << (firstCnt * K) / 2 << endl;
        return 0;
    }

    if(S[0] == S.back()){
        link = (firstCnt + lastCnt) / 2;
    }
    else{
        inner += firstCnt / 2 + lastCnt / 2;
        firstCnt = 0;
        lastCnt = 0;
    }

    long long ans = inner * K + link * (K - 1) + firstCnt / 2 + lastCnt / 2;

    cout << ans << endl;

    return 0;
}

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

using namespace std;

typedef pair<int,int> P;
typedef pair<int,pair<int,int>> PP;
typedef long long ll;

const double EPS = 1e-9;
const int INF = 1e9;
const int MOD = 1e9+7;

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

int main(void) {
	int N;
	cin >> N;
	vector<ll> a(N);
	vector<ll> p(1000001);
	for(int i=0;i<N;i++){
		cin >> a[i];
		p[a[i]]++;
	}
	for(int i=0;i<=1000000;i++)p[i] *= i;
	for(int i=0;i<1000000;i++){
		p[i+1] += p[i];
	}

	int M;
	cin >> M;
	vector<ll> b(M),c(M);
	for(int i=0;i<M;i++){
		cin >> b[i];
	}
	for(int i=0;i<M;i++){
		cin >> c[i];
	}

	for(int i=0;i<M;i++){
		if(p[b[i]] >= c[i])cout << "Yes" << endl;
		else cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 15840
from collections import defaultdict
import math

def Sieve_of_Eratosthenes(maxA):
    lst = [-1]*(maxA+1)
    lst[0] = 0
    lst[1] = 1
    for i in range(2, maxA+1):
        if lst[i] == -1:
            for g in range(i, maxA+1, i):
                if lst[g] == -1:
                    lst[g] = i
    return lst

def factorization(n):  # 「n = 1」はダメ！！！
    d = defaultdict(int)
    now = n
    while True:
        if now == lst[now]:
            if now != 1:
                d[now] += 1
            break
        r = lst[now]
        while now % r == 0:
            now //= r
            d[r] += 1
    return d

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

g = a[0]
for i in range(1, n):
    g = math.gcd(g, a[i])

if g == 1:
    d = defaultdict(int)
    maxA = max(a)
    lst = Sieve_of_Eratosthenes(maxA)
    for m in a:
        fs = factorization(m)
        for f in fs.keys():
            d[f] += 1
    for f in d.values():
        if f != 1:
            print("setwise coprime")
            exit()
    print("pairwise coprime")
else:
    print("not coprime")


Measured memory_bytes: 182028
#include<bits/stdc++.h>
using namespace std;
 
#define             ll  long long
#define            ull  unsigned long long
#define            P_B  push_back
#define            M_P  make_pair
#define         DBG(x)  printf("%s %d\n", #x, x)
#define       DBGLL(x)  printf("%s %lld\n", #x, x)
#define         SCI(x)  scanf("%d",&x)
#define         SCD(x)  scanf("%lf",&x)
#define         SCS(x)  scanf("%s",x)
#define         CLR(x)  memset(x, 0, sizeof(x))
#define        CLRN(x)  memset(x, -1, sizeof(x))
#define        SCLL(x)  scanf("%lld", &x)
#define      FOR(i, n)  for(int i = 0; i < n; i++)
#define  FORR(i, m, n)  for(int i = m; i < n; i++)
#define     SCI2(m, n)  scanf("%d%d", &m, &n)
#define  SCI3(m, n, o)  scanf("%d%d%d",&m, &n, &o)
#define     SCD2(m, n)  scanf("%lf%lf",&m,&n)
#define  SCD3(m, n, o)  scanf("%lf%lf%lf",&m,&n,&o)
#define    SCLL2(m, n)  scanf("%lld%lld", &m, &n)
#define SCLL3(m, n, o)  scanf("%lld%lld%lld",&m, &n, &o)
#define             vi  vector<int>
#define            vii  vector<pair<int, int> >
#define            vll  vector<pair<ll, ll> >
#define            Mod  998244353
#define            INF  1000000000
 

int a[100005][4];
int n;
int dp[100005][4];


int f(int day, int k)
{
	if(day == n) return 0;
	if(dp[day][k]) return dp[day][k];
	if(k == 0){
		int x = max(f(day + 1, 1)+a[day][0], max(f(day+1, 2)+a[day][1], f(day+1, 3) + a[day][2]));
		dp[day][k] = max(dp[day][k], x);
	}
	else if(k == 1){
		int x = max(f(day+1, 2) + a[day][1], f(day+1, 3) + a[day][2]);
		dp[day][k] = max(dp[day][k], x);
	}
	else if(k == 2){
		int x = max(f(day+1, 1) + a[day][0], f(day+1, 3) + a[day][2]);		
		dp[day][k] = max(dp[day][k], x);
	}
	else if(k == 3){
		int x = max(f(day+1, 1) + a[day][0], f(day+1, 2) + a[day][1]);
		dp[day][k] = max(dp[day][k], x);
	}
	return dp[day][k];
}

int main()
{
	SCI(n);
	FOR(i, n)
		FOR(j, 3)
			SCI(a[i][j]);
	printf("%d\n", f(0, 0));    
}

Measured memory_bytes: 9600
#include <cstdio>
int main() {
  int h, w;
  for (;;) {
    scanf("%d%d", &h, &w);
    if (h == 0 && w == 0) break;
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        putchar(((i & 1) ^ (j & 1)) == 0 ? '#' : '.');
      }
      putchar('\n');
    }
    putchar('\n');
  }
  return 0;
}



Measured memory_bytes: 2608
#include<stdio.h>
int main(void) {

	int n;
	int i;
	int h[100];
	int x = 0, y = 0;
	int ans = 0;

	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		scanf("%d", &h[i]);
	}

	while (true) {
		if (x == n)break;
		if (h[x] == 0){
			x++;
			continue;
		}
		if (h[x] > 0) {
			y = x;
			while (h[y] > 0 && y < n) {
				h[y]--;
				y++;
			}
			ans++;
		}
	}

	printf("%d\n", ans);

	return 0;
}

Measured memory_bytes: 128
use std::io::*;
use std::str::FromStr;

fn main() {
    let n: usize = read();

    println!("{}",
        if n % 2 == 0 {
            (n-2) * n / 2
        } else {
            (n-1) * (n-1) / 2
        });
        
    for i in 1..n+1 {
        for j in i+1..n+1 {
            let sum = if n % 2 == 0 { n+1 } else { n };
            if i + j != sum {
                println!("{} {}", i, j);
            }
        }
    }
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


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

int main(){
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;

  vector<int> l(1, 1);
  int ind = 0;
  for (int i = 1; i < n; i++){
    if (s.at(i) != s.at(i - 1)){
      l.push_back(1);
      ind++;
    }else{
      l.at(ind)++;
    }
  }

  int ans = 0;
  for (int i = 0; i < l.size(); i++){
    ans += l.at(i) - 1;
  }

  if (l.size() / 2 <= k){
    ans = n - 1;
  }else{
    ans += 2 * k;
  }

  cout << ans << endl;
}

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

using namespace std;

typedef long long ll;

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

	string S;
	cin >> S;

	int n = (int) S.size();

	int ans1 = 0;
	for(int i  = 0; i < n; i++){
		if(i % 2 == 0 && S[i] == '0'){
			ans1++;
		}else if(i % 2 == 1 && S[i] == '1'){
			ans1++;
		}
	}

	int ans2 = 0;
	for(int i = 0; i < n; i++){
		if(i % 2 == 0 && S[i] == '1'){
			ans2++;
		}else if(i % 2 == 1 && S[i] == '0'){
			ans2++;
		}
	}

	cout << min(ans1, ans2) << endl;
}


Measured memory_bytes: 512
import java.util.*;
public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		String s1 = sc.next();
		String s2 = sc.next();
		String s3 = sc.next();
		System.out.println(s1.substring(0, 1).toUpperCase() + s2.substring(0, 1).toUpperCase() + s3.substring(0, 1).toUpperCase());
	}
}


Measured memory_bytes: 23636
#include <iostream>

using namespace std;

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

    int n;
    cin >> n;
    if (n == 3) {
        cout << 2 << '\n';
        cout << 1 << ' ' << 3 << '\n';
        cout << 2 << ' ' << 3 << '\n';
        return 0;
    }
    if (n == 4) {
        cout << 4 << '\n';
        cout << 1 << ' ' << 2 << '\n';
        cout << 1 << ' ' << 3 << '\n';
        cout << 3 << ' ' << 4 << '\n';
        cout << 2 << ' ' << 4 << '\n';
        return 0;
    }
    if (n & 1) {
        cout << 2 * (n - 1) << '\n';
        cout << 1 << ' ' << n << '\n';
        cout << n - 1 << ' ' << n << '\n';
        for (int i = 0; i < n / 2 - 1; i++) {
            cout << i + 1 << ' ' << i + 2 << '\n';
            cout << i + 1 << ' ' << n - i - 2 << '\n';
            cout << n - i - 1 << ' ' << i + 2 << '\n';
            cout << n - i - 1 << ' ' << n - i - 2 << '\n';
        }
        cout << n / 2 << ' ' << n << '\n';
        cout << n / 2 + 1 << ' ' << n << '\n';
    } else {
        cout << 2 * n << '\n';
        cout << 1 << ' ' << n / 2 << '\n';
        cout << 1 << ' ' << n / 2 + 1 << '\n';
        for (int i = 0; i < n / 2 - 1; i++) {
            cout << i + 1 << ' ' << i + 2 << '\n';
            cout << i + 1 << ' ' << n - i - 1 << '\n';
            cout << n - i << ' ' << i + 2 << '\n';
            cout << n - i << ' ' << n - i - 1 << '\n';
        }
        cout << n << ' ' << n / 2 << '\n';
        cout << n << ' ' << n / 2 + 1 << '\n';
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()


//長さlの中にk個詰め込まれている場合の数(横)
//(l*m)Ck - ((l-1)*m)Ck * 2 + ((l-2)*mCk)
//これはn-l+1の自由度

//n*m-2 C k-2 を最後にかける
//m*m*(1*(n-1) + 2*(n-2) + 3*(n-3) + ... + (n-1) * 1)
//たてもやる

vector<ll> iCk;

ll mpow(ll a, ll b){
	if(b==0){
		return 1;
	}else if(b%2==1){
		return (mpow(a,b-1) * a)%MOD;
	}else{
		ll ret = mpow(a,b/2);
		return (ret*ret)%MOD;
	}
}

int main(void){
	ll n,m,k;
	cin>>n>>m>>k;
	ll ans = 0;
	ll sum = 0;
	reps(i,n-1){
		sum += i*(n-i);
		sum %= MOD;
	}
	sum *= m;
	sum %= MOD;
	sum *= m;
	sum %= MOD;
	ans += sum;

	sum = 0;
	reps(i,m-1){
		sum += i*(m-i);
		sum %= MOD;
	}
	sum *= n;
	sum %= MOD;
	sum *= n;
	sum %= MOD;
	ans += sum;

	ans %= MOD;
	rep(i,k-2){
		ans *= (n*m-2-i);
		ans %= MOD;
		ans *= mpow(k-2-i, MOD-2);
		ans %= MOD;
	}
	cout<<ans<<endl;


	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>

using namespace std;

int f[101][10001],w[101];

int getint()
{
	char ch;int b=1;
	for(ch=getchar();ch>'9'||ch<'0';ch=getchar())if(ch=='-')b=-1;
	int num=ch-'0';
	for(ch=getchar();ch>='0'&&ch<='9';ch=getchar())num=num*10+ch-'0';
	return num*b;
}

int main()
{
	int n=getint();
	for(int i=1;i<=n;i++)w[i]=getint();
	f[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=10000;j++)
		{
			f[i][j]=f[i][j]||f[i-1][j];
			if(j+w[i]<=10000)f[i][j+w[i]]=f[i-1][j]||f[i][j+w[i]];
		}
	}
	int ans=0;
	for(int i=0;i<=10000;i++)
	{
		if(i%10==0)continue;
		if(f[n][i])ans=max(ans,i);
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 4096
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Linq;
using System.Diagnostics;
using System.Globalization;
using static System.Console;
using static System.Math;

namespace agc27_a
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] tmp = ReadLine().Split().Select(int.Parse).ToArray();
            int n = tmp[0];
            int x = tmp[1];
            int[] input = ReadLine().Split().Select(int.Parse).ToArray();

            int cnt=0;
            Array.Sort(input);
            for (int i = 0; i < n; i++)
            {
                if (input[i] < x && i == n-1){
                   break;
                }else if (input[i] <= x){
                   cnt++;
                   x -= input[i];
                }else{
                    break;
                }
            }

            WriteLine(cnt);
        }
    }
}

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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] a = new long[n];

		for (int i = 0; i < n; i++) {
			a[i] = sc.nextLong();
			a[i] -= i + 1;
		}

		Arrays.sort(a);
		long b = (n % 2 == 1) ? a[n / 2] : (a[n / 2] + a[n / 2 - 1]) / 2;
		long sadness = 0;
		for (int i = 0; i < n; i++) {
			sadness += Math.abs(a[i] - b);
		}

		System.out.println(sadness);
	}
}


Measured memory_bytes: 65108
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repn(i,n) for(ll i=0;i<=(ll)(n);i++)
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
//cin.tie(0);
//ios::sync_with_stdio(false);

bool ans=true;

signed main(){
  ll n,m;cin>>n>>m;
  vector<ll> v(n+1,INF);//座標
  vector<vector<pair<ll,ll>> > e(n+1,vector<pair<ll,ll>>(0));//グラフ情報
  vector<bool> f(n+1,false);//通ったか

  for(int i=0;i < m;i++)
  {
    ll l,r,d;cin>>l>>r>>d;
    e[l].pb({r,d});
    e[r].pb({l,-d});
  }

  stack<ll> s;
  for(int i=1;i <= n;i++)
  {
    if(!f[i]){
      s.push(i);
      s.push(0);
    }
    
    while(!s.empty()){
      ll x=s.top();s.pop();
      ll num=s.top();s.pop();
      f[num]=true;

      if(x!=v[num] && v[num]!=INF){ans=false;}
      else v[num]=x;

      for(int j=0;j < siz(e[num]);j++)
      {
        if(!f[e[num][j].fi]){
          s.push(e[num][j].fi);
          s.push(v[num]+e[num][j].se);
        }
      }
    }
  }

  if(ans)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 15488
#include <bits/stdc++.h>
using namespace std;
#define REP(i,N) for(int i=0;i<N;i++)
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

int main(void){
  int N,K;cin >> N >> K;
  ll h[N];
  REP(i,N) cin >> h[i];
  //dp[i]:i+1番目にたどり着くまでに払うコストの総和の最小値
  ll dp[N];
  dp[0] = 0;
  REP(i,N){
    dp[i+1] = dp[i] + abs(h[i+1]-h[i]);
    REP(j,min(K-1,i)){
      dp[i+1] = min(dp[i+1],dp[i-j-1]+abs(h[i+1]-h[i-j-1]));
    }
  }
  cout << dp[N-1] << endl;
  return 0;
}


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

#define all_of(x) std::begin(x), std::end(x)
#ifdef _GLIBCXX_DEBUG
    #define debug(x) cerr << #x << ": " << x << endl
#else
    #define debug(x) 
#endif

using namespace std;

using LL = long long;

template<typename T>
ostream& operator << (ostream& out, const vector<T>& v) {
    out << "[";
    for(const auto& x : v) {
        out << x << ", ";
    }
    return out << "]";
}
template<typename T>
istream& operator >> (istream& in, vector<T>& v) {
    for(auto& x : v) {
        in >> x;
    }
    return in;
}

template<typename S, typename T>
ostream& operator << (ostream& out, const pair<S, T>& p) {
    return out << "{" << p.first << ", " << p.second << "}";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int N;
    cin >> N;
    vector<int> D(N, 0);
    for(int n = 1; n < N; ++n) {
        for(int q = n; q < N; q += n) {
            D[q]++;
        }
    }
    LL ans = 0;
    for(int n = 1; n < N; ++n) {
        ans += D[n];
    }
    cout << ans << "\n";
    
    
    
    return 0;
}


Measured memory_bytes: 7128
import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    String t = sc.next();
    int length = s.length();
    String ans = "No";
    for (int i = 0; i < length - 1; i++) {
      if (s.equals(t)) {
        ans = "Yes";
        break;
      }
      String rotateS = s.substring(length - 1 - i, length) + s.substring(0, length - 1 - i);
      if (rotateS.equals(t)) {
        ans = "Yes";
        break;
      }
    }
    System.out.println(ans);

  }
}

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }

vector<int> par;
vector<bool> used;
vector<vector<int>> adj;
int last;

void dfs(int n) {
  bool islast = true;
  for (auto x: adj[n]) {
    if (used[x]) continue;
    else {
      used[x] = true; islast = false;
      if (par[n]==-1) par[n] = x;
      else par[x] = n;
      dfs(x);
      break;
    }
  }
  if (islast) last = n;
}

int main() {
  int N, M; cin >> N >> M;
  par.resize(N,-1); used.resize(N,false); adj.resize(N);
  int p1, p2;
  rep(i,M) {
    int A, B; cin >> A >> B; A--; B--;
    adj[A].push_back(B); adj[B].push_back(A);
    if (i==0) { p1 = A; p2 = B; }
  }
  par[p1] = p2; used[p1] = true; used[p2] = true;
  dfs(p2); dfs(p1);
  // debug(all(par)); cout << last << endl;
  vector<int> result;
  while (last!=-1) {
    result.push_back(last+1);
    last = par[last];
  }
  cout << result.size() << endl;
  debug(all(result));
  return 0;
}

Measured memory_bytes: 7160
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD=1e9+7;
const long double Pi=acos(-1);
long double nature(long double a){
  if(a>=0){return a;}
  else{return -1*a;}
}
int main(){
  long double A,B,H,M;
  cin>>A>>B>>H>>M;
  long double time=60.0*H+M;
  long double hour=time/12.0;
  long double minute=M;
  long double sa=nature(hour-minute);
  //cout<<sa<<endl;
  if(sa>=30){sa=60.0-sa;}
  //cout<<sa<<endl;
  long double kakudo=sa*6.0;
  //cout<<kakudo<<endl;
  //cout<<cos(kakudo*Pi/180)<<endl;
  long double answer=A*A+B*B-2*A*B*cos(Pi*kakudo/180);
  long double left=0,right=A+B;
  long double mid=0;
  //cout<<answer<<endl;
  while (right >= left) {
    mid=left+(right-left)/2;
    if (mid*mid == answer) return mid;
    else if (mid*mid >answer)right=mid-0.0000000001;
    else if (mid*mid< answer)left=mid+0.0000000001;
  }
  //cout<<mid<<endl;
  cout << fixed << setprecision(9) << mid << endl;
}

Measured memory_bytes: 4168
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long int


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ull a;
    double b;
    cin>>a>>b;
    ull x=a*(ull)(round((b*100)));
    cout<<x/100;
    return 0;
}




Measured memory_bytes: 3788
// AOJ 3001: GPA JANKEN
// 2017.11.29 bal4u@uu

#include <stdio.h>

typedef struct { int id, a; } T;
T tbl[100002]; int n;
T tbl2[100002];
int p[100002];

char buf[10], *bp;
int getint() { int n = 0; while (*bp >= '0') n = (n<<3) + (n<<1) + (*bp++ & 0xf); return n; }
int getdbl() {
	int n = 0; while (*bp >= '0') n = (n<<3) + (n<<1) + (*bp++ & 0xf);
	if (*bp == '.') { bp++; while (*bp >= '0') n = (n<<3) + (n<<1) + (*bp++ & 0xf);	} return n;
}

int f[4002], vmax, vmin;
void distsort()
{
	int i, x;
	T *tp;

	for (tp = tbl, i = 0; i < n; i++, tp++) f[tp->a]++;
	for (i = vmax-1; i >= vmin; i--) f[i] += f[i+1];
	for (i = 0; i < n; i++) {
		x = tbl[i].a, tbl2[--f[x]] = tbl[i];
	}
}

int main()
{
	int a, i, j, win, draw;

    fgets(bp=buf, 10, stdin), n = getint();
	for (i = 0; i < n; i++) {
		fgets(bp=buf, 10, stdin);
		tbl[i].id = i, tbl[i].a = a = getdbl();
		if (i == 0) vmin = vmax = a;
		else if (a < vmin) vmin = a;
		else if (a > vmax) vmax = a;
	}
	distsort();

	win = n-1, draw = 0;
	for (i = 0, j = 1; j < n; j++) {
		a = tbl2[i].a, draw = 0;
		while (j < n && tbl2[j].a == a) draw++, j++;
		while (i < j) p[tbl2[i].id] = (win-draw)*3 + draw, i++;
		i = j;
		win -= (draw+1);
	}
	for (i = 0; i < n; i++) printf("%d\n", p[i]);
    return 0;
}

Measured memory_bytes: 3508
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

int main() {
    std::cin.tie(0);
    std::ios_base::sync_with_stdio(false);
    for(int N,M; std::cin >> N >> M; ) {
        typedef std::pair<int,int> G;
        std::vector<std::vector<std::pair<int,int>>> g; g.reserve(M*3);
        std::vector<G> i2t; i2t.reserve(M*3);
        int s=0;
        {
            std::map<G,int> t2i;
            auto add = [&g,&t2i,&i2t](const G&t) {
                if(!t2i.count(t)) {
                    t2i[t]=i2t.size();
                    i2t.emplace_back(t);
                    g.resize(i2t.size());
                }
                return t2i[t];
            };
            s=add(G(1,0));
            for(int i=0; i<M; ++i) {
                int p,q,c; std::cin >> p >> q >> c;
                const G tg[4] = {G(p,c),G(q,c),G(p,0),G(q,0)};
                int t[4];
                for(int i=0; i<4; ++i) t[i] = add(tg[i]);
                g[t[0]].emplace_back(t[1],0);
                g[t[1]].emplace_back(t[0],0);
                g[t[0]].emplace_back(t[2],0);
                g[t[2]].emplace_back(t[0],1);
                g[t[1]].emplace_back(t[3],0);
                g[t[3]].emplace_back(t[1],1);
            }
        }
        typedef std::pair<int,int> T;
        std::priority_queue<T,std::vector<T>,std::greater<T>> q;
        q.emplace(0,s);
        std::vector<bool> u(i2t.size(),false);
        int r=-1;
        while(!q.empty()) {
            int d,t;
            std::tie(d,t) = q.top(); q.pop();
            if(i2t[t].first == N){ r=d; break; }
            if(u[t]) continue;
            u[t]=true;
            for(const auto& w:g[t]) {
                if(u[w.first]) continue;
                q.emplace(d+w.second,w.first);
            }
        }
        std::cout << r << std::endl;
    }
}

Measured memory_bytes: 66676
PROGRAM ATCODER

implicit none
integer :: n,k,i
character(len=10) :: s
character(len=1) :: c

read*, n,s,k

c = s(k:k)

do i = 1, len_trim(s)
  if ( s(i:i) /= c ) then
    s(i:i) = '*'
  end if
end do

print'(a)', trim(s) 

END PROGRAM ATCODER

Measured memory_bytes: 256
#include<stdio.h>
int main (void)
{
 int a=0;
 int b=0;
 scanf("%d",&a);
 scanf("%d",&b);
 if(a>b)printf("a > b\n");
 else if(a<b)printf("a < b\n");
 else if(a==b)printf("a == b\n");
 return 0;
}


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

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

ll modpow(ll a, ll p, ll mod){
        if(p == 0) return 1;
        if(p%2 == 0){
            ll half = modpow(a, p/2,mod);
            return half * half % mod;
        }
        else return a * modpow(a,p-1,mod) % mod;
    }

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

    ll N; cin >> N;
    ll x[100005];
    for (int i = 0;i < N;i++){
        cin >> x[i];
    }

    ll mod = 1e9+7;
    ll ans = 0;

    ll tmp = 1;
    for (ll i = 1;i < N;i++){
        tmp = (tmp*i)%mod;
    }

    ll dif = tmp*modpow(2,mod-2,mod)%mod;

    ll cnt = 2;
    for (ll i = 0;i < N-1;i++){
        //cout << tmp << endl;
        ans += (x[i+1]-x[i])*tmp;
        ans %= mod;
        tmp = (tmp+dif) % mod;
        dif = ((dif*cnt)%mod)*modpow(cnt+1,mod-2, mod)%mod; 
        cnt++;
    }

    cout << ans << endl;

    return 0;

}

Measured memory_bytes: 1024
N,A,B=map(int,input().split())
S=input()
L=[0 for i in range(N)]
a=0;b=0
for i in range(N):
    if S[i]=="c":
        continue
    elif S[i]=="a":
        if a+b<A+B:
            L[i]=1
            a+=1
    else:
        if a+b<A+B and b<B:
            L[i]=1
            b+=1
for i in range(N):
    if L[i]==1:
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 4784
using System;
using System.Linq;
using CompLib.Util;

public class Program
{

    public void Solve()
    {
        var sc = new Scanner();
        var n = sc.Next();
        switch (n[n.Length - 1])
        {
            case '3':
                Console.WriteLine("bon");
                break;
            case '0':
            case '1':
            case '6':
            case '8':
                Console.WriteLine("pon");
                break;
            default:
                Console.WriteLine("hon");
                break;
        }
    }

    public static void Main(string[] args) => new Program().Solve();
}

namespace CompLib.Util
{
    using System;
    using System.Linq;

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}


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

int main(){
	int N;
	cin >> N;
	vector<int> D(N);
	for(int i = 0;i<N;i++){
		cin >> D.at(i);
	}
	
	vector<int> dan(105,0);
	int cnt =0;
	for(int i =0;i<N;i++){
		
		dan.at(D.at(i))++;
	}
	for(int i =0;i<105;i++){
		if(dan.at(i)>0){
			cnt++;
		}
	}
	cout << cnt << endl;
}

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

#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll H, W;

int main() {
  cin >> H >> W;

  if (H%3 == 0 || W%3 == 0) {
    cout << 0 << endl;
    return 0;
  }

  ll ans = min(W, H);

  for (int a = 1; a < W; ++a) {
    ans = min(ans, max(H*(W-a), (H-H/2)*a) - min(H*(W-a), (H/2)*a));
  }
  for (int b = 1; b < H; ++b) {
    ans = min(ans, max(W*(H-b), (W-W/2)*b) - min(W*(H-b), (W/2)*b));
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
# 20-08-12再トライ
import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.rank = [0] * n
        self.par = list(range(n))
        self._size = [1] * n  # 木の根のみ有効、集合に属する要素数

    def find(self, x):
        ch = []
        while self.par[x] != x:
            ch.append(x)
            x = self.par[x]
        for c in ch:
            self.par[c] = x

        return x

    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return
        if self.rank[rx] >= self.rank[ry]:
            self.par[ry] = rx
            self._size[rx] += self._size[ry]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
        else:
            self.par[rx] = ry
            self._size[ry] += self._size[rx]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return self._size[self.find(x)]

N, M = [int(x) for x in input().split()]
E = [tuple(int(x) - 1 for x in input().split()) for _ in range(M)]
inconv = [0] * M
inconv[M - 1] = N * (N - 1) // 2
uf = UnionFind(N)

for i in range(M - 1, 0, -1):
    a = E[i][0]
    b = E[i][1]
    inconv[i - 1] = inconv[i]
    if uf.same(a, b):
        continue
    inconv[i - 1] -= uf.size(a) * uf.size(b)
    uf.union(a, b)

for i in range(M):
    print(inconv[i])

Measured memory_bytes: 28800
#include <algorithm>
#include <bitset>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define MOD (1000000007l)
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)

using namespace std;

ll N;
vector<ll> A;
vector<ll> acc;
unordered_map<ll, ll> memo;

ll rec(ll from, ll to) {
  ll key = from * 1000 + to;
  if (memo.count(key)) return memo[key];
  ll ans = 0;
  if (from == to) {
    ans = 0;
  } else if (from + 1 == to) {
    ans = A[from] + A[to];
  } else {
    ans = rec(from,  from) + rec(from + 1, to) + acc[to + 1] - acc[from];
    rep (i,  to - from) {
      if (i == 0) continue;
      ll tmp = rec(from,  from + i) + rec(from + i + 1, to) + acc[to + 1] - acc[from];
      ans = min(ans, tmp);
    }
  }
  memo[key] = ans;
  return ans;
}

void solve() {
  cin >> N;
  A = vector<ll>(N);
  rep (i, N) cin >> A[i];
  acc = vector<ll>(N+1);
  rep (i, N) acc[i+1] = acc[i] + A[i];

  cout << rec(0, N-1) << endl;
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(12);
  cout << fixed;
  solve();
  return 0;
}


Measured memory_bytes: 3748
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
//const int MOD = (int) 1e9 + 7;
const int MOD = 119 << 23 | 1;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int) 1e9 + 23111992;
const ll LINF = (ll) 1e18 + 23111992;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ull isqrt(ull k) {ull r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int mrand() {return abs((int) mt());}
inline int mrand(int k) {return abs((int) mt()) % k;}
#define db(x) cerr << "[" << #x << ": " << (x) << "] ";
#define endln cerr << "\n";

void chemthan() {
    int a, b, c, d; cin >> a >> b >> c >> d;
    vector<vi> dp(c + 1, vi(d + 1));
    dp[a][b] = 1;
    FOR(i, 1, c + 1) FOR(j, 1, d + 1) {
        addmod(dp[i][j], mult(dp[i - 1][j], j));
        addmod(dp[i][j], mult(dp[i][j - 1], i));
        submod(dp[i][j], mult((i - 1) * (j - 1), dp[i - 1][j - 1]));
    }
    cout << dp[c][d] << "\n";
}

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0), cin.tie(0);
    if (argc > 1) {
        assert(freopen(argv[1], "r", stdin));
    }
    if (argc > 2) {
        assert(freopen(argv[2], "wb", stdout));
    }
    chemthan();
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}


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

int main() {
  int N, K;
  cin >> N >> K;
  vector<int>P(N);
  vector<int>C(N);
  for(int i=0; i<N; i++)cin >> P.at(i);
  for(int i=0; i<N; i++)cin >> C.at(i);
  
  int64_t score =0;
  int64_t ans =0;
  int64_t next, count;
  for(int i=0; i<N; i++){
    next =i;
    count =0;
    for(int j=1; j<=K; j++){
      score += C.at(next);
      ans =max(ans, score);
      next = P.at(next)-1;
      if(next == i && count ==0){
        score =(K/j-1)*score;
        j = K-K%j-j;
        ans =max(ans, score);
        count ++;
      }
    }
    score =0;
  }
  
  if(ans ==0){
    sort(C.begin(), C.end());
    ans = C.at(N-1);
  }
  
  cout << ans << endl;
      
}

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

int main()
{
   string s1, s2, ans;
   int n1, n2;
   cin >> s1 >> s2 >> n1 >> n2 >> ans;
   if(ans == s1){
      n1--;
   }
   else{
      n2--;
   }
   cout << n1 << " " << n2 << endl;
   return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y){
  if(x<y){
    swap(x,y);
  }
  while(y>0){
    int  r=x%y;
    x=y;
    y=r;
  }
  return x;
}

int main(){
  int x;
  int y;
  cin >> x >> y;
  
  int ans=gcd(x,y);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3100
#include<stdio.h>
int main(void){
  int a,b,i,c,d;
  scanf("%d%d",&a,&b);
  for(i=1;i<1000000;i++){
    c=i*0.08;
    d=i*0.1;
    
    if(c==a&&d==b){
      printf("%d",i);
      return 0;
    }
  }
    printf("-1");
    return 0;
  }

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

using namespace std;

using ll = long long;


int main(){
	int N;
	cin >> N;
	vector<string> s(N);
	vector<int> t(N);
	
	for (int i=0; i<N; i++){
		cin>>s[i];
		cin >> t[i];		
	}
	
	string X;
	cin >> X;
	
	bool flag = false;
	int sum = 0;
	for (int i=0; i<N; i++){
		if (flag) sum += t[i];
		if (s[i] == X){
			flag = true;			
		}		
	}
	cout<<sum;

	
	
	return 0;
}

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

int n, k, mod = 1e9+7;
long long mn, mx, ans;

int main() {
    cin >> n >> k;
    for (int i = 0; i < k-1; i++){
        mn += i;
        mx += (n-i);
    }
    for (int i = k-1; i <= n; i++){
        mn += i;
        mx += (n-i);
        ans += mx-mn+1;
        ans %= mod;
    }
    cout << ans << "\n";
}


Measured memory_bytes: 3624
#include <iostream>
#include <deque>

int main() {
    int q;
    std::cin >> q;

    std::deque<int> A;

    for (int i = 0; i < q; i++) {
        int op;
        std::cin >> op;
        if (op == 0) {
            int d, x;
            std::cin >> d >> x;
            if (d == 0) {
                A.push_front(x);
            } else if (d == 1) {
                A.push_back(x);
            }
        } else if (op == 1) {
            int p;
            std::cin >> p;
            std::cout << A[p] << std::endl;
        } else if (op == 2) {
            int d;
            std::cin >> d;
            if (d == 0) {
                A.pop_front();
            } else if (d == 1) {
                A.pop_back();
            }
        }
    }
}



Measured memory_bytes: 4640
n,k = map(int,input().split())
denominator = 0
ans = 0

for i in range(1, n + 1):
    tmp = i
    coin = 0
    while k > tmp:
        tmp *= 2
        coin += 1
    denominator = 2 ** coin * n
    ans += 1 / denominator
print(ans)

Measured memory_bytes: 2940
n = int(input())
p = [int(i) for i in input().split()]

cnt = 1
m = p[0]
for i in range(1,n):
	if m > p[i-1]:
		m = p[i-1]
	if m >= p[i]:
		cnt += 1
	#print(cnt,i)
	#print(p[0:i],p[i])
print(cnt)

Measured memory_bytes: 24744