akhauriyash/Code-Regression huggingface dataset:
import math

n, h = map(int, input().split())
b = [0] * n
maxa = 0
for i in range(n):
    x, y = map(int, input().split())
    maxa = max(x, maxa)
    b[i] = y
b.sort(reverse = True)
ans = 0
for i in range(n):
    if b[i] < maxa:
        break
    h -= b[i]
    ans += 1
    if h <= 0:
        break
if not h <= 0:
    ans += math.ceil(h / maxa)
print(ans)

Measured memory_bytes: 13284
#include <iostream>

using namespace std;

void solve()
{
	int n;
	while(cin >> n, n)
	{
		int z = n * n * n;
		int x = n - 1;
		int y = 1;
		int min = z;
		while(x >= y)
		{
			int result = z - x * x * x - y * y * y;
			while(result >= 0)
			{
				if(result < min)
				{
					min = result;
				}
				++y;
				result = z - x * x * x - y * y * y;
			}
			--x;
		}
		cout << min << endl;
	}
}

int main()
{
	solve();
	return(0);
}

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

using namespace std;
using ll = long long;
using pint = pair<int, int>;

int main() {
	int N;
	cin >> N;
	vector<pint> xy(N);
	vector<int> p(N);
	for (int i = 0; i < N; ++i) {
		int x, y;
		cin >> x >> y;
		xy[i] = make_pair(x, y);
		p[i] = i;
	}

	int cnt = 0;
	double sum = 0.0;
	do {
		for (int i = 0; i < N-1; ++i) {
			int x = (xy[p[i]].first - xy[p[i + 1]].first);
			x = x * x;
			int y = (xy[p[i]].second - xy[p[i + 1]].second);
			y = y * y;

			sum += sqrt(x + y);
		}
		cnt++;
	} while (next_permutation(p.begin(), p.end()));

	double ans = sum / cnt;
	cout << fixed << setprecision(14) << ans << endl;

	return 0;
}


Measured memory_bytes: 3816
import fractions
A,B = map(int,input().split())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n = fractions.gcd(A,B)
print(len(set(prime_factorize(n)))+1)

Measured memory_bytes: 5048
import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static BufferedReader in;
    static PrintWriter out;
    static StringTokenizer tok;

    void solve() throws IOException {
        int n = ni();
        int[] a = nia(1 << n);

        for (int i = n - 1; i >= 0; i--) {
            int[] next = new int[1 << i];
            for (int j = 0; j < 1 << i; j++) {
                next[j] = a[j * 2] == a[j * 2 + 1] ? a[j * 2] : Math.abs(a[j * 2] - a[j * 2 + 1]);
            }
            a = next;
        }

        out.println(a[0]);
    }

    String ns() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine(), " ");
        }
        return tok.nextToken();
    }

    int ni() throws IOException {
        return Integer.parseInt(ns());
    }

    long nl() throws IOException {
        return Long.parseLong(ns());
    }

    double nd() throws IOException {
        return Double.parseDouble(ns());
    }

    String[] nsa(int n) throws IOException {
        String[] res = new String[n];
        for (int i = 0; i < n; i++) {
            res[i] = ns();
        }
        return res;
    }

    int[] nia(int n) throws IOException {
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = ni();
        }
        return res;
    }

    long[] nla(int n) throws IOException {
        long[] res = new long[n];
        for (int i = 0; i < n; i++) {
            res[i] = nl();
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        tok = new StringTokenizer("");
        Main main = new Main();
        main.solve();
        out.close();
    }
}

Measured memory_bytes: 29780
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define ff first
#define ss second
#define cy cout<<"Yes"<<endl;
#define cn cout<<"No"<<endl;
#define urs(r...)          typename decay<decltype(r)>::type
#define fi(i,n)                for(urs(n) i=0;i<n;i++)
#define rep(i,n)               for(urs(n) i=1;i<=n;i++)
#define pb push_back
#define gap ' '
#define endl '\n'
#define mex 300000
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>*/
main()
{
	int i,j,k,n,q;
	int cnt=0;
	bool flag=0,ok=0,f=0;
	string x;
	cin>>x;
	for(i=0;i<x.size();i++)
	{
		if(x[i]=='7') cnt++;
	}
	if(!cnt) cn
		else cy
}


Measured memory_bytes: 3620
#include<iostream>
#include<map>
#include<vector>

using namespace std;

typedef long long ll;

struct cum_sum_lm {
	vector<int> sum;
	int N;
	cum_sum_lm() = default;
	cum_sum_lm(int _N) {
		N = _N;
		sum.resize(N + 1);
	}

	void setup(vector<int>& _ar) {
		sum.resize(_ar.size() + 1);
		for (int i = 0; i < N; i++) {
			sum[i + 1] = sum[i] + _ar[i];
		}
	}
	ll getval(int l, int r) {
		//[l, r)
		ll ret = sum[r] - sum[l];
		return ret;
	}
};

int N;
vector<int> A(300000 + 10);
vector<int> B(300000 + 10);
cum_sum_lm sum;

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

	X = N;
	ll s = X;
	for (int i = 0; i < A.size(); i++) {
		B[A[i]]++;
	}
	sum.setup(B);
	
	cout << X << endl;
	ll cnt = 0;
	for (int k = 2; k <= N; k++) {
		while (X > 0) {
			//X*K<=取れるもの ならば今のXでOK
			if (X * k <= s + cnt * X) {
				break;
			}
			else {
				//sをX-1としたときに減る分を高速計算しておく
				s -= B[X] * X;
				cnt += B[X];
				X--;
			}
		}
		cout << X << endl;
	}
	return 0;
}


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

int main() {
  int N, i, j;
  bool ans;
  string S;
  cin >> N >> S;
  
  ans = false;
  
  if(N % 2 == 0){
 	 //先頭の文字と同じ文字の番号を取得
 	 i = N / 2;
  
   	//文字列検索
    ans = true;
  	for(j = 0;i < N;j++){
    	  if(S.at(j) != S.at(i)){
       	 ans = false;
     	 }
    
    	i++;
 	 }
  }
  
  //回答
  if(ans){
  	cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define req(i,n) for(long long i=n-1; i>=0; i--)
#define range(i,a,b) for(long long i=a; i<b; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define onBoard(y,x) (y>=0 && y<h && x>=0 && x<w)
#define vint vector<int>
#define pri_que priority_queue
#define vvint vector<vector<int>>
#define vstr vector<string>
#define vp vector<pair<int,int>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<"Yes"<<endl
#define coutn cout<<"No"<<endl
#define coutY cout<<"YES"<<endl
#define coutN cout<<"NO"<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
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;}
const long long dx[8]={1,0,-1,0,1,-1,-1,1};
const long long dy[8]={0,1,0,-1,1,1,-1,-1};
const long long INF = 1e12;
const long long MOD = 1e9+7;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(15);

    int n; cin >> n;
    vint a(n);
    rep(i,n) cin >> a[i];

    int res=0;
    rep(i,n){
        if(a[i]==i+1){
            if(i!=n-1) swap(a[i],a[i+1]);
            else swap(a[i],a[i-1]);
            res++;
        }
    }
    cout<<res<<endl;
}


Measured memory_bytes: 3976
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int num = sc.nextInt();
    int a = sc.nextInt();
    int b = sc.nextInt();
    int sum = 0;
    
    for(int i =1; i <= num; i++){
      int wa = i%10 + i/10%10 + i/100%10 + i/1000%10 + i/10000%10;
      if(wa >= a && wa <= b){
		sum += i;
      }
    }  
    System.out.println(sum);
  }
}

Measured memory_bytes: 21972
"use strict";

    
const make6digit = num => {
    num = String(num);
    let digit = num.split("").length;
    
    if(digit < 6) {
        for(let i=0; i<6-digit; i++) {
            num = "0" + num;
        }
    }
    
    return num;
}

const main = arg => {
    arg = arg.trim().split("\n");
    const N = parseInt(arg[0].split(" ")[0]);
    const M = parseInt(arg[0].split(" ")[1]);
    
    const cities = arg.slice(1, M + 1);
    let data = [];
    
    for(let i in cities) {
        let tempPrefecture = parseInt(cities[i].split(" ")[0]);
        let tempBirth      = parseInt(cities[i].split(" ")[1]);
        
        data.push({
            prefecture: tempPrefecture,
            birth:      tempBirth,
            index:      i
        })
    }
    
    data.sort((a,b) => {
        if(a.prefecture < b.prefecture) {
            return -1;
        }
        
        if(a.prefecture > b.prefecture) {
            return 1;
        }
        
        if(a.birth < b.birth) {
            return -1;
        }
        
        if(a.birth > b.birth) {
            return 1;
        }
    });
    
    let num = 1;
    
    for(let i in data) {
        if(data[i-1]) {
            if(data[i].prefecture !== data[i-1].prefecture) {
                num = 1;
            }
        }
        
        let firstHalf = make6digit(data[i].prefecture);
        let lastHalf  = make6digit(num);
        
        const id = firstHalf + lastHalf;
        
        data[i].id = id;
        
        num++;
    }
    
    data.sort((a,b)=>a.index - b.index);
    
    for(let i in data) {
        console.log(data[i].id);   
    }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));


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

#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)x.size()
#define int ll

pair<int, int> combine(int l, int r, int l2, int r2) {
	return {max(l, l2), min(r, r2)};
}

int get(int l, int r) {
	return max(0ll, r - l + 1);
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	vector<pair<int, int>> arr(n);
	for (auto &it : arr) {
		cin >> it.F >> it.S;
	}
	sort(all(arr));
	vector<pair<int, int>> pref(n);
	pref[0] = arr[0];
	for (int i = 1; i < n; i++) {
		pref[i] = combine(pref[i - 1].F, pref[i - 1].S, arr[i].F, arr[i].S);
	}
	int R = arr.back().S;
	int ans = 0;
	for (int i = n - 2; i >= 0; i--) {
		R = min(R, arr[i + 1].S);
		int L = arr.back().F, L2 = arr[i].F, R2 = arr[i].S;
		if (i == 0) {
			ans = max(ans, get(L, R) + get(L2, R2));
		}
		else {
			auto it = combine(L, R, pref[i - 1].F, pref[i - 1].S), 
			it2 = combine(L2, R2, pref[i - 1].F, pref[i - 1].S);
			ans = max(ans, get(L, R) + get(it2.F, it2.S));
			ans = max(ans, get(L2, R2) + get(it.F, it.S));
		}
	}
	cout << ans << '\n';
}

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

int main(){
  int N;
  string S;
  cin >> N >> S;
  int ssize = S.size();
  for(int i = 0; i < ssize; i++){
    if(S.at(i) + N <= 'Z') cout << (char)(S.at(i) + N);
    else cout << (char)(S.at(i) + N - 26);
  }
  cout << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int a[]=new int[n];
    for (int i=0;i<n;i++) {
      a[i]=sc.nextInt();
    }
    int ans=0;
    Arrays.sort(a);
    for (int i=0;i<n-1;i++) {
        if(a[i]==a[i+1]) ans++;
    }

    if(ans==0){
      System.out.println("YES");
    }else{
      System.out.println("NO");
    }
  }
}


Measured memory_bytes: 85880
/// a.cpp
# include <stdio.h>
# include <bits/stdc++.h>
using namespace std;
const pair < int , int > DD[] = {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define IOS ios_base :: sync_with_stdio(0);cin.tie(0)
# define p(v) cerr << #v << " = " << v << '\n'
# define p2(v) cerr << #v << " = " << (complex < decltype(v.x) > (v.x,v.y)) << '\n'
# define vi vector < int >
# define vl vector < ll >
# define pll pair < ll , ll >
# define pii pair < int , int >
# define mp make_pair
# define db long double
# define fail puts("-1")
# define yes puts("YES")
# define no puts("NO")
# define PP puts("Possible")
# define II puts("Impossible")
# define vii vector < pii >
# define vll vector < pll >
# define pb push_back
# define pdd pair < db , db >
# define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int main(void)
{
    #ifdef CF
    freopen("input","r",stdin);
    #endif // CF
    srand(time(0));
    fo << fixed << setprecision(7);
    cerr << fixed << setprecision(7);
    int n,k;
    fi>>n>>k;
    int a = 0,b = 0;
    while (n --)
    {
        int v;
        fi>>v;
        b += v & 1;
        a += !(v & 1);
    }
    ll cnt = 0;
    if (b)
        cnt += (1ll << a) * (1ll << (b - 1));
    if (k)
        fo << cnt << '\n';
    else
        fo << (1ll << (a + b)) - cnt << '\n';
    cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    int N;
    cin >> N;
    map<string, int> mp;
    for (int i = 0; i < N; i++) {
        string S;
        cin >> S;
        mp[S]++;
    }
    for (string s : {"AC", "WA", "TLE", "RE"}) {
        if (mp.count(s) == 0)
            cout << s << " x " << 0 << '\n';
        else cout << s << " x " << mp[s] << '\n';
    }
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define BIT(n) (1LL << (n))
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPB(i, n) for (int i = 0; i < BIT(n); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); 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 FORA(i, n) for (auto &&i : n)
#define FORS(i, m, n) for (int i = m; i <= n; i++)
#define DEBUG(x) cerr << #x << ": " << x << "\n"
#define PRINTALL(V)                                                            \
  for (auto v : (V)) {                                                         \
    cout << v << " ";                                                          \
  }                                                                            \
  cout << "\n";
#define ALL(v) v.begin(), v.end()
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define epb emplace_back
#define int long long
using namespace std;
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 (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template < class T > using vec = std::vector< T >;
template < class T > void print(const T &x) { cout << x << "\n"; }
const int MOD = 1000000007, INF = 1061109567;
const double EPS = 1e-10, PI = acos(-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
signed main() {
  cin.tie(0), ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int A, B;
  cin >> A >> B;
  print(max({A + B, A - B, A * B}));
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define INF (1<<26)
#define MAX_N 305
#define MAX_E 1005
int N,E,T;
int W[MAX_N];
int dp[MAX_N];
 
vector<int> S[MAX_E];
int G[MAX_E];
 
void init(){
  for(int i=0;i<MAX_E;i++)S[i].clear();
}
 
int solve(){
  for(int i=0;i<N;i++){
    if(W[i]==1)dp[i]=1;
    else dp[i]=INF;
  }
  vector<int> vec;
 
  bool update=true;
  while(update){
    update=false;
    for(int i=0;i<E;i++){
 
      vec.clear();
      for(int j=0;j<(int)S[i].size();j++){
    int x=S[i][j];
    vec.push_back(dp[x]);
      }
      sort(vec.begin(),vec.end());
      reverse(vec.begin(),vec.end());
 
      int cost=vec[0];
      for(int j=1;j<(int)vec.size();j++){
    cost=max(cost,vec[j]+j);
      }
 
      if(dp[G[i]]>cost){
    dp[G[i]]=cost;
    update=true;
      }
       
    }//i
  }//while
 
  if(dp[T]==INF)return -1;
  else return dp[T];
}
 
int main(){
  while(cin>>N>>E>>T){
    T--;
    init();
    for(int i=0;i<N;i++)cin>>W[i];
    for(int i=0;i<E;i++){
      int c;
      cin>>G[i]>>c;
      G[i]--;
      S[i].resize(c);
      for(int j=0;j<c;j++){
    cin>>S[i][j];
    S[i][j]--;
      }
    }
    cout<<solve()<<endl;
  }
}

Measured memory_bytes: 1280
#include <bits/stdc++.h> 
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)
 
using ll  = long long;
using ull = unsigned long long;
using Pii = std::pair<int, int>;
 
int main(int argc, char *argv[])
{
    std::string n;
    std::cin >> n;


    for (int i = 0; i < 3; i++) {
        if (n[i] == '1') {
            n[i] = '9';
        } else {
            n[i] = '1';
        }
    }

    std::cout << n << std::endl;
    return 0;
}


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

using namespace std;

int N;

void solve() {
    int ans = 0;
    for(int i = 1; i <= N; ++i) {
        ans += i;
    }
    printf("%d\n", ans);
}

signed main() {
        cin >> N;
        solve();
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define VAL 100000
#define ll long long
#define INF 10000000000000000LL
#define pll pair<long long , long long>
const int MAX=1e4+10;
const int MOD=1e9+7;
const int TOT_PRIMES=19;
const int MAX_A=70;
using namespace std;
int main() 
{ 
	//ios_base::sync_with_stdio(false);
  //  cin.tie(NULL);	
//	#ifndef ONLINE_JUDGE
//	freopen("inp.txt" ,"r", stdin );
//	freopen("out.txt", "w", stdout);
//	#endif
	int n;
	cin>>n;
	int dp[n+1][4];
	int act[n+1][4];
	for(int i=1;i<=n;i++)
		cin>>act[i][1]>>act[i][2]>>act[i][3];
	memset(dp , 0 , sizeof(dp));
	dp[1][1]=act[1][1];
	dp[1][2]=act[1][2];
	dp[1][3]=act[1][3];
	for(int i=2;i<=n;i++){
		for(int j=1;j<=3;j++){
			for(int k=1;k<=3;k++)
				if(j!=k)
					dp[i][j]=max(dp[i][j] , dp[i-1][k]+act[i][j]);
		}
	}
	cout<<max(dp[n][1], max(dp[n][2], dp[n][3]));
}

Measured memory_bytes: 3328
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

const uint64_t MOD = 1'000'000'007L;

uint64_t dpow(uint64_t x, uint64_t y)
{
    if (y == 0) {
        return 1;
    }
    if (y % 2 == 0) {
        return dpow(x * x % MOD, y / 2);
    } else {
        return x * dpow(x, y - 1) % MOD;
    }
}

uint64_t inv(uint64_t x)
{
    return dpow(x, MOD - 2);
}

uint64_t comb(uint64_t n, uint64_t k)
{
    uint64_t a = 1, b = 1;
    for (uint64_t i = 0; i < k; i++) {
        a *= (n - i);
        a %= MOD;
        b *= i + 1;
        b %= MOD;
    }
    return a * inv(b) % MOD;
}

int main()
{
    int x, y;
    cin >> x >> y;

    int z = 2 * x - y, w = -x + 2 * y;
    if (z % 3 != 0 || w % 3 != 0) {
        cout << 0 << endl;
        return 0;
    }
    if (z < 0 || w < 0) {
        cout << 0 << endl;
        return 0;
    }
    z /= 3;
    w /= 3;

    cout << comb(z + w, z) << endl;
    return 0;
}

Measured memory_bytes: 384
//HEADER FILES//
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <iomanip>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <set>

using namespace std; 

typedef unsigned long long int fuck;
// Function to find the number of divisors 
// of all numbers in the range [1, n] 
void findDivisors(fuck n) 
{ 

	// Array to store the count 
	// of divisors 
	long div[n + 1]; 
	memset(div, 0, sizeof div); 

	// For every number from 1 to n 
	for (int i = 1; i <= n; i++) { 

		// Increase divisors count for 
		// every number divisible by i 
		for (int j = 1; j * i <= n; j++) 
			div[i * j]++; 
	} 
    fuck ans=0;
	// Print the divisors 
	for (int i = 1; i <= n; i++) 
		 ans+=div[i]*i;
         cout<<ans;
} 

// Driver code 
int main() 
{ fuck n;
cin>>n;
	findDivisors(n); 

	return 0; 
} 


Measured memory_bytes: 81264
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        int left = 0;
        int right = s.length-1;
        int ans = 0;
        while(left < right){
            if(s[left] == s[right]){
                left++;
                right--;
            }else if(s[left] == 'x'){
                left++;
                ans++;
            }else if(s[right] == 'x'){
                right--;
                ans++;
            }else{
                System.out.println(-1);
                return;
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 26196
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        String s = sc.next();
        String t = sc.next();

        boolean flag = true;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) != t.charAt(i)){
                flag = false;
            }
        }

        System.out.println(flag?"Yes":"No");
    }
}

Measured memory_bytes: 35600
#include<bits/stdc++.h>
using namespace std;
int main()
{
     ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  long long n,i,j,k;
  cin>>n>>k;
  long long a[n];
  for(i=0;i<n;i++)cin>>a[i];
  long long dp[n];
  dp[0]=0;
  for(i=1;i<n;i++)
  {
    dp[i]=INT_MAX;
    for(j=i-1;j>=i-k && j>=0;j--)
    {
      dp[i]=min(dp[i],dp[j]+abs(a[i]-a[j]));
    }
  }
  cout<<dp[n-1];
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
#define all(a) (a).begin(),(a).end()
#define overload4(_1, _2, _3, _4, name, ...) name
#define rep1(n) for(ll i = 0;i < (n);i++)
#define rep2(i,n) for(ll i = 0;i < (n);i++)
#define rep3(i,a,b) for(ll i = (a);i < (b);i++)
#define rep4(i,a,b,c) for(ll i = (a);i < (b);i += (c))
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for(ll i = (n)-1;i >= 0;i--)
#define rrep2(i,n) for(ll i = (n)-1;i >= 0;i--)
#define rrep3(i,a,b) for(ll i = (a)-1;i >= (b);i--)
#define rrep4(i,a,b,c) for(ll i = (a)-1;i >= (b);i -= (c))
#define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define SHOW(x) cout << #x << ": " << x << endl;
template<class T> ll sumArr(const T& a){ return accumulate(all(a), 0LL);}
template<class T> auto minArr(const T& a){ return *min_element(all(a));}
template<class T> auto maxArr(const T& a){ return *max_element(all(a));}
template<class T> void DEBUG_PRINT(T tmp){cout<<tmp<<endl;}
template<class T1,class... T2> void DEBUG_PRINT(T1 tmp,T2... tmp2){cout<<tmp<<" ";DEBUG_PRINT(tmp2...);}
ll gcd(ll a, ll b){ while(b){ ll c = b; b = a % b; a = c; } return a; }
const ll INF=1e18,MOD = 1e9+7;
const int iINF = 1e9;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll k,ans = 0;
    cin>>k;
    k++;
    rep(a,1,k)rep(b,1,k)rep(c,1,k){
        ans += gcd(a,gcd(b,c));
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3664
#include<bits/stdc++.h>
 
#define INF 1000010000
#define nl '\n'
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pdd pair<double,double>
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define sz(c) (c).size()
#define rep(i,n) for( int i = 0; i < n; ++i )
#define repi(i,n) for( int i = 1 ; i <= n; ++i )
#define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
#define repf(j,i,n) for( int j = i ; j < n ; ++j )
#define die(s) {std::cout << s << nl;}
#define dier(s) {std::cout << s; return 0;}
#define vi vector<int>
typedef long long ll;
#define MAXN 202020
using namespace std;
 
 
 
int n;
vector<vi> t(2 , vi(2 * MAXN , INF));
 
 
void build(int par){
    for(int i = n - 1 ; i > 0 ; --i){
        t[par][i] = min(t[par][2 * i] , t[par][2 * i + 1]);
    }
}
 
void modify(int par , int p , int val){
    for(t[par][p += n] = val ; p > 1 ; p /= 2){
        t[par][p / 2] = min(t[par][p] , t[par][p ^ 1]);
    }
}
 
int query(int par , int l , int r){//[l , r)
    int res = INF;
    for(l += n , r += n ; l < r ; l /= 2 , r /= 2){
        if(l % 2){
            res = min(res, t[par][l]);
            ++l;
        }
        if(r % 2){
            --r;
            res = min(res , t[par][r]);
        }
    }
    return res;
}
 
int last = 0;
map<int , pii> code;
map<pii , int> rcode;
vi pos;
 
vi g[MAXN / 2];
 
void solve(vi & p , int l , int r , int prev = -1){
	if(r - l < 1)return;
	if(r >= sz(p) || l < 0)return;
	if(r - l == 1){
		code[last] = {p[l] , p[r]};
		rcode[{p[l] , p[r]}] = last;
		
		if(prev != -1){
			g[prev].pb(last);
		}
		prev = last;
		++last;
	}else{
		pii o = {0 , 0};
		
		int par = l % 2;
		o.fi = query(par , l , r + 1);
		
		int pos1 = pos[o.fi];
		o.se = query((pos1 + 1) % 2 , pos1 + 1 , r + 1);
		
		code[last] = o;
		rcode[o] = last;
		
		if(prev != -1){
			g[prev].pb(last);
		}
		prev = last;
		++last;	
 
		int pos2 = pos[o.se];
 
		solve(p , pos1 + 1 , pos2 - 1 , prev);
		solve(p , l , pos1 - 1 , prev);
		solve(p , pos2 + 1 , r  , prev);
		
	}
}
 
vi restore(){
	vi res;
	priority_queue<pii , vector<pii> , greater<pii>> q; 
	q.push(code[0]);
	
	while(!q.empty()){
		pii u = q.top();
		q.pop();
		
		res.pb(u.fi);
		res.pb(u.se);
		
		for(int c : g[rcode[u]]){
			q.push(code[c]);
		}
	}
	return res;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.precision(0); 
 
 
	cin >> n;
	
	pos.resize(n + 1);
	
	vi p(n);
	rep(i , n){
		cin >> p[i];
		pos[p[i]] = i;
		
		int par = i % 2;
		
		t[par][n + i] = p[i];
		t[par ^ 1][n + i] = INF;
	}
 
	
	build(0);
	build(1);
	
	solve(p , 0 , n - 1);
	
	for(int e : restore()){
		cout << e << " ";
	}
	
	return 0;
}

Measured memory_bytes: 38612
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <set>
#include <math.h>
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
typedef long long ll;
using namespace std;

const int64_t INF=1000000000000000000;

int main() {
    int n;
    cin >> n;
    int64_t sum=1;
    bool flag = false;
    vector<int64_t> a(n);
    rep(i,0,n) {
        ll a;
        cin >> a;
        if(a==0) {
            cout << 0 << endl;
            return 0;
        }
        if(flag||INF/sum<a) {
            flag=true;
        }
        sum*=a;
    }
    if (flag) cout << -1 << endl;
    else cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3564
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> A(N);
	int res = 1;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		res *= 3;
	}
	int k = 1;
	for (int i = 0; i < N; i++) {
		if (A[i] % 2 == 0) {
			k *= 2;
		}
	}
	cout << res - k << endl;
}

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


void solve(long long N){
  cout << std::fixed << std::setprecision(10) << 2 * N * PI << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    solve(N);
    return 0;
}

Measured memory_bytes: 3844
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define NIL -1
typedef long long ll;
const ll INF = 1LL<<60;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const ll MOD = 1000000007;


int main() {
    int N;
    cin >> N;
    int ave = 0;
    int X[N];
    rep(i,N) {
        cin >> X[i];
        ave += X[i];
    }
    // cout << ave << endl;
    // cout << 1.0 * ave / N << endl; 
    ave = round(1.0 * ave / N);
    // cout << ave << endl;

    int res = 0;
    rep(i, N) {
        res += pow((X[i] - ave ),2);
    }

    cout << res << endl;
    return 0;

}

Measured memory_bytes: 256
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    Long[] a=new Long[2];
    a[0]=sc.nextLong();
    a[1]=sc.nextLong();
    Long[] c=new Long[2];
    c[0]=sc.nextLong();
    c[1]=sc.nextLong();
    Long max=Long.MIN_VALUE;
    for(int i=0;i<2;i++){
      for(int j=0;j<2;j++){
        if(max<a[i]*c[j])max=a[i]*c[j];
      }
    }
    System.out.println(max);
  }
}

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

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

    int n;
    string s;
    cin >> n;
    cin >> s;
    
    int countR=0, countB=0;
    
    rep(i, n){
        if(s[i]=='R') countR++;
        else countB++;
    }
    
    string ans="No";
    if(countR>countB){
        ans = "Yes";
    }
    
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,m,n) for(int i=m;i<n;i++)
ll mod=1e9+7;

int main(){
  int a,b,k;
  cin>>a>>b>>k;
  int d=a+k-1;
  int e=b-k+1;
  if(d>=e){
    rep(i,a,b+1) cout<<i<<endl;
  }
  else{
    rep(i,a,d+1) cout<<i<<endl;
    rep(i,e,b+1) cout<<i<<endl;
  }
}

Measured memory_bytes: 256
S=input()
N=len(S)
C=13
MOD=10**9+7

DP=[[0]*C for _ in range(N+1)]#DP[i][j]はi番目まで見て、あまりがjノヤツの個数
DP[0][0]=1

for i,s in enumerate(S,1):
    if s=="?":
        for k in range(C):
            for j in range(10):
                new_mod=k*10+j
                DP[i][new_mod%13]+=DP[i-1][k]
    else:
        for k in range(C):
            new_mod=k*10+int(s)
            DP[i][new_mod%13]+=DP[i-1][k]
    for k in range(C):
        DP[i][k]%=MOD

print(DP[-1][5])


Measured memory_bytes: 61916
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import deque
from itertools import product
def resolve():
    m, n = map(int, input().split())
    si, sj = map(lambda x : int(x) - 1, input().split())
    ti, tj = map(lambda x : int(x) - 1, input().split())
    grid = [input() for _ in range(m)]

    queue = deque([(si, sj)])
    dist = [[INF] * n for _ in range(m)]
    dist[si][sj] = 0
    while queue:
        i, j = queue.popleft()
        for di, dj in product(range(-2, 3), repeat = 2):
            if di == dj == 0:
                continue
            ni, nj = i + di, j + dj
            if not (0 <= ni < m and 0 <= nj < n):
                continue
            if grid[ni][nj] == '#':
                continue
            dd = int(abs(di) + abs(dj) > 1)
            nd = dist[i][j] + dd
            if nd < dist[ni][nj]:
                dist[ni][nj] = nd
                if dd == 0:
                    queue.appendleft((ni, nj))
                else:
                    queue.append((ni, nj))


    ans = dist[ti][tj]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Measured memory_bytes: 94620
lvl = [1.1, 0.6, 0.2, 0.0] 
rst = [[0]*4 for _ in range(2)]
eyes = []
while True:
    try:
        l,r = map(float,input().strip().split())
        eyes.append([l,r])
    except EOFError:
        break

for e in eyes:
    for lr in range(2):
        for l in range(len(lvl)):
            if e[lr]>=lvl[l]: 
                rst[lr][l] += 1
                break
        else:
            raise ValueError('Do not come here')

for lv in range(len(lvl)):
    print("%d %d" % (rst[0][lv],rst[1][lv]))

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

#define int long long
#define f first

#define s second
using namespace std;

template<typename T> using vc = vector<T>;
using pii=pair<int, int>;

void xmax(int & a, int b){
    a=max(a, b);
}
void xmin(int& a, int b){
    a=min(a, b);
}

void print(vc <int> & a, string s){
    cerr << s << " : ";
    for (int i=0; i<a.size(); i++){
        cerr <<a[i] << " ";
    }
    cerr << endl;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL_RUN
    freopen("input.txt", "r", stdin);
    int ttt;
    cin >> ttt;
    while(ttt--){
    #endif // LOCAL_RUN

    vc <int> a = {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 n;
    cin >> n;
    n--;
    cout << a[n] << "\n";

    #ifdef LOCAL_RUN
    }
    #endif // LOCAL_RUN
}


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

// 約数の列挙O(√n)
vector<long long> divisor(long long n) {
	vector<long long> res;
	for (long long i = 1; i * i <= n; i++) {
  	if (n % i == 0) {
			res.push_back(i);
			if (i != n / i) res.push_back(n / i);
		}
	}
	return res;
}

long long extgcd(long long a, long long b, long long& x, long long& y) {
	long long d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	} else {
		x = 1; y = 0;
	}
	return d;
}

void solve(long long A, long long B, long long K){
	long long x, y;
	vector<long long> v;
	v = divisor(extgcd(A, B, x, y));
	sort(v.begin(), v.end());
	printf("%lld\n", v[v.size()-K]);
}

int main(){
	long long K;
	long long A;
	long long B;
	scanf("%lld",&A);
	scanf("%lld",&B);
	scanf("%lld",&K);
	solve(A, B, K);
	return 0;
}


Measured memory_bytes: 256
N = int(input())
p = list(map(int, input().split()))
n = [i+1 for i in range(N)]
c = 0
for i in range(N):
    if n[i] != p[i]:
        c += 1
if c == 0 or c == 2:
    print("YES")
else:
    print("NO")


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;

int a[100001];
int b[100001];
int x[100001];
int y[100001];
int c[100001];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int A, B, m;
    cin >> A >> B >> m;
    for (int i = 1; i <= A; ++i)
        cin >> a[i];
    for (int i = 1; i <= B; ++i)
        cin >> b[i];

    int sol = 1e9;
    for (int i = 0; i < m; ++i)
    {
        cin >> x[i] >> y[i] >> c[i];
        sol = min(sol, a[x[i]] + b[y[i]] - c[i]);
    }
    sort(a + 1, a + A + 1);
    sort(b + 1, b + B + 1);
    sol = min(sol, a[1] + b[1]);
    cout << sol;
}


Measured memory_bytes: 2176
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner sc=new Scanner(System.in);

		int K=sc.nextInt();
		int S=sc.nextInt();
		int ans=0;
		
		for(int i=0;i<=K;i++) {
			for(int j=0;j<=K;j++) {
				if(0<=S-i-j&&S-i-j<=K) {
					ans++;
				}
			}
		}

		System.out.println(ans);

		sc.close();
	}
}


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

using namespace std;

int main(void)
{
    stack<int> st;
    string s;

    while (cin >> s){
        if (isdigit(s[0])){
            st.push(stoi(s));
        }
        else {
            int x = st.top(); st.pop();
            int y = st.top(); st.pop();
            if (s[0] == '+'){
                st.push(x + y);
            }
            else if (s[0] == '-'){
                st.push(y - x);
            }
            else {
                st.push(x * y);
            }
        }
    }

    cout << st.top() << endl;

    return (0);
}



Measured memory_bytes: 3236
#include<bits/stdc++.h>
using namespace std;
int dp[100001];
int mk=0;
vector<int>adj[100001];
vector<int>bdj[100001];
bool visited[100001];
vector<int>topo;
void dfs(int start)
{
    visited[start]=true;
    for(auto x:adj[start])
    {
    	if(!visited[x])
    		dfs(x);
    }
   topo.emplace_back(start);
}
void toposort(int n)
{
	for(int i =1;i<=n;i++)
		if(!visited[i])
			dfs(i);
	reverse(topo.begin(),topo.end());	
}
int main(void)
{
	int n,m;
	cin>>n>>m;
    memset(dp,0,sizeof(dp));
    memset(visited,false,sizeof(visited));
	for(int i =0;i<m;i++)
	{
		int a,b;
		cin>>a>>b;
        adj[a].emplace_back(b);
	}
    toposort(n);
    mk =0;
    for(auto x:topo)
    {
        for(auto y :adj[x])
        {
        	if(dp[y]<dp[x]+1)
        		dp[y]=dp[x]+1;
        }
        if(mk<dp[x])
        	mk=dp[x];
    }

	cout<<mk<<endl;
}


Measured memory_bytes: 11260
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
using namespace std;
typedef long long ll;

int n, limit;

vector<int> g[2005];
bool removed[2005];
int visited[2005];
int dist[2005];
int counter;

int q[100000];
int bfs(int s) {
  ++counter;
  int qbg = 0;
  int qed = 0;
  q[qed++] = s;
  visited[s] = counter;
  int far = dist[s] = 0;
  while(qbg < qed) {
    int cur = q[qbg++];
    REP(i, g[cur].size()){
      int next = g[cur][i];
      if(!removed[next] && visited[next] != counter) {
        q[qed++] = next;
        visited[next] = counter;
        far = dist[next] = dist[cur] + 1;
      }
    }
  }
  REP(i, n) {
    if(visited[i] == counter && dist[i] > limit) {
      removed[i] = true;
    }
  }
  if(far > limit)
    far = limit;
  REP(i, n) {
    if(visited[i] == counter && dist[i] == far) {
      return i;
    }
  }
  return s;
}

int main(void) {
  scanf("%d%d", &n, &limit);
  REP(i, n-1) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a;
    --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  int res = n;
  REP(s, n) {
    REP(i, n)
      removed[i] = false;
    int t = bfs(s);
    bfs(t);
      
    int cur = 0;
    REP(i, n)
      if(removed[i])
        ++cur;
    res = min(res, cur);
  }
  cout << res << endl;
  
  return 0;
}


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

int main() {
  ll n, ans = 0; cin >> n;
  rep(i, 5) {
    ll a; cin >> a;
    ans = max(ans, ((n - 1)/ a) + 1);
  }
  cout << ans + 4 << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
        int N; cin>>N;
        vint T(N+1);
        int sumT=0;
        for(int i=1;i<=N;i++){
                cin>>T[i];
                sumT+=T[i];
        }
        int M; cin>>M;
        REP(i,M){
                int P,X; cin>>P>>X;
                cout<<sumT-T[P]+X<<endl;
        }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MEM 100006
#define sanic ios_base::sync_with_stdio(0)
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll MOD = 1e9+7;
ll n,m,sum;
ll c[MEM];
string s;
int main()
{
    sanic; cin.tie(0);
    cin >> n;
    for(int i=0; i<n; i++){
        ll q;
        cin >> q;
        c[q]++;
        sum += q;
    }
    cin >> m;
    while(m--){
        ll q1, q2;
        cin >> q1 >> q2;
        sum -= q1*c[q1];
        //cout << sum <<' ';
        sum += q2*c[q1];
        c[q2] += c[q1];
        //cout << sum << ' ';

        c[q1] = 0;
        cout << sum << '\n';
    }
}


Measured memory_bytes: 4376
def inv(a,m):
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

mod=998244353
n,m,k=map(int,input().split())
frac=[1 for i in range(n+1)]
frac_inv=[1 for i in range(n+1)]
beki=[m for i in range(n+1)]

for i in range(1,n+1):
    frac[i]=frac[i-1]*i%mod
    frac_inv[i]=inv(frac[i],mod)
    beki[i]=beki[i-1]*(m-1)%mod
ans=0
for i in range(n-k,n+1):
    ans+=beki[i-1]*frac_inv[n-i]*frac_inv[i-1]%mod
    ans%=mod
print(ans*frac[n-1]%mod)

Measured memory_bytes: 94016
using namespace std;
#include <bits/stdc++.h>
#define rep(i, s) for (int i = 0; i < s; ++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 all(v) (v.begin(), v.end())
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define VEC(a, n) vector<int>a(n)
#define PQ(a) priority_queue<int>a
#define PQmin(a) priority_queue< int, :vector<int>, greater<int> >a
#define PAIR pair<int, int>
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define EPS (1e-7)
#define INF (1e10)
#define PI (acos(-1))
const ll mod = 1000000007;
bool f(string s){
  bool ans=true;
  rep(i,s.size()/2){
    if(s[i]!=s[s.size()/2+i]){
      ans=false;
      break;
    }
  }
  return ans;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N,A;
  cin>>N>>A;
  if(A*2>=N)
    cout<<0<<endl;
  else
    cout<<N-A*2<<endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const long long MOD=1e9+7;
const long double Pi=acos(-1);
using  P=pair<ll,ll>;
ll gcd(ll a,ll b){//aとbの最大公約数を返す//計算量は0(log(max(a,b))
  if(a%b==0){return b;}
  else{return gcd(b,a%b);}
}
ll lcm(ll a,ll b){//aとbの最小公倍数を返す//計算量は0(log(max(a,b))
  return a*b/gcd(a,b);
}
ll pow(ll x,ll y){//x^yを返す//計算量は0(log(y))
  ll tmp=x,res=1;
  while(y){
    if(y%2){res=res*tmp%MOD;}
    y>>=1;
    tmp=tmp*tmp%MOD;
  }
  return res;
}
ll nature(ll a){//絶対値を返す
  if(a>=0){return(a);}
  else{return(-1*a);}
}
ll prime(ll a){//素数なら1を返す//計算量は0(sqrt(a))
  if(a==2){return 1;}
  else if(a%2==0 || a==1){return 0;}
  for(ll i=3;i*i<=a;i+=2){if(a%i==0){return 0;}}
  return 1;
}
int main(){
  ll N;
  cin>>N;
  vector<ll> A(N);
  for(int i=0;i<N;i++){
    cin>>A.at(i);
  }
  sort(A.begin(),A.end());
  reverse(A.begin(),A.end());
  ll ans=0;
  priority_queue<ll> que;
  for(int i=1;i<N;i++){
    if(i==1){
      ll a=min(A.at(0),A.at(1));
      que.push(a);
      que.push(a);
      ans+=A.at(0);
    }
    else{
      ll t=que.top();
      que.pop();
      que.push(A.at(i));
      que.push(A.at(i));
      ans+=t;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 6928
"""
A,B=map(int, input().split())

print(B if A >= 13 else 0 if A <= 5 else int(B/2))
"""
"""
r,D,x2000=map(int, input().split())
xNext=x2000*r-D
for i in range(10):
  print(xNext)
  xNext=xNext*r-D
"""
N,M=map(int, input().split())
L=[]
R=[]
for i in range(M):
  l,r=map(int, input().split())
  L.append(l)
  R.append(r)

D=[0]*(N+1)
for i in range(M):
  D[L[i]-1] += 1
  D[R[i]] -= 1
S=[0]*(N+1)
S[0] = D[0]
for i in range(1,N):
  S[i] = S[i-1] + D[i]
cnt=0
for i in range(N):
  if S[i] == M: cnt += 1
print(cnt)

Measured memory_bytes: 15928
#include <iostream> // プログラムの耳と口
#include <vector> // 超有能配列秘書
#include <algorithm> // みんな大好きソートと二分探索
#include <queue> // きゅーちゃん、だいすき
#include <string> // to_string
#include <functional> // 関数を変数に入れる子
#include <set> // 値の取得・挿入・削除を高速に
#include <map> // setの妹 これまた優秀
#include <random> // 乱択さん

#define DB cerr<<"D"<<endl
using namespace std; using ll=long long; using ld=long double; const int INF=1e9; const ll LINF=1e18; const double dINF = 1e18; const ld ldINF = 1e18; const double EPS = 1e-6;
template<typename T, typename U, typename O> void caut(T a, U b, O c){cout<<"("<<a<<","<<b<<","<<c<<") ";} template<typename T, typename U> void caut(T a, U b){cout<<"("<<a<<","<<b<<") ";} template<typename T> void caut(T a){cout<<"("<<a<<") ";};
using P=pair<ll,ll>;
const ll M = 1e9+7;
ll mod_pow(ll x, ll a) { ll an = 1; while(a > 0) { if (a&1) an = an * x % M; x = x * x % M; a >>= 1;} return an;}
ll adad(ll x) {return x*(x+1)/2;} // 1～xの総和
void add(ll& x, ll y) {x+=y; x%=M;}; void mul(ll& x, ll y) {x*=y; x%=M;}; template<typename T, typename U> void chmax(T& x, U y) {if (x<y) x=y;}; template<typename T, typename U> void chmin(T& x, U y) {if (x>y) x=y;}
bool vaild(int x, int y, int hh, int ww){return 0<=x&&x<hh&&0<=y&&y<ww;}

int main() {
  int l,r,d; cin>>l>>r>>d;
  cout<<-(l-1)/d+r/d<<endl;
}

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

using namespace std;

int main(void){
  int N;
  cin >> N;
  map<int, int> m;
  for(int i = 0; i < N; i++){
    int a;
    cin >> a;
    m[a]++;
    m[a - 1]++;
    m[a + 1]++;
  }
  int ans = 0;
  for(auto c : m) ans = max(ans, c.second);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4736
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define repi(i, n) for (int i = 0; i < (int)(n); i++)
#define repd(i, n) for (int i = (int)(n); i >= 0; i--)
#define repm(i, m) for (auto i = m.begin(); i != m.end(); i++)

int main()
{
    int N;
    cin >> N;
    int ans = 0;
    for (int i = 1; i <= N; i += 2)
    {
        int cnt = 0;
        for (int j = 1; j <= N; j+=2)
        {
            if (i % j == 0)
            {
                cnt++;
            }
        }
        if (cnt == 8)
        {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int d[1000000]={},p[1000000]={};
void calc(){
	for(int i=2;i<1000000;i++){
		if(d[i]==0){
			for(int j=2;j<1000000;j++){
				if(i*j>1000000) break;
					d[i*j]=1;
			}
		}
	}
	for(int i=2;i<1000000;i++){
		if(d[i]==0)
		p[i]=p[i-1]+1;
		else
		p[i]=p[i-1];
	}
}
int main(){
	calc();
	int n;
	while(cin>>n,n){
		if(cin.eof())break;
		cout<<p[n]<<endl;
	}
	return 0;
}

Measured memory_bytes: 8972
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<vi>;
using ll = long long;

int main() {
    int n; cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a.at(i);

    ll ans;
    ll p = pow(10, 18);
    rep(i, n) {
        if (a.at(i) == 0) {
            cout << 0 << endl;
            return 0;
        }
    }
    ll prod = 1;
    rep(i, n) {
        //ll prod = 1;
        if (a.at(i) <= p /prod) prod *= a.at(i);
        else {
            cout << -1 << endl;
            return 0;
        }
        //ans = prod;
    }

    cout << prod << endl;
    //cout << p << endl;
    return 0;
}

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

int main()
{
    ll N;

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

    ll min_ = 10000000000;
    ll sum_ = 0;
    for(int i = 0; i < 100; i++) {
        sum_ = 0;
        for (int j = 0; j < X.size(); j++) {
            sum_ += pow((X[j] - i + 1), 2);
        }
        if ( min_ > sum_ )
            min_ = sum_;
    }
    cout << min_ << endl;
    return 0;
}

Measured memory_bytes: 3636