akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.TreeMap;
import java.util.stream.IntStream;

public class Main{
	public static void main(String[]$) throws IOException{
		new Main().solve();
	}
	static FastScanner s=new FastScanner(System.in);
	static IntStream REPS(int v){return IntStream.range(0,v);}
	static IntStream REPS(int l,int r){return IntStream.rangeClosed(l,r);}
	static int gInt() throws IOException{return s.nextInt();}
	static long gLong() throws IOException{return s.nextLong();}
	static long gDouble() throws IOException{return s.nextLong();}

	private void solve() throws IOException{
		TreeMap<Integer,Integer>m=new TreeMap<>();
		for(int i=gInt();i>0;--i) {
			m.merge(gInt(),1,Integer::sum);
		}
		for(int i=gInt();i>0;--i) {
			m.merge(gInt(),-1,Integer::sum);
		}
		System.out.println(m.values().stream().noneMatch(o->o<0)?"YES":"NO");
	}
}
class FastScanner{
	private final BufferedInputStream	in;
	private static final int			bufSize	=1<<16;
	private final byte					buf[]	=new byte[bufSize];
	private int							i		=bufSize;
	private int							k		=bufSize;
	private final StringBuilder			str		=new StringBuilder();

	FastScanner(InputStream in){
		this.in=new BufferedInputStream(in,bufSize);
	}
	int nextInt() throws IOException{
		return (int)nextLong();
	}
	long nextLong() throws IOException{
		int c;
		long x=0;
		boolean sign=true;
		while((c=nextChar())<=32)
			;
		if(c=='-'){
			sign=false;
			c=nextChar();
		}
		if(c=='+'){
			c=nextChar();
		}
		while(c>='0'){
			x=x*10+(c-'0');
			c=nextChar();
		}
		return sign?x:-x;
	}
	int nextChar() throws IOException{
		if(i==k){
			k=in.read(buf,0,bufSize);
			i=0;
		}
		return i>=k?-1:buf[i++];
	}
	String next() throws IOException{
		int c;
		str.setLength(0);
		while((c=nextChar())<=32&&c!=-1)
			;
		if(c==-1){
			return null;
		}
		while(c>32){
			str.append((char)c);
			c=nextChar();
		}
		return str.toString();
	}
	String nextLine() throws IOException{
		int c;
		str.setLength(0);
		while((c=nextChar())<=32&&c!=-1)
			;
		if(c==-1){
			return null;
		}
		while(c!='\n'){
			str.append((char)c);
			c=nextChar();
		}
		return str.toString();
	}
}

Measured memory_bytes: 55584
H, W = map(int, input().split())
a = []
for _ in range(H):
    t = list(input())
    if t.count('.') != W:
        a.append(t)
    # a.append(list(input()))
# x_white = '.' * W
# i, j = 0, 0
# while True:
#     if a[i] == x_white:
#         a.remove(x_white)
#         j += 1
#     else:
#         i += 1
#     if i == H - j:
#         break
# print(a)
for i in range(W):
    y_white = True
    for j in range(len(a)):
        if a[j][i] == '#':
            y_white = False
    if y_white:
        for j in range(len(a)):
            a[j][i] = ''

for i in range(len(a)):
    answer = ''
    for j in a[i]:
        answer += j
    print(answer)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    int N,X;
    cin >> N >> X;
    vector<int> A(N);
    rep(i,N) cin >> A[i];
    // 左端から貪欲法
    ll ans = 0;
    if(A[0]>X){
        ans += A[0] - X;
        A[0] = X;
    }
    for(int i=1;i<N;i++){
        if(A[i-1]+A[i]>X){
            ans += A[i-1]+A[i]-X;
            A[i] = X - A[i-1];
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3748
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <cmath>
#include <iomanip>
#include <map>

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

using namespace std;
using ll = long long;
using P = pair<int,int>;
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;}

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 <typename T>
T GCD(T x, T y)
{
    return (y ? GCD<T>(y, x % y) : x);
}


struct Item{
    Item(int num, string str) : num(num), str(str){};
    int num;
    string str;

    bool operator<( const Item& right ) const {
        return num == right.num ? str < right.str : num < right.num;
    }

};

int main() {
    int N;
    cin >> N;
    map<string, int> mp;
    int max=0;
    rep(i, N){
        string tmp;
        cin >> tmp;
        mp[tmp]+=1;
        max=std::max(mp[tmp], max);
    }

    for(auto& comp : mp){
        if(comp.second<max)
            continue;
        cout<<comp.first<<endl;
    }
}



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

bool is_prime (int x){
  if(x<=1) return false;
  for(int i =2; i*i<=x; i++)
    if(x%i==0) return false;
  return true;
}

signed main(){
  int x;
  cin >> x;
  
  int p = x;
  while(!is_prime(p)) p++;
  
  cout << p << endl;
  return 0;
}

Measured memory_bytes: 256
/*
    Author:zeke

    pass System Test!
    GET AC!!
*/
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
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;
}
typedef pair<ll, ll> P;
typedef vector<ld> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll mod = 1e9 + 7;
ll MOD = 1e9 + 7;
ll INF = 1e18;
// cout << "Case #" << index << " :IMPOSSIBLE";
ll n,k;
bool judge(ld x,V &vec){
    ll res=0;
    for(auto i:vec){
        if(i<=x){
            continue;
        }
        ld temp=i/x;
        if(temp==(ll)temp){
            res--;
        }
        res+=(ll)temp;
     //   cout<<x<<" " <<i<<" "<<temp<<endl;
    }
  //  cout<<x<<" "<<res<<endl;
    return res>k;
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    
    cin>>n>>k;
    V vec(n);
    rep(i,n){
        cin>>vec[i];
    }
    ld MAX=1e18;
    ld MIN=0;
    rep(i,200){
        ld HALF=(MAX+MIN)/2.00;
        if(!judge(HALF,vec)){
            MAX=HALF;
        }else{
            MIN=HALF;
        }
    }
    if(MIN==(ll)MIN){
        cout<<(ll)MIN<<endl;
    }else{
        cout<<(ll)MIN+1<<endl;
    }
  //  cout<<MIN<<endl;
}


Measured memory_bytes: 6448
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10;
const int mod=1e9+7;
int gi() {
    int x=0,o=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
struct matrix {
    int val[3][3];
    matrix() { memset(val,0,sizeof(val)); }
    int* operator[](int x) { return val[x]; }
    void init() { val[1][1]=val[2][2]=1; }
} S,T;
matrix operator*(matrix a,matrix b) {
    matrix ret;
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            for(int k=1;k<=2;k++) ret[i][j]=(ret[i][j]+1ll*a[i][k]*b[k][j]%mod)%mod;
    return ret;
}
int qpow(int a,ll b) {
    int ret=1;
    while(b) {
        if(b&1) ret=1ll*ret*a%mod;
        a=1ll*a*a%mod; b>>=1;
    }
    return ret;
}
matrix qpow(matrix a,ll b) {
    matrix ret;ret.init();
    while(b) {
        if(b&1) ret=ret*a;
        a=a*a; b>>=1;
    }
    return ret;
}
int n,m;
ll k;
char s[N][N];
int main() {
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
    if(k==1) return puts("1"),0;
    int v=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) if(s[i][j]=='#') v++;
    int lr=0,ud=0;
    for(int i=1;i<=n;i++) if(s[i][1]=='#'&&s[i][m]=='#') lr++;
    for(int i=1;i<=m;i++) if(s[1][i]=='#'&&s[n][i]=='#') ud++;
    if(lr&&ud) return puts("1"),0;
    if(!lr&&!ud) return printf("%d\n",qpow(v,k-1)),0;
    int ev=0;
    if(lr) {
        for(int i=1;i<=n;i++)
            for(int j=1;j<m;j++) if(s[i][j]=='#'&&s[i][j+1]=='#') ev++;
    }
    else {
        for(int i=1;i<n;i++)
            for(int j=1;j<=m;j++) if(s[i][j]=='#'&&s[i+1][j]=='#') ev++;
    }
    int V=qpow(v,k-1);
    S[1][1]=1;S[1][2]=0;
    T[1][1]=v;T[1][2]=ev;T[2][2]=lr+ud;
    int E=(S*qpow(T,k-1))[1][2];
    printf("%d\n",(V-E+mod)%mod);
    return 0;
}
//orzgzy
//鸡贼明年进队超稳


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

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[allow(dead_code)]
fn pow_mod(base: usize, power: usize, modulo: usize) -> usize {
    let mut base = base;
    let mut power = power;
    let mut ans = 1;
    while power > 0 {
        if power & 1 == 1 { ans = ans * base % modulo; }
        power >>= 1;
        base = base * base % modulo;
    }
    ans
}

const MOD: usize = 1e+9 as usize + 7;

fn calc_small(s: usize, v: usize) -> usize {
    let mut v = v;
    let mut w = 1;
    let mut base = 1;
    while base * 10 <= v { w += 1; base *= 10; }
    let mut sum = 0;
    loop {
        let rest = base * 10 - v;
        let need = (s - sum) / w;
        if need <= rest {
            v += need;
            sum += need * w;
            break;
        }
        sum += rest * w;
        base *= 10;
        v = base;
        w += 1;
    }
    if sum == s { 1 } else { 0 }
}

fn calc(s: usize, w: usize) -> usize {
    let mut ret = 0;
    if w < 8 {
        let left = std::cmp::max(1, usize::pow(10, w as u32 - 1));
        let right = usize::pow(10, w as u32);
        for i in left..right {
            ret += calc_small(s, i);
        }
    } else {
        let cnt = s / w;
        let rest = s % w;
        if rest == 0 {
            ret = (pow_mod(10, w, MOD) + MOD - pow_mod(10, w - 1, MOD) + MOD - cnt) % MOD;
        }
        if rest < cnt {
            ret = (ret + 1 + (cnt - rest - 1) / (w + 1)) % MOD;
        }
        // println!("{} {} {}", w, cnt, rest);
    }
    ret % MOD
}

fn main() {
    let s: usize = read();
    // println!("{}", calc(123, 3));
    //return;
    let mut min_digit = 1;
    let mut ans = 0;
    loop {
        ans = (ans + calc(s, min_digit)) % MOD;
        if min_digit * min_digit > s { break; }
        min_digit += 1;
    }
    for i in 1.. {
        let target = s / i;
        if target <= min_digit { break; }
        ans = (ans + calc(s, target)) % MOD;
    }
    println!("{}", ans);
}

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

using namespace std;

typedef long long ll;
typedef long double ld;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back

struct State {
    int aI;
    int bI;
    int cI;
    ll cost;

    bool operator<(State o) const {
        if (cost != o.cost) {
            return cost < o.cost;
        }
        if (aI != o.aI) {
            return aI < o.aI;
        }
        if (bI != o.bI) {
            return bI < o.bI;
        }
        return cI < o.cI;
    }
};

ll a[1005];
ll b[1005];
ll c[1005];

int main() {
    int X, Y, Z, K;
    cin >> X >> Y >> Z >> K;

    for (int i = 0; i < X; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < Y; i++) {
        cin >> b[i];
    }
    for (int i = 0; i < Z; i++) {
        cin >> c[i];
    }
    sort(a, a + X, greater<ll>());
    sort(b, b + Y, greater<ll>());
    sort(c, c + Z, greater<ll>());

    priority_queue<State, vector<State>> queue;
    set<State> inQ;

    State sState = {0, 0, 0, a[0] + b[0] + c[0]};
    queue.push(sState);
    inQ.insert(sState);

    for (int i = 0; i < K; i++) {
        State cS = queue.top();
        queue.pop();
        cout << cS.cost << '\n';

        State nS;
        if (cS.aI + 1 < X) {
            nS = {cS.aI + 1, cS.bI, cS.cI, a[cS.aI + 1] + b[cS.bI] + c[cS.cI]};
            if (inQ.find(nS) == inQ.end()) {
                queue.push(nS);
                inQ.insert(nS);
            }
        }
        if (cS.bI + 1 < Y) {
            nS = {cS.aI, cS.bI + 1, cS.cI, a[cS.aI] + b[cS.bI + 1] + c[cS.cI]};
            if (inQ.find(nS) == inQ.end()) {
                queue.push(nS);
                inQ.insert(nS);
            }
        }
        if (cS.cI + 1 < Z) {
            nS = {cS.aI, cS.bI, cS.cI + 1, a[cS.aI] + b[cS.bI] + c[cS.cI + 1]};
            if (inQ.find(nS) == inQ.end()) {
                queue.push(nS);
                inQ.insert(nS);
            }
        }
    }
    cout << flush;
}

Measured memory_bytes: 896
package main 

import (
        "fmt"
        "sort"
)

func main () {
        var n, k, h, an, x, y int
        f := []int{}
        fmt.Scan(&n,&k)
        for i := 0 ; i < n ; i ++ {
                fmt.Scan(&h)
                f = append (f, h)
        }
        sort.Sort(sort.IntSlice(f))
        for i := 0 ; i < n ; i++{
                y = i + k - 1
                if y  < n {
                         x = f[y] - f[i]
                        if an == 0{
                                an = x
                        }  else if an > x{
                                an = x
                        }
                } else {
                        break 
                }
        }
        fmt.Println(an)
}


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

using namespace std;

int main() {

	int x, n;
	cin >> x >> n;
	vector<int> p(n);
	for (int i = 0; i < n; i++) {
		cin >> p[i];
	}
	bool contflg;
	int res = 10000;
	int ress;
	for (int i = 0; i <= 101; i++) {
		contflg = false;
		for (int j = 0; j < n; j++) {
			if (i == p[j]) { contflg = true; break; }
		}
		if (contflg == true) { continue; }

		if (res > abs(x - i)) {
			res = abs(x - i);
			ress = i;
		}

	}

	cout << ress << endl;

	return 0;
}

Measured memory_bytes: 3640
from operator import itemgetter
s=input()
t=input()
u=[]
v=[]
s_len=len(s)
for i in range(s_len):
    s_i=s[i]
    t_i=t[i]
    ts=t_i+s_i
    if s_i!=t_i:
        if ts not in u:
            u.append(ts)
    elif s_i not in v:
        v.append(s_i)
u_len=len(u)
ans="Yes"
if u_len!=0:
    u1=sorted(u)
    u1.append("XX")
    for i in range(u_len):
        if u1[i][0] in v or u1[i][1] in v:
            ans="No"
            break
        elif u1[i][0]==u1[i+1][0] and u1[i][1]!=u1[i+1][1]:
            ans="No"
            break
    if ans=="Yes":
        u2=sorted(u,key=itemgetter(1))
        u2.append("XX")
        for i in range(u_len):
            if u2[i][0]!=u2[i+1][0] and u2[i][1]==u2[i+1][1]:
                ans="No"
                break
print(ans)

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, A, B, C, D;
    cin >> N >> A >> B >> C >> D;
    A--; B--; C--; D--;
    string S;
    cin >> S;

    if(C > D)
    {
        int cnt = 0;
        for(int i=B-1; i<=D+1; i++)
        {
            if(S[i] == '.') cnt++;
            else cnt = 0;
            if(cnt == 3) break;
        }
        if(cnt != 3)
        {
            cout << "No\n";
            return 0;
        }
    }
    int iwa = 0;
    for(int i=0; i<S.size(); i++)
    {
        if(S[i] == '#') iwa++;
        else iwa = 0;
        if(iwa >= 2)
        {
            if((A<=i && i<=C) || (B<=i && i<=D))
            {
                cout << "No\n";
                return 0;
            }
        }
    }

    cout << "Yes\n";

    return 0;
}


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

int main()
{
	int x, y;
	cin >> x >> y;

	for (int i = 0; i <= x; i++)
	{
		if (2 * i + 4 * (x - i) == y)
		{
			cout << "Yes\n";
			return 0;
		}
	}

	cout << "No\n";
}

Measured memory_bytes: 3592
A, V = map(int, input().split())
B,W = map(int, input().split())
T = int(input())

if(A<B):
  a_ans = A + V*T
  b_ans = B + W*T
  if(a_ans>=b_ans):
  	print("YES")
  else:
    print("NO")
else:
  a_ans = A - V*T
  b_ans = B - W*T
  if(a_ans<=b_ans):
  	print("YES")
  else:
    print("NO")


  
#print(a_ans,b_ans)

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

long long int pow5(long long int x) {
    return (x*x*x*x*x);
}

int main() {
    long long int x;
    cin >> x;
    for(long long int i = -3000; i <= 3000; ++i) {
        for(int j = -3000; j <= 3000; ++j) {
            if(pow5(i) - pow5(j) == x) {
                cout << i << " " << j << '\n';
                return 0;
            }
        }
    }
    
    return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;

string field[505];
int ans = 0;
int H, W;
int Left[505][505];
int Right[505][505];
int Up[505][505];
int Down[505][505];

vector<i_i> g(int h, int w) {
    vector<i_i> ret;
    while(Up[h][w] > 0) {
        if(field[Up[h][w]][w] != '.') {
            ret.push_back({Up[h][w], w});
            break;
        }
        Up[h][w]--;
    }
    while(Down[h][w] <= H) {
        if(field[Down[h][w]][w] != '.') {
            ret.push_back({Down[h][w], w});
            break;
        }
        Down[h][w]++;
    }
    while(Left[h][w] > 0) {
        if(field[h][Left[h][w]] != '.') {
            ret.push_back({h, Left[h][w]});
            break;
        }
        Left[h][w]--;
    }
    while(Right[h][w] <= W) {
        if(field[h][Right[h][w]] != '.') {
            ret.push_back({h, Right[h][w]});
            break;
        }
        Right[h][w]++;
    }
    return ret;
}
bool f() {
    for(int h = 1; h <= H; h++) {
        for(int w = 1; w <= W; w++) {
            if(field[h][w] != '.') continue;
            vector<i_i> ret = g(h, w);
            for(int i = 0; i < ret.size(); i++) {
                for(int j = i + 1; j < ret.size(); j++) {
                    if(field[ret[i].first][ret[i].second] == field[ret[j].first][ret[j].second]) {
                        field[ret[i].first][ret[i].second] = '.';
                        field[ret[j].first][ret[j].second] = '.';
                        ans += 2;
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> H >> W;
    for(int h = 1; h <= H; h++) {
        cin >> field[h];
        field[h] = "#" + field[h];
    }
    for(int h = 1; h <= H; h++) {
        for(int w = 1; w <= W; w++) {
            Left[h][w] = w-1;
            Right[h][w] = w+1;
            Up[h][w] = h-1;
            Down[h][w] = h+1;
        }
    }
    while(true) {
        if(!f()) break;
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 7332
from collections import defaultdict

N = int(input())
d = defaultdict(int)


def soinsuu(n):
    while n != 1:
        for i in range(2, int(n**0.5)+1):
            if n % i == 0:
                d[i] += 1
                n = n // i
                break
        else:
            d[n] += 1
            n = 1


for i in range(1, N+1):
    soinsuu(i)
ans = 1
for v in d.values():
    ans = ans * (v+1) % int(1e9+7)
print(ans)

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

using namespace std;

int gcd(int a, int b){
    if(a < b) swap(a, b);
    int r;
    while(r = a % b){
        a = b;
        b = r;
    }
    return b;
}

int main(){
    int n;
    cin >> n;
    int ans, a;
    cin >> ans;
    for(int i = 0; i < n-1; i++){
        cin >> a;
        ans = gcd(ans, a);
    }

    cout << ans << endl;

    

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int const mx = 100010;
    int n;
    cin >> n;
    vector<int> count(mx, 0);
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        count[x]++;
        sum += x;
    }
    int q;
    cin >> q;
    while (q--) {
        int b, c;
        cin >> b >> c;
        sum -= (ll)count[b] * b;
        sum += (ll)count[b] * c;

        count[c] += count[b];
        count[b] = 0;
        cout << sum << "\n";
    }
    return 0;
}


Measured memory_bytes: 3728
#include<stdio.h>
#include<stdlib.h>

typedef long long int int64;

#define MIN(a,b) ((a)<(b)?(a):(b))

void run(void){
  int n,x;
  scanf("%d%d",&n,&x);
  int *a=(int *)malloc(sizeof(int)*n);
  int i;
  for(i=0;i<n;i++) scanf("%d",a+i);
  int *min=(int *)malloc(sizeof(int)*n);
  for(i=0;i<n;i++) min[i]=a[i];
  int64 ans=(int64)1000000000*n;
  int k;
  for(k=0;k<n;k++){
    int64 local=(int64)k*x;
    for(i=0;i<n;i++) local+=min[i];
    ans=MIN(ans,local);
    for(i=0;i<n;i++) min[i]=MIN(min[i],a[(i-k-1+n)%n]);
  }
  printf("%lld\n",ans);
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 128
#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
const int dx[4]={ 1,0,-1,0 };
const int dy[4]={ 0,1,0,-1 };

int N;
ll A[200000];
ll all = 0;

signed main(){
    cin >> N;
    rep(i, N){
        cin >> A[i];
        all ^= A[i];
    }

    rep(i, N) cout << (A[i]^all) << endl;
}

Measured memory_bytes: 5124
H, W = map(int, input().split())
bl = 0
br = 0
for i in range(H):
    line = input().strip()
    foot = []
    for j in range(W):
        if line[j] == '#':
            foot.append(j)
    nl = foot[0]
    nr = foot[-1]
    if nl < br:
        print('Impossible')
        exit()
    bl, br = nl, nr
print('Possible')


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;

long long dp[10][200005];
long long add[200005];
struct node{
    int l;
    long long val;
};
node st[1000005];
int tmp[1000005];
node merge(node x, node y){
    node ans;
    ans.l = x.l+y.l;
    ans.val = (x.val*add[y.l] + y.val)%mod;
    return ans;
}
void push(int n, int s, int e){
    if(tmp[n] == 0) return;
    st[n].val = dp[tmp[n]][st[n].l];
    if(s != e){
        tmp[n+n] = tmp[n];
        tmp[n+n+1] = tmp[n];
    }
    tmp[n] = 0;
}
void build(int n, int s, int e){
    if(s == e){
        st[n].l = e-s+1;
        st[n].val = 1;
    }
    else{
        int mid = (s+e)/2;
        build(n+n, s, mid);
        build(n+n+1, mid+1, e);
        st[n] = merge(st[n+n], st[n+n+1]);
    }
}
void update(int n, int s, int e, int l, int r, int val){
    push(n, s, e);
    if(s > r || l > e) return;
    if(l <= s && e <= r){
        tmp[n] = val;
        push(n, s, e);
        return;
    }
    int mid = (s+e)/2;
    update(n+n, s, mid, l, r, val);
    update(n+n+1, mid+1, e, l, r, val);
    st[n] = merge(st[n+n], st[n+n+1]);
}
int main(){
    int n, q;
    scanf("%d%d", &n, &q);
    add[0] = 1;
    for(int i=1;i<=n;i++) add[i] = add[i-1]*10%mod;
    for(int j=1;j<=9;j++){
        dp[j][0] = 0;
        for(int i=1;i<=n;i++){
            dp[j][i] = (dp[j][i-1]*10 + j)%mod;
        }
    }
    build(1, 1, n);
    for(int i=1;i<=q;i++){  
        int l, r, d;
        scanf("%d%d%d", &l, &r, &d);
        update(1, 1, n, l, r, d);
        printf("%lld\n", st[1].val);
    }
}

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

using namespace std;

static const int INF = 1e9 + 7;

void hawawa()
{
  unsigned long long x, y;
  cin >> x >> y;
  int ans = 0;
  while (x <= y) {
    ans++;
    x *= 2;
  }
  cout << ans << "\n";
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  hawawa();
}

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


Measured memory_bytes: 2052
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
n,m=map(int,input().split())
s=input()
A=[0]*n
B=[0]*n
Edges=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    if a==b:
        if s[a]=='A':
            A[a]+=1
        else:
            B[a]+=1
    else:
        Edges[a].append(b)
        Edges[b].append(a)
        if s[a]=='A':
            A[b]+=1
        else:
            B[b]+=1
        if s[b]=='A':
            A[a]+=1
        else:
            B[a]+=1
Del=[False]*n
q=deque()
for i in range(n):
    if A[i]*B[i]==0:
        q.append(i)
        Del[i]=True
while q:
    u=q.pop()
    l=s[u]
    for v in Edges[u]:
        if Del[v]:
            continue
        if l=='A':
            A[v]-=1
        else:
            B[v]-=1
        if A[v]*B[v]==0:
            q.append(v)
            Del[v]=True
print('No' if sum(Del)==n else 'Yes')

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

using namespace std;

int main() {
    int n,x;
    cin>>n>>x;
    int ans=n;
    int mm=1000;
    int t;
    for(int i =0;i<n;i++){cin>>t;mm=min(mm,t);x-=t;}
    ans+=(x-x%mm)/mm;
    cout<<ans<<endl;
    return 0;
}

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

int MAX = 100;
int A, B;
char G[100][100];
int pos[] = {-1, 0, 1};

void print()
{
    cout << "100 100" << endl;
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            cout << G[i][j];
        }
        cout << endl;
    }
}

bool check(int h, int w, char c)
{
    for (int i = 0; i < 3; i++) {
        int x = h + pos[i];
        if (x < 0 || x >= MAX) {
            continue;
        }
        for (int j = 0; j < 3; j++) {
            int y = w + pos[j];
            if (y < 0 || y >= MAX) {
                continue;
            }
            if (G[x][y] == c) {
                return false;
            }
        }
    }
    return true;
}

main()
{
    cin >> A >> B;

    for (int i = 0; i < MAX; i++) {
        if (i < MAX / 2) {
            for (int j = 0; j < MAX; j++) {
                G[i][j] = '#';
            }
        } else {
            for (int j = 0; j < MAX; j++) {
                G[i][j] = '.';
            }
        }
    }

    for (int i = 1, h = 0, w = 0; i < A;) {
        if (check(h, w, '.')) {
            G[h][w] = '.';
            i++;
            
            w += 2;
            if (w >= MAX) {
                w = 0;
                h += 1;
            }
        } else {
            w += 1;
            if (w >= MAX) {
                w = 0;
                h += 1;
            }
        }
    }

    for (int i = 1, h = MAX-1, w = MAX-1; i < B;) {
        if (check(h, w, '#')) {
            G[h][w] = '#';
            i++;
            
            w -= 2;
            if (w < 0) {
                w = MAX-1;
                h -= 1;
            }
        } else {
            w -= 1;
            if (w < 0) {
                w = MAX-1;
                h -= 1;
            }
        }
    }

    print();
}

Measured memory_bytes: 256
#include <stdio.h>
static int n, p[100001], i, tmp, sum;
int main(void) {
    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
        scanf("%d", p + i);
    for (i = 1; i < n; ++i)
        if (p[i] == i) {
            tmp = p[i];
            p[i] = p[i + 1];
            p[i + 1] = tmp;
            ++sum;
        }
    if (p[n] == i) {
        tmp = p[n];
        p[n] = p[n - 1];
        p[n - 1] = tmp;
        ++sum;
    }
    printf("%d\n", sum);
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
int main( ) {
    //freopen("A.01.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    cout << n/3 << endl; 
    return 0;
}

Measured memory_bytes: 3608
#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; }


int main() {
  string S, T; cin >> S >> T;
  ll l = S.size();
  ll result = 0; rep(i,l) result += S[i]!=T[i];
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 3912
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    if(a<10)
    {
        a=(100*(10-a));
        b+=a;
        cout<<b<<endl;
    }
    else
    {
        cout<<b<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
//-----------------------
// author : xyqkoala
// time : 2020-08-22
//-----------------------

#include<iostream>
#include<vector>
#include<string>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<algorithm>
#include<cmath>
#include<numeric>
using namespace std;

typedef long long LL;
const int MOD = 1e9+7;

void solve();


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


void solve(){
	string str;
	cin>>str;
	int res = 0;
	for(auto item:str){
		res += (item-'0');
		res = (res)%9;
	}
	if(res==0){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
}


Measured memory_bytes: 3744
#include<bits/stdc++.h>
// Begin Header {{{
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i,n) for(ll i=0; i<n; i++)
#define loop(i, j, n) for(ll i=j; i<n; i++)
#define all(x) (x).begin(), (x).end()
constexpr int INF  = 0x3f3f3f3f;
const long long mod=1e9+7;
const long double PI = acos(-1);
// }}} End Header
int main() {
	ll n, sum=0;
	cin >> n;
	vector<ll> a(n);
	map<ll, ll> T;
	rep(i,n){
		cin >> a[i];
		T[a[i]]++;
		sum+=a[i];
	}
	ll q;
	cin >> q;
	rep(i,q){
		ll b, c;
		cin >> b >> c;
		sum = sum-T[b]*b+T[b]*c;
		cout << sum << endl;
		T[c]+=T[b];
		T[b]=0;
	}
	return 0;
}

Measured memory_bytes: 9964
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define pr pair<int,int>
#define mod 1000000007
#define endl "\n"

int power(int a,int b,int m=mod)
{
	if(b==0)	return 1;
	if(b==1)	return a;
	int res=power(a,b/2,m);
	res=(res*res)%m;
	if(b&1)	res=(res*a)%m;
	return res;
}
int modinv(int a,int m=mod){ return power(a,m-2,m);}
int add(int a,int b,int m=mod){	return (a+b)%m;}
int sub(int a,int b,int m=mod){	return (a-b+m)%m;}
int mul(int a,int b,int m=mod){	return (a*b)%m;}
// x<<1 => x*2		x>>1 => x/2;	cout<<flush;
//	cout<<fixed<<setprecision(10)<<ans<<endl;

void fun(int &a,int &b)
{
	if(a==0 && b==0)
		return;
	if(a==0)
		{b=1;return;}
	if(b==0)
		{a=1;return;}
	int g=__gcd(abs(a),abs(b));
	a/=g;
	b/=g;
	if(b>0)	return;
	b*=-1;
	a*=-1;
}

pr opp_pair(int a,int b)
{
	b*=-1;
	if(a<0)
		a*=-1,b*=-1;
	if(b==0)	a=1;
	if(a==0)	b=1;
	return {b,a};
}

void solve()
{
	int n,i;
	cin>>n;
	int a[n],b[n];
	map<pr,int> mp,vis;
	for(i=0;i<n;i++)
	{
		cin>>a[i]>>b[i];
		fun(a[i],b[i]);
		mp[{a[i],b[i]}]++;
	}
	int ans=1;
	for(auto &it:mp)
	{
		pr x={0,0};
		if(vis[it.fi] || it.fi==x)
			continue;
		pr p=opp_pair(it.fi.fi,it.fi.se);
		if(mp.count(p))
		{
			vis[p]=1;
			int val=add(power(2,it.se),power(2,mp[p]));
			ans=mul(ans,sub(val,1));
		}
		else
			ans=mul(ans,power(2,it.se));
	}
	ans=add(ans,mp[{0,0}]-1+mod);
	cout<<ans<<endl;
}

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

Measured memory_bytes: 31708
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>
#include <cmath>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define ENDL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
/* libraries */

signed main() {
	int n;
	std::cin >> n;
	int cp[2] = {0,0};
	int ct = 0;
	rep(i,n) {
		int t,x,y;
		std::cin >> t >> x >> y;
		int dist = std::abs(x-cp[0]) + std::abs(y-cp[1]);
		if(dist>t-ct || (t-ct)%2!=dist%2) {
			print("No");
			return 0;
		}
		ct = t; cp[0] = x; cp[1] = y;
	}
	print("Yes");

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long 
using namespace std ;
const int inf = 1e9;

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

	int a,b,m;
	cin>>a>>b>>m;
	int ref[a],mic[b];
	for(int& i : ref) cin>>i;
	for(int& i : mic) cin>>i;

	int ans = (*min_element(ref,ref+a))+(*min_element(mic,mic+b)); 
	while(m--){
		int x,y,c;
		cin>>x>>y>>c;
		ans = min(ans,ref[x-1]+mic[y-1]-c);
	}
	cout<<ans<<endl; 

	return 0;
}


Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
	public static Scanner sc = new Scanner(System.in);
	public static void main(String[] args){
		//A
		int N = sc.nextInt();
		int K = sc.nextInt();
		if(N%K==0)
		System.out.println("0");
		else
			System.out.println("1");
	}
}


Measured memory_bytes: 21588
#include <bits/stdc++.h>
 
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;
ll a[maxn];
ll ans=1e18;
int main() {
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; i++)
        cin>>a[i];
    int l;
    int r;
    for(int i=1; i+k-1<=n; i++){
        l=i,r=i+k-1;
        ans=min(ans,a[r]-a[l]+min(abs(a[l]),abs(a[r])));
    }
    cout<<ans<<endl;
    return 0;
}

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

class Program
{
    static void Main(string[] args)
    {
        var AB = Console.ReadLine().Split().Select(int.Parse);
        Console.WriteLine((AB.First() - 1) * (AB.Last() - 1));
    }
}

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

using namespace std;
typedef long long ll;
ll n;
ll p[100];
ll p2[100];
bool comp2( const ll left, const ll right){
    return (left <= right);
}
int main(){
    cin >> n;
    for( ll i=0; i<n; i++) cin >> p[i];
    for( ll i=0; i<n; i++) p2[i] = p[i];    

    sort( p2, p2+n, comp2);

    ll cnt = 0;
    for(ll i=0; i<n; i++){
        if( p[i] != p2[i]) cnt++;
        if( cnt > 2 ) break;
    }

    if( cnt > 2 ) cout << "NO" << endl;
    else cout <<"YES"<< endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll     = int64_t;
using ull    = uint64_t;
using prefix = __attribute__((constructor))void;
const ll MOD = 1000000007;
const ll INF = LONG_MAX;

#define elif           else if
#define def            inline auto
#define func           inline constexpr ll
#define up(i,a,n)      for(ll i=(a),i##_1=(n);i<=i##_1;++i)
#define down(i,a,n)    for(ll i=(a),i##_1=(n);i>=i##_1;--i)
#define rep(i,n)       up(i,0,n-1)
#define append(a)      push_back(a)
#define fout           cout<<fixed<<setprecision(10)
#define fasten         cin.tie(0),ios::sync_with_stdio(0)

func    gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
func    lcm(ll a,ll b) {return a*b/gcd(a,b);}
def     dig(ll a)      {return to_string(a).length();}
prefix  init()         {fasten,fout;}

    ll rail[500][500];
signed main(){
    ll N,M,Q,L,R,S;
    cin>>N>>M>>Q;
    rep(i,M){
        cin>>L>>R;
        rail[L-1][R-1]++;
    }
    rep(i,N){
        rep(j,N){
            if(j)rail[i][j]+=rail[i][j-1];
        }
    }
    rep(i,Q){
        cin>>L>>R;
        S=0;
        up(j,L-1,R-1){
            S+=rail[j][R-1]-(L-1?rail[j][L-2]:0);
        }
        cout<<S<<"\n";
    }
}
//for compilation: g++ -o _ _.cpp -std=c++14 (or 17)
//
//for fastening: g++ -O2 -o _ _.cpp -std=c++14 (or 17)
//for fastening: g++ -O3 -mtune=native -march=native -o _ _.cpp -std=c++14 (or 17)


Measured memory_bytes: 2816
#include <bits/stdc++.h>
 
using namespace std;
typedef long long int lli;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef pair <lli,lli> pii;
#define ff first
#define ss second
#define MOD 1000000007
#define pb push_back

bool isrow(vector<vector<int>> &num, int x,int y ){
    for(int i=0; i<3; i++){
        if(num[x][i]!=0) return 0;
    }
    return 1;
}
bool iscol(vector<vector<int>> &num, int x,int y ){
    for(int i=0; i<3; i++){
        if(num[i][y]!=0) return 0;
    }
    return 1;
}
bool isdia(vector<vector<int>> &num, int x,int y ){
    if(num[0][0]==0 && num[1][1]==0 && num[2][2]==0) return 1;
    if(num[0][2]==0 && num[1][1]==0 && num[2][0]==0) return 1;
    return 0;
}

int main(){
	fast;
	bool ans=0;
  	vector<vector<int>> num(3, vector<int> (3));
  	unordered_map<int, pair<int,int> > mp;
  	for(int i=0; i<3; i++){
  	    for(int j=0; j<3; j++){
  	        cin>>num[i][j];
  	        mp[num[i][j]]={i,j};
  	    }
  	}
  	int q; 
  	cin>>q;
  	while(q--){
  	    int t,x,y;
  	    cin>>t;
  	    if(mp.find(t)!=mp.end()){
  	        x=mp[t].ff;
  	        y=mp[t].ss;
  	        num[x][y]=0;
  	        if(isrow(num,x,y) || iscol(num,x,y) || isdia(num,x,y)){
  	            ans=1;
  	        }
  	    }
  	    
  	}
  	if(ans) cout<<"Yes"<<"\n";
  	else cout<<"No"<<"\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lli=long long int;
using vi=vector<int>;  using vs=vector<string>; using gi=greater<int>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define soao(c) sort((c).begin(),(c).end()) //昇順
#define sodo(c) sort((c).begin(),(c).end(),gi()) //降順
#define rev(c) reverse((c).begin(), (c).end())


int main(){
    int n; cin>>n;
    map<string,int> p;
    string S;
    int score_max=0;
    rep(i,n){
        cin>>S;
        if(p.count(S)) p.at(S)++;
        else p[S]=1;
    }
    int max=0;
    for(auto t:p){
        int score=t.second;
        if(score>max) max=score;
    }
    for(auto it=p.begin();it!=p.end();it++){
        if(it->second==max){
            cout<<it->first<<endl;
        }
    }
}

Measured memory_bytes: 25216
// C - GeT AC
#include <bits/stdc++.h>
using namespace std;

int main(){
	int N,Q; string S; cin>>N>>Q>>S;

	vector<int> P(N+1);
	for(int i=0; i<N; ++i)
		P[i+1] = S[i]=='A' && S[i+1]=='C'? P[i]+1: P[i];

	for(int i=0; i<Q; ++i){
		int l,r; cin>>l>>r;
		cout<< P[r-1] - P[l-1] <<endl;
	}

}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct union_find{
  //sizeバージョン
  vector<ll> par;
  vector<ll> size;
  union_find(ll n):par(n),size(n){
    for(ll i=0;i<n;i++){
      par[i]=i;
      size[i]=1;
    }
  }
  ll root(ll x){
    return par[x]==x?x:par[x]=root(par[x]);
  }
  bool same(ll x,ll y){
    return root(x)==root(y);
  }
  void unit(ll x,ll y){
    x=root(x);
    y=root(y);
    if(size[x]<size[y]){
      par[x]=y;
      size[y]+=size[x];
    }else{
      par[y]=x;
      size[x]+=size[y];
    }
  }
  ll treesize(ll x){
    return size[root(x)];
  }
};

int main(){
  ll N,M;
  cin>>N>>M;
  union_find uf(N);
  vector<pair<ll,ll>> dot(M);
  for(ll i=0;i<M;i++){
    ll a,b;
    cin>>a>>b;
    a--,b--;
    dot[M-1-i].first=a;
    dot[M-1-i].second=b;
  }
  
  ll res=N*(N-1)/2;//すべての道順
  
  vector<ll> ans;
  for(ll i=0;i<M;i++){
    ans.push_back(res);
    ll a=dot[i].first;
    ll b=dot[i].second;
    if(uf.same(a,b))continue;
    ll sa=uf.treesize(a);
    ll sb=uf.treesize(b);
    res-=sa*sb;
    uf.unit(a,b);
  }
  reverse(ans.begin(),ans.end());
  for(ll i=0;i<M;i++)cout<<ans[i]<<endl;
}

Measured memory_bytes: 5364
#include <vector>
#include <iostream>
#include <unordered_map>
#include <map>
#include <iomanip>
#include <functional>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <string>
#include <sstream>

using namespace std;

#define x first
#define y second
#define ll long long
#define ld long double
#define pii pair<int,int>
#define wh(x) (x).begin(),(x).end()
#define ri(x) int x;cin>>x;
#define rii(x,y) int x,y;cin>>x>>y;
#define rl(x) ll x;cin>>x;
#define rv(v) for(auto&_cinv:v) cin>>_cinv;
#define wv(v) for(auto&_coutv:v) cout << _coutv << ' '; cout << endl;
#define ev(v) for(auto&_cerrv:v) cerr << _cerrv << ' '; cerr << endl;
#define MOD 1000000007

namespace std { 
template<typename T,typename U>struct hash<pair<T,U>>{hash<T>t;hash<U>u;size_t operator()(const pair<T,U>&p)const{return t(p.x)^(u(p.y)<<7);}};
}
template<typename T,typename F>T bsh(T l,T h,const F&f){T r=-1,m;while(l<=h){m=(l+h)/2;if(f(m)){l=m+1;r=m;}else{h=m-1;}}return r;}
template<typename T,typename F>T bsl(T l,T h,const F&f){T r=-1,m;while(l<=h){m=(l+h)/2;if(f(m)){h=m-1;r=m;}else{l=m+1;}}return r;}
template<typename T> T gcd(T a,T b) { if (a<b) swap(a,b); return b?gcd(b,a%b):a; }

typedef pair<pii,pii> C;

void norm(const C& c, C&r) {
    r=min(min(C{{c.x.y, c.y.x}, {c.y.y, c.x.x}}, C{{c.y.y,c.x.x},{c.x.y,c.y.x}}), min(c, {c.y,c.x}));
}

int get(const C&c, int i) {
    switch(i&3) {
        case 0: return c.x.x;
        case 1: return c.x.y;
        case 2: return c.y.x;
        case 3: return c.y.y;
    }
}

int rot(const C&c) {
    if (c.x == c.y) {
        if (c.x.x == c.x.y) return 4;
        else return 2;
    } else return 1;
}

int main(int,char**) {
    ios_base::sync_with_stdio(false);

    int N; cin >> N;

    unordered_map<C, int> P;
    vector<C> Q;
    for (int i = 0; i < N; i++) {
        int a,b,c,d; cin >> a >> b >> c >> d;
        C x{{a,b},{c,d}};
        norm(x, x);
        P[x] += 1;
        Q.push_back(x);
    }

    ll ans = 0;
    for (int i = 0; i < N; i++) {
        C &p = Q[i];
        for (int j = i+1; j < N; j++) {
            C &q = Q[j];
            for (int k = 0; k < 4; k++) {
                ll cur = 1;
                C u[4];
                for (int l = 0; l < 4; l++) {
                    norm({{get(p,l+1),get(p,l)},{get(q,k-l+1),get(q,k-l)}}, u[l]);
                    int opts = P[u[l]];
                    if (u[l] == p) --opts;
                    if (u[l] == q) --opts;
                    for (int m = 0; m < l; m++) {
                        if (u[m] == u[l]) --opts;
                    }
                    if (opts <= 0) {
                        cur = 0;
                    } else {
                        cur *= opts*rot(u[l]);
                    }
                }
                ans += cur;
            }
        }
    }

    cout << ans/3 << endl;
}


Measured memory_bytes: 76880
N,M,X=map(int,input().split())
CA=[list(map(int,input().split())) for i in range(N)]
from itertools import product
ans=10**9
for p in product((0,1),repeat=N):
    f=[0]*M
    c=0
    for i,x in enumerate(p):
        if x:
            c+=CA[i][0]
            for j in range(M):
                f[j]+=CA[i][j+1]
    a=1
    for j in range(M):
        if f[j]<X:
            a=0
    if a:
        ans=min(ans,c)
print(ans if ans<10**9 else -1)

Measured memory_bytes: 9228
n=int(input())
a=list(map(int,input().split()))
sm=sum(a)
x=[a[0]]
y=[sm-a[0]]
for i in range(1,n):
  x.append(x[i-1]+a[i])
  y.append(sm-x[i])
min=9999999999
for (p,q) in zip(x,y):
  sa=abs(p-q)
  if sa<min:
    min=sa

print(min)

Measured memory_bytes: 29548
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef long double ld;
const double pi=acos(-1.0);
const ll mod=pow(10,9)+7;
const ll INF=pow(2,31)-1;
typedef pair<int,int> P;
typedef vector<int> vi;

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; }

ll gcd(ll a , ll b){
	if(b == 0) return a;
	return gcd(b , a % b);	
}
ll lcm(ll a , ll b){
	ll g = gcd(a , b);
	ll lc = (a/g) * b;
	return lc;
}

int main(){
    ios::sync_with_stdio(false);
    int n; cin >> n;
    int time=0;
    P p[200005];
    rep(i,n){
        cin >> p[i].second >> p[i].first;
    }
    sort(p,p+n);
    int ind=0;
    rep(i,n){
        time+=p[i].second;
        if(time>p[i].first){
            break;
        }
        ind++;
    }
    if(ind==n) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))

using namespace std;

using i32 = int;
using i64 = long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); return a / gcd(a, b) * b; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

void solve() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  int q;
  cin >> q;
  rep(_, q) {
    int k;
    cin >> k;
    i64 d = 0;
    i64 m = 0;
    i64 dm = 0;
    i64 ans = 0;
    for (int r = 1; r <= n; r++) {
      if (s[r - 1] == 'D') {
        d++;
      } else if (s[r - 1] == 'M') {
        m++;
        dm += d;
      }
      if (r - k > 0) {
        int rem = r - k - 1;
        if (s[rem] == 'D') {
          d--;
          dm -= m;
        } else if (s[rem] == 'M') {
          m--;
        }
      }
      if (s[r - 1] == 'C') {
        ans += dm;
      }
    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 1948