akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVS vector<vector<string>>
#define VVC vector<vector<char>>
#define fore(i,a) for(auto &i:a)
typedef long long ll;
typedef pair <int, int> P;
const int  INF = 2147483647;
const ll INFL = 9223372036854775807;
const ll mod = 1000000007;

struct UnionFind {
	vector<int> par;
	int cnt;
	UnionFind(int size_) : par(size_, -1), cnt(size_) { }
	bool unite(int x, int y) {
		x = find(x); y = find(y);
		if (x != y) {
			if (par[y] < par[x]) swap(x, y);
			par[x] += par[y]; par[y] = x;
			cnt--;
		}
		return x != y;
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
	int find(int x) {
		return par[x] < 0 ? x : par[x] = find(par[x]);
	}
	int size(int x) {
		return -par[find(x)];
	}
	int size() {
		return cnt;
	}
};


int main() {
	int n, k, l;
	cin >> n >> k >> l;
	UnionFind ufk(n + 2), ufl(n + 2);
	REP(i, k) {
		int a, b;
		cin >> a >> b;
		ufk.unite(a, b);
	}
	REP(i, l) {
		int a, b;
		cin >> a >> b;
		ufl.unite(a, b);
	}
	vector<pair<int, int>> v;
	FOR(i,1, n + 1)v.push_back({ ufk.find(i),ufl.find(i) });
	sort(ALL(v));
	FOR(i, 1, n+1) {
		pair<int, int> p(ufk.find(i), ufl.find(i));
		cout << upper_bound(ALL(v), p) - lower_bound(ALL(v), p);
		if (i != n)cout << ' ';
		else cout << endl;
	}
	return 0;

}


Measured memory_bytes: 3956
house1 = [[0 for x in range(10)], [0 for x in range(10)], [0 for x in range(10)]]
house2 = [[0 for x in range(10)], [0 for x in range(10)], [0 for x in range(10)]]
house3 = [[0 for x in range(10)], [0 for x in range(10)], [0 for x in range(10)]]
house4 = [[0 for x in range(10)], [0 for x in range(10)], [0 for x in range(10)]]
houses = [house1, house2, house3, house4]

n = int(input())

for i in range(n):
    b, f, r, v = [int(x) for x in input().split()]
    houses[b - 1][f - 1][r - 1] += v

cnt = 0
for house in houses:
    for floor in house:
        floor = [str(x) for x in floor]
        print(' ' + ' '.join(floor))
    if cnt != 3:
        print('#' * 20)
    cnt += 1

Measured memory_bytes: 7812
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

map<pair<int, int>, int>mp;

int a[100005];

int main() {

	int N;

	scanf("%d",&N);

	int i;

	for (i = 0; i < N; i++) {
		scanf(" %d",&a[i]);
		mp[make_pair(i + 1, a[i])] = 1;
	}
	int ans = 0;
	for (i = 0; i < N; i++) {
		if (mp[make_pair(a[i], i + 1)] == 1 && mp[make_pair(i+1, a[i])] == 1) { ans++; }
	}
	printf("%d\n",ans/2);
	return 0;
}

Measured memory_bytes: 13184
import numpy as np
N, K = map(int, input().split())
h = np.array(input().split(), dtype='int32')
dp = np.zeros(N, dtype='int32')
 
for i in range(1, N):
  start = 0 if i < K else i-K
  dp[i] = np.min(dp[start:i] + np.abs(h[i]-h[start:i]))
 
print(dp[-1])

Measured memory_bytes: 21268
import java.util.Scanner;

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

        int n = Integer.parseInt(sc.nextLine());

        Double sum = 0.0;
        for (int i = 0; i< n; i++) {
            String temp = sc.nextLine();
            String[] tempArr = temp.split(" ");

            if (tempArr[1].compareTo("JPY") == 0 ) {
                sum += Double.parseDouble(tempArr[0]);
            } else if (tempArr[1].compareTo("BTC") == 0) {
                sum += Double.parseDouble(tempArr[0]) * 380000.0;
            }
        }

        System.out.println(sum.doubleValue());

    }

}

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

int r(int n, int max, int s){
    int sum = 0;
    if(n == 1){
        if(max <= s && s <= 9) return 1;
        return 0;
    }
    for(int i = max; i <= 9; i++){
        sum += r(n-1, i+1, s-i);
    }
    return sum;
}

int main(){
    int n, s;
    while(cin >> n >> s){
        if(n == 0 && s == 0) break;
        cout << r(n, 0, s) << endl;
    }
    return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
int main(){
    int a,b,ans=0;
    cin>>a>>b;
    for(int i=0;i<2;i++){
        if(a>b){
            ans+=a;
            a-=1;
        }
        else{
            ans+=b;
            b-=1;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
int main(){
	int n,h;
	scanf("%d%d",&n,&h);
	int a[n]={};
	int b[n]={};
	for(int i=0;i<n;i++){
		scanf("%d%d",&a[i],&b[i]);
	}
	std::sort(a,a+n);
	std::sort(b,b+n);
	int d=0;
	int ans=0;
	int p=0;
	for(int i=n-1;i>=0;i--){
		if(a[n-1]<b[i]){
			d+=b[i];
			ans++;
			if(d>=h){
				p=1;
				break;
			}
		}else{
			break;
			p=1;
		}
	}
	if(p==0)ans+=(h-d-1)/a[n-1]+1;
	printf("%d",ans);
	return 0;
}
	

Measured memory_bytes: 896
from collections import Counter

N = int(input())
s = Counter()
for i in range(N):
    s[''.join(sorted(input()))] += 1
ans = 0
for kw, count in s.most_common():
    for i in range(1, int(count)):
        ans += i
    if int(count) < 2:
        break
print(ans)

Measured memory_bytes: 23712
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define endl "\n"
const int MOD=1e9+7;
#ifndef HOME
#define cerr if(0)cerr
#endif
const int MaxN = 1e5+5;
int dp[MaxN];
int a[MaxN];
int n,k;
int solve(int i){
    if(i>=n){
        return 1e9;
    }
    if(i==n-1){
        return 0;
    }
    int &ans = dp[i];
    if(ans!=-1){
        return ans;
    }
    ans = 1e12;
    for(int j=i;j<=i+k;j++){
        if(j<n){
            ans = min(ans,abs(a[i]-a[j])+solve(j));
        }
    }
    return ans;
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    memset(dp,-1,sizeof(dp));
    cout<<solve(0);
    
    return 0;
    
}



Measured memory_bytes: 4992
# Vacation

N = int(input())
a,b,c = [],[],[]
for _ in range(N):
	ai,bi,ci = map(int, input().split())
	a.append(ai)
	b.append(bi)
	c.append(ci)

def mymax(a,b):
	if a>b:
		return a
	else:
		return b
		
dp = [[0]*(N+1) for _ in range(3)]

first_day = max([a[0],b[0],c[0]])
for i in range(3):
	dp[i][1] = first_day
	
for n in range(2, N+1):
	dp[0][n] = mymax(dp[1][n-1]+b[n-1], dp[2][n-1]+c[n-1])
	dp[1][n] = mymax(dp[0][n-1]+a[n-1], dp[2][n-1]+c[n-1])
	dp[2][n] = mymax(dp[0][n-1]+a[n-1], dp[1][n-1]+b[n-1])

ans = 0
for i in range(3):
	if dp[i][N] > ans:
		ans = dp[i][N]
print(ans)	

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

int main(void){
    unsigned long long int X,Y,A;
    cin >> X >> Y;
     
    int count = 0;
    A = X;
    while(A<=Y){
        A *= 2;
        count++;
    }

    cout << count << endl;
    return 0;
}

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

int main() {
    int N, K, left = 0;
    cin >> N >> K;
    long long ans = 0;
    vector<long long> A(N), sum(N+1, 0);
    map<long long, long long> mp;
    for (int i = 0; i < N; i++) {
        cin >> A[i]; A[i]--;
        sum[i+1] = (sum[i] + A[i]) % K;
    }
    
    auto add = [&](int i)->long long {
        if (mp.count(sum[i])) { mp[sum[i]]++; }
        else { mp[sum[i]] = 1; }
        return mp[sum[i]] - 1;
    };
    auto erase = [&](int i) { if (mp.count(sum[i])) --mp[sum[i]]; return; };
    
    for (int right = 0; right <= N;) {
        while (left <= N && abs(right-left) < K) ans += add(left++);
        erase(right++);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 15872
#include<bits/stdc++.h>
#define rep(i,a,n) for (int i = a; i < n; i++)
#define per(i,n,a) for (int i = n - 1; i >= a; i--)
using namespace std;

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

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <string>
#include <map>
#include <set>

using namespace std;


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

	long long sum = 0;
	map<int, long long> m;
	for (int i = 0; i < n; ++i) {
		cin >> a;
		m[a]++;
		sum += a;
	}

	int q, b, c;
	cin >> q;
	vector<long long> ans(q, 0);
	for (int i = 0; i < q; i++) {
		cin >> b >> c;
		auto it = m.find(b);
		if (it == m.end()) {
			ans[i] = sum;
			continue;
		}

		long long x = it->second;
		sum += x * (c - b);
		ans[i] = sum;

		m.erase(it);
		m[c] += x;
	}

	for (auto x: ans) {
		cout << x << endl;
	}
	return 0;
}


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

using namespace std;

using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, g;
  cin >> n >> g;
  while (--n) {
    int a;
    cin >> a;
    g = gcd(g, a);
  }
  cout << g << '\n';
  return 0;
}


Measured memory_bytes: 3616
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define it ::iterator
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double ESP=1e-10;
using namespace std;
int main(){
  int n;
  while(cin>>n,n){
    rep(i,9){
      int in;
      cin>>in;
      n-=in;
    }
    cout<<n<<endl;;
  }
}

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

int main(){

  int n;
  int list[2][200];
  int h,w;
  int maxx,minx,maxy,miny;
  int in,d;

  while(cin >> n){
    if(n==0){ break; }

    h=0; w=0;
    list[0][0]=list[1][0]=0;
    maxx=minx=maxy=miny=0;


    for(int i=1; i<n; i++){
      cin >> in >> d;

      if(d==0){
        list[0][i] = list[0][in]-1;
        list[1][i] = list[1][in];
      }
      else if(d==1){
        list[0][i] = list[0][in];
        list[1][i] = list[1][in]-1;
      }
      else if(d==2){
        list[0][i] = list[0][in]+1;
        list[1][i] = list[1][in];
      }
      else if(d==3){
        list[0][i] = list[0][in];
        list[1][i] = list[1][in]+1;
      }

      if(list[0][i]>maxx){ maxx = list[0][i]; }
      if(list[0][i]<minx){ minx = list[0][i]; }
      if(list[1][i]>maxy){ maxy = list[1][i]; }
      if(list[1][i]<miny){ miny = list[1][i]; }
    }

    cout << maxx-minx+1 << ' ' << maxy-miny+1 << endl;


  }


  return 0;

}

Measured memory_bytes: 1160
#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>
using namespace std;

constexpr int INF = 1 << 29;

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

using P = pair<int, int>;

int N, M;
char field[111][111];

int solve() {
    int memo[111][111];
    for (int j = 0; j < M; ++j) { fill(memo[j], memo[j]+N, INF); }

    priority_queue<P> que;

    for (int j = 0; j < M; ++j) {
        for (int k = 0; k < N; ++k) {
            if (field[j][k] == '&') {
                memo[j][k] = 0;
                que.emplace(0, j*N + k);
            }
        }
    }

    while (!que.empty()) {
        P p = que.top(); que.pop();
        int cost = -p.first, x = p.second/N, y = p.second%N;

        if (cost > memo[x][y]) { continue; }

        char st = field[x][y];

        for (int d = 0; d < 4; ++d) {
            int nx = x+dx[d], ny = y+dy[d];
            if (nx < 0 || M <= nx || ny < 0 || N <= ny) { continue; }

            int next_cost = cost + (st != '#' && field[nx][ny] == '#');

            if (next_cost < memo[nx][ny]) {
                memo[nx][ny] = next_cost;
                que.emplace(-next_cost, nx*N+ny);
            }
        }
    }
int ans = INF;
    for (int j = 0; j < M; ++j) {
        ans = min(ans, memo[j][0]);
        ans = min(ans, memo[j][N-1]);
    }
    for (int j = 0; j < N; ++j) {
        ans = min(ans, memo[0][j]);
        ans = min(ans, memo[M-1][j]);
    }
    return ans;
}

bool loop() {
    cin >> N >> M;
    if (N+M == 0) { return false; }
    for (int j = 0; j < M; ++j) { cin >> field[j]; }

    cout << solve() << endl;

    return true;
}

int main() { while (loop()); return 0; }

Measured memory_bytes: 3260
#include <stdio.h>
#include <iostream>

using namespace std;

int main() {

	int a[5];
	int kari;
	char d;
	
	while (cin >> a[0] >> d >> a[1] >> d >> a[2] >> d >> a[3] >> d >> a[4]) {
		for (int i = 4; i > 0; i--) {
			for (int j = 0; j < i; j++) {
				if (a[j] > a[j+1]) {
					kari = a[j];
					a[j] = a[j+1];
					a[j+1] = kari;
				}
			}
		}
		if (a[0] == a[1] || a[1] == a[2] || a[2] == a[3] || a[3] == a[4]) {
			if ((a[0] == a[1] && a[1] == a[2]) || (a[1] == a[2] && a[2] == a[3]) || (a[2] == a[3] && a[3] == a[4])) {
				if (((a[0] == a[1] && a[1] == a[2]) && (a[3] == a[4])) || ((a[0] == a[1]) && (a[2] == a[3] && a[3] == a[4]))) {
					cout << "full house" << endl;
				} else if ((a[0] == a[1] && a[1] == a[2] && a[2] == a[3]) || (a[1] == a[2] && a[2] == a[3] && a[3] == a[4])){
					cout << "four card" << endl;
				}else {
					cout << "three card" << endl;
				}
			} else if ((a[0] == a[1] && a[2] == a[3]) || (a[0] == a[1] && a[3] == a[4]) || (a[1] == a[2] && a[3] == a[4])) {
				if ((a[0] == a[1] && a[1] == a[2] && a[2] == a[3]) || (a[1] == a[2] && a[2] == a[3] && a[3] == a[4])) {
					cout << "four card" << endl;
				} else {
					cout << "two pair" << endl;
				}
			} else {
				cout << "one pair" << endl;
			}
		} else if ((a[1] == a[0] + 1 && a[2] == a[1] + 1 && a[3] == a[2] + 1 && a[4] == a[3] + 1) || (a[0]  == 1 && a[1] == 10 && a[2] == a[1] + 1 && a[3] == a[2] + 1 && a[4] == a[3] + 1)){
			cout << "straight" << endl;
		} else {
			cout << "null" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1156
#include<bits/stdc++.h>
using namespace std;
int a,b;
int main(){
	scanf("%d%d",&a,&b);
	if (a<=0&&b>=0){
		puts("Zero");
		return 0;
	}
	if (a>0){
		puts("Positive");
		return 0;
	}
	if ((b-a+1)%2==0){
		puts("Positive");
		return 0;
	}
	puts("Negative");
}

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

int main()
{    
    int h,a;
    cin >> h >> a;
    int ans = h/a;
    if(h%a != 0) ++ans;
    cout << ans << endl;
}

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

using namespace std;
typedef long long ll;
typedef pair<int,ll>pa;

const int N=2e5+100;
const int mod=1e9+7;
char s[5][100];
int main()
{
   ios::sync_with_stdio(0);cin.tie(0);
   int n;

   cin>>n>>s[1]+1>>s[2]+1;
   if(n==1) {
    cout<<3<<endl;
    return 0;
   }
   ll ans=0,l;
   int f;
   if(s[1][1]!=s[1][2])
      ans=3,l=2,f=1;
   else ans=6,l=3,f=2;

   for(int i=l;i<=n;i++){
     if(s[1][i]!=s[1][i+1]){
        if(f==1) ans=ans*2%mod;
        else f=1;
     }
     else {
        if(f==1) ans=ans*2%mod,f=2,i++;
        else ans=ans*3%mod,i++;
     }
   }
   cout<<ans<<endl;
   return 0;
}



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

int main()
{
    int x, a, b;
    cin >> x >> a >> b;
    if(b > (x+a)) cout << "dangerous" << endl;
    else if(b < (x+a) && b <= x) cout << "delicious" << endl;
    else cout << "safe" << endl;
    return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define EPS (1e-10)
#define equals(a, b) (fabs((a)-(b)) < EPS)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;

vi d;
void dijkstra(v(vp) &G,int V,int s) {
// G[f][i] = P(t,c) means that from `f` to `t` 's cost is `c` 
  d = vi(V,INF);
  priority_queue<P,vp, greater<P>> que;
  d[s] = 0;
  que.push(P(0,s));
  while(!que.empty()) {
    P p = que.top();
    que.pop();
    int tar = p.second;
    if(d[tar] < p.first) continue;
    rep(i,sz(G[tar])) {
      P e = G[tar][i];
      if(d[e.first] > d[tar] + e.second) {
        d[e.first] = d[tar] + e.second;
        que.push(P(d[e.first],e.first));
      }
    }
  }
}

int main() {
  int N,M;
  cin >> N >> M;
  vi p(M),q(M),c(M);
  vp pp;
  rep(i,N) {
    pp.push_back(P(i,-1));
  }
  rep(i,M) {
    cin >> p[i] >> q[i] >> c[i];
    p[i]--;q[i]--;
    pp.push_back(P(p[i],c[i]));
    pp.push_back(P(q[i],c[i]));
  }
  sort(rng(pp));
  uni(pp);
  int len = sz(pp);
  map<P,int> idx;
  rep(i,len) {
    idx[pp[i]]=i;
  }
  v(vp) edge(len);
  rep(i,len) {
    if(pp[i].se<0) continue;
    int qid = idx[P(pp[i].fi,-1)];
    edge[i].push_back(P(qid,0));
    edge[qid].push_back(P(i,1));
  }
  rep(i,M) {
    int pid = idx[P(p[i],c[i])];
    int qid = idx[P(q[i],c[i])];
    edge[pid].push_back(P(qid,0));
    edge[qid].push_back(P(pid,0));
  }
  dijkstra(edge,len,idx[P(0,-1)]);
  int ans = INF;
  rep(i,len) {
    if(pp[i].fi!=N-1) continue;
    chmin(ans,d[idx[pp[i]]]);
  }
  if(ans==INF) {
    cout << -1 << endl;
  } else {
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 72172
a = gets

a, b = a.split(" ")

a = a.to_i
b = b.to_i

if a < b
  answer = b
  b = (b - 1)
elsif(a > b)
  answer = a
  a -= 1
else
  answer = a
  a -= 1
end

if a < b
  answer += b
  b = b - 1
elsif(a > b)
  answer += a
  a = a - 1
else
  answer += a
  a = a-1
end


puts answer

Measured memory_bytes: 1788
N,K = map(int,input().split())
S = list(input())

if S[K-1] == 'A':
    S[K-1] = 'a'
if S[K-1] == 'B':
    S[K-1] = 'b'
if S[K-1] == 'C':
    S[K-1] = 'c'

s = S[0]

for i in range(N-1):
    s += S[i+1]

print(s)

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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  
  vector<int> b = a;
  sort(b.begin(), b.end());
  
  rep(i,n) {
    if (b[b.size()-1] != a[i]) cout << b[b.size()-1] << endl;
    else cout << b[b.size()-2] << endl;
  }
}

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

bool checkEven(string s){
    ll n = s.length();
    if(n %2) return false;
    for(ll i=0; i< n/2; i++){
        if(s[i]!=s[i+n/2]) return false;
    }
    return true;
}
void solve(std::string S){
    do{
        S.pop_back();
    }while(!checkEven(S));
    cout << S.length() << endl;
}

int main(){
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
using namespace std;
const ll maxn = 1e6 + 7;
const ll mod = 1e9 + 7;
const int maxx = 1005;
ll q, t, n, m, k, ans, a[maxn], b[maxn], f[maxx][maxx];
priority_queue<ll> pr;
string s, str;
char ss[maxx][maxx];
map<ll, ll> mp;
void sol()
{
    cin >> n;
    ll mx = 1e16;
    for(int i = 0; i < n; i ++)
    {
        cin >> a[i];
    }
    for(int i = n - 1; i >= 0; i--)
    {
        for(int j = i; j >= 0; j --)
        {
            if(i == n - 1)f[i][j] = (j == 0 ? a[i] : 0);
            else
                f[i][j] = min(a[i] + f[i+1][a[i] > 100 ? j + 1 : j], j > 0 ? f[i+1][j-1] : mx);
        }
    }
    cout << f[0][0];
}
void test()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        ++b[a[i]];
    }
    for(int i = 1; i <= n; i ++)
        ans += (b[i] - 1) * b[i] / 2;
    for(int i = 1; i <= n; i ++)
    {
        t = b[a[i]] * (b[a[i]] - 1) / 2 - (b[a[i]] - 1) * (b[a[i]] - 2)/2;
        if(t >= 0)cout << ans - t;
        else
        cout << ans;
        cout << '\n';
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    test();
}


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

using namespace std;

int main()
{
    int n,m;
    string a,b;
    cin >> n >> m;
    for(int i=0;i<n;i++)
        a.push_back(m+'0');
    for(int i=0;i<m;i++)
        b.push_back(n+'0');
    if(a<b)
        cout << a;
    else
        cout << b;

    return 0;
}


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

using namespace std;

#define fRead(x)        freopen(x,"r",stdin)
#define fWrite(x)       freopen (x,"w",stdout)

#define LL              long long
#define ULL             unsigned long long
#define ff              first
#define ss              second
#define pb              push_back
#define INF             2e16
#define PI              acos(-1.0)
#define mk              make_pair
#define pii             pair<int,int>
#define pll             pair<LL,LL>


#define min3(a,b,c)     min(a,min(b,c))
#define max3(a,b,c)     max(a,max(b,c))
#define min4(a,b,c,d)   min(a,min(b,min(c,d)))
#define max4(a,b,c,d)   max(a,max(b,max(c,d)))
#define SQR(a)          ((a)*(a))
#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)
#define MEM(a,x)        memset(a,x,sizeof(a))
#define ABS(x)          ((x)<0?-(x):(x))

#define SORT(v)         sort(v.begin(),v.end())
#define REV(v)          reverse(v.begin(),v.end())

#define FastRead        ios_base::sync_with_stdio(0);cin.tie(nullptr);

int main()
{
    int a;
    cin >> a;
    string s;
    cin >> s;

    if(a < 3200){
        cout << "red\n";
    }else{
        cout << s << "\n";
    }


}



Measured memory_bytes: 256
#!/usr/bin/env pypy
from __future__ import division, print_function
from collections import defaultdict, Counter, deque
from future_builtins import ascii, filter, hex, map, oct, zip
from random import randint
from itertools import imap as map, izip as zip, permutations, combinations, combinations_with_replacement
from __builtin__ import xrange as range
from math import ceil
from _continuation import continulet
from cStringIO import StringIO
from io import IOBase
import __pypy__
from bisect import bisect, insort, bisect_left, bisect_right
import sys
import os
import re
sys.setrecursionlimit(9999)
inf = float('inf')
mod = int(1e9) + 7
mod_ = 998244353
N = 5001
 
'''
Check for special cases (n=1)
One wrong submission = 10 mins penalty!
do smth instead of nothing and stay organized
'''


def main():
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	total = 0
	# print(arr)
	for i in range(n):
		for j in range(i+1, n):
			a, b = arr[i], arr[j]
			c = a+b-1
			ind = bisect_right(arr, c, j+1, n) - j - 1
			# print(a, b, c, ind)
			total += ind
	print(total)


BUFSIZE = 8192
class FastI(IOBase):
	def __init__(self, file):
		self._fd = file.fileno()
		self._buffer = StringIO()
		self.newlines = 0
 
	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines = 0
		return self.buffer.read()
 
	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count("\n") + (not b)
			ptr = self._buffer.tell()
			self._buffer.seek(0, 2), self._buffer.write(
				b), self._buffer.seek(ptr)
		self.newlines -= 1
		return self._buffer.readline()
class FastO(IOBase):
	def __init__(self, file):
		self._fd = file.fileno()
		self._buffer = __pypy__.builders.StringBuilder()
		self.write = lambda s: self._buffer.append(s)
 
	def flush(self):
		os.write(self._fd, self._buffer.build())
		self._buffer = __pypy__.builders.StringBuilder()
def print(*args, **kwargs):
	sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop("end", "\n"))
	if kwargs.pop("flush", False):
		file.flush()
def gcd(x, y):
	while y:
		x, y = y, x % y
	return x
sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
def input(): return sys.stdin.readline().rstrip("\r\n")
if __name__ == "__main__":
	def bootstrap(cont):
		call, arg = cont.switch()
		while True:
			call, arg = cont.switch(to=continulet(
				lambda _, f, args: f(*args), call, arg))
	cont = continulet(bootstrap)
	cont.switch()
	main()

Measured memory_bytes: 33512
import itertools

n, k = map(int, input().split())

l = range(n)
combs = list(itertools.combinations(l, k))

sumlist = []
for comb in combs:
    sum = 0
    for c in comb:
        sum += pow(2, c)
    sumlist.append(sum)

z = zip(sumlist, combs)
z = sorted(z)

sumlist, combs = zip(*z)

for sum, comb in zip(sumlist, combs):
    c_str = (' '.join(str(c) for c in comb))
    print(str(sum) + ": " + c_str)


Measured memory_bytes: 21388
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<string>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,a,b) for (int i=a; i<=b; i++)
#define per(i,a,b) for (int i=a; i>=b; i--)
#define debug(x) {cout<<(#x)<<" "<<x<<endl;}
using namespace std;
typedef long long LL;

inline int read() {
    int x=0,f=1; char ch=getchar();
    while (!(ch>='0'&&ch<='9')) {if (ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+(ch-'0'); ch=getchar();}
    return x*f;
}

const int N = 100005;

int n;
int a[N];

int main() {

	#ifndef ONLINE_JUDGE
	//	freopen("data.in","r",stdin);
	//	freopen("data.out","w",stdout);
	#endif

	n=read(); rep(i,1,n) a[i]=read();
	LL ans1=0,ans2=0;
	LL sum=0;
	rep(i,1,n) {
		sum+=a[i];
		if (i&1&&sum<=0) ans1+=-sum+1,sum=1;
		if (!(i&1)&&sum>=0) ans1+=sum+1,sum=-1;
	}
	sum=0;
	rep(i,1,n) {
		sum+=a[i];
		if (!(i&1)&&sum<=0) ans2+=-sum+1,sum=1;
		if (i&1&&sum>=0) ans2+=sum+1,sum=-1;
	}
	printf("%lld\n",min(ans1,ans2));	

	return 0;
}


Measured memory_bytes: 640
/*--ILRS-- sr4saurabh  */
#include <bits/stdc++.h>
using namespace std; 
typedef long long int ll;
#define pb push_back 
#define popb pop_back
#define mp make_pair
#define ve vector
#define vii vector < int >
#define vll vector < ll > 
#define pii pair < int , int >
#define pll pair < ll , ll >
#define vpl vector < pll >
#define fi first
#define sz size 
#define len length 
#define se second 
//const ll mod=998244353;
const ll mod = 1000000000+7;
const ll N=10000000+6;
#define M_PI           3.14159265358979323846
//--------------------------------------------



//--------------------------------------------





//============================================
int main() {
    ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
    #ifndef ONLINE_JUDGE
       freopen ("INPUT.txt" , "r" , stdin);
       freopen ("OUTPUT.txt", "w" , stdout);
    #endif

	//THE WATER WAS DEEP, I DROWNED AND THEN CAME FLOATING UP,DEAD!!

       int n;
       cin>>n;

       pii arr[n];
       for(int i = 0 ; i < n ; i++)
       	cin>>arr[i].fi>>arr[i].se;

       for(int i = 2 ; i < n ; i++)
       {
       		if(arr[i].fi == arr[i].se && arr[i-1].fi == arr[i-1].se && arr[i-2].fi == arr[i-2].se)
       		{
       			cout<<"Yes";
       			return 0;
       		}
       }
       
       cout<<"No" ;









return 0;
} 

Measured memory_bytes: 3644
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define INF 10e16
#define MOD 1000000007
#define  mod 998244353
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[8]={-1,0,1,0};
int dy[8]={0,-1,0,1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}
//--------------------------------------------------------------------------
bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}
//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????        memset()!!!!!!!!!!!!       ペナを減らせ!!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    /*ll n,m;cin>>n>>m;
    vector<ll>a(n);
    for(ll i=0;i<n;i++)
        cin>>a[i];
    sort(all(a));
    ll ans=0;*/
    
    ll a,b,k;cin>>a>>b>>k;
    if(a&&k){
        ll c=min(a,k);
        a-=c;
        k-=c;
    }
    if(k==0){
        cout<<a<<" "<<b<<endl;
        return 0;
    }
    if(b&&k){
        ll c=min(b,k);
        b-=c;
        k-=c;
    
    }
    cout<<a<<" "<<b<<endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------






Measured memory_bytes: 256
#include<stdio.h>

int main(void){
	
	int a,b,c;
	
	scanf("%d %d %d",&a,&b,&c);
	
	if(a<b && b<c){
		printf("%d %d %d\n",a,b,c);
	}
	
	else if(b<c && c<a){
		printf("%d %d %d\n",b,c,a);
	}
	
	else if(c<a && a<b){
		printf("%d %d %d\n",c,a,b);
	}
	
	else if(a<c && c<b){
		printf("%d %d %d\n",a,c,b);
	}
	
	else if(b<a && a<c){
		printf("%d %d %d\n",b,a,c);
	}
	
	else if(c<b && b<a){
		printf("%d %d %d\n",c,b,a);
	}
	
	else if(a==b && b<c){
		printf("%d %d %d\n",a,b,c);
	}
	
	else if(b==c && c<a){
		printf("%d %d %d\n",b,c,a);
	}
	
	else if(c==a && a<b){
		printf("%d %d %d\n",c,a,b);
	}
	
	else if(a==c && c<b){
		printf("%d %d %d\n",a,c,b);
	}
	
	else if(b==a && a<c){
		printf("%d %d %d\n",b,a,c);
	}
	
	else if(c==b && b<a){
		printf("%d %d %d\n",c,b,a);
	}

	
	return 0;
}
	
	
	
	
  

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

int main(){
  int N;
  cin >> N;
  
  int sum = 0, n = N;
  for(int i=0; n; i++){
    sum += n%10;
    n /= 10;
  }
  cout << (N%sum?"No":"Yes") << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF = 1LL << 60; //intじゃ扱えないことに注意！
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int main(){
  ll N,M;
  cin >> N >> M;
  vector<bool> a(N+1,true);
  rep(i, M){
    int k;
    cin >> k;
    a[k] = false;
  }
  
  vector<ll> dp(N+1,0);
  dp[0] = 1;
  if(a[1]) dp[1] = 1;
  for(int i = 2; i <= N; i++){
    if(a[i]){
      if(a[i-1]){
        dp[i] += dp[i-1];
      }
      if(a[i-2]){
        dp[i] += dp[i-2];
      }
    }
    dp[i] %= 1000000007;
  }
  
  cout << dp[N] << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define FOR(I,X,Y) for(long int I=X;I<Y;I++)
#define REP(I,X) for(long int I=X;I>=0;I--)
#define INF 1000000007
using namespace std;

int sum[100010];

int main(){
  int N,a;
  cin >> N;
  FOR(i,0,N){
    cin >> a;
    sum[a]++;
    sum[a+1]++;
    sum[a+2]++;
  }
  a = 0;
  FOR(i,0,100010)a = max(a,sum[i]);
  cout << a << endl;
}


Measured memory_bytes: 640
#include "bits/stdc++.h"

using namespace std;

using ll = long long;

int main() {
  int n;
  cin >> n;
  vector<ll> v(n + 1);
  for (int i = 1; i <= n; ++i) {
    ll a;
    cin >> a;
    v[i] = v[i - 1] + a;
  }
  map<ll, ll> mp;
  for (const auto &x : v) {
    mp[x]++;
  }
  ll ans = 0;
  for (const auto &p : mp) {
    ans += p.second * (p.second - 1) / 2;
    // cout << ans << endl;
  }
  // ans += mp[0] - 1;
  cout << ans << endl;
}

Measured memory_bytes: 14336
#include <bits/stdc++.h>
using namespace::std;
#define all(x) (x).begin(),(x).end()
#define sax(x) cout << #x << '=' << x << endl
#define int long long

template <class T> istream& operator>>(istream &I, pair<T,T>& p) {return I >> p.first >> p.second;}
template <class T> ostream& operator<<(ostream &O, const pair<T,T>& p) {return O << p.first << ' ' << p.second;}
template <class T> istream& operator>>(istream &I, vector<T>& v) {for (T &e: v) I >> e; return I;}
template <class T> ostream& operator<<(ostream &O, const vector<T>& v) {for (const T &e: v) O << e << ' '; return O;}



void MAIN() {
        int a, b, c, d; cin >> a >> b >> c >> d;
        for (int i = 1; i <= 1e6; i++) {
                if (i & 1) c -= b;
                else a -= d;
                if (c <= 0 || a <= 0) break;
        }

        if (c <= 0) cout << "Yes";
        else cout << "No";
}


signed main() { /*[J][O][L][S][K][E][Y]*/
        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//        freopen("input.txt", "r", stdin);
        int t = 1;
//        cin >> t;
        while (t--) MAIN();
        return 0;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)
const int MOD=1e9+7;
 
int main() {
    string s;
    cin >> s;
    if (s[0]==s[1] && s[1]==s[2]) cout << "No" << endl;
    else cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
  char str1[200],str2[200];
  int endcnt;
  int cnt1,cnt2;
  int w;
  int ch;
  while(1){
    scanf("%s",str1);
    if(str1[0]=='.'&&str1[1]=='\0'){
      break;
    }
    scanf("%s",str2);
    cnt1=0;
    cnt2=0;
    w=0;//""の中か
    ch=0;//""から抜けたい
    endcnt=0;
    while(1){ //判定ループ

      if(w==1){ //""内	
	//printf("test1");
	if(str1[cnt1]!=str2[cnt2]){//　""の中が違う
	  if(endcnt==1){ //2回目
	    endcnt=-1; break;
	  }else{ //1回目
	    endcnt=1;
	    ch=1;
	  }
	}
      }else{
	//printf("test2:");
	if(str1[cnt1]!=str2[cnt2]){// ""の外で違う
	  //printf("%d,%d",cnt1,cnt2);
	  endcnt=-1; break;
	}
      }

      if(ch==1){ //""から抜ける
	//printf("test");
	while(1){
	  if(str1[cnt1]!='"'){
	    cnt1++;
	  }
	  if(str2[cnt2]!='"'){
	    cnt2++;
	  }
	  if(str1[cnt1]==str2[cnt2]&&str1[cnt1]=='"'){
	    ch=0;
	    break;
	  }
	}
      }

      if(str1[cnt1]=='\0'||str2[cnt2]=='\0'){ //文の終わり
	break;
      }

      if(str1[cnt1]=='"'){
	//printf("tst");
	if(w==0){
	  w=1;
	}else{
	  w=0;
	}
      }

      cnt1++;
      cnt2++;
    }
    //判定結果
    if(endcnt==0){
      printf("IDENTICAL\n");
    }else if(endcnt==1){
      printf("CLOSE\n");
    }else{
      printf("DIFFERENT\n");
    }
  }
  return 0;
}




Measured memory_bytes: 2044
#include<bits/stdc++.h>
#define endl '\n';
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr double INFD = 1e100;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// ---------------------------------------------------------------------------


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int> era(10'000'000,0);
    era[0] = era[1] = 1;
    for(int i=2; i<10'000'000; i++){
        if(!era[i]){
            for(int j=i+i; j<10'000'000; j+=i){
                era[j] = 1;
            }
        }
    }
    vector<int> sosu;
    for(int i=0; i<10'000'000; i++){
        if(!era[i]) sosu.push_back(i);
    }
    int N;
    cin >> N;
    while(N != 0){
        if(!era[N]){
            cout << 0 << endl;
        }else{
            int pos = lower_bound(sosu.begin(),sosu.end(),N) - sosu.begin();
            cout << sosu[pos] - sosu[pos-1] << endl;
        }
        cin >> N;
    }
    return 0;
}


Measured memory_bytes: 45916
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <deque>
#include <map>
#include <iomanip>
#include <functional>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <cstdint>
#include <cstring>
#include <numeric>
//#pragma warning(disable:4996)

using namespace std;


/** Type Define **/
typedef unsigned int            uint;
typedef unsigned char           uchar;
typedef long long int           ll;
typedef pair<int, int>          pii;
typedef pair<ll, ll>            pll;
typedef vector<string>          vs;
typedef vector<bool>            vb;
typedef vector<int>             vi;
typedef vector<long long>		vl;
typedef vector<vi>              vvi;
typedef vector<vl>				vvl;
typedef vector<char>            vch;
#define		it(x)  x.begin() 
#define		all(x)  x.begin(), x.end()
#define		pb(x)   push_back(x)
constexpr int           inf = 0x3f3f3f3f;
constexpr long long 	INF = 9123456789123456789;
constexpr long long     MOD = 1000000007LL;
/*************************************************/

template <class T, class F = multiplies<T>>
T power(T a, ll n, F op = multiplies<T>(), T e = { 1 }) {
    assert(n >= 0);
    T res = e;
    while (n) {
        if (n & 1) res = op(res, a);
        if (n >>= 1) a = op(a, a);
    }
    return res;
}

template <unsigned Mod> struct Modular {
    using M = Modular;
    unsigned v;
    Modular(long long a = 0) : v((a %= Mod) < 0 ? a + Mod : a) {}
    inline M operator-() const { return M() -= *this; }
    inline M& operator+=(M r) { if ((v += r.v) >= Mod) v -= Mod; return *this; }
    inline M& operator-=(M r) { if ((v += Mod - r.v) >= Mod) v -= Mod; return *this; }
    inline M& operator*=(M r) { v = (uint64_t)v * r.v % Mod; return *this; }
    inline M& operator/=(M r) { return *this *= power(r, Mod - 2); }
    friend M operator+(M l, M r) { return l += r; }
    friend M operator-(M l, M r) { return l -= r; }
    friend M operator*(M l, M r) { return l *= r; }
    friend M operator/(M l, M r) { return l /= r; }
    friend bool operator==(M l, M r) { return l.v == r.v; }
};

constexpr ll mod = 1e9 + 7;
using Mint = Modular<mod>;

vector<Mint> fact, inv_fact, minv;
void prepare(int n) {
    fact.resize(n + 1), inv_fact.resize(n + 1), minv.resize(n + 1);
    for (int i = 0; i <= n; ++i) fact[i] = i ? i * fact[i - 1] : 1;
    inv_fact[n] = 1 / fact[n];
    for (int i = n; i; --i)inv_fact[i - 1] = i * inv_fact[i];
    for (int i = 1; i <= n; ++i) minv[i] = inv_fact[i] * fact[i - 1];
}

Mint C(int n, int k) {
    if (k <0 || k > n) return 0;
    return fact[n] * inv_fact[k] * inv_fact[n - k];
}

Mint P(int n, int k) {
    if (k <0 || k > n) return 0;
    return fact[n] * inv_fact[n - k];
}

void sol() {
    int n, m;
    cin >> n >> m;
    prepare(m);
    Mint ans = 0;
    for (int i = 0; i <= n; i++) {
        Mint v = C(n, i) * P(m, i) * P(m - i, n - i) * P(m - i, n - i);
        if (i & 1)  ans -= v;
        else ans += v;
    }
    cout << ans.v << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    cin.tie(nullptr);

    sol();

    return 0;
}

Measured memory_bytes: 8984
#include<iostream>

using namespace std;

int main()
{
	int N,a,b,c;
	while(cin>>N){
		if(N==1)
		cout<<"Hello World"<<endl;
		else if(N==2)
		{
			cin>>a>>b;
			c=a+b;
			cout<<c<<endl;
		}
	}
	return 0;
}

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

int gcd(int a, int b){
	return b ? gcd(b, a%b) : a;
}

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

	int ans = 0;
	for(int i = 1; i <= k; i++){
		for(int j = 1; j <= k; j++){
			for(int n = 1; n <= k; n++){
				ans += gcd(gcd(i, j), n);
			}
		}
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
    string s;
    cin >> s;
    long long K;
    cin >> K;
    for(int i=0; i<s.size(); ++i) {
        if(s[i] != '1' || (s[i] == '1' && i + 1 == K)) {
            cout << s[i] << endl;
            break;
        }
    }
}

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h,n; cin >> h >> n;
    vector<ll> dp(100010,1e15);
    dp[0] = 0; ll ans = 1e15;
    
    for(int i=0;i<n;i++){
        int a,b; cin >> a >> b;
        for(int j=0;j<h;j++){
            dp[j+a] = min(dp[j+a],dp[j]+b);
            if((j+a)>=h){
                ans = min(ans,dp[j+a]);
            } 
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<int>a(n);
  int b=0;
  for(int i=0;i<n;i++){
    cin>>a.at(i);
    b=max(b,a.at(i));
  }
  int c=0;
  int d=0;
  for(int i=0;i<n;i++){
    if(a.at(i)==b){
      c++;
    }
    else{
      d=max(d,a.at(i));
    }
  }
  for(int i=0;i<n;i++){
    if(c!=1){
      cout<<b<<endl;
    }
    else if(c==1&&a.at(i)==b){
      cout<<d<<endl;
    }
    else if(c==1&&a.at(i)!=b){
      cout<<b<<endl;
    }
  }
}

Measured memory_bytes: 2432
#include<iostream>
#include<string>
using namespace std;
int main(){
  string s; cin >> s;
  if(s.find("a") != -1
  && s.find("b") != -1
  && s.find("c") != -1){
       cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
//D
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll a,b,n;
	cin >> a >> b >> n;
	ll x = min(n,b-1);
	ll ans = floor((double)a*x/b) - a*floor((double)x/b);
	cout << ans;
	return 0;
}


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


int main() {
  ll n;
  cin >> n;
  vector<ll> a(1100000);
  rep(i, 3*n) cin >> a[i];
  sort(&a[0], &a[0]+n*3);
  
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    ans += a[n + 2*i];
  }
  cout << ans << endl;
}




Measured memory_bytes: 8832
'''input
100000 5
'''
from math import ceil, log2
N, K = [int(x) for x in input().split()]

ats = 0.0

for i in range(1, N+1):
	if i >= K:
		ats += 1/N
		continue

	ats += 1/N/(2.0**(float(ceil(log2(K/i)))))

print(ats)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
typedef pair<LL,LL> PL;

const int MOD=1000000007;
int INF=100100100;
int main(){
  int n;cin>>n;
  string s,t;cin>>s>>t;
  for(int i=0;i<2*n;i++){
    if(i%2==0)cout<<s[i/2];
    else cout<<t[i/2];
  }
  cout<<endl;
  return 0;
}

Measured memory_bytes: 256
import sys
a=sys.stdin.readline()
res = [int(i) for i in a.split(" ")] 
N,L = [res[i] for i in (0,1)]
flavour1=0
if (N>=2 and N<=200) and (L>=-100 and L<=100) and type(N)==int and type(L)==int:
    a1=[x for x in range(1,N+1)]
    b=[(L+i-1) for i in a1]
    for i in a1:
        flavour1+=b[i-1]
    c=[abs(x) for x in b]
    d=min(c)
    e=c.index(d)
    print((flavour1)-(b[e]))
else:
    print("Error")

Measured memory_bytes: 3064
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n, k, q;
    cin >> n >> k >> q;
    long a[n];
    set<long> mins;
    for(int i=0; i<n; i++){
        cin >> a[i];
        mins.insert(a[i]);
    }
    long ans = 1e18;
    for(auto mi: mins){         // Y to be tested
        vector<long> v;
        vector<long> t;
        for(int i=0; i<n; i++){
            if(a[i] < mi){
                if(t.size() >= k){
                    sort(t.begin(), t.end());
                    for (int j = 0; j< t.size()-k+1; j++) {
                        v.push_back(t[j]);
                    }
                }
                t.clear();
            }else{
                t.push_back(a[i]);
            }
        }
        if(t.size() >= k){
            sort(t.begin(), t.end());
            for (int j = 0; j< t.size()-k+1; j++) {
                v.push_back(t[j]);
            }
        }
        if(v.size() < q) continue;
        sort(v.begin(), v.end());
        ans = min(ans, v[q-1]-v[0]);
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 512
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Convert;
using static System.Math;
using Pair = System.Tuple<int, int>;
using Edge = System.Tuple<int, int, long>;
//using Debug;
//using static System.Globalization.CultureInfo;

class Program
{
    static void Main(string[] args)
    {
        var nq = Input.ar;
        var str = ReadLine();
        var qur = Enumerable.Repeat(0, nq[1]).Select(v => ReadLine().Split(' ')).ToArray();
        var left = 0;
        var right = nq[0]-1;
        qur = qur.Reverse().ToArray();
        for (var i = 0; i < nq[1]; i++)
        {
            if (left != nq[0] && qur[i][0][0] == str[left] && qur[i][1][0] == 'L')
                left++;
            if (left != nq[0] && left != 0 && qur[i][0][0] == str[left - 1] && qur[i][1][0] == 'R')
                left--;
            if (right != -1 && qur[i][0][0] == str[right] && qur[i][1][0] == 'R')
                right--;
            if (right != -1 && right != nq[0] - 1 && qur[i][0][0] == str[right + 1] && qur[i][1][0] == 'L')
                right++;
        }
        WriteLine(Min(-left + right + 1, nq[0]));
    }
}

public class Input
{
    public static string read => ReadLine();
    public  static int[] ar => Array.ConvertAll(read.Split(' '), int.Parse);
    public  static int num => ToInt32(read);
    public static long[] arL => Array.ConvertAll(read.Split(' '), long.Parse);
    public  static long numL => ToInt64(read);
    public static char[][] gred(int h) 
        => Enumerable.Repeat(0, h).Select(v => read.ToCharArray()).ToArray();
    public static int[][] twodim(int num)
        => Enumerable.Repeat(0, num).Select(v => ar).ToArray();
    public static long[][] twodimL(int num)
        => Enumerable.Repeat(0, num).Select(v => arL).ToArray();
    public const long Inf = (long)1e18;
    public const double eps = 1e-6;
    public  const string Alfa = "abcdefghijklmnopqrstuvwxyz";
    public  const int MOD = 1000000007;
}


Measured memory_bytes: 48584
// デバッグ実行：Ctrl+F5

using System;

class Program
{
    static void Main(string[] args)
    {
        String line;
        line = Console.ReadLine();
        String[] words = line.Split(' ');
        int A = int.Parse(words[0]);

        if (A % 2 == 1)
        {
            Console.WriteLine(A / 2 * (A / 2 + 1));
        }
        else
        {
            Console.WriteLine(A / 2 * A / 2);
        }
    }
}

Measured memory_bytes: 13268