akhauriyash/Code-Regression huggingface dataset:
INF=1e8
path=[]
dp=[]
while(True):
    try:
        temp=list(map(int,input().split(',')))
        path.append(temp)
        dp.append([INF for i in range(len(temp))])
    except:
        break
dp[0][0]=path[0][0]
for i in range(1,len(dp)):
    for j in range(len(dp[i])):
        if len(dp[i])>len(dp[i-1]):
            start=0 if j-1<0 else j-1
            dp[i][j]=max(dp[i-1][start:j+1])+path[i][j]
        else:
            dp[i][j]=max(dp[i-1][j:j+2])+path[i][j]
print(dp[-1][-1])


Measured memory_bytes: 5732
#include <stdio.h>

int main(void) {

  int N, K;
  do {
    scanf("%d %d", &N, &K);
  } while (N < 1 || N > 50 || K < 1 || K > N);

  char S[N];
  scanf("%s", S);

  if (S[K - 1] == 'A') {
    S[K - 1] = 'a';
  } else if (S[K - 1] == 'B') {
    S[K - 1] = 'b';
  } else if (S[K - 1] == 'C') {
    S[K - 1] = 'c';
  }

  printf("%s\n", S);

  return 0;
}

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

const ll mod = 1e9+7;

ll factorial(ll x) {
  ll ans = 1;
  for (int i = 2; i <= x; ++i) {
    ans = (ans * i) % mod;
  }
  return ans;
}

int main()
{
  int N, M; cin >> N >> M;
  if (N == M) {
    ll fact = factorial(N);
    cout << (2*fact*fact)%mod << endl;
  } else if (abs(N-M) == 1){
    ll fact1 = factorial(min(N, M));
    ll fact2 = factorial(max(N, M));
    cout << (fact1*fact2)%mod << endl;
  } else {
    cout << 0 << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define N 100000
 
int Partition(int [], int, int);

int main(void){
  int n,i,a[N],q;

  scanf("%d",&n);
  for(i = 1; i < n+1; i++){
    scanf("%d",&a[i]);
  }

  q = Partition(a,1,n);

  for(i = 1; i < n; i++){
    if(i == q){
      printf("[%d] ",a[i]);
    }else{
      printf("%d ",a[i]);
    }
  }
  
  printf("%d\n",a[i]);

  return 0;
}

int Partition(int A[], int p, int r){
  int x,i,j,tmp;

  x = A[r];
  i = p - 1;

  for(j = p; j <= r-1; j++){
    if(A[j] <=  x){
      i =  i + 1;
      tmp = A[i];
      A[i] = A[j];
      A[j] = tmp;
    }
  }
  tmp = A[i+1];
  A[i+1] = A[r];
  A[r] = tmp;

  return i+1; 
}

Measured memory_bytes: 988
#include <bits/stdc++.h>
using namespace std;
int main() {
  string A,B,C;
  cin >> A >> B >> C;
  
  if (A.at(A.size()-1) == B.at(0) && B.at(B.size()-1) == C.at(0)){
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 3632
#pragma region Template
#include <bits/stdc++.h>
using namespace std;
struct ios_accelerate { ios_accelerate() { ios::sync_with_stdio(false); cin.tie(nullptr); } } CALL;

#define REP(i, n) for(int i = 0; i < n; i++)
#define RNG(i, a, b) for(int i = a; i < b; i++)
#define RBF(i, v) for(auto& i : v)
#define ALL(x) x.begin(), x.end()

using LL = long long;
using UL = unsigned long;
using ULL = unsigned long long;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
template<typename T> using P = pair<T, T>;
template<typename T> using VP = vector<pair<T, T>>;

const double PI = 3.141592653589793;
const int MOD = 1000000007;
const LL INF64 = static_cast<LL>(1e18) + 2;
const int INF = static_cast<int>(1e9) + 2;

template<typename T> inline void upsort(vector<T>& x) { sort(x.begin(), x.end()); }
template<typename T> inline void downsort(vector<T>& x) { sort(x.begin(), x.end(), greater<T>()); }
template<typename T> inline void col(T x) { cout << x << '\n'; }
template<> inline void col(double x) { cout << fixed << setprecision(12) << x << '\n'; }
#pragma endregion

signed main()
{
    V<int> x(5);
    RBF(xi, x) cin >> xi;

    int i = 1;
    RBF(xi, x) {
        if (xi == 0) {
            col(i);
            break;
        }
        i++;
    }
    return 0;
}


Measured memory_bytes: 3636
#include <stdio.h>
int main(void) {
    int n;
    long long int a0=2, a1=1, a2=1;
    scanf("%d", &n);
    for(int i=2; i<=n; i++) {
        a2=a0+a1;
        a0=a1;
        a1=a2;
    }
    
    printf("%lld", a2);
    return 0;
}


Measured memory_bytes: 128
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

n = readint()

print(sum([k*(n//k)*(n//k+1)//2 for k in range(1,n+1)]))

Measured memory_bytes: 224248
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define _USE_MATH_DEFINES
#include <math.h>
#define rep(i,n) for(int i = 0;i < n;i++)
#define NIL = -1;
#define all(x) x.begin(),x.end()
const ll INF = 1e9;
const ll mod = 1e9 + 7;

int digit(ll x) {
    if (x / 10 == 0) return 1;
    return digit(x / 10) + 1;
}

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

ll lcm(ll a,ll b){
    return ((a * b == 0)) ? 0 : (a / gcd(a,b) * b);
}

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


//////////////////////////////////////////////////////////////////////////////////////b,cl

int main(){
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1;i <= n;i += 2){
        int count = 0;
        for(int j = 1;j <= i;j++){
            if (i % j == 0){
                count++;
            }
        }
        if (count == 8){
            ans++;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3624
#include<stdio.h>
#define N 100

int main(){

  int i,j,n,tmp,count=0,a[N];

  scanf("%d",&n);

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

    scanf("%d",&a[i]);
  }
  for(i=0;i<n;i++){
    for(j=n-1;j>i;j--){
      if(a[j]<a[j-1]){
	tmp=a[j-1];
	a[j-1]=a[j];
	a[j]=tmp;
	count++;
      }
    }
  }
  printf("%d",a[0]);

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

    printf(" %d",a[i]);
  }
  printf("\n%d\n",count);

  return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cstdio>

using namespace std;

int query(const vector<char>& vc){
    cout << "? ";
    for(auto& c : vc) cout << char(c);
    cout << endl;
    int q; cin >> q;
    return q;
}

int main(){
    vector<char> vc;
    for(int i=0;i<10;i++) vc.push_back('0'+i);
    for(int i=0;i<26;i++) vc.push_back('a'+i);
    for(int i=0;i<26;i++) vc.push_back('A'+i);

    int L = 0;
    auto cmp = [](const vector<char>& a, const vector<char>& b){ return a.size() > b.size(); };
    priority_queue<vector<char>, vector<vector<char>>, decltype(cmp)> qu(cmp);
    for(int i=0;i<vc.size();i++){
        vector<char> cur(128, vc[i]);
        int q = query(cur);
        if(q == 128) continue;
        qu.push(vector<char>(128-q, vc[i]));
        L += 128 - q;
    }
    while(qu.size() >= 2){
        auto a = qu.top(); qu.pop();
        auto b = qu.top(); qu.pop();
        swap(b, a);
        int idx = 0;
        int cur = L - a.size();
        for(int i=0;i<b.size();i++){
            a.push_back(b[i]);
            for(int j=a.size()-2;j>=idx;j--) swap(a[j], a[j+1]);
            while(true){
                ++idx;
                if(idx == a.size()) break;
                int q = query(a);
                if(q == L - a.size()) break;
                swap(a[idx-1], a[idx]);
            }
        }
        qu.push(a);
    }
    auto res = qu.top();
    cout << "! ";
    for(auto& c : res) cout << char(c);
    cout << endl;
}


Measured memory_bytes: 3800
n = int(input())
# for i in range(n):
#     print('0', end='')
# print(flush=True)
s = input()
x = int(s, base=2)
popcount = s.count('1')
y_zero = x % (popcount + 1)
if popcount > 1:
    y_one = x % (popcount - 1)
dp = [-1] * n
dp[0] = 0


def calc(y):
    if dp[y] != -1:
        return dp[y]
    dp[y] = 1 + calc(y % bin(y).count('1'))
    return dp[y]


ans = [0] * n
rem_zero = 1
if popcount > 1:
    rem_one = popcount - 2
for i in range(n):
    if s[n - 1 - i] == '0':
        ans[n - 1 - i] = 1 + calc((y_zero + rem_zero) % (popcount + 1))
    elif popcount > 1:
        ans[n - 1 - i] = 1 + calc((y_one + rem_one) % (popcount - 1))
    else:
        ans[n - 1 - i] = 0
    rem_zero = rem_zero * 2 % (popcount + 1)
    if popcount > 1:
        rem_one = rem_one * 2 % (popcount - 1)
for i in range(n):
    print(ans[i])

Measured memory_bytes: 12540
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mii map <int, int>
#define mll map <ll, ll>
#define pii pair <int, int>
#define pll pair <ll, ll>
#define vi vector <int>
#define vd vector <double>
#define vll vector <ll>
#define fi first
#define se second
#define si set <int>
#define sll set <ll>
#define spii set <pii>
#define vs vector <string>
#define vpii vector <pair <int,int> >
#define vpll vector <pair <long long,long long> >
#define vvi vector <vector <int> >
#define vvpii vector <vector <pii > >
#define mp make_pair
#define vvll vector <vll>
#define vsi vector <si>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define MANX MAXN
#define itn int
#define in(x); { for (auto &to : x) cin>>to;}
#define out(x); { for (auto &to : x) cout<<to<<" ";cout<<'\n'; }

const ll INFLL = 1e18;
const int MAXN = 1e6+100;
const ll INF = 1e9;
const ll mod1=1e9+7;
const ll mod2=2e9+11;


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef Mip182
    freopen("a.in","r",stdin);
    #endif
    int k;
    cin>>k;
    ll sum=0;
    ll x=1;
    for (int i=1;i<=2*k;i++)
    {
        sum=(sum*10)%k;
        sum=(sum+7)%k;
        if (sum==0)
        {
            cout<<i;
            return 0;
        }
    }
    cout<<-1;


    //n=1 ?
    //recursion - matrix exponential
    //linear algebra - just a joke
    //check ios_base, MAXN, mod1 before submit
    //if debug more than 15 minutes - write stress
    //compression
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ for(auto it : P) { s << "<" << it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s << endl; }


using Edge = pair<int, long long>;
using Graph = vector<vector<Edge>>;
int N;
Graph G;

long long rec(int v, int p, long long &ans) {
    vector<long long> chs;
    for (auto e : G[v]) {
        if (e.first == p) continue;
        chs.push_back(rec(e.first, v, ans) + e.second);
    }
    sort(chs.begin(), chs.end(), greater<long long>());
    if (chs.size() == 0) return 0;
    else if (chs.size() == 1) chmax(ans, chs[0]);
    else chmax(ans, chs[0] + chs[1]);
    return chs[0];
}

int main () {
    while (cin >> N) {
        G.assign(N, vector<Edge>());
        for (int i = 0; i < N-1; ++i) {
            int u, v;
            long long w;
            cin >> u >> v >> w;
            G[u].push_back({v, w});
            G[v].push_back({u, w});
        }
        long long ans = 0;
        rec(0, -1, ans);
        cout << ans << endl;
    }
}   
    



Measured memory_bytes: 20680
import java.util.Scanner;
import java.util.function.LongSupplier;
import java.util.stream.IntStream;

public class Main{
	static final Scanner s=new Scanner(System.in);
	static final long[] fal_rnd(long[] ar,LongSupplier sp){
		int l=-1,r=ar.length;
		while(l+1!=r)
			ar[Math.random()<0.5?++l:--r]=sp.getAsLong();
		return ar;
	}
	static final IntStream REPS(int v){return IntStream.range(0, v);};
	public static void main(String[] __){
		int n;
		while ((n=s.nextInt())!=0) {
			int l=1,r=2,c=0;
			while (l*2+1<=n) {
				final int v=(l+r)*(r-l+1)/2;
				if(v==n) c++;
				if(v>=n) l++;
				if(v<n) r++;
			}
			System.out.println(c);
		}
	}
}

Measured memory_bytes: 26320
import java.util.Scanner;

public class Main {
	public static void main(String[]args) {
		try(Scanner scan = new Scanner(System.in)){

			int N = scan.nextInt();

			long[]A = new long[N];
			long[]B = new long[N];

			for(int i = 0;i<N;i++) {
				A[i] = scan.nextLong();
				B[i] = scan.nextLong();
			}


			long count = 0;

			for(int i = N-1;i>=0;i--) {
				A[i]+=count;
				long s=0;
				if(A[i]%B[i]!=0)
				 s = B[i]-A[i]%B[i];
				count+=s;
			}

			System.out.println(count);


		}


	}


}


Measured memory_bytes: 61136
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define repreverse(i, start, end) for (long long i = start; i >= end; --i)
#define all(x) (x).begin(), (x).end()
#define len(x) ((long long)(x).size())
#define g(a, b) __gcd((a), (b))
#define l(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
using pll = pair<ll, ll>;
template<class T>void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T>void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
template<class T, class U>bool haskey(T mp, U key) { return mp.find(key) != mp.end(); }
template<class T, class U>bool isin(T el, U container) { return find(all(container), el) != container.end(); }
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; }
template<class T>ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T>ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;



int main()
{
        ll N, K;
        cin >> N >> K;
        vector<pll> p(N);
        rep(i, 0, N) cin >> p[i].first >> p[i].second;
        sort(all(p));

        ll ans = inf;
        rep(i, 0, N) {
                if (K > p[i].second) {
                        K -= p[i].second;
                } else {
                        ans = p[i].first;
                        break;
                }
        }
        cout << ans << endl;
}

Measured memory_bytes: 1792
#include<iostream>
#include<functional>
#include<vector>
#include<vector>
#include<utility>
#include<cmath>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
using ll =long long;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define all(i) i.begin(),i.end()
template<typename T=ll>
using v =vector<T>;
template<typename T=ll>
using vv = vector<v<T>>;
template<typename T=ll,typename U=ll> using p = pair<T,U>;
const ll INF = (ll)1e9;
const ll MOD = INF+7;
template<typename T> T chmin(T &a,T b){a=min(a,b);}
template<typename T> T chmax(T &a,T b){a=max(a,b);}

void b(){
    ll k,t;
    cin >> k >> t;
    v<> a(t,0LL);
    rep(i,t){
        cin >> a[i];
    }
	
    sort(a.begin(),a.end());
    while(1){
        auto it = upper_bound(a.begin(),a.end(),0LL);
        if(it==a.end()-1)break;
      	if(it==a.end()) break;
        a[t-1] -=*it;
        *it=0;
        sort(a.begin(),a.end());
    }
    cout << max(0LL,a[t-1]-1) <<endl;

}

int main(){
    b();
}

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

int main() {
  long long int a,b;
  scanf("%lld %lld",&a,&b);
  char p[a+b+1];
  scanf("%s",p);
  long long int i;
  long long int check = 0;
  for(i=0;i<a;i++) {
    if(p[i]=='-') {
      check = 1;
      goto LABEL;
    }
  }
  i = a;
  if(p[i]!='-') {
    check = 1;
    goto LABEL;
  }
  for(i=a+1;i<a+b+1;i++) {
    if(p[i]=='-') {
      check = 1;
      goto LABEL;
    }
  }
  LABEL:
  if (check == 0) {
    printf("Yes\n");
  } else {
    printf("No\n");
  }
  return 0;
}


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

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

long long MOD = 1000000000 + 7;

int main(){
  cout << setprecision(10);
  int K;
  cin >> K;
  int A,B;
  cin >> A >> B;
  bool flg = false;
  for(int i = A; i <= B; i++){
    if(i%K == 0){
      flg = true;
      break;
    }
  }
  cout << (flg ? "OK" : "NG") << endl;
}


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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  double n, a, b, ans = 1000000000.00;
  cin >> n;
  for (a = 1; a*a <= n; a++) {
    if ((double)fmod(n,a) != 0.0) continue;    
    b = n/a;
    b = max(a, b);
    ans = min(ans, b);
  }
  string s = to_string((int)ans);
  cout << s.size() << '\n';
}


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

int main(){
    int n,k,cnt = 0,N;
    cin >> n >> k;
    N = n;

    while(1){
        n = n / k;
        cnt++;
        if(n < k){
            cnt++;
            break;
        }
    }

    if(N < k) {cout << 1 <<endl;}
    else {cout << cnt << endl;}

}

Measured memory_bytes: 256
import math

n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

m = [abs(x[i] - y[i]) for i in range(n)]
m_d = sum(m)

m2 = [abs(x[i] - y[i]) ** 2 for i in range(n)]
m_u= math.sqrt(sum(m2))

m3=[abs(x[i] - y[i]) ** 3 for i in range(n)]
m_3= (sum(m3))**(1/3)

mi= [abs(x[i] - y[i]) for i in range(n)]
m_c=max(mi)

print('{:.6f}'.format(m_d))
print('{:.6f}'.format(m_u))
print('{:.6f}'.format(m_3))
print('{:.6f}'.format(m_c))


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

using namespace std;

#define int long long

int n;
int id;
deque<int>S1,S2;
void Dfs(int x){
	if(x == 1)return;
	Dfs(x >> 1);
	id++;
	S1.push_front(id);
	S2.push_front(id);
	if(x & 1){
		id++;
		S1.push_back(id);
		S2.push_front(id);
	}
}
signed main(){
#ifdef Sirius
	freopen("in","r",stdin);
#endif 
	cin >> n;
	Dfs(n + 1);
	cout << S1.size() + S2.size() << endl;
	while(S1.size())cout << S1.front() << " ",S1.pop_front();
	while(S2.size())cout << S2.front() << " ",S2.pop_front();
	cout << endl;
	return 0;
}


Measured memory_bytes: 256
N,X,D=map(int,input().split())
r=N*(X!=0)+1
if D:
 f,c,r={},[0]*abs(D),0
 for x,y,z in sorted(((N-k)*k*j+~-k*k//2+k*X//D,j,k*X%D)for k in range(N+1) for j in[0,1]):
  if c[z]<2*y:
    r+=(x-f[z]+1)*(c[z]<2)*y
  if c[z]+y<1:
   f[z]=x
  c[z]-=2*y-1
print(r)

Measured memory_bytes: 887772
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <numeric>
#include <limits>
using namespace std;


int main(){
    int w, h, n;
    cin >> w >> h >> n;
    int xy[w][h] = {};
    int x, y, a;
    for(size_t i = 0; i < n; i++)
    {
        cin >> x >> y >> a;
        if(a == 1){
            for(size_t i = 0; i < x; i++)
            {
                for(size_t j = 0; j < h; j++)
                {
                    xy[i][j] = 1;
                }
            }
        }
        else if(a == 2){
            for(size_t i = x; i < w; i++)
            {
                for(size_t j = 0; j < h; j++)
                {
                    xy[i][j] = 1;
                }
            }
        }
        else if(a == 3){
            for(size_t i = 0; i < w; i++)
            {
                for(size_t j = 0; j < y; j++)
                {
                    xy[i][j] = 1;
                }
            }
        }
        else if(a == 4){
            for(size_t i = 0; i < w; i++)
            {
                for(size_t j = y; j < h; j++)
                {
                    xy[i][j] = 1;
                }
            }
        }
    }
    int ans = 0;
    for(size_t i = 0; i < w; i++)
    {
        for(size_t j = 0; j < h; j++)
        {
            if(xy[i][j] == 0) ans ++;
         }
        
    }
    
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<set>
#include<iomanip>
#define pi 3.14159265358979323846
#define ill long long int
#define rep(i, a, n) for(int i = a; i < n; i++)
using namespace std;
int main(){
  ill a, b, c;
  cin >> a >> b >> c;
  a += b;
  if(a >= c){
    cout << "Yes\n";
    return 0;
  }
  cout << "No\n";
}

Measured memory_bytes: 3656
#include<bits/stdc++.h>
using namespace std;
#define M 200005
vector<int>d[M];
int ln[M],rn[M],dfn,n,sum[M],q;
void dfs(int x,int f){
	ln[x]=++dfn;
	for(int i=0;i<(int)d[x].size();++i){
		int v=d[x][i];
		if(v==f)continue;
		dfs(v,x);
	}rn[x]=dfn;
}
void update(int x,int w){
	for(;x<=n;x+=x&-x)sum[x]+=w;
}
int query(int x){
	int ans=0;
	for(;x;x-=x&-x)ans+=sum[x];
	return ans;
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1,x,y;i<n;++i){
		scanf("%d%d",&x,&y);
		d[x].push_back(y);
		d[y].push_back(x);
	}dfs(1,0);
	for(int i=1,p,w;i<=q;++i){
		scanf("%d%d",&p,&w);
		update(ln[p],w);
		update(rn[p]+1,-w);
	}
	for(int i=1;i<=n;++i)printf("%d ",query(ln[i]));
}

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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;

using ll = long long;
using ull = unsigned long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;
template<class T,class U> using umap = unordered_map<T,U>;
template<class T> using uset = unordered_set<T>;

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

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

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v)is >> e;
  return is;
}

int Sum(const string&s){
  int n = (int)s.size();
  int sum = 0;
  for(int i = 0; i < n; ++i)sum += s[i] - '0';
  return sum;
}

int main(){
  double a,b; cin >> a >> b;
  cout << b + (b-a) << endl;
}


Measured memory_bytes: 3744
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1<<29;
const int MOD = 1e9+7;
const ll LINF = 1e18;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    REP(i,v.size()){if(i)os<<" ";os<<v[i];}return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
    REP(i,v.size()){if(i)os<<endl;os<<v[i];}return os;}

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

const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};

const int dx8[8] = {1,1,0,-1,-1,-1,0,1};
const int dy8[8] = {0,1,1,1,0,-1,-1,-1};

vector< vector<int> > Graph;
vector< int > value;





int main(int argc, const char * argv[]) {
    
    // remove the bottom 3 lines when you submit this code.
    std::ifstream in("sample.txt");
    std::cin.rdbuf(in.rdbuf());

    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n; cin >> n;
    vector<int> t(n+1);
    vector<int> x(n+1);
    vector<int> y(n+1);
    t[0] = 0;
    x[0] = 0;
    y[0] = 0;
    for (int i = 1; i < n+1; i++) cin >> t[i] >> x[i] >> y[i];
    
    for (int i = 1; i < n+1; i++) {
        
        int dt = t[i] - t[i-1];
        int dx = x[i] - x[i-1];
        int dy = y[i] - y[i-1];
        int dh = dx + dy;
        
        if(   !(dh <= dt && (dt-dh)%2==0)  ) {
            cout << "No" << endl;
            return 0;
        }
        
        
    }
    
    cout << "Yes" << endl;
    
}



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

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

    long long r=sqrt(n);
    for(long long i=r; i>=1; i--){
        if(n%i==0){
            cout << i+n/i-2 << endl;
            break;
        }
    }
}

Measured memory_bytes: 256
#include <stdio.h>

int partition(int, int);

int A[100000];

int main(){
  int n,key;
  int i,j;
  
  scanf("%d",&n);
  for(i=1; i<=n; i++){
    scanf("%d",&A[i]);
  }
  
  i = 1;
  key = partition(i,n);
  
  for(i=1; i <= n; i++){
    
    if(i == key){
      printf("[%d]",A[i]);
    }
    else printf("%d",A[i]);

    if((i >= 1) && (i < n))
      printf(" ");
  }
  printf("\n");
  
  return 0;
}

int partition(int p, int r){
  int x,i,j;
  int temp;
  
  x = A[r];
  i = p-1;

  for(j=p; j <= r-1; j++){
    if(A[j] <= x){
      i = i+1;

      temp = A[i];
      A[i] = A[j];
      A[j] = temp;
    } 
  }
    temp = A[i+1];
    A[i+1] = A[r];
    A[r] = temp; 
  
  return i+1;
}

Measured memory_bytes: 992
import java.util.*;
import java.util.Map.Entry;

import javax.swing.text.Segment;
import javax.xml.ws.WebEndpoint;

import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

public class Main implements Runnable
{
//    static int dx[]={-1,0,1,0};
//    static int dy[]={0,-1,0,1};
    static long mod=1000000007;
    
    public static void main(String[] args) {        
        new Thread(null, new Main(), "", 200 * 1024 * 1024).start();        
    }

    public void run() {
        Reader sc = new Reader(System.in);
        PrintWriter out=new PrintWriter(System.out);

        int n=sc.nextInt();
        int d[] = sc.nextIntArray(n);
        for (int i = 0; i < d.length; i++) {
        	if(d[i]%2==0) {
        		if(d[i]%3==0 || d[i]%5==0)continue;
        		ret("DENIED");
        	}
		}

        out.println("APPROVED");
     	out.flush();
    }
   
    static void ret(String ans) {
    	System.out.println(ans);
    	System.exit(0);
    }

    static void ret(long ans) {
    	System.out.println(ans);
    	System.exit(0);
    }
    
    static boolean validpos(int x,int y,int r, int c){
        return x<r && 0<=x && y<c && 0<=y;
    }

    static void db(Object... os){
        System.err.println(Arrays.deepToString(os));
    }
}

//class P {
//	int x,y; double d;
//	P(int  x, int y, double d) {
//	  this.x=x;
//	  this.y=y;
//	  this.d=d;
//	}
//}


class P implements Comparable<P>{
    int p,h,f; long m;
    P(int p,int h, int f, long m) {
    	this.p=p;
    	this.h=h;
    	this.f=f;
    	this.m=m;
    }

    public int compareTo(P p){
    	if(this.p==p.p) {
    		if(this.f==-1) return 1;
    		return -1;
    	}
        return this.p-p.p;
    }
}

class Reader
{ 
    private BufferedReader x;
    private StringTokenizer st;
    
    public Reader(InputStream in)
    {
        x = new BufferedReader(new InputStreamReader(in));
        st = null;
    }
    public String nextString()
    {
        while( st==null || !st.hasMoreTokens() )
			try {
				st = new StringTokenizer(x.readLine());
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
        return st.nextToken();
    }
    public int nextInt()
    {
        return Integer.parseInt(nextString());
    }
    public int[] nextIntArray(int size) {
        int r[] = new int[size];
        for (int i = 0; i < size; i++) {
            r[i] = this.nextInt(); 
        }
        return r;
    }
    public long[] nextLongArray(int size) {
        long r[] = new long[size];
        for (int i = 0; i < size; i++) {
            r[i] = this.nextLong(); 
        }
        return r;
    }
    public char[] getCharSet() {
        return this.nextString().toCharArray();
    }    
    public long nextLong()
    {
        return Long.parseLong(nextString());
    }
    public double nextDouble() throws IOException
    {
        return Double.parseDouble(nextString());
    }
}


Measured memory_bytes: 25300
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner std = new Scanner(System.in);
        int n = std.nextInt();
        int k = std.nextInt();
        String s = std.next();
        StringBuilder sb = new StringBuilder();
        Map<Character, Character> mapping = new HashMap<>();
        mapping.put('A', 'a');
        mapping.put('B', 'b');
        mapping.put('C', 'c');

        for (int i = 0; i < n; i++) {
            Character c = s.charAt(i);
            if (i == k - 1) {
                sb.append(mapping.get(c));
            } else {
                sb.append(c);
            }
        }

        System.out.println(sb.toString());
    }
}


Measured memory_bytes: 21844
#include <iostream>
#include <string>
#include <math.h>
#include <map>
#include <vector>
#include <algorithm>
#define REP(i, n) for(int i = 0; i < (n); i++)

using namespace std;

int main()
{
    long long x; cin >> x;
    long long y = 100;
    int yy = 0;
    while (y < x) {
        y = (long long)(y * 1.01);
        yy++;
    }
    cout << yy << endl;
    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PI acos(-1)
#define vi vector<int>
#define pi pair<int, int>
#define pl pair<ll, ll>
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
const int MOD = 1e9+ 7;
const int INF = numeric_limits<int>::max() - (int)1e8;
const ll INFLL = numeric_limits<ll>::max() - (ll)1e17;

int main() {
    int A, B, C;
    cin >> A >> B >> C;
    int K;
    cin >> K;
    int ans = 0, minus = 0;
    minus = min(A, K);
    ans += minus;
    K -= minus;
    minus = min(B, K);
    K -= minus;
    minus = min(C, K);
    K -= minus;
    ans -= minus;
    cout << ans << endl;
}

Measured memory_bytes: 3636
import sys
sys.setrecursionlimit(2**20)  


class Node:
    def __init__(self, parent=None, left=None, right=None):
        self.parent = parent
        self.left = left  
        self.right = right


def pre_parse(T, u, pre_ls):
    if u == None:
        return
    pre_ls.append(u)
    pre_parse(T, T[u].left, pre_ls) 
    pre_parse(T, T[u].right, pre_ls)


def in_parse(T, u, in_ls):
    if u == None:
        return
    in_parse(T, T[u].left, in_ls)
    in_ls.append(u)
    in_parse(T, T[u].right, in_ls)


def insert(T, ROOT, z):
    if ROOT == z:
        T[z] = Node()
    else:
        T[z] = Node()  
        x = ROOT
        while x is not None:  
            next_parent = x  
            if z < x:  
                x = T[x].left
            else:
                x = T[x].right
        T[z].parent = next_parent
        # 親の右と左どっちにつける？
        if z < next_parent:
            T[next_parent].left = z
        else:
            T[next_parent].right = z


def print_result(T):
    pre_ls, in_ls = [], []
    in_parse(T, ROOT, in_ls)
    pre_parse(T, ROOT, pre_ls)
    print('', *in_ls)
    print('', *pre_ls)


n = int(input())
T = {}
for i in range(n):
    tmp = input()
    if i == 0:
        ROOT = int(tmp[7:])
    if tmp[0] == "p":
        print_result(T)
    else:
        insert(T, ROOT, int(tmp[7:]))



Measured memory_bytes: 141248
#include <stdio.h>
#include <stdlib.h>
#define int long long

signed main(){
	int X, Y, i, ans;
	scanf("%lld%lld", &X, &Y);
	for(i = X, ans = 1; i <= Y; i *= 2){
		ans++;
	}
	printf("%lld\n", ans - 1);
	return 0;
}

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

const int maxn = 1e5+115;

int n, m;
int A[maxn];
int pa[maxn] = {0};
vector<int> contain[maxn];
vector<int> pos[maxn];

int Getfa(int i)
{
	if (pa[i] == i) return i;
	return pa[i] = Getfa(pa[i]);
}

int main()
{
	int Ans = 0;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) scanf("%d", A + i), pa[i] = i;
	for (int i = 1; i <= m; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		pa[Getfa(a)] = Getfa(b);
	}
	for (int i = 1; i <= n; ++i) {
		pa[i] = Getfa(i);
		contain[pa[i]].push_back(A[i]);
		pos[pa[i]].push_back(i);
	}
	for (int i = 1; i <= n; ++i) {
		if (pos[i].empty()) continue;
		sort(contain[i].begin(), contain[i].end());
		sort(pos[i].begin(), pos[i].end());
		while (!contain[i].empty() && !pos[i].empty()) {
			if (contain[i].back() == pos[i].back()) {
				++Ans;
				contain[i].pop_back();
				pos[i].pop_back();
			}
			else if (pos[i].back() > contain[i].back()) {
				pos[i].pop_back();
			}
			else {
				contain[i].pop_back();
			}
		}
	}
	cout << Ans << endl;
	return 0;
}


Measured memory_bytes: 12032
n, k = map(int, input().split())

l = (list)(map(int, input().split()))

d = 10**10
for i in range(n-k+1):
    x_l = l[i]
    x_r = l[i+k-1]

    if x_l >= 0:
        tmp = x_r
    elif x_r <= 0:
        tmp = -x_l
    else:
        tmp = min(abs(x_r), abs(x_l)) + abs(x_l-x_r)

    d = min(d, tmp)

print(d)


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

int main() {
  int a, b;
  cin >> a >> b;
  
  if(b % a == 0) cout << a+b << endl;
  else cout << b-a << endl;
  
  
  
  
  return 0;
}


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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
 
#define mp make_pair
#define pb push_back
#define f first
#define s second

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

    int a, b;
    cin >> a >> b;
    
    if (a * b % 2 == 0) cout << "No" << endl;
    else cout << "Yes" << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Comparator;
public class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n = sc.nextInt();
		long W = sc.nextLong();
		ArrayList<Long>[] list = new ArrayList[4];
		long w1=0;
		for(int i = 0; i<4; i++){
			list[i]=new ArrayList<>();
		}
		for(int i = 0; i<n; i++){
			long w = sc.nextLong();
			long v = sc.nextLong();
			if(i==0){
				w1=w;
				list[0].add(v);
			}else{
				int y=(int)(w-w1);
					list[y].add(v);
					
			}
		}
		for(int i = 0; i<4; i++){
			list[i].sort(Comparator.reverseOrder());
		}
		for(int i = 0; i<4; i++){
			for(int j=1; j<list[i].size(); j++){
				list[i].set(j,list[i].get(j-1)+list[i].get(j));
			}
		}
		long ans=0;
		for(int i = -1; i<list[0].size(); i++){
			for(int j = -1; j<list[1].size(); j++){
				for(int k = -1; k<list[2].size(); k++){
					for(int l = -1; l<list[3].size(); l++){
						if(w1*(i+1)+(w1+1)*(j+1)+(w1+2)*(k+1)+(w1+3)*(l+1)<=W){
							long a=(i==-1)? 0:list[0].get(i);
							long b=(j==-1)? 0:list[1].get(j);
							long c=(k==-1)? 0:list[2].get(k);
							long d=(l==-1)? 0:list[3].get(l);
							ans=Math.max(ans,a+b+c+d);
						}
					}
				}
			}
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 23124
N=int(input())
A=list(map(int,input().split()))
B=[0]*(N+1)
B[0]=abs(A[0])
B[N]=abs(A[N-1])
for i in range(N-1):
  B[i+1]=abs(A[i+1]-A[i])
C=[0]*N
C[0]=abs(A[1])
C[N-1]=abs(A[N-2])
for i in range(N-2):
  C[i+1]=abs(A[i+2]-A[i])
sum=0
for i in range(N+1):
  sum+=B[i]
for i in range(N):
  print(sum-B[i]-B[i+1]+C[i])

Measured memory_bytes: 15940
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<functional>
#include<stack>
#include<queue>
#include <iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int i = 0;i < (n);i++)cerr << v[i] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

struct SCC
{
	vector<vector<int> > G;
	vector<vector<int> > rG;
	vector<int> vs;
	vector<bool> used;
	vector<int> cmp;
	int sz,newsz;
	SCC(int n):G(n),rG(n),used(n,false),cmp(n){sz = n;}
	
	void add_edge(int from,int to)
	{
		G[from].PB(to);
		rG[to].PB(from);
	}
	
	void dfs(int v)
	{
		used[v] = true;
		REP(i,G[v].size())
		{
			if(!used[G[v][i]])dfs(G[v][i]);
		}
		vs.PB(v);
	}
	
	void rdfs(int v,int k)
	{
		used[v] = false;
		cmp[v] = k;
		REP(i,rG[v].size())
		{
			if(used[rG[v][i]])rdfs(rG[v][i],k);
		}
	}
	
	int reMake()
	{

		vs.clear();
		REP(i,sz)if(!used[i])dfs(i);
		int k = 0;
		for(int i = sz-1;i >= 0;i--)
		{
			if(used[vs[i]])
			{
				rdfs(vs[i],k++);
			}
		}
		return newsz = k;
	}
	
	
	
	void makeList(vector<vector<int> > &v)
	{
		REP(i,sz)
		{
			REP(j,G[i].size())
			{
				if(cmp[i] == cmp[G[i][j]])continue;
				v[cmp[i]].PB(cmp[G[i][j]]);
			}
		}
	}

	void makeReverseList(vector<vector<int> > &v)
	{
		REP(i,sz)
		{
			REP(j,G[i].size())
			{
				if(cmp[i] == cmp[G[i][j]])continue;
				v[cmp[G[i][j]]].PB(cmp[i]);
			}
		}
	}
	
	int scc_node(int n)
	{
		return cmp[n];
	}
};


#define MOD 1000000007 

vector<vector<int> > v(1000);
vector<vector<int> > rv(1000);

bool check[10001];
ll dp[1111][2];

void dfs(int n)
{
	check[n] = true;
	
	if(rv[n].size() == 0)
	{
		dp[n][0] = 1;
		dp[n][1] = 1;
		return;
	}
	
	REP(i,rv[n].size())
	{
		dfs(rv[n][i]);
	}

	ll tmpa = 1;
	ll tmpb = 1;	
	REP(i,rv[n].size())
	{
		tmpa = (tmpa * ((dp[rv[n][i]][0]+dp[rv[n][i]][1])%MOD))%MOD;
		tmpb = (tmpb * dp[rv[n][i]][0])%MOD;
	}
	dp[n][0] = tmpb;
	dp[n][1] = tmpa;
	
	return;
}
	

int main()
{
	int n,m;cin >> n >> m;
	
	SCC scc(n);
	REP(i,m)
	{
		int a,b;cin >> a >> b;
		a--;b--;
		scc.add_edge(a,b);
	}
	
	scc.reMake();
	scc.makeList(v);
	scc.makeReverseList(rv);
	
	
	ll ans = 1;
	REP(i,scc.newsz)
	{
		if(v[i].size() == 0 && !check[i])
		{
			dfs(i);
			ans = (ans * (dp[i][0]+dp[i][1]))%MOD;
		}
	}		
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 3268
#include<stdio.h>
#include<string>
#include<iostream>
using namespace std;

int main(void) {
	int N, A, B;
	cin >> N >> A >> B;
	int tmp;
	tmp = N*A;
	if (tmp == B)cout << tmp << endl;
	else {
		if (tmp < B)cout << tmp << endl;
		else cout << B << endl;
	}

	return 0;
}

Measured memory_bytes: 256
import std.stdio, std.conv, std.string;
import std.algorithm, std.array, std.container;
import std.numeric, std.math;
import core.bitop;

T RD(T = string)() { static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res.to!T; }
string RDR()() { return readln.chomp; }

long mod = pow(10, 9) + 7;
long moda(long x, long y) { return (x + y) % mod; }
long mods(long x, long y) { return ((x + mod) - (y % mod)) % mod; }
long modm(long x, long y) { return (x * y) % mod; }

void main()
{
	auto N = RD!long;
	auto a = RDR.split.to!(long[]);

	auto dp = new long[](N+1);
	dp[0] = 0;
	foreach (i, e; a)
	{
		dp[i+1] = dp[i] + e;
	}
	long best = long.max;
	foreach (e; dp[1..$-1])
	{
		auto x = e;
		auto y = dp[N] - e;
		if (abs(x - y) < best)
		{
			best = abs(x - y);
		}
	}

	writeln(best);
	stdout.flush();
}

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

int main(){
  string s, t;
  cin >> s >> t;
  int ans = 1e9;
  for(size_t i = 0; i+t.length() <= s.length(); ++i){
    int d = 0;
    for(size_t j = 0; j < t.length(); ++j){
      d += s[i+j] != t[j];
    }
    ans = min(ans,d);
  }
  cout << ans << endl;
}


Measured memory_bytes: 3620
package main

import (
	"fmt"
	"math"
)

func main() {
	var n int
	fmt.Scan(&n)
	count := 0
	temp := primeFactor(n)

	if n == 1 {
		fmt.Println(0)
		return
	}
	for i, v := range temp {
		for j := 1; j <= v; j++ {
			h := int(math.Pow(float64(i), float64(j)))
			if can(h) && n%h == 0 {
				n /= h
				count++
			}
			if n == 1 {
				fmt.Println(count)
				return
			}
		}
	}
	fmt.Println(count)

}

func can(n int) bool {
	if len(primeFactor(n)) == 1 {
		return true
	}
	return false
}

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

Measured memory_bytes: 1856
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n + 2];
        long m = 1000;
        long c = 0;
        a[0] = 200; a[n + 1] = 100;

        for (int i = 1 ; i <= n ; i++) {
            a[i] = sc.nextInt();
        }
        List<Integer> list = new ArrayList<Integer>();
        list.add(200);
        for (int i = 1 ;  i < n + 2 ; i++) {
            if (a[i] != list.get(list.size()- 1)) {
                list.add(a[i]);
            }
        }
        for (int i = 0 ; i < list.size() - 2 ; i++) {
            if (list.get(i) > list.get(i + 1) && list.get(i + 1) < list.get(i + 2)) {
                c = m / list.get(i + 1);
                m %= list.get(i + 1);
            }
            if (list.get(i) < list.get(i + 1) && list.get(i + 1) > list.get(i + 2)) {
                m += c * list.get(i + 1);
            }
        }
        System.out.println(m);
    }

}

Measured memory_bytes: 35900
#include <bits/stdc++.h>
#define repl(i, l, r) for (ll i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

int main()
{
    int n;
    cin >> n;
    int c0, c1, c2, c3;
    c0 = 0;
    c1 = 0;
    c2 = 0;
    c3 = 0;
    rep(i, n) {
        string s;
        cin >> s;
        if(s == "AC") c0++;
        if(s == "WA") c1++;
        if(s == "TLE") c2++;
        if(s == "RE") c3++;
    }
    cout << "AC x " << c0 << endl;
    cout << "WA x " << c1 << endl;
    cout << "TLE x " << c2 << endl;
    cout << "RE x " << c3 << endl;
    return 0;
}


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

#define debug(...) fprintf(stderr, __VA_ARGS__)

#ifndef AT_HOME
#define getchar() IO::myGetchar()
#define putchar(x) IO::myPutchar(x)
#endif

namespace IO {
	static const int IN_BUF = 1 << 23, OUT_BUF = 1 << 23;

	inline char myGetchar() {
		static char buf[IN_BUF], *ps = buf, *pt = buf;
		if (ps == pt) {
			ps = buf, pt = buf + fread(buf, 1, IN_BUF, stdin);
		}
		return ps == pt ? EOF : *ps++;
	}

	template<typename T>
	inline bool read(T &x) {
		bool op = 0;
		char ch = getchar();
		x = 0;
		for (; !isdigit(ch) && ch != EOF; ch = getchar()) {
			op ^= (ch == '-');
		}
		if (ch == EOF) {
			return false;
		}
		for (; isdigit(ch); ch = getchar()) {
			x = x * 10 + (ch ^ '0');
		}
		if (op) {
			x = -x;
		}
		return true;
	}

	inline int readStr(char *s) {
		int n = 0;
		char ch = getchar();
		for (; isspace(ch) && ch != EOF; ch = getchar())
			;
		for (; !isspace(ch) && ch != EOF; ch = getchar()) {
			s[n++] = ch;
		}
		s[n] = '\0';
		return n;
	}

	inline void myPutchar(char x) {
		static char pbuf[OUT_BUF], *pp = pbuf;
		struct _flusher {
			~_flusher() {
				fwrite(pbuf, 1, pp - pbuf, stdout);
			}
		};
		static _flusher outputFlusher;
		if (pp == pbuf + OUT_BUF) {
			fwrite(pbuf, 1, OUT_BUF, stdout);
			pp = pbuf;
		}
		*pp++ = x;
	}

	template<typename T>
	inline void print_(T x) {
		if (x == 0) {
			putchar('0');
			return;
		}
		static int num[40];
		if (x < 0) {
			putchar('-');
			x = -x;
		}
		for (*num = 0; x; x /= 10) {
			num[++*num] = x % 10;
		}
		while (*num){
			putchar(num[*num] ^ '0');
			--*num;
		}
	}

	template<typename T>
	inline void print(T x, char ch = '\n') {
		print_(x);
		putchar(ch);
	}

	inline void printStr_(const char *s, int n = -1) {
		if (n == -1) {
			n = strlen(s);
		}
		for (int i = 0; i < n; ++i) {
			putchar(s[i]);
		}
	}

	inline void printStr(const char *s, int n = -1, char ch = '\n') {
		printStr_(s, n);
		putchar(ch);
	}
}
using namespace IO;

const int N = 205;

int n;
long long a[N];
char s[N];

long long B[64];

bool insert(long long x) {
	for (int i = 59; ~i; --i) {
		if (x >> i & 1) {
			if (B[i]) {
				x ^= B[i];
			} else {
				B[i] = x;
				return true;
			}
		}
	}
	return false;
}

void solve() {
	read(n);
	for (int i = 1; i <= n; ++i) {
		read(a[i]);
	}
	for (int i = 0; i < 60; ++i) {
		B[i] = 0;
	}
	readStr(s + 1);
	for (int i = n; i; --i) {
		if (s[i] == '0') {
			insert(a[i]);
		} else {
			if (insert(a[i])) {
				print(1);
				return;
			}
		}
	}
	print(0);
}

int main() {
	int T = 1;
	read(T);
	while (T--) {
		solve();
	}
}


Measured memory_bytes: 3960
n=int(input())
a=list(map(int,input().split()))
d={}
for i in range(n):
    if a[i] in d:
        d[a[i]]+=1
    else:
        d[a[i]]=1
ans=0
D=list(d.values())
for i in range(len(D)):
    s=D[i]*(D[i]-1)//2
    ans+=s
for i in range(n):
    print(ans-d[a[i]]+1)

Measured memory_bytes: 107252
#ifdef __APPLE__
#include <iostream>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <iomanip>
#include <cmath>
#include <ctgmath>
#include <math.h>
#include <cassert>
#include <chrono>
#else
#include <bits/stdc++.h>
#endif

using namespace std;
#define io ios_base::sync_with_stdio(false), cin.tie(NULL)
#define GFOR(i,a,n) for (i=a;i<n;i++)
#define FOR(i,a,n) for (int i=a;i<n;i++)
#define RFOR(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define tc(t) for (int tc=1; tc<=t; tc++)
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<long long int> vll;
typedef vector<pair<int, int> > vpi;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll modInverse (ll a) {ll p = mod - 2; return powmod(a, p);}
// head

void solve() {
    ll n, x, m;
    cin >> n >> x >> m;
    vll arr, freq(m, -1);
    ll start;
    freq[x] = 0;
    arr.push_back(x);
    n--;
    while (n--) {
        ll curr = (x*x)%m;
        if (freq[curr] >= 0) {
            start = freq[curr];
            n++;
            break;
        }
        x = curr;
        arr.pb(x), freq[x] = sz(arr) - 1;
    }

    ll ans = 0;
    if (n <= 0) {
        for (auto y : arr)
            ans += y;
    } else {
        for (auto y : arr)
            ans += y;
        ll mul = n/(sz(arr) - start), rem = n%(sz(arr) - start);
        ll csum = 0;
        for (int i = start; i < sz(arr); i++)
            csum += arr[i];
        ll rsum = 0;
        for (int i = start; i < (start + rem); i++)   
            rsum += arr[i];
        ans += mul*csum + rsum;
    }
    cout << ans << '\n';
}

int main() {
    #ifdef LOCAL
    auto t1 = std::chrono::high_resolution_clock::now();
    #endif

    io;
    solve();

    #ifdef LOCAL
    auto t2 = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>( t2 - t1 ).count();

    std::cout << "Time Taken: " << duration << "\n";
    #endif

}
// check for edge cases in limits
// printing double may print 1.223232e9 like values, beware of that
// carefully observe simulation of test cases
// multiset erase is does not do what it is supposed to


Measured memory_bytes: 4616