akhauriyash/Code-Regression huggingface dataset:
def main():
    n, m = map(int, input().split())
    ans = [-1]*n
    for _ in range(m):
        s, c = map(int, input().split())
        if ans[s-1] == -1:
            ans[s-1] = c
        elif ans[s-1] != -1 and ans[s-1] != c:
            print(-1)
            exit()

    if n == 1:
        if ans[0] == -1:
            ans[0] = 0
    else:
        if ans[0] == 0:
            print(-1)
            exit()

        if ans[0] == -1:
            ans[0] = 1

        for i in range(1, n):
            if ans[i] == -1:
                ans[i] = 0
    print(*ans, sep="")


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<cmath>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }

double const toRad = std::acos(-1)/1.8e2;
double a, b, S;

bool isOK(double deg) {
  double rad = deg*toRad;
  double s = std::sin(rad);
  if(s <= 1e-12) return true; // should be full
  double c = std::cos(rad);
  if(c <= 1e-12) return false; // should be zero
  double h = b*c/s;
  double cS;
  if(h <= a) cS = b*h*0.5;
  else {
    h = a*s/c;
    cS = a*(b - h*0.5);
  }
  //return S/cS-1.0 <= 1e-8;
  return S < cS;
}

int main() {
  std::cout << std::setprecision(10) << std::fixed;
  double x; std::cin >> a >> b >> x;
  S = x/a;
  double ok = 0.0, ng = 90.0;
  while(ng-ok > 1e-6) {
    double mid = (ok+ng)*0.5;
    if(isOK(mid)) ok = mid; else ng = mid;
  }
  fin((ok+ng)*0.5);
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
 class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int n = s.length();
    String x , y;
    x = s.substring(0,n/2);
    y = s.substring(n/2+1,n);
    if(x.equals(y)){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }

  }
}


Measured memory_bytes: 23764
// Problem: A - Rainy Season
// Contest: AtCoder - AtCoder Beginner Contest 175
// URL: https://atcoder.jp/contests/abc175/tasks/abc175_a
// Parsed on: 2020-09-02 13:00:06
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <algorithm>
#include <cmath>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);

using namespace std;

int main() {
    string s;
    cin >> s;
    if (s == "SSS")
        cout << "0";
    else if (s == "SSR")
        cout << "1";
    else if (s == "SRS")
        cout << "1";
    else if (s == "SRR")
        cout << "2";
    else if (s == "RSS")
        cout << "1";
    else if (s == "RSR")
        cout << "1";
    else if (s == "RRS")
        cout << "2";
    else if (s == "RRR")
        cout << "3";
    else
        return -2;
    return 0;
}


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

int main() {
  std::string N;
  std::cin >> N;

  long long ans = 0;
  int carry = 0;

  for (int i=N.size(); i>0; i--) {
    int n = N[i-1] - '0';
    // std::cerr << n << '(' << carry << ')';
    n += carry;
    if (n > 9) {
      carry = 1;
    } else if (n > 5) {
      carry = 1;
      ans += 10 - n;
    } else {
      if (i>1 && n==5) {
        int m = N[i-2] - '0';
        if (m > 4) {
          carry = 1;
          ans += n;
        } else {
          carry = 0;
          ans += n;
        }
      } else {
        carry = 0;
        ans += n;
      }
    }
    // std::cerr << ans << '\n';
  }

  ans += carry;

  std::cout << ans << std::endl;

  return 0;
}


Measured memory_bytes: 1412
h,w = (int(i) for i in input().split())
s = [input() for i in range(h)]

wl = [0]*h*w
hl = [0]*h*w
for j in range(h):
    for i in range(w):
        if s[j][i] == "#":
            continue

        # 横方向
        if i != 0 and wl[w*j+i-1] != 0:
            wl[w*j+i] = wl[w*j+i-1]
        else:
            if "#" in s[j][i:]:
                wl[w*j+i] = s[j][i:].index("#")
            else:
                wl[w*j+i] = w-i

        # 縦方向
        if j != 0 and hl[w*(j-1)+i] != 0:
            hl[w*j+i] = hl[w*(j-1)+i]
        else:
            for y in range(j,h):
                if s[y][i] == "#":
                    break
                hl[w*j+i] = y-j+1
            

res = [x + y for (x, y) in zip(wl, hl)]

print(max(res)-1)

Measured memory_bytes: 241144
#include<iostream>
#include<string>
#include<cstdlib>
#include<math.h>
using namespace std;
int main(void){
    long long a,b,K;
    cin >> a >> b >> K;
    
    for(int j=1;j<=K;j++){
        if(j%2){
            if(a%2){
                a--;
            }
            a=a/2;
            b+=a;
        }else{
            if(b%2){
                b--;
            }
            b=b/2;
            a+=b;
        }
    }
    printf("%lld %lld",a,b);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007;	// 998244353
using ll = long long;
using namespace std;

struct query{
	int vert;
	int dist;
	int col;
};

vector<int> graph[100010];
vector<query> ql;
// farbe[v] := 頂点 v は何色か？（初期値 0）
int farbe[100010];
// dmax[v] := 頂点 v から距離いくつまでのノードが塗られているか？
int dmax[100010];

void init(){
	for( int i = 0; i < 100010; ++i ) dmax[i] = -1;
}

int main(){
	init();
	int n, m; cin >> n >> m;
	for( int i = 0; i < m; ++i ){
		int a, b; cin >> a >> b; --a; --b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	int qnum; cin >> qnum;
	for( int i = 0; i < qnum; ++i ){
		int vt, dt, ct; cin >> vt >> dt >> ct; --vt;
		ql.push_back((query){vt, dt, ct});
	}
	reverse( ql.begin(), ql.end() );
	for( int i = 0; i < qnum; ++i ){
		query &q = ql[i];
		// pair<a, b> := 頂点 a で距離が b
		queue<pair<int, int>> que;
		que.emplace(q.vert, q.dist);
		while( !que.empty() ){
			auto p = que.front(); que.pop();
			int v = p.first, d = p.second;
			if( d <= dmax[v] ) continue;
			dmax[v] = d;
			if( farbe[v] == 0 ) farbe[v] = q.col;
			for( auto next : graph[v] ){
				que.emplace(next, d-1);
			} 
		}
	}
	for( int i = 0; i < n; ++i ){
		cout << farbe[i] << endl;
	}
}

Measured memory_bytes: 9328
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=500005;

int len;
char N[MAXN];
int cnt[15];

int main()
{
    scanf("%s",N);
    len=strlen(N);
    reverse(N,N+len);
    for(int i=0;i<len;i++)
    {
        N[i]-='0';
        cnt[N[i]]++;
    }
    int ans=0;
    int tmp=len;
    int num=-1,pos=-1;
    for(;;)
    {
        int i=len-1;
        if(N[i]==num)
            i=pos-1;
        else
            while(i>0&&N[i-1]>=N[i])
                i--;
        ans++;
        if(i==0||cnt[N[0]]==len)
            break;
        while(N[i]==N[i+1])
            i++;
        num=N[i],pos=i;
        for(int j=len-1;j>=i;j--)
            cnt[N[j]]--;
        len=i;
        N[len]=0;
        cnt[N[0]]--;
        N[0]++;
        cnt[N[0]]++;
        for(int j=0;N[j]==10;j++)
        {
            cnt[N[j]]--;cnt[N[j+1]]--;
            N[j]=0,N[j+1]++;
            cnt[N[j]]++;cnt[N[j+1]]++;
        }
        /*for(int j=len;j<tmp;j++)
            putchar(' ');
        for(int j=len-1;j>=0;j--)
            putchar(N[j]+'0');
        putchar('\n');*/
    }
    printf("%d\n",ans);

    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int K, N, A[200010], B[200010];

    cin >> K >> N;

    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    sort(A, A+N);

    for (int i = 0; i < N-1; i++)
    {
        B[i] = (A[i+1] - A[i]);
    }

    B[N-1] = K - A[N-1] + A[0];

    long long int D = 0;

    for (int i = 0; i < N; i++)
    {
        D += B[i];
    }

    D -= *max_element(B, B+N);

    cout << D << "\n";

    return 0;
}

Measured memory_bytes: 1920
// D - Xor Sum 4
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rp(i,s,e) for(int i=(s);i<(e);++i)
#define MOD 1000000007

int main(){
	int N; cin>>N;
	ll Z[60], O[60]; rp(i,0,60) Z[i] = O[i] = 0;
	rp(i, 0, N){
		ll a; scanf("%lld",&a);
		rp(j, 0, 60) if((a>>j)&1) O[j]++; else Z[j]++;
	}
	ll ans = 0;
	rp(i, 0, 60) ans = (ans + (Z[i]*O[i] % MOD) * ((1LL<<i) % MOD)) % MOD;
	cout<< ans <<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>

using namespace std;

int main(){
    int N, M, n, m;

    cin >> N >> M;
    
    N --;
    M --;
    n = N;
    m = M;

    while(n){
        if(n == -1){
            N = 0;
            break;
        }
        n --;
        N += n;
    }
    while(m){
        if(m == -1){
            M = 0;
            break;
        }
        m --;
        M += m;
    }

    cout << N + M << endl;

    return 0;
}

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

#pragma GCC optimize("O3")
#define MOD 1000000007
#define pb push_back
#define fi first
#define se second
#define fr front()
#define ba back()
#define tp top()
#define mem(x,n) memset(x,n,sizeof(x));
#define sz(x) (int)((x).size())
#define all(x) (x).begin(),(x).end()
#define foreach(it,l) for(auto it=l.begin();it!=l.end();it++)
#define pnl printf("\n")
#define len(x) x.length()

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
typedef pair<pii,int> piii;
const int inf=(1<<30);
const LL llinf=(1ll<<60);
const double eps=(1e-10);
//const double pi=2*acos(0.0);
//const double GOLD=((1+sqrt(5))/2);
const int xx[8]={1,0,-1,0,1,-1,1,-1};
const int yy[8]={0,1,0,-1,-1,1,1,-1};

/* \( ·w·)~ Clapie ~(·w· )/ */

int n,W;
LL wei[105],val[105];
LL memo[105][100005];

LL dp(int idx,int weight){
	if(weight>W) return -inf;
	if(idx<0) return 0;
	if(memo[idx][weight]!=-1) return memo[idx][weight];
	
	return memo[idx][weight]=max(dp(idx-1,weight+wei[idx])+val[idx],dp(idx-1,weight));
}

int main(){
	mem(memo,-1);
	scanf("%d%d",&n,&W);
	for(int i=0;i<n;i++){
		scanf("%lld%lld",&wei[i],&val[i]);
	}
	
	LL ans=dp(n-1,0);
	printf("%lld\n",ans);
}

Measured memory_bytes: 82812
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define check(v) rep(i,v.size()) cout << v[i] << " ";\
cout << endl
#define INF 1e9
typedef long long ll;
using namespace std;
//オーバーフローに気をつけろよおおおおおお
//確認忘れるなよおおおおおお

int main() {
    string s; cin >> s;
    sort(ALL(s));
    bool a = true;
    for(int i = 0; i < s.size(); i += 2){
        if(s[i]!=s[i+1]){
            a = false;
        }
    }
    if(a) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
int main (void) {
    ll x, y;

    cin >> x >> y;

    ll ans = 0;
    if (x > y) {
        x *= -1;
        ans++;
    }
    ans += abs(abs(y) - abs(x));
    if (x * y < 0) {
        ans++;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
int main(){
  int n;
  std::cin>>n;
  vector <int> d;
  int i,input;
  for(i=0;i<n;i++)
  {
    std::cin>>input;
    d.push_back(input);
  }
  int j=0,sum=0;
  for(i=0;i<n-1;i++)
  {
    for(j=i+1;j<n;j++)
      sum+=d[i]*d[j];
  }
  std::cout<<sum;
}

Measured memory_bytes: 256
n,m = map(int, input().split())
l = [0] * (n+1)
for _ in range(m):
  a,b = map(int, input().split())
  if a == 1: l[b] += 1
  if b == n: l[a] += 1

print("POSSIBLE" if 2 in l else "IMPOSSIBLE")

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

int main() {
    int N;
    string S;
    cin >> N >> S;

    int cnt[N + 1];
    // i文字目までにEがいくつあるか

    cnt[0] = 0;
    for (int i = 0; i < N; ++i) {
        cnt[i + 1] = cnt[i];
        if (S[i] == 'E') ++cnt[i + 1];
    }

    int ans = N;
    for (int i = 1; i <= N; ++i) {
        // 自分より西にいて西を向いている人が
        //  (i-1)-cnt[i-1]人
        // 自分より東にいて東を向いている人が
        // cnt[N]-cnt[i]人
        ans = min(ans, i - 1 - cnt[i - 1] + cnt[N] - cnt[i]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1796
#include <cstdio>
#include <sstream>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <iostream>
#include <fstream>
#include <numeric>
#include <string>
#include <vector>
#include <cstring>
#include <map>
#include <iterator>
#include <iomanip>
#include <unordered_map>

using namespace std;

#define MAX 30001
#define ll long long int



int main()
{
   ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll n,a,b,cycle,ans=0;
    cin>>n>>a>>b;
    cycle=n/(a+b);
    ans=cycle*a+min(n-cycle*(a+b),a);
    cout<<ans;
}


Measured memory_bytes: 256
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//Abdulhamid Han
//Bismillahirrahmanirrahim
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█▄█
//█─█─█▄─█▄─█─█─█─█

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

typedef long long lo;
typedef pair< lo,lo > PII;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 1000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;

int n,m,b[li],a[li],k,flag,t;
int cev;
string s;
vector<int> v;

int main(void){
	fio();
	cin>>s;
	for(int i=0;i<(int)s.size();i++){
		if(s[i]!=s[(int)s.size()-i-1]){s[i]=s[(int)s.size()-i-1];cev++;}
	}
	cout<<cev<<endl;
	return 0;
}



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

int main(){
    int n,m,wa=0,ac=0;
    cin >> n >> m;
    vector<int> P(n);
    vector<int> WA(n);
    for(int i=0;i<m;i++){
        int p;
        string s;
        cin >> p >> s;
        p--;
        if(P[p] == 0 && s[0]=='W'){
            WA[p]++;
        }else if(P[p] == 0 && s[0]=='A'){
            P[p] = 1;
            wa += WA[p];
            ac++;
        }
    }
    cout << ac << " " << wa << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cmath>

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
typedef long long ll;
typedef unsigned long long ull;

int A[80][80];
int B[80][80];
vector<bool> dp[80][80];

int main()
{
	int H, W;

	cin >> H >> W;
	rep(i, H) rep(j, W) cin >> A[i][j];
	rep(i, H) rep(j, W) cin >> B[i][j];

	rep(i, H) rep(j, W) {
		int diff = abs(A[i][j] - B[i][j]);
		int k_max = 80 * (1 + i + j);
		dp[i][j].resize(k_max + 1, false);

		if (i == 0 && j == 0) {
			repc(k, 0, k_max) {
				if (k == diff) dp[i][j][k] = true;
			}
			continue;
		}

		if (i > 0) {
			repc(k, 0, k_max - 80) {
				if (dp[i - 1][j][k]) {
					dp[i][j][abs(k - diff)] = true;
					dp[i][j][k + diff] = true;
				}
			}
		}

		if (j > 0) {
			repc(k, 0, k_max - 80) {
				if (dp[i][j - 1][k]) {
					dp[i][j][abs(k - diff)] = true;
					dp[i][j][k + diff] = true;
				}
			}
		}
	}

	repc(i, 0, 80 * (H + W - 1)) {
		if (dp[H - 1][W - 1][i]) {
			cout << i << endl;
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 5888
#include <stdio.h>
 
void set(int i, char str[], int count[]);
void pull3(int count[]);
 
int main(void) {
    char str[14];
    int count[9];
    int i, j, k, l, m;
    _Bool comp;
    _Bool first;
    while (scanf("%s", str) != EOF) {
        first = 0;
        for (i = 0; i < 9; i++) {
            comp = 0;
             
            for (j = 0; j < 9 && !comp; j++) {
                set(i, str, count);
                for (k = 0; k < 9; k++)
                    if (count[k] > 4)
                        break;
                if (k != 9)
                    continue;
                if (count[j] >= 2) {
                    for (m = 0; m < 2; m++) {
                        set(i, str, count);
                        count[j] -= 2;
                        if (m == 0)
                            pull3(count);
                        for (k = 0; k < 9; k++) {
                            for (l = count[k]; l > 0; l--) {
                                if ( k < 7 && count[k] > 0 && count[k+1] && count[k+2]) {
                                    count[k]--;count[k+1]--;count[k+2]--;
                                }
                            }
                            if (count[k] > 0)
                                break;
                        }
                        if (m == 1)
                            pull3(count);
                         
                        for (k = 0; k < 9; k++) {
                            if (count[k] > 0)
                                break;
                        }
                        if (k == 9)
                            comp = 1;
                    }
                }
            }
             
            if (comp) {
                if (first)
                    printf(" ");
                printf("%d", i+1);
                first = 1;
            }
        }
        if (!first)
            printf("0");
        printf("\n");
    }
    return 0;
}
 
void set(int i, char str[], int count[]) {
    int j;
    for (j = 0; j < 9; j++)
        count[j] = 0;
    for (j = 0; j < 13; j++)
        count[str[j]-'1']++;
    count[i]++;
}
 
void pull3(int count[]) {
    int k;
    for (k = 0; k < 9; k++) {
        if (count[k] >= 3)
            count[k] -= 3;
    }
}



Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i < n; i++)
#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define pi 3.1415926536
#define ff first
#define ss second
#define pq priority_queue
#define ipair pair<int, int> s
#define lpair pair<LL, LL>
#define MP make_pair
#define INF 2147483647
#define _INF -2147483647
#define MM multimap
#define PB push_back
#define MAXN 100004

int main() {
    int N, D;
    cin >> N >> D;
    vvi X(N, vi(D));
    rep(i, 0, N) {
        rep(j, 0, D) {
            cin >> X[i][j];
        }
    }
    int ans = 0;
    rep(i, 0, N) {
        rep(j, i + 1, N) {
            int norm = 0;
            rep(k, 0, D) {
                int diff = abs(X[i][k] - X[j][k]);
                norm += diff * diff;
            }
            // check whether norm = k for some k
            bool flag = false;
            rep(k, 0, norm + 1) {
                if (k * k == norm) {
                    flag = true;
                }
            }
            if (flag) ++ans;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here! 
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        
        if (str.equals("SUN")) {
            System.out.println(7);
        } else if (str.equals("MON")) {
            System.out.println(6);
        } else if (str.equals("TUE")) {
            System.out.println(5);
        } else if (str.equals("WED")) {
            System.out.println(4);
        } else if (str.equals("THU")) {
            System.out.println(3);
        } else if (str.equals("FRI")) {
            System.out.println(2);
        } else {
            System.out.println(1);
        }
    }
}

Measured memory_bytes: 21588
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = (1e+9)+7;

ll mpow(ll base, ll p){
    ll x = 1;
    while(p){
        if(p%2 == 1){
            x = (x * base) % MOD;
            p--;
        }
        base = (base * base) % MOD;
        p /= 2;
    }
    return x;
}

int main(){
    ll n,a,b; 
    cin >> n >> a >> b;
    ll mx = mpow(2, n)-1;
    ll vx = 1;
    for(int i=0;i<a;i++){
        vx = (vx * (n-i)) %MOD;
    }
    for(int i=1;i<=a;i++){
        vx = (vx * mpow(i, MOD-2)) %MOD;
    }
    mx -= vx;
    vx = 1;
    for(int i=0;i<b;i++){
        vx = (vx * (n-i)) %MOD;
    }
    for(int i=1;i<=b;i++){
        vx = (vx * mpow(i, MOD-2)) %MOD;
    }
    mx -= vx;
    while(mx < 0) mx += MOD;
    cout << mx << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define swap(type,a,b) do{type t=a;a=b;b=t;}while(0);
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define ll long long
#define MOD 1000000007
#define FOR(i,a,n) for(i=a;i<n;i++)
typedef struct{
	int x,y,num;
}Pos;
int comp1(const void* a,const void* b){
	return ((Pos*)a)->x - ((Pos*)b)->x;
}
int comp2(const void *a,const void *b){
	return ((Pos*)a)->y - ((Pos*)b)->y;
}
//Union-Find
int *par;
int *rank;
void union_init(int size){
	int i;
	par=calloc(size,sizeof(int));
	rank=calloc(size,sizeof(int));
	FOR(i,0,size) par[i]=i;
	return;
}
int root(int a){
	if(par[a]==a) return a;
	else{
		par[a]=root(par[a]);
		return par[a];
	}
}
int is_same(int a,int b){
	return root(a)==root(b);
}
void unite(int a,int b){
	a=root(a);
	b=root(b);
	if(a==b) return;
	if(rank[a]>rank[b])
	    par[b]=a;
	else{
		par[a]=b;
		if(rank[a]==rank[b]) rank[b]++;
	}
	return;
}
void delete_union(){
	free(par);
	free(rank);
	return;
}

typedef struct{
	int s,t,cost;
} Edge;
int comp(const void *a,const void *b){
	return ((Edge*)a)->cost > ((Edge*)b)->cost?1:-1;
};
ll kruscal(Edge *edge,int V,int E){
	int i,cnt=0;
	ll res=0;
	Edge e;
	qsort(edge,E,sizeof(Edge),comp);
	union_init(V);
	FOR(i,0,E){
		e=edge[i];
		if(!is_same(e.s,e.t)){
			unite(e.s,e.t);
			res+=e.cost,cnt++;
		}
	}
	delete_union();
	return cnt==V-1?res:-1;
}
Edge edge[200000];
Pos a[100000];
int main(void)
{
	int n,i;
	scanf("%d",&n);
	FOR(i,0,n){
		scanf("%d%d",&a[i].x,&a[i].y);
		a[i].num=i;
	}
	qsort(a,n,sizeof(Pos),comp1);
	FOR(i,0,n-1) edge[i].s=a[i].num,edge[i].t=a[i+1].num,edge[i].cost=a[i+1].x-a[i].x;
	qsort(a,n,sizeof(Pos),comp2);
	FOR(i,0,n-1) edge[i+n-1].s=a[i].num,edge[i+n-1].t=a[i+1].num,edge[i+n-1].cost=a[i+1].y-a[i].y;
	printf("%lld\n",kruscal(edge,n,2*(n-1)));
	return 0;
}


Measured memory_bytes: 7144
import sys
sys.setrecursionlimit(10**6)

N = int(input())
paths = [dict() for i in range(N + 1)]
for i in range(N-1):
    u, v, w = map(int,input().split())
    paths[u][v] = w
    paths[v][u] = w

node_colors = [-1] * (N+1)

def route(last, now, dist):
    for next_node, next_distance in zip(paths[now].keys(), paths[now].values()):
        node_colors[next_node] = (dist + next_distance) % 2
        if next_node != last:
            route(now, next_node, dist + next_distance)

node_colors[1] = 0

route(0, 1, 0)

for i in range(N):
    print(node_colors[i+1])


Measured memory_bytes: 102940
# -*- coding: utf-8 -*-
"""
Created on Mon Apr 30 11:23:30 2018
ALDS1-4a most simple implementation using the features of the python
@author: maezawa
"""

n = int(input())
s = map(int, input().split())
q = int(input())
t = map(int, input().split())

s_set = set(s)
t_set = set(t)
sandt = s_set & t_set
print(len(sandt))


Measured memory_bytes: 6060
#include <algorithm>
#include <array>
#include <deque>
#include <functional>
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#define ll long long int
#define FOR(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n)

using namespace std;

int main() {
    int n;
    cin >> n;
    string s[n];
    int ac = 0, wa = 0, tle = 0, re = 0;
    REP(i, n) {
        cin >> s[i];
        if (s[i] == "AC") {
            ac++;
        } else if (s[i] == "WA") {
            wa++;
        } else if (s[i] == "TLE") {
            tle++;
        } else {
            re++;
        }
    }
    cout << "AC x " << ac << endl;
    cout << "WA x " << wa << endl;
    cout << "TLE x " << tle << endl;
    cout << "RE x " << re << endl;
    return 0;
}


Measured memory_bytes: 6708
#include<bits/stdc++.h>
#define rep(i, n) for(int (i)=0 ;i <(n); ++(i))
#define REP(i,m,n) for(int (i) = (m); (i) <= (n); ++(i))
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)? "YES":"NO")
typedef long long ll;
using namespace std;

int main() {
  int a, p;
  cin >> a >> p;
  p = p + a*3;
  int ans = p/2;
  cout << ans << endl;
  return 0;
}

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

const int maxn = 100010, P = 1000000007;
int n, m, fact[maxn];

int main() {
    for (int i = fact[0] = 1; i <= 100000; i++) {
        fact[i] = 1LL * i * fact[i - 1] % P;
    }
    scanf("%d %d", &n, &m);
    if (n == m) printf("%d\n", 2LL * fact[n] * fact[m] % P), exit(0);
    if (abs(n - m) == 1) printf("%d\n", 1LL * fact[n] * fact[m] % P);
    else printf("0\n");
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <limits>
#include <sstream>
#include <fstream>
#include <climits>
#include <map>
#include <numeric>
#include <functional>

typedef signed char        int8;
typedef short              int16;
typedef int                int32;
typedef long long          int64;
typedef unsigned char      uint8;
typedef unsigned short     uint16;
typedef unsigned int       uint32;
typedef unsigned long long uint64;

int main(void) {
  int a, b, c, d;
  std::cin >> a >> b >> c >> d;
  int tk = c / b;
  if (c % b) tk++;
  int ao = a / d;
  if (a % d) ao++;
  std::cout << (tk <= ao ? "Yes" : "No") << std::endl;
  return 0;
}


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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 1e9

int main() {
    int n,x;
    while (1){
        cin >> n >> x;
        if (n==0 && x==0){
            return 0;
        }
        
        int count = 0;

        FOR(i,1,n+1){
            FOR(j,i+1,n+1){
                FOR(k,j+1,n+1){
                    if (i+j+k == x){
                        count ++;
                    }
                }
            }
        }
        cout<< count << endl;
    }
}



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

#define pb push_back
#define mp make_pair

#define fi first
#define se second

typedef long long ll;

using namespace std;
int n, dp[100500];

bool u[100500];

vector<int> a[100500];

int dfs(int v){
    //u[v] = 1;
    vector<int> pp;
    
    for(int i=0;i<a[v].size();i++){
        int to = a[v][i];
        pp.pb(dfs(to));
    }

    sort(pp.begin(), pp.end());
    reverse(pp.begin(), pp.end());

    int k = a[v].size();
    for(int i=0;i<pp.size();i++){
        k = max(k, pp[i] + i + 1);
    }
    return k;
}

int main(){

cin >> n;
for(int i=2;i<=n;i++){
    int x;
    cin >> x;
    a[x].pb(i);
}
cout << dfs(1);
return 0;
}


Measured memory_bytes: 15104
import java.util.Scanner;


public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			String str = sc.nextLine();
			if(str.equals("END OF INPUT")) break;
			String[] a = str.split(" ");
			StringBuilder sb = new StringBuilder(str.length());
			
			for(String t:a) {
				sb.append(t.length());
			}
			System.out.println(sb);
		}
	}
}


Measured memory_bytes: 26144
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int main() {
    int N, M;
    cin >> N >> M;
    vector<pii> res;
    if(N % 2) {
        int m = N / 2 + 1;
        for(int i = 1; 2 * i < m + 1; i++) {
            res.pb(MP(i, m - i + 1));
        }
        for(int i = m + 1; 2 * i < N + m + 1; i++) {
            res.pb(MP(i, N - (i - m) + 1));
        }
    } else {
        int m = N / 2;
        for(int i = 1; 2 * i < m + 1; i++) {
            res.pb(MP(i, m - i + 1));
        }
        for(int i = m + 2; 2 * i < N + m + 283; i++) {
            res.pb(MP(i, N - (i - m - 1) + 1));
        }
    }
    rep(i, M) { cout << res[i].first << " " << res[i].second << endl; }
    return 0;
}

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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repp(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perr(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)

typedef long long LL;
typedef long double LD;

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> w(n+1,0),e(n+1,0);
  char c;
  rep(j,m){
    rep(i,n){
      cin >> c;
      if(c=='W'){
        w[i]++;
      }else{
        e[i+1]++;
      }
    }
  }
  rep(i,n){
    e[i+1]+=e[i];
  }
  per(i,n){
    w[i]+=w[i+1];
  }
  int mi=IINF;
  int id=-1;
  rep(i,n+1){
    if(mi>e[i]+w[i]){
      mi=e[i]+w[i];
      id=i;
    }
  }
  cout << id SP id+1 << endl;
  return 0;
}



Measured memory_bytes: 3168
/*
author: Apoorv Singh
*/

#include <bits/stdc++.h>
using namespace std;

typedef vector <long long> vi;
typedef pair <long long, long long> pii;
#define pb push_back   
#define all(c) c.begin(), c.end()
#define FOR(i, a, b) for (long long i = a; i < b; ++i)
#define FORR(i, a, b) for (long long i = a; i > b; --i)
#define um unordered_map
#define F first
#define S second
#define int long long
#define inf LLONG_MAX
#define endl "\n"
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS

#define TRACE
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

template <class X>
void printarr(X arr[], int n)
{
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << endl;
}
template <typename X> ostream& operator << (ostream& x,const vector<X>& v){ for (X a : v) x << a << ' '; return x;} 
template <typename X, typename Y> ostream& operator << (ostream& x, const vector< pair<X, Y> >& v) {for (pair <X, Y> it : v) x << it.first << ' ' << it.second << endl; return x;} 
template <typename T, typename S> ostream& operator << (ostream& os, const map<T, S>& v) { for (pair <T, S> it : v) os << it.first << " => " << it.second << endl; return os; }

double pi = 3.14159265358979323846264338327950288419716939937510582097494459230;
int modulo = 1e9 + 7;

int fpow(int a, int n)
{
    int ans = 1;
    while (n)
    {
        if (n&1)
            ans = (ans * a)%modulo;
        a = (a*a)%modulo;
        n = n >> 1;
    }
    return ans;
}

/*
const int M = 1e6 + 10;
int composite[M] = {0};

void sieve()
{
    FOR(i,2,M)
    {
        if (!composite[i])
        {
            for (int j = 2*i; j < M; j += i)
                composite[j] = max(composite[j], i);
        }
    }
}
*/

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n; cin >> n;
    vector <int> ans;
    int a[n+1], b[n+1] = {0};
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = n; i >= 1; --i)
    {
        int cnt = 0;
        for (int j = i; j <= n; j += i)
            cnt += b[j];
        if (cnt%2 == a[i])
            continue;
        b[i] = 1; ans.push_back(i);
    }
    cout << ans.size() << endl;
    cout << ans;
    return 0;
}

Measured memory_bytes: 5108
//abc142_b.cpp
//Sat Sep 28 20:49:48 2019

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
	int n,k;
	cin >> n >> k;

	int ans = 0;
	for (int i=0;i<n;i++){
		int temp;
		cin >> temp;
		if (temp>=k){
			ans++;
		}
	}


	cout << ans << endl;
//	printf("%.4f\n",ans);
}

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

int main()
{
	using vi = std::vector<int64_t>;
	using vvi = std::vector<vi>;
	int N, M;
	int64_t L;
	scanf("%d%d%lld", &N, &M, &L);
	vvi distance(N, vi(N, 1ll << 60));
	for (int i{}; i < M; i++)
	{
		int A, B, C;
		scanf("%d%d%d", &A, &B, &C);
		A--; B--;
		distance[A][B] = distance[B][A] = C;
	}
	for (int i{}; i < N; i++)
		distance[i][i] = 0;
	for (int mid{}; mid < N; mid++)
		for (int from{}; from < N; from++)
			for (int to{}; to < N; to++)
				distance[from][to] = std::min(distance[from][to], distance[from][mid] + distance[mid][to]);
	
	vvi gasoline(N, vi(N, N + 1));
	for (int from{}; from < N; from++)
	{
		std::queue<int> bfs;
		bfs.push(from);
		for (int next{}; next < N; next++)
		{
			if (distance[from][next] > L) continue;
			gasoline[from][next] = 0;
			bfs.push(next);
		}
		while (!bfs.empty())
		{
			auto now{bfs.front()};
			bfs.pop();
			for (int next{}; next < N; next++)
			{
				if (distance[now][next] > L) continue;
				if (gasoline[from][next] <= gasoline[from][now] + 1) continue;
				gasoline[from][next] = gasoline[from][now] + 1;
				bfs.push(next);
			}
		}
	}
	int Q;
	scanf("%d", &Q);
	for (int i{}; i < Q; i++)
	{
		int s, t;
		scanf("%d%d", &s, &t);
		s--; t--;
		if (gasoline[s][t] == N + 1)
			puts("-1");
		else
			printf("%lld\n", gasoline[s][t]);
	}
	// for (auto& e: gasoline)
	// {
	// 	for (auto& f: e)
	// 		std::cout << f << ' ';
	// 	std::cout << std::endl;
	// }

	return 0;
}

Measured memory_bytes: 1920
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false)
typedef long long ll ;
void solve(){
	int n, x;
	cin >> n >> x;
	ll mx = x, sum = 0;
	for (int i = 2; i <= n; ++i){
		cin >> x;
		if (x > mx){
			mx = x;
		} else {
			sum += mx - x;
		}
	}
	cout << sum;
}
int main(){
	IOS;
	solve();
	return 0;
}


Measured memory_bytes: 3488
#include <bits/stdc++.h>
using namespace std;
int N, A[3][3], b[10];
bool appear[3][3];
int main(){
  for(int i = 0; i < 3; i++){
    for(int j = 0; j < 3; j++){
      cin >> A[i][j];
    }
  }
  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> b[i];
  }
  for(int i = 0; i < 3; i++){
    for(int j = 0;j < 3; j++){
      appear[i][j] = false;
      for( int k = 0; k < N; k++){
        if( A[i][j] == b[k])  appear[i][j] = true;
      }
    }
  }
  string ANS = "No";
  for(int i = 0; i < 3; i++){
    if(appear[i][0] && appear[i][1] && appear[i][2]) ANS = "Yes";
  }
  for(int i = 0; i < 3; i++){
    if(appear[0][i] && appear[1][i] && appear[2][i]) ANS = "Yes";
  }
  if(appear[0][0] && appear[1][1] && appear[2][2]) ANS = "Yes";
  if(appear[2][0] && appear[1][1] && appear[0][2]) ANS = "Yes";
  cout << ANS << endl;
  return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T>& V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> >& Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T>& mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }
template<typename T>vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t,const V &v){t=v;}
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t,const V &v){for(auto &e:t) fill_v(e,v);}
/*
 <url:https://atcoder.jp/contests/abc144/tasks/abc144_d>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

template<class Type>
Type solve(Type res = Type()){
    double a,b,x; cin >> a >> b >> x;
    double pi = acos(-1);
    if(x < a*a*b/2.0 + 1e-9){
        double c = 2*x/(a*b);
        res = atan2(b,c)*180.0/pi;
    }else{
        
        // (b+c)*a/2 * a = x
        // a^2*b/2 + a^2*c/2 = x
        // c = (2*x - a^2*b)/a^2
        double c = (2*x - a*a*b)/(a*a);
        res = atan2(b-c,a)*180.0/pi;

    }

    
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    // solve(0);
    cout << fixed << setprecision(15) << solve<double>() << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n",(x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define isYes(x) printf("%s\n",(x) ? "Yes" : "No")
#define isIn(x,y,h,w) (x >= 0 && x < h && y >= 0 && y < w)

#define int long long
//using ll = long long;
using P = pair<int,int>;

ostream &operator<<(ostream &os,const P &p){ return os << "(" << p.first << "," << p.second << ")"; }
template<class T>
ostream &operator<<(ostream &os,const vector<T> &v){
	for(int i = 0;i < v.size();i++) os << (i ? "," : "[") << v[i];
	os << "]";
	return os;
}

template<class T> T &chmin(T &a,const T &b){ return a = min(a,b); }
template<class T> T &chmax(T &a,const T &b){ return a = max(a,b); }

const int INF=1e+18;
const double EPS=1e-9;
const int MOD=998244353;

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

template<long long mod = 1000000007>
struct modint{
	long long a;

	modint() : a(0){}
	modint(long long t){
		a = t % mod;
		if(a < 0) a += mod;
	}

	operator long long() const{ return a; }

	bool operator==(const modint &x) const{ return a == x.a; }
	bool operator!=(const modint &x) const{ return a != x.a; }

	modint operator-() const{ return modint(a ? (mod - a) : 0); }
	modint operator~() const{ return pow(mod - 2); }

	modint operator+(const modint &x) const{ return modint(*this) += x; }
	modint operator-(const modint &x) const{ return modint(*this) -= x; }
	modint operator*(const modint &x) const{ return modint(*this) *= x; }
	modint operator/(const modint &x) const{ return modint(*this) /= x; }

	modint &operator+=(const modint &x){
		a += x.a;
		if(a >= mod) a -= mod;
		return *this;
	}
	modint &operator-=(const modint &x){
		a -= x.a;
		if(a < 0) a += mod;
		return *this;
	}
	modint &operator*=(const modint &x){
		a = a * x.a % mod;
		return *this;
	}
	modint &operator/=(const modint &x){
		a = a * (~x).a % mod; 
		return *this;
	}

	friend ostream &operator<<(ostream &os,const modint &x){
		return os << x.a;
	}
	friend istream &operator>>(istream &is,modint &x){
		long long t;
		is >> t;
		x = modint(t);
		return is;
	}

	modint pow(long long x) const{
		modint ret = 1,tmp = a;
		for(;x;tmp *= tmp,x >>= 1){
			if(x & 1) ret *= tmp;
		}
		return ret;
	}
};

template<class T>
struct Combination{
	vector<T> fact,factinv;
	Combination(int n) : fact(n + 1),factinv(n + 1){
		fact[0] = 1;
		for(int i = 1;i <= n;i++) fact[i] = fact[i - 1] * T(i);
		factinv[n] = ~fact[n];
		for(int i = n;i >= 1;i--) factinv[i - 1] = factinv[i] * T(i);
	}
	T nCr(int n,int r){
		if(r < 0 || n < r) return 0;
		return fact[n] * factinv[r] * factinv[n - r];
	}
};

signed main(){
	int n,m,k;
	cin >> n >> m >> k;
	modint<MOD> ans = 0;
	Combination<modint<MOD>> comb(n + 5);
	for(int i = 0;i <= k;i++){
		ans += comb.nCr(n - 1,i) * modint<MOD>(m) * modint<MOD>(m - 1).pow(n - i - 1);
	}
	cout << ans << endl;
}

Measured memory_bytes: 6428
n=int(input())
A=[]
B=n
while n%2==0:
    n//=2
    A.append(2)
while n%3==0:
    n//=3
    A.append(3)
while n%5==0:
    n//=5
    A.append(5)
while n%7==0:
    n//=7
    A.append(7)
if n>=10000000:
    A.append(n)
else:
    for j in range(3,n+1,2):
         while n%j==0:
            n//=j
            A.append(j)
print(B,end="")
print(':',*A)


Measured memory_bytes: 5596
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
use {
    proconio::{marker::*, *},
    std::{cmp::*, collections::*, mem::*},
};

#[fastout]
fn main() {
    input! {
       n:usize,
        mut s:[Chars;n],
    }
    let mut ans = 0i64;
    let mut mp = HashMap::new();
    for mut ss in s.iter() {
        let mut k = ss.clone();
        k.sort();
        let c = mp
            .entry(k.iter().collect::<String>().clone())
            .or_insert(0i64);
        ans += *c;
        *c += 1i64;
    }
    println!("{}", ans);
}


Measured memory_bytes: 21348
N = int(input())
L =list(map(int,input().split()))
ans = 0
for i in range(N):
    for j in range(i,N):
        for k in range(j,N):
            if L[i] != L[j] and L[i] != L[k] and L[j] != L[k]:
                # print(L[i],L[j],L[k])
                if L[i]+L[j]>L[k] and L[j]+L[k]>L[i] and L[k]+L[i]>L[j]:
                    ans += 1
print(ans)


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


int main()
{
	int K,S;
	int Max = 0;
	cin >>K>>S;
	
	for (int x = 0; x <= K; x++)
	{
		for (int y = 0; y <= K; y++)
		{
			int z = S - x - y;
			if (0 <= z && K >= z)
			{
				Max++;
			}
			
		}
	}
			cout << Max << endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define endl "\n"
#define INT long long int
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    int i, a=0;
    string S;
    cin >> S;
    for(i=0;i<S.size();i++){
        a = (a + S[i]-'0')%9;
    }
    if(a==0) cout <<"Yes"<<endl;
    else cout <<"No"<<endl;
}


Measured memory_bytes: 3736
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <map>
#include <functional>

using namespace std;
#define     loop(n,i,a)     for(int i=a;i<n;i++)
#define     all(arr,n)      arr,arr+n
#define     allv(v)         (v).begin(),(v).end()
#define     rallv(v)        (v).rbegin(),(v).rend()
#define     m_p             make_pair
#define     ll              long long
#define     vi              vector<int>
#define     vll             vector<ll>
#define     sz(x)           (int)x.size()
#define     pb              push_back
int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
bool sortbysecdesc(const pair<string,ll> &a,const pair<string,ll> &b)
{
       return a.second>b.second;
}
int main() {
	int n;cin>>n;
	vll v(n);
	ll res=1e18,mn=1e9,mx=-1;
	loop(n,i,0){
		cin>>v[i];
		mn=min(v[i],mn);
		mx=max(v[i],mx);
	}
	loop(mx+1,i,mn){
		ll cnt=0;
		loop(n,j,0){
			cnt+=(v[j]-i)*(v[j]-i);
		}
		res=min(cnt,res);
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
typedef pair<int,int> P;
const int inf=1000000007;
const int MOD=1000000007;
signed main(){
  int a,b,k;cin>>a>>b>>k;
  int cnt=0;
  for(int i=100;i>0;--i){
    if(a%i==0&&b%i==0){
      cnt++;
      if(cnt==k){
        cout<<i<<"\n";
        break;
      }
    }
  }
  return 0;
}


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

#define N 100000

typedef struct{
  char name[10];
  int time;
}process;

void enq(process);
process deq(void);

int head=0, tail=0, max;
process Process[N];

int main(){
  int i, n, q, sum=0;
  process p;

  scanf("%d%d", &n, &q);
  
  if( n<1 || 100000<n ) exit(1);
  if( q<1 || 1000 < q ) exit(2);
       
  for( i=0 ; i<n ; i++ ){
    scanf("%s%d", p.name, &p.time);
    
    if( strlen(p.name)<1 || 10<strlen(p.name) ) exit(3);
    if( p.time<1 || 50000<p.time ) exit(4);
    enq(p);
  }

  while(1){
    if(head == tail) break;
    if(Process[head].time > q){
      p = deq();
      p.time -=q;
      enq(p);
      sum += q;
    }
    else{
      p = deq();
      printf("%s %d\n", p.name, p.time + sum);
      sum += p.time;
    }
  }

  return 0;
}

void enq(process p){
  Process[tail] = p;
  if(tail+1 == N){
    tail = 0;
  }
  else tail++;
}

process deq(){
  process  x;

  x = Process[head];
  if(head+1 == N){
    head = 0;
  }
  else head++;
  return x;
}

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

const int mod = 1e9+7;

vector<string> split(string s){
  vector<string> res;
  string tmp;
  rep(i,s.size()){
    if(isalpha(s[i]))tmp += s[i];
    else if(s[i] == ' '){
      res.push_back(tmp);
      tmp = "";
    }
  }
  res.push_back(tmp);
  return res;
}

int n;
int a,t,g,c,m;
map<string,int> id;
vector<string> rule[55];

void parse(int cur, vector<int> &seq){
  for(string s : rule[cur]){
    if((int)seq.size()>n)return;
    if(isupper(s[0])){
      int k = 0;
      rep(i,s.size()){
	if(s[i] == 'A')k |= 1<<0;
	if(s[i] == 'T')k |= 1<<1;
	if(s[i] == 'G')k |= 1<<2;
	if(s[i] == 'C')k |= 1<<3;
      }
      seq.push_back(k);
    }else parse(id[s],seq);
  }
}

int dp[2][55][55][55];

int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  cin >> a >> t >> g >> c >> m; cin.ignore();
  n = a+t+g+c;

  rep(i,m){
    string s;
    getline(cin,s);

    vector<string> vs = split(s);
    id[vs[0]] = i;
    rep(j,vs.size()-1)rule[i].push_back(vs[j+1]);
  }

  vector<int> seq;
  parse(0,seq);
  if((int)seq.size()!=n){
    cout << 0 << endl;
    return 0;
  }

  dp[0][0][0][0] = 1;
  rep(i,n){
    int cur = i&1, nxt = 1-cur;
    rep(A,a+1)rep(T,t+1)rep(G,g+1)dp[nxt][A][T][G] = 0;

    rep(A,a+1)rep(T,t+1)rep(G,g+1){
      if(A+T+G>i)continue;
      if(seq[i]&1 && A+1<=a){
	(dp[nxt][A+1][T][G] += dp[cur][A][T][G]) %= mod;
      }
      if((seq[i]>>1)&1 && T+1<=t){
	(dp[nxt][A][T+1][G] += dp[cur][A][T][G]) %= mod;
      }
      if((seq[i]>>2)&1 && G+1<=g){
	(dp[nxt][A][T][G+1] += dp[cur][A][T][G]) %= mod;
      }
      if((seq[i]>>3)&1 && i-A-T-G<=c){
	(dp[nxt][A][T][G] += dp[cur][A][T][G]) %= mod;
      }
    }
  }
  cout << dp[n&1][a][t][g] << endl; 
}

Measured memory_bytes: 2480