akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to return the count of valid pairs 
int countPairs(int a[], int n) 
{ 
    // Storing occurrences of each element 
    unordered_map<int, int> mp; 
    for (int i = 0; i < n; i++) 
        mp[a[i]]++; 
  
    // Sort the array in deceasing order 
    sort(a, a + n, greater<int>()); 
  
    // Start taking largest element each time 
    int count = 0; 
    for (int i = 0; i < n; i++) { 
  
        // If element has already been paired 
        if (mp[a[i]] < 1) 
            continue; 
  
        // Find the number which is greater than 
        // a[i] and power of two 
        int cur = 1; 
        while (cur <= a[i]) 
            cur <<= 1; 
  
        // If there is a number which adds up with a[i] 
        // to form a power of two 
        if (mp[cur - a[i]]) { 
  
            // Edge case when a[i] and crr - a[i] is same 
            // and we have only one occurrence of a[i] then 
            // it cannot be paired 
            if (cur - a[i] == a[i] and mp[a[i]] == 1) 
                continue; 
  
            count++; 
  
            // Remove already paired elements 
            mp[cur - a[i]]--; 
            mp[a[i]]--; 
        } 
    } 
  
    // Return the count 
    return count; 
} 
  
// Driver code 
int main() 
{ 
   int n;
  cin>>n;
  int a[n];
  for(int i =0;i<n;i++)cin>>a[i];
    cout << countPairs(a, n); 
    return 0; 
} 

Measured memory_bytes: 17524
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n=Integer.parseInt(sc.next());
int ans=0;
for(int i=0;i<=25;i++){
    for(int j=0;j<=14;j++){
    if(4*i+7*j==n){ans=1;break;}
    }
    if(ans==1)break;
}
if(ans==1){
System.out.println("Yes");
}
else{System.out.println("No");}
}}


Measured memory_bytes: 23252
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
// #define int long long
//#define ll long long
#define ull  unsigned long long
#define pb push_back
#define double long double

using namespace std;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = 340000;
int mod = 1e9 + 7;
int a[N];
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("input.txt", "r", stdin);
    int x, y;
    cin >> x >> y;
    a[1] = 3;
    a[2] = 2;
    a[3] = 1;
    int ans = 0;
    ans += a[x] + a[y];
    if (x == 1 && y == 1) ans += 4;
    cout << ans * 100000;
}


Measured memory_bytes: 256
import java.util.*; 
 class Main
{
    public static void main(String args[])
    {
        Scanner in=new Scanner(System.in);
        int k;
        k=in.nextInt();
        int a,b,i,num;
        a=in.nextInt();
        b=in.nextInt();
        num=a;
        for(i=num;i<=b;i++,num++)
        {
            if(i%k==0)
            {
                System.out.println("OK");
                System.exit(0);
            }
        }
        System.out.println("NG");
    }
}

Measured memory_bytes: 35932
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#define REP(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 0
//#ifdef LOCAL
//#define DEBUG(s) cout << (s) << endl
//#define dump(x)  cerr << #x << " = " << (x) << endl
//#define BR cout << endl;
//#else
//#define DEBUG(s) do{}while(0)
//#define dump(x) do{}while(0)
//#define BR
//#endif


//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 20)
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね

//ここから編集する


int main() {
    int n,k;
    cin >> n >> k;
    int num = 1;
    REP(i,0,n){
        if(num <= k){
            num += num;
        }else{
            num += k;
        }
    }

    cout << num << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//-------------------------------------------MACROS---------------------------------------------
#define 	TIEMPO_CORRIDA		cerr << "tiempo: "<<1.0*clock()/CLOCKS_PER_SEC <<" seg.\n";
#define 	FILES				freopen("input.txt","r",stdin),freopen("output.txt","w",stdout);
#define 	FORIT(it,e)			for(it = e.begin() ; it != e.end() ; it++)
#define 	FOR(i,a,b)			for(i = a ; i < b ; i++)
#define 	RFOR(i,a,b)			for(i = a ; i >= b ;i--)
#define 	FORSW(i,a,b,sw)		for(i = a ; i < b && sw ; i++)
#define 	RFORSW(i,a,b,sw)	for(i = a ; i >= b && sw ; i--)
#define 	fast 				ios::sync_with_stdio(false),cin.tie(),cout.tie();
#define 	to_int(x) 			atoi(x.data())
#define 	to_long(x) 			atoll(x.data())
#define 	ALL(x) 				x.begin(),x.end()
#define 	RALL(x) 			x.rbegin(),x.rend()
typedef 	long long 			ll;
typedef 	pair<int,int> 		pi;
typedef 	pair<ll,ll> 		pl;
const		int 				modN = 1e9+7;
const		double 				PI = 3.1415926535897932384626433832795028841;
//---------------------------------------------------------------------------------------------

int n,m;
char grid[1002][1002];
int memo[1002][1002];

int dp(int i, int j){
	if(i==n-1 && j==m-1) {memo[i][j]=0;return 1;}
	if(grid[i][j]=='#') return memo[i][j]=0;
	if(memo[i][j]!=-1) return memo[i][j];
	if(i==n-1) return memo[i][j]=dp(i,j+1);
	if(j==m-1) return memo[i][j]=dp(i+1,j);
	return memo[i][j]=((dp(i+1,j)%modN+dp(i,j+1)%modN)%modN); 
}

int main(){
	char c;
	int i,j;
	while(cin >>n >>m){
		memset(memo,-1,sizeof memo);
		FOR(i,0,n) FOR(j,0,m) cin >> grid[i][j];
		cout << dp(0,0)<<endl;
		
	}
	return 0;
}

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

int main()
{
    string S;
    cin >> S;
    int cnt = 0;
    for (int i = 0; i < S.size(); i++)
    {
        if (S[i] == '1')
        {
            cnt++;
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
sub main {
    chomp(my $S = <STDIN>);
    chomp(my $K = <STDIN>);
    print solver($S,$K);
}
main() unless caller;

sub solver {
    my ($S,$K) = @_;
    my @ar = split //, $S;
    my $fst = $ar[0];
    my $end = $ar[-1];
    my $idx = 0;
    my @ans;
    my $anser = 0;
    my $len = scalar @ar;
    if($len == 1){
        return 0 if $K == 1;
        return int($K/2);
    }
    if($S =~ /^(.)\1*$/){
        if($len%2 != 0 && $K > 1){
            return int($len * $K /2);
        }
        $anser = int($len/2);
        return $anser * $K;
    }
    for my $i(0 .. $len-1) {
        if(!defined $ans[$idx]) {
            $ans[$idx] = 1;
        }
        if($i < $len-1 && $ar[$i] eq $ar[$i+1]){
            $ans[$idx]++;
            next;
        } elsif($len > $i+1) {
            $idx++;
        }
    }
    for my $n(@ans) {
        next if $n == 1;
        $anser += int($n/2);
    }
    $anser *= $K;
    if($fst eq $end){
        if($ans[0] == 1 && $ans[-1]%2 != 0) {
            $anser += $K-1;
        }
        elsif($ans[-1] == 1 && $ans[0]%2 != 0) {
            $anser += $K-1;
        }
        elsif($ans[0]%2!=0 && $ans[-1]%2!=0 ){
            $anser += $K-1;
        }
    }
    return $anser;
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<vector>
#define inf 2147483647
#define rep(i,a,b) for(int i=a;i<b;i++)
#define  rr read()
#define ll long long
#define repb(i,a,b) for(int i=a;i<=b;i++)
#define CloseIo   ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
int read()
{
    char ch = getchar();
	int x = 0, f = 1;
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int a[10]={0};
int main()
{
  string s;
  cin>>s;
 
  for(int i=1;i<s.length();i++)
  {
  	 if(s[i-1]==s[i])
  	 {printf("Bad\n");
  	 return 0;
	   }
   } 
   printf("Good\n");
}




Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=4000+10;
int head[MAXN],e[MAXN],nxt[MAXN],tot,cnt;
pair<int,int> ed[MAXN];

inline void addedge(int u,int v)
{
	e[++tot]=v;nxt[tot]=head[u];head[u]=tot;
	e[++tot]=u;nxt[tot]=head[v];head[v]=tot;
}

void dfs(int u,int fa,int lim)
{
	++cnt;if(!lim) return ;
	for(int i=head[u];i;i=nxt[i])
		if(e[i]!=fa) dfs(e[i],u,lim-1);
}

int main()
{
	int n,k;scanf("%d %d",&n,&k);
	for(int i=1,u,v;i<n;++i) scanf("%d %d",&u,&v),addedge(u,v),ed[i]=make_pair(u,v);
	int ans=n;
	if(k&1)
	{
		for(int i=1;i<n;++i) 
		{
			cnt=0;
			dfs(ed[i].first,ed[i].second,(k-1)>>1);
			dfs(ed[i].second,ed[i].first,(k-1)>>1);
			ans=min(ans,n-cnt);
		};
	}else
	{
		for(int i=1;i<=n;++i)
		{
			cnt=0;
			dfs(i,-1,k>>1);
			ans=min(ans,n-cnt);
		};
	};
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define mod 1000000007
#define MAX 1000000000000000
#define all(v) v.begin(),v.end()
#define rep(i,a,b) for(i=(ll)a;i<(ll)b;i++)
#define revrep(i,a,b) for(i=(ll)a;i>=(ll)b;i--)
#define ii pair<ll,ll>
#define MP make_pair
#define pb push_back
#define f first
#define se second
#define ll long long int
#define vi vector<ll>
ll modexp(ll a,ll b){ ll res = 1; while(b > 0){  if(b & 1) res = (res * a)%mod;  a = (a * a)%mod;  b/=2;  }  return res; }
#define rs resize
typedef tree< ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update > OST;
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        cout << name << " : " << arg1 << endl;
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    }
#else
#define trace(...)
#endif

const ll N = 100003;
ll i,a,b,n,m,ans = -MAX;
stack<ll> s;
ll out[N],dp[N];
bool visit[N];
vector<vi> adj(N);
void dfs(ll v)
{
    visit[v] = 1;
    for(auto it: adj[v]) if(!visit[it])
        dfs(it);
    s.push(v);
}
int main()
{
    std::ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>m;
    rep(i,0,m){
        cin>>a>>b;
        adj[a].pb(b);
        out[b] += 1;
    }
    rep(i,1,n + 1) if(out[i] == 0)
        dfs(i);
    while(!s.empty()){
        a = s.top();
        ans = max(ans,dp[a]);
        s.pop();
        for(auto it: adj[a])
            dp[it] = max(dp[it],dp[a] + 1);
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 12416
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int a = 0;
        int b = 0;        
        

        for(int i=1; i<=n; i+=2){
            for(int j=1;j<=n;j+=2){
                if(i%j==0 && i>=j){
                    a++;
                    if(a==8){
                        b++;
                    }
                }
            }
            a=0;
        }
        System.out.print(b);
    }
}

Measured memory_bytes: 21844
#include <stdio.h>

int main()
{
    long num=0;
    int i,N;
    long M=0,A=0,R=0,C=0,H=0;
    char name[20];

    scanf("%d",&N);
    for(i=0;i<N;i++){
        scanf("%s",name);
        if(name[0] == 'M') {M++;}
        if(name[0] == 'A') {A++;}
        if(name[0] == 'R') {R++;}
        if(name[0] == 'C') {C++;}
        if(name[0] == 'H') {H++;}
    }
  
    num+=M*A*R;
    num+=M*A*C;
    num+=M*A*H;
    num+=A*R*C;
    num+=A*R*H;
    num+=R*C*H;
    num+=M*R*C;
    num+=M*R*H;
    num+=M*C*H;
    num+=A*C*H;
  
    printf("%ld\n",num);

    return 0;

}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
const int MOD = 1e9 + 7, N = 1e5 + 3;

int main(){
    fast;
    ll n;
    cin >> n;
    ll a[n+1], sum = 0;
    ll hash[N] = {0};
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        sum += a[i];
        hash[a[i]]++;
    }
    ll q;
    cin >> q;
    pair <ll, ll> b[q+1];
    for(int i = 1; i <= q; ++i){
        cin >> b[i].first >> b[i].second;
        ll ans = hash[b[i].first] * (b[i].second - b[i].first);
        sum += ans;
        hash[b[i].second] += hash[b[i].first];
        hash[b[i].first] = 0;
        cout << sum << endl;
    }
    return 0;
}

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

int main(void){
    int s;
    vector<vector<int> > A(52,vector<int>(3));

    
    for(int i=0;i<52;i++){
        for(int j=0;j<3;j++){
            cin>>A.at(i).at(j);
        }
        if(A.at(i).at(0)==-1 && A.at(i).at(1)==-1 && A.at(i).at(2)==-1 )break;
    }

    for(int i=0;i<52;i++){
        s=A.at(i).at(0)+A.at(i).at(1);
        if(s==-2 && A.at(i).at(2)==-1)break;
        else if(A.at(i).at(0)==-1 || A.at(i).at(1)==-1)cout<<"F"<<endl;
        else if(s>=80)cout<<"A"<<endl;
        else if(s>=65 && s<85)cout<<"B"<<endl;
        else if(s>=50 && s<65)cout<<"C"<<endl;
        else if(s>=30 && s<50){
            if(A.at(i).at(2)>=50)cout<<"C"<<endl;
            else cout<<"D"<<endl;
        }
        else if(s<30)cout<<"F"<<endl;
        s=0;
    }
}



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

int main()
{
	ios::sync_with_stdio(false);
	
	int n,k;
	cin>>n>>k;
	long a=1;
	
	for(int i=0;i<n-1;i++)
		a*=k-1;
	
	long answer=a*k;
	
	cout<<answer<<endl;
	return 0;
}

Measured memory_bytes: 256
from itertools import permutations

N = int(input())
xlist = []
ylist = []

n = 1
for i in range(1, N+1):
    x, y = map(int, input().split())
    xlist.append(x)
    ylist.append(y)
    n *= i

ans = 0
for perm in permutations(range(N)):
    for i in range(N-1):
        x1, y1 = xlist[perm[i]], ylist[perm[i]]
        x2, y2 = xlist[perm[i+1]], ylist[perm[i+1]]
        ans += ((x1 - x2)**2 + (y1 - y2)**2)**0.5 / n

print(ans)

Measured memory_bytes: 9372
#include<cstdio>
int F[45];
int n;
int fibonacci(int n){
	if(n == 0 || n == 1){
		return F[n] = 1;
	}
	if(F[n] != 0){
		return F[n];
	}
	return F[n] = fibonacci(n-2) + fibonacci(n-1);
}

int main(){
	int i;
	for(i=0;i<45;i++){
		F[i] = 0;
	}
	scanf("%d",&n);
	printf("%d\n",fibonacci(n));
	return 0;
}

Measured memory_bytes: 2692
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"

using namespace std;
using namespace __gnu_pbds;


#define ll long long int
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(a) a.begin(),a.end()

typedef tree <ll, null_type, less <ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// order_of_key(val): returns the number of values less than val
// find_by_order(k): returns an iterator to the kth largest element (0-based)

int main(void)
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll h, w, k, i, j, mask, ans = 1e9, cur, prev = 0;
    cin>>h>>w>>k;
    string s[h];
    ll a[h][w];
    for(i = 0; i < h; i++) {
    	cin>>s[i];
    	for(j = 0; j < w; j++) {
    		a[i][j] = s[i][j] - '0';
    	}
    }
    vector<ll> hori;
    for(mask = 0; mask < (1 << (h - 1)); mask++) {
    	hori.clear();
    	for(i = 0; i < (h - 1); i++) {
    		if(mask & (1 << i)) {
    			hori.pb(i);
    		}
    	}
    	cur = hori.size();
    	vector<ll> tot(cur + 1, 0);
    	for(i = 0; i < w; i++) {
    		// for(auto u: tot) {
    		// 	cout<<u<<" ";
    		// }cout<<"\n";
    		ll pos = 0, flag = 0;
    		for(j = 0; j < h;j++) {
    			tot[pos] += a[j][i];
    			if(!hori.empty() && pos != hori.size() && j == hori[pos]) {

    				pos++;
    			}
    		}
    		for(auto u: tot) {
    			if(u > k) {
    				flag = 1;
    				// cout<<mask<<" "<<i<<" "<<u<<"\n";
    			}
    		}
    		if(flag) {
    			if(prev == i) {
    				goto here;
    			}
    			prev = i;
    			cur++;
    			i--;
    			for(j = 0; j < tot.size(); j++) {
    				tot[j] = 0;
    			}
    		}
    	}
    	ans = min(ans, cur);
    	here:;
    }
    cout<<ans<<"\n";
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define mem(a) memset(a,0,sizeof(a))
#define dbg(x) cout<<#x<<" = "<<x<<endl
#define ll long long
int main()
{
	int k;
	cin>>k;
	string s;
	cin>>s;
	if(s.size()<=k)cout<<s;
	else cout<<(s.substr(0,k).c_str())<<"...";
	
	return 0;
}

Measured memory_bytes: 3616
#include "bits/stdc++.h"
#define rep(i,a,n) for(int (i) = (a);(i) < (n);(i)++)

typedef long long ll;
using namespace std;

int main(){
    int e,y;
    cin >> e >> y;
    
    switch(e){
        case 0:
            if(1868 <= y && y <= 1911){
                cout << "M" << y - 1868 + 1 << endl;
            }
            else if(1912 <= y && y <= 1925){
                cout << "T" << y - 1912 + 1 << endl;
            }
            else if(1926 <= y && y <= 1988){
                cout << "S" << y - 1926 + 1 << endl;
            }
            else{
                cout << "H" << y - 1989 + 1 << endl;
            }
            break;
        case 1:
            cout << y + 1868 - 1 << endl;
            break;
        case 2:
            cout << y + 1912 - 1 << endl;
            break;
        case 3:
            cout << y + 1926 - 1 << endl;
            break;
        case 4:
            cout << y + 1989 - 1 << endl;
            break;
    }
}


Measured memory_bytes: 3132
from itertools import combinations
n, d = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]
ans = 0
for xi, xj in combinations(x, 2):
    d = sum((yi - zi) ** 2 for yi, zi in zip(xi, xj))
    l, r = 0, 1001001001
    while r - l > 1:
        c = (l + r) // 2
        if c ** 2 <= d:
            l = c
        else:
            r = c
    if l ** 2 == d:
        ans += 1
print(ans)


Measured memory_bytes: 3064
#include <stdio.h>

int point[101];
int r[101];

int main(void)
{
	int n;
	int i, j;
	int a, b, ap, bp;
	
	scanf("%d", &n);
	
	for (i = 0; i < n * (n - 1) / 2; i++){
		scanf("%d %d %d %d", &a, &b, &ap, &bp);
		if (ap == bp){
			point[a - 1]++;
			point[b - 1]++;
		}
		else if (ap > bp){
			point[a - 1] += 3;
		}
		else {
			point[b - 1] += 3;
		}
	}
	for (i = 0; i < n; i++){
		for (j = 0; j < n; j++){
			if (point[i] < point[j]){
				r[i]++;
			}
		}
		printf("%d\n", r[i] + 1);
	}

	return (0);
}

Measured memory_bytes: 600
#!/usr/bin/env python3
import sys
import math
INF = float("inf")

tol = 1e-6


def solve(N: int, D: int, X: "List[List[int]]"):

    counter = 0
    for i in range(N):
        for j in range(i+1, N):
            dist = 0
            for a, b in zip(X[i], X[j]):
                dist += (a-b)**2
            dist = math.sqrt(dist)
            if abs(dist - round(dist)) < tol:
                counter += 1
    print(counter)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    X = [[int(next(tokens)) for _ in range(D)]
         for _ in range(N)]  # type: "List[List[int]]"
    solve(N, D, X)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 1<<30
#define MOD 1000000007
#define mod 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef long long int LL;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
template<class T> using V=vector<T>;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int ddx[8]={-1,0,1,0,1,1,-1,-1};
int ddy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp(pair<ll,ll>a,pair<ll,ll> b){
        if(a.se!=b.se)
        return a.se<b.se;
        else
        return a.fi<b.fi;
}
//---------------------------------------------------------------------------
bool color[200001];
//---------------------------------------------------------------------------
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    int n,k;string s;
    cin>>n>>s>>k;
    for(int i=0;i<n;i++)
        if(s[i]!=s[k-1])s[i]='*';
    cout<<s<<endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------

/*
ll n;cin>>n;
vector<ll>a(n);
for(ll i=0;i<n;i++)
    cin>>a[i];
 
ll n;cin>>s;
string s;cin>>s;

ll n,m;cin>>n>>m;
vector<ll>a(n),b(m);
for(ll i=0;i<n;i++){
    cin>>a[i];
}
for(ll i=0;i<m;i++){
    cin>>b[i];
}

ll n;cin>>n;
vector<Pll>xy;
for(ll i=0;i<n;i++){
    ll x,y;cin>>x>>y;
    xy.pb({x,y});
}
*/


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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = ((int)(n)-1); i >= 0; i--)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;
 
const int INF = 1e9;
//const ll INF = 1e18;
const double EPS = 1e-10;
const int MOD = 1e9+7;
const double PI = acos(-1.0);

class UnionFind{
private:
	vector<int> par; //�e
	vector<int> sizes; //�f�[�^�̐�

public:
	UnionFind(int n){ 
		par.resize(n);
		sizes.resize(n);
		for(int i = 0; i < n; i++){
			par[i] = i;
			sizes[i] = 1;
		}
	}
	//�؂̍������߂�
	int find(int x){
		if(par[x] == x) return x;
		else return par[x] = find(par[x]);
	}
	//x��y�̑�����W���𕹍�
	void unite(int x,int y){
		x = find(x); //x,y�͊e�f�[�^�̍��m�[�h�𓾂�
		y = find(y);
		if(x == y) return;
		if (sizes[x] < sizes[y]) swap(x,y);
		par[y] = x; //x��y�̐e�ƂȂ�悤�ɘA������
		sizes[x] += sizes[y];
	}
	//x��y�������W���ɑ����邩�ۂ�
	bool same(int x, int y){
		return find(x) == find(y);
	}
	//x��������W���̃f�[�^��
	int size(int x){
		return sizes[find(x)];
	}
};

int main()
{
	int n,m;
	cin >> n >> m;
	vi a(m),b(m);
	rep(i,m){
		cin >> a[i] >> b[i];
		a[i]--,b[i]--;
	}
	UnionFind uni(n);
	vector<ll> ans(m);
	ans[m-1] = (ll)n*(n-1)/2;
	for(int i = m-1; i >= 1; i--){
		ans[i-1] = ans[i];
		if(!uni.same(a[i],b[i])){
			ans[i-1] -= (ll)uni.size(a[i])*uni.size(b[i]);
			uni.unite(a[i],b[i]);
		}
	}
	rep(i,m) cout << ans[i] << endl;
	return 0;
}

Measured memory_bytes: 3712
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define I int
#define GG(x) if(x)printf("-1\n"),exit(0);
const I N=1e6+5;struct G{I o,r;}e[N];I h[N],w=1;void E(I x,I y){e[w]=(G){y,h[x]};h[x]=w++;}I S[N],d[N],K[N],V[N],X,Y,L,T=0,Q[N],P;ll A=0;void D(I u,I f){V[u]=((d[u]&1)?1:-1);P+=V[u];for(I i=h[u];i;i=e[i].r){I v=e[i].o;if(v^f)d[v]?(X=u,Y=v,L=abs(d[u]-d[v])+1):(d[v]=d[u]+1,D(v,u),0);}}void D2(I u,I f){S[u]=V[u];for(I i=h[u];i;i=e[i].r){I v=e[i].o;if(!(v==f||(u==X&&v==Y)||(u==Y&&v==X)))D2(v,u),S[u]+=S[v],K[u]+=K[v];}K[u]?(Q[++T]=K[u]*S[u]):(A+=abs(S[u]));}int main(){I n,m;scanf("%d%d",&n,&m);for(I i=1;i<=m;i++){I x,y;scanf("%d%d",&x,&y),E(x,y),E(y,x);}d[1]=1;D(1,1);if(m==n-1){GG(P)}else if(L&1){GG(P&1)A+=abs(P)/2,V[X]-=P/2,V[Y]-=P/2;}else {GG(P)K[X]++,K[Y]--;}D2(1,1);Q[++T]=0;sort(Q+1,Q+T+1);for(I i=1;i<=T;i++)A+=abs(Q[(T+1)/2]-Q[i]);printf("%lld\n",A);}


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

typedef long long ll;
ll n, a[85], memo[85];
typedef pair<ll, ll> ii;
priority_queue<ii, vector<ii>, greater<ii> > pq;

/*
int dp(int day, int money){
    printf("%d %d\n", day, money);
    if (day == n) return money;
    int tmp = 0;
    for (int i = day; i < n; ++i){
        int profit = (money / a[day]) * (a[i] - a[day]);
        tmp = max(tmp, dp(i + 1, money + profit));
    }
    return memo[day][money] = tmp;
}*/

int main(){
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
    memset(memo, -1, sizeof memo);
    pq.push(ii(1, -1000));
    while (!pq.empty()){
        ll day, money; tie(day, money) = pq.top(); pq.pop();
        //printf("%lld %lld\n", day, money);
        money = - money;
        if (memo[day] != -1) continue;
        memo[day] = money;
        for (int i = day; i <= n; ++i){
            pq.push(ii(i + 1, -(money + (money / a[day]) * (a[i] - a[day]) )));
        }
    }
    ll ans = memo[n + 1];
    printf("%lld", ans);
}


Measured memory_bytes: 3820
N, *A = map(int, open(0).read().split())

ans = [0] * N
for i in range(N):
    ans[0] += (-1) ** i * A[i]
    
for i in range(1, N):
    ans[i] = (A[i - 1] - ans[i - 1] // 2) * 2
    
print(*ans)


Measured memory_bytes: 93132
/*
Though leaves are many , the root is one.
Through all the lying days of my youth
I swayed my leaves and flowers in the sun.
Now I may wither into the truth.
	  	  	- William Butler Yeats
*/
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
#include<bits/stdc++.h>
#define int long long
//#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
const double eps=1e-6;
typedef long long ll;
#ifndef LOCAL
#define cerr if(0)cout
#endif
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
inline string getstr(string &s,int l,int r){string ret="";for(int i=l;i<=r;i++)ret.push_back(s[i]);return ret;}
int n,dp[100005],ans[100005],mod;
vector<int>g[100005];
void dfs(int x,int par){
	dp[x]=1;
	for(int i=0;i<g[x].size();i++){
		int to=g[x][i];
		if(to!=par){
			dfs(to,x);
			dp[x]=dp[x]*(1ll+dp[to])%mod;
		}
	}
}
void calc(int x,int par){
	vector<int>pre,suf;
	for(int i=0;i<g[x].size();i++){
		int to=g[x][i];
		if(to!=par){
			pre.push_back(dp[to]+1);
			suf.push_back(dp[to]+1);
		}
	}
	pre.insert(pre.begin(),1);pre.push_back(1);
	suf.insert(suf.begin(),1);suf.push_back(1);
	for(int i=1;i<pre.size();i++){
		pre[i]*=pre[i-1];pre[i]%=mod;
	}
	for(int i=(int)suf.size()-2;i>=0;i--){
		suf[i]*=suf[i+1];suf[i]%=mod;
	}
	int pos=1;
	for(int i=0;i<g[x].size();i++){
		int to=g[x][i];
		if(to!=par){
			ans[to]=(pre[pos-1]*suf[pos+1]%mod*ans[x]+1)%mod;
			calc(to,x);pos++;
		}
	}
}
signed main(){
	cin>>n>>mod;
	for(int i=1;i<n;i++){
		int x,y;cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1,-1);
	for(int i=1;i<=n;i++)ans[i]=1;
	calc(1,-1);
	for(int i=1;i<=n;i++)cout<<ans[i]*dp[i]%mod<<endl;
	return 0;
}

Measured memory_bytes: 26496
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <cassert>
#include <fstream>
#include <iomanip>
#include <stack>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

const ll mod = 1e9 + 7;
const ll mmod = 998244353;

vector<ll> dx = {1, -1, 0, 0};
vector<ll> dy = {0, 0, 1, -1};

vector<string> g;
vector<vector<bool>> used;
vector<ll> d;

long long ppow(const long long &v, const long long &n, const long long &mod)
{
    long long ret = 1;
    long long num = n;
    long long now = v;
    
    while (num > 0)
    {
        if (num & 1)
        {
            ret = ret * now % mod;
        }
        now = now * now % mod;
        num = num >> 1;
    }
    
    return ret;
}

int main() {
    
    
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    
    ll k;
    string s;
    
    cin >> k >> s;
    
    vector<long long> fac(s.size() + k + 1, 1);
    vector<long long> inv(s.size() + k + 1, 1);
    
    for (int i = 1; i <= s.size() + k; ++i)
    {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = ppow(fac[i], mod - 2ll, mod);
    }
    
    
    ll ret = 0;
    for (int i = s.size(); i <= s.size() + k; ++i)
    {
        ret += ppow(25, s.size() + k - i, mod) * fac[s.size() + k] % mod * inv[i] % mod * inv[s.size() + k - i] % mod;
        ret %= mod;
    }
    
    cout << ret << endl;
    
    return 0;
}

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

int main(){
    long long a=0,b=0,A=0,B=0,ans=0,N=0,x=100000000;
    int i=0;
    cin >> N;
    vector<long long> P(N);
    for(i=0;i<N;i++){
        cin >> P[i];
    }
    for(i=0;i<N;i++){
        if(P[i]<=x){
            ans++;
            x = P[i];
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;

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

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

ll N;
vector<ll> a(3),b(3);

const int MAX = 30000000;
ll dp[MAX];

ll calc(vector<ll> sei, vector<ll> obj, ll M){
    memset(dp,0,sizeof(dp));
    REP(i,sei.size()){
        for(int v=0;v+sei[i]<=M;++v){
            chmax(dp[v+sei[i]],dp[v]+obj[i]);
        }
    }
    ll res = M;
    for(int v=0;v<=M;++v) chmax(res,dp[v] + M - v);
    return res;
}

ll solve(){
    N = calc(a,b,N);
    N = calc(b,a,N);
    return N;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>N;
    REP(i,3) cin>>a[i];
    REP(i,3) cin>>b[i];
    cout << solve() << endl;
}


Measured memory_bytes: 234752
#include <stdio.h>
#include <vector>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<vs> vvs;

typedef vector<pair<int, int>> vpi;
typedef vector<tuple<int, int, int>> vti;


int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int a, b, c;
    cin >> a >> b >> c;
    cout << max(0, c - (a - b)) << endl;
}


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

ll solve(ll N, ll K) {
  ll cnt1, cnt2, ans;

  if (K % 2 == 1) {
    cnt1 = N / K;
    ans = cnt1 * cnt1 * cnt1;
  } else {
    cnt1 = N / K;
    cnt2 = N / (K / 2) - cnt1;
    ans = cnt1 * cnt1 * cnt1 + cnt2 * cnt2 * cnt2;
  }
  return ans;
}

int main() {
  ll N, K;
  cin >> N >> K;
  cout << solve(N, K) << "\n";
  return 0;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (N, M) = readLine()!!.split(" ").map { it.toLong() }
    when (N - M) {
        0L -> println(factorial(N) * factorial(M) * 2 % mod)
        1L, -1L -> println(factorial(N) * factorial(M) % mod)
        else -> println(0)
    }
}

val mod = 1000000007

fun factorial(n: Long): Long = if (n == 1L) 1 else n * factorial(n - 1) % mod

Measured memory_bytes: 41012
import math
from collections import deque
def main():
    s = input()
    if(len(s)%2!=0):
        print("No")
        return

    for i,c in enumerate(s):
        if i%2==0:
            if c!='h':
                print("No")
                return
        else:
            if c!='i':
                print("No")
                return

    print("Yes")


if __name__ == "__main__":
    main()

Measured memory_bytes: 3316
// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>  
#include <cmath>
#include <map>
#define re register
using namespace std;
typedef long long ll;

inline ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,L=2155+10;

int n; ll a[N],x[N],y[N];
map<ll,int> o,vis;

int v[N],p[N],cnt=0;
inline void sieve(int n) {
    for (re int i=2;i<=n;++i)  {
        if (!v[i]) p[++cnt]=i;
        for (re int j=1;j<=cnt&&i*p[j]<=n;++j) {
            v[i*p[j]]=1;
            if (i%p[j]==0) break;
        }
    }
}

int main() { sieve(2155);
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=n;++i) {
        x[i]=y[i]=1;
        for (re int j=1;j<=cnt;++j) {
            if (a[i]%p[j]==0) { int c=0;
                while (a[i]%p[j]==0) ++c,a[i]/=p[j];
                if (c%3==1) x[i]*=p[j],y[i]*=p[j]*p[j];
                if (c%3==2) x[i]*=p[j]*p[j],y[i]*=p[j];
                if (a[i]==1) break;
            }
        }
        if (a[i]>1) {
            ll r=sqrt(a[i]);
            if (r*r==a[i]) x[i]*=r*r,y[i]*=r;
            else x[i]*=a[i],y[i]*=a[i]*a[i];
        }
    }
    int ans=0,flag=0;
    for (re int i=1;i<=n;++i) ++o[x[i]];
    for (re int i=1;i<=n;++i) {
        if (vis[x[i]]) continue;
        if (x[i]==1) flag=1;
        else ans+=max(o[x[i]],o[y[i]]),vis[x[i]]=vis[y[i]]=1;
    }
    printf("%d\n",ans+flag);
    return 0;
}


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

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

template <typename T1, typename T2>
bool chmin(T1& a, const T2& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool chmax(T1& a, const T2& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

class Prints {
private:
    class __Prints {
    public:
        __Prints(const char* sep, const char* term) : sep(sep), term(term) {}
        template <class... Args>
        void operator()(const Args&... args) const { print(args...); }

    private:
        const char *sep, *term;
        void print() const { std::cout << term; }
        void print_rest() const { std::cout << term; }
        template <class T, class... Tail>
        void print(const T& head, const Tail&... tail) const { std::cout << head, print_rest(tail...); }
        template <class T, class... Tail>
        void print_rest(const T& head, const Tail&... tail) const { std::cout << sep << head, print_rest(tail...); }
    };

public:
    Prints() {}
    __Prints operator()(const char* sep = " ", const char* term = "\n") const { return __Prints(sep, term); }
};

Prints prints;

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

ll dp[100010][2];

void solve() {
    ll N;
    cin >> N;
    Vl A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }

    for (ll i = 0; i <= N - 1; i++) {
        dp[i][0] = dp[i][1] = -L_INF;
    }
    dp[0][0] = 0;

    for (ll i = 0; i < N - 1; i++) {
        if (dp[i][0] != -L_INF) {
            chmax(dp[i + 1][0], dp[i][0] + A[i]);
            chmax(dp[i + 1][1], dp[i][0] - A[i]);
        }
        if (dp[i][1] != -L_INF) {
            chmax(dp[i + 1][0], dp[i][1] - A[i]);
            chmax(dp[i + 1][1], dp[i][1] + A[i]);
        }
    }

    ll ans = -L_INF;
    chmax(ans, dp[N - 1][0] + A[N - 1]);
    chmax(ans, dp[N - 1][1] - A[N - 1]);
    prints()(ans);
}

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

int main() {
#ifdef FASTIO
    cin.tie(nullptr), cout.tie(nullptr);
    ios::sync_with_stdio(false);
#endif
#ifdef FILEINPUT
    ifstream ifs("./in_out/input.txt");
    cin.rdbuf(ifs.rdbuf());
#endif
#ifdef FILEOUTPUT
    ofstream ofs("./in_out/output.txt");
    cout.rdbuf(ofs.rdbuf());
#endif
    cout << setprecision(18) << fixed;
    solve();
    cout << flush;
    return 0;
}

Measured memory_bytes: 5568
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

n,k = ip()
x = ip()
for i in range(k,n):
    if x[i] > x[i-k]:
        print('Yes')
    else:
        print("No")


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

#define int long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x) cout << #x << " = " << (x) << endl;
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define SP << " " <<

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
typedef vector<int> vec;
typedef vector<P> pvec;
typedef vector<vector<int>> vvec;
typedef vector<vector<P>> pvvec;
typedef priority_queue<int> PQI;
typedef priority_queue<P> PQP;
typedef priority_queue<int,vector<int>,greater<int>> PQIG;
typedef priority_queue<P,vector<P>,greater<P>> PQPG;

const vector<int> DX = {0, -1, 0, 1, 1, 1, -1, -1};
const vector<int> DY = {1, 0, -1, 0, 1, -1, 1, -1};
constexpr int MOD = (1000000007);
// const int MOD = (998244353);
// const int INF = (1 << 30); // 1073741824
const ll INF = (1LL << 60); // 1152921504606846976
const double PI = (3.141592653589794);
const double EPS = (0.0000000001); // 10^(-10)

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}
template<class T> inline T ceil(T a, T b) {return T((a + b - 1) / b);}
template<class T> inline T round(T a, T b) {return T(a / b);}
template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; }
template <class T> inline void out(T &a) { bool flag=true; for(auto&x:a){if(flag) {flag=false;} else{ cout << ' '; } cout<<x; } cout << endl; }



//----------------------------------------------------------------
int nmax=200000; // 2*(10^5)
vvec G(nmax);





void solve4ts()
{
    
    vector<bool> pri(1000000+100,true);

    for(int i=2;i<1000000+100;i++){
        if(pri[i]){
            for(int j=i*2;j<1000000+100;j+=i){
                pri[j]=false;
            }
        }
    }
    
    int n;
    cin>>n;
    int ans=0;
    if(n==1){
        cout<<0<<endl;
        return;
    }
    for(int i=2;i<1000000+50;i++){
        int cnt=0;
        while(n%i==0){
            n/=i;
            cnt++;
        }
        int hiku=1;
        while(cnt>=hiku){
            cnt-=hiku;
            hiku++;
            ans++;
        }
    }
    if(n!=1) ans++;
    cout<<ans<<endl;
}
//-----------------------------------------------------------------

signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(15);
    int repeat = 1;
    // cin >> repeat;
    while(repeat--) solve4ts();
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;

static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const ll INF = 1023456789;

#define REP(i,n)	for(int i=0;i<n;++i)
#define REPR(i,n)	for(int i=n-1;i>=0;--i)
#define FOR(i,s,n)	for(int i=s;i<n;++i)
#define FORR(i,s,n)	for(int i=n-1;i>=s;--i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define F			first
#define S			second

ll n, a[200000];
bool t[1000001];

int main(int argc, char **argv) {
	CLEAR(t);
	cin >> n;
	set<ll> s, d;
	REP(i, n) {
		cin >> a[i];
		if (s.count(a[i]) != 0) d.insert(a[i]);
		s.insert(a[i]);
	}
	if (s.count(1) != 0) {
		cout << (d.count(1) != 0 ? 0 : 1) << endl;
		return 0;
	}
	FOR(i, 2, 1000001) if (!t[i] && s.count(i) != 0) {
		for (ll b = 2*i; b < 1000001; b += i) t[b] = true;
	}
	ll res = 0;
	REP(i, n) if (!t[a[i]] && d.count(a[i]) == 0) ++res;
	cout << res << endl;
	return 0;
}


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

ll gcd(ll x,ll y) {return y ? gcd(y,x%y) : x;} 
ll lcm(ll x,ll y) {return x/gcd(x,y)*y;}


int main(){
    ll x,y,ans=0;
    cin >> x >> y;
    while(x<=y){
        ans++;
        x*=2;
    }
    cout << ans << endl;
    
    return 0;
}











Measured memory_bytes: 256
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
for i in range(1, 10):
  for j in range(1, 10):
    if i * j == N:
      print("Yes")
      exit()
print("No")



Measured memory_bytes: 5780
#include <iostream>
#include <vector>
#include <string>
#include <cctype>
#include<algorithm>
using namespace std;
vector<char> s;
int dp[3001][3001];


void printLcs(string x,string y,int m,int n){
     for(int i=0;i<=m;i++){
        for(int j=0;j<=n;j++){
            if(i==0||j==0){
                dp[i][j]=0;
            }
            else if(x[i-1]==y[j-1]){
                dp[i][j]=1+dp[i-1][j-1];
            }
            else{
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
     }
    //int dp[m+1][n+1];
    //vector<string> s;
        int i=m;
        int j=n;
        string res="";
        while(i>0&&j>0){
               
                
                    if(dp[i][j]==dp[i][j-1]){
                        j--;
                    }
                    else if(dp[i][j]==dp[i-1][j]){
                        i--;
                    }
              else{
                    //cout<<x[i-1];
                    //cout<<ch;
                    //s.push_back(x[i-1]);
                    res=x[i-1]+res;
                    i--;
                    j--;

                }
               
        }
            
        
       // reverse(s.begin(),s.end());
        //for(auto x: s){
           // cout<<x;
        //}
        cout<<res;
        
    }

int main() {
   string x;
   string y;
   cin>>x;
   cin>>y;
   int m=x.length();
   int n=y.length();
   printLcs(x,y,m,n);
}


Measured memory_bytes: 38872
#include <stdio.h>
#define MAX(A, B) (((A) < (B)) ? (B) : (A))
#define MIN(A, B) (((A) < (B)) ? (A) : (B))
#define ABS(A) (((A) < 0 ) ? (0 - A) : (A))

int lett(char a, char b, char c) {
  int d = (a-'0')*100 + (b-'0')*10 + (c-'0');
  return d;
}

int main() {
  char a[10];
  scanf("%s", &a);
  int b = 753;
  int c = 0;
  int i=0;
  
  while (a[i+2] != 0) {
    c = lett(a[i], a[i+1], a[i+2]);
    c = 753 - c;
    c = ABS(c);
    b = MIN(b, c);
    i++;
  }
  printf("%d\n", b);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <time.h>
using namespace std;
typedef long long ll;
bool x[110], y[110];
int main() {
	ll n, a, b;
	cin >> n >> a >> b;
	if (a > b||(n==1&&a!=b)) {
		cout << 0 << endl;
		system("PAUSE");
		return 0;
	}
	else if (n == 1) {
		cout << 1 << endl;
		system("PAUSE");
		return 0;
	}
	if (n == 2) {
		cout << 1 << endl;
		system("PAUSE");
		return 0;
	}
	cout << (b*(n - 1) + a) - (a*(n - 1) + b) + 1 << endl;
	system("PAUSE");
	return 0;
}


Measured memory_bytes: 504
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) begin(x), end(x)
using namespace std;
using ll = long long;
template <typename T> using V = vector<T>;
constexpr int Mod = 998244353;
constexpr int mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;
template <typename T> constexpr bool chmax(T &a, const T &b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <typename T> constexpr bool chmin(T &a, const T &b) {
    if(a <= b) return false;
    a = b;
    return true;
}

/*-------------------------------------------*/

int cnt[2020];

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

    string s;
    cin >> s;
    int x = 0;
    int y = 1;
    reverse(ALL(s));
    cnt[0]++;
    for(auto &&c : s) {
        x += y * (c - '0');
        cnt[x %= 2019]++;
        y *= 10;
        y %= 2019;
    }
    ll ans = 0;
    rep(i, 2019) { ans += 1LL * cnt[i] * (cnt[i] - 1) / 2; }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3748
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n,x;
    cin>>n>>x;
    ll a[n];
    ll sum=0,min=1001;
    for(ll i=0; i<n; i++){cin>>a[i]; sum+=a[i]; if(a[i]<min){min=a[i];}}
    ll diff = x-sum;
    ll ans = n;
    ans = ans + (diff/min);
    cout<<ans<<"\n";
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <climits>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <functional>

using namespace std;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	string s;
	cin >> s;
	sort(s.begin(), s.end());

	if (s[0] == s[1] && s[2] == s[3] && s[0] != s[2])
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	

	return 0;
}

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

int main() {
    int H,N;
    cin >> H >> N;

    int total = 0;
    rep(i, N){
        int A;
        cin >> A;
        total += A;
    }

    if (total >= H)cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        int t = sc.nextInt();
        System.out.println(((n + x - 1) / x) * t);
        sc.close();
    }
}

Measured memory_bytes: 35684
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = Integer.parseInt(sc.next());
		int B = Integer.parseInt(sc.next());
		
		int ans = 0;
		int kuchi = 1;
		
		while(kuchi < B) {
			kuchi += A-1;
			ans++;
			//System.out.println(kuchi);
			//System.out.println(ans);
			//System.out.println("---");
		}
		
		System.out.println(ans);
		
		
	}

}


Measured memory_bytes: 21716