akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef long double ld;
#define mod 1000000007

int main()
{
	ll n,m,k;
	cin>>n>>m>>k;
	ll arr[n],brr[m];

	for(ll i=0;i<n;i++)
  		cin>>arr[i];

    for(ll i=0;i<m;i++)
		cin>>brr[i];
  
    
    for(ll i=1;i<n;i++)
    	arr[i]=arr[i]+arr[i-1];

    for(ll i=1;i<m;i++)
    	brr[i]=brr[i]+brr[i-1];
    
    if(arr[n-1]+brr[m-1]<=k)
    {
    	cout<<m+n;
    	return 0;
    }
    if(arr[0]>k && brr[0]>k)
    {
    	cout<<0;
    	return 0;
    }


    ll minn=-1;

    for(ll i=0;i<n;i++)
    { 
      if(arr[i]<=k)
       {
      	minn=i;
       }
    }
    
     ll  pp2=upper_bound(arr,arr+n,k)-arr;
     ll  pp=upper_bound(brr,brr+m,k)-brr;
    
      if(minn==-1)
      {
        ll  ans=upper_bound(brr,brr+m,k)-brr-1;
         cout<<ans+1;
         return 0;

      }

     ll ans=minn+1;

     while(minn!=-1)
     {
       ll d=arr[minn];
       ll temp=k-d;

       if(temp<brr[0])
       {
       	minn--;
       	continue;
       }
       if(temp>=brr[m-1])
       {
       	ans=max(ans,minn+m+1);
       	minn--;
       	continue;
       }
       ll p= upper_bound(brr,brr+m,temp)-brr-1;

       	ans=max(ans,minn+p+2);
       minn--;
     } 

     cout<<max(ans,max(pp,pp2));


  return 0;
}





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

int main() {
  int r, g, b;
  cin >> r >> g >> b;
  
  if((10 * g + b) % 4 == 0) {
    cout << "YES" << endl;
  }
  
  else {
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main() {
	int n;
	cin >> n;
	int A[111];
	for (int i = 0; i < n; i++)cin >> A[i];
	sort(A, A + n);
	cout << A[n - 1] - A[0] << endl;
}

Measured memory_bytes: 256
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998_244_353

@njit((i8, i8), cache=True)
def mpow(a, n):
    p = 1
    while n:
        if n & 1:
            p = p * a % MOD
        a = a * a % MOD
        n >>= 1
    return p

@njit((i8[:], ), cache=True)
def build(raw_data):
    bit = raw_data.copy()
    for i in range(len(bit)):
        j = i + (i & (-i))
        if j < len(bit):
            bit[j] += bit[i]
            bit[j] %= MOD
    return bit


@njit((i8[:], i8), cache=True)
def get_sum(bit, i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s % MOD


@njit((i8[:], i8, i8), cache=True)
def add(bit, i, x):
    while i < len(bit):
        bit[i] += x
        bit[i] %= MOD
        i += i & -i

@njit((i8, i8[:]), cache=True)
def main(K, A):
    N = len(A)
    # 各処理の段階で、n が active になっている確率を求める。
    # 個数の分布も持つ。
    # 更新を sparse にするために、時刻（右端のインデックス） i にアクティブになったところの
    # 生存率には、p^{-i} を入れておく。時刻 t には確率 p^{t-i} なので、和に p^t をかける
    p = (1 - mpow(K, MOD - 2)) % MOD
    p_inv = mpow(p, MOD - 2)
    bit_active = np.zeros(N + 1, np.int64)
    bit_cnt = np.zeros(N + 1, np.int64)
    half = (MOD + 1) // 2
    ans = 0
    # 最初の起動
    ans += K * (K - 1) // 2 % MOD * half % MOD
    ans %= MOD
    for i in range(K):
        x = A[i]
        add(bit_cnt, x, 1)
        add(bit_active, x, mpow(p_inv, K - 1))
    for i in range(K, N):
        x = A[i]
        low_cnt = get_sum(bit_cnt, x)
        high_cnt = i - low_cnt
        pt = mpow(p, i)
        active_sum_low = get_sum(bit_active, x) * pt % MOD
        active_sum_high = K - 1 - active_sum_low
        # 追加処理
        add(bit_cnt, x, 1)
        add(bit_active, x, mpow(p_inv, i))
        # A[i] と A[j] (j<i) の転倒数の期待値を計算
        inv = 0
        inv += active_sum_low * half % MOD
        inv += (high_cnt - active_sum_high)
        inv += active_sum_high * half % MOD
        inv %= MOD
        ans += inv
        ans %= MOD
    return ans

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

print(main(K, A))

Measured memory_bytes: 119476
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<iomanip>


#define MOD 1000000007
#define INF 1001001001
#define MIN -1001001001
#define rep(i,k,N) for(int i=k;i<N;i++)
#define MP make_pair
#define MT make_tuple //tie,make_tuple は別物
#define PB push_back
#define PF push_front
#define all(x) (x).begin(),(x).end()


using namespace std;
typedef long long ll;
typedef vector<ll> v;
typedef vector<vector<ll>> vv;

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

int main(){
    ll N;
    cin>>N;
    string S;
    cin>>S;
    ll r=0,g=0,b=0;
    v rv,gv;
    v bSum(N,0);
    ll ans =0;
    rep(i,0,N){
        if(S[i] == 'R'){
            r++;
            rv.PB(i);
        }
        if(S[i] == 'G'){
            g++;
            gv.PB(i);
        }
        if(S[i] == 'B'){
            b++;
            if(i == 0)bSum[0] = 1;
            else bSum[i] = bSum[i-1]+1;
        }
        else {
            if(i != 0)bSum[i] = bSum[i-1];
        }
    }
    rep(i,0,rv.size())rep(j,0,gv.size()){
        if(2*gv[j]-rv[i]>=0 && 2*gv[j]-rv[i] < N)if(S[2*gv[j]-rv[i]] == 'B')ans--;
        if(2*rv[i]-gv[j]>=0 && 2*rv[i]-gv[j] < N)if(S[2*rv[i]-gv[j]] == 'B')ans--;
        if((rv[i]+gv[j])%2 == 0){
            if(S[(rv[i]+gv[j])/2] == 'B')ans--;
        }
        ans += b;
    }

    cout<<ans;
    return 0;
}

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

int main(){
    ll N, D; cin >> N >> D;
    int ans = 0;
    rep(i, N){
        ll x, y; cin >> x >> y;
        if(x*x + y*y <= D*D) ++ans;
    }
    cout << ans << endl;
}



Measured memory_bytes: 3592
N,M = [int(x) for x in input().strip().split()]

Knk=[]
for _ in range(N):
    Knk.append([int(x) for x in input().strip().split()])

ans = [0] * M

for i,Kn in enumerate(Knk):
    for n,A in enumerate(Kn):
        if n == 0:
            continue
        ans[A-1]+=1

print(len([x for x in ans if x == N]))


Measured memory_bytes: 3060
package main

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

func isInt(n float64) bool {
	return math.Floor(n) == n
}

func main() {
	var a, b string
	fmt.Scan(&a, &b)

	s := []string{a, b}
	n, _ := strconv.Atoi(strings.Join(s, ""))

	if isInt(math.Sqrt(float64(n))) {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> P;
typedef string str;
typedef vector<P> vp;
typedef vector<string> vs;
typedef vector<bool> vb;

const ll mod=1e9;
const ll inf=1e16;

#define rep(i,m,n) for(ll i=m;i<n;i++)
#define repr(i,m,n) for(ll i=m-1;i>=n;i--)
#define fi first
#define se second
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#define eb(x) emplace_back(x)
#define pb(x) pop_back(x)
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define sum(x) accumulate(all(x),0)
#define pc(x) __builtin_popcount(x)
#define gll greater<ll>()

void solve(){
 ll x,k,d;
  cin >> x >> k >> d;
 ll n=min(abs(x)/d,k);
 
 x-=x/abs(x)*n*d;
 k-=n;
 k%=2;
  cout << min(abs(x+k*d),abs(x-k*d)) << endl;

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


Measured memory_bytes: 3660
#include<stdio.h>

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

int main(){
  int n,s[size],q,t[size];
  int i,j,k;
  int count=0;
  int l,m,h;

  scanf("%d",&n);
  rep(i,n)
    scanf("%d",&s[i]);
  scanf("%d",&q);
  rep(i,q)
    scanf("%d",&t[i]);

  rep(i,q){
    l=0;h=n;
    while(l<h){
      m=(l+h)/2;
      if(s[m]>t[i]){
	h=m;
      }else if(s[m]<t[i]){
	l=m+1;
      }else{
	count++;
	break;
      }
    }
      
  }
  printf("%d\n",count);
  return 0;
}

Measured memory_bytes: 3136
N = int(input())
V_lst = list(map(int, input().split()))
C_lst = list(map(int, input().split()))


P_lst = []
for i in range(N):
    P_lst.append(V_lst[i] - C_lst[i])
    
ans = 0    
for i in range(N):
    if P_lst[i] > 0:
        ans += P_lst[i]
        
print(ans)        

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
int main(){
  int n,k;
  cin >> n >> k;
  int ans[n]={};
  rep(i,k){
    int d;
    cin >> d;
    rep(j,d){
      int temp;
      cin>> temp;
      ans[temp-1]++;
    }
  }
  int ansa=0;
  rep(i,n){

    if(ans[i]==0){
      ansa++;
    }
  }
  cout << ansa <<endl;
  return 0;
}

Measured memory_bytes: 3592
#include <cstdio>

int main(){
    int i, h;
    scanf("%d",&h);
    int a[h];
    int p, l, r;
    for(i=0;i<h;i++)scanf("%d",a+i);
    for(i=0;i<h;i++){
        printf("node %d: key = %d, ",i+1, a[i]);
        if(i>0)printf("parent key = %d, ",a[(i+1)/2-1]);
        if((i+1)*2-1<h)printf("left key = %d, ", a[(i+1)*2-1]);
        if((i+1)*2<h)printf("right key = %d, ", a[(i+1)*2]);
        printf("\n");
    }
    return 0;
}



Measured memory_bytes: 2672
#include <iostream>
#include <iomanip> //! for setprecision(10)
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>

using namespace std;

typedef long long LL;

#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define rep(i,n) for (int i = 0; i < (n); ++i)

const int MOD = 1000000007;

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

    string S;
    int N, P;
    cin >> N >> P >> S;

    LL ans = 0;

    if (P == 2 || P == 5) {
        rep(i, N) {
            int d = S[N-1-i] - '0';
            if (d % P == 0) {
                ans += (N-i);
            }
        }
    } else {
        vector<int> m(N);
        int b = 1;
        int prev = 0;
        rep(i, N) {
            int d = S[N-1-i] - '0';
            m[i] = (prev + b * d) % P;
            prev = m[i];
            b = (b * 10) % P;
        }
        vector<int> hist(P);
        hist[0] = 1;
        rep(i, N) {
            ans += hist[m[i]];
            ++hist[m[i]];
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1428
//It’s never too late to become what you might have been....
 #include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define inf 1000000000000
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define S second
#define F first
#define boost1 ios::sync_with_stdio(false);
#define boost2 cin.tie(0);
#define mem(a,val) memset(a,val,sizeof a)
#define endl "\n"
#define maxn 100001

int main()
{
	boost1;boost2;	
	ll i,j,n,ans=0;
	char ch;
	string s;
	cin>>s;
	for(i=0;i<s.length();i++)
	{
		if(i%2==0)
		ch='g';
		else
		ch='p';
		if(ch==s[i])
		continue;
		if(ch=='p')
		ans++;
		else
			ans--;
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring> //memset(dp,0,sizeof(dp))
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<ll,ll> P;
typedef pair<ll,ll> Pll;
//小数点以下　cout << fixed << setprecision(10) << num << endl;
//桁数はlog10(mid)でやれ　log(mid)/log(10)はWA
//long*long<0で判定するな
//開区間と閉区間
//アルファベットが何番目かは x=s[i]-'a'
//bfsはmain()内で　rep(i,h)rep(j,w)rep(i,4)でバグ
//切り上げ：(a+(b-1))/b
//32bit以上は 1ull<<j
// map 初期値0 for(auto itr=mp.begin();itr!=mp.end();++itr) itr->fi itr->se で全探索
// for(auto u:mp) u.fi u.se も可能
//n個のgcd,lcmは一つずつみて更新していく
//大きな数を扱うときは素因数分解した形で持っておく
// (l/a[i]) = l*powmod(a[i],MOD-2)%MOD;
//auto itr=lower_bound(ALL(a),key) a[itr-a.begin()]

const ll MOD=10000000000000000;
int main(){
    ll k; cin >> k;
    if(k==0){
        cout << 2 << endl;
        cout << 1 << " " << 1 << endl;
        return 0;
    }
    ll n=k/MOD;
    if(k%MOD!=0) n++;
    if(n==1) n++;
    if(n==0) n+=2;
    cout << n << endl;
    ll a=k/n;
    ll res[n];
    rep(i,n) res[i]=a+i;
    rep(i,k-n*a){
        res[i%n]+=n;
        for(int j=1;j<n;j++){
            res[(i+j)%n]--;
        }
    }
    rep(i,n) cout << res[i] <<" ";
}


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

using namespace std;

int main() {
	int H, W, h, w, Swap = 0;
	cin >> H >> W >> h >> w;
	if(H % h == 0 && W % w == 0) {
		puts("No");
	} else {
		puts("Yes");
		int val = (h * w - 1) * 500 + 1;
		for(int i = 1; i <= H; i++) {
			for(int j = 1; j <= W; j++) {
				if(i % h == 0 && j % w == 0)
					printf("%d ", -val);
				else
					printf("500 ");
			}
			puts("");
		}
	}
	return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
int main(){
  int x,y;
  cin >> x >> y;
  if(x < y){
    swap(x,y);
  }
  while(y){
    int temp = y;
    y = x % y;
    x = temp;
  }
  cout << x << endl;
  return 0;
}

Measured memory_bytes: 1160
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32
from functools import lru_cache



def solve(N: int, K: int):
    @lru_cache(None)
    def f(n: int, k:int):
        if n < 10:
            if k == 0:
                # n <= 9 and k == 0のときは0個
                return 1
            elif k == 1:
                # n <= 9 and k == 1のときは、1-9の9個
                return n
            else:
                # n <= 9でk == 2以上の時は、解がない
                return 0

        return f(n//10, k-1)*(n%10) + f(n//10-1, k-1) *(9-n%10) + f(n//10, k)


    print(f(N, K))

    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
    K = int(next(tokens))  # type: int
    solve(N, K)

if __name__ == '__main__':
    main()


Measured memory_bytes: 6180
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#define maxn 2005
using namespace std;
typedef pair<int,int> PII;
int n,a[maxn],ans[maxn],deg[maxn];
bool G1[maxn][maxn],vis[maxn];
vector<int> G[maxn];
priority_queue<PII> q;
int gcd(int a,int b)
{
	if(!b) return a;
	return gcd(b,a%b);
}
void dfs(int u,int fa)
{
	vis[u]=true;
	for(int v=1;v<=n;v++)
		if(G1[u][v]&&!vis[v])
		{
			G[u].push_back(v); deg[v]++;
			dfs(v,u);
		}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(gcd(a[i],a[j])!=1) G1[i][j]=G1[j][i]=true;
	for(int i=1;i<=n;i++)
		if(!vis[i]) dfs(i,0);
	for(int i=1;i<=n;i++)
		if(!deg[i]) q.push(PII(a[i],i));
	int cnt=0;
	while(!q.empty())
	{
		PII u=q.top(); q.pop();
		ans[++cnt]=u.first;
		for(int i=0,siz=G[u.second].size();i<siz;i++)
		{
			int v=G[u.second][i]; deg[v]--;
			if(!deg[v]) q.push(PII(a[v],v));
		}
	}
	for(int i=1;i<cnt;i++) printf("%d ",ans[i]);
	printf("%d\n",ans[n]);
}

Measured memory_bytes: 4480
from __future__ import print_function

import sys
sys.setrecursionlimit(500000)

import re
import array
import copy
import functools
import operator

import math
import string
import fractions
from fractions import Fraction

import collections
import itertools
import bisect

import random
import time

import heapq
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace
from queue import PriorityQueue as pq
from queue import Queue

from itertools import accumulate

from collections import deque
from collections import Counter

from operator import mul
from functools import reduce

input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    x = int(input().strip())
    for a in range(0,2000):
        for b in range(-100,2000):
            if a**5 - b**5 == x:
                print(a,b)
                return


if __name__ == '__main__':
    main()

Measured memory_bytes: 78232
#include <stdio.h>
#include <math.h>
int len(int a){
    int count=0;
    while (a>0){
        a=a/10;
        count+=1;
    }
    return count;
}
int pow10(int x){
int ans=1;
    for(int i=0;i<x;i++){
ans *=10;
    }
    return ans;
}
int judge(int c){
    
    for(int i=0;i<=c;i++){
   
        if(i*i==c){
            return 1;
        }
    }
    return 0;
}

int main(){
    int a,b;
    int a2;
   
    scanf("%d%d",&a,&b);
 
    a2=a;
  
   int ans=pow10(len(b))*a2;
   int result = ans+b;
   int n;
  
   int aaa=judge(result);

   if(judge(result)==1){
       printf("Yes");
   }else{
       printf("No");
   }
}

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

using namespace std;

int main(){
  int a,N,X,min=1000;
  cin >> N >> X;
  a=N;
  int m[N];
  for(int i=0;i<N;i++){
    cin >> m[i];
    if(m[i]<min){min=m[i];}
    X-=m[i];
  }
  while(X>=min){
    a++;
    X-=min;
  }
  cout << a << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::string s;
    std::cin >> s;
    int cnt = std::count(s.begin(), s.end(), '0');
    std::cout << 2 * std::min(cnt, (int)s.size() - cnt) << std::endl;

    return 0;
}


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

int main() {
    int n, m;
    cin >> n >> m;
    string t;
    rep(i,n) {
        t += 'x';
    }
    bool ilegal = false;
    vector<char> check(n);
    rep(i,n) {
        check[i] = '0';
    }
    rep(i,m) {
        int s;
        char c;
        cin >> s >> c;
        if (check[s-1] == '0' || check[s-1] == c) {
            check[s-1] = c;
        }
        else {
            ilegal = true;
        }
        t[s-1] = c;
    }
    int ans;
    if (ilegal) {
        cout << -1 << endl;
        return 0;
    }
    if (n == 3) {
        if (t[0] == 'x') t[0] = '1';
        if (t[0] != 0 && t[1] == 'x') t[1] = '0';
        if (t[2] == 'x') t[2] = '0';
        if (t[0] == '0' || (t[0] == '0' && t[1] == '0')) {
            cout << -1 << endl;
            return 0;
        }
    }
    if (n == 2) {
        if (t[0] == 'x') t[0] = '1';
        if (t[0] != '0' && t[1] == 'x') t[1] = '0'; 
        if (t[0] == '0') {
            cout << -1 << endl;
            return 0;
        }
    }
    if (n == 1) {
        if (t[0] == 'x') t[0] = '0';
    }
    ans = stoi(t);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
	x=0;char c=getchar();bool f=0;
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
	if(x<0){putchar('-'),write(-x);}
	else{if(x>9)write(x/10);putchar('0'+x%10);}
}

//#define int long long

const int mod=1e9+7,N=1e7+5;
int fac[N],inv[N],n,k;

int fpow(int x,int y){
	int res=1;
	for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod;
	return res;
}

int C(int n,int m){
	if(m>n) return 0;
	return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}

int lucas(int n,int m){
	if(!m) return 1;
	return 1ll*C(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;
}

signed main(){
	read(n);read(k);
	fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	inv[n]=fpow(fac[n],mod-2);
	for(int i=n-1;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
	for(int i=1;i<=k;i++) write(1ll*C(k-1,i-1)*C(n-k+1,i)%mod),puts("");
}

Measured memory_bytes: 2304
#include <bits/stdc++.h>
using namespace std;
using LL = long long; using PII = pair<LL, LL>; using VI = vector<LL>; using VVI = vector<VI>;
using VB = vector<bool>; using VS = vector<string>; using VP = vector<PII>;
#define VV(T)        vector<vector<T>>
#define PB           push_back
#define MP           make_pair
#define SZ(a)        LL((a).size())
#define EACH(x, c)   for (auto x : (c))
#define ALL(c)       (c).begin(), (c).end()
#define REVERSE(c)   reverse(ALL(c))
#define SORT(c)      stable_sort(ALL(c))
#define RSORT(c)     stable_sort((c).rbegin(), (c).rend())
#define FOR(i, a, b) for (LL i = (a); i < (b); ++i)
#define REP(i, n)    FOR(i, 0, n)
#define $(x)         {cout << #x << " = " << (x) << endl;}


inline LL minMult(LL x, LL n) { return (x / n + (x % n == 0 ? 0 : 1)); }


void solve(LL D, LL G, vector<LL> p, vector<LL> c){
    LL min_n_prob = accumulate(ALL(p), 0);
    REP(i, 1 << D) {   // choice of complete solve or complete non-solve
        LL n_prob = 0, sum_points = 0;
        LL non_complete_max_k = -1;
        REP(k, D) {
            if (i & ((LL)1 << k)) {   // k-th problem set will be completely solved
                n_prob += p[k];
                sum_points += p[k] * (k + 1) * 100 + c[k];
            } else {
                non_complete_max_k = max(non_complete_max_k, k);
            }
        }
        if (sum_points >= G) {
            min_n_prob = min(min_n_prob, n_prob);
        } else {
            LL non_complete_n_prob = minMult(G - sum_points, 100 * (non_complete_max_k + 1));
            if (non_complete_n_prob <= p[non_complete_max_k]) {
                min_n_prob = min(min_n_prob, n_prob + non_complete_n_prob);
            }
        }
    }
    cout << min_n_prob << endl;
}

int main(){
    LL D;
    scanf("%lld",&D);
    LL G;
    scanf("%lld",&G);
    vector<LL> p(D);
    vector<LL> c(D);
    for(int i = 0 ; i < D ; i++){
        scanf("%lld",&p[i]);
        scanf("%lld",&c[i]);
    }
    solve(D, G, move(p), move(c));
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
signed main(){
  int n,dp[100005],a[100005];
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a[i];
  }

  a[0]=100001;
  for(int i=2;i<=n;i++){
    dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
  }
  
  cout<<dp[n]<<endl;
  return(0);
}
		     
  


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

int main(){
    long long a, b, c;cin>>a>>b>>c;
    vector<long long> cookies{a, b, c};
    long long acc = 0;

    while (true){
        if (cookies[0] % 2 == 1 || cookies[1] % 2 == 1 || cookies[2] % 2 == 1){
            cout << acc << endl;
            break;
        }
        vector<long long> temp(3);
        temp[0] = cookies[1] / 2 + cookies[2] / 2;
        temp[1] = cookies[0] / 2 + cookies[2] / 2;
        temp[2] = cookies[0] / 2 + cookies[1] / 2;
        cookies = temp;
        acc++;

        if (a == cookies[0] && b == cookies[1] && c == cookies[2]){
            cout << -1 << endl;
            break;
        }
    }
    return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(n); ++i)
#define repr(i, a, b) for (int i=a; i<(b); ++i)
#define reprev(i, n) for (int i=n-1; i>=0; --i)
#define reprrev(i, a, b) for (int i=b-1; i>=(a); --i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    cout << fixed << setprecision(10);
    
    int N; cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];

    rep(i, N) {
        if (A[i] % 2 == 0) {
            if (!(A[i] % 5 == 0 | A[i] % 3 == 0)) {
                cout << "DENIED" << endl;
                return 0;
            }
        }
    }
    cout << "APPROVED" << endl;
    return 0;
}

Measured memory_bytes: 256
import itertools

n = int(input())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
seq = []
count = 0
a = 0
b = 0

for i in range(n):
    seq.append(i+1)

permutation = list(itertools.permutations(seq))
#print(permutation[0][0])
#print(p)

for i in range(len(permutation)):
    for j in range(n):
        if(p[j] != permutation[i][j]):
            #print(permutation[i])
            #print(p)
            break
        if(j == n-1):
            a = count
    for k in range(n):
        if(q[k] != permutation[i][k]):
            break
        if(k == n-1):
            b = count
    count = count + 1

#print(a)
#print(b)
print(abs(b-a))

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

#define NIL (Node *)-1

struct Node {
	int key;
	Node *p, *left, *right;
	Node( int k ) { key = k; p = left = right = NIL; }
};
Node *root = NIL;

void insert( Node *z )
{
	Node *y = NIL;
	Node *x = root;
	while( x != NIL ) {
		y = x;
		if( z->key < x->key ) {
			x = x->left;
		}
		else {
			x = x->right;
		}
	}
	z->p = y;
	if( y == NIL ) {
		root = z;
	}
	else if( z->key < y->key ) {
		y->left = z;
	}
	else {
		y->right = z;
	}
}

void printp( Node *n )
{
	if( n == NIL ) return;
	cout << " " << n->key;
	printp( n->left );
	printp( n->right );
}

void printm( Node *n )
{
	if( n == NIL ) return;
	printm( n->left );
	cout << " " << n->key;
	printm( n->right );
}

int main()
{
	int m;
	cin >> m;
	for( int i = 0; i < m; i++ ) {
		string com;
		cin >> com;
		if( com == "insert" ) {
			int k;
			cin >> k;
			Node *n = new Node( k );
			insert( n );
		}
		else {
			printm( root );
			cout << endl;
			printp( root );
			cout << endl;
		}
	}
}



Measured memory_bytes: 26560
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#define FL "a"
using namespace std;
typedef long long ll;
typedef long double dd;
const int N=105;
inline ll read(){
  ll d=0,w=1;char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
  if(ch=='-')w=-1,ch=getchar();
  while(ch<='9'&&ch>='0')d=d*10+ch-48,ch=getchar();
  return d*w;
}
inline void file(){
  freopen(FL".in","r",stdin);
  freopen(FL".out","w",stdout);
}

int main()
{
  int a,b,c;
  cin>>a>>b>>c;
  puts(a==b&&b==c?"Yes":"No");
  return 0;
}


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

int N;

int main() {
    cin >> N;

    int ans = 0;
    for (int i = 1; i <= N; i++) {
        string s = to_string(i);
        if (s.size() % 2 == 1) {
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void _main()
{
    string s;
    cin >> s;
    cout << ((((s.size() % 2) == 0) != (s[0] == s[s.size() - 1])) ? "Second" : "First") << endl;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
using ll  = long long;
using vl  = vector<ll>;
using vi  = vector<int>;
#define _GLIBCXX_DEBUG
#define IO_STREAM cin.tie(0);ios::sync_with_stdio(false)
#define all(x) x.begin(),x.end()
#define rep(i,sta,end) for(int i=sta;i<end;++i)
#define lcm(a,b) (a)/__gcd((a),(b))*(b)
#define pb push_back
const ll INF = 1000000000000000;
const ll MOD = 1000000007;
const double PI = acos(-1);
//||
#define DBG(a,b,c,d) //cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<endl
//DBG("","","","");

signed main(){
	IO_STREAM;
	int N,M;
	cin>>N>>M;
	string S;
	int p;
	map<int,int>mp;
	int AC_cnt=0;
	int WA_cnt=0;
	vi WA(N+1,0);
	rep(i,0,M){
		cin>>p>>S;
		if(mp[p]==0){
			if(S=="AC"){
				AC_cnt++;
				WA_cnt+=WA[p];
				mp[p]=1;
			}
			else{
				WA[p]++;
			}
		}
	}
	cout<<AC_cnt<<' '<<WA_cnt<<endl;
	return 0;
}


Measured memory_bytes: 8176
# -*- coding: utf-8 -*-
_a, _b, m = map(int, input().split())

a = list(map(int, input().split()))
b = list(map(int, input().split()))

cost = min(a) + min(b)
for i in range(m):
    ai, bi, c = map(int, input().split())
    cost = min(cost, a[ai-1] + b[bi-1] - c)

print(cost)



Measured memory_bytes: 70892
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		Boolean isEnd = str == null;
		while (!isEnd) {
			long number = Long.parseLong(str);
			long[] list = new long[(int) number];
			list[0] = 2;
			int count = 1;
			if (number == 1) {
				System.out.println("0");
				str = br.readLine();
				isEnd = str == null;
				continue;
			} else if (number == 2) {
				System.out.println("1");
				str = br.readLine();
				isEnd = str == null;
				continue;
			} else {
				for (int i = 3; i <= number; i = i + 2) {
					for (int j = 0; true; j++) {
						;
						if (i % list[j] == 0) {
							break;
						} else if (list[j] >= Math.pow(i, 0.5)) {
							list[count] = (long) i;
							count++;
							break;
						}
					}
				}
				System.out.println(count);
				str = br.readLine();
				isEnd = str == null;
			}
		}
	}
}

Measured memory_bytes: 54880
s = list(input())
k = int(input())

x = [0]*len(s)
for i in range(len(s)-1):
    if (s[i] == s[i+1]) and x[i] == 0:
        x[i+1] = 1


y = [0]*len(s)
if (k > 1) and (s[0] == s[-1]) and (x[-1] == 0):
    y[0] = 1
    for i in range(len(s)-1):
        if (s[i] == s[i+1]) and y[i] == 0:
            y[i+1] = 1
else:
    y = x

if y[-1] == 1:
    z = k//2
    print(sum(x)*(k-z) + sum(y)*z)
else:
    print(sum(x) + sum(y)*(k-1))

Measured memory_bytes: 3064
#include <iostream>
#include <cmath>
#include <iomanip>

#define ld long double

using namespace std;

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

    ld a, b, x, ans;
    cin >> a >> b >> x;
    ld y = x / a / a * 2 - b;

    if (y >= 0)
        ans = atan2(b - y, a);
    else
    {
        y = x / a * 2 / b;
        ans = atan2(b, y);
    }

    cout << fixed << setprecision(20);
    cout << ans * 180 / atan2(0, -1) << "\n";

    return 0;
}


Measured memory_bytes: 256
from sys import stdin

def main():
    from collections import deque
    input = stdin.readline

    h, w = map(int, input().split())
    cm = [["."] * (w + 2) for _ in range(h + 2)]
    que = deque([])
    for i in range(1, h + 1):
        cm[i] = "." + input().rstrip('\n') + "."
    que.append([1, 1])
    while len(que) > 0:
        y, x = que.popleft()
        if (cm[y + 1][x] == "#" and cm[y][x + 1] == "#") or cm[y + 1][x - 1] == "#" or cm[y - 1][x + 1] == "#":
            print('Impossible')
            exit()
        if cm[y + 1][x] == "#":
            que.append([y + 1, x])
        if cm[y][x + 1] == "#":
            que.append([y, x + 1])
    print('Possible')
main()

Measured memory_bytes: 3316
#include <iostream>
#include<cmath>
#include<string>
#include<algorithm>
#include<ctime>
#include<functional>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<map>
#include<set>
#include<tuple>
#include<cassert>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<iomanip>
#include<climits>
#include<typeinfo>
#include<utility>
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,n) for(ll i=0;i<n;i++)
#define For(i,m,n) for(int i=m;i<n;i++)
#define FOR(i,m,n) for(ll i=m;i<n;i++)
double pi = 3.141592653589793238;
using ll = long long;
using namespace std;

ll LGCD(ll x, ll y) { if (x % y == 0) return y;else return LGCD(y, x % y); }
ll LLCM(ll x, ll y) { return x * y / LGCD(x, y); }

int GCD(int x, int y) { if (x % y == 0) return y;else return GCD(y, x % y); }
int LCM(int x, int y) { return x * y / GCD(x, y); }
ll dpcombination[10000][10000];

ll modi = 1000000007;
ll combination(ll n, ll r) {
	if (n == r) { return dpcombination[n][n] = 1; }
	else if (r == 0) { return dpcombination[n][0] = 1; }
	else if (r == 1) { return dpcombination[n][1] = n; }
	else if (dpcombination[n][r]) { return dpcombination[n][r]; }
	else { return dpcombination[n][r] = combination(n - 1, r - 1) % modi + combination(n - 1, r) % modi; }
}

void clockman(int time1) {

	cout << 1.0*(clock() - time1) / CLOCKS_PER_SEC << endl;
	return;
}
//cout << fixed << setprecision(10)

void printVec(std::vector<int> &vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}


int main() {
	int n;
	cin >> n;
	if (n % 1000 == 0)cout << 0 << endl;
	else cout << 1000-n % 1000 << endl;
	
	return 0;
}

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

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

	std::vector<long long int> v(n+1);
	v[0] = 0; 
	for (long long int i = 1; i <= n; ++i)
	{
		cin>>v[i];
	}

	map<long long int,long long int> mp;
	long long int ans=0;
	mp[v[1] + 1]++;
	for (long long int i = 2; i <= n; ++i)
	{	
		if(mp.find(i - v[i]) != mp.end())
			ans+=mp[i - v[i]];
		mp[v[i] + i]++;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 16960
import sys, array, re, functools
input = lambda: sys.stdin.readline()
@functools.lru_cache(maxsize = 10000)

def Main():
  a, b = map(int, input().split())
  ans  = a + b
  if( ans < 24):
    print(ans)
  elif ans  == 24:
    print(0)
  else:
    print(ans - 24)
  
if __name__ == '__main__':
  Main()

Measured memory_bytes: 4084
#include <stdio.h>


int main(void)
{
	char word[1201];
	int alphabet[26] = {0};
	int i;

	while(scanf("%s", word)!=EOF){

		for(i=0;word[i]!='\0';i++){
			if('A'<=word[i] && word[i]<='Z')
				alphabet[word[i]-'A']++;
			if('a'<=word[i] && word[i]<='z')
				alphabet[word[i]-'a']++;
		}
	}

	for(i=0;i<26;i++)
		printf("%c : %d\n", 'a'+i, alphabet[i]);

	return 0;
}

Measured memory_bytes: 540
#include<cstdio>
#define ll long long
using namespace std;
int s[1005000];

int main(){
	int n,K;
	scanf("%d%d",&n,&K);
	ll ans=0;
	for (int i=1;i<=n;i++)
	s[i%K]++;
	for (int i=1;i<=n;i++)
	if ((K-i%K)*2==K)ans+=1ll*s[K-i%K]*s[K-i%K];else 
	if (i%K==0) ans+=1ll*s[0]*s[0];
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 512
package main

import (
	"fmt"
	"sort"
)

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

	res := solve(n)
	ans := len(res)
	fmt.Println(ans)
}

func solve(n int) []int {
	var res []int

	divs1 := divisors(n - 1)
	res = divs1[1:]

	divs := divisors(n)
	for _, k := range divs {
		if k == 1 {
			continue
		}
		m := n
		for m%k == 0 {
			m /= k
		}
		if m%k == 1 {
			res = append(res, k)
		}
	}
	sort.Ints(res)

	return res
}

func divisors(n int) []int {
	res := make([]int, 0)
	for i := 1; i*i <= n; i++ {
		if n%i == 0 {
			res = append(res, i)
			if n/i != i {
				res = append(res, n/i)
			}
		}
	}
	sort.Ints(res)

	return res
}


Measured memory_bytes: 2088
#!/usr/bin/env python3
import sys
import statistics

def F(b,A):
    L = [abs(a-(b+i+1)) for i,a in enumerate(A)]
    return sum(L)

def solve(N: int, A: "List[int]"):
    L = [ a-(i+1) for i,a in enumerate(A) ]
    medl = statistics.median_low(L)
    medh = statistics.median_high(L)

    print(min(F(medl,A),F(medh,A)))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


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

using namespace std;


void SelectionSort(vector<int> v){
    int cnt=0;
    for(int i=0;i<v.size();i++){
        int mini=i;
        for(int j=i;j<v.size();j++){
            if(v[j]<v[mini]){
                mini=j;
            }
        }

        if(i!=mini){
            int tmp=v[i];
            v[i]=v[mini];
            v[mini]=tmp;
            cnt++;
        }
       
    }
    for(int i=0;i<v.size()-1;i++){
        cout<<v[i]<<" ";
    }
    cout<<v[v.size()-1]<<endl;
    cout<<cnt<<endl;
}


int main(){
    int n;
    vector<int> v;
    cin>>n;
    for(int i=0;i<n;i++){
        int tmp;
        cin>>tmp;
        v.push_back(tmp);
    }
    SelectionSort(v);
    return 0;
}

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

using namespace std;

#define N 10000+1000
  
int main() {
  bool dp[N] = {0};
  int n; cin >> n;
  dp[0] = 1;
  while(n--) {
    int s; cin >> s;
    for(int i = 10000; i >= 0; i--) {
      if (!dp[i]) continue;
      dp[i+s] = 1;
    }
  }
  int res = 10000;
  while(res && (!dp[res] || (dp[res] && res%10==0))) res--;
  cout << res << endl;

  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <array>
#include <algorithm>


using namespace std;

int main(int argc, char* argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    long long a;
    long long minValue = 1000000;
    long long maxValue = -1000000;
    long long sum = 0;

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a;
        if ( a < minValue ) minValue = a;
        if ( a > maxValue ) maxValue = a;
        sum += a;
    }

    cout << minValue << " " << maxValue << " " << sum << endl;
    return 0;
}


Measured memory_bytes: 3216
#include<bits/stdc++.h>
#define rep(i, n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
 
int main(void){
    int h, w, a, b;
    cin>>h>>w>>a>>b;
    vector<vector<int> > v(h, vector<int>(w));
    if(w/2>=a && h/2>=b){
        vector<int> s1(w);
        vector<int> s2(w);
        rep(i, a){
            s1[i] = 1;
        }
        for(int i = a;i<=w-1;i++){
            s2[i] = 1;
        }
        rep(i, b){
            v[i] = s1;
        }
        for(int i = b;i<=h-1;i++){
            v[i] = s2;
        }
        rep(i, h){
            rep(j, w) cout<<v[i][j];
            cout<<endl;
        }
    }
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 5120
#include<cstdio>
#include<algorithm>
using namespace std;
int n, w[101000], C[101000], res;
int main() {
	int i;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d", &w[i]);
		if (w[i] > n)continue;
		if (w[i] <= n)C[w[i]]++;
	}
	for (i = 1; i <= n; i++) {
		if (C[i] >= i)res += i;
	}
	printf("%d\n", n - res);
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
 
	public Main() {
		// TODO 自動生成されたコンストラクター・スタブ
	}
 
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n,k,count,m,index;
		long a,b,a2,b2,common,answer,c,i,j;
		String s,t;
		
			// 整数の入力
		
		a = sc.nextLong();
		b = sc.nextLong();
		sc.close();
		count=0;
		if(a==b) {
			common=a;
		}
		else {
			if(a<b) {
				c=a;
				a=b;
				b=c;
			}
			LoopA: for(;;) {
				c=a%b;
				if(c==0) {
					common=b;
					break LoopA;
				}
				a=b;
				b=c;
			}
		}
		//System.out.print(common);
		answer=0L;
		if(common==1) answer=1L; 
		else {
			answer=1L;
			LoopC: for(i=2;i<=common;) {
				if(common%i==0) {
					answer++;
					LoopB: for(;;) {
						common=common/i;
						if(common%i>0) break LoopB;
					}
				}
				else if(i*i>common) {
					answer++;
					break LoopC;
				}
				if(i==2)i=3;
				else if(i==3)i=5;
				else if(i==5)i=7;
				else if(i==7)i=11;
				else if(i==11)i=13;
				else if(i==13)i=17;
				else if(i%3==1) i=i+4;
				else if(i%5==3) i=i+4;
				else if(i%7==5) i=i+4;
				else if(i%11==9) i=i+4;
				else if(i%13==11) i=i+4;
				else i=i+2;
			}
		}
		System.out.print(answer);

			// 出力
 
	}
}	

Measured memory_bytes: 23636
import sys
input = sys.stdin.readline
ri = lambda: int(input())
#rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rl = lambda: map(int,input().split())
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7

N = ri()
coler = [0]*N
ME = [None]*N
MO = [None]*N
UVW=[]
for i in range(N-1):
    u,v,w = rl()
    u -= 1
    v -= 1
    if w%2 == 1:
        if MO[u] == None:
            MO[u] = [v]
        else:
            MO[u].append(v)
        if MO[v] == None:
            MO[v] = [u]
        else:
            MO[v].append(u)
    else:
        if ME[u] == None:
            ME[u] = [v]
        else:
            ME[u].append(v)
        if ME[v] == None:
            ME[v] = [u]
        else:
            ME[v].append(u)

from collections import deque
q = deque([0])
visited = [False]*N
while len(q)>0:
    n = q.popleft()
    if visited[n] == True:
        continue
    else:
        visited[n] = True
    v = coler[n]
    e = ME[n]
    if not e is None:
        q.extend(e)
        for en in e:
            coler[en] = v
    o = MO[n]
    if not o is None:
        v += 1
        q.extend(o)
        for on in o:
            coler[on] = v

for c in coler:
    print(c%2)
    



Measured memory_bytes: 28708
/*"Success isn't permanent, failure isn't fatal,
                                      it's the courage to continue that counts"*/
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define ll long long 
#define scn(n) scanf("%d",&n)
#define lscn(n) scanf("%lld",&n)
#define lpri(n) printf("%lld",n)
#define pri(n) printf("%d",n)
#define pln() printf("\n")
#define priln(n) printf("%d\n",n)
#define lpriln(n) printf("%lld\n",n)
#define rep(i,init,n) for(int i=init;i<n;i++)
#define pb push_back     
#define mp make_pair
#define F first
#define S second
#define gcd __gcd
#define inf INT_MAX
#define ninf INT_MIN
const int mod=1e9+7;         
const int N=5e2+4;

int main()
{
	ll sum=0;

	int n;

	scn(n);

	rep(i,1,n+1)
	if(i%3!=0 and i%5!=0)
	sum+=i;

	lpri(sum);
	
    return 0;
}

Measured memory_bytes: 3816
#include <iostream>
#include <string>

using namespace std;

int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  for (int i = 0; i < s.size(); ++i) {
    char x = s[i];
    x = (((x - 'A') + n) % 26) + 'A';
    s[i] = x;
  }
  cout << s << endl;
  return 0;
}

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

const int mod = 1e9+7;
void tlfclwx(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
const int maxn=1e6+10;


int main()
{
   ll a, b; cin >> a >> b;
   ll c = a/__gcd(a, b)*b;
   cout << c << endl;
}


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

int main()
{
  string s;
  cin >> s;
  int start, end, answer;
  for (int i = 0; i < s.size(); i++) {
    if (s.at(i) == 'A') {
      start = i;
      break;
    }
  }
  for (int i = 0; i < s.size(); i++) {
    if (s.at(i) == 'Z') {
      end = i;
    } 
  }
  answer = end - start + 1;
  cout << answer << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#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 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 IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;


signed main() {
  int N, x; 
  cin >> N >> x;

  if(x == 1 || x == 2*N-1){
    No; return 0;
  }

  Yes;

  if(N == 2){
    cout << "1 2 3" << endl;
    return 0;
  }
  
  vector<bool> used(N*2+10, false);
  vector<int> ans(N*2-1, 0);
  if(x != 2){
    ans[N-2] = x-1;
    ans[N-1] = x;
    ans[N+0] = x+1;
    ans[N+1] = x-2;
    REP(i, 4) used[x-2+i] = true;
  }else{
    ans[N-2] = 3;
    ans[N-1] = 2;
    ans[N+0] = 1;
    ans[N+1] = 4;
    REP(i, 4) used[i+1] = true;
  }

  int now = 1;
  REP(i, N-2){
    while(used[now]) now++;
    ans[i] = now;
    used[now++] = true;
  }
  FOR(i, N+2, 2*N-1){
    while(used[now]) now++;
    ans[i] = now;
    used[now++] = true;
  }

  REP(i, 2*N-1) cout << ans[i] << endl;

  return 0;
}

Measured memory_bytes: 3072
//大文字->小文字 tolower(),逆はtoupper()
//int a = stoi(c); 文字列をintへ
//途中の出力をそのまま残さない
//数値計算 個数以外はdouble
//map<キー,値> p は辞書。p[キー] = 値
//map 全探索
//auto begin = p.begin(), end = p.end();
//for (auto it = begin; it != end; it++) {}
//mapのキー：it->first mapのバリュー：it->second
//絶対値 abs()
//入力は空白で切れる
//大文字判定 isupper(文字) 小文字判定 islower(文字)
//do{}while(next_permutation(ALL(配列)))
//while(N)で回すとき、Nはコピーを作っておく
//小文字に対応する文字コード：S[i] - 'a'
//文字コード→小文字：(char)(数字+'a')
//グラフの距離:隣接行列で扱う
//等価なものに変換する思考
#include <bits/stdc++.h>
#define rep(i,N) for(int i = 0; i < N;i++)
#define ALL(a) (a).begin(),(a).end()
#define ll long long int
using namespace std;

// K進数でのNの桁数
ll dig(ll N,ll K) {
	ll dig = 0;
	while (N) {
		dig++;
		N /= K;
	}
	return dig;
}
// a,bの最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b,a%b);
}

ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

//nC2の計算
ll C(ll N) {
	return N * (N - 1) / 2;
}

//円周率
const double PI = 3.14159265358979323846;

int main() {
	ll N, M; cin >> N >> M;
	vector<ll> a(M), b(M); rep(i, M)cin >> a[i] >> b[i];

	bool x[N + 1] = {}, y[N + 1] = {};
	rep(i, M) {
		if (a[i] == 1) x[b[i]] = 1;
		if (b[i] == N) y[a[i]] = 1;
	}

	for(int i = 2; i <= N-1;i++){
		if (x[i] == 1 && y[i] == 1) {
			cout << "POSSIBLE" << endl;
			return 0;
		}
	}

	cout << "IMPOSSIBLE" << endl;
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0;i<n;++i)
#define FOR(i, a, b) for(int i=a;i<b;++i)
#define RFOR(i, a, b) for (int i=a;i>=b;--i)
#define ll long long
#define all(a) a.begin(),a.end()
#define ull unsigned long long
#define pb(x) push_back(x)
#define dbg(x) cout<<#x<<" : "<<(x)<<endl;
using namespace std;
const int INF = 1500000000;
const double PI = 3.14159265359;
const int mod = 1000000000 + 7;

int n, s[1000];

void solve() {
  int res = 0, mins = 1000, maxs = 0;
  rep(i, n) {
    res += s[i];
    maxs = max(maxs, s[i]);
    mins = min(mins, s[i]);
  }
  res -= maxs;
  res -= mins;
  printf("%d\n", res / (n-2));
}

int main() {
  while(true) {
    scanf("%d", &n);
    if (!n) break;
    rep(i, n) scanf("%d", &s[i]);
    solve();
  }
  return 0;
}

Measured memory_bytes: 3200