akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace  std;
int N,a[100001],x;
long long sum = 0;
int main(){
	cin >> N >> x;
	for(int i=0;i<N;i++) cin >> a[i];
	if(a[0] > x){
		sum += a[0]-x;
		a[0] = x;
	}
	for(int i=1;i<N;i++){
		if(a[i]+a[i-1] > x){
			sum += a[i] -(x - a[i-1]);
			a[i] =x - a[i-1];
			
		}
	}
	//for(int i=0;i<N;i++) cerr << a[i] << " ";
	//cerr << endl;
	cout << sum << endl;
}

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

int main() {
    ll N;
    int count;
    cin >> N;
    count=0;
    for (int i=1;i<N+1;i++) {
        for (int j=1; j<N+1 ; j++){
            if(i*j>=N){
                break;
            }
            else{
                count=count+1;
            }
        }
    }
    cout << count;
}

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

int main() {
    int n, m, l;
    cin >> n >> m >> l;
    
    vector<long> v(m, 0), w(l, 0);
    vector<vector<long> > a(n, v), b(l, v), c(n, w);
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    
    for (int j = 0; j < m; j++) {
        for (int k = 0; k < l; k++) {
            cin >> b[k][j];
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < l; k++) {
            for (int j = 0; j < m; j++) {
                c[i][k] += a[i][j] * b[k][j];
            }
            // cout << c[i][k] << " ";
        }
        // cout << endl;
    }
    
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < l - 1; k++) {
            // for (int j = 0; j < m; j++) {
            //     c[i][k] += a[i][j] * b[k][j];
            // }
            cout << c[i][k] << " ";
        }
        cout << c[i][l-1] << endl;
    }
    
    return 0;
}


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

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;


//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

const ll INF = 1e10;

int main(){
  int n,W;
  cin >> n >> W;
  VI w(n);
  VI v(n);

  rep(i,n) cin >> w[i] >> v[i];
  VVLL dp(n+1,VLL(1e5 + 10,INF));
  rep(i,n+1) dp[i][0] = 0;

  rep(i,n){
    rep(j,1e5+1){
      if( dp[i][j] + w[i] <= W ) dp[i+1][v[i] + j] = min(dp[i][j] + w[i], dp[i][v[i] + j]);
      dp[i+1][j] = min(dp[i][j] , dp[i+1][j]);
    }
    //rep(k,10) cout << ((dp[i+1][k] == INF) ? "x" : toString(dp[i+1][k]) ) << " ";
    //cout << endl;
  }

  for(int i = 1e5 + 1; i >= 0; i--){
    if(dp[n][i] != INF){
      cout << i << endl;
      return 0;
    }
  }
  return 0;
}


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

#define fast ios_base::sync_with_stdio(false),cin.tie(NULL)
#define ldb long double 
#define db double
#define str string
#define int long long

#define fr first
#define se second
#define lb lower_bound 
#define ub upper_bound 
#define pb push_back
#define mpr make_pair

#define pi pair<int,int>
#define pdb pair<db,db>
#define pldb pair<ldb,ldb>

#define vi vector<int>
#define vdb vector<db>
#define vldb vector<ldb>
#define vpi vector< pi >

#define mi map<int,int>
#define mdb map<db,db>
#define mldb map<ldb,ldb>


#define forr(a,b) for (int i = (a); i < (b); ++i)
#define rrof(a,b) for (int i = (b)-1; i >= (a); --i)

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)

const int md = 1e9+7;
const int MX = 2e5+5;
const int INF = 1e18; 
const ldb PI = 4*atan((ldb)1);

int power(int a,int n)
{
 int res=1;
 while(n)
{
 if(n%2)
  res*=a;
  a*=a;
  n/=2;
}
return res;
}

int abst(int a)
{
 return ((a<0)?(-1*a):(a));
}
int n;
vector<str> res;

void fun(str s,char pmax)
{
    if(s.size()==n)
    {
        res.pb(s);
        return;
    }
    char chp;
    if(s.size()==0)
     chp=pmax;
     else
      chp=pmax+1;
     for(char ch='a';ch<=chp;ch++)
     {
         str q=s;
         q+=ch;
         if(ch<=pmax)
         fun(q,pmax);
         else
          fun(q,ch);
     }
     return;
}


int32_t main()
{
fast;
    cin>>n;
    str s="";
    char ch='a';
    fun(s,ch);
    sort(res.begin(),res.end());
    for(int i=0;i<res.size();i++)
     cout<<res[i]<<"\n";
    return 0;
}

Measured memory_bytes: 7796
def II(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def check(n):
  n=str(n)
  if len(n)!=N:
    return False
  for j in range(M):
    if n[int(S[j])]!=str(C[j]):
      return False
  return True  
N,M=MI()
S=[]
C=[]
for j in range(M):
  s,c=MI()
  s-=1         
  S.append(s)
  C.append(c)
i=0
while True:
  if check(i):
    print(i)
    exit()
  i+=1
  if i>1000:
    break  
print(-1)

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

int main(){
  int D,N;
  cin>>D>>N;
  int ans=1;
  rep(i,D){
    ans*=100;
  }
  if(N<100){
    ans*=N;
  }else{
    ans*=N+1;
  }
  cout<<ans<<endl;
}


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

gray = 0
brown = 0
green = 0
lightblue = 0
blue = 0
yellow = 0
orange = 0
red = 0
other = 0

for rate in a:
    if 1 <= rate <= 399:
        gray += 1
    elif 400 <= rate <= 799:
        brown += 1
    elif 800 <= rate <= 1199:
        green += 1
    elif 1200 <= rate <= 1599:
        lightblue += 1
    elif 1600 <= rate <= 1999:
        blue += 1
    elif 2000 <= rate <= 2399:
        yellow += 1
    elif 2400 <= rate <= 2799:
        orange += 1
    elif 2800 <= rate <= 3199:
        red += 1
    else:
        other += 1

s = [gray, brown, green, lightblue, blue, yellow, orange, red]
s = list(filter(lambda x: x > 0, s))

cnt = len(s)

cnt1 = max(1, cnt)

print('{} {}'.format(cnt1,  cnt+other))


Measured memory_bytes: 3064
#include<stdio.h>
int main(){
  int n,m,num,i,astart=1,bstart;
  scanf("%d%d",&n,&m);
  bstart=n/2+n%2+1;
  num=bstart;
  for(i=0;i<m;i++){
    if(i%2==0){
      printf("%d %d\n",astart,num-astart);
      astart++;
    }
    else{
      if(n%2!=0)
        printf("%d %d\n",bstart,n-bstart+num);
      else
        printf("%d %d\n",bstart,n-bstart+num-1);
      bstart++;
    }
  }
  return 0;
}


Measured memory_bytes: 1676
#include <stdio.h>
int main(void){
    long long int n, m;
    scanf("%lld %lld", &n, &m);
    
    long long int ans;
    if(n==1 && m==1)ans=1;
    else if(n==1 && m>1)ans=m-2;
    else if(n>1 && m==1)ans=n-2;
    else if(n==2 || m==2)ans=0;
    else ans=n*m-(2*n+2*m-4);
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 1696
<?php
fscanf(STDIN,'%d',$N);
fscanf(STDIN,'%d%d',$D,$X);
$choco=$X;
for ($i=1; $i <=$N ; $i++) {
  // code...
  $A=fgets(STDIN);
  if($D%$A==0){
    $choco+=$D/$A;
  }else{
    $choco+=1+floor($D/$A);
  }
}
echo $choco;
 ?>


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

using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

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

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

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  int N;
  cin >> N;

  vector<double> a(N);

  double sum = 0.0;
  rep(i, N){
    cin >> a[i];
    sum += a[i];
  }

  double mean = sum / N;

  double min_val = 200;
  rep(i, N){
    chmin(min_val, abs(a[i]-mean));
  }

  int ans = 0;
  rep(i, N){
    if(abs((abs(min_val)-abs(a[i]-mean))) < 1e-10){
      ans = i;
      break;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 int N, M, point;
  string mi;
  cin >> N;
  vector<string> nec(N);
  for(int i=0;i<N;i++) cin >> nec.at(i);
  cin >> M;
  vector<string> mec(M);
  for(int i=0;i<M;i++) cin >> mec.at(i);
    int f, h;
  f=-M;
  h=-M;
  for(int i=0;i<N;i++){
    mi = nec.at(i);
    point =0;
    for(int j=0;j<N;j++) if (mi == nec.at(j)) point++;
    for(int j=0;j<M;j++) if (mi == mec.at(j)) point--;
    if (point>=f) f = point;
  }
  if (f<0) cout << 0 << endl;
  else cout << f << endl;
}
  
    

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define pf push_front
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define SZ(x) (int)(x).size()
#define ft front()
#define bk back()
#define endl '\n'
#define FOR(a, b, c) for (auto(a) = (b); (a) < (c); ++(a))
#define ROF(a, b, c) for (auto(a) = (b); (a) > (c); --(a))
#define F0R(a, b) FOR ((a), 0, (b))
#define R0F(a, b) ROF ((a), (b), -1)
#define CEIL(a, b) ((a) + (b)-1) / (b)
#define SET(a, b) memset((a), (b), sizeof(a))
template <class t>
bool ckmin(t& a, const t& b) {
    return a > b ? a = b, true : false;
}
template <class t>
bool ckmax(t& a, const t& b) {
    return a < b ? a = b, true : false;
}
#ifndef DEBUG
#define DEBUG 0
#endif
#define dout \
    if (DEBUG) std::cerr
#define dvar(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
template <class a, class b>
ostream& operator<<(ostream& o, const pair<a, b>& p);
template <class T>
struct IsC {
    template <class C>
    static char test(typename C::const_iterator*);
    template <class C>
    static int test(...);
    static const bool value = sizeof(test<T>(0)) == sizeof(char);
};
template <>
struct IsC<string> {
    static const bool value = false;
};
template <class C>
typename enable_if<IsC<C>::value, ostream&>::type operator<<(ostream& o,
                                                             const C& c) {
    o << '[';
    for (auto it = c.begin(); it != c.end();)
        o << *it << (++it != c.end() ? ", " : "");
    return o << ']';
}
template <class a, class b>
ostream& operator<<(ostream& o, const pair<a, b>& p) {
    return o << '(' << p.fi << ", " << p.se << ')';
}

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

    ll x;
    cin >> x;
    int n = 0;
    ll b = 100;
    while (b < x) {
        b += b / 100;
        ++n;
    }
    cout << n << endl;
    return 0;
}


Measured memory_bytes: 3648
import java.util.Scanner;

public class Main {
	public static void main(String[] args)
	{
		Scanner scan = new Scanner(System.in);
		int cards = scan.nextInt();
		String[] cardA = new String[cards];
		String[] cardB = new String[cards];
		int scoreA = 0;
		int scoreB = 0;
		for(int i = 0;i < cards;i++)
		{
			cardA[i] = scan.next();
			cardB[i] = scan.next();
			
			if(cardA[i].compareTo(cardB[i]) > 0) //winner:A
			{
				scoreA += 3;
			}else if(cardA[i].compareTo(cardB[i]) < 0){ //winner:B
				scoreB += 3;
			}else{ //drrow
				scoreA += 1;
				scoreB += 1;
			}
		}
		System.out.println(scoreA + " " + scoreB);
	}
}

Measured memory_bytes: 20812
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <math.h>
#include <algorithm>
#include <deque>
#include <climits>
using namespace std;
#define rep(i,l,r) for(int i=l;i<r;i++)
#define repb(i,r,l) for(int i=r;i>l;i--)
#define ll long long
#define ull unsigned long long
#define ve vector
#define umap unordered_map
#define iter iterator

int main() {
    string s;
    cin>> s;
    int l, r;
    for(int i=0;i<s.size();i++) {
        if(s[i]=='A') {
            l=i;
            break;
        }
    }
    for(int i=s.size()-1;i>=0;i--) {
        if(s[i]=='Z') {
            r=i;
            break;
        }
    }
    cout<<r-l+1<<endl;
    return 0;
}

Measured memory_bytes: 640
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]

DP_W=[0]*(W+1)

for i in range(N):
    for j in range(W,-1,-1):
        if j+WV[i][0]<=W:
            DP_W[j+WV[i][0]]=max(DP_W[j+WV[i][0]],DP_W[j]+WV[i][1])

print(max(DP_W))

Measured memory_bytes: 42732
sx,sy,tx,ty = map(int,input().split())
r = 'R'
l = 'L'
for i in range(tx-sx-1):
    r += 'R'
    l += 'L'
u = 'U'
d = 'D'
for i in range(ty-sy-1):
    u += 'U'
    d += 'D'
ans = r + u + l + d + 'D' + r + 'R' + u + 'U' + 'L' + 'U' + l + 'L' + d + 'D' + 'R'
print(ans)

Measured memory_bytes: 3060
#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 INF = 1001001001;
const ll mod = ll(1e9)+7;

struct mint{
    ll x;
    mint(ll x = 0):x((x%mod + mod) % mod){}
    mint& operator+=(const mint a){
        if((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a){
        if((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a){
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if(!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if(t&1) a*= *this;
        return a;
    }
    mint inv() const{
        return pow(mod-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res/=a;
    }

};

struct combination {
    vector<mint> fact,ifact;
    combination(int n):fact(n+1),ifact(n+1){
        assert(n<mod);
        fact[0] = 1;
        for(int i = 1; i <= n;i++)fact[i] = fact[i] = fact[i-1] *i;
        ifact[n] = fact[n].inv();
        for(int i = n; i >= 1;i--)ifact[i-1] = ifact[i]*i; 
    }
    mint operator()(int n,int k){
        if(k < 0 || k > n) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
};


int main(){
    int x ,y;
    cin >> x >> y;
    if((x+y)%3){
        cout << 0 << endl;
        return 0;
    }
    int n = (x+y) / 3;
    x-=n;y-=n;
    if(x < 0 || y < 0){
        cout << 0 << endl;
        return 0;
    }
    combination c(x+y);
    mint ans = c(x+y,x);
    cout << ans.x << endl;
}

Measured memory_bytes: 13672
#include <cstring>
#include <cstdio>
#define INF 1e9
#define eps 1e-6
typedef long long ll;

char c[210];
int k, n, dp[110][5][2];

int dfs(int now, int cnt, bool equalN){
	if(now == n + 1)
		return cnt == k;
	if(cnt > k)
		return 0;
	if(dp[now][cnt][equalN] >= 0 && !equalN)
		return dp[now][cnt][equalN];
	
	int maxx = equalN ? c[now] - '0' : 9, sum = 0;
	for(int i = 0; i <= maxx; i++)
		sum += dfs(now + 1, cnt + (i != 0), equalN && (i == maxx));
	
	return dp[now][cnt][equalN] = sum;
}

int main(){

	memset(dp, -1, sizeof(dp));
	scanf("%s\n%d", c + 1, &k);
	n = strlen(c + 1);
	printf("%d\n", dfs(1, 0, 1));

	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<numeric>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
using ulong = unsigned long;
using ll = long long;
const int M = 1e9 + 7;
#pragma unused(M)

int main(){
	int n;
	cin >> n;
	vector<int> ts(n), as(n);
	vector<bool> tb(n), ab(n);
	for(int i=0;i<n;i++){ int t; cin >> t; ts[i] = t; }
	for(int i=0;i<n;i++){ int a; cin >> a; as[i] = a; }
	int prev = -1;
	for(int i=0;i<n;i++){ if(prev == ts[i]){ tb[i] = true; } prev = ts[i]; }
	prev = -1;
	for(int i=n-1;i>=0;i--){ if(prev == as[i]){ ab[i] = true; } prev = as[i]; }
	
	ll ans = 1;
	for(int i=0;i<n;i++){
		if(tb[i] && ab[i]){
			ans = ans * min(ts[i], as[i]) % M;
		}else if(
				!tb[i] && !ab[i] && ts[i] != as[i] || 
				!tb[i] && ts[i] > as[i] || 
				!ab[i] && as[i] > ts[i]
				){
			cout << 0 << endl;
			return 0;
		}
	}
	cout << ans << endl;
	return 0;
}



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

#pragma warning(disable:4996)
using namespace std;

typedef int Value1;
typedef int Value2;
const Value1 Zero1(10000000);
const Value2 Zero2(0);

struct Node {
	Value1 sum;//更新された値. この値を参照する時は評価が完全に完了しているようにする.
	Value2 lazy;	//遅延されている値を保存している
	Node() :sum(Zero1) {
		lazy = Zero2;
	}
};
struct lazy_segtree {
	int N;
	vector<Node>dat;
	lazy_segtree(int n) :N(1) {
		while (N < n) N *= 2;
		dat.resize(2 * N);
		for (int i = N - 1; i >= 1; --i) {
			update_node(i);
		}
	}

	Value2 lazy_connect(const Value2 l, const Value2 r) {
		return l+r;
	}

	void lazy_func(const int k, const int a, const int b) {
		dat[k].sum+=dat[k].lazy;
	}

	Value1 connect(const Value1 l, const Value1 r) {
		return min(l,r);

	}

	// inlineつけないと大変なことになるよ!(遅い)
	inline void lazy_evaluate_node(int k, int a, int b) {
		lazy_func(k, a, b);
		if (k < N) { // 2*k(左の子番号) < 2*N (節点の数) のイメージで. 末端ノードじゃなきゃ伝搬するのと等価.
			dat[2 * k].lazy = lazy_connect(dat[2 * k].lazy, dat[k].lazy);	//次は君が伝搬してね☆って感じ.
			dat[2 * k + 1].lazy = lazy_connect(dat[2 * k + 1].lazy, dat[k].lazy);
		}
		dat[k].lazy = Zero2;
	}

	inline void update_node(int k) { // kの子が既に評価されていることが前提. 末端以外のときしか呼び出さないような位置に書くのでif文要らない.
		dat[k].sum = connect(dat[2 * k].sum, dat[2 * k + 1].sum);

	}

	// update(l,r,v) := [l,r)を更新する. 区間は0-indexed.
	void update(int l, int r, Value2 v, int k = 1, int a = 0, int b = -1) {
		if (b == -1)b = N;
		if (l < 0 || r < 0)assert(false);
		lazy_evaluate_node(k, a, b); 	// とりあえず辿ったノードは都合がいいので伝搬しとけ精神.

		if (b <= l || r <= a) //[a,b)と[l,r)が交差している場合
			return;
		if (l <= a && b <= r) { // [l,r)が[a,b)を完全に含んでいる場合
			dat[k].lazy = lazy_connect(dat[k].lazy, v);
			lazy_evaluate_node(k, a, b); //一回遅延評価しとかないと都合悪いので.
			return;
		}

		int m = (a + b) / 2;
		update(l, r, v, 2 * k, a, m);
		update(l, r, v, 2 * k + 1, m, b);
		update_node(k);
	}
	//get(l,r) := [l,r)に対するクエリの答えを得る. 区間は0-indexed.
	Value1 get(int l, int r, int k = 1, int a = 0, int b = -1) {
		if (b == -1)b = N;

		if (l < 0 || r<0)assert(false);
		lazy_evaluate_node(k, a, b); // とりあえず辿ったノードは都合がいいので伝搬しとけ精神.

		if (b <= l || r <= a) //[a,b)と[l,r)が交差している場合
			return Zero1;

		if (l <= a && b <= r) { // [l,r)が[a,b)を完全に含んでいる場合
			return dat[k].sum;
		}

		int m = (a + b) / 2;
		Value1 vl = get(l, r, 2 * k, a, m);
		Value1 vr = get(l, r, 2 * k + 1, m, b);
		update_node(k);
		return connect(vl, vr);
	}
};
int main() {
	vector<int>v;
	for (int i = 0; i < 4; ++i) {
		int a;cin>>a;
		v.push_back(a);
	}
	sort(v.begin(),v.end());
	string st=(v == vector<int>{1, 4, 7, 9})?"YES":"NO";
	cout<<st<<endl;
	return 0;
}


Measured memory_bytes: 256
require 'set'

def bfs(start_node, extra = nil)
    return 0 if start_node.is_goal?(extra)
    reached = Set[start_node]
    dist = 1
    queue = [start_node]
    until queue.empty?
        next_queue = []
        until queue.empty?
            node = queue.shift
            node.each_next_node(extra) do |next_node|
                return dist if next_node.is_goal?(extra)
                next if reached.include?(next_node)
                reached << next_node
                next_queue << next_node
            end
        end
        dist += 1
        queue = next_queue
    end
    return nil
end

class Array
    def is_goal?(extra)
        self[0] <= 0
    end

    def each_next_node(extra)
        d, t = self
        (extra[:valid_weapons][t] || []).each do |a, e|
            ne = t + e
            ne = extra[:max_e] if ne > extra[:max_e]
            yield [d - a, ne]
        end
    end
end

loop do
    d, n = gets.split.map(&:to_i)
    break if n == 0
    weapons = (1..n).map { gets.split.map(&:to_i) }
    weapons.sort_by!(&:last)
    valid_weapons = {}
    (0..weapons[-1][2]).each do |t|
        l = weapons.select {|a, e, r| r <= t}
        l.map! {|a, e, _| [a, e]}
        l.uniq!
        l = l.select {|a1, e1| l.all?{|a2, e2| (a1 == a2 && e1 == e2) || (a1 > a2 || e1 > e2)}}
        valid_weapons[t] = l
    end
    puts bfs([d, 0], {:valid_weapons => valid_weapons, :max_e => weapons[-1][2]}) || 'NA'
end



Measured memory_bytes: 7128
#include <bits/stdc++.h>
using intl = long long;
using itnl = long long;
using itn = int;
using ld = long double;
using namespace std;
#define rep(i, n) for(intl i = 0; i < (intl)(n); i++)
#define rrep(i, n) for(intl i = (intl)(n) - 1; i >= 0; i--)
#define repi(i, a, b) for(intl i = (intl)(a); i < (intl)(b); i++)
#define rrepi(i, a, b) for(intl i = (intl)(a); i > (intl)(b); i--)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,1,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define alength(a) (sizeof(a) / sizeof(a[0]))
#define cin(i, a) rep(i, alength(a))cin >> a[i]
#define ccin(i, j, a) rep(i, alength(a))rep(j, alength(a[i]))cin >> a[i][j]
#define debug(x) cout << #x << ":" << x << endl
#define rdebug(i,x) rep(i, alength(x))cout << #x << "[" << i << "]:" << x[i] << endl
#define sqrt sqrtl
#define itn int
#define double ld
#define pb push_back
#define mp make_pair
#define pii pair<intl,intl>
const intl INF = 1e9;
const intl MOD = 1e9+7;
const ld eps = 1.0e-14;//-9
void fp(bool f){cout << (f ? "Yes" : "No") << endl;}
void fp(bool f, string s, string t){cout << (f ? s : t) << endl;}
intl kai(intl k){
    intl a = 1;
    for(int i = 2; i <= k; i++){
        a *= i;
    }
    return a;
}
intl gcd(intl a, intl b){
    if(!b)return a;
    return gcd(b, a % b);
}
intl lcm(intl a,intl b){
    return a / gcd(a, b) * b;
}
intl digit10(intl a){
    intl b = 0;
    do{
        a /= 10;
        b++;
    }while(a);
    return b;
}
signed main(){
    cout << fixed << setprecision(10);
    intl n;
    cin >> n;
    intl p[n];
    cin(i,p);
    intl cnt = 0;
    repi(i,1,n-1){
        intl a[3];
        a[0] = p[i-1];
        a[1] = p[i];
        a[2] = p[i+1];
        sort(a,a + 3);
        cnt += (a[1] == p[i]);
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }

template <typename T> inline T read(){
    T sum = 0;
    int fl = 1,ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') fl = -1;
    for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
    return sum * fl;
}

int n;
int ans = 0x7ffffffffffffff;

inline void Solve (){
	for(int i = 1; i <= sqrt(n); i++){
		if(!(n % i)) Chkmin(ans,(i + n / i - 2));
	}
	printf("%lld\n",ans);
}

inline void Input (){
	n = read<int>();
}

signed main(){
	Input();
	Solve();
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <map>
#include <algorithm>
#include <stdio.h>
#include <set>
#include <cmath>
#include <functional>

typedef long long ll;
using namespace std;


int main(){
    int k;
    cin >> k;
    ll ch = 10000000;
    ll a = 0;
    ll b = 7;
    ll ans = -1;
    for(ll i = 0; i < ch; i++){
        ll new_a = (a + b) % k;
        if(new_a == 0){
            ans = i + 1;
            break;
        } else {
            a = new_a;
            b = (b % k) * 10;
        }
        
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 3608
#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>
#include <utility>
#include <vector>

int main() {
  int n;
  int a[100];
  int min_cost = 1e9;
  std::cin >> n;
  for (int ni = 0; ni < n; ++ni) {
    std::cin >> a[ni];
  }
  for (int x = -100; x <= 100; ++x) {
    int cost = 0;
    for (int ni = 0; ni < n; ++ni) {
      cost += (a[ni] - x) * (a[ni] - x);
    }
    min_cost = std::min(min_cost, cost);
  }
  std::cout << min_cost << std::endl;
  return 0;
}

Measured memory_bytes: 888
#include<iostream>
#define MAX 25
#define NIL -1
using namespace std;

struct Node{
    int p,lc,rc;
};

Node T1[MAX],T2[MAX],T3[MAX];

void Preorder(Node T[],int u){
    if(u==NIL) return;
    cout<<" "<<u;
    Preorder(T,T[u].lc);
    Preorder(T,T[u].rc);
}

void Inorder(Node T[],int u){
    if(u==NIL) return;
    Inorder(T,T[u].lc);
    cout<<" "<<u;
    Inorder(T,T[u].rc);
}

void Postorder(Node T[],int u){
    if(u==NIL) return;
    Postorder(T,T[u].lc);
    Postorder(T,T[u].rc);
    cout<<" "<<u;
}

int main(){
    int n,v,l,r,root;
    cin>>n;
    for(int i=0;i<n;i++){
        T1[i].p=T1[i].lc=T1[i].rc=NIL;
    }
    for(int i=0;i<n;i++){
        cin>>v>>l>>r;
        T1[v].lc=l;
        T1[v].rc=r;
        if(l!=NIL) T1[l].p=v;
        if(r!=NIL) T1[r].p=v;
    }
    for(int i=0;i<MAX;i++){
        T2[i]=T1[i];
        T3[i]=T1[i];
    }
    for(int i=0;i<n;i++){
        if(T1[i].p==NIL) root=i;
    }
    cout<<"Preorder"<<endl;
    Preorder(T1,root);
    cout<<endl;
    cout<<"Inorder"<<endl;;
    Inorder(T2,root);
    cout<<endl;
    cout<<"Postorder"<<endl;
    Postorder(T3,root);
    cout<<endl;
}


Measured memory_bytes: 3088
k = int(input())
s = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

print(s[k - 1])

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()
#define let auto const

template<typename... Types>
struct dynarr: std::vector<Types...> {
  using std::vector<Types...>::vector;
  using size_type = typename std::vector<Types...>::size_type;
  auto&& operator[](size_type i) { return this->at(i); }
  auto&& operator[](size_type i) const { return this->at(i); }
};

int main() {
  i64 N, M;
  cin >> N >> M;
  dynarr<i64> A(M);
  dynarr<i64> B = { 0, 2, 5, 5, 4, 5, 6, 3, 7, 6 };
  rep(i,0,M) cin >> A[i];
  auto cmp = [](const string& a, const string& b) {
    if(a == "$") return true;
    else if(b == "$") return false;
    else if(a.size() != b.size()) return a.size() < b.size();
    else return a < b;
  };

  dynarr<string> dp(N + 1, "$");
  dp[0] = "";
  rep(i,1,N + 1) {
    for(auto a: A) {
      if(i - B[a] >= 0 && dp[i - B[a]] != "$") {
        string tmp = dp[i - B[a]] + (char)('0' + a);
        if(cmp(dp[i], tmp)) {
          dp[i] = tmp;
        }
      }
    }
  }

  cout << dp[N] << endl;
}


Measured memory_bytes: 41472
from functools import reduce

def binom(n, r):
    if n < r or n < 0 or r < 0: return 0
    
    if n - r < r: r = n - r
    if r == 0: return 1
    elif r == 1: return n

    numerator = [n - r + 1 + k for k in range(r)]  # (n-r+1)*(n-r+2)*...*(n-1)*n
    denominator = [1 + k for k in range(r)]         # 1*2*...*(r-1)*r

    # reduce prod(numerator)//prod(denominator)
    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] //= pivot
                denominator[k] //= pivot
    
    # calculate nCr
    return reduce(lambda x, y: x*y, numerator)

N, M = map(int, input().split())
ans = binom(N, 2) + binom(M, 2)
print(ans)

Measured memory_bytes: 3700
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)

	p := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&p[i])
	}

	rIndex := 0

	for i := 0; i <  n - 1; i++ {
		if p[i] > p[i + 1] {
			rIndex = i + 1
		}
	}

	if rIndex == 0 {
		fmt.Println("YES")
		return
	}

	for i := 0; i < n; i++ {
		if p[i] > p[rIndex] {
			tmp := p[i]
			p[i] = p[rIndex]
			p[rIndex] = tmp
			break
		}
	}

	for i := 0; i < n - 1; i++ {
		if p[i] > p[i + 1] {
			fmt.Println("NO")
			return
		}
	}
	fmt.Println("YES")
}

Measured memory_bytes: 512
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
using namespace std;

long long M = 1000000007;

#define INF (1ll<<60)
int main(int argc, char const *argv[]) {
  long long n,m;cin>>n>>m;
  vector<long long> x(n),y(m);
  for(int i=0;i<n;i++)cin>>x[i];
  for(int i=0;i<m;i++)cin>>y[i];
  long long a=0,b=0;
  for(long long i=0;i<n-1;i++){
    a+=(x[i+1]-x[i])*(i+1)*(n-i-1);
    a%=M;
  }
  for(long long i=0;i<m-1;i++){
    b+=(y[i+1]-y[i])*(i+1)*(m-i-1);
    b%=M;
  }
  cout<<(a*b)%M<<endl;
  return 0;
}


Measured memory_bytes: 1920
#include <bits/stdc++.h>
#include <string>
#include <cmath>
#include <sstream>
//#include <unordered_map>
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORD(i, a, b) for(int i = (a-1); i >= (b); i--)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
typedef long long int ll;
using namespace std;
ll mod=1000000007;
//ll mod=67280421310721;
//ll mod=998244353;
ll INF=1e18;
ll po(ll a,ll b)
{
	ll re=1;
	while(b)
	{
		if(b%2==1)
		{
			re=(re*a);
			re%=mod;
		}
		a=(a*a);
		a%=mod;
		b>>=1;
	}
	return re;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int test=1;
//	cin>>test;
	while(test--)
	{
		int a;
		cin>>a;
		cout<<a+a*a+a*a*a;
	}
	return 0;
}

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

using namespace std;

void Output(vector<int> A)
{
	int i;
	for(i=0;i<A.size()-1;i++){
		cout << A[i] << " ";
	}
	cout << A[i] << endl;
}

void InsertionSort(vector<int> A,int N)
{
	for(int i=0;i<N;i++)
	{
		int v = A[i];
		int j = i - 1;
		while(j>=0 && A[j]>v){
			A[j+1] = A[j];
			j--;
		}
		A[j+1] = v;
		Output(A);
	}
}

int main()
{	
	int N;
	cin >> N;
	
	vector<int> A;
	A.resize(N);
	for(int i=0;i<N;i++)cin >> A[i];
	InsertionSort(A, N);
	
	return 0;
}

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


void solve(long long N, std::string S){
	long ans = 0;
	int i,j;
	for(i=0;i<N;i++){
		while(1){
			if(S[i]!=S[i+1]){
				ans++;
				break;
			}
			i++;
		}
	}
	cout << ans << endl;


}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    std::string S;
    std::cin >> S;
    solve(N, S);
    return 0;
}


Measured memory_bytes: 1020
#include <functional>
#include <list>
#include <string>
#include <vector>
#include <climits>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <set>
#include <deque>
#include <stack>
#include <cassert>
using namespace std;
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define ALL(x) (x).begin(),(x).end()
#define CASET2 int ___T, case_n = 1; scanf("%d ", &___T); while ((___T > 0 ? printf("Case #%d:\n", case_n++) : 0), ___T-- > 0)
#define CASET1 int ___T, case_n = 1; scanf("%d ", &___T); while ((___T > 0 ? printf("Case #%d: ", case_n++) : 0), ___T-- > 0)
#define CASET int ___T; scanf("%d ", &___T); while (___T-- > 0)
#define SZ(X) ((int)(X).size())
#define LEN(X) strlen(X)
#define REP(i,n) for(int i=0;i<int(n);i++)
#define REP1(i,a,b) for(int i=(a);i<=int(b);i++)
#define PER1(i,a,b) for(int i=(a);i>=(b);i--)
#define REPL(i,x) for(int i=0;x[i];i++)
#define PER(i,n) for(int i=(n)-1;i>=0;i--)
#define RI1(x) scanf("%d",&x)
#define RI2(x,y) RI1(x), RI1(y)
#define RI3(x,y...) RI1(x), RI2(y)
#define RI4(x,y...) RI1(x), RI3(y)
#define RI5(x,y...) RI1(x), RI4(y)
#define RI6(x,y...) RI1(x), RI5(y)
#define GET_MACRO(_1, _2, _3, _4, _5, _6, NAME, ...) NAME
#define RI(argv...) GET_MACRO(argv, RI6, RI5, RI4, RI3, RI2, RI1)(argv)
#define DRI(argv...) int argv;RI(argv)
#define WRI(argv...) while (RI(argv) != EOF)
#define DWRI(x...) int x; WRI(x)
#define RS(x) scanf("%s",x)
#define MP make_pair
#define PB push_back
#define MS0(x) memset(x,0,sizeof(x))
#define MS1(x) memset(x,-1,sizeof(x))
#define X first
#define Y second
#define V(x) vector<x >

typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef long long LL;
const int INF = 1000000000;

void print(int i) { printf("%d", i); }
void print(LL i);
template<class T> void PI(T i) { print(i); puts(""); }
template<class T> void PIS(T i) { print(i); printf(" "); }

template<class T>
void PV(T const &v, int N) {
    REP(i, N) {
        print(v[i]);
        printf("%c", i == N-1 ? '\n' : ' ');
    }
}

template<class T> void PV(T const &v) { PV(v, SZ(v)); }

template<class T, class S> bool has_bit(T mask, S i) { return (mask >> i) & 1; }
long long shift(int i) { return 1ll << i; }

template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
int popcount(int x) { return __builtin_popcount(x); } 
int popcount(long long x) { return __builtin_popcountll(x); } 

#include <unordered_set>
#include <unordered_map>
#define EB emplace_back
#define RL(x) scanf("%lld", &(x))
#define PL(x) printf("%lld\n", x)
#define DRL(x) LL x; RL(x)

char s[104];

int main() {
    char c[] = "keyence";
    RS(s);
    int N = LEN(s), M = LEN(c);
    int i = 0, j = 0;
    while (i < min(N, M) && c[i] == s[i]) {
        i++;
    }
    while (j < min(N, M) && c[M-1-j] == s[N-1-j]) {
        j++;
    }
    if (i + j >= M) {
        puts("YES");
    } else {
        puts("NO");
    }
    return 0;
}


Measured memory_bytes: 256
fun main(args:Array<String>?): Unit {
    while(true) {
        val n = readLine()!!.trim().toInt()
        if (n == 0) return
        val islands = Array(n){
            val (w, b) = readLine()!!.trim().split(' ').map(String::toLong)
            Pair(w, b)
        }.sortedByDescending(Pair<*, Long>::second)
        val sum = islands.map(Pair<Long, *>::first).sum()
        println(
                if (islands.fold(sum){weights, (w, b) ->
                            if (b >= weights) weights - w
                            else weights } == 0L) "Yes" else "No"
        )
    }
}


Measured memory_bytes: 32932
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define ll long long 
const int MAX=1e9+7;
const int mod=1e9+7;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	ll a,b,num,x,y;
	cin>>a>>b;
	num=a/0.08;
	while(1)
	{
		x=num*0.08;y=num*0.1;
		if(x>a||y>b)
		{
			cout<<-1; return 0;
		}
		if(x==a&&y==b)
		{
			cout<<num;return 0;
		}
		num++;
	}
	
	
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1e9
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

int main(){
    int n,k;
    cin>>n>>k;
    vector<ll> h(n);
    rep(i,n) cin>>h[i];
    bool ok[n];
    rep(i,n) ok[i]=false;
    sort(all(h));
    reverse(all(h));
    rep(i,min(k,n)){
        ok[i]=true;
    }
    ll ans=0;
    rep(i,n){
        if(!ok[i]){
            ans+=h[i];
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 2048
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int INF = 1LL << 30;
int MOD = 1e9+7;
main(){
    string S;
    cin >> S;
    vector<string> str = {"KIH","B","R"};
    for(int i = 0;i < (1<<4);i++){
        string cmp = "";
        for(int j = 0;j < 4;j++){
            if(i & (1 << j))cmp += "A";
            if(j < 3)cmp += str[j]; 
        }
        if(cmp == S){
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
#include<complex>

using namespace std;

#define ll long long
#define ld long double
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

const double PI=acos(-1);
const double EPS=1e-9; //うまくいかなかったらゆるめる

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef vector<pii> vp;
typedef vector<vi> vvi;

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


signed main(void) {
    int h,n;
    cin >> h >> n;
    int sum = 0;
    rep(i,n){
        int t;
        cin >> t;
        sum += t;
    }
    if(h > sum){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }
}


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

int main(){
int w,n,a,b,c;
int number[30];
for(int i=0;i<30;i++){
	number[i]=i+1;}
cin>>w;
cin>>n;
for(int i=0;i<n;i++){
scanf("%d,%d",&a,&b);
c=number[a-1];
number[a-1]=number[b-1];
number[b-1]=c;}
for(int i=0;i<w;i++){
cout<<number[i]<<endl;}}

Measured memory_bytes: 1240
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		PriorityQueue<Integer> queue = new PriorityQueue<>();
		for (int i = 0; i < n; i++) {
		    queue.add(sc.nextInt());
		}
		Change[] changes = new Change[m];
		for (int i = 0; i < m; i++) {
		    changes[i] = new Change(sc.nextInt(), sc.nextInt());
		}
		Arrays.sort(changes);
		long total = 0;
		for (Change x : changes) {
		    if (queue.size() == 0 || queue.peek() > x.value) {
		        break;
		    }
		    for (int i = 0; i < x.times; i++) {
		        if (queue.size() == 0 || queue.peek() > x.value) {
		            break;
		        }
		        total += x.value;
		        queue.poll();
		    }
		}
		while (queue.size() > 0) {
		    total += queue.poll();
		}
		System.out.println(total);
	}

    static class Change implements Comparable<Change> {
        int value;
        int times;
        
        public Change (int times, int value) {
            this.value = value;
            this.times = times;
        }
        
        public String toString() {
            return "value:" + value + " times:" + times;
        }
        public int compareTo(Change another) {
            return another.value - value;
        }
    }

}


Measured memory_bytes: 99524
package main

import (
	"fmt"
	"strconv"
	"strings"
)

type input struct {
	from, to int
}

func main() {
	var n, k, l int
	// n = 1
	fmt.Scan(&n, &k, &l)

	inputs := make([]input, k+l)
	for i := 0; i < k+l; i++ {
		in := input{}
		fmt.Scan(&in.from, &in.to)
		inputs[i] = in
	}
	// fmt.Println(inputs)

	solve := func(inputs []input) string {
		roads := newUnion(n + 1)
		rails := newUnion(n + 1)

		for i, in := range inputs {
			if i < k {
				roads.unite(in.from, in.to)
			} else {
				rails.unite(in.from, in.to)
			}
		}
		routeSet := make(map[[2]int]int)
		for i := 1; i <= n; i++ {
			roads.parent[i] = roads.root(i)
			rails.parent[i] = rails.root(i)
			routeSet[[2]int{roads.parent[i], rails.parent[i]}]++
		}
		results := make([]string, n)
		for i := 1; i <= n; i++ {
			results[i-1] = strconv.Itoa(routeSet[[2]int{roads.parent[i], rails.parent[i]}])
		}
		return strings.Join(results, " ")
	}

	fmt.Println(solve(inputs))

}

func newUnion(n int) *union {
	u := new(union)
	u.init(n)
	return u
}

type union struct {
	parent []int
	rank   []int
}

func (u *union) init(n int) {
	u.parent = make([]int, n)
	u.rank = make([]int, n)
	for i := 0; i < n; i++ {
		u.parent[i] = i
		u.rank[i] = 0
	}
}

func (u *union) root(x int) int {
	if u.parent[x] == x {
		return x
	}
	return u.root(u.parent[x])
}
func (u *union) same(x, y int) bool {
	return u.root(x) == u.root(y)
}
func (u *union) unite(x, y int) {
	xr := u.root(x)
	yr := u.root(y)
	if xr == yr {
		return
	}
	if u.rank[xr] < u.rank[yr] {
		u.parent[xr] = yr
	} else {
		u.parent[yr] = xr
		if u.rank[xr] == u.rank[yr] {
			u.rank[xr]++
		}
	}
}


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

using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<n;i++)

int main()
{
    string s; cin>>s;
    char a = s[0];
    bool b = false;
    for(int i=1;i<s.size();i++){
        if(a==s[i]){
            cout<<"Bad"<<endl;
            b = true;
            break;
        }
        a = s[i];
    }
    if(!b){
        cout<<"Good"<<endl;
    }
    return 0;
}


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

using namespace std;
using ll = long long;

int main(int argc, const char *argv[]) {
  ll n, x, m;
  cin >> n >> x >> m;

  ll cur = x % m, cnt = 0, sum = x % m, loop_offset = -1;
  bool has_loop = false;
  vector<int> loop, loop_offsets(m + 1, -1);
  while (cur > 1 && cnt < n - 1) {
    cur = (cur * cur) % m;
    if (loop_offsets[cur] > -1) {
      has_loop = true;
      loop_offset = loop_offsets[cur];
      break;
    }

    loop_offsets[cur] = loop.size();
    loop.push_back(cur);
    sum += cur;
    cnt++;
  }

  vector<ll> loop_csum{0};
  for (int i = loop_offset; i < loop.size(); ++i) {
    loop_csum.push_back(loop_csum.back() + loop[i]);
  }

  ll remain = n - cnt - 1;
  if (!has_loop) {
    sum += remain * cur;
  } else {
    ll loop_sz = loop_csum.size() - 1;
    sum += (remain / loop_sz) * loop_csum.back();
    sum += loop_csum[remain % loop_sz];
  }

  cout << sum << '\n';

  return 0;
}

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

#define SWAP(a, b, v) v = a, a = b, b = v
#define PRED(a, b) ((a)->value > (b)->value)

typedef struct card {
	char suite[4];
	int value;
	int order;
} TYPE;

int
partition(TYPE *a, int p, int r)
{
	TYPE x = a[r];
	TYPE v;
	int i;

	for (i = p; i < r; i++) {
		if (PRED(&a[i], &x))
			continue;

		SWAP(a[p], a[i], v);
		p++;
	}

	SWAP(a[p], a[r], v);

	return p;
}

void
quick_sort(TYPE *a, int p, int r)
{
	if (p < r) {
		int q = partition(a, p, r);
		quick_sort(a, p, q - 1);
		quick_sort(a, q + 1, r);
	}
}

int
is_stable(TYPE *a, int n)
{
	int i;

	for (i = 1; i < n; i++)
		if (a[i - 1].value == a[i].value &&
		    a[i - 1].order > a[i].order)
			return 0;

	return 1;
}

int
main(void)
{
	int i, n, q;
	TYPE *a;

	scanf("%d", &n);

	a = (TYPE *)malloc(sizeof(TYPE) * n);
	if (a == NULL)
		return 1;

	for (i = 0; i < n; i++)
		scanf("%s%d", a[i].suite, &a[i].value), a[i].order = i;

	quick_sort(a, 0, n - 1);

	printf("%stable\n", is_stable(a, n) ? "S" : "Not s");
	for (i = 0; i < n; i++)
		printf("%s %d\n", a[i].suite, a[i].value);

	return 0;
}



Measured memory_bytes: 2888
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int X;
  int n = 0;
  cin >> X;
  int Y = X;
  while(X != 0){
    n += X % 10;
    X /= 10;
  }
  if(Y % n == 0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#!/usr/bin/env python3
#CADDi C

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def trial_division(n):
    factor = []
    tmp = int(math.sqrt(n)) + 1
    for i in range(2,tmp):
        while n % i == 0:
            n //= i
            factor.append(i)
    if n != 1:
        factor.append(n)
    factor.sort()
    return factor
n,p = LI()
P = trial_division(p)
P = list(Counter(P).items())
ans = 1
for i,j in P:
    ans *= i**(math.floor(j/n))
print(ans)


Measured memory_bytes: 38512
// warm heart, wagging tail,and a smile just for you!
//                                                                     ███████████   
//                                                                   ███╬╬╬╬╬╬╬╬╬╬███
//                                                                ███╬╬╬╬╬████╬╬╬╬╬╬███
//                                            ███████████       ██╬╬╬╬╬████╬╬████╬╬╬╬╬██
//                                      █████████╬╬╬╬╬████████████╬╬╬╬╬██╬╬╬╬╬╬███╬╬╬╬╬██
//                               ████████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬██╬╬╬╬╬╬╬██
//                             ████╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬╬╬╬╬╬██
//                           ███╬╬╬█╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬███╬╬╬╬╬╬╬█████
//                         ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬████████╬╬╬╬╬██
//                       ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬╬╬╬╬███
//                     ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬██
//                 ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬████
//     █████████████╬╬╬╬╬╬╬╬██╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬██████
//   ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬██████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████╬╬╬╬╬╬╬███████████╬╬╬╬╬╬╬╬██╬╬╬██╬╬╬██
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬█╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬██
// ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬▓▓▓▓▓▓╬╬╬████╬╬████╬╬╬╬╬╬╬▓▓▓▓▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬███
// ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████▓▓▓▓▓▓▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓▓▓▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬█████
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████████
//   ███╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██
//       ██████████████  ████╬╬╬╬╬╬███████████████████████████╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████
//                         ███████                           █████  ███████████████████  
#include "bits/stdc++.h"
using namespace std;
#define MOD 998244353
#define INF 1LL<<60
#define fs first
#define sc second
#define pb push_back
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) (a)<=(i) && (i)<(b)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<vector<P> > Graph;

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

  vector<int> a(4);
  REP(i,4) cin >> a[i];

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

  if(a[0] == 1 && a[1] == 4 && a[2] == 7 && a[3] == 9) cout << "YES" << endl;
  else cout << "NO" << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include<unordered_map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include<bitset>
#include<deque>
#include<string>
#include<list>
#include<iterator>
#include<sstream>
#include <algorithm>
# include <math.h>
#define lli long long int
#define lower(a) transform(a.begin(),a.end(),a.begin(),::tolower);

using namespace std;

const int N = 3e5 + 500;
const long long mod = 1e9 + 7;
const long long cmod = 998244353 ;
const long long inf = 1LL << 61;
const int M = 1e6 + 500;
const lli ths = 1LL << 40;
const int NN = 5e3 + 6;

void solve()
{
    lli n;
    cin>>n;
    string s;
    cin>>s;
    lli ans = 0;
    for(int i = 0; i < s.size(); )
    {
        while(i + 1 < s.size() && s[i] == s[i + 1])
            i ++;
        if(s[i] != s[i + 1])
            ans ++, i ++;

    }
    cout<<ans<<endl;
    return ;
}
/*
*/

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


Measured memory_bytes: 512