akhauriyash/Code-Regression huggingface dataset:
use std::io::*;
use std::str::FromStr;
use std::collections::VecDeque;

fn main() {
    let n: usize = read();
    let m: usize = read();
    
    let mut vec: Vec<Vec<usize>> = vec![vec![]; n];
    for i in 0..m {
        let u: usize = read();
        let v: usize = read();
        vec[u-1].push(v-1);
    }
    let s: usize = read();
    let t: usize = read();

    let mut que: VecDeque<(usize, usize)> = VecDeque::new();
    que.push_front((s-1, 0));
    let mut d: Vec<[bool; 3]> = vec![[false, false, false]; n];
    d[s-1][0] = true;

    let mut ans: i64 = -1;
    while let Some(q) = que.pop_front() {
        let qu = q.0;
        let qd = q.1;
        if qu == t-1 && qd % 3 == 0 {
            ans = (qd / 3) as i64;
            break;
        }
        for i in &vec[qu] {
            if !d[*i][(qd+1)%3] {
                d[*i][(qd+1)%3] = true;
                que.push_back((*i, qd + 1));
            }
        }
    }
    println!("{}", ans);
}

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: 10492
fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let v: Vec<usize> = s.trim().split_whitespace().map(|x| x.parse().unwrap()).collect();
    println!("{}", std::cmp::max(v[0]*v[1], v[2]*v[3]));
}



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

typedef pair<long long, long long> pair_t;

bool comp(const pair_t &a, const pair_t &b){
    return a.first < b.first;
}

void sort2vectors(vector<long long> &A, vector<long long> &B){
    long long n = A.size();
    vector<pair_t> p(n);
    vector<long long> A2(n), B2(n);
    for (long long i = 0; i < n; i++)
            p[i] = make_pair(A[i], B[i]);
    sort(p.begin(), p.end(), comp);
    for (int i = 0; i < n; i++) {
            A2[i] = p[i].first;
            B2[i] = p[i].second;
    }
    A = A2;
    B = B2;
}

void solve(long long N, long long M, std::vector<long long> A, std::vector<long long> B){
    long long cnt = 0;
    long long ans = 0;
    sort2vectors(A, B);
    long long tmp = 0;
    for(long long i = 0; i < N; ++i){
        //cout << A[i] << " " << B[i] << endl;
        tmp = i;
        for(long long j = 0; j < (long long)(B[i]); ++j){
            if(cnt >= M){
                break;
            }
            ans = ans + A[i];
            cnt ++;
        }
    }
    //tmp --;
    //cnt --;
    /*
    cout << cnt << endl;
    for(long long i = 0; i < tmp-1; ++i){
        cnt = cnt - B[i];
    }
    cout << tmp << endl;
    cout << cnt << endl;
    cout << A[tmp] << endl;
    for(long long k = 0; k < tmp-1; ++k){
        ans = ans + A[k] * B[k];
    }

    for(long long l = 0; l < cnt; ++ l){
        ans = ans + A[tmp-1];
    }
    */
    cout << ans << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> A(N);
    std::vector<long long> B(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
        scanf("%lld",&B[i]);
    }
    solve(N, M, std::move(A), std::move(B));
    return 0;
}


Measured memory_bytes: 4992
END { load __FILE__ unless $stdin.eof? }

@m = 10**9 + 7

n = gets.to_i
a = gets.split.map!(&:to_i)

a1sum = a.sum % @m
a2sum = a.inject(0) { |s, ai| (s + ai * ai) % @m }

a_sum = (a1sum * a1sum - a2sum) % @m
a_sum += @m if a_sum.odd?

puts a_sum / 2


Measured memory_bytes: 26548
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <array>
#include <vector>
#include <functional>
#include <unordered_map>
#include <map>
#include <numeric>
#include <limits>
#include <utility>
#include <queue>
#include <random>
#include <bitset>
#include <memory>
#include <complex>
#include<fstream>
#include <chrono>
using namespace std;
typedef long long LL;


int main(void)
{
	
	chrono::system_clock::time_point start, end;
	start = chrono::system_clock::now();
	
	//printf("time %lf[ms]\n", time);
	

	LL D,dim=1;
	cin >> D;
	random_device rnd;
	mt19937 mt(rnd());
	uniform_int_distribution<> randabc(1, 26);
	vector<vector<LL>> t(dim, vector<LL>(D + 1));

	


	vector<int> c(27);
	
	for (int i = 1; i <= 26; i++) {
		cin >> c[i];
	}
	vector<vector<LL>> s(D + 1, vector<LL>(27, 0));
	
	for (int i = 1; i <= D; i++) {
		for (int j = 1; j <= 26; j++) {
			cin >> s[i][j];
		}
	}

	LL man = 0;
	double timee;
	do {
		for (int i = 0; i < dim; i++) {
			for (int j = 1; j <= D; j++) {
				t[i][j] = randabc(mt);
			}
		}
		for (int k = 0; k < dim; k++) {
			vector<LL> last(27, 0);
			man = 0;
			for (int i = 1; i <= D; i++) {
				LL dis = 0;
				man += s[i][t[k][i]];
				last[t[k][i]] = i;
				for (int j = 1; j <= 26; j++) {
					dis += (c[j] * (i - last[j]));
				}
				man -= dis;
				//cout <<man<<endl;
			}
		}
		end = chrono::system_clock::now();
		timee = static_cast<double>(chrono::duration_cast<chrono::microseconds>(end - start).count() / 1000.0);
	}while(man<0 && timee<=1900);



	for (int i = 0; i < dim; i++) {
		for (int j = 1; j <= D; j++) {
			cout << t[i][j] << endl;;
		}
	}


	return 0;
}


Measured memory_bytes: 3744
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<functional>
#include<queue>
#include <iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int i = 0;i < (n);i++)cerr << v[i] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

int main()
{
	int ans = 0,tmp;
	
	REP(i,5)
	{
		cin >> tmp;
		tmp = max(40,tmp);
		ans += tmp;
	}
	
	cout << ans / 5 << endl;
	
	
	return 0;
}

Measured memory_bytes: 3080
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
#define rep2(i,a,n) for(int i=a;i<n;i++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
const int mod =1000000007;
const double PI = acos(-1);
vector<P> edge[100005];
vl seen(100005,INFL);
int main(){
	ll s;cin>>s;
    ll x=1e9,y=1;
    ll yy= s/x+(s%x==0?0:1);
    ll xx= abs(s-x*yy);
    cout<<0<<' '<<0<<' ';
    cout<<x<<' '<<y<<' ';
    cout<<xx<<' '<<yy<<endl;
}

Measured memory_bytes: 6316
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = (s); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for(int i = (n); i >= 0; i--)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(void)
{
    IOS
    const ll LINF = 1LL << 60;
    const int SMAX = 2500;
    using plpii = pair<ll,pii>;
    auto makep = [](const ll time,const int to,const int sil) {
        return make_pair(time,make_pair(to,sil));
    };

    int N, M;
    cin >> N >> M;
    int S; cin >> S;
    vector<vector<plpii>> g(N);
    REP(i,M) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        ll toll, t;
        cin >> toll >> t;
        g[u].push_back(makep(t,v,toll));
        g[v].push_back(makep(t,u,toll));
    }
    vector<ll> C(N),D(N);
    REP(i,N) cin >> C[i] >> D[i];

    S = min(S,SMAX);
    vector<vector<ll>> dp(N,vector<ll>(SMAX+5,LINF));
    dp[0][0] = 0;

    priority_queue<plpii,vector<plpii>,greater<plpii>> dj;

    auto append = [&](plpii p){
        ll time = p.first;
        int cnt = p.second.first;
        int sil = p.second.second;
        if (dp[cnt][sil] < time) return;
        
        // 1回分交換を追加
        if (sil + C[cnt] <= SMAX) {
            int sc = sil+C[cnt];
            ll tc = time + D[cnt];
            if (dp[cnt][sc] > tc) {
                dp[cnt][sc] = tc;
                dj.push(makep(tc,cnt,sc));
            }
        }

        // 辺を通る
        for(auto p2:g[cnt]) {
            ll time2 = time + p2.first;
            int to = p2.second.first;
            int sil2 = sil - p2.second.second;
            if (sil2 < 0) continue;
            if (dp[to][sil2] > time2) {
                dp[to][sil2] = time2;
                dj.push(makep(time2,to,sil2));
            }
        }
    };

    dj.push(makep(0,0,S));

    while(!dj.empty()) {
        plpii x = dj.top(); dj.pop();
        append(x);
    }

    FOR(i,1,N) {
        ll ans = LINF;
        REP(j,SMAX) ans = min(ans,dp[i][j]);
        OUT(ans)
    }

    return 0;
}

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

int main(){
    int n,r;
    cin >> n >> r;
    
    if(n >= 10){
        cout << r << endl;
    }else{
        cout << r + 100*(10 - n) << endl;
    }
}

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

int main(){
    
    int n,m;
    cin >> n >> m;
    vector<int> ans(m,0);
    int k;
    for(int j=0; j<n; j++){
    cin >> k;
    vector<int> a(k);
        for(int i=0; i<k; i++){
            cin >> a.at(i);
            ans.at(a.at(i)-1) += 1;
        }
    }
    int solve = 0;
    for(int i:ans) {
        if(i == n){
            solve += 1;
        }
    }
    cout << solve << endl;
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
#define LL long long

const int maxn=2e5+10;

int n,m,f[maxn],fk[maxn],dep[maxn];
LL k,x[maxn],y[maxn];

int main()
{
#ifdef h10
	freopen("C.in","r",stdin);
	freopen("C.out","w",stdout);
#endif
	int i,pos;
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%lld",&x[i]);
	for (i=n;i>=1;i--) x[i]-=x[i-1];
	for (i=1;i<=n;i++) f[i]=i;
	scanf("%d%lld",&m,&k);
	for (i=1;i<=m;i++)
	{
		scanf("%d",&pos);
		swap(f[pos],f[pos+1]);
	}
	for (i=1;i<=n;i++)
		if (!dep[i])
		{
			int u=i,v,move;
			while (1)
			{
				dep[f[u]]=dep[u]+1;
				u=f[u];
				if (u==i) break;
			}
			for (move=k%dep[i],v=i;move--;) v=f[v];
			for (fk[i]=v;u=f[u],v=f[v],u!=i;) fk[u]=v;
		}
	for (i=1;i<=n;i++) y[i]=x[fk[i]];
	for (i=1;i<=n;i++)
		y[i]+=y[i-1],printf("%lld\n",y[i]);
}


Measured memory_bytes: 5120
#include <iostream>
using namespace std;
static const int size = 10001;
int parent[size];
int rk[size];
void init(){
	for (int i = 0; i < size; ++i){
		parent[i] = i;
		rk[i] = 0;
	}
}
int find(int x){
	if (x == parent[x]){
		return(x);
	}
	else{
		return(parent[x] = find(parent[x]));
	}
}
void unite(int x, int y)
{
	x = find(x);
	y = find(y);
	if (x == y){
		return;
	}
	if (rk[x] < rk[y]){
		parent[x] = y;
	}
	else{
		parent[y] = x;
		if (rk[x] == rk[y]){
			rk[x]++;
		}
	}
}

bool same(int x, int y){
	return(find(x) == find(y));
}

void solve(){
	init();
	int n, q;
	cin >> n >> q;
	for (int i = 0; i < q; ++i)
	{
		int com, x, y;
        cin >> com >> x >> y;
		if (com == 0){
			unite(x, y);
		}
		else
		{
			if (same(x, y)){
				cout << 1 << endl;
			}
			else{
				cout << 0 << endl;
			}
		}
	}
}
int main(){
	solve();
	return 0;
}



Measured memory_bytes: 3172
#include <stdio.h>

int main(int argc, char const *argv[]) {
  int a,b,c;
  int flag=0;
  scanf("%d %d %d",&a , &b, &c );

  if( (a == b + c)  || (b==a+c) || (c==a+b)) flag = 1;
  if(flag==1){
    puts("Yes");
  }else{
    puts("No");
  }

  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
static const int MAX = 200000;
int main(){
  int R[MAX], n;

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

  int maxv = -2000000000;
  int minv = R[0];

  for(int i=1;i<n;i++){
    maxv = max(maxv, R[i] - minv);
    minv = min(minv, R[i]);
  }

  cout << maxv << endl;
}



Measured memory_bytes: 3864
#include <stdio.h>

#define MAX 100000

int partition(int *, int, int);
void swap(int *, int *);

int main(void)
{
	int i, n, pi, A[MAX];
	
	scanf("%d",&n);
	for (i=0; i<n; i++) {
		scanf("%d",&A[i]);
	}
	
	pi = partition(A, 0, n-1);
	
	for (i=0; i<n; i++) {
		if(i>0) printf(" ");
		if(i==pi) printf("[%d]",A[i]);
		else printf("%d",A[i]);
	}
	printf("\n");
	
	return 0;
}

int partition(int *A, int p, int r)
{
	int i, j, q, x;
	
	x = A[r];
	i = p-1;
	for (j=p; j<r; j++) {
		if (A[j] <= x) {
			swap(&A[++i], &A[j]);
		}
	}
	swap(&A[++i], &A[r]);
	return i;
}

void swap(int *a, int *b)
{
	int temp=*a;
	*a = *b;
	*b = temp;
}

Measured memory_bytes: 996
#include <stdio.h>
#include<string.h>
int main(int argc, char *argv[])
{
	char s[100],t[100];
	 while(scanf("%s",s)!=EOF){
 		scanf("%s",t);
 		int n=strlen(s),flag=0;
 		for(int i=0;i<n;i++)
 		{
		 	if(strcmp(s,t)==0){
	 		flag=1;break;	
	 		}
	 		char ch=s[0];
	 		for(int j=0;j<n-1;j++)
	 		 s[j]=s[j+1];
	 		 s[n-1]=ch;
		 }
		if(flag==1)printf("Yes\n");
		else printf("No\n"); 
 	}
	return 0;
}

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

using namespace std;

#define maxn 100007
#define ll long long int
#define db(x) cout<<#x<<" -> "<<x<<" "<<endl
#define db2(x,y) cout<<#x<<"->"<<x<<", "<<#y<<" -> "<<y<<endl
#define db3(x,y,z) cout<<#x<<" -> "<<x<<" , "<<#y<<" -> "<<y<<" , "<<#z<<" -> "<<z<<endl
#define prt(x) for(auto it:x) { cout<<it<<" "; } cout<<endl
#define IN freopen("input.txt","r",stdin)

int main(){
    ios_base::sync_with_stdio(false) ;
    cin.tie(0);
//    IN ;
    int n,m;
    cin>>n>>m;
    vector< ll > V ;
    priority_queue < pair< ll , ll >  > pq;
//    while(!pq.empty()){ cout<<pq.top().first<<" " ; pq.pop() ;}
    for(int i=1; i<=n; i++){
        ll x;
        cin>>x;
        V.push_back(x);
    }
    sort(V.begin(),V.end());
    for(int i=0; i<m; i++){
        ll a,b;
        cin>>a>>b;
        pq.push({b,a});
    }
    int idx = 0 ;
    ll ans = 0LL ;
    while( ! pq.empty() ){
        pair< ll , ll > T = pq.top() ;
        pq.pop() ;
        int c = T.first ;
        int amount = T.second  ;
        if( ( idx + amount ) < n ){
            if( V[ idx + amount ] < c ){ idx = idx+amount ; ans+=(1LL * c*amount) ; }
            else{
                int k = 0 ;
                int a = idx ;
                int i ;
                for(i=a; i < n; i++){
                    if(V[i] >=c ){ break ; }
                    idx++;
                }
                ans+=1LL * (idx-a) * c;
                break ;
            }
        }
        else{
            for(int i=idx ; i < n; i++){
                if( V[ i ] >= c){ break  ; }
                else{
                    ans+=(1LL  * c); idx++;
                }
            }
        }
    }
    for(int i=idx; i <n; i++){
        ans+=V[i];
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N; cin>>N;
  vector<int>A(N);
  vector<int>B(N);
  for(int i=0;i<N;i++)cin>>A[i];
  B=A;
  sort(A.begin(),A.end());
  for(int i=0;i<N;i++){
    if(B[i]>=A[N/2])cout<<A[N/2-1]<<endl;
    else cout<<A[N/2]<<endl;
  }
}

Measured memory_bytes: 4704
#include <iostream> //üoÍ
#include <string>   //¶ñ
#include <vector>   //®Izñ
#include <sstream>  //¶ñtH[}bg

using namespace std;

int main(){
	int n, num;
	cin >> n;
	while(1){
		if(n == 0){ break; }
		vector<int> vec1, vec2;
		for(int i=0;i<n;i++){
			cin >> num;
			vec1.push_back(num);
			cin >> num;
			vec2.push_back(num);
		}
		int x;
		int flag = 1;
		int w = 0;
		for(int j=0;j<vec1.size();j++){
			int min = 9999999;
			for(int i=0;i<vec2.size();i++){
				if(vec2[i]!=-1 && min > vec2[i]){
					min = vec2[i];
					x = i;
				}
			}
			w += vec1[x];
			
			if(w>vec2[x]){
				flag = 0;
				break;
			}
			vec2[x] = -1;
		}
		if(flag==1){ cout << "Yes" << endl; }
		else{ cout << "No" << endl; }

		cin >> n;
		
	}
	
		
		

	return 0;
	
}

Measured memory_bytes: 0
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static void main(String[] args) {
        FastReader sc = new FastReader();
        int a = sc.nextInt();
        int b = sc.nextInt();
        System.out.println(a*b);
    }
}



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

const int mod = 1'000'000'007;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  int ans = 0;
  int x = 0;
  rep(i,n) {
    ans = (ans+(ll)a[i]*x)%mod;
    x = (x+a[i])%mod;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4028
# -*- coding:utf-8 -*-
a, b, c = map(int, input().split())

if a<b and a<c:
    if b<c :
        print(a, b, c)
    else :
        print(a, c, b)
elif b<a and b<c :
    if a<c :
        print(b, a, c)
    else :
        print(b, c, a)
else :
    if a<b :
        print(c, a, b)
    else :
        print(c, b, a)

Measured memory_bytes: 7680
N = int(input())
A = list(map(int, input().split(" ")))
A = [a for a in A if a >= 1]

def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x

temp = A[0]
for i in range(N-1):
    temp = gcd(temp, A[i+1])
    if temp == 1:
        break
print(temp)

Measured memory_bytes: 14224
/*
author : seryu
title : ABC167E_"Colorful Blocks"
*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(all(x), val), x.end())
typedef long long ll;
typedef pair<int, int> P;
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; }
//ll MOD = 1000000007;
ll MOD = 998244353;
int INF = 1001001001;

//Power with MOD: O(logp)
template<typename T>
T mod_pow(T a, int p)
{
	if (p == 0)return 1;
	else if (p == 1)return a;
	else if (p % 2 == 0)
	{
		ll h = mod_pow(a, p / 2);
		return h * h % MOD;
	}
	else return (mod_pow(a, p - 1) * a) % MOD;
}

//Combination using factorial: O(n)
struct comb_fact
{
	int N;
	vector<ll> fact, fact_inv;
	comb_fact(int n):N(n)
	{
		fact = vector<ll>(N+1,1);
		fact_inv = vector<ll>(N+1,1);
		rep(i, n)
		{
			fact[i+1] = (fact[i]*ll(i+1)) % MOD;
			fact_inv[i+1]=(fact_inv[i]*mod_pow(ll(i+1),MOD-2)) % MOD;
		}
	};

	ll comb(ll n, ll m)
	{
		return (((fact[n]*fact_inv[m]) % MOD) * fact_inv[n-m]) % MOD;
	}
};


void solve()
{
	ll n, m, k;
	cin >> n >> m >> k;
	comb_fact cf(n);
	vector<ll> a(n+1);
	a[0] = m;
	rep(i, n)a[i+1] = (a[i]*(m-1)) % MOD;
	ll ans = 0;
	rep(i, k+1)
	{
		ans += (a[n-1-i]*cf.comb(n-1,i)) % MOD;
		ans %= MOD;
	}
	cout << ans << endl;
	return;
}

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


Measured memory_bytes: 7900
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    private static long n;

    public static void main(String[] args) throws Exception {
        try (BufferedInputStream in = new BufferedInputStream(System.in);
             PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out))) {

            Scanner sc = new Scanner(in);

            // 11:24-

            int n = sc.nextInt();
            List<R> rs = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                rs.add(new R(i, sc.next(), sc.nextInt()));
            }

            rs.stream()
                    .sorted()
                    .forEach(p -> out.println(p.id + 1));
        }
    }
    
    private static class R implements Comparable<R> {
        private final int id;
        private final String name;
        private final int score;

        public R(int id, String name, int score) {
            this.id = id;
            this.name = name;
            this.score = score;
        }

        @Override
        public int compareTo(R o) {
            int r1 = this.name.compareTo(o.name);
            if (r1 != 0) {
                return r1;
            }
            return o.score - this.score;
        }
    }
}


Measured memory_bytes: 26700
input_line_1 = raw_input()
input_line_2 = raw_input()
#N = int(input_line_1)
array = []
count_2 = 0
for i in input_line_2.split(" "):
	point = int(i)/400
	if point < 8:
		if point not in array:
			array.append(point)
	else:
		count_2 += 1

max_point = len(array) + count_2
min_pount = max(len(array), 1)

print min_pount, " ", max_point

Measured memory_bytes: 2568
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			String line = sc.nextLine();
			if(line.equals(".")==true) break;
			String[] line2 = line.split("");
			Queue<String> queue = new LinkedList<String>();
			Stack<String> stack = new Stack<String>();
			for(int i=0;i<line2.length;++i){
				if(line2[i].matches("[()\\[\\]]")==true){
					queue.add(line2[i]);
				}
			}
			boolean flag=true;
			int[] flag2=new int[2];
			int flag3=0;
			while(true){
				if(queue.isEmpty() || flag==false) break;
				String cur = queue.remove();
				if(cur.equals("(")){ flag2[0]++; flag3=1; stack.add(cur);}
				if(cur.equals("[")){ flag2[1]++; flag3=2; stack.add(cur);}
				if(cur.equals(")")){
					if(flag3==1&&1<=flag2[0]){
						flag2[0]--;
						 stack.pop();
						if(!stack.isEmpty()&&stack.peek().equals("[")==true) flag3=2;
					}
					else flag=false;
				}
				if(cur.equals("]")){
					if(flag3==2&&1<=flag2[1]){
						flag2[1]--;
						stack.pop();
						if(!stack.isEmpty()&&stack.peek().equals("(")==true) flag3=1;
					}
					else flag=false;
				}
			}
			if((flag2[0]==0&&flag2[1]==0)&&flag==true) System.out.println("yes");
			else System.out.println("no");
		}
	}
}



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

#define LEN 100005

typedef struct P{
    char name[100];
    int time ;
} P;

int tail,head,n;
P Q[LEN];

void enqueue(P x){
    Q[tail] = x;
    tail = (tail + 1) % LEN;
}

P dequeue(){
    P x = Q[head];
    head = (head + 1) % LEN;
    return x;
}

int min(int a, int b){return a < b ? a : b;}

int main(){
    
    int elaps = 0, c;
    int i,q;
    P u;
    scanf("%d %d",&n,&q);
    
    for (i = 1; i <= n; i++) {
        scanf("%s", Q[i].name);
        scanf("%d", &Q[i].time);
    }
    
    head = 1;tail = n + 1;
    while (head != tail) {
        u = dequeue();
        c = min(q,u.time);
        u.time -= c;
        elaps += c;
        if (u.time > 0) {
            enqueue(u);
        }else{
            printf("%s %d\n",u.name,elaps);
        }
    }

   return 0;
}

Measured memory_bytes: 10756
#include <iostream>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

using namespace std;

signed main() {
  IOS;
  int N,H,maxx, i, ans=1;
  cin >> N;
  cin >> H;
  maxx = H;
  for (i = 1; i < N; ++i) {
    cin >> H;
    if (H >= maxx) ans++;
    maxx = max(H, maxx);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int n,k; cin>>n>>k;
	string s; cin>>s,k--;
	s[k]=tolower(s[k]);
	cout<<s<<endl;
	return 0;
}


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

#define rep(a,b) for(int a = 0;a < b;a++)
#define REP(i, x, n) for(int i = x; i < n; i++)
#define P(a) cout << a << endl
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define ssort(v) sort(v.begin(),v.end())
#define rev(v) reverse(v.begin(),v.end())
#define vP(v) for(int i = 0;i < v.size();i++){cout << v[i];if(i != v.size()-1)cout << endl;}
#define vcin(v,n) rep(i,n){int a;cin >> a;v.pb(a);}

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int dx[] = { 1, -1 , 0 , 0 };
int dy[] = { 0,  0,  1, -1 };
ll MOD = 1000000007;

void solve(){
	int a,b;
	cin >> a >> b;
	P((a >= b ? a-b : 0));
}

int main() {
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <list>
#include <string.h>
#define _USE_MATH_DEFINES
#include <math.h>

using namespace std;

struct node{
	int key;
	node *parent, *left, *right;
};

node *root, *NIL;

void insert(int k) {
	node *y = NIL;
	node *x = root;
	node *z;

	z = (node *)malloc(sizeof(node));
	z->key = k;
	z->left = NIL;
	z->right = NIL;

	while( x != NIL) {
		y = x;
		if( z->key < x->key) x = x->left;
		else x = x->right;
	}
	z->parent = y;
	if( y == NIL) {
		root = z;
	} else if( z->key < y->key){
		y->left = z;
	} else {
		y->right = z;
	}
}

node * find(int k) {
	node *x = root;
	node *y = NIL;
	while( x != NIL && k != x->key) {
		if( k < x->key) x = x->left;
		else  x = x->right;
	}
	return x;
}


void Preorder(node *t) {
	if( t == NIL) return;
	printf(" %d", t->key);
	Preorder(t->left);
	Preorder(t->right);
}

void Inorder(node *t) {
	if( t == NIL) return;
	Inorder(t->left);
	printf(" %d", t->key);
	Inorder(t->right);
}

void Postorder(node *t) {
	if( t == NIL) return;
	Postorder(t->left);
	Postorder(t->right);
	printf(" %d", t->key);
}

int main(){
	int x, n;
	string st;
	cin >> n;
	for( int i = 0; i < n; i++) {
		cin >> st;
		if(st[0] == 'i') {
			cin >> x;
			insert(x);
		} else if(st[0] == 'p'){
			Inorder(root);
			cout << endl;
			Preorder(root);
			cout << endl;
		} else {
			cin >> x;
			node *t = find(x);
                        if( t != NIL) cout << "yes" <<endl;
                        else cout << "no" <<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 19968
#include<iostream>
using namespace std;
int a[51][51]={},d[51][51]={},ans=0,w,h,dx[8]={-1,0,1,-1,1,-1,0,1},dy[8]={-1,-1,-1,0,0,1,1,1};
int f(int y,int x){
	if(d[y][x]==1 && a[y][x]==0){
		a[y][x]=1;
		for(int i=0;i<8;i++){
			if(y+dy[i]>-1 && y+dy[i]<h && x+dx[i]>-1 && x+dx[i]<w){
				if(a[y+dy[i]][x+dx[i]]==0)
				f(y+dy[i],x+dx[i]);
			}
		}
		return 1;
	}
	else{
		return 0;
	}
}
int main(){
	while(cin>>w>>h,w){
		ans=0;
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				a[i][j]=0;
				cin>>d[i][j];
			}
		}
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				if(f(i,j))
				ans++;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 1252
#include <bits/stdc++.h>
#define ls  (n<<1)
#define rs  (ls|1)
using namespace std;

const int N=100010;
struct edge{int s,t,n;}e[2*N],E[N];
int n,h[N],f[N],g[N],siz[N],hs[N],dfn[N],dep[N],t1[4*N],t2[4*N],tag[4*N],Xor[4*N];

void dfs(int x,int fa)
{
	f[x]=fa,siz[x]=1;
	for (int i=h[x],y; y=e[i].t,i; i=e[i].n)
		if (y!=fa)
			{
				dfs(y,x),siz[x]+=siz[y];
				if (siz[y]>siz[hs[x]])  hs[x]=y;
			}
}

void dfs2(int x,int gf)
{
	g[x]=gf,dfn[x]=++dfn[0],dep[x]=dep[f[gf]]+1;
	if (hs[x])  dfs2(hs[x],gf);
	for (int i=h[x],y; y=e[i].t,i; i=e[i].n)
		if ((y!=f[x])&&(y!=hs[x]))  dfs2(y,y);
}

void merge(int n)
{
	if (t1[ls]<t1[rs])  t1[n]=t1[ls],t2[n]=min(t2[ls],t1[rs]);
	else  if (t1[ls]>t1[rs])  t1[n]=t1[rs],t2[n]=min(t2[rs],t1[ls]);
	else  t1[n]=t1[ls],t2[n]=min(t2[ls],t2[rs]);
	t1[n]+=tag[n],t2[n]+=tag[n];
}

void modify(int n,int l,int r,int L,int R,int k)
{
	if ((L<=l)&&(r<=R))
		if (k>0)  Xor[n]^=k,t1[n]++,t2[n]++,tag[n]++;
		else  Xor[n]^=-k,t1[n]--,t2[n]--,tag[n]--;
	else
		{
			int mid=(l+r)>>1;
			if (L<=mid)  modify(ls,l,mid,L,R,k);
			if (mid<R)  modify(rs,mid+1,r,L,R,k);
			merge(n);
		}
}

int find(int n,int l,int r)
{
	if (tag[n]==1)  return Xor[n];
	int mid=(l+r)>>1;
	return (t1[ls]==1)||(t2[ls]==1)?find(ls,l,mid):find(rs,mid+1,r);
}

void modify(int x,int y,int k)
{
	while (g[x]!=g[y])
		{
			if (dep[x]<dep[y])  swap(x,y);
			modify(1,1,n,dfn[g[x]],dfn[x],k),x=f[g[x]];
		}
	if (dfn[x]>dfn[y])  swap(x,y);
	if (x!=y)  modify(1,1,n,dfn[x]+1,dfn[y],k);
}

void work()
{
	scanf("%d",&n);
	for (int i=1,u,v,tot=0; i<n; i++)
		{
			scanf("%d %d",&u,&v);
			e[++tot]=(edge){u,v,h[u]},h[u]=tot;
			e[++tot]=(edge){v,u,h[v]},h[v]=tot;
		}
	for (int i=1; i<n; i++)  scanf("%d %d",&E[i].s,&E[i].t);
	dfs(1,0),dfs2(1,1),memset(t2,127,sizeof(t2));
	for (int i=1; i<n; i++)  modify(E[i].s,E[i].t,i);
	for (int i=1,j; i<n; i++)
		if (t2[1]==1)  j=find(1,1,n),modify(E[j].s,E[j].t,-j);
		else  puts("NO"),exit(0);
	puts("YES");
}

int main()
{
	work();
	return 0;
}


Measured memory_bytes: 16384
import math
M,N = list(map(int,input().split()))
def comb(n,r):
    if n >= r:
        return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))
    else:
        return 0
   
 
A = comb(M,2)
B = comb(N,2)
print(A+B)

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

const int d = 20100;

int main(){
	vector<pair<int,int> > v;
	int N;
	cin>>N;
	for(int i=0;i<N;i++){
		int p;
		cin>>p;
		p--;
		v.push_back(make_pair(p,i));
	}
	sort(v.begin(),v.end());
	vector<int> a(N),b(N);
	for(int i=0;i<N;i++){
		a[i] = v[i].second+1;
		b[i] = 0;
		a[i] += d*i;
		b[i] += -d*i + 500000000;
	}
	for(int i=0;i<N;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;
	for(int i=0;i<N;i++){
		cout<<b[i]<<" ";
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 892
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()

  ans=inf
  for i in range(1,int(math.sqrt(n))+1):
    if n%i==0:
      ans=min(ans,i+n//i-2)
  return ans

# main()
print(main())


Measured memory_bytes: 5680
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Dice dice1 = new Dice();
		Dice dice2 = new Dice();

		for (int i = 0; i < 6; i++) {
			dice1.setupDice(sc.nextInt());
		}
		for (int i = 0; i < 6; i++) {
			dice2.setupDice(sc.nextInt());
		}

		dice1.setTopMax();
		dice2.setTopMax();

		boolean isSameDice = false;
		for (int i = 0; i < 10; i++) {
			dice2.spin();
			if (dice1.getFace(2) == dice2.getFace(2)) {
				break;
			}
		}

		if (dice1.getFace(3) == dice2.getFace(3) &&
				dice1.getFace(4) == dice2.getFace(4) &&
				dice1.getFace(5) == dice2.getFace(5) &&
				dice1.getFace(6) == dice2.getFace(6)) {
			isSameDice = true;
		}

		if(isSameDice) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}

	}
}

class Dice {
	List<Integer> faces;
	List<Integer> first;

	public Dice() {
		this.faces = new ArrayList<Integer>();
		faces.add(0);
		this.first = new ArrayList<Integer>();
		first.add(0);
	}

	public void setupDice(int value) {
		faces.add(value);
		first.add(value);
	}

	public void roll(int direction) {
		faces.set(0, faces.get(1));
		switch (faces.indexOf(direction)) {
		case 5:
			faces.set(1, faces.get(5));
			faces.set(5, faces.get(6));
			faces.set(6, faces.get(2));
			faces.set(2, faces.get(0));
			break;
		case 3:
			faces.set(1, faces.get(3));
			faces.set(3, faces.get(6));
			faces.set(6, faces.get(4));
			faces.set(4, faces.get(0));
			break;
		case 2:
			faces.set(1, faces.get(2));
			faces.set(2, faces.get(6));
			faces.set(6, faces.get(5));
			faces.set(5, faces.get(0));
			break;
		case 4:
			faces.set(1, faces.get(4));
			faces.set(4, faces.get(6));
			faces.set(6, faces.get(3));
			faces.set(3, faces.get(0));
			break;
		case 6:
			faces.set(1, faces.get(6));
			faces.set(6, faces.get(0));
			faces.set(0, faces.get(2));
			faces.set(2, faces.get(5));
			faces.set(5, faces.get(0));
			break;
		default:
			break;
		}
	}

	public void spin() {
		faces.set(0, faces.get(2));
		faces.set(2, faces.get(3));
		faces.set(3, faces.get(5));
		faces.set(5, faces.get(4));
		faces.set(4, faces.get(0));
	}

	public void setTopMax() {
		int max = 0;
		for (int i = 0; i <= 6; i++) {
			max = Math.max(max, faces.get(i));
		}
		this.roll(max);
	}

	public void setFront(int value) {
		while (faces.get(2) != value) {
			this.spin();
		}
	}

	public void reset() {
		for (int i = 1; i <= 6; i++) {
			faces.set(i, first.get(i));
		}
	}

	public int getFace(int face) {
		return faces.get(face);
	}

}



Measured memory_bytes: 26444
from sys import stdin
def main():
  from math import sqrt
  readline = stdin.readline
  p = [True] * (10 ** 5 + 1)
  p[0] = False
  p[1] = False
  n = int(sqrt(10 ** 5)) + 1
  for j in range(4, 10 ** 5 + 1, 2):
    p[j] = False
  for i in range(3, n + 1, 2):
    if p[i]:
      for j in range(i + i, 10 ** 5 + 1, i):
        p[j] = False
  c = [0] * (10 ** 5 + 2)
  for i in range(2, 10 ** 5 + 2):
    c[i] = c[i - 1]
    if p[i - 2] and p[(i - 1) // 2]:
      c[i] += 1
  q = int(readline())
  for _ in range(q):
    l, r = map(int, readline().split())
    print(c[r + 2] - c[l + 1])
main()


Measured memory_bytes: 5432
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,fa[N],dep[N];
vector<int> son[N];
bool cmp(int x,int y){return dep[x]>dep[y];}
void dfs(int x){
	dep[x]=son[x].size();
	for (int i=0;i<son[x].size();i++) dfs(son[x][i]);
	sort(son[x].begin(),son[x].end(),cmp);
	for (int i=0;i<son[x].size();i++) dep[x]=max(dep[x],dep[son[x][i]]+i+1);
}
int main()
{
	scanf("%d",&n);
	for (int i=2;i<=n;i++) scanf("%d",&fa[i]),son[fa[i]].push_back(i);
	dfs(1);
	printf("%d\n",dep[1]);
	return 0;
}

Measured memory_bytes: 11136
a,b = map(int,input().split())
if a ==1:
  if b==1:
    print("Draw")
  else:
    print("Alice")
else:
  if b==1:
    print("Bob")
  else:
    if a ==b:
      print("Draw")
    elif a < b:
      print("Bob")
    else:
      print("Alice")


Measured memory_bytes: 2940
#define	_USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cctype>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <string>
#include <set>
#include <complex>
#include <utility>
#include <numeric>
#include <bitset>
using namespace std;
const int INF=1<<30;

int d[11][7];
int x=2,y=1;
int k=0;

typedef pair<int,int> P;


void R(){
	if(d[y-1][x]) {
	k=2; 
	y-=2; 
	cout<<"U";
	}
	else if(d[y][x]) {
	k=0; 
	x++; 
	cout<<"R";
	}
	else if(d[y+1][x]){
		k=3;
		y+=2;
		cout<<"D";
	}
	else{
		k=1;
		x--;
		cout<<"L";
	}

}
void L(){
	if(d[y+1][x]) {
	k=3; 
	y+=2; 
	cout<<"D";
	}
	else if(d[y][x-1]) {
	k=1; 
	x--; 
	cout<<"L";
	}
	else if(d[y-1][x]){
		k=2;
		y-=2;
		cout<<"U";
	}
	else{
		k=0;
		x++;
		cout<<"R";
	}

}
void U(){
	if(d[y][x-1]) {
	k=1; 
	x--; 
	cout<<"L";
	}
	else if(d[y-1][x]) {
	k=2; 
	y-=2; 
	cout<<"U";
	}
	else if(d[y][x]){
		k=0;
		x++;
		cout<<"R";
	}
	else{
		k=3;
		y+=2;
		cout<<"D";
	}

}
void D(){
	if(d[y][x]) {
	k=0; 
	x++; 
	cout<<"R";
	}
	else if(d[y+1][x]) {
	k=3; 
	y+=2; 
	cout<<"D";
	}
	else if(d[y][x-1]){
		k=1;
		x--;
		cout<<"L";
	}
	else{
		k=2;
		y-=2;
		cout<<"U";
	}

}

void tansaku(){
	
	while(!(x==1&&y==1)){
		switch(k){
		case 0: R();break;
		case 1: L();break;
		case 2: U();break;
		case 3: D();break;
		default:return;
		}
		
	}
}

int main(){
	string s;
	for(int i=1;i<10;i++){
		getline(cin,s);
		if(s[s.size()-1]=='\r')
			s.substr(0,s.size()-1);
		for(int j=0;j<s.size();j++){
			if(i%2!=0){
				d[i][j+1]=s[j]-'0';
			}
			else{
				d[i][j+1]=s[j]-'0';
			}
			
		}
	}
	cout<<"R";
	tansaku();
	cout<<endl;
	

}

Measured memory_bytes: 3208
#include<bits/stdc++.h>
using namespace std;
int n,i,j,a[2005],book[2005][2005];
int max1,ans[2005],flag[2005],du[2005];
int vis[2005],top,nex[4000005],to[4000005],fir[2005];
int lj(int u,int v){
	top++;
	nex[top]=fir[u];
	fir[u]=top;
	to[top]=v;
	return 0;
}
int ss(int v){
	vis[v]=1;
	for(int top1=fir[v];top1;top1=nex[top1])
		if(vis[to[top1]]==0){
			book[v][to[top1]]=1;
			du[to[top1]]++;
			ss(to[top1]);
		}
	return 0;
}
int read(){
	int xx=0,flag=1;
	char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')
		ch=getchar();
	if(ch=='-'){
		flag=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		xx=xx*10+ch-'0';
		ch=getchar();
	}
	return flag*xx;
}
int gcd(int u,int v){
	if(v==0) return u;
	return gcd(v,u%v);
}
int main(){
	n=read();
	for(i=1;i<=n;i++)
		a[i]=read();
	sort(a+1,a+n+1);
	for(i=n;i>=1;i--)
		for(j=n;j>=i+1;j--)
			if(gcd(a[i],a[j])!=1){
				lj(i,j);
				lj(j,i);
			}
	for(i=1;i<=n;i++)
		if(vis[i]==0)
			ss(i);
	for(i=1;i<=n;i++){
		max1=0;
		for(j=1;j<=n;j++)
			if(flag[j]==0&&du[j]==0)
				max1=j;
		for(j=1;j<=n;j++)
			if(book[max1][j]==1)
				du[j]--;
		ans[i]=a[max1];
		flag[max1]=1;
	} 
	for(i=1;i<=n;i++)
		printf("%d ",ans[i]);
	cout<<endl;
	return 0;
}

Measured memory_bytes: 38144
#include <bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
int n,ans=0;
int32_t main(){
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin >> n;
	pair <int,int> v[n];
	map <int,int> m;
	for(int i=0;i<n;i++){
		cin >> v[i].f >> v[i].s;
		v[i].f+=v[i].s;
		v[i].s=v[i].f-2*v[i].s;
	}
	sort(v,v+n);
	int i=0,j=1;
	while(i<n){
		if(j>=n)break;
		int p=v[j].s,q=v[i].f;
		if(p<q){
			ans++;j++;
		}
		else{
			i=j;
			j=i+1;
		}
	}
	cout << n-ans;
}


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

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define sz(s) (int)s.size()

const int OO = int(1e8);
int a[2000], b[2000], c[2000];
int d[200][200];

int main() {
    int n, m;
    cin >> n >> m;
    rep(i, 0, n) rep(j, 0, n) d[i][j] = (i == j ? 0 : OO);

    rep(i, 0, m) {
        cin >> a[i] >> b[i] >> c[i];
        --a[i]; --b[i];
        d[a[i]][b[i]] = d[b[i]][a[i]] = c[i];
    }
    rep(k, 0, n) rep(i, 0, n) rep(j, 0, n) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    int ans = 0;
    rep(t, 0, m) {
        bool need = false;
        int u = a[t], v = b[t];
        rep(i, 0, n) rep(j, 0, n)
        if (d[i][j] == d[i][u] + c[t] + d[v][j] || d[i][j] == d[i][v] + c[t] + d[u][j]) need = true;
        ans += (!need);
    }
    cout << ans << '\n';
}

Measured memory_bytes: 384
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.nextLine());
		List<Long> list = Arrays.stream(sc.nextLine().split(" ",0)).map(Long::valueOf).collect(Collectors.toList());
		int count = 0;
		boolean hasZero = false;
		for (long i : list) {
			if (i == 0) {
				hasZero = true;
				break;
			} else if (i < 0) {
				count++;
			}
		}

		long out = list.stream().mapToLong(Math::abs).sum();
		if (! (hasZero || count%2 == 0) ) {
			long min = list.stream().mapToLong(Math::abs).min().getAsLong();
			out-= min*2;
		}

		System.out.println(out);
		sc.close();
	}

}

Measured memory_bytes: 56676
const input=require('fs').readFileSync('/dev/stdin', 'utf8').split(/[\s]/);const nin=()=>{const r = input[0];input.shift();return Number(r)};const nrin=(n)=>{const a:number[]=[];rep(n,()=>a.push(nin()));return a};const sin=()=>{const r = input[0];input.shift();return String(r)};const out=(...a)=>{console.log(...a)};const floor=(a)=>{return Math.floor(a)};const abs=(a)=>{return Math.abs(a)};const min=(...a)=>{return Math.min(...a)};const max=(...a)=>{return Math.max(...a)};const rep=(n, callback)=>{for(let i = 0;i < n; i++){callback()}};const strrep=(s, i, v)=>{return s.slice(0, i)+v+s.slice(i+1);};const permutation=({result=[],pre=[],post,n=post.length})=>{if(n>0){post.forEach((_,i)=>{const rest=[...post];const elem=rest.splice(i, 1);permutation({result, pre: [...pre,...elem],post:rest,n:n-1})})}else{result.push(pre)}return result};const sw=(s,a:any[],op:'=='|'>='|'>'|'<='|'<'='==')=>{for(let i=0;i<a.length;i+=2){if(op==='=='){if(s==a[i])return a[i+1]}else if(op==='>='){if(s>=a[i])return a[i+1]}else if(op==='<='){if(s<=a[i])return a[i+1]}else if(op==='>'){if(s>a[i])return a[i+1]}else if(op==='<'){if(s<a[i])return a[i+1]}}return a[a.length-1];};const or=(a,...b)=>{for(let i=0;i<b.length;i++)if(a==b[i])return true;return false};const maxindex=(...a)=>{return a.indexOf(Math.max.apply(null,a))};const asc=(ar:number[])=>{return ar.sort((a,b)=>{return a-b})};const desc=(ar:number[])=>{return ar.sort((a,b)=>{return b-a})};const ceil=a=>{return Math.ceil(a)};const srin=s=>{const a:string[]=[];rep(s,()=>a.push(sin()));return a};let ssinteger=-1;const ssin=()=>{ssinteger++;return input[0][ssinteger]};
const main = ()=>{
  let [a,b]=srin(2)
  let c=0;
  for(let i=0;i<3;i++) if(a[i] == b[i])c++; 
  out(c)
}
main()

Measured memory_bytes: 7372
def resolve():
    N = int(input())
    A = [0] * (10 ** 5 + 1)
    ans = 0
    for a in input().split():
        a = int(a)
        A[a] += 1
        ans += a

    Q = int(input())
    for _ in range(Q):
        a, b = map(int, input().split())
        l_a = A[a]
        ans -= l_a * a
        A[b] += l_a
        A[a] -= l_a
        ans += l_a * b
        print(ans)

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 18156
#include <vector>
#include <bitset>
#include <iostream>
#include <algorithm>
#define coor(i,j) ((i)+(j)*m)
#define in(i,j) (0<=(i)&&(i)<m&&0<=(j)&&(j)<n)
using namespace std;
vector<bitset<626> > M(625);
main(){
	int m,n,d;
	int i,j,k;
	int success,ans;
	for(;cin>>m>>n>>d,d;cout<<ans<<endl){
		for(j=0;j<n;j++)
			for(i=0;i<m;i++){
				M[coor(i,j)].reset();
				M[coor(i,j)][coor(i,j)]=1;
				cin>>k;M[coor(i,j)][m*n]=k;
				for(k=0;k<=d;k++){
					if(in(i-k,j-(d-k)))M[coor(i,j)][coor(i-k,j-(d-k))]=1;
					if(in(i+k,j-(d-k)))M[coor(i,j)][coor(i+k,j-(d-k))]=1;
					if(in(i-k,j+(d-k)))M[coor(i,j)][coor(i-k,j+(d-k))]=1;
					if(in(i+k,j+(d-k)))M[coor(i,j)][coor(i+k,j+(d-k))]=1;
				}
			}
		k=0;
		for(i=0;i<m*n;i++){
			for(j=k;j<m*n&&!M[j][i];j++);
			if(j==m*n)continue;
			swap(M[k],M[j]);
			for(j=k+1;j<m*n;j++)if(M[j][i])M[j]^=M[k];
			k++;
		}
		ans=1;
		for(j=0;j<m*n;j++)if(M[j][m*n]&&M[j].count()==1)ans=0;
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100003,INF=1<<30;

int main(){
    
    ll N;cin>>N;
    ll ans=N-1;
    
    for(ll i=1;i*i<=N;i++){
        if(N%i==0){
            ans=min(ans,(i-1)+(N/i-1));
        }
    }
    
    cout<<ans<<endl;
}



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

double DP[301][301][301];
int N;

double solve(int c1,int c2,int c3){
	if(c1==0&&c2==0&&c3==0) return 0.0;
	if(DP[c1][c2][c3]) return DP[c1][c2][c3];
	double ret=0.0;
	
	if(c1) ret+=1.0*solve(c1-1,c2,c3)*c1/(c1+c2+c3);
	if(c2) ret+=1.0*solve(c1+1,c2-1,c3)*c2/(c1+c2+c3);
	if(c3) ret+=1.0*solve(c1,c2+1,c3-1)*c3/(c1+c2+c3);
	ret+=1.0*N/(c1+c2+c3);
		
	return DP[c1][c2][c3]=ret;
}

int main(){
	int count1,count2,count3;
	count1=count2=count3=0;
	cin>>N;
	
	for(int i=0;i<N;i++){
		int input;
		cin>>input;
		if(input==1){
			count1++;
		}else if(input==2){
			count2++;
		}else if(input==3){
			count3++;
		}
	}
	
	printf("%.10lf\n",solve(count1,count2,count3));
	
	return 0;
}

Measured memory_bytes: 213248
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <deque>
#include <numeric>
#include <utility>
using namespace std;

void solve(long long N, std::vector<long long> s){
    vector<long long> dp1(10, -1);
    vector<long long> dp2(10, -1);
    dp1[0]=0;
    for(int i=0; i<N; i++){
        for(int j=0; j<10; j++)dp2[j]=dp1[j];
        for(int j=0; j<10; j++){
            if(dp1[j]<0)continue;
            auto dist = (s[i]%10+j)%10;
            dp2[dist] = max(dp2[dist], dp1[j]+s[i]);
        }
        swap(dp1, dp2);
    }
    cout << max(0ll, *max_element(dp1.begin()+1, dp1.end())) << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> s(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&s[i]);
    }
    solve(N, std::move(s));
    return 0;
}


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

int main(){
    int a,b,c,d,e;
    cin >> a >> b >> c >> d >> e;
    int ans=0;
    int S[5];

    S[0]=((a+9)/10)*10-a;
    S[1]=((b+9)/10)*10-b;
    S[2]=((c+9)/10)*10-c;
    S[3]=((d+9)/10)*10-d;
    S[4]=((e+9)/10)*10-e;

    int res=-1e9;
    for(int i=0;i<5;i++){
        ans+=S[i];
        res=max(res,S[i]);
    }

    ans-=res;
    ans+=a+b+c+d+e;
    cout << ans << endl;
    
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int H = int.Parse(input[0]);
            int W = int.Parse(input[1]);
            string[] pic = new string[H];

            for(int i = 0; i < H; i++)
            {
                pic[i] = "#" + Console.ReadLine() + "#";
            }

            string header_fotter = new string('#',W+2);

            Console.WriteLine(header_fotter);

            for(int i = 0; i < H; i++)
            {
                Console.WriteLine(pic[i]);
            }

            Console.WriteLine(header_fotter);
        }
    }
}


Measured memory_bytes: 11092
#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int a,b,c;
    cin>>a>>b>>c;
    int ans[3];
    ans[0]=abs(a-b);
    ans[1]=abs(a-c);
    ans[2]=abs(b-c);
    int num=1000000;
    if (ans[0]+ans[1]<num)
        num=ans[0]+ans[1];
    if (ans[2]+ans[1]<num)
        num=ans[2]+ans[1];
    if (ans[0]+ans[2]<num)
        num=ans[0]+ans[2];
    cout<<num<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#define Rep(i,a,n)for(int i=(int)(a);i<(int)(n);i++)
#define rep(i,n)Rep(i,0,n)
typedef long long lld;
#define Ma(x,y)(x>y?x:y)

int main(){
	int n,W,v[2<<6],w[2<<16];
	scanf("%d%d", &n, &W);
	rep(i,n)scanf("%d%d",&w[i],&v[i]);
	lld dp[2<<6][2<<16];//dp[a+1][b]...v[a]w[a]までの品物の中から重さがbを超えぬように選んだ時の価値の総和の最大値
	rep(i,W+1)dp[0][i] = 0;//1つも選んでいない
	rep(i,n){//(0~N-1で)i番目まで
		rep(j,W+1){//(0~Wで)j gまで
		//(0から数えて)i番目のを入れるかどうか
			if(j<w[i])dp[i+1][j]=dp[i][j];//w[i]がjより大きくて選べない
			else dp[i+1][j]=Ma(dp[i][j],dp[i][j-w[i]]+v[i]);
		}
	}
	printf("%lld",dp[n][W]);
	return 0;
}

Measured memory_bytes: 105344