akhauriyash/Code-Regression huggingface dataset:
n,m = list(map(int,input().split()))
x = n//2
y = n//2+1

temp_used = [0] * (n+1)

for i in range(m):
    print("{x} {y}".format(x=x,y=y))
    temp_used[y-x]+=1
    temp_used[n+x-y]+=1
    x-=1
    y+=1
    if temp_used[y-x]==1 or temp_used[n+x-y]==1 or y-x==n/2:
        y+=1

print("")

Measured memory_bytes: 10460
#include <bits/stdc++.h>
#define meow(args...) fprintf(stderr, args)
typedef unsigned u32;
typedef unsigned long long u64;
const u32 P=998244353;
int n, m;
u32 p[1<<18], f[1<<18], d[1<<18];
u32 inc(u32 &a, u32 b) {return (a+=b)<P?a:(a-=P);}
u32 dec(u32 &a, u32 b) {return (a-=b)&0x80000000?(a+=P):a;}
u32 sum(u32 a, u32 b) {return inc(a, b);}
u32 dif(u32 a, u32 b) {return dec(a, b);}
u64 power(u64 a, int b) {
	u64 ans=1;
	for(; b; a=a*a%P, b>>=1) if(b&1) ans=ans*a%P;
	return ans;
}
void wt(u32 *a) {
	for(int i=1; i<m; i<<=1)
		for(int j=i; j<m; j=j+1|i) {
			u32 s=a[j-i], t=a[j];
			a[j-i]=sum(s, t);
			a[j]=dif(s, t);
		}
}
void iwt(u32 *a) {
	u64 inv=power(m, P-2);
	wt(a);
	for(int i=0; i<m; ++i) a[i]=a[i]*inv%P;
}
int main() {
	assert(scanf("%d", &n)==1);
	m=1<<n;
	for(int i=0; i<m; ++i) assert(scanf("%d", p+i)==1);
	u64 inv=power(std::accumulate(p, p+m, 0), P-2);
	for(int i=0; i<m; ++i) p[i]=(u64)inv*p[i]%P;
	wt(p);
	f[0]=1;
	iwt(f);
	for(int i=1; i<m; ++i) d[i]=power(P+1-p[i], P-2);
	iwt(d);
	inv=power(f[0], P-3);
	for(int i=0; i<m; ++i) printf("%llu\n", ((u64)f[i]*d[0]+(u64)(P-f[0])*d[i])%P*inv%P);
	return 0;
}


Measured memory_bytes: 5888
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void POSS(T condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
template<class T> inline void Poss(T condition){ if(condition) cout << "Possible" << endl; else cout << "Impossible" << endl; }
template<class T> inline void First(T condition){ if(condition) cout << "First" << endl; else cout << "Second" << endl; }
int character_count(string text, char character){ int ans = 0; for(int i = 0; i < text.size(); i++){ ans += (text[i] == character); } return ans; }
long power(long base, long exponent, long module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ long root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position move_pattern[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++){ ans += to_string(*i) + " "; } ans.pop_back(); cout << ans << endl; }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
#define mod long(1e9 + 7)
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl(long(n))
#define fcout cout << fixed << setprecision(10)
#define highest(x) (63 - __builtin_clzl(x))

int main(){
    int A, B, C;
    cin >> A >> B >> C;
    cout << max({A, B, C}) - min({A, B, C}) << endl;
}


Measured memory_bytes: 256
import sys
import math
def get_array(): return list(map(int,sys.stdin.readline().strip().split()))
def get_ints(): return map(int,sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()
x,n=get_ints()
p=get_array()
ans1=x 
ans2=x
for j in range(x,-100,-1):
    if j not in p:
        ans1=j 
        break
for k in range(x,200):
    if k not in p:
        ans2=k 
        break
if ans2-x<x-ans1:
    print(ans2)
elif x-ans1<ans2-x:
    print(ans1)
else:
    print(ans1)
            
            

    

Measured memory_bytes: 62180
#!/usr/bin/env ruby
# frozen_string_literal: true

S = gets.chomp.chars
T = gets.chomp.chars

checker = 1
(0..S.length - 1).each do |i|
  if S[i] != T[i]
    checker = 0
    break
  end
end

if checker == 0
  puts 'No'
else
  puts 'Yes'
end



Measured memory_bytes: 14392
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;

int main()
{
  int N; cin >> N;
  vector<string> s(N); REP(i, N) cin >> s[i];

  ll ans = 0, acnt = 0, bcnt = 0, abcnt = 0;
  for (string ss : s) {
    for (int i = 1; i < ss.size(); ++i) {
      if (ss[i-1] == 'A' and ss[i] == 'B') ans++;
    }

    if (ss.front() == 'B' and ss.back() == 'A') abcnt++;
    else if (ss.front() == 'B') bcnt++;
    else if (ss.back() == 'A') acnt++;
  }

  // printf("ans: %lld, %lld, %lld, %lld\n", ans, acnt, bcnt, abcnt);

  ans += max(abcnt-1, 0LL);
  if (abcnt > 0) {
    if (acnt > 0) {
      ans++;
      acnt--;
    }
    if (bcnt > 0) {
      ans++;
      bcnt--;
    }
  }

  ans += min(acnt, bcnt);

  cout << ans << endl;
}

Measured memory_bytes: 768
#include<bits/stdc++.h>
#define MAX_LOG_V 20
#define MAX_V 100005
using namespace std;
typedef long long ll;
vector<int> G[MAX_V],G2[MAX_V];
int root;
int parent[MAX_LOG_V][MAX_V];
int depth[MAX_V];

void dfs(int v,int p,int d){
  parent[0][v]=p;
  depth[v]=d;
  for(int i=0;i<G[v].size();i++)
    if(G[v][i]!=p)dfs(G[v][i],v,d+1);
}

void init(int V){
  dfs(root,-1,0);
  for(int k=0;k+1<MAX_LOG_V;k++)
    for(int v=0;v<V;v++)
      if(parent[k][v]<0)parent[k+1][v]=-1;
      else parent[k+1][v]=parent[k][parent[k][v]];
}

int lca(int u,int v){
  if(depth[u]>depth[v])swap(u,v);
  for(int k=0;k<MAX_LOG_V;k++){
    if((depth[v]-depth[u])>>k&1)v=parent[k][v];
  }
  if(u==v)return u;
  for(int k=MAX_LOG_V-1;k>=0;k--){
    if(parent[k][u]!=parent[k][v]){
      u=parent[k][u];
      v=parent[k][v];
    }
  }
  return parent[0][u];
}

queue<int> q;

int main(){
  int n,p;
  cin>>n;
  for(int i=1;i<n;i++){
    cin>>p; p--;
    G[i].push_back(p);
    G[p].push_back(i);
    G2[p].push_back(i);
  }
  init(n);
  for(int i=0;i<n;i++)
    sort(G2[i].begin(),G2[i].end());
  for(int i=0;i<G2[0].size();i++)
    q.push(G2[0][i]);
  int pv=0;
  ll ans=0;
  while(!q.empty()){
    int v=q.front(); q.pop();
    int r=lca(pv,v);
    ans+=depth[v]+depth[pv]-depth[r]*2;
    for(int i=0;i<G2[v].size();i++)
      q.push(G2[v][i]);
    pv=v;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 26836
#include <iostream>
#include <string>
#include <vector>
#include <utility>
using namespace std;
int main(void){
  char n[4];
  cin >> n;
  if((n[0]==n[1] && n[1]==n[2])||(n[1]==n[2] && n[2]==n[3]))
    cout << "Yes" << "\n";
  else
    cout << "No\n";
  return 0;
}


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n;
  cin >> n;
  int a[n];
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  
  bool judge = true;
  for(int i = 0; i < n; i++) {
    if(a[i] % 2 == 0) {
      if(a[i] % 3 != 0 && a[i] % 5 != 0) {
        judge = false;
        break;
      }
    }
  }
  if(judge == true) {
    cout << "APPROVED" << endl;
  }else {
    cout << "DENIED" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using V = vector<ll>;
#define _GLIBCXX_DEBUG
#define rep(i, a, b) for(int i = a; i < b; i++)
#define ALL(v) v.begin(), v.end()

int main(){
    string a,b,c; cin>>a>>b>>c;
    if(a[a.size()-1]==b[0]&&b[b.size()-1]==c[0])
    cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}


Measured memory_bytes: 256
W,H,x,y,r=map(int,input().split())
if x-r<0 or x+r>W:
    print("No")
elif x-r>=0 and x+r<=W:
    if y-r<0 or y+r>H:
        print("No")
    elif y-r>=0 or y+r<=H:
        print("Yes")


Measured memory_bytes: 5596
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<climits>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>v;
    map<int,vector<int> >ma;
    string str;
    int mi=INT_MAX;
    for(int i=0;i<n;i++){
        int m;
        cin>>m;
        v.push_back(m);
        ma[m].push_back(i);
    }
    mi=0;
    //find mi
    while(1){
        //find all digits of mi
        vector<int>d;
        int mi_=mi;
        while(mi_){
            d.push_back(mi_%10);
            mi_/=10;
        }
        reverse(d.begin(),d.end());
        //search 1st in ma and traverse
        
        if(!d.size())d.push_back(0);
       // cout<<"cout<<d ";for(int i=0;i<d.size();i++)cout<<d[i];cout<<endl;
        bool f=false;
        for(int i=0;i<ma[d[0]].size();i++){
            f=true;
            int j=0;
            for(;j<d.size()&&(ma[d[0]][i]+j<v.size());j++){
                if(v[ma[d[0]][i]+j]!=d[j]){
                    f=false;
                    break;
                }
                //cout<<"--- "<<v.size()<<" "<<ma[d[0]][i]+j<<" "<<v[ma[d[0]][i]+j]<<" "<<d[j]<<endl;
            }
            f=f&&(j==d.size());
            if(f){
                break;
            }
        }
        //cout<<mi<<" f:"<<f<<endl;
        if(!f){
            for(int j=0;j<d.size();j++){
                cout<<d[j];
            }
            cout<<endl;
            return 0;
        }
        //if can't find then break
        //else mi++
        mi++;
    }
}

Measured memory_bytes: 1232
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
long long n, m, a[210000], b[210000], col[210000], cnt, d[210000], e[210000], dist[210000];
vector<long long>x[210000], w[210000], z;
map<pair<int, int>, int>M; vector<pair<int, int>>y[210000];

void dfs(int p) {
	col[p] = cnt;
	for (int i = 0; i < x[p].size(); i++) {
		if (col[x[p][i]] == 0)dfs(x[p][i]);
	}
}
int main() {
	for (int i = 0; i < 210000; i++) { x[i].clear(); d[i] = 0; e[i] = 0; a[i] = 0; b[i] = 0; col[i] = 0; cnt = 0; z.clear(); }
	cin >> n >> m; M.clear();
	for (int i = 0; i < m; i++) {
		cin >> a[i] >> b[i]; if (a[i] > b[i])swap(a[i], b[i]);
		if (M[make_pair(a[i], b[i])] == 1) { a[i] = 0; b[i] = 0; continue; }
		M[make_pair(a[i], b[i])] = 1;
		z.push_back(a[i]); z.push_back(b[i]);
	}
	sort(z.begin(), z.end()); z.erase(unique(z.begin(), z.end()), z.end());
	for (int i = 0; i < m; i++) {
		if (a[i] == 0 && b[i] == 0)continue;
		a[i] = lower_bound(z.begin(), z.end(), a[i]) - z.begin();
		b[i] = lower_bound(z.begin(), z.end(), b[i]) - z.begin();
		x[a[i]].push_back(b[i]); x[b[i]].push_back(a[i]);
	}
	long long ans = n*n - 1LL * z.size()*z.size();
	for (int i = 0; i < z.size(); i++) {
		if (col[i] >= 1)continue;
		cnt++; dfs(i);
	}

	for (int i = 0; i < z.size(); i++)d[col[i]]++;
	for (int i = 0; i < m; i++) { if (a[i] >= 1 || b[i] >= 1) e[col[a[i]]]++; }
	for (int i = 0; i < m; i++) { if (a[i] >= 1 || b[i] >= 1) y[col[a[i]]].push_back(make_pair(a[i], b[i])); }
	
	ans += cnt*cnt;
	long long E = 0;
	for (int i = 1; i <= cnt; i++){
		//二部グラフであるかどうか判定
		for (int j = 0; j < y[i].size(); j++) {
			w[y[i][j].first].push_back(y[i][j].second);
			w[y[i][j].second].push_back(y[i][j].first);
			dist[y[i][j].first] = -1; dist[y[i][j].second] = -1;
		}
		queue<int>Q; Q.push(y[i][0].first); dist[y[i][0].first] = 0;
		bool OK = true;
		while (!Q.empty()) {
			int a1 = Q.front(); Q.pop();
			for (int j = 0; j < w[a1].size(); j++) {
				if (dist[w[a1][j]] == dist[a1]) { OK = false; }
				if (dist[w[a1][j]] == -1) { Q.push(w[a1][j]); dist[w[a1][j]] = 1 - dist[a1]; }
			}
		}
		if (OK == true)E++;
	}
	ans += E*E;
	cout << ans << endl;
	return 0;
}

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

typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 28;

// ====================================================================

int main() {
  char c;
  cin >> c;
  cout << char(c + 1) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <set>
#include <utility>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <cstdio>
#include <map>

using namespace std;

using ll = long long;
using P = pair<ll,ll>;

#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define rrep(i,x) for(ll i = ((ll)(x) - 1); i >= 0; i--)

#define all(x) (x).begin(), (x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define chmin(x,y) (x=min(x,y))
#define chmax(x,y) (x=max(x,y))

//ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

const ll mod = 1e9 + 7;
const ll IMF = 1LL<<29;
const double PI = 3.14159265358979323846;






int main(){

        int H,W;
        cin >> H >> W;

        vector<vector<int>> cnt(H, vector<int>(W));

        vector<string> s(H);

        rep(i,H) cin >> s[i];


        rep(i,H){
                //毎回チェックする場所を決定するためのもの。
                vector<int> done(W);
                rep(j,W){
                        //もし壁に当たったり、もう訪れた場所ならcontinue
                        if(s[i][j] == '#') continue;
                        if(done[j]) continue;

                        //何個明かりを照らすますがあるか記録する。
                        int l = 0;
                        while(j+l < W){
                                if(s[i][j+l] == '#') break;
                                l++;
                        }

                        //その照らせるマス目に照らせる数を代入してもうしたよーっていうチェックをする。
                        rep(k,l){
                                cnt[i][j+k] += l;
                                done[j+k] = 1;
                        }
                }
        }


        rep(i,W){
                vector<int> done(H);
                rep(j,H){
                        if(s[j][i] == '#') continue;
                        if(done[j]) continue;

                        int l = 0;
                        while(j+l < H){
                                if(s[j+l][i] == '#') break;
                                l++;
                        }

                        rep(k,l){
                                cnt[j+k][i] += l;
                                done[j+k] = 1;
                        }
                }
        }


        int ans = 0;
        rep(i,H) rep(j,W) chmax(ans, cnt[i][j]);
        cout << ans -1 << endl;
        return 0;
}



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

int main(){
	vector<int> v = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
	int K;cin >> K;
	K--;
	cout<<v[K]<<endl;
}

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

#include <math.h>
#include <stdlib.h>


#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

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

// const int INF = 1001001001;
// long long max => LLONG_MAX

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int a, b, c; cin >> a >> b >> c;
    if(a <= c && c <= b) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}


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

using namespace std;

#define REP(i, a, n) for (int i = a, _n = n; i <= _n; ++i)
#define DREP(i, a, n) for (int i = a, _n = n; i >= _n; --i)
#define FOR(i, a, n) for (int i = a, _n = n; i < _n; ++i)
#define EREP(i, a) for (int i = first[a]; i; i = edge[i].nxt)
#define debug(x) cout << #x << " = " << x << endl

int n, k;
const int SIZE = 100005;

int first[SIZE], ecnt;
struct Edge {
	int v, nxt, dis, c;
} edge[SIZE << 1];
void Add_Edge (int u, int v, int c, int dis) {
	++ecnt;
	edge[ecnt].v = v;
	edge[ecnt].dis = dis;
	edge[ecnt].c = c;
	edge[ecnt].nxt = first[u];
	first[u] = ecnt;
}

int tree[SIZE], Lson[SIZE * 18], Rson[SIZE * 18], cnt[SIZE * 18], node_cnt;
long long tot[SIZE * 18];

void Insert (int& rt, int od, int L, int R, int x, int d) {
	rt = ++node_cnt;
	Lson[rt] = Lson[od];
	Rson[rt] = Rson[od];
	if (L == R) {
		cnt[rt] = cnt[od] + 1;
		tot[rt] = tot[od] + d;
		return;
	}
	int mid = L + R >> 1;
	if (x <= mid) Insert (Lson[rt], Lson[od], L, mid, x, d);
	else Insert (Rson[rt], Rson[od], mid + 1, R, x, d);
}

long long y;
long long Query (int rt, int L, int R, int x) {
	if (L == R) return cnt[rt] * y - tot[rt];
	int mid = L + R >> 1;
	if (x <= mid) return Query (Lson[rt], L, mid, x);
	else return Query (Rson[rt], mid + 1, R, x);
}

long long dis[SIZE];
int dp[SIZE][18], dep[SIZE];

void DFS (int u, int fa) {
	EREP (i, u) {
		Edge& e = edge[i];
		if (e.v == fa) continue;
		dis[e.v] = dis[u] + e.dis;
		dep[e.v] = dep[u] + 1;
		dp[e.v][0] = u;
		Insert(tree[e.v], tree[u], 1, n - 1, e.c, e.dis);
		DFS (e.v, u);
	}
}

int Up (int x, int step) {
	REP (i, 0, 17) if (1 << i & step)
		x = dp[x][i];
	return x;
}

int LCA (int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	x = Up (x, dep[x] - dep[y]);
	if (x == y) return x;
	DREP (i, 17, 0) if (dp[x][i] != dp[y][i])
		x = dp[x][i], y = dp[y][i];
	return dp[x][0];
}

int main () {
	scanf ("%d%d", &n, &k);

	REP (i, 1, n - 1) {
		int u, v, c, d;
		scanf ("%d%d%d%d", &u, &v, &c, &d);
		Add_Edge (u, v, c, d);
		Add_Edge (v, u, c, d);
	}

	DFS (1, 0);

	REP (i, 1, 17) REP (j, 1, n)
		dp[j][i] = dp[dp[j][i - 1]][i - 1];

	REP (i, 1, k) {
		int x, u, v;
		scanf ("%d%lld%d%d", &x, &y, &u, &v);
		int lca = LCA (u, v);
		printf ("%lld\n", dis[u] + dis[v] + Query (tree[u], 1, n - 1, x) + Query (tree[v], 1, n - 1, x) - 2 * dis[lca] - 2 * Query (tree[lca], 1, n - 1, x));
	}

	return 0;
}


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

int main() {
	int n,k;
	cin>>n>>k;
	vector<int>prev(n);
	for(int i=0;i<n;i++){
	    cin>>prev[i];
	}
	vector<int>act(n,n);
	for(int i=0; i<k &&prev!=act;i++){
	    vector<int>next(n+1,0);
	    for(int j=0; j<n; j++){
	        int k=max(0,j-prev[j]);
	        int l=min(n,j+prev[j]+1);
	        next[k]++;
	        next[l]--;
	        //cout<<k<<" "<<l<<endl;
	    }
	    for(int j=0; j<n; j++){
	        next[j+1]+=next[j];
	        //cout<<next[j]<<" ";
	    }
	    next.pop_back();
	    //cout<<endl;
	    prev=next;
	}
	for(int i=0;i<n;i++)cout<<prev[i]<<" ";
}


Measured memory_bytes: 5584
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define F_OR(i, a, b, s) for (int i = (a); ((s) > 0 ? i < (b) : i > (b)); i += (s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, (b)<(e)?1:-1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define FOR(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)(__VA_ARGS__)
#ifdef LOCAL
#define dbg(x) cerr << '[' << #x << ":" << (x) << "]\n"
#else
#define dbg(x)
#endif
ll dp[100001];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,w;cin>>n>>w;
	fill(dp,dp+100001,1e15);
	dp[0]=0;
	ll ans=0;
	FOR(n){
		ll a,b;cin>>a>>b;
		FOR(j,n*1000+1,1){
			if(j-b>=0)dp[j]=min(dp[j],a+dp[j-b]);
			else break;
		}
	}
	FOR(i,1,n*1000+1){
		if(dp[i]<=w)ans=max(ans,(ll)i);
	}
	cout<<ans<<'\n';
}

Measured memory_bytes: 4396
// ALDS1_2_C
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Card{
	char mark;
	int value;
};

void Swap(struct Card &x, struct Card &y){
	struct Card z = x;
	x = y;
	y = z;
}

void BubbleSort(vector<Card> &C){
	for(int i=0;i<C.size();i++)
		for(int j=C.size()-1;j>i;j--)
			if(C[j].value < C[j-1].value)
				Swap(C[j], C[j-1]);
}

void SelectionSort(vector<Card> &C){
	for(int i=0;i<C.size();i++){
		int minj = i;
		for(int j=i;j<C.size();j++)
			if(C[j].value < C[minj].value)
				minj = j;
		Swap(C[minj], C[i]);
	}
}

bool match(Card a, Card b){
	if((a.mark == b.mark) && (a.value == b.value))
		return true;
	else
		return false;
}

bool isStable(vector<Card> a, vector<Card> b){
	for(int i=0;i<a.size();i++)
		if(!match(a[i], b[i]))
			return false;

	return true;
}

void print_struct(vector<Card> a){
	for(int i=0;i<a.size();i++){
		if(i!=0) cout<<" ";
		cout<<a[i].mark<<a[i].value;
	}
	cout<<endl;
}

int main(){
	int n;
	string str;
	vector<Card> a, b;
	Card card;

	cin>>n;
	for(int i=0;i<n;i++){		
		cin>>str;
		card.mark = str[0];
		card.value = str[1] - '0';
		a.push_back(card);
		b.push_back(card);
	}

	BubbleSort(a);
	SelectionSort(b);

	print_struct(a);
	cout<<"Stable"<<endl;
	
	print_struct(b);
	if(isStable(a, b))
		cout<<"Stable"<<endl;
	else
		cout<<"Not stable"<<endl;
	
	return 0;
}

Measured memory_bytes: 1232
N = int(input())
S = input()
max_kind = 0

for i in range(N):
    sl = set()
    sr = set()

    for j, char in enumerate(S):
        if j <= i:
            sl.add(char)
        else:
            sr.add(char)
    
    if len(sl & sr) > max_kind:
        max_kind = len(sl & sr)

print(max_kind)

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

int main() {
  int r, g, b;
  cin >> r >> g >> b;

  int sum = r * 100 + g * 10 + b;
  if (sum % 4 == 0)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}


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

int d[500010],n,D,q;

int p[500010];
bool ok[500010];

int main()
{
    scanf("%d%d",&n,&D);
    for(int i=1;i<=n;++i)
	scanf("%d",&d[i]);

    p[n+1]=1;
    for(int i=n;i;--i)
	if(d[i]<2*p[i+1])p[i]=p[i+1]+d[i];
	else p[i]=p[i+1];

    for(int i=1;i<=n;++i)
    {
	ok[i]=D>=p[i+1];
	D=std::min(D,abs(D-d[i]));
    }

    scanf("%d",&q);
    for(int i=1,x;i<=q;++i)
    {
	scanf("%d",&x);
	puts(ok[x]?"YES":"NO");
    }
    
    return 0;
}


Measured memory_bytes: 6272
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i < (int)(n); i++)
typedef long long ll;
int main() {
	int n, m;
	cin >> n >> m;
	vector< vector<int> > jobs(m); 
	rep(i, n) {
		int a, b;
		cin >> a >> b;
		if(a > m)continue; 
		jobs[m-a].push_back(b); 
	}      
	priority_queue<int> q;
	ll ans = 0;      
	for (int i= m-1; i >= 0; --i){	
		for(int b : jobs[i]) { 
			q.push(b);
		}		
		if(!q.empty()) {  
		ans += q.top(); 
		q.pop(); 
		}
	}
	cout << ans << endl;
    return 0;	
}

Measured memory_bytes: 5632
#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 500001;
 
int A[MAXN], B[MAXN];
vector<int> T[4 * MAXN];
 
void build(int i, int l, int r) {
    if (l == r) T[i].push_back(B[r]);
    else {
        int m = (l + r) / 2;
        build(2 * i, l, m);
        build(2 * i + 1, m + 1, r);
        merge(T[2 * i].begin(), T[2 * i].end(), 
              T[2 * i + 1].begin(), T[2 * i + 1].end(),
              back_inserter(T[i]));
    }
}
 
int ask(int i, int l, int r, int ql, int qr) {
    if (r < ql || qr < l) 
        return 0;
    if (ql <= l && r <= qr) 
        return lower_bound(T[i].begin(), T[i].end(), ql) - T[i].begin();
    int m = (l + r) / 2;
    return ask(2 * i, l, m, ql, qr) + ask(2 * i + 1, m + 1, r, ql, qr);
}
 
void solver() {
    int N, M;
    cin >> N >> M;
    //cin >> N;
 
    for(int i = 0; i < N; ++i) 
        cin >> A[i];
 
    memset(B, -1, sizeof (B));
    
    map<int,int> last;
 
    for (int i = 0; i < N; ++i) {
        if (!last.count(A[i]))
            B[i] = -1;
        else B[i] = last[A[i]];
 
        last[A[i]] = i;
    }
 
    build(1, 0, N - 1);
    
    //cin >> M;
 
    while(M-- > 0) {
        int left, right;
        cin >> left >> right;
        cout << ask(1, 0, N - 1, left - 1, right - 1) << '\n';
    }
 
}
 
int main() {
 
    ios_base :: sync_with_stdio(0); cin.tie(NULL);
 
    int t;
    //cin >> t;
    t = 1;
 
    while(t--)
        solver();
 
    return 0;
}

Measured memory_bytes: 142920
kk = int(input())
if kk < 10:
    print(kk)
    exit()
 
 
dp = [[0] * 10 for _ in range(15)]
dp[0] = [1] * 10
for i in range(14):
    #dp[i+1][0] += sum(dp[i])
    for j in range(10):
        for k in range(-1, 2):
            if not (0 <= j + k < 10):
                continue
            dp[i + 1][j + k] += dp[i][j]
 
a = 0
for i in range(15):
    if a+sum(dp[i][1:]) >= kk:
        break
    a += sum(dp[i][1:])
 
ii = i
 
 
for j in range(1, 10):
    if a + dp[i][j] >= kk:
        kk -= a
        break
    a += dp[i][j]
 
ans = j
for i in reversed(range(ii)):
    a = 0
    for k in range(-1, 2):
        if not (0 <= j + k < 10):
            continue
        if a + dp[i][j + k] >= kk:
            kk -= a
            j = j + k
            ans = ans * 10 + j
 
            break
        a += dp[i][j + k]
 
 
print(ans)

Measured memory_bytes: 3064
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <chrono>
#include <random>
#include <tuple>
#include <utility>
#include <fstream>
#include <complex>

const long INF = (1l << 30);
const long LINF = (1l << 60);

long d, g;
long p[11], c[11];

long ans = LINF;

long divCeil(long a, long b){
    return (a-1)/b+1;
}

int main(){
    //printf("%ld\n", sizeof(long));
    scanf("%ld%ld", &d, &g);
    for(int i = 0; i < d; i++){
        scanf("%ld%ld", p+i, c+i);
    }
    for(long i = 0; i < (1 << d); i++){
        long score = 0;
        long prob = 0;
        for(int j = 0; j < d; j++){
            if((1 << j) & i){
                score += p[j] * (j+1) * 100 + c[j];
                prob += p[j];
            }
        }
        //std::cout << std::bitset<sizeof(i)>(i).to_string() << std::endl;
        if(score >= g){
            //printf("  %ld\n", prob);
            ans = std::min(prob, ans);
            continue;
        }
        //printf("    %ld\n", score);
        long rem = -1;
        for(int j = d-1; j >= 0; j--){
            if(!((1 << j) & i)){
                //printf("      %ld\n", j);
                rem = j;
                break;
            }
        }
        //printf("    %ld\n", rem);
        if(score + (p[rem] - 1) * (rem+1) * 100 < g){
            continue;
        }
        prob += divCeil(g - score, (rem+1) * 100);
        //printf("  %ld\n", prob);
        ans = std::min(prob, ans);
    }
    printf("%ld\n", ans);
}


Measured memory_bytes: 256
CARDMAX = 100
POINTMAX = 100
    
def main():
    head = []
    c_taro = []
    c_hana = []

    while True:
        # 初期化
        head.clear()
        c_taro.clear()
        c_hana.clear()

        # 先頭情報
        head = input()
        head = head.split(" ")

        # 終了処理
        if head == ['0', '0']:
            return 0

        for j in range(int(head[0])):
            c_taro.append(int(input()))

        for j in range(int(head[1])):
            c_hana.append(int(input()))

        sum_taro = showsum(c_taro)
        sum_hana = showsum(c_hana)
        avee = showave(sum_taro, sum_hana)
        toave = avee - sum_taro

        print(showchcard(c_taro, c_hana, toave))
"""
        print("headdata::")
        print(head)
        print("c_taro::")
        print(c_taro)
        print("c_hana::")
        print(c_hana)
        print("sum_taro::")
        print(sum_taro)
        print("sum_hana::")
        print(sum_hana)
        print("average::")
        print(avee)
        print("")
"""

def showsum(array):
    summ = 0
    for item in array:
        summ += item
    return summ

def showave(a, b):
    return (a + b) / 2

def showchcard(tarray, harray, toave):
    wa = CARDMAX * 2 + 1
    for tnum in tarray:
        for hnum in harray:
            if hnum - tnum == toave:
                if wa >= (hnum + tnum):
                    tans = tnum
                    hans = hnum
                    wa = tans + hans

    if wa != CARDMAX * 2 + 1:
        result = str(tans) + " " + str(hans)
        return result
    else:
        return -1

main()



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

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

#define CIN(T, x) T x; cin >> x;
#define CINS(T, x, N) vector<T> x(N); for(int i = 0; i < (N); i++) { cin >> x[i]; }
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << " "; } cout << "\n";
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << "\n";


int main() {

    CIN(double, W);
    CIN(double, H);
    CIN(double, x);
    CIN(double, y);

    double S = W * H / 2;
    int count = 0;
    if ( x == W / 2 && y == H / 2 ) {
        count = 1;
    }
    
    printf("%.10f", S);
    cout << " " << count << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005
#define m 1000000007
#define dd double
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep1(i,b) for(int i=1;i<=b;i++)
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define F first
#define S second
int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin>>n;
	if(n%10==7)
	{
		cout<<"Yes";
	}
	else
	{
		n/=10;
		if(n%10==7)
		{
			cout<<"Yes";
		}
		else
		{
			n/=10;
			if(n%10==7)
				cout<<"Yes";
			else
				cout<<"No";
		}
	}
	return 0;
}

Measured memory_bytes: 3596
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
#include <set>
#include <map>

using namespace std;

#define EPS 1e-14
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) FOR(i, 0, n)
#define PI 2*acos(0.0)
#define ALL(a) (a).begin(),(a).end()
#define DEBUG(x) cout<<#x <<": "<< x << "\n"
#define DEBUG_ARR(a) REP(i, size(a)){ cout << #a << "[" << i << "]: " << a[i] << "\n"; }
const int VX[] = { 0, 1, 0, -1 };
const int VY[] = { 1, 0, -1, 0 };
const long MOD = 1000000007;

int main()
{
	//	--- I/O 高速化 ---
	cin.tie(0);
	ios::sync_with_stdio(false);
	// --- ここまで ---

	int a, b, c;
	cin >> a >> b >> c;

	cout << a + b + c - max(a, max(b, c)) << "\n";


	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
string s;
int main(){
    cin>>s;
    int c=s.size();
    if(c%2!=0){
        printf("No");
        return 0;
    }
    for(int i=0;i<c/2;i++){
        short t=abs(s[i]-s[c-i-1]);
        if(t!=1&&t!=2){ 
            printf("No\n"); 
            return 0;
        }
    }
    printf("Yes\n"); 
    return 0;
}

Measured memory_bytes: 512
s = str(input())
n = len(s)
s1 = s[:]
s1 = s1[:(n-1)//2]
s2 = s[:]
s2 = s2[((n+3)//2)-1:]
if s == s[::-1] and s1 == s1[::-1] and s2 == s2[::-1]:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
typedef long double ld;
const ld eps = 1.0e-11; // 許容される誤差
 
ld mysqrtl(ld x)
{
  ld a = sqrt((double)x); // 近似値
  do {
    a = (a + x/a) / 2.0L;
  } while (fabsl(x - a*a) > eps);
  return a;
}
 
int main() 
{
	long double a, b, c;
	cin >> a >> b >> c;
	
	a /= 65536.0;
	b /= 65536.0;
	c /= 65536.0;
  
	cout << (((a+b-c) + 2.0*mysqrtl(a*b) < 0) ? "Yes" : "No") << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#define STMAX 50
int main(void)
{
  int i, slen, tlen, spos, tpos, sflag = 0;
  char str[STMAX+1], ttr[STMAX+1];
  scanf("%s%*c", str);
  scanf("%s%*c", ttr);
  slen = strlen(str);
  tlen = strlen(ttr);
  spos = slen - 1;
  tpos = tlen - 1;
  while (spos >= 0) {
    if (str[spos] != '?') {
      while (tpos < tlen && str[spos] != ttr[tpos]) tpos++;
    }
    tpos--;
    if (tpos == -1) {
      sflag = 1;
      break;
    }
    spos--;
  }
  if (sflag) {
    for (i = spos; i < spos + tlen; i++) str[i] = ttr[i-spos];
    for (i = 0; i < slen; i++) {
      if (str[i] == '?') str[i] = 'a';
    }
    printf("%s\n", str);
  } else printf("UNRESTORABLE\n");
}


Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<map>
#include<bitset>
using namespace std;

typedef long long ll;
#define rep(i, n) for(int i = 0;i < (n);i++)
#define repr(i, n) for(int i = (n);i >= 0;i--)
#define repf(i, m, n) for(int i = (m);i < (n);i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1;} return 0;}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//////////////////////////////////////////////////


int main() {
    int h, a; cin >> h >> a;
    cout << (h+a-1)/a << endl;
    return 0;
}

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

const long double CHANGE = 1e-8;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge {c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

const int nax = 3005;
int val[nax];
vector<int> w[nax];
bool vis[nax];
const int inf = 1e9;

int main() {
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &val[i]);
	for(int i = 0; i < n - 1; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		w[a].push_back(b);
		w[b].push_back(a);
	}
	vector<int> ans;
	for(int rep = 0; rep < n; ++rep) {
		pair<int,int> best = make_pair(inf, -1);
		for(int i = 1; i <= n; ++i) if(!vis[i])
			best = min(best, make_pair(val[i], i));
		int who = best.second;
		vis[who] = true;
		bool ok = false;
		for(int x : w[who])
			if(val[x] < val[who])
				ok = true;
		if(ok) {
			val[who] = inf;
			ans.push_back(who);
		}
	}
	sort(ans.begin(), ans.end());
	for(int x : ans) printf("%d ", x);
	puts("");
}



Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <cstring>
#include <cstdio>
#include <cmath>

using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using ll = long long;

#define MOD (ll)(1e9 + 7)
#define MAX_N 200000

// memo
ll fact[MAX_N], fact_inv[MAX_N];

// n!
void factorial_prepare (ll n) {
  fact[0] = fact[1] = 1;
  for (int i = 2; i <= n; ++i) {
    fact[i] = (i * fact[i - 1]) % MOD;
  }
}

// pow(x, n) := x^n
ll power (ll x, ll n) {
  if (n == 0) return 1LL;

  ll ret = power((x * x) % MOD, n / 2) % MOD;
  if (n % 2) ret = (ret * x) % MOD;

  return ret;
}

// x^(-1) ≡ x^(MOD - 2) (mod MOD)
// (x!)^(-1) ≡ (x!)^(MOD - 2) (mod MOD)
void inverse_prepare (ll x) {
  // (x!)^(-1)を求めて, その値にx, x-1, ... を順に掛ける
  fact_inv[x] = power(fact[x], MOD - 2);

  for (int i = x - 1; i >= 1; --i) {
    fact_inv[i] = ((fact_inv[i + 1] * (i + 1)) % MOD);
  }
}

// nCr, nPr の想定される最大の n で初期化
void init (ll n) {
  factorial_prepare(n);
  inverse_prepare(n);
}

// nCr
ll C (ll n, ll r) {
  if (n < r || r < 0) return 0LL;
  if (n == r || r == 0) return 1LL;
  // n! / ((n - r)! * r!)
  return (((fact[n] * fact_inv[r]) % MOD) * fact_inv[n - r]) % MOD;
}

// nPr
ll P (ll n, ll r) {
  if (n < r || r < 0) return 0LL;
  return (fact[n] * fact_inv[r]) % MOD;
}


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

  int h, w, a, b;

  cin >> h >> w >> a >> b;

  ll ans = 0;
  init(MAX_N); // nCr, nPr の想定される最大の n で初期化

  for (int i = b; i < w; ++i) {
    ans = (ans + (C(h - a - 1 + i, i) * C(a - 1 + w - i - 1, w - i - 1))) % MOD;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3328
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

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

    string s1, s2;
    cin >> s1;
    cin >> s2;

    long long count = 1;
    int color = 3;
    for (int i = 0; i < n; i++) {
        if (s1[i] == s2[i]) {
            count *= color;
            color = 2;
        } else {
            i++;
            if (color == 3)
                count *= 6;
            if (color == 2)
                count *= 2;
            if (color == 1)
                count *= 3;
            color = 1;
        }
    }
    cout << count % 1000000007 << endl;
    
    return 0;
}


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

#define int             long long int
#define ff              first
#define ss              second
#define pb              push_back

#define vi              vector <int>
#define pii             pair <int, int>

#define loop(i,s,e)     for(int i=s;i<e;i++)
#define rloop(i,e,s)    for(int i=e;i>=s;i--)
#define mset(a,f)       memset(a,f,sizeof(a))

#define endl            "\n"
#define sz(x)           ((int) x.size())
#define all(p)          p.begin(), p.end()

#define bug(...)        __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)        for (auto x : a) cout << x << " "; cout << endl
#define Print(a,x,y)    for (int i=x; i<y; i++) cout<< a[i]<< " "; cout << endl



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...);
}

const int N = 500005;
const int M = 1000000007;

int fact[N + 1];
int ifact[N + 1];

int add(int a, int b)
{
	if (a + b < 0) return a + b + M;
	if (a + b >= M) return a + b - M;
	return a + b;
}
int mul(int a, int b)
{
	return (a * b) % M;
}

int pwr(int a, int b)
{
	if (b == 0) return 1;
	int c = pwr(a, b / 2);
	if (b % 2 == 1) return mul(a, mul(c, c));
	return mul(c, c);
}

int inv(int a, int m)
{
	return pwr(a, m - 2);
}
void cal()
{
	fact[0] = 1;
	loop(i, 1, N + 1) fact[i] = mul(i, fact[i - 1]);

	ifact[N] = inv(fact[N], M);

	rloop(i, N - 1, 0) ifact[i] = mul(ifact[i + 1], i + 1);

}

int ncr(int n, int r)
{

	if (r > n) return 0;
	else
	{
		return mul(fact[n], mul(ifact[r], ifact[n - r]));
	}
}

// N, M -> N LENGTH SEQ, 1 <= A[i] <= M

// M >= N
// total -> m*(m - 1)(m - 2)....(m - i)....(m - n - 1)
// 2 A, B, s.t (A[i] != B[i]) for all  1 < i < n

// totals pairs = total * total -- > 0 id, 1 id , 2 id, 3 id
//                a[1] = b[1] -- > a[2] = b[2]
// 	                                       a[1] = b[1] -- > 3, 3
// 	                                               ncr(n, 1) * (mc1) * 1!*[ (m - 1) * (m - 2) * (m - 3).... ] * [ (m - 1) * (m - 2) * (m - 3).... ] -- > 1 id, 2 * id, 3 * 3id
// 	                                               ncr(n, 2) * (mc2) * 2!*[ m - 2 * m - 3 * m.][....]


void solve()
{
	cal();
	int n, m;
	cin >> n >> m;
	int ans = 1;

	loop(i, 0, n) ans = mul(ans, m - i);
	ans = mul(ans, ans);
	vi a(n + 1, 1);

	a[n - 1] = m - (n - 1);
	rloop(i, n - 2, 0) a[i] = mul(a[i + 1], m - i);

	loop(i, 1, n + 1)
	{
		int x = mul(ncr(n, i), mul(ncr(m, i), fact[i]));

		int y = mul(a[i], a[i]);

		x = mul(x, y);

		if (i % 2 == 0) ans = add(ans, x);
		else ans = add(ans, -x);

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

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

#ifndef ONLINE_JUDGE
	freopen("input.txt",  "r",  stdin);
	freopen("output.txt", "w", stdout);
#endif

	int t = 1;
	//cin >> t;
	while (t--) solve();

	return 0;
}


Measured memory_bytes: 14748
/* Preprocess */
#include <bits/stdc++.h>

/* Field */
using namespace std;

/* Function */
int main (void) 
{

  string N; // input
  string ans;

  cin >> N;

  if( N.at(0) == N.at(1) && N.at(1) == N.at(2) )
  {
    ans = "Yes";
  }
  else if( N.at(1) == N.at(2) && N.at(2) == N.at(3) )
  {
    ans = "Yes";
  }
  else
  {
    ans = "No";
  }

  cout << ans << endl;


  return 0;

}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#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 FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 1000000000
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N,M;
  cin >> N >> M;
  vector<int> sum(N,0);
  for(int i=0;i < M;i++){
    int a,b;
    cin >> a >> b;
    sum[a-1]++;
    sum[b-1]++;
  }
  REP(i,N) cout << sum[i] << endl;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var nextReader func() string

func newScanner() func() string {
	sc := bufio.NewScanner(os.Stdin)
	sc.Buffer(make([]byte, 1024), int(1e11))
	sc.Split(bufio.ScanWords)
	return func() string {
		sc.Scan()
		return sc.Text()
	}
}

func nextString() string { return nextReader() }

func nextInt() int { n, _ := strconv.Atoi(nextReader()); return n }

func main() {
	nextReader = newScanner()
	A, B, C := nextInt(), nextInt(), nextInt()
	if A == B && B == C {
		fmt.Println("No")
		return
	}
	if A == B || A == C || B == C {
		fmt.Println("Yes")
		return
	}
	fmt.Println("No")
}


Measured memory_bytes: 640
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

/*
	?????°???????????¨
	???????????° 2n (m<=n=2^e)
	?????¨??? ??????????????????
		?????????
		?????¨????????????
		??¨??????????????????
*/
struct Monoid {
	using T = int;
	T operator()(const T &a, const T& b) { return min(a, b); }
	static const T I = INT_MAX;
};
struct SegmentTree {
	using T = Monoid::T;
	Monoid op;
	int n;
	vector<T> d;
	SegmentTree(int m) {
		for (n = 1; n < m; n *= 2);
		d.assign(2 * n - 1, op.I);
	}
	void update(int k, T x) {
		k += n - 1;
		d[k] = x;
		while (k > 0) {
			k = (k - 1) / 2;
			d[k] = op(d[2 * k + 1], d[2 * k + 2]);
		}
	}
	T query(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l)return op.I;
		if (a <= l&&r <= b)return d[k];
		int xl = query(a, b, 2 * k + 1, l, (l + r) / 2);
		int xr = query(a, b, 2 * k + 2, (l + r) / 2, r);
		return min(xl, xr);
	}
	T query(int a, int b) {
		return query(a, b, 0, 0, n);
	}
};

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, q; cin >> n >> q;
	SegmentTree st(n);
	rep(i, 0, q) {
		int com, x, y; cin >> com >> x >> y;
		dump(com, x, y);
		if (com == 0) {
			st.update(x, y);
		}
		else {
			cout << st.query(x, y + 1) << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3888
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array, std.math;


void main() {
    int n, m, x;
    scan(n, m, x);
    auto a = readln.split.to!(int[]);
    int l, r;
    foreach (ai ; a) {
        if (ai < x) l++;
        else r++;
    }
    writeln(min(l, r));
}


void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

using namespace std;

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

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

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

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

	int maxA = *max_element(all(a));

	int ret = 0;
	sort(all(b));
	reverse(all(b));

	rep(i, N) {
		if (b[i] < maxA) break;
		H -= b[i];
		ret++;
		if (H <= 0) break;
	}

	if (H > 0) {
		ret += (H + maxA - 1) / maxA;
	}

	cout << ret << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

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

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

// Self settings
// clang-format off
#define MAX_N 100000
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SLN(i,N) (i == N-1 ? "\n" : " ")
ll fact(ll n) { ll res = 1; for(ll i=2;i<=n;++i) res = res * i; return res;}
ll nCr(ll n, ll r) {return (fact(n)/fact(n-r)*fact(r)) ;}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const ll MOD = 1e9+7;
const ll INF = 1LL << 60;
const int inf = 1 << 31;
// clang-format on

int N, Y;
int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> N >> Y;

  for (int i = 0; i <= N; i++) {
    for (int j = 0; j <= (N - i); j++) {
      int k = N - j - i;
      if (i * 10000 + j * 5000 + k * 1000 == Y) {
        printf("%i %i %i\n", i, j, k);
        return 0;
      }
    }
  }
  printf("-1 -1 -1\n");

  return 0;
}


Measured memory_bytes: 888