akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define DEBUG_ARR(v,n) cout<<#v<<":";REP(i,n)cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

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

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int N,W;
    cin>>N>>W;
    vi w(N), v(N);
    REP(i,N) cin>>w[i]>>v[i];

    vl dp(W+5, -1);
    dp[0] = 0;
    REP(i,N){
        FORR(j,0,W){
            if(dp[j] >= 0 && j + w[i] <= W)
                chmax(dp[j + w[i]], dp[j] + v[i]);
        }
    }
    //DEBUG_VEC(dp);

    ll ans = 0;
    REP(i,W+1){
        chmax(ans,dp[i]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

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

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------
string S;
string T;

int main() {
  cin >> S >> T;
  for (int i = 0; i < S.size(); ++i) {
    if (S == T) {
      cout << "Yes" << endl;
      return 0;
    }
    S = S[S.size() - 1] + S.substr(0, S.size() - 1);
  }
  cout << "No" << endl;
}


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

int main()
{
  int S[13], H[13], C[13], D[13];
  int n;
  char a;
  int num;
  for (int i = 0; i < 13; i++)
  {
    S[i] = -1;
    H[i] = -1;
    C[i] = -1;
    D[i] = -1;
  }
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> a >> num;
    switch (a)
    {
    case ('S'):
      S[num - 1] = 1;
      break;
    case ('H'):
      H[num - 1] = 1;
      break;
    case ('C'):
      C[num - 1] = 1;
      break;
    case ('D'):
      D[num - 1] = 1;
      break;
    }
  }

  for (int i = 0; i < 13; i++)
  {
    if (S[i] == -1)
    {
      cout << "S" << " " <<  i + 1 << endl;
    }
  }
  for (int i = 0; i < 13; i++)
  {
    if (H[i] == -1)
    {
      cout << "H" << " " << i + 1 << endl;
    }
  }
  for (int i = 0; i < 13; i++)
  {
    if (C[i] == -1)
    {
      cout << "C" << " " << i + 1 << endl;
    }
  }
  for (int i = 0; i < 13; i++)
  {
    if (D[i] == -1)
    {
      cout << "D" << " " << i + 1 << endl;
    }
  }
}


Measured memory_bytes: 3096
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
using namespace std;

int main(){
    long long n, p;
    cin >> n >> p;

    map<long long, long long> T;
    long long num = p;
    for(long long i = 2; i * i <= num; i++){
        if(num % i != 0) continue;

        while(num % i == 0){
            if(T.find(i) == T.end()){
                T[i] = 1;
                num /= i;
            }
            else{
                T[i]++;
                num /= i;
            }
        }
    }
    if(num != 1) T[num] = 1;

    long long ans = 1;
    map<long long, long long>::iterator it;
    for(it = T.begin(); it != T.end(); it++){
        long long r = it->second / n;
        for(long long i = 0; i < r; i++){
            ans *= it->first;
        }
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

int main() {
  int n; cin >> n;
  map<int, int> mp;
  LL ans = 0;
  for (int i = 0; i < n; i ++) {
    int a; cin >> a;
    ans += mp[i - a];
    mp[i + a] ++;
  }

  cout << ans << endl;
}


Measured memory_bytes: 20584
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ull B = 100000007;
int mod = 1000000007;

class Solution {
public:
    vector<ll> dp;
    int N, M;
    ll e(int N, int M) {
        dp = vector<ll>(N + 1, -1);
        ll res = 1;
        for(int i = 0; i < N; ++i) {
            res *= (M - i);
            res %= mod;
        }
        return (res * dfs(N, M)) % mod;
    }
    ll dfs(int n, int m) {
        if(dp[n] != -1) { return dp[n]; }
        if(n < 1) return 1;
        ll res = 0;
        res += (m - n) * dfs(n - 1, m - 1) % mod;
        res %= mod;
        res += (n - 1) * (dfs(n - 1, m - 1) + dfs(n - 2, m - 2)) % mod;
        res %= mod;
        dp[n] = res;
        return res;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    Solution zhy;
    cout << zhy.e(n, m) << endl;
    return 0;
}

Measured memory_bytes: 46224
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
using namespace std;

int main(){
string s;cin>>s;
int a,b;
for(int i=0;i<s.length();i++){
    if(s[i]=='A'){a=i;break;}
}
for(int i=s.length()-1;i>=0;i--)
if(s[i]=='Z'){b=i;break;}
cout<<b-a+1;
}

Measured memory_bytes: 832
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
	int a;
	cin>>a;
	if(a>=1200)cout<<"ARC"<<endl;
	else cout<<"ABC"<<endl;
	return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

n, k = [int(x) for x in input().split()]
a = [int(x) for x in range(n + 1)]
a_rev = a[::-1]
mod = 10**9 + 7

left = sum(a[:k])
right = sum(a_rev[:k])

ans = right - left + 1

for i in range(k, n + 2):
    if i > n:
        break
    left += a[i]
    right += a_rev[i]
    ans += right - left + 1
    ans %= mod

print(ans)


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

typedef const void cv;

int downint(cv *a, cv *b) {
  return *(int *)a < *(int *)b ? 1 : *(int *)a > *(int *)b ? -1 : 0;
}

int main(void){
  int n,a[200000],i,j;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  
  qsort(a,n,sizeof(int),downint);
  for(i=0;i<n-1;i++){
      if(a[i] == a[i+1]){
      	printf("NO");
      	return 0;
      }
  }
  printf("YES");
  
  return 0;
}
   

Measured memory_bytes: 1788
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <functional>
#include <assert.h>
using ll=long long;
#define int ll
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define SZ(x) x.size()
#define fi first
#define se second
const int INF = 1e9;
using namespace std;

template<class T> using vc=vector<T>;
template<class T> using vvc=vc<vc<T>>;

using pi=pair<int,int>;
using vi=vc<int>;

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

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(20);

    while(true){
        int N; cin >> N;
        if(N==0) break;
        int l=0,r=0;
        int frag=0;
        int cnt=0;
        rep(i,N){
            string s; cin >> s;
            if(s=="lu") l=1;
            else if(s=="ru") r=1;
            else if(s=="ld") l=0;
            else r=0;
            if(l==r){
                if(l^frag){
                    cnt++; frag=1-frag;
                }
            }
        }
        cout << cnt << "\n";
    }
}


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

int main() {
  long long n,a,b;
  cin>>n>>a>>b;
  if(a>b)cout<<0<<endl;
  else if(n==1&&a!=b)cout<<0<<endl;
  else cout<<(n-2)*(b-a)+1<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>
#include<unordered_map>
#include<string.h>
using namespace std;

const int a[6] = { 500,100,50,10,5,1 };
signed main() {
	int b;
	while (cin >> b, b) {
		int ans = 1 << 29;
		int d[6];
		for (int c = 0; c < 6; c++)cin >> d[6-c-1];
		for (int i = 0; i <= 500; i++) {//i???????¨??????????
			int sum = 0;
			int K = b+i;
			for (int i = 0; i < 6; i++) {
				sum += min(K / a[i], d[i]);
				K -= min(K / a[i], d[i]) * a[i];
			}
			if (K)continue;
			K = i;
			for (int i = 0; i < 6; i++) {
				sum += K / a[i];
				K -= K / a[i] * a[i];
			}
			ans = min(ans, sum);
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 3044
#include<bits/stdc++.h>
#include<iomanip>
#include <numeric>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007
#define KETA 40

using namespace std;

typedef long long  ll;
typedef pair<ll,ll> P1;
typedef pair<string,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<Pi,int> P2;
const ll INF=1000000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};


int main() {

	int n;
	int p[100001];

	cin>>n;
	rep(i,n){
		cin>>p[i];
	}

	sort(p,p+n);

	if(p[n/2-1]==p[n/2])cout<<"0"<<endl;
	else cout<<p[n/2]-p[n/2-1]<<endl;

	return 0;

}


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


int main() {
    int a,b,c,d;
    cin >>a>>b>>c>>d;
    int l=abs(a-c);
    if(l<=d || (abs(a-b)<=d&&abs(b-c)<=d))cout<<"Yes"<<endl;
    else cout <<"No"<<endl;
}

Measured memory_bytes: 256
N,M=map(int,input().split())
H=list(map(int,input().split()))
A=[]
B=[]
for _ in range(M):
  a,b=map(int,input().split())
  A.append(a)
  B.append(b)
ans=0
f=[True]*N
for j in range(M):
  if H[A[j]-1]<=H[B[j]-1]:
    f[A[j]-1]=False
  if H[B[j]-1]<=H[A[j]-1]:
    f[B[j]-1]=False
for i in f:
  if i:ans+=1
print(ans)

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

using namespace std;

const int max_n = 303, mod = 998244353;

int n, m;
bitset<max_n> b;
vector<bitset<max_n>> v;

int power(int n) {
    int res = 1;
    for (int i = 0; i < n; ++i) {
        res *= 2;
        res %= mod;
    }
    return res;
}

bool operator < (const bitset<max_n> &a, const bitset<max_n> &b) {
    for (int i = 0; i < m; ++i) {
        if (a[i] != b[i]) {
            return a[i] < b[i];
        }
    }
    return false;
}

void add(bitset<max_n> b) {
    for (int i = 0; i < v.size(); ++i) {
        if ((b ^ v[i]) < b) {
            b ^= v[i];
        }
    }
    if (b == 0) {
        return;
    }
    for (int i = 0; i < v.size(); ++i) {
        if ((b ^ v[i]) < v[i]) {
            v[i] ^= b;
        }
    }
    v.push_back(b);
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int x;
            cin >> x;
            b[j] = x;
        }
        add(b);
    }
    int ans = (power(n) + mod - power(n - v.size())) % mod;
    ans = 1LL * ans * power(m - 1) % mod;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <utility>
using namespace std;

#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define RFOR(i, a, b) for (int i = a; i > b; --i)
#define REP(i, n) for (int i = 0; i < n; ++i)

typedef long long ll;

int X, Y;
int ans = 0;

int Gcd(int a, int b) {
  if (b == 0) {
    return a;
  } else {
    return Gcd(b, a%b);
  }
}

int main() {
  cin >> X >> Y;

  if (X < Y) {
    ans = X;
  } else if (Gcd(X, Y) != Y) {
    ans = X;
  } else {
    ans = -1;
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
n = int(input())
x_list = list(map(float,input().split()))
y_list = list(map(float,input().split()))

print(sum([abs(x_list[i]-y_list[i]) for i in range(n)]))
print(pow(sum([abs(x_list[i]-y_list[i])**2 for i in range(n)]),1/2))
print(pow(sum([abs(x_list[i]-y_list[i])**3 for i in range(n)]),1/3))
print(max([abs(x_list[i]-y_list[i]) for i in range(n)]))


Measured memory_bytes: 5672
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int main(){
  string S;
  cin >> S;
  int count1 = 0, count2 = 0;
  for(int i=0;i<S.size();i++){
    if(i%2 == 0){
      if(S[i] == '0'){
        count1++;
      }else{
        count2++;
      }
    }else{
      if(S[i] == '1'){
        count1++;
      }else{
        count2++;
      }
    }
  }
  cout << min(count1, count2) << endl;
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int64_t N, K;
  vector<int64_t> H(200010);
 
  cin >> N >> K;
  for(int i=0; i<N; i++) cin >> H[i];
 
  sort(H.begin(), H.begin()+N);
 
  int64_t ans = 0;
  for(int i=0; i<N-K; i++){
    ans += H[i];
  }
 
  cout << ans << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <cstring>
#include <string>    
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll n, m;

int main(){
	cin >> n >> m;
	if(n > m){
		ll tmp = n;
		n = m;
		m = tmp; 
	}
	
	ll ans;
	if(m <= 2){ans = n*m*(n*m%2);}
	if(n == 1 && m >= 3){ans = m-2;}
	if(n == 2 && m >= 3){ans = 0;}
	if(n >= 3 && m >= 3){ans = (n-2)*(m-2);}
	
	cout << ans << endl;
	return 0;
}

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

using ull = unsigned long long;
struct RollingHash_Mersenne {
	const ull MASK30 = (1ULL << 30) - 1;
	const ull MASK31 = (1ULL << 31) - 1;
	const ull MASK61 = (1ULL << 61) - 1;
	const ull MOD = MASK61;
	const ull POSITIVIZER = MOD << 2;

	vector<ull> hash, power;

	RollingHash_Mersenne(const string &s, ull base = 10007) {
		int sz = (int)s.size();
		hash.assign(sz + 1, 0);
		power.assign(sz + 1, 0);
		power[0] = 1;
		for(int i = 0; i < sz; i++) {
			power[i + 1] = CalcMod(Mul(power[i], base));
			hash[i + 1] = CalcMod(Mul(hash[i], base) + s[i]);
		}
	}

	template <class T>
	RollingHash_Mersenne(const vector<T> &v, ull base = 10007) {
		int sz = (int)v.size();
		hash.assign(sz + 1, 0);
		power.assign(sz + 1, 0);
		power[0] = 1;
		for(int i = 0; i < sz; i++) {
			power[i + 1] = CalcMod(Mul(power[i], base));
			hash[i + 1] = CalcMod(Mul(hash[i], base) + v[i]);
		}
	}

	// a * b と mod が等しい数を返す
	// 結果は (1UL << 63) + 3 - (1UL << 31) * 3 以下
	ull Mul(ull a, ull b) {
		ull au = a >> 31;
		ull ad = a & MASK31;
		ull bu = b >> 31;
		ull bd = b & MASK31;
		ull mid = ad * bu + au * bd;
		ull midu = mid >> 30;
		ull midd = mid & MASK30;
		return au * bu * 2 + midu + (midd << 31) + ad * bd;
	}

	// mod 2^61-1を計算する
	ull CalcMod(ull x) {
		ull xu = x >> 61;
		ull xd = x & MASK61;
		ull res = xu + xd;
		if(res >= MOD) res -= MOD;
		return res;
	}

	ull get(int l, int r) { return CalcMod(hash[r] + POSITIVIZER - Mul(hash[l], power[r - l])); }

	ull connect(ull h1, ull h2, ull h2len) { return CalcMod(Mul(h1, power[h2len]) + h2); }

	// Longest Common Prefix
	int LCP(int l_this, int r_this, RollingHash_Mersenne &other, int l_other, int r_other) {
		int len = min(r_this - l_this, r_other - l_other);
		int low = 0, high = len + 1;
		while(high - low > 1) {
			int mid = (low + high) / 2;
			if(get(l_this, l_this + mid) == other.get(l_other, l_other + mid))
				low = mid;
			else
				high = mid;
		}
		return (low);
	}
};

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

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

	RollingHash_Mersenne rh(s, rand() % 10007 + 3);
	int res = 0;
	rep(i, n) {
		rep(j, n) {
			if(j <= i) continue;
			int a = rh.LCP(i, n, rh, j, n);
		//	cout << a << endl;
			res = max(res, min(a, j - i));
		}
	}
	cout << res << endl;
}

Measured memory_bytes: 3728
from collections import deque

N = int(input())
E = [[] for i in range(N)]
C = {}
D = [0] * N
parent = [0]*N
for i in range(N-1):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  E[a].append(b)
  E[b].append(a)
  C[(a,b)] = c
  C[(b,a)] = c
  
M, K = map(int, input().split())
K -= 1
parent[K] = K
Q = deque()
Q.append(K)

while Q:
  u = Q.popleft()
  d = D[u]
  for v in E[u]:
    if parent[u] == v:
      continue
    parent[v] = u
    D[v] = d + C[(u,v)]
    Q.append(v)

for i in range(M):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  print(D[x]+D[y])


  
 

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

using namespace std;

#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define EXIT(...) printf(__VA_ARGS__), exit(0)

template<typename T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int maxn = 280000;

int n, L;
int a[maxn + 5];

int ans[maxn + 5];

int pos[maxn + 5];
bool vis[maxn + 5];

int bitrev[maxn + 5];

int pre[maxn + 5];

int get_pre(int x) { return pre[x] == x ? x : pre[x] = get_pre(pre[x]); }

void dfs(int x)
{
	if (vis[x]) return;
	vis[x] = 1;
	int tmp = n - 1;
	REP(i, 0, L) if (!(x >> i & 1))
	{
		dfs(x | (1 << i));
		chkmin(tmp, a[x | (1 << i)]);
	}
	if (!~a[x]) 
	{
		tmp = get_pre(tmp);
		if (tmp == n) EXIT("NO\n");
		a[x] = tmp;
		if (!tmp) pre[tmp] = n;
		else pre[tmp] = get_pre(tmp - 1);
	}
	else if (tmp < a[x]) EXIT("NO\n");
}

int main()
{
#ifdef matthew99
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	scanf("%d", &L), n = 1 << L;
	REP(i, 0, n) scanf("%d", a + i), --a[i], pos[i] = i;
	sort(pos, pos + n, [&](int x, int y) { return a[x] > a[y]; });
	REP(i, 0, n + 1) pre[i] = i;
	REP(i, 0, n) if (~a[i])
	{
		if (!a[i]) pre[a[i]] = n;
		else pre[a[i]] = get_pre(a[i] - 1);
	}
	memset(vis, 0, sizeof vis);
	REP(i, 0, n) if (!vis[pos[i]])
	{
		dfs(pos[i]);
	}
	REP(i, 0, n) bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << (L - 1));
	REP(i, 0, n) 
	{
		ans[bitrev[i]] = a[i];
	}
	REP(i, 0, n) debug("%d ", a[i]);
	debug("\n");
	puts("YES");
	REP(i, 0, n) printf("%d ", ans[i] + 1);
	printf("\n");
	return 0;
}


Measured memory_bytes: 7552
N , X , M = map(int,input().split())
a = (X*X)%M
lis = [X]
while a not in lis:
    lis.append(a)
    a = a*a%M
i = lis.index(a)
lis1 = lis[:i]
lis2 = lis[i:]
ans=0
if N<=len(lis1):
    ans = sum(lis1[:N])
else:
    ans = sum(lis1)
    n = N - len(lis1)
    ans += (n//len(lis2))*sum(lis2)
    ans += sum(lis2[:n%len(lis2)])
#print(lis1)
#print(lis2)
print(ans)


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

#define int long long
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define vcopy(v1,v2) copy((v1).begin(), (v1).end(), back_inserter((v2)));
#define pb(n) push_back(n);

int a,b,ans;

main() {
    cin >> a >> b;
    int c=1,d=b;
    while(d) {
        c*=10;
        d/=10;
    }
    ans = a*c+b;
    int z=1;
    while(1) {
        if (pow(z,2) > ans) break;
        else if (pow(z,2) == ans) {
            ct("Yes")
            return 0;
        }
        z++;
    }
    ct("No")
}






Measured memory_bytes: 256
//A.cpp
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const ll mod=1e9+7;


int main(){
  ll r,d,x;
  cin >> r >> d >> x;
  ll memo = x;
  rep(i,10){
    memo = r*memo - d;
    printf("%lld\n", memo);
  }
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main {

    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        int gozenn = scan.nextInt();
        int gogo = scan.nextInt();
        
        while (gozenn != 0 || gogo != 0) {
            int hikaku = 0;
        int best = 0;
            for (int i = 0; i < 5; i++) {
                int kazu = gozenn + gogo;
                if (hikaku < kazu) {
                    hikaku = kazu;
                    best = i;
                }
                gozenn = scan.nextInt();
                gogo = scan.nextInt();
            }
            System.out.println((char)('A' + best) + " " + hikaku);
        }
    }
}



Measured memory_bytes: 30088
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
//using namespace __gnu_pbds;
#define rep(i,a,b) for(i=(a);i<=(b);i++)
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int,int>
#define pb push_back
#define F first
#define S second
#define mod 1000000007
#define maxn 100005
#define inf 1e10
#define boost ios::sync_with_stdio(false);cin.tie(0)
#define fr freopen("source.txt","r",stdin),freopen("output.txt","w",stdout)
#define SET(a,b) memset(a,b,sizeof(a))
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define all(x) x.begin(), x.end()
//template<typename T>
//using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
int main()
{
    boost;
    ll n,i,j,x,t,l;
    cin>>n;
    vector<pll>v;
    for(i=0;i<n;i++) {
        cin>>x>>l;
        v.pb({x-l,x+l});
    }
    sort(all(v));
    //for(auto p:v) cout<<p.F<<" "<<p.S<<"\n";
    vector<pll>ans;
    ans.pb(v[0]);
    x=v[0].S;
    for(i=1;i<v.size();i++){
        if(v[i].F<x){
            if(v[i].S<=x){
                ans.pop_back();
                x=v[i].S;
                ans.pb(v[i]);
            }
        }
        else{
            x=v[i].S;
            ans.pb(v[i]);
        }
    }
    cout<<ans.size();
}


Measured memory_bytes: 4848
matchString :: String -> String -> Bool
matchString [] _  = False
matchString s@(x:xs) p@(y:_)
  | x == y && match s p = True
  | otherwise           = matchString xs p
  where
      match :: String -> String -> Bool
      match _ [] = True
      match [] _ = False
      match (x:xs) (y:ys)
        | x == y    = match xs ys
        | otherwise = False

main :: IO ()
main = do
    s <- getLine
    p <- getLine
    if matchString (s++s) p then putStrLn "Yes" else putStrLn "No"



Measured memory_bytes: 3608
#include <stdio.h>
#include <math.h>

int main(void)
{
	double x1, x2, y1, y2;
	double X, Y, L;
	
	scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
	X=pow(x1-x2, 2);
	Y=pow(y1-y2, 2);
	L=sqrt(X+Y);
	printf("%f\n", L);
	
	return 0;
}


Measured memory_bytes: 652
#ABC141_C
import numpy as np
N,K,Q=map(int,input().split())
ans=(K-Q)*np.ones((1,N),dtype='int32')

for _ in range(Q):
    idx=int(input())
    ans[0,idx-1]+=1
ans=ans.tolist()[0]
for i in range(len(ans)):
    if ans[i]>0:
        print('Yes')
    else:
        print('No')   

Measured memory_bytes: 16832
#include "bits/stdc++.h"
using namespace std;
#define lint long long
#define low lower_bound
#define upp upper_bound
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define Rep(i, n) for (int i = int(n); i >= 0; --i)
#define all(vec) (vec).begin(), (vec).end()
#define cend printf("\n");
#define prique(T) priority_queue<T, vector<T>, greater<T>>
#define prique2(T) priority_queue<T>

struct edge { int to; double cost; };
#define P pair<int, int>
#define D pair<double, double>
#define DI pair<double, int>
//const lint mod = 998244353LL;
const lint mod = 1000000007LL;
const lint inf = 3LL * mod * mod;

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

lint modpow(lint x, lint n, lint m) {
	lint ans = 1;
	while (n > 0) {
		if (n & 1) {
			ans *= x;
			if (m <= ans) ans %= m;
		}
		x *= x;
		if (m <= x) x %= m;
		n >>= 1;
	}
	return ans;
}

lint fact[1000000];
void f_init(lint n) {
	if (1000000 <= n) return;
	fact[0] = fact[1] = 1;
	for (lint i = 2; i <= n; ++i) {
		fact[i] = i * fact[i - 1];
		if (mod <= fact[i]) fact[i] %= mod;
	}
	return;
}

lint inver[1000000]; bool inve[100000];
lint inv(lint x) {
	if (x == 0) return 0;
	else if (inve[x]) return inver[x];
	else {
		inve[x] = true;
		return inver[x] = modpow(x, mod - 2, mod);
	}
}

lint comb(lint n, lint r) {
	if (n < r) return 0;
	if (n == r) return 1;
	lint ans = fact[n] * inv(fact[n - r]) % mod * inv(fact[r]) % mod;
	if (ans < 0) return ans + mod;
	return ans;
}

lint nck[1010][1010];
void comb(lint n) {
	rep(i, n + 1) {
		rep(j, i + 1) {
			if (j == 0 || i == j) nck[i][j] = 1;
			else nck[i][j] = nck[i - 1][j - 1] + nck[i - 1][j];
		}
	}
}

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

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

bool pri(lint p) {
	for (lint i = 2; i * i <= p; i == 2 ? ++i : i += 2) if (p % i == 0) return false;
	return p > 1;
}

map<lint, lint> factring(lint n) {
	map<lint, lint>ans;
	for (lint i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			n /= i;
			++ans[i];
		}
	}
	if (n != 1) ++ans[n];
	return ans;
}

double dis(D a, D b) { return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second)); }

int n, q;
int a[100010];
int main() {
	cin >> n >> q;
	rep(i, n) {
		cin >> a[i];
	}
	sort(a, a + n);
	rep(i, q) {
		int l, r;
		cin >> l >> r;
		int b = low(a, a + n, l) - a;
		int c = upp(a, a + n, r) - a;
		cout << c - b << endl;
	}
}


Measured memory_bytes: 3544
#include <iostream>
     
    using namespace std;
     
    int main()
    {
        int n;
        cin >> n;
     
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            int a;
            cin >> a;
            while (a % 2 == 0)
            {
                sum++;
                a /= 2;
            }
        }
        cout << sum << endl;
        return 0;
    }

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

int main() {
	long long h, w, ans = 9223372036854775807;
	cin >> h >> w;
	
	if(w >= 3) ans = min(ans, (long long) ((w % 3 ? 1 : 0) * h)); // ||
	
	if(h >= 3) ans = min(ans, (long long) ((h % 3 ? 1 : 0) * w)); // =
	
	long long half = floor(w / 2), a, b, c; // T
	for(long long H = 1; H < h; H++){ // H is the height for the upper part
		a = H * w;
		b = (h - H) * half;
		c = (h - H) * (w - half);
		ans = min(ans, max(a, max(b, c)) - min(a, min(b, c)));
	}
	
	half = floor(h / 2); // |-
	for(long long W = 1; W < w; W++){ // W is the width for the left part
		a = W * h;
		b = (w - W) * half;
		c = (w - W) * (h - half);
		ans = min(ans, max(a, max(b, c)) - min(a, min(b, c)));
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
ll inf =  1e9;


int main(){
    ll n,a,b;
    cin>>n>>a>>b;
    if( (b-a)%2 == 0 ){
	cout<< ( b-a )/2<<endl;
    }else{
	//cout<< min( b-1 , n-a )<<endl;
	ll bb = n-a+1;
	ll aa = n-b+1;

	cout<< min(  ( b-(a-1) -1 )/2 + a , ( bb-(aa-1) -1 )/2 + aa )<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

dist_sum = 0
for n, i in enumerate(XY[:-1]):
    for j in XY[n+1:]:
        dist_sum += ((i[0] - j[0])**2 + (i[1] - j[1])**2) ** 0.5
print(dist_sum * 2 / N)


Measured memory_bytes: 2940
#include <iostream>
using namespace std;
template <typename T>
T gcd(T a,T b){
  if(a%b==0)return b;
  else return gcd(b,a%b);
}
template <typename T>
T lcm(T a,T b){
  return a/gcd(a,b)*b;
}
int main(){
  int a,b,c,d;cin>>a>>b>>c>>d;
  if(a==c || b==d){
    cout << 0 << endl;
    return 0;
  }
  cout << abs(a-c)+abs(b-d)-gcd(abs(a-c),abs(b-d)) << endl;
}

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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  
  if (A + B > C + D) {
    cout << "Left" << endl;
  }
  else if (A + B < C + D) {
    cout << "Right" << endl;
  }
  else {
    cout << "Balanced" << endl;
  }
}

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

int main(){
    long long n;
    string s;
    cin >> n;
    cin >> s;

    long long cnt_r = 0, cnt_g = 0, cnt_b = 0;

    for(long long i = 0; i < n; i++){
        if(s[i] == 'R') cnt_r++;
        if(s[i] == 'G') cnt_g++;
        if(s[i] == 'B') cnt_b++;
    }

    long long cnt = 0;
    for(long long i = 0; i < n; i++){
        for(long long j = 1; i+2*j < n ;j++){
            if(s[i] != s[i+j] and s[i+j] != s[i+2*j] and s[i+2*j] != s[i]) cnt++;
        }
    }

    cout << cnt_r * cnt_g * cnt_b  - cnt << endl;
    return 0;
}

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

int main()
{
  int b;
  double n,y,t,r;
  double max,sum;
  int ans;
  while(cin>>n,n){
    cin>>y;
    ans=0;
    max=0;
    for(int i=0;i<n;i++){
      cin>>b>>r>>t;
      if(t==1){
	sum=1+y*(r/100);
      }else{
	sum=pow(1+(r/100),y);
      }
      if(sum>max){
	max=sum;
	ans=b;
      }
    }
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 0
/*
 * Author:  heyuhhh
 * Created Time:  2020/6/21 20:23:32
 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#include <functional>
#include <numeric>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << std::endl; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
  template <template<typename...> class T, typename t, typename... A> 
  void err(const T <t> &arg, const A&... args) {
  for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
  #define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;

void run() {
    int n; cin >> n;
    vector <int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum ^= a[i];
    }
    for (int i = 0; i < n; i++) {
        cout << (sum ^ a[i]) << " \n"[i == n - 1];
    }
}

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

Measured memory_bytes: 3960
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <map>
#include <set>
using namespace std;
#pragma comment(linker, "/stck:1024000000,1024000000")
#define lowbit(x) (x&(-x))
#define max(x,y) (x>=y?x:y)
#define min(x,y) (x<=y?x:y)
#define MAX 100000000000000000
#define MOD 1000
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.1415926535897932384626433832
#define ios() ios::sync_with_stdio(true)
#define INF 1044266558
#define mem(a) (memset(a,0,sizeof(a)))
typedef long long ll;
int prime[100006],vis[100005][2];
void get_prime()
{
    memset(prime,0,sizeof(prime));
    prime[1]=1;
    for(int i=2;i<=100001;i++)
    {
        if(prime[i]) continue;
        for(int j=2;j*i<=100000;j++)
            prime[j*i]=1;
    }
    memset(vis,0,sizeof(vis));
    for(int i=3;i<=100000;i+=2)
    {
        vis[i][0]=vis[i-2][0];
        if(!prime[i] && !prime[(i+1)/2]) vis[i][0]++,vis[i][1]=1;
    }
}
int main()
{
    get_prime();
    int n,l,r;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d%d",&l,&r);
        printf("%d\n",vis[r][0]-vis[l][0]+(vis[l][1]?1:0));
    }
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,l;
  cin >> n >> l;
  vector<string> a(n);
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  
  sort(a.begin(),a.end());
  for(int i=0;i<n;i++){
    cout << a[i];
  }
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
    int N; cin>>N;
    vint a(N);
    REP(i,N) cin>>a[i];

    cout<<accumulate(ALL(a),0)-*max_element(ALL(a))/2<<endl;
 
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<string>
#include<sstream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<vector>
//#define int  long long 
using namespace std;
int dis[505], n, m, num, ans, k;
int find(int x)
{
	return  x == dis[x] ? x : dis[x] = find(dis[x]);
}
void uni(int x, int y)
{
	int xx = find(x), yy = find(y);
	if (xx != yy)
		dis[xx] = yy;
}
struct node{
	int x, y, c;
	friend bool operator < (node a, node b)
	{
		return a.c < b.c;
	}
}s[50005];
map<int, vector<int> > mp;
vector<int> vec;
signed main()
{
	while (~scanf("%d%d", &n, &m))
	{
		vec.clear();
		mp.clear();
		k = num = ans = 0;
		for (int i = 1; i <= n; i++)	dis[i] = i;
		for (int i = 0; i < m; i++)
		{
			scanf("%d%d%d", &s[i].x, &s[i].y, &s[i].c);
		}
		sort(s, s + m);
		for (int i = 0; i < m; i++)
		{
			if (k == n - 1)	break;
			if (find(s[i].x) != find(s[i].y))
			{
				uni(s[i].x, s[i].y);
				k++;
				vec.push_back(i);
			}
		}
		for (int i = 0; i < m; i++)
		{
			mp[s[i].c].push_back(i);
		}
		for (int i = 0; i < vec.size(); i++)
		{
			for (int j = 1; j <= n; j++)	dis[j] = j;
			for (int j = 0; j < vec.size(); j++)
			{
					if (j != i)
						uni(s[vec[j]].x, s[vec[j]].y);
			}
			int ct = s[vec[i]].c;
			k = 0;
			for (int j = 0; j < mp[ct].size(); j++)
			{
				if (find(s[mp[ct][j]].x) != find(s[mp[ct][j]].y))
				{
					k++;
				}
			}
			if (k == 1)	
			{
				num++;
				ans += ct;
			}
		}
		printf("%d %d\n", num, ans);
	}
}



Measured memory_bytes: 4208
#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 ll INF = 1LL << 60;

int main(void){
    ll x; cin >> x;
    ll t; cin >> t;
    ll ans = x-t;
    if (ans>=0) cout << ans << endl;
    else cout << "0" << endl;
    
    return 0;
}


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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ll long long

int main() {
    fastio;
    int a, b;
    cin >> a >> b;
    int ans = 0, have = 1;
    while (have < b) {
        have += a - 1;
        ans++;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
N,K = map(int,input().split())
A = list(map(int,input().split()))

MOD = 10**9+7

ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        if A[i] > A[j]:
            ans += 1
ans *= K

from collections import Counter
ctr = Counter(A)

P = (K*(K-1)//2) % MOD

s = 0
for k,v in sorted(ctr.items()):
    tmp = (v*s*P)%MOD
    ans += tmp
    ans %= MOD
    s += v

print(ans)

Measured memory_bytes: 3572
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
#include <map>
#include <stack>
using namespace std;
typedef long long int lli;
#define urept(soeji, start, n) for (int soeji = start; soeji < n; soeji++)
#define drept(soeji, start, n) for (int soeji = start; soeji > n; soeji--)
int main(void)
{
    lli N;
    cin >> N;
    lli sum = 0;
    lli county = 0;
    lli ans = 0;
    for (lli i = 2; i <= N; i++)
    {
        sum = i;
        county = 0;
        for (lli j = 1; j <= sum; j++)
        {
            if (i % j == 0)
            {
                county++;
            }
        }
        if (county == 8 && i % 2 == 1)
        {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import math
from scipy.spatial import distance
A,B,H,M = map(int,input().split())

x1 = A*math.cos((3-H)*math.pi/6-M*math.pi/(360))
y1 = A*math.sin((3-H)*math.pi/6-M*math.pi/(360))

x2 = B*math.cos((15-M)*math.pi/30)
y2 = B*math.sin((15-M)*math.pi/30)
print(math.sqrt((x2-x1)**2 + (y2-y1)**2))

Measured memory_bytes: 44444
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define P pair<int,int>
#define PP pair<P,int>
#define fi first
#define se second
#define INF 1e9
#define MOD 1000000007
#define REP(i,n) for(int i=0;i<n;i++)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define all(x) (x).begin(),(x).end()

struct UF {
  vector<int> data;
  UF(int size) : data(size, -1) { }
  bool unite(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool find(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};


int main(){
    int n,k,l;
    cin>>n>>k>>l;
    UF p(n);
    UF q(n);
    REP(i,k){
        int a,b;
        cin>>a>>b;
        a--;b--;
        p.unite(a,b);
    }
    REP(i,l){
        int a,b;
        cin>>a>>b;
        a--;b--;
        q.unite(a,b);
    }
    map<P,int> ma;
    REP(i,n){
        ma[P(p.root(i),q.root(i))]++;
    }
    REP(i,n){
        if(i)cout<<" ";cout<<ma[P(p.root(i),q.root(i))];
    }cout<<endl;
    return 0;
}

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

struct Edge {
  int v, w;
};
typedef vector<vector<Edge> > Graph;
struct State {
  int v;
  double w;
  int b;
  bool operator < (const State &s) const {
    return w > s.w;
  }
};

const int MAXN = 8;
const int MAXM = 31;
const double INF = 1e10;

int n, m, p, a, b;
int t[MAXN];
Graph g;
double cost[MAXM][1<<MAXN];

double dijkstra() {
  priority_queue<State> que;
  fill(cost[0], cost[MAXM], INF);
  que.push((State){a, 0.0, 0});
  cost[a][0] = 0;
  while(que.size()) {
    const State s = que.top();
    que.pop();
    if(cost[s.v][s.b] < s.w) continue;
    if(s.v == b) return s.w;
    for(int i = 0; i < g[s.v].size(); ++i) {
      for(int j = 0; j < n; ++j) {
        if(s.b >> j & 1) continue;
        const State u = {g[s.v][i].v,
                         s.w + (double)g[s.v][i].w / (double)t[j],
                         s.b | (1 << j)};
        if(cost[u.v][u.b] <= u.w) continue;
        cost[u.v][u.b] = u.w;
        que.push(u);        
      }
    }
  }
  return -1;
}

int main() {
  while(cin >> n >> m >> p >> a >> b &&
        (n|m|p|a|b)) {
    --a; --b;
    for(int i = 0; i < n; ++i) {
      cin >> t[i];      
    }
    g.clear(); g.resize(m);
    for(int i = 0; i < p; ++i) {
      int x, y, z;
      cin >> x >> y >> z;
      --x; --y;
      g[x].push_back((Edge){y, z});
      g[y].push_back((Edge){x, z});
    }
    double res = dijkstra();
    if(res == -1) printf("Impossible\n");
    else printf("%.10f\n", res);
  }
  return 0;
}

Measured memory_bytes: 3480
// Copyright 2020 yaito3014
#include <bits/stdc++.h>

int main() {
  using namespace std;
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  using namespace chrono_literals;
  chrono::high_resolution_clock clock;
  auto be = clock.now();
  int D;
  cin >> D;
  array<int, 26> c;
  for (auto& e : c) cin >> e;
  vector<array<int, 26>> d(D);
  for (auto& r : d)
    for (auto& e : r) cin >> e;
  auto eval = [&](vector<int> t) {
    int S = 0;
    array<int, 26> last = {};
    for (int i = 0; i < D; ++i) {
      S += d[i][t[i]];
      last[t[i]] = i + 1;
      for (int j = 0; j < 26; ++j) S -= c[j] * (i + 1 - last[j]);
    }
    return S;
  };
  mt19937 mt(random_device{}());
  uniform_int_distribution<int> dist_type(0, 25), dist_day(0, D - 1);
  vector<int> t(D);
  for (int i = 0; i < D; ++i) t[i] = i % 26;
  int S = eval(t);
  while (clock.now() - be < 1950ms) {
    int day1 = dist_day(mt);
    int day2 = dist_day(mt);
    swap(t[day1], t[day2]);
    int score = eval(t);
    if (score > S) {
      S = score;
      continue;
    }
    swap(t[day1], t[day2]);
  }
  for (const auto& e : t) cout << (e + 1) << '\n';
}


Measured memory_bytes: 3684
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, r;
void init(){
    n = read(), r = read();
}
void solve(){
    if (n >= 10) printf("%d\n", r);
    else printf("%d\n", r + 100 * (10 - n));
}
int main(){
    init();
    solve();
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
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; }
const ll MOD = 1e9+7;

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

ll A[100100];
ll L[100100];
ll R[100100];

int main(){
    int N;
    cin >> N;
    REP(i,N){
        ll a;
        cin >> a;
        A[i] = a;
    }

    L[0] = A[0];
    for(int i = 1; i < N; i++){
        L[i] = gcd(L[i-1], A[i]);
    }

    R[N-1] = A[N-1];
    for(int i = N-2; i >= 0; i--){
        R[i] = gcd(R[i+1], A[i]);
    }

    ll ans = 0;
    REP(i,N){
        if(i == 0){
            ll right = R[1];
            chmax(ans, right);
        }
        else if(i == N-1){
            ll left = L[N-2];
            chmax(ans, left);
        }
        else{
            ll left = L[i-1];
            ll right = R[i+1];
            ll tmp = gcd(left, right);
            chmax(ans, tmp);
        }
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
vector <vector<int>> vec;
vector <int> dp;

void dfs(int i){
    if(vec[i].size()==0){dp[i]=0;}
    for(auto v:vec[i]){
        if(dp[v]==-1)dfs(v);
        dp[i]=max(dp[v]+1,dp[i]);
    }
}

int main() {
    int n,m;
    cin>>n>>m;
    vec.assign(n,vector <int>(0));
    dp.assign(n,-1);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        vec[a].pb(b);
    }
    int mx=-1;
    for(int i=0;i<n;i++){
    if(dp[i]==-1)dfs(i);
    mx=max(mx,dp[i]);}
    cout<<mx<<endl;
    
    
}

Measured memory_bytes: 8192
#include<bits/stdc++.h> 
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
string s,t;
map<pair<ll,ll>,string>m;
/*string common(ll i,ll j,string s1)
{
	pair<ll,ll>p;
	//cout<<i<<" "<<j<<endl;
	p=make_pair(i,j);
	if(i==-1||j==-1)
		return s1;
	if(m.find(p)!=m.end())
		return m[p];
	if(s[i]==t[j])
	{
		string s2=s1+s[i]+common(i-1,j-1,s1);
		m[p]=s2;
	}
	else
	{
		string s3=common(i-1,j,s1);
		string s2=common(i,j-1,s1);
		if(s3.size()>s2.size())
			m[p]=s3;
		else
			m[p]=s2;
	}
	//cout<<i<<" "<<j<<" "<<m[p]<<endl;
	return m[p];
}*/
ll gcd(ll a,ll b) 
{ 
	if (a == 0) 
		return b; 
	return gcd(b % a, a); 
} 
bool isprime(ll n)
{
    for(ll i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)
            return false;
    }
    return true;
}
void lcs(string X,string Y, int m, int n ) 
{ 
   int L[m+1][n+1]; 
  
   /* Following steps build L[m+1][n+1] in bottom up fashion. Note 
      that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
   for (int i=0; i<=m; i++) 
   { 
     for (int j=0; j<=n; j++) 
     { 
       if (i == 0 || j == 0) 
         L[i][j] = 0; 
       else if (X[i-1] == Y[j-1]) 
         L[i][j] = L[i-1][j-1] + 1; 
       else
         L[i][j] = max(L[i-1][j], L[i][j-1]); 
     } 
   } 
  
   // Following code is used to print LCS 
   int index = L[m][n]; 
  
   // Create a character array to store the lcs string 
   char lcs[index+1]; 
   lcs[index] = '\0'; // Set the terminating character 
  
   // Start from the right-most-bottom-most corner and 
   // one by one store characters in lcs[] 
   int i = m, j = n; 
   while (i > 0 && j > 0) 
   { 
      // If current character in X[] and Y are same, then 
      // current character is part of LCS 
      if (X[i-1] == Y[j-1]) 
      { 
          lcs[index-1] = X[i-1]; // Put current character in result 
          i--; j--; index--;     // reduce values of i, j and index 
      } 
  
      // If not same, then find the larger of two and 
      // go in the direction of larger value 
      else if (L[i-1][j] > L[i][j-1]) 
         i--; 
      else
         j--; 
   } 
  
   // Print the lcs 
  // cout << "LCS of " << X << " and " << Y << " is " << lcs; 
  cout<<lcs;
} 
int main()
{
	cin>>s>>t;
	ll i,j;
	//string ans=common(s.size()-1,t.size()-1,"");
	lcs(s,t,s.size(),t.size());
	return 0;
}

Measured memory_bytes: 35456
#include<iostream>
    using namespace std;
     
    int main(){
        int N, X, m[101];
        cin>>N>>X;
        
        int S=0, M=1001001001;
        for(int i=0; i<N;++i){
            cin>>m[i];
            S+=m[i];
            if(m[i]<M){
                M=m[i];
            }
        }
        int ans=N+(X-S)/M;
        cout<<ans<<endl;
    }

Measured memory_bytes: 256
#include<iostream>
#include <cmath>
using namespace std;
 
int main(){
 
	int N;
  	int T,A;
  
  	cin >> N;
  	cin >> T >> A;
  	
  	double H;
  
  	
  
  	double min = 2147483647;
  	int num = 0;
  	double d = 0;
  	for(int i =1 ; i <= N ; i++){
    	//cout << abs(A-(T*1000-H[i]*6))/1000 << endl;
      	//cout << A << endl;
      
      	cin >> H; 
      	d = A-(T-H*0.006);
      	
      	
      	if(d < 0) d = -d;
        //cout << "num" << endl;      	
      	//cout << d << endl;
        //cout << "min" << endl;
        //cout << min << endl;
  		if(d < min){
        	min = d;
          	//cout << "num;Update" << endl;
			//cout << i << endl;
        	num = i;
        }  	
    
    }
  	
	cout << num << endl;
 
}

Measured memory_bytes: 256
s=input()
if 'SU' in s:
  print('7')
if 'MO' in s:
  print('6')
if 'TU' in s:
  print('5')
if 'WE' in s:
  print('4')
if 'TH' in s:
  print('3')
if 'FR' in s:
  print('2')
if 'SA' in s:
  print('1')


Measured memory_bytes: 9028
import sys
INPUT=input().split()
N=int(INPUT[0])
X=int(INPUT[1])
Y=int(INPUT[2])
LENGTH=[0]*(N-1)
for i_a in range(1,N):
    for i_b in range(i_a+1,N+1):
        way_a=i_b-i_a
        way_b=abs(X-i_a)+abs(Y-i_b)+1
        LENGTH[min(way_a,way_b)-1]+=1

for _ in range(N-1):
    print(LENGTH[_])

Measured memory_bytes: 3444