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 pair<ll, ll> Pll;


//===

const ll mod = static_cast<ll>(1e9 + 7);



int main() {
	int n, a, b, c, d;
	cin >> n >> a >> b >> c >> d;
	--a; --b; --c; --d;
	string s;
	cin >> s;

	Vi drock;
	Vi tribrank;
	
	for (int i = 0; i < n - 1; ++i) {
		if (s[i] == '#' && s[i + 1] == '#') {
			drock.push_back(i);
		}
	}
	for (int i = 1; i < n - 1; ++i) {
		if (s[i - 1] == '.' && s[i] == '.' && s[i + 1] == '.') {
			tribrank.push_back(i);
		}
	}

	//sort(drock.begin(), drock.end());
	//sort(tribrank.begin(), tribrank.end());

	bool ok = true;
	for (int i = 0; i < drock.size(); ++i) {
		if (a < drock[i] && drock[i] + 1 < c) {
			ok = false;
			break;
		}
		if (b < drock[i] && drock[i] + 1 < d) {
			ok = false;
			break;
		}
	}

	bool ok2 = true;
	if (c - d > 0) {
		ok2 = false;
		for (int i = 0; i < tribrank.size(); ++i) {
			if (b <= tribrank[i] && tribrank[i] <= d) {
				ok2 = true;
				break;
			}
		}
	}

	cout << ((ok && ok2) ? "Yes" : "No") << endl;
}

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

int main(){
	string s;
	int price;
	price = 700;
	cin >> s;
	for(int i=0; i<3; i++){
		if(s[i]=='o'){
			price +=100;
		}
	}
	cout << price << endl;
	return 0;
}

Measured memory_bytes: 256
n,a,b=map(int,input().split())
mod=(10**9+7)
def nCr_mod(n,r,mod):
  x=1
  y=1
  for i in range(r):
    x=(x*(n-i)) % mod
    y=(y*(i+1)) % mod
  return (x * pow(y, mod - 2, mod)) % mod

ans=(pow(2,n,mod)-1-nCr_mod(n,a,mod)-nCr_mod(n,b,mod))% mod
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fr first
#define sc second
const int inf=INT_MAX;
const int nmax=1e5+5;
const int mod=1e9+7;
typedef long long ll;
using namespace std;
int r,g,b,ans;
int main() 
{
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    cin>>r>>g>>b;
    ans=r*100+g*10+b;
    if(ans%4==0)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
// ofstream fout("beads.out");
//   ifstream fin("beads.in");
  string s = "";
  cin>>s;
  string year = "2018";

  s.replace(0,4,year);
  cout << s << endl;
}

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

const int inf = 1e9;
const ll linf = 1e18;
const ll mod = 1e9 + 7;

int main()
{
    int N; cin >> N;
    vector<int> d(N);
    for (int i = 0; i < N; i++) cin >> d[i];
    
    sort(d.begin(), d.end());

    cout << d[N/2] - d[N/2-1] << endl;
    return 0;
}

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

const long long maxn = 100000, mod = 1e9 + 7;
vector <long long> P3(maxn + 1), P2(maxn + 1);

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	P3[0] = 1;
	P2[0] = 1;
	for (int i = 1; i <= maxn; i++){
		P3[i] = P3[i - 1] * 3;
		P2[i] = 2 * P2[i - 1];
		P3[i] %= mod;
		P2[i] %= mod;
	}
	string s;
	cin >> s;
	long long ans = 0;
	int j = 0;
	for (int i = 0; i < s.size(); i++){
		if (s[i] == '1'){
			ans += P3[s.size() - i - 1] * P2[j];
			ans %= mod;
			j ++;
		}
	}
	ans += P2[j];
	cout << ans % mod;
}

Measured memory_bytes: 2048
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, A, B = MI()
M = min(A, B)
m = max(0, (A + B) - N )
print(M, m)

Measured memory_bytes: 38256
N = int(input())
a = list(map(int, input().split()))
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)
LCM = lcm(a[0], a[1])
# print(LCM, a[0], a[1])
for i in range(2, N):
    LCM = lcm(LCM, a[i])
answer = 0
for aN in a:
    answer += (LCM - 1) % aN
    # print(LCM, aN)

print(answer)

Measured memory_bytes: 3316
import java.util.Scanner;

public class Main {

	void main() {
		Scanner sc=new Scanner(System.in);
		
				int a = sc.nextInt();
				int b = sc.nextInt();

					System.out.println((a*b)+" "+(a+a+b+b));
	}
	
	public static void main(String[] args) {
		new Main().main();
	}

}


Measured memory_bytes: 26000
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
  int n;
  string s,t;
  cin >> n;
  cin >> s >> t;
  string result = "";
  for (int i = 0; i<n; ++i){
    result += s[i];
    result += t[i];
  }
  cout << result << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int h,w;
	cin>>h>>w;
	char a[h+2][w+2];
	for(int i=0;i<h+2;i++)
	
{
	for(int j=0;j<w+2;j++)
	a[i][j]='#';
}

	for(int i=1;i<=h;i++)
	
{
	for(int j=1;j<=w;j++)
	cin>>a[i][j];
}
for(int i=0;i<h+2;i++)
	
{
	cout<<endl;
	for(int j=0;j<w+2;j++)
	cout<<a[i][j];
}


}

Measured memory_bytes: 256
H, W = map(int,input().split())
A = []
Q = []
for _ in range(H):
    A.append(list(map(int,input().split())))
for h in range(H-1):
    for w in range(W):
        if A[h][w] % 2 == 1:
            Q.append([h+1, w+1, h+2, w+1])
            A[h+1][w] += 1
for w in range(W-1):
    if A[H-1][w] % 2 == 1:
        Q.append([H, w+1, H, w+2])
        A[H-1][w+1] += 1
print(len(Q))
for i in range(len(Q)):
    print(*Q[i])

Measured memory_bytes: 30248
n = int(input())
a = list(map(int,input().split()))
t = 0
l = 0
r = 0
ans = 0
while r < n:
    if t^a[r] == t+a[r]:
        t += a[r]
        r += 1
    else:
        t -= a[l]
        ans += r-l
        l += 1
ans += (r-l)*(r-l+1)//2
print(ans)

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

#define deb(x) cout << #x << "=" << x << endl
#define ll long long

const int mod = 1000000007;
const int N = 3e5, M = N;



void solve() {
	ll a, b, n, W;
	ll input;
	cin >> n >> W;
	vector<ll> wt(n);
	vector<ll> val(n);
	for (int i = 0; i < n; i++)
	{
		cin >> wt[i] >> val[i];
	}
	ll V = 0;
	for (auto x : val)
		V += x;
	vector<ll> dp(V + 1, INT_MAX);
	dp[0] = 0;
	for (int i = 1; i < (int) dp.size(); i++) dp[i] = INT_MAX;
	for (int i = 0; i < n; i++)
	{
		vector<ll> newdp(V + 1);
		for (int j = 0; j <= V; j++)
		{
			if (j >= val[i])
			{
				newdp[j] = min(dp[j], (ll) wt[i] + dp[j - val[i]]);
			}
			else
				newdp[j] = dp[j];
		}
		dp = newdp;
	}


	for (int i = V; i >= 0; i--)
	{
		if (dp[i] <= W)
		{
			cout << i << endl;
			break;
		}
	}
	cout << endl;














}



int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ll t = 1;
	// cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}



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

int main() {
  long long n,min = 1000000000001;
  cin >> n;
  for(int i = 1;i <= sqrt(n);i++){
    if(n%i == 0){
      if(n/i+i-2 < min) min = n/i+i-2;
    }
  }
  cout << min << endl;
}

Measured memory_bytes: 256
# include<iostream>
# include<cstring>
# include<cstdio>
using namespace std;
const int MAX=3e5+1;
int n;
string a;
int l[MAX],r[MAX];
int main()
{
	scanf("%d",&n);
	cin>>a;
	for(int i=1;i<=n;++i)
	  if(a[i-1]=='W') l[i]=l[i-1]+1,r[i]=r[i-1];
	  else l[i]=l[i-1],r[i]=r[i-1]+1;
	int ans=1e8;
	for(int i=1;i<=n;++i)
	  ans=min(ans,l[i-1]+r[n]-r[i]);
	 printf("%d",ans);
	 return 0; 
}

Measured memory_bytes: 2948
#include<stdio.h>

int main()
{
    char a[105],i,j,temp,c, flag;
    scanf("%s", a);
    for(i=0;a[i]!='\0';i++)
    {
        c=0;
        if(a[i]>='a' && a[i]<='z')
        {
            c++;
            flag=0;
            temp = a[i];
            a[i] = 'A';
            for(j=0;a[j]!='\0';j++)
            {
                if(temp==a[j])
                {
                    c++;
                    a[j]='A';
                }
            }
        }
        if(c%2==0)
        {
            flag=1;
        }
        else
        {
            break;
        }
    }
    if(flag==1)
    {
        printf("Yes\n");
    }
    else
    {
        printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 128
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ABC127_b solver = new ABC127_b();
        solver.solve(1, in, out);
        out.close();
    }

    static class ABC127_b {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int r = in.nextInt();
            int D = in.nextInt();
            int x2000 = in.nextInt();
            int bef = x2000;

            for (int i = 0; i < 10; i++) {
                bef = r * bef - D;
                out.println(bef);
            }
        }

    }
}



Measured memory_bytes: 21460
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <list>
#include <utility>
#include <tuple>
#include <cstdio>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <cmath>
#define _GLIBCXX_DEBUG
using namespace std;
const long long INF = 1LL << 60;
typedef long long ll;
int main() {
    string S,T;
    cin >> S >> T;
    int size_S=S.size();
    int size_T=T.size();
    vector<string> str(size_S - size_T+1);
    for(int i=0;i<=(size_S - size_T);i++){
        str[i]=S.substr(i,size_T);
    }
    int cnt=0;
    int max=0;
    for(int i=0;i<=size_S-size_T;i++){
        cnt=0;
        for(int j=0;j<size_T;j++){
            if(str[i][j]==T[j]){ 
                cnt++;
            }
            if(cnt>max){
                    max = cnt;
                }
        }
    }
    int ans = size_T-max;
    cout << ans << endl;
    
}

Measured memory_bytes: 3736
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
using namespace std;

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    if((b-a) % 2 == 0)cout << "Alice";
    else cout << "Borys";
}

Measured memory_bytes: 384
using System;
class Program
 {
        static void Main(string[] args)
        {
          int b,c;
         string[] str = Console.ReadLine().Split(' ');//2つ以上のスペース区切り入力の取得
            b = int.Parse(str[0]);  //数値で受け取りたい場合は変換する
            c = int.Parse(str[1]);
          int ans=b-c*2;
          if(ans<=0)
          {
            Console.WriteLine(0);
          }
          else
          {
            Console.WriteLine(ans);
          }
         
          
        }
 }

Measured memory_bytes: 13140
#include <iostream>

#define REP(i, n) for(int i = 0;i < n;i++)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ALL(a) (a).begin(), (a).end()

using namespace std;

int main(void)
{
    string str; cin >> str;
    string odd = "";

    bool add = true;
    REP(i, str.size())
    {
        if( add ) odd += str[i];
        add = !add;
    }

    cout << odd << endl;

    return 0;
}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define _GLIBCXX_DEBUG
int main() {
    int n,m;
    cin>>n>>m;
    vector<int> vec[100010];
    rep(i,n){
        int a,b;
        cin>>a>>b;
        vec[a].push_back(b);
    }
    long ans=0;
    priority_queue<int> q;
    for (int i=1;i<m+1;i++){
        if (vec[i].size()!=0){
            for (int x:vec[i]){
                q.push(x);
            }
        }
        if(q.size()==0){
            continue;
        }
        else{
        ans+=q.top();
        q.pop();
        }
    }
    cout<<ans<<endl;


    return 0;
}

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

int main()
{
    int a,b,c;
    cin >> a >> b >> c;
    int n;
    cin >> n;
    //int answer = 0;
    int m = max({a,b,c});
    for (int i=0; i<n; ++i) {
        m = m  * 2;
    }
    cout << a + b + c + m - max({a,b,c})  << endl;
    return 0;
    
}


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

using namespace std;

const int N = 2e5;

int n, m, ans;
vector<int> adj[N];
bool vis[N];

int bfs(int src) {
	int ret = 0;
	queue<int> q;

	q.push(src);
	vis[src] = 1;

	while (!q.empty()) {
		int u = q.front();
		q.pop();
		++ret;

		for (int v, i = 0; i < adj[u].size(); ++i) {
			v = adj[u][i];

			if (!vis[v]) {
				q.push(v);
				vis[v] = 1;
			}
		}
	}

	return ret;
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	cin >> n >> m;
	for (int u, v, i = 0; i < m; ++i) {
		scanf("%d%d", &u, &v);

		adj[--u].push_back(--v);
		adj[v].push_back(u);
	}

	for (int i = 0; i < n; ++i)
		if (!vis[i])
			ans = max(ans, bfs(i));

	cout << ans << endl;
}


Measured memory_bytes: 15224
/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		int[] arr = new int[b];
		int sum =0;
		for(int i=0;i<b;i++){
			arr[i] = scan.nextInt();
			sum+= arr[i];
		}
		if(sum>=a){
			System.out.println("Yes");
		}else{
				System.out.println("No");
		}
		
}

}

Measured memory_bytes: 49740
#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
const double eps=1e-10;

int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

int main(){
    while(1){
        int x, y, s; cin>>x>>y>>s;
        if(x==0) return 0;

        int ans=0;
        for(int i=1; i<s; i++){
            int a=i, b=s-i;

            int va=0;
            while(1){
                if((va*(100+x))/100>a) break;
                va++;
            }
            va--;

            int vb=0;
            while(1){
                if((vb*(100+x))/100>b) break;
                vb++;
            }
            vb--;

            if((va*(100+x))/100!=a) continue;
            if((vb*(100+x))/100!=b) continue;

            chmax(ans, va*(100+y)/100 + vb*(100+y)/100);
        }

        cout << ans << endl;
    }
}


Measured memory_bytes: 3088
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long a,b,c;
  cin >> a >> b;
  for(long long i=1;i<=min(a,b);i++){
    if(a%i==0LL&&b%i==0LL)c=i;
  }
  cout << (a*b/c) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rp(i,n) for(int i=0;i<n;i++)
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define lrp(i,n) for(long long i=0;i<n;i++)
#define lrep(i,m,n) for(long long i=m;i<=n;i++)
#define ll long long
#define sort(a) sort(a.begin(),a.end())
#define reverse(a) reverse(a.begin(),a.end())
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define abs(a,b) (a-b>0?a-b:b-a)
#define size size()

int main(){
    int n;
    cin >> n;
    vi a(n);
    rp(i,n){
        cin >> a[i];
    }
    int j,i=0,ans=0;
    vi used(n);
    rp(k,n){
        used[k]=1;
    }
    while(1){
        ans ++;
        if(a[i]==2){
            cout << ans << endl;
            break;
        }
        if(used.at(i)==0){
            cout << -1 << endl;
            break;
        }
        used.at(i)=0;
        i=a[i]-1;
    }
}






Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
//const int MOD=998244353;
const long long LINF=1e18;
#define int long long
//template
template <typename T>
void fin(T a){
  cout<<a<<endl;
  exit(0);
}
//main
signed main(){
  int N;cin>>N;
  std::vector<int> v(N+1),ans(10000000,-1);
  for(int i=0;i<N;i++)cin>>v[i],v[i]--;
  typedef pair<int,int> P;
  std::vector<P> w(N);
  for(int i=0;i<N;i++)w[i]=P(v[i],i+1);
  sort(w.begin(),w.end());
  int now=0;
  for(int i=0;i<N;i++){
    int po=w[i].first,num=w[i].second;
    for(int j=1;j<num;j++){
      while(~ans[now])now++;
      ans[now]=num;if(now>=po)fin("No");
    }
    ans[po]=num;
  }
  for(int i=0;i<N;i++){
    int po=w[i].first,num=w[i].second;
    for(int j=0;j<N-num;j++){
      while(~ans[now])now++;
      ans[now]=num;if(now<=po)fin("No");
    }
  }
  bool f=false;
  cout<<"Yes"<<endl;
  for(int i=0;i<N*N;i++){
    if(f)cout<<" ";
    cout<<ans[i];f=true;
  }
  cout<<endl;
}


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

int getsumdigits(int n){
  int get=0;
  while( n>0){
  get += n%10;
  n = n/10;}
return get;
}


int main(){
  int N, A, B;
  cin >> N >> A >> B;
  int sum=0;
  for(int i=1; i<=N; i++){
    if( getsumdigits(i)>=A && getsumdigits(i)<=B){
      sum += i;
  }
  }
  
  cout << sum << endl;
  return 0;}


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

#define     bip(a)         __builtin_popcount(a)
#define     ull            unsigned long long
#define     ll             long long
#define     u              unsigned
#define     pb             push_back
#define     pf             push_front ///for list
#define     mp             make_pair
#define     is             insert
#define     ff             first
#define     ss             second
#define     vi             vector<int>
#define     vl             vector<ll>
#define     si             set<int>
#define     sl             set<ll>
#define     li             list<int>
#define     pii            pair<int,int>
#define     pll            pair<ll,ll>
#define     mii            map<int,int>
#define     mll            map<ll,ll>
#define     ma             INT_MAX
#define     mi             INT_MIN
#define     mod            1000000007
#define     pi             3.14159265359
#define     e              2.71828182846
#define     inf            1000000000000000LL
#define     all(x)         x.begin(), x.end()
#define     lb(a,b,c)      lower_bound(a,a+b,c)-a
#define     ub(a,b,c)      upper_bound(a,a+b,c)-a
#define     lbv(a,c)       lower_bound(all(a),c)-a.begin()
#define     ubv(a,c)       upper_bound(all(a),c)-a.begin()
#define     srt1(a,b)      sort(a,a+b)
#define     srt2(a,b)      sort(a,a+b,greater<int>())
#define     gcd(a,b)       __gcd(a,b)
#define     lcm(a,b)       (a*(b/gcd(a,b)))
#define     harmonic(n)    0.57721566490153286l+log(n)
#define     mem(a, b)      memset(a, b, sizeof(a))

///s.lower_bound(a),s.upper_bound(a), for set
///nCr(x, y) = nCr(x-1, y-1) + nCr(x-1, y)
///factorial digit   ((n * log10(n / e) +log10(2 * pi * n) /2.0));


int main()
{
    int a,b,c,d,c1=0,c2=0;
    cin>>a>>b>>c>>d;
    bool flag1=false,flag2=false;
    for(int i=1;i<=10000;i++)
    {
        c-=b;
        if(c<=0 && a>0){
            cout<<"Yes\n";
            flag2=true;
            break;
        }
        a-=d;
        if(a<=0 && c>0){
            cout<<"No\n";
            flag1=true;
            break;
        }
    }
    /*if(flag1)
        cout<<"Yes\n";
    else if(flag2)
        cout<<"No\n";*/

}



Measured memory_bytes: 3584
#include <bits/stdc++.h>
#define meow(args...) fprintf(stderr, args)
typedef unsigned u32;
typedef long long s64;
typedef unsigned long long u64;
template<class T1, class T2> inline bool cmin(T1 &a, const T2 &b) {return b<a?(a=b, true):false;}
template<class T1, class T2> inline bool cmax(T1 &a, const T2 &b) {return a<b?(a=b, true):false;}
template<class Type> Type read() {
	Type a;
	bool b;
	unsigned char c;
	while(c=getchar()-48, (c>9)&(c!=253));
	for(a=(b=c==253)?0:c; (c=getchar()-48)<=9; a=a*10+c);
	return b?-a:a;
}
int (*rd)()=read<int>;

const int N=111;
int n, from[N], dis[N], maxdeg[N], queue[N], *qhead, *qtail;
std::vector<int> e[N];
int bfs(int src) {
	qhead=qtail=queue;
	memset(from+1, 0, n*sizeof(int));
	from[*qtail++=src]=-1;
	while(qhead!=qtail) {
		int u=*qhead++;
		for(int v: e[u]) if(from[v]==0) from[*qtail++=v]=u;
	}
	return qtail[-1];
}
s64 solve(int src1, int src2=-1) {
	s64 res=1;
	int maxdis;
	memset(dis+1, -1, n*sizeof(int));
	qhead=qtail=queue;
	dis[*qtail++=src1]=0;
	if(src2!=-1) dis[*qtail++=src2]=0;
	while(qhead!=qtail) {
		int u=*qhead++;
		for(int v: e[u]) if(dis[v]==-1) dis[*qtail++=v]=dis[u]+1;
	}
	maxdis=dis[qtail[-1]];
	memset(maxdeg, 0, (maxdis+1)*sizeof(int));
	for(int i=1; i<=n; ++i) cmax(maxdeg[dis[i]], e[i].size());
	if(src2==-1) ++maxdeg[0]; else ++res;
	for(int i=0; i<maxdis; ++i) res*=maxdeg[i]-1;
	return res;
}
int main() {
	s64 minleaf;
	std::vector<int> dia;
	n=rd();
	for(int i=1; i<n; ++i) {
		int a=rd(), b=rd();
		e[a].push_back(b);
		e[b].push_back(a);
	}
	for(int i=bfs(bfs(1)); i!=-1; i=from[i]) dia.push_back(i);
	if(dia.size()%2==0) {
		minleaf=solve(dia[dia.size()/2-1], dia[dia.size()/2]);
	} else {
		int u=dia[dia.size()/2];
		minleaf=solve(u);
		for(int v: e[u]) cmin(minleaf, solve(u, v));
	}
	printf("%d %lld\n", (int)(dia.size()+1)/2, minleaf);
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h> 
#include<string>
#include<math.h>
using namespace std; 
#define ll long long int
int main() 
{ 
  string arr;
  cin>>arr;
  if(arr[2]==arr[3]&&arr[4]==arr[5])
  cout<<"Yes";
  else
    cout<<"No";
 return 0;
} 



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define maxn 100005
#define Mod 1000000007
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef map<int,int> mii;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<long long> vll;
typedef vector<bool> vb;
typedef set<int> si; 
#define fori(i,a,b) for(int i = (a); i < (b); ++i)
#define rep(i,b,a) for(int i = (b); i >= (a); --i)
#define all(a) (a).begin(), (a).end()
#define __builtin_popcountll bitCountLL
#define __builtin_popcount bitCount
//__builtin_ctz 末尾0的个数, __builtin_clz 前导0的个数
//__builtin_ffs 最后一个1的位置
const int INF = 2e9;
const ll ML = 4e18;
struct cmp {
    bool operator ()  (const pll& a, const pll& b) {
        return (a.first - a.second) - (b.first - b.second) > 0;
    }
};
void solve() {
    int n;
    cin >> n;
    //vi a(n);
    vector<vector<pll>> x(n + 1),y(n + 1);
    ll res = 0;
    fori(i,0,n) {
        ll k, a, b;
        cin >> k >> a >> b;
        if(a > b) {
            x[k].push_back({a,b});
            res += a;
        }
        else {
            y[k].push_back({b,a});
            res += b;
        }
    }

    auto f = [](pll& a, pll& b) {
        return (a.first - a.second) - (b.first - b.second) > 0;
    };
    priority_queue<pll,vector<pll>, cmp> pq,tp;
    fori(i,1,n+1) {
        if(x[i].size()) {
            for(auto p : x[i]) {
                pq.push(p);
            }
            while(pq.size() > i) {
                auto p = pq.top();
                pq.pop();
                res -= p.first - p.second;
            }   
        }
    }
    rep(i,n,1) {
        if(y[i].size()) {
            int len = n - i;
            for(auto p : y[i]) {
                tp.push(p);
            }
            while(tp.size() > len) {
                auto p = tp.top();
                tp.pop();
                res -= p.first - p.second;
            } 
        }
    }
    cout << res << endl;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
	//cout.precision(30); cout << fixed;
	//freopen("D:\\data_in.txt", "r", stdin);
    int T;
    cin >> T;
    for(int kase = 1; kase <= T; ++kase) {
        solve();
    }
    
    /*clock_t start,finish;
    start = clock();
   
    finish = clock();
    cout << "\n" << (double)(finish - start) / (double)(CLOCKS_PER_SEC) * 1000 << "ms" << endl;
    */
    return 0;
}

/***************************************************************
 question:
 idea:
 tag:
 record:
 ***************************************************************/


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

#define PI 3.141592653589793

int main(){

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false); 


	int a;
	cin >> a;
	cout << a + a*a + a*a*a;
	
}

Measured memory_bytes: 3608
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
 
using namespace std;
int MOD = 1000000007;

signed main(){

    int n;
    cin >> n;
    int a[100010];
    rep(i,n)cin >> a[i];
    int x = 0;
    int y = 0;
    int s = a[0];
    int t = -1;
    unordered_set<int> st;
    rep(i,n){
        st.insert(a[i]);
        if(a[i] == a[0]){
            x++;
        }
        else{
            y++;
            t = a[i];
        }
    }
    if(st.size() >= 3){
        cout << "No" << endl;
        return 0;
    }
    if(x == n && s == n-1){
        cout << "Yes" << endl;
        return 0;
    }else if(x == n){
        if(s <= n/2)cout << "Yes" << endl;
        else cout << "No" << endl;
        return 0;
    }
    if(abs(s-t) != 1){
        cout << "No" << endl;
        return 0;
    }

    if(s > t){
        int tmp = s;
        s = t;
        t = tmp;
        tmp = x;
        x = y;
        y = tmp;
    }

    if(y >= 2*(t-x) && t-x >= 1)cout << "Yes" << endl;
    else cout << "No" << endl;



    return 0;   
}

// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://agc016.contest.atcoder.jp/tasks/agc016_b
// rm -r -f test;oj dl http://yahoo-procon2017-qual.contest.atcoder.jp/tasks/yahoo_procon2017_qual_c


Measured memory_bytes: 5156
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

using pi = pair<int,int>;

string solve()
{
    map<pi,int> ct;
    vector<int> l;
    rep(i,6)
    {
        int h,w;
        cin >>h >>w;
        if(h>w) swap(h,w);

        l.pb(h);
        l.pb(w);
        ++ct[pi(h,w)];
    }

    sort(all(l));
    l.erase(unique(all(l)),l.end());

    int L = l.size();

    rep(k,L)rep(j,k+1)rep(i,j+1)
    {
        int a=l[i], b=l[j], c=l[k];
        pi x[3];
        x[0] = pi(a,b);
        x[1] = pi(a,c);
        x[2] = pi(b,c);

        map<pi,int> rem=ct;
        bool ok = true;
        rep(xx,3)
        {
            if(rem[x[xx]]>=2) rem[x[xx]]-=2;
            else ok=false;
        }
        if(ok) return "yes";
    }

    return "no";
}

int main()
{
    cout << solve() << endl;
    return 0;
}

Measured memory_bytes: 3220
def dfs(i, f, sum):
    if i == 3:
        if sum == 7:
            # 答えは1つ出力すれば良いので =7 になれば終了
            print(f + "=7")
            exit()

    else:
        # 式 f の末尾に符号と次の数字を追加し、その分 sum に加減する
        dfs(i + 1, f + "-" + s[i + 1], sum - int(s[i + 1]))
        dfs(i + 1, f + "+" + s[i + 1], sum + int(s[i + 1]))


s = input()

dfs(0, s[0], int(s[0]))

Measured memory_bytes: 9200
using System;
class Program
{
	static void Main(string[] args)
	{
		// スペース区切りの整数の入力
		string[] input = Console.ReadLine().Split(' ');
		int num0 = int.Parse(input[0]);
		int num1 = int.Parse(input[1]);
		int num2 = int.Parse(input[2]);
		int sum = num0+num1+num2;
		if (sum>=22)
			Console.WriteLine("bust");
		else
			Console.WriteLine("win");
	}
}

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

int main(){
  int n;
  cin >> n;
  string str;
  cin >> str;
  int fw;
  rep(i,str.size()){
    if(str[i]=='W'){
      fw = i;
      break;
    }
  }
  int lr;
  for(int i=str.size()-1;i>=0;i--){
    if(str[i]=='R'){
      lr = i;
      break;
    }
  }
  int cntr=0;
  int cntw=0;
  for(int i=fw;i<=lr;i++){
    if(str[i]=='R')cntr++;
    if(str[i]=='W')cntw++;
  }
  int pos=0;
  for(int i=fw;i<fw+cntr;i++){
    if(str[i]=='W')pos++;
  }

  cout << pos << endl;


}


Measured memory_bytes: 3736
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s=sc.next();
    long res=0,buff=(long)Math.pow(10, s.length())-1,buff1=(Integer.valueOf(s.substring(0, 1))+1)*(long)Math.pow(10, s.length()-1)-1;
    if(buff==Long.valueOf(s)) {
    	System.out.println(s.length()*9);
    }else if(s.length()==1) {
    	System.out.println(s);
    }else if(buff1==Long.valueOf(s)) {
    	System.out.println(Integer.valueOf(s.substring(0, 1))+9*(s.length()-1));
    }else if(s.substring(0, 1).equals("1")) {
    	System.out.println(9*(s.length()-1));
    }else {
    	res=Long.valueOf(s.substring(0,1))-1;
    	System.out.println(res+9*(s.length()-1));
    }
   // System.out.println(buff1);
  }
}

Measured memory_bytes: 22868
#include <bits/stdc++.h>
#pragma target("avx")
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;
    
#define rep(i,n) for(ll (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(ll i=(a);i<(b);i++)
#define rrrep(i,a,b) for(ll i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 
#define U_MAP unordered_map<ll,ll>
#define pq priority_queue<ll>
#define rpq priority_queue<ll,vector<ll>,greater<ll>>
#define p_b push_back
    
ll n,cnt,ans,a[ohara],b[ohara],c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k,q;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};
P p[ohara];
    
//------ Believe yourself as a genius!!!!!! ------

bool ok(ll x){
    ll cou=0;
    rep(i,n){
        if(p[i].fi<=x)continue;
        cou+=a[p[i].se]-x/b[p[i].se];
    }
    //if(x==4)Cout(cou);
    if(cou>k)return false;
    else return true;
}
    
int main(void){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    
    cin>>n>>k;
    rep(i,n)cin>>a[i];
    rep(i,n)cin>>b[i];
    sort(a,a+n);
    sort(b,b+n);
    reverse(b,b+n);
    rep(i,n){
        p[i]=m_p(a[i]*b[i],i);
        //cout<<p[i].fi<<"\n";
    }
    sort(p,p+n);
    reverse(p,p+n);
    ll le=0,ri=LINF,mid;
    while(ri-le>1){
        mid=(le+ri)/2;
        if(ok(mid))ri=mid;
        else le=mid;
    }
    //cout<<le<<" "<<ri<<"\n";
    //Cout(ok(4));
    rrep(i,max(le-10,0LL),min(ri+10,LINF+1)){
        //Cout(i);
        //Cout(ok(i));
        if(ok(i)==true){
            Cout(i);
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 12544
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
  string s;
  cin>>s;
  map<char,int>m;
  for(int i=0;i<s.size();i++)
  {
      m[s[i]]++;
  }
  map<char,int>::iterator it;
  int f=0;
  for(it=m.begin();it!=m.end();it++)
  {
      int x=it->second;
      if(x%2!=0)
      {
           f=1;
          cout<<"No\n";break;
      }
  }
  if(f==0)
    cout<<"Yes\n";
}


Measured memory_bytes: 3616
#include<bits/stdc++.h>
int n,m,a[101],sum,x,y;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),sum+=a[i];
	scanf("%d",&m);
	while(m--)
		scanf("%d%d",&y,&x), 
		printf("%d\n",sum-a[y]+x);
	return 0;
}

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

const int mxN = 3003;
string s,t;
const long long inf =1e18l+7;
int dp[mxN+1][mxN+1];

string LCS(string X, string Y, int m, int n)
{
	
	if (m == 0 || n == 0)
		return string("");

	
	if (X[m - 1] == Y[n - 1])
	{
	
		return LCS(X, Y, m - 1, n - 1) + X[m - 1];
	}

	
	if (dp[m - 1][n] > dp[m][n - 1])
		return LCS(X, Y, m - 1, n);

	else
	return LCS(X, Y, m, n - 1);
}

int main(){
    cin >> s >> t;
    
    int n = s.length();
    int m = t.length();
    
    for(int i=0 ; i < n+1 ; ++i){
        for(int j=0 ; j < m+1 ; ++j){
           if(i==0 || j==0){
               dp[i][j]=0;
           }else if(s[i-1]==t[j-1]){
               dp[i][j] = 1+dp[i-1][j-1];
           }else{
               dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
           }

        }

    }
    string res = LCS(s,t,n,m);
    /*
    int i = n , j = m ,ind = dp[n][m] ;
    while(i>=0 && j>=0){
        if(s[i-1]==t[j-1])
        {
            res+=s[i-1];
            i--,j--;
        }
        else if(dp[i-1][j] > dp[i][j-1]){
            i--;
        }else{
            j--;
        }
    }
     
    if(res.length()>1){
    reverse(res.begin(),res.end());
    //cout << res.length() ;
    if(!(res[0]>=95 && res[0]<=120 )){
        res = res.substr(1);
    }
    }
    //cout << "\n" << res.length()<<"\n";
    */
    cout << res;     
           
}

Measured memory_bytes: 68812
#include <stdio.h>

int main(void)
{
	int e[101][101];
	int R, C, r, c;
	int s, total;

	scanf("%d%d", &R, &C);
	for (r = 1; r <= R; r++) {
		for (c= 1; c <= C; c++) scanf("%d", &e[r][c]);
	}
	
	for (r = 1; r <= R; r++) {
		s = 0;
		for (c = 1; c <= C; c++) s += e[r][c];
		e[r][0] = s;
	}
	total = 0;
	for (c = 1; c <= C; c++) {
		s = 0;
		for (r = 1; r <= R; r++) s += e[r][c];
		e[0][c] = s;
		total += s;
	}
	for (r = 1; r <= R; r++) {
		for (c = 1; c <= C; c++) printf("%d ", e[r][c]);
		printf("%d\n", e[r][0]);
	}
	for (c = 1; c <= C; c++) printf("%d ", e[0][c]);
	printf("%d\n", total);
	return 0;
}



Measured memory_bytes: 2108
#include <stdio.h>

int main(void) {
	int total[11];
	int i, n, k, s, val;

	while (1) {
		scanf("%d", &n);
		if (!n)
			break;

		for (i = 0; i <= n; i++) {
			total[i] = 0;
		}
		for (i = 0; i < n; i++) {
			s = 0;
			for (k = 0; k < n; k++) {
				scanf("%d", &val);
				total[k] += val;
				s += val;
				printf("%5d", val);
			}
			total[k] += s;
			printf("%5d\n", s);
		}
		for (i = 0; i <= n; i++) {
			printf("%5d", total[i]);
		}
		putchar('\n');
	}
	return 0;
}

Measured memory_bytes: 616
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
typedef pair<LL, LL> pii;
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { -1,0,1,0 }, dy[4] = { 0,-1,0,1 };
const char dir[4] = { 'u','l','d','r' };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)
# pragma warning(disable:4996)


struct UnionFind {
	vector<int>Par, Rank;
	UnionFind(int n) {
		Par.resize(n);
		Rank.resize(n);
		for (int i = 0; i < n; i++) {
			Par[i] = i;
			Rank[i] = 0;
		}
	}

	int find(int x) {
		if (Par[x] == x) {
			return x;
		}
		else {
			return Par[x] = find(Par[x]);
		}
	}

	void unite(int  x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (Rank[x] < Rank[y]) {
			Par[x] = y;
		}
		else {
			Par[y] = x;
			if (Rank[x] == Rank[y])Rank[x]++;
		}
	}

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

int main() {
	int n, m;
	cin >> n >> m;
	UnionFind uf(n);
	REP(i, m) {
		int s, t;
		cin >> s >> t;
		uf.unite(s, t);
	}
	int q;
	cin >> q;
	REP(qqq, q) {
		int s, t;
		cin >> s >> t;
		cout << (uf.same(s, t) ? "yes" : "no") << endl;
	}
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lb(x) (x&-(x))
const int N = 101010;
int getsum(int num)
{
	int ans=0;
	while(num)
	{
		ans+=num%10;
		num/=10; 
	}
	return ans;
}
int main(){

	int n;
	cin>>n;
	
	if((n/getsum(n))*getsum(n)==n)
	cout<<"Yes"<<endl;
	else 
	cout<<"No"<<endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
main()
{
    int n,i;
    cin>>n;
    if(n>=30)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
         cout<<"No"<<endl;
    }
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0; i<(int)(n); i++)
int main(){
int N, K; cin >> N >> K; int A[N];
REP(i, N){ 
  cin >> A[i];
  if(i>=K){
    if(A[i-K]<A[i]){ cout << "Yes\n"; }else{ cout << "No\n"; }
  }
}
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
using V = vector<ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i, n) for(ll i=1;i<=(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rep3(i, m, n) for(ll i=m;i<=(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define MOD 1000000007
#define INF 1000000000
#define LLINF 1000000000000000000

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

// 素数判定
bool is_prime(ll n) {
	if (n == 1) return false;
	for (int i = 2; i * i <= n; ++i) {
		if (n % i == 0) return false;
	}
	return true;
}

void solve_abc_d() {
	ll n, m;
	ll l_ans = 0;

	cin >> n;

	V a(n);
	ll cnt = 0;
	rep(c, 5) {
		cnt = 0;
		for (ll p = c; p <= 55555; p += 5) {
			if (is_prime(p)) {
				a[cnt++] = p;
				if (cnt == n) {
					rep(i, n) {
						cout << a[i] << " ";
					}
					return;
				}
			}
		}
	}

	return;
}

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

	solve_abc_d();

	return 0;
}


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

int main() {
	
	int n;
	cin >> n;
	
	int ans = n;
	for(int i = 0; i <= n; i++){
		int cnt = 0;
		int t = i;
		while(t > 0){
			cnt += t % 6;
			t /= 6;
		}
		t = n - i;
		while(t > 0){
			cnt += t % 9;
			t /= 9;
		}
		if(ans > cnt) ans = cnt;
	}
	cout << ans << endl;
	return 0;
}

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

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORd(i, a, b) for (int i = (a) ; i >= (b); i--)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define sp system("pause")
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
const int N = (int) 1e5 + 10;
void TimeExecution() {
    cout << "\n\n===>> Time Execution: " << clock() / (double)1000 << " sec(s).";
}
int t;
int n;
int a[N];
int cnt[N];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    /*
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    */
    bool ok = 1;
    cin >> n;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, n)
    {
        int x = ((n - 1) + a[i]) / 2;
        int y = ((n - 1) - a[i]) / 2;
        cnt[x + 1]++;
        cnt[y + 1]++;
        if(cnt[x + 1] > 2 || cnt[y + 1] > 2) ok = 0;
    }
    ll res = 1;
    FOR(i, 1, n / 2)
    {
        if(cnt[i] == 1)
        {
            res = (res * 4) % MOD;
        }
        if(cnt[i] == 2)
        {
            res = (res * 2) % MOD;
        }
       /// cout << cnt[i] << " ";
    }
    if(ok) cout << res;
    else cout << 0;
    return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

struct edge{
	int from,to,weight;
};

bool asc(const edge &e,const edge &f){
	return e.weight < f.weight;
}

int init(vector<int> &U){
	for (int i=0;i<U.size();i++){
		U[i]=i;
	}
}

int root(vector<int> &U,int x){
	if(x==U[x]){
		return x;
	}else{
		return U[x]=root(U,U[x]);
	}
}

void unite(vector<int> &U,int x,int y){
	int px=root(U,x);
	int py=root(U,y);
	U[px]=py;
}

bool same(vector<int> &U,int x,int y){
	return root(U,x)==root(U,y);
}

int main(){
	int V,E,s,t,w;
	cin >> V >> E;
	
	vector<int> U(V);
	init(U);
	
	vector<edge> EdgeList(E);
	
	for (int i=0;i<E;i++){
		edge e;
		cin >> e.from >> e.to >> e.weight;
		EdgeList[i]=e;
	}
	
	sort(EdgeList.begin(),EdgeList.end(),asc);
	
	int W=0;
	
	for (int i=0;i<E;i++){
		edge e=EdgeList[i];
		if(same(U,e.from,e.to)){
			continue;
		}else{
			unite(U,e.from,e.to);
			W+=e.weight;
		}
	}
	
	cout << W << endl;
	
	return 0;
}

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

#define int long long
#define INF ((int)(1e17))


signed main(){
  int N;
  int A = 1, B = (int)1e9;
  vector<int> p, a, b;

  cin>>N;

  p.resize(N);
  a.resize(N);

  for(int i = 0; i < N; i++){
    cin>>p[i];
    a[p[i]-1] = i;
  }
  for(int i = 0; i < N; i++){
    if(i)cout<<" ";
    cout<<i*N+a[i]+1;
  }
  cout<<endl;
  for(int i = N-1; i >= 0; i--){
    if(i != N-1)cout<<" ";
    cout<<i*N+1;
  }
  cout<<endl;
  
  return 0;
}


Measured memory_bytes: 896
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	as := make([]int, n)
	ps := make(map[int]int)
	for i := 0; i < n; i++ {
		fmt.Scan(&as[i])

		ns := primeFactorize(as[i])
		for k, v := range ns {
			ps[k] = max(ps[k], v)
		}
	}

	x := 1
	for k, v := range ps {
		for i := 1; i <= v; i++ {
			x = mul(x, k)
		}
	}

	ans := 0
	for i := 0; i < n; i++ {
		ans = add(ans, div(x, as[i]))
	}
	fmt.Println(ans)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func primeFactorize(n int) map[int]int {
	res := make(map[int]int)
	for i := 2; i*i <= n; i++ {
		for n%i == 0 {
			n /= i
			res[i]++
		}
	}
	if n != 1 {
		res[n]++
	}
	return res
}

const mod int = 1000000007

func pow(n, k int) int {
	if k == 0 {
		return 1
	} else if k%2 == 1 {
		return pow(n, k-1) * n % mod
	} else {
		t := pow(n, k/2)
		return t * t % mod
	}
}

func add(a, b int) int {
	return (a + b) % mod
}

func sub(a, b int) int {
	return (a + mod - b) % mod
}

func mul(a, b int) int {
	return a % mod * b % mod % mod
}

func div(a, b int) int {
	return mul(a, pow(b, mod-2))
}


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

using db = double;
using ll = long long;
using vi = vector <int>;
#define op operator
#define pb push_back

db a[11];

int main() {
	cout << fixed << setprecision(9);
	ios :: sync_with_stdio(0);

	while(cin >> a[1]) {
		for(int i = 2; i <= 10; i ++)
			if(i & 1)
				a[i] = a[i - 1] / 3;
			else
				a[i] = a[i - 1] * 2;
		cout << accumulate(a + 1, a + 11, 0.0) << '\n';
	}

	return 0;
}

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

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long a, b, c, k;
  cin >> a >> b >> c >> k;
  cout << (k % 2 == 0 ? a - b : b - a) << endl;
  return 0;
}



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


void solve(){
  int n;
  cin >> n;
  int d[n+10];
  rep(i,n){
      cin >> d[i];
  }
  ll sum = 0;
  for(int i=0; i<n; i++){
      for(int j=i+1; j<n; j++){
          sum += d[i]*d[j];
      }
  }
  cout << sum << endl;
}

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


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

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

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

void solve() {
    int N;
    cin >> N;
    vector<int> v(N,0);
    REP(i,N-1) {
        int A;
        cin >> A;
        A--;
        v[A]++;
    }
    for(const auto &it: v) cout << it << endl;
}

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


Measured memory_bytes: 4048
import sys
import math
from collections import deque
input = sys.stdin.readline
M, D = map(int,input().split())
ans = 0
for i in range(1, D+1):
    for l in range(1, M+1):
        if int(str(i)[0]) >= 2 and int(str(i)[-1]) >= 2 and len(str(i)) >= 2 and l == int(str(i)[0])*int(str(i)[-1]):
            ans += 1
print(ans)


Measured memory_bytes: 3564
#include <stdio.h>

int main(){
	int W[10];
	int K[10];
	int i;
	for(i=0;i<10;i++){
		scanf("%d", &W[i]);
	}
	for(i=0;i<10;i++){
		scanf("%d", &K[i]);
	}
	int W1=0, W2=0, W3=0;
	int K1=0, K2=0, K3=0;
	int tmp;
	
	for(i=0;i<10;i++){
		if(W1<=W[i]){
			W3=W2;
			W2=W1;
			W1=W[i];
		}else if(W2<W[i]){
			W3=W2;
			W2=W[i];
		}else if(W3<W[i]){
			W3=W[i];
		}
	}
	
	for(i=0;i<10;i++){
		if(K1<=K[i]){
			K3=K2;
			K2=K1;
			K1=K[i];
		}else if(K2<K[i]){
			K3=K2;
			K2=K[i];
		}else if(K3<K[i]){
			K3=K[i];
		}
	}
	
	
	printf("%d %d\n", W1+W2+W3, K1+K2+K3);
	return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
	#define cina(a, n) for (int i = 0; i < n; ++i){ cin >> a[i]; }
	#define ll long long

	using namespace std;

	int main () {
		
		ios::sync_with_stdio(0);
		cin.tie(0);
		
		int n;
		cin >> n;
		ll a[n], result = 1;
		for (int i = 0; i < n; ++i) {
			cin >> a[i];
			if (a[i] == 0) {
				cout << 0;
				return 0;
			}
		}
		for (int i = 0; i < n; ++i) {
			if (a[i] <= 1000000000000000000 / result) {
				result *= a[i];
			} else {
				cout << -1;
				return 0;
			}
		}
		cout << result;
		return 0;
	}

Measured memory_bytes: 4444