stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <string>

#include <iostream>



using namespace std;



int main()

{

	string S, T;



	cin >> S >> T;



	if (S.size() >= T.size())

	{

		for (int i = 0; i <= S.size() - T.size(); i++)

		{

			if (T[0] == S[i])

			{

				if (T == S.substr(i, T.size()))

				{

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

				}

			}

		}

	}



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.294865724448858x):
#include <cstdio>

#include <cstring>

#pragma warning(disable : 4996)

char s[1000009], t[10009];

int main() {

	scanf("%s%s", s, t);

	unsigned long long hs = 0, ht = 0, pw = 1;

	int sl = strlen(s), tl = strlen(t);

	for (int i = 0; i < tl; i++) {

		hs = hs * 257 + s[i];

		ht = ht * 257 + t[i];

		pw *= 257;

	}

	for (int i = tl; i <= sl; i++) {

		if (hs == ht) printf("%d\n", i - tl);

		hs = hs * 257 + s[i] - s[i - tl] * pw;

	}

	return 0;

}
// Slower C++ solution:
#include <string>

#include <iostream>



using namespace std;



int main()

{

	string S, T;



	cin >> S >> T;



	if (S.size() >= T.size())

	{

		for (int i = 0; i <= S.size() - T.size(); i++)

		{

			if (T[0] == S[i])

			{

				if (T == S.substr(i, T.size()))

				{

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

				}

			}

		}

	}



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.33605429309565x):
#include <cstdio>

#include <cstring>

char s[1000009], t[10009];

int main() {

	int sl = 0, tl = 0;

	while ((s[sl++] = getchar_unlocked()) != '\n'); sl--;

	while ((t[tl++] = getchar_unlocked()) != '\n'); tl--;

	unsigned long long hs = 0, ht = 0, pw = 1;

	for (int i = 0; i < tl; i++) {

		hs = (hs << 8) + hs + s[i];

		ht = (ht << 8) + ht + t[i];

		pw = (pw << 8) + pw;

	}

	for (int i = tl; i <= sl; i++) {

		if (hs == ht) printf("%d\n", i - tl);

		hs = (hs << 8) + hs + s[i] - s[i - tl] * pw;

	}

	return 0;

}
// Slower C++ solution:
#include <string>

#include <iostream>



using namespace std;



int main()

{

	string S, T;



	cin >> S >> T;



	if (S.size() >= T.size())

	{

		for (int i = 0; i <= S.size() - T.size(); i++)

		{

			if (T[0] == S[i])

			{

				if (T == S.substr(i, T.size()))

				{

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

				}

			}

		}

	}



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.4416142998893715x):
#include <cstdio>

#include <cstring>

inline void writeln(int x) {

	int s = 0, p; char f[7];

	while (x) {

		p = x; x /= 10;

		f[s++] = p - (x << 1) - (x << 3);

	}

	if (!s) f[s++] = 0;

	while (s--) putchar_unlocked(f[s] + '0');

	putchar_unlocked('\n');

}

char s[1000009], t[10009];

int main() {

	int sl = 0, tl = 0;

	while ((s[sl++] = getchar_unlocked()) != '\n'); sl--;

	while ((t[tl++] = getchar_unlocked()) != '\n'); tl--;

	unsigned long long hs = 0, ht = 0, pw = 1;

	for (int i = 0; i < tl; i++) {

		hs = (hs << 8) + hs + s[i];

		ht = (ht << 8) + ht + t[i];

		pw = (pw << 8) + pw;

	}

	for (int i = tl; i <= sl; i++) {

		if (hs == ht) writeln(i - tl);

		hs = (hs << 8) + hs + s[i] - s[i - tl] * pw;

	}

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

using namespace std;



typedef pair<int, int> P;



int main() {

int n,r;

long long m=0,c=1,q=1e9+7;

P p[200000];

cin>>n;

for(int i=0;i<n*2;i++){

    cin>>p[i].first;

    p[i].second=i/n;

}

sort(p,p+n*2);

for(int i=0;i<n*2;i++){

    if(m==0){

        m++;

        r=p[i].second;

    }else if(p[i].second==r){

        m++;

    }else{

        c=(c*m)%q;

        m--;

    }

}

cout<<c<<endl;





	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.6003308707392807x):
#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

typedef pair<int, int> P;

int main(void){

    int n;

    cin >> n;

    vector<P> v;

    for(int i=0;i<n*2;i++){

        int a;

        cin >> a;

        v.push_back(P(a, i));

    }

    sort(v.begin(), v.end());

    int lft = 0;

    long long ans = 1, mod = 1e9+7;

    for(int i=0;i<n*2;i++){

        int s = v[i].second;

        if(s < n){

            if(lft <= 0) lft--;

            else ans *= lft--;

        }else{

            if(lft >= 0) lft++;

            else ans *= -lft++;

        }

        ans %= mod;

    }

    cout << ans << endl;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;



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

#define FOR(i, m, n) for(int i = (int)(m); i < (int)(n); ++i)



const int MOD = 1e+9 + 7;



int main()

{

    int N;

    cin >> N;

    vector<int> a(N), b(N);    

    REP(i, N) cin >> a[i];

    REP(i, N) cin >> b[i];



    vector<long long> factorial(100001, 1);

    FOR(i, 1, 100001){

        factorial[i] *= i*factorial[i-1];

        factorial[i] %= MOD;

    }



    sort(a.begin(), a.end());

    sort(b.begin(), b.end());



    long long ans = 1;

    REP(i, N){

        int pos = lower_bound(a.begin(), a.end(), b[i]) - a.begin(), n;

        if(a[i] < b[i]) n = pos-i;

        else n = i-pos+1;

        ans *= n;

        ans %= MOD;

        // i += n-1;

        // cout << i << " " << ans << endl;

    } 

    cout << ans << endl;



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.4611324699961616x):
#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;



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

#define FOR(i, m, n) for(int i = (int)(m); i < (int)(n); ++i)



const int MOD = 1e+9 + 7;



int main()

{

    int N;

    cin >> N;

    vector<int> a(N), b(N);    

    REP(i, N) cin >> a[i];

    REP(i, N) cin >> b[i];



    sort(a.begin(), a.end());

    sort(b.begin(), b.end());



    long long ans = 1;  // 最初は a[i] - b[i] で繋がっている 

    REP(i, N){

        int pos = lower_bound(a.begin(), a.end(), b[i]) - a.begin(), n;

        if(a[i] < b[i]) n = pos-i;

        else n = i-pos+1;

        ans *= n;  // a[i] が繋げる可能性があるものは n 通り

        ans %= MOD;

        // cout << i << " " << ans << endl;

    } 

    cout << ans << endl;



    return 0;

}
// Slower C++ solution:
//============================================================================

// Name        : AOJ.cpp

// Author      :

// Version     :

// Copyright   : Your copyright notice

// Description : Hello World in C++, Ansi-style

//============================================================================



#include <iostream>

using namespace std;

int P[100001];

long long A[100001],B[100001],C[100001];

int D[100001];



int main() {

	int N,M;

	long long R=0;

	cin>>N>>M;

	for(int i=1;i<M+1;i++)cin>>P[i];



	for(int i=1;i<N;i++)cin>>A[i]>>B[i]>>C[i];



	for(int i=1;i<M;i++){

		if(P[i]<P[i+1]){

			for(int j=P[i];j<P[i+1];j++)D[j]+=1;

		}else{

			for(int j=P[i+1];j<P[i];j++)D[j]+=1;

		}

	}



	for(int j=1;j<N;j++)R+=min(D[j]*B[j]+C[j],D[j]*A[j]);

	cout<<R<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.218973093159185x):
#include<cstdio>

#include<algorithm>



using namespace std;



const int MAX_N = 100000;

const int MAX_M = 100000;

int cnt[MAX_N+1];

int A[MAX_N],B[MAX_N],C[MAX_N];



int P[MAX_M];



int N,M;



int main(){

	scanf("%d%d",&N,&M);

	for(int i=0;i<M;i++){

		scanf("%d",P+i);

	}

	for(int i=0;i<N-1;i++){

		scanf("%d%d%d",A+i,B+i,C+i);

	}

	for(int i=0;i<M-1;i++){

		int x=P[i],y=P[i+1];

		if(x>y) swap(x,y);

		x--;

		y--;

		cnt[x]++;

		cnt[y]--;

	}

	for(int i=1;i<N;i++){

		cnt[i]+=cnt[i-1];

	}

	long long ans=0;

	for(int i=0;i<N-1;i++){

		long long paper=(long long)A[i]*cnt[i];

		long long ic=(long long)B[i]*cnt[i]+C[i];

		ans+=min(paper,ic);

	}

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

	return 0;

}
// Slower C++ solution:
#include <iostream>

using namespace std;

int P[100001];

long long A[100001], B[100001], C[100001];

int D[100001];



int main() {

	int N,M;

	long long R=0;



	cin>>N>>M;

	for(int i=1; i<M+1; i++)cin>>P[i];

	for(int i=1; i<N; i++)cin>>A[i]>>B[i]>>C[i];



	for(int i=1; i<M; i++){

		if(P[i]<P[i+1]){

			for(int j=P[i]; j<P[i+1]; j++)D[ j ] += 1;

		}else{

			for(int j=P[i+1]; j<P[i]; j++)D[ j ] += 1;

		}

	}



	for(int j=1; j<N; j++) R += min(D[ j ]*B[ j ]+C[ j ],  D[ j ]*A[ j ]);

	cout<<R<<endl;

	return 0;

}




// Faster C++ solution for the same problem (measured speedup: 5.218973093159185x):
#include<cstdio>

#include<algorithm>



using namespace std;



const int MAX_N = 100000;

const int MAX_M = 100000;

int cnt[MAX_N+1];

int A[MAX_N],B[MAX_N],C[MAX_N];



int P[MAX_M];



int N,M;



int main(){

	scanf("%d%d",&N,&M);

	for(int i=0;i<M;i++){

		scanf("%d",P+i);

	}

	for(int i=0;i<N-1;i++){

		scanf("%d%d%d",A+i,B+i,C+i);

	}

	for(int i=0;i<M-1;i++){

		int x=P[i],y=P[i+1];

		if(x>y) swap(x,y);

		x--;

		y--;

		cnt[x]++;

		cnt[y]--;

	}

	for(int i=1;i<N;i++){

		cnt[i]+=cnt[i-1];

	}

	long long ans=0;

	for(int i=0;i<N-1;i++){

		long long paper=(long long)A[i]*cnt[i];

		long long ic=(long long)B[i]*cnt[i]+C[i];

		ans+=min(paper,ic);

	}

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

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define INF 1000000000



int main(void){

    

    int n, m; cin >> n >> m;

    int p[100010];

    for(int i = 0; i < m; i++){

        cin >> p[i];

    }

    long long array[100010] = {};

    for(int i = 0; i < m-1; i++){

        if(p[i] < p[i+1]){

            for(int j = p[i]; j < p[i+1]; j++){

                array[j]++;

            }

        }else{

            for(int j = p[i+1]; j < p[i]; j++){

                array[j]++;

            }

        }

    }



    

    long long ans = 0;



    for(int i = 1; i < n; i++){

        long long a, b, c; cin >> a >> b >> c;

        ans += min(a*array[i], c + b*array[i]);

    }

    cout << ans << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2891784509520363x):
#include<bits/stdc++.h>

using namespace std;

#define INF 1000000000





int main(void){

    

    int n, m; cin >> n >> m;

    int p[100010];

    for(int i = 0; i < m; i++){

        cin >> p[i];

    }



    int array[100010] = {};

    //テヲツ?堙ァツ崢エ

    /*for(int i = 0; i < m-1; i++){

        if(p[i] < p[i+1]){

            for(int j = p[i]; j < p[i+1]; j++){

                array[j]++;

            }

        }else{

            for(int j = p[i+1]; j < p[i]; j++){

                array[j]++;

            }

        }

    }*/



    //テ」ツつ、テ」ツδ「テ」ツつケテヲツウツ?

    for(int i = 0; i < m-1; i++){

        if(p[i] < p[i + 1]){

            array[p[i]]++;

            array[p[i + 1]]--;

        }else{

            array[p[i + 1]]++;

            array[p[i]]--;

        }

    }



    for(int i = 1; i < n; i++){

        array[i+1] += array[i];

    }

    

    

    long long ans = 0;



    for(int i = 1; i < n; i++){

        long long a, b, c; cin >> a >> b >> c;

        ans += min(a*array[i], c + b*array[i]);

    }

    cout << ans << endl;

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define INF 1000000000



int main(void){

    

    int n, m; cin >> n >> m;

    int p[100010];

    for(int i = 0; i < m; i++){

        cin >> p[i];

    }

    long long array[100010] = {};

    for(int i = 0; i < m-1; i++){

        if(p[i] < p[i+1]){

            for(int j = p[i]; j < p[i+1]; j++){

                array[j]++;

            }

        }else{

            for(int j = p[i+1]; j < p[i]; j++){

                array[j]++;

            }

        }

    }



    

    long long ans = 0;



    for(int i = 1; i < n; i++){

        long long a, b, c; cin >> a >> b >> c;

        ans += min(a*array[i], c + b*array[i]);

    }

    cout << ans << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.7980573878982944x):
#include<bits/stdc++.h>

using namespace std;

#define int long long

const int MOD = 1000000007LL;

const int INF = LLONG_MAX;



signed main(){

    

    int n, m; cin >> n >> m;

    vector<int> p(n);

    for(int i = 0; i < m; i++){

        cin >> p[i];

        p[i]--;

    }

    vector<int> a(n - 1);

    vector<int> b(n - 1);

    vector<int> c(n - 1);

    for(int i = 0; i < n - 1; i++) cin >> a[i] >> b[i] >> c[i];

    

    vector<int> imos(n, 0);

    for(int i = 1; i < m; i++){

        int r = max(p[i], p[i - 1]);

        int l = min(p[i], p[i - 1]);

        imos[l]++;

        imos[r]--;

    }



    for(int i = 0; i < n - 1; i++) imos[i + 1] += imos[i];

    int ans = 0;

    for(int i = 0; i < n - 1; i++){

        ans += min(imos[i] * a[i], imos[i] * b[i] + c[i]);

    }



    cout << ans << endl;

    

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define INF 1000000000





int main(void){

    

    int n, m; cin >> n >> m;

    int p[100010];

    for(int i = 0; i < m; i++){

        cin >> p[i];

    }



    int array[100010] = {};

    //テヲツ?堙ァツ崢エ

    /*for(int i = 0; i < m-1; i++){

        if(p[i] < p[i+1]){

            for(int j = p[i]; j < p[i+1]; j++){

                array[j]++;

            }

        }else{

            for(int j = p[i+1]; j < p[i]; j++){

                array[j]++;

            }

        }

    }*/



    //テ」ツつ、テ」ツδ「テ」ツつケテヲツウツ?

    for(int i = 0; i < m-1; i++){

        if(p[i] < p[i + 1]){

            array[p[i]]++;

            array[p[i + 1]]--;

        }else{

            array[p[i + 1]]++;

            array[p[i]]--;

        }

    }



    for(int i = 1; i < n; i++){

        array[i+1] += array[i];

    }

    

    

    long long ans = 0;



    for(int i = 1; i < n; i++){

        long long a, b, c; cin >> a >> b >> c;

        ans += min(a*array[i], c + b*array[i]);

    }

    cout << ans << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.3947311844767958x):
#include<bits/stdc++.h>

using namespace std;

#define int long long

const int MOD = 1000000007LL;

const int INF = LLONG_MAX;



signed main(){

    

    int n, m; cin >> n >> m;

    vector<int> p(n);

    for(int i = 0; i < m; i++){

        cin >> p[i];

        p[i]--;

    }

    vector<int> a(n - 1);

    vector<int> b(n - 1);

    vector<int> c(n - 1);

    for(int i = 0; i < n - 1; i++) cin >> a[i] >> b[i] >> c[i];

    

    vector<int> imos(n, 0);

    for(int i = 1; i < m; i++){

        int r = max(p[i], p[i - 1]);

        int l = min(p[i], p[i - 1]);

        imos[l]++;

        imos[r]--;

    }



    for(int i = 0; i < n - 1; i++) imos[i + 1] += imos[i];

    int ans = 0;

    for(int i = 0; i < n - 1; i++){

        ans += min(imos[i] * a[i], imos[i] * b[i] + c[i]);

    }



    cout << ans << endl;

    

    return 0;

}
// Slower C++ solution:
#include <vector>

#include <iostream>

#include <algorithm>



using namespace std;



int main()

{

    int N, M;

    

    scanf("%d", &N);

    scanf("%d", &M);

    

    vector<long long> P(M);

    

    vector<long long> Q(N - 1);

    vector<long long> A(N - 1);

    vector<long long> B(N - 1);

    vector<long long> C(N - 1);

    

    for(int i = 0; i < M; i++)

    {

        scanf("%lld", &P[i]); P[i]--;

    }

    

    for(int i = 0; i < M - 1; i++)

    {

        for(int j = min(P[i], P[i + 1]); j < max(P[i], P[i + 1]); j++)

        {

            Q[j]++;

        }

    }

    

    for(int i = 0; i < N - 1; i++)

    {

        scanf("%lld", &A[i]);

        scanf("%lld", &B[i]);

        scanf("%lld", &C[i]);

    }

    

    long long ret = 0;

    

    for(int i = 0; i < N - 1; i++)

    {

        long long s = A[i] * Q[i];

        long long t = B[i] * Q[i] + C[i];

        

        ret += min(s, t);

    }

    

    printf("%lld\n", ret);

    

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.192765463364042x):
#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

int N, M, A[100009], B[100009], C[100009], P[100009], sum[100009];

int main() {

	scanf("%d%d", &N, &M);

	for (int i = 0; i < M; i++) scanf("%d", &P[i]), P[i]--;

	for (int i = 0; i < N - 1; i++) scanf("%d%d%d", &A[i], &B[i], &C[i]);

	for (int i = 1; i < M; i++) {

		int pl = P[i - 1], pr = P[i];

		if (pl > pr) swap(pl, pr);

		sum[pl]++; sum[pr]--;

	}

	for (int i = 1; i < N; i++) sum[i] += sum[i - 1];

	long long ret = 0;

	for (int i = 0; i < N - 1; i++) ret += min(1LL * A[i] * sum[i], 1LL * B[i] * sum[i] + C[i]);

	printf("%lld\n", ret);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



int main(){

    int N;

    int64_t X, x[200001];

    cin >> N >> X;

    for(int i=1; i<=N; i++) cin >> x[i];

    int64_t accum[200001] = {0};

    for(int i=1; i<=N; i++) accum[i] = x[i] + accum[i-1];



    int64_t ans = 2e15;

    for(int k=1; k<=N; k++){

        int64_t result = (N+k) * X;

        for(int j=0; j<(N-1)/k+1; j++){

            int M = N - j*k;

            int m = max(0, M-k);

            int c = j==0 ? 5 : 2*j+3;

            result += c * (accum[M] - accum[m]);

            if(result >= ans) break;

        }

        ans = min(ans, result);

    }

    cout << ans << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.637917347180867x):
#include <bits/stdc++.h>

using namespace std;



int main(){

    int64_t N, X;

    cin >> N >> X;

    vector<int64_t> x(N+1), S(N+1);

    for(int i=1; i<=N; i++){

        cin >> x[i];

        S[i] = S[i-1] + x[i];

    }



    int64_t ans = 1e18;

    for(int d=1; d<=N; d++){

        int64_t res = (N+d)*X;

        int pt = N;

        for(int64_t i=0; pt>0; i++){

            int nxt = max(0, pt-d);

            res += (S[pt]-S[nxt]) * (i==0 ? 5 : 2*i+3);

            if(res >= ans) break;

            pt = nxt;

        }

        ans = min(ans, res);

    }

    cout << ans << endl;

}
// Slower C++ solution:
#include <cstdio>

#include <cmath>

#include <vector>

using namespace std;



typedef vector<double> point;

typedef const point &rpoint;



point add(rpoint p1, rpoint p2){

	point p(3);

	for(int i = 0; i < 3; ++i)

		p[i] = p1[i] + p2[i];

	return p;

}



point sub(rpoint p1, rpoint p2){

	point p(3);

	for(int i = 0; i < 3; ++i)

		p[i] = p1[i] - p2[i];

	return p;

}



point mul(double t, rpoint p2){

	point p(3);

	for(int i = 0; i < 3; ++i)

		p[i] = t * p2[i];

	return p;

}



double abs(rpoint p){

	double s = 0.0;

	for(int i = 0; i < 3; ++i)

		s += p[i] * p[i];

	return sqrt(s);

}



int main(){

	int n;

	point p(3);



	while( scanf("%d", &n), n != 0 ){

		vector<point> v;

		v.reserve(n);



		for(int i = 0; i < n; ++i){

			for(int j = 0; j < 3; ++j){

				scanf("%lf", &p[j]);

			}

			v.push_back(p);

		}

		

		double mv = 0.5;

		double minr;

		while( mv > 1e-8 ){

			for(int k = 0; k < 100; ++k){

				minr = -1.0;

				int mini = -1;

				

				for(int i = 0; i < n; ++i){

					double r = abs(sub(v[i], p));

					if( minr < r ){

						minr = r;

						mini = i;

					}

				}

				

				p = add(p, mul(mv, sub(v[mini], p) ) );

			}

			

			mv *= 0.5;

		}

		

		printf("%.10f\n", minr);

	}

}

// Faster C++ solution for the same problem (measured speedup: 1.3757657857047507x):
#include <cstdio>

#include <cmath>

#include <vector>

using namespace std;



typedef vector<double> point;

typedef const point &rpoint;



point add(rpoint p1, rpoint p2){

	point p(3);

	for(int i = 0; i < 3; ++i)

		p[i] = p1[i] + p2[i];

	return p;

}



point sub(rpoint p1, rpoint p2){

	point p(3);

	for(int i = 0; i < 3; ++i)

		p[i] = p1[i] - p2[i];

	return p;

}



point mul(double t, rpoint p2){

	point p(3);

	for(int i = 0; i < 3; ++i)

		p[i] = t * p2[i];

	return p;

}



double abs(rpoint p){

	double s = 0.0;

	for(int i = 0; i < 3; ++i)

		s += p[i] * p[i];

	return sqrt(s);

}



int main(){

	int n;

	point p(3);



	while( scanf("%d", &n), n != 0 ){

		vector<point> v;

		v.reserve(n);



		for(int i = 0; i < n; ++i){

			for(int j = 0; j < 3; ++j){

				scanf("%lf", &p[j]);

			}

			v.push_back(p);

		}

		

		double mv = 0.5;

		double minr;

		while( mv > 1e-8 ){

			for(int k = 0; k < 50; ++k){

				minr = -1.0;

				int mini = -1;

				

				for(int i = 0; i < n; ++i){

					double r = abs(sub(v[i], p));

					if( minr < r ){

						minr = r;

						mini = i;

					}

				}

				

				p = add(p, mul(mv, sub(v[mini], p) ) );

			}

			

			mv *= 0.5;

		}

		

		printf("%.10f\n", minr);

	}

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



long long f(long long a[],long long x)

{

    if(x==a[x]);

    else a[x]=f(a,a[x]);

    return a[x];

}

long long a[200010];

long long b[200010];

long long c[200010];

long long d[200010];

int e[200010];

int main()

{



    long long n,m,k;

    long long x,y,i;

    scanf("%lld%lld%lld",&n,&m,&k);

    for(i=1; i<=n; i++)

    {

        a[i]=i;

        b[i]=i;

    }

    while(m--)

    {

        scanf("%lld%lld",&x,&y);

        x=f(a,x);

        y=f(a,y);

        a[x]=y;

    }

    while(k--)

    {

        scanf("%lld%lld",&x,&y);

        x=f(b,x);

        y=f(b,y);

        b[x]=y;

    }

    for(i=1; i<=n; i++)

    {

        c[i]=f(a,i)+(n+1)*f(b,i);

        d[i]=c[i];

    }

    sort(d+1,d+n+1);

    memset(e,0,sizeof(e));

    for(i=1; i<=n; i++)

    {

        y=lower_bound(d+1,d+n+1,c[i])-d;

        e[y]++;

    }

    for(i=1; i<=n; i++)

    {

        y=lower_bound(d+1,d+n+1,c[i])-d;

        if(i==n)printf("%d\n",e[y]);

        else printf("%d ",e[y]);

    }

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.7953527800313345x):
#include<bits/stdc++.h>



using namespace std;

const int N = 212345;



int f1[N],f2[N];



map<pair<int,int>,int>mp;



int Find1(int x) {

    if (x != f1[x]) f1[x] = Find1(f1[x]);

    return f1[x];

}



int Find2(int x) {

    if (x != f2[x]) f2[x] = Find2(f2[x]);

    return f2[x];

}



void Join2(int x,int y) {

    int fx = Find2(x);

    int fy = Find2(y);

    if (fx != fy) {

        f2[fx] = fy;

    }

}



void Join1(int x,int y) {

    int fx = Find1(x);

    int fy = Find1(y);

    if (fx != fy) {

        f1[fx] = fy;

    }

}



int main() {

    int n, k, l;

    scanf("%d%d%d", &n, &k, &l);

    for (int i = 0; i <= n; i++) {

        f1[i] = i;

        f2[i] = i;

    }

    for (int i = 0; i <= k - 1; i++) {

        int x, y;

        scanf("%d%d", &x, &y);

        Join1(x, y);

    }

    for (int i = 0; i <= l - 1; i++) {

        int x, y;

        scanf("%d%d", &x, &y);

        Join2(x, y);

    }

    for (int i = 1; i <= n; i++) {

        mp[make_pair(Find1(i), Find2(i))]++;

    }

    for (int i = 1; i <= n; i++) {

        if (i == 1)printf("%d", mp[make_pair(Find1(i), Find2(i))]);

        else printf(" %d", mp[make_pair(Find1(i), Find2(i))]);

    }

    return 0;

}