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

using namespace std;
#define X first
#define Y second
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define debug(x) cerr << #x << " = " << (x) << endl;
template<typename T>
ostream& operator<<(ostream& o, vector<T>& v) {
    for (auto& x : v) o << x << ' ';
    return o;
}

const int MOD = (int)1e9 + 7;
void add(int &a, int b){
    a += b;
    if (a >= MOD) a -= MOD;
}
int exp(int a, int b){
    if (b == 0) return 1;
    if (b & 1) {
        return (ll)a * exp(a, b-1) % MOD;
    }
    int tmp = exp(a, b/2);
    return (ll)tmp * tmp % MOD;
}

const int MAXN = 1024;
int binom[MAXN][MAXN];
int fact[MAXN], ifact[MAXN];
int N, A, B, C, D;
ll memo[MAXN][MAXN];
ll dp(int n, int k){
    ll &res = memo[n][k];
    if (res != -1) return res;
    if (k > B) return res = (n == 0);
    res = dp(n, k + 1);
    ll den = 1;
    for (int i = C; i <= D; i++){
        int tk = i * k;
        if (tk > n) break;
        if (i == C){
            for (int iter = 0; iter < C-1; iter++)
                den = den * ifact[k] % MOD;
        }
        den = den * ifact[k] % MOD;
        ll cur = (ll)binom[n][tk] * fact[tk] % MOD * den % MOD;
        cur = cur * dp(n - tk, k + 1) % MOD * ifact[i] % MOD;
        res += cur;
    }
    res %= MOD;
    //cout << n << ' ' << k << " = " << res << endl;
    return res;
}

int main(){
    std::ios_base::sync_with_stdio(false); cin.tie(0);
    fact[0] = ifact[0] = 1;
    for (int i = 1; i < MAXN; i++){
        fact[i] = (ll)fact[i-1] * i % MOD;
        ifact[i] = exp(fact[i], MOD - 2);
    }

    for (int i = 0; i < MAXN; i++)
        binom[i][0] = binom[i][i] = 1;
    for (int i = 2; i < MAXN; i++){
        for (int j = 1; j < i; j++){
            binom[i][j] = (binom[i-1][j] + binom[i-1][j-1]) % MOD;
        }
    }
    cin >> N >> A >> B >> C >> D;
    memset(memo, -1, sizeof memo);
    int res = dp(N, A);
    cout << res << endl;
}


Measured memory_bytes: 12672
#include <bits/stdc++.h>
using namespace std;
const int INF = 1001001001;

int main(){
  int n;
  cin >> n;
  vector<vector<int>> v(n);
  for(int i=0; i<n-1; ++i){
    int a, b;
    cin >> a >> b;
    --a; --b;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  vector<int> fen(n,INF);
  queue<int> que;
  que.push(0);
  fen[0] = 0;
  while(!que.empty()){
    int x = que.front();
    que.pop();
    for(int a: v[x]){
      if(fen[a] != INF) continue;
      fen[a] = fen[x] +1;
      que.push(a);
    }
  }
  vector<int> snu(n,INF);
  que.push(n-1);
  snu[n-1] = 0;
  while(!que.empty()){
    int x = que.front();
    que.pop();
    for(int a: v[x]){
      if(snu[a] != INF) continue;
      snu[a] = snu[x] +1;
      que.push(a);
    }
  }
  int fenp = 0;
  for(int i=0; i<n; ++i){
    if(fen[i] <= snu[i]) ++fenp;
  }
  int snup = n-fenp;
  if(fenp > snup) cout << "Fennec" << endl;
  else cout << "Snuke" << endl;
}

Measured memory_bytes: 9576
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vvi = vector<vector<int>>;
using vp = vector<pii>;
using vs = vector<string>;
using qi = queue<int>;
using qp = queue<pii>;
using pqi = priority_queue<int>;
using pqim = priority_queue<pii, vector<pii>, greater<pii> >;
using ppp = pair<int, pair<int, int>>;
#define all(vec) vec.begin(), vec.end()
#define rall(vec) vec.rbegin(), vec.rend()
#define pb push_back
const ll mod = 998244353;
const ll inf = 1e18;

int x, n;
vi a;

void input() {
	cin >> x >> n;
	a = vi(n);
	for (int i = 0; i < n; ++i)
		cin >> a[i];
}

void solve() {

	if (!n) {
		cout << x;
		return;
	}

	int ex[110] = {};
	for (int i = 0; i < n; ++i) {
		ex[a[i]] = 1;
	}

	int l = x, r = x;
	while (ex[l]) l--;
	while (ex[r]) r++;

	if (x - l <= r - x) cout << l;
	else cout << r;



	return;
}

int main() {
	cin.tie(NULL); ios_base::sync_with_stdio(false);

	input();
	solve();
}

Measured memory_bytes: 3612
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int n,wt;
    cin>>n>>wt;
    vector<ll> w(n);
    vector<ll> v(n);
    for(int i=0;i<n;i++)
    {
        cin>>w[i]>>v[i];
    } 

    ll dp[wt+1][n+1];
    memset(dp,0,sizeof(dp));

    for(int i=1;i<=wt;i++)
    {
        for(int j=n-1;j>=0;j--)
        {
            dp[i][j]=dp[i][j+1];
            if(i>=w[j])
            {
                dp[i][j]=max(dp[i][j],dp[i-w[j]][j+1]+v[j]);
            }
        }
    }

    cout<<dp[wt][0]<<endl;
    return 0;
}
 

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

int main(){
    double W, H, x, y; cin >> W >> H >> x >> y;
    bool flag;
    if(x == W / 2 && y == H / 2){
        flag = true;
    }else{
        flag = false;
    }
    double S = H * W / 2;
    cout << S << " " << (flag ? "1" : "0") << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <array>

using namespace std;

#define forange(counter, end) forstep(counter, 0, end)
#define forstep(counter, begin, end) forstep_type(size_t, counter, begin, end)
#define forange_type(type, counter, end) forstep_type(type, counter, 0, end)
#define forstep_type(type, counter, begin, end) for (type counter = begin, forstep_type_end_##counter = end; counter < forstep_type_end_##counter; counter++)

const int D = 365;
const int C = 26;

array<int, C> contest;
array<array<int, C>, D> satisfaction;

int decr(const int c, const int last, const int now) {
	return contest[c] * (now - last);
}

int getScore(const array<short, C>& last, const int open, const int day) {

	int score = 0;

	forange_type(int, c, C)
	{
		if (c == open)
		{
			score += satisfaction[day][c];
		}
		else
		{
			score -= decr(c, last[c], day);
		}
	}

	return score;
}

int getScore(const array<char, D>& cont) {

	int score = 0;
	array<short, C> last;
	last.fill(-1);

	forange_type(short, d, D)
	{
		score += getScore(last, cont[d], d);
		last[cont[d]] = d;
	}

	return 1000000 + score;
}

struct Data {
	Data() {
		last.fill(-1);
		c.fill(0);
	}

	array<short, C> last;
	array<char, D> c;
	int score = 0;

	bool operator<(const Data& o) const {
		return score < o.score;
	}
};

array<char, D> think() {

	priority_queue<Data> qData;
	qData.push(Data());

	const int BeamWidth = 240;

	forange_type(int, d, D)
	{
		decltype(qData) next;
		forange(w, BeamWidth)
		{
			if (qData.empty()) break;

			const auto top = qData.top();
			qData.pop();

			forange_type(char, c, C)
			{
				Data nextData = top;
				const int score = getScore(nextData.last, c, d);

				nextData.last[c] = d;
				nextData.c[d] = c;
				nextData.score += score;

				next.push(nextData);
			}

		}

		qData.swap(next);
	}

	const auto& top = qData.top();

	cerr << "score:" << getScore(top.c) << endl;

	return top.c;
}

int main() {

	int d;
	cin >> d;

	for (auto& c : contest)
	{
		cin >> c;
	}

	forange(d, D)
	{
		forange(s, C)
		{
			cin >> satisfaction[d][s];
		}
	}

	const auto ans = think();

	for (const auto& a : ans)
	{
		cout << (int)(a + 1) << endl;
	}

	return 0;
}


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

long long member[4000];
bool ached[4000];
vector<int> ach;

int main(void){
  int n;
  while(true){
    cin >> n;
    if(n == 0)  break;
    fill(member, member + 4000, 0);
    fill(ached, ached + 4000, false);
    ach.clear();
    for(int i = 0; i < n; i++){
      long long id, tanka, suryo;
      cin >> id >> tanka >> suryo;
      member[id] += tanka * suryo;
      if(member[id] >= 1000000 && ached[id] == false){
        ach.push_back(id);
        ached[id] = true;
      }
    }

    if(ach.empty()){
      cout << "NA" << endl;
    }else{
      for(int i = 0; i < ach.size(); i++){
        cout << ach[i] << endl;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 1272
def examA():
    S = SI()
    ans = "No"
    if S[:4]=="YAKI":
        ans = "Yes"
    print(ans)


import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examA()


Measured memory_bytes: 38256
#include<stdio.h>
#include<string.h>
int main()
{
	char s[16];
	scanf("%s", s);
	if (strlen(s) < 4)
		printf("No\n");
	else if (s[0] == 'Y' && s[1] == 'A' && s[2] == 'K' && s[3] == 'I')
		printf("Yes\n");
	else
		printf("No\n");
	return 0;
}

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

using namespace std;

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


  int start = -1;
  int end = -1;
  for(int i = 0;i < s.length() - 1;i++){
    char cur_s = s[i];
    if(s[i + 1] == cur_s){
      start = (i + 1);
      end = (i + 2);
      // std::cout << (i + 1) << " " << (i + 2) << std::endl;
      break;
    }else if(i + 2 < s.length() && s[i + 2] == cur_s){
      start = (i + 1);
      end = (i + 3);
      // std::cout << (i + 1) << " " << (i + 3) << std::endl;
      break;
    }

    // char cur_s = s[i];
    // int count = 1;
    // int len = 1;
    // for(int j = 1;j < s.length();j++){
    //   if(s[j] == cur_s) count++;
    //   len++;

    //   if(count*2 > len){
    // 	std::cout << (i + 1) << " " << (j + 1) << std::endl;
    // 	exit(0);
    //   }
    //   int unbalance_len = len - count + 1 - count;
    //   int unbalance_num = (unbalance_len + len)/2 + 1;
    //   if(unbalance_len >= 2 && (unbalance_len > (unbalance_num - count)*2)){
    // 	break;
    //   }
    // }
  }

  std::cout << start << " " << end << std::endl;
}


Measured memory_bytes: 512
#include<iostream>
#include<math.h>
#define ll long long 
using namespace std;
int main()
{
	int n,i;
	ll a,b,c,d,temp,ans;
	while(scanf("%d",&n)!=EOF)
	{
		cin>>a>>b>>c>>d;
		if(a>b)
		{
			temp=a-b;
			
		}else temp=b-a;//数组由0到b-a 
		int flag=0;
		for( i=0;i<=n-1;i++)
		{
			ans=i*d-(n-1-i)*c;//可取上界 ，由 -c 和 d 构成 
			if(ans>=temp&&ans<=temp+(n-1)*(d-c))//(n-1)*(d-c)表示第 n 个上界的区间长度 ，从第二个square开始 
			{
				flag=1;
				break;
			}			
		}
		if(flag)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<double,double> pdd;
#define MEM(a, b) memset(a, (b), sizeof(a))
#define SZ(i) int(i.size())
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define REP1(i,j) FOR(i, 1, j+1, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define ALL(_a) _a.begin(),_a.end()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define X first
#define Y second
#ifdef tmd
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,deque<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
#endif

const ll MOD = 1000000007;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int iNF = 0x3f3f3f3f;
const ll MAXN = 200005; 

int n, a[MAXN];
vector<int> v;
/********** Good Luck :) **********/
int main()
{
    IOS();
    cin >> n;
    REP (i, n) {
        cin >> a[i];
        v.eb(a[i]);
    }
    sort(ALL(v));
    int mx1 = v.back(), mx2 = v[n-2];
    REP (i, n) {
        if (a[i] == mx1) {
            cout << mx2 << endl;
        } else {
            cout << mx1 << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3316
#include<bits/stdc++.h>
#include<string>
#include<vector>
using namespace std;
main()
{
	int n;
	cin>>n;
	map<string,int>mp;
	char prev;
	char next;
	int f=0;
	int f1 =0;
	for(int i=0;i<n;i++)
	{
		string s1;
		cin>>s1;
		mp[s1]++;
		if(f==0)
		{
			prev = s1[s1.length()-1];
			f=1;
		}
		else
		{
		//	cout<<prev<<" "<<s1[0]<<endl;
			if(prev != s1[0])
			{
				f1 = 1;
				//cout<<"here1"<<endl;
			}
			prev = s1[s1.length()-1];
		}
	}
	for (std::map<string,int>::iterator it=mp.begin(); it!=mp.end(); ++it)
	{
		if(it->second > 1)
		{
			f1 = 1;
		//	cout<<"here2"<<endl;
			break;
		}
	}
	//cout<<f1<<endl;
	if(f1 == 0)
	{
		cout<<"Yes"<<endl;
	}
	else
	{
		cout<<"No"<<endl;
	}
	
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
//#include <boost/functional/hash.hpp>
//example: unordered_set< pair<int,int>,boost::hash< std::pair<int, int> > > used;
//priority_queue< pair<int,pair<int,int> >, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int> > > > pqueue;    //cost, vertex(行き先)
using namespace std;

#define MODULE 1000000007
#define MP make_pair
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second

template<class T, class U>
inline void chmin(T &t, U f) { if (t > f)t = f; }

template<class T, class U>
inline void chmax(T &t, U f) { if (t < f)t = f; }

typedef pair<int, int> P;
typedef long long LL;
const LL INF = LLONG_MAX / 2;    //int_max->2*e+9 LLの時はLLONG_MAX
const int MAXN = 100001;

/*struct edge {
    edge(int to, int cost) : to(to), cost(cost) {}
    int to, cost;
};
vector<edge> graph[MAXN];

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

//-----Template---------
int h, w;
vector<string> color(301);
LL sum = 0;
int main() {
    ios::sync_with_stdio(false); //cout<< fixed << setprecision(10);
    cin >> h >> w;
    for (int i = 0; i < h; ++i) {
        cin >> color[i];
    }
    for (int i = 0; i < w - 1; ++i) {     //2列毎の最小コストを求める
        vector<vector<LL>> cost(301,vector<LL>(301));
        for (int j = 0; j <= h; ++j) {
            for (int k = 0; k <= h; ++k) {
                if (j == 0 || k == 0) {
                    LL tmp = 0;
                    for (int l = 0; l < h; ++l) {//0 .. h-1まで回して，変なとこを飛ばす
                        if (l - j >= 0 && l - k >= 0 && color[l - j][i] == color[l - k][i + 1])
                            tmp++;
                    }
                    cost[j][k] = tmp;
                } else {
                    cost[j][k] = cost[j - 1][k - 1] - (color[h - j][i] == color[h - k][i + 1] ? 1 : 0);
                }
            }
        }
        vector<vector<LL>> dp(301,vector<LL>(301,INF));
        dp[0][0] = 0;
        for (int j = 0; j <= h; ++j) {
            for (int k = 0; k <= h; ++k) {
                LL tmpA = j > 0 ? dp[j - 1][k] + cost[j - 1][k] : INF;
                LL tmpB = k > 0 ? dp[j][k - 1] + cost[j][k - 1] : INF;
                chmin(dp[j][k], min(tmpA, tmpB));
            }
        }
        sum += dp[h][h];
    }
    cout << sum << endl;
}

Measured memory_bytes: 1888
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
#define ff first
#define ss second
#define pb push_back
#define debug(val) cerr << "The value of " << #val << " is = " << val << '\n';
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll inf = 922337203685477;
const ll mininf = -922337203685477;
const ll nax = 1e5 + 5;
string a;
int b;

int main(){
	IOS
	cin >> a;
	b=a.length();
	int l=0;
	int r=b-1;
	int ans=0;
	while(l<=r){
		if(a[l]!=a[r]){
			ans++;
		}
		l++;
		r--;
	}
	cout << ans << '\n';
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int N,X;
    cin >> N >> X;
    vector<int> D(N+1);
    D[0] = 0;
    
    for(int i=0;i<N;i++){
        int x;
        cin >> x;
        D[i+1] = D[i] + x;
    }
    
    int count = 0;
    
    for(int i=0;i<=N;i++){
        if(D[i]<=X) count++;
    }

    
    cout << count;
    return 0;
}

Measured memory_bytes: 3564
# ABC087 B

def main():
    a = int(input())
    b = int(input())
    c = int(input())
    x = int(input())

    result = 0

    for i in range(a+1):
        for j in range(b+1):
            for k in range(c+1):
                total = 500 * i + 100 * j + 50 * k
                if total == x:
                    result += 1
    
    print(result)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
MOD=10**9+7
cnt=0; sum=0; prev=nil; h=Hash.new(0)
def gs() gets.chomp end
def gi() gets.to_i end
def gsmi() gets.chomp.split.map(&:to_i) end

def desc(ar) ar.sort!{|x,y|y<=>x} end
def min(a,b) a<=b ? a : b end
def max(a,b) a>=b ? a : b end

def puts_yesno(can) puts(can ? 'Yes' : 'No') end
def putsend(s) puts s; exit end
def debug(k,v) puts "#{k}:#{v}" end
########### ( ˘ω˘ )ｽﾔｧ… ###########
a,b,c,d=gsmi

# U-(Cで割り切れる)-(Dで割り切れる)+(CとDで割り切れる)
all = b-a+1
[c,d].each do |i|
  num = i
  cnt = b/num - (a-1)/num
  all -= cnt
end

lcm = c.lcm(d)
cnt = b/lcm - (a-1)/lcm
all += cnt

puts all

Measured memory_bytes: 1788
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<functional>
using namespace std;
long long n, a, b, c[100009], d[100009];
bool solve(long long P) {
	if (P < 0)return false;
	for (int i = 0; i < n; i++)d[i] = c[i] - P*b;
	long long ret = 0;
	for (int i = 0; i < n; i++) { if (d[i] >= 0)ret += (d[i] + (a - b) - 1) / (a - b); }
	if (ret > P)return false;
	return true;
}
int main() {
	cin >> n >> a >> b;
	for (int i = 0; i < n; i++)cin >> c[i];
	long long L = -1, R = 1000000009, M;
	while (true) {
		M = (L + R) / 2;
		bool p1 = solve(M - 1), p2 = solve(M);
		if (p1 == false && p2 == true) { cout << M << endl; break; }
		if (p1 == true)R = M; else L = M;
	}
	return 0;
}

Measured memory_bytes: 1792
#include<iostream>
using namespace std;
    int n;

int main(){
    cin>>n;
    int H[100000];
    int p=n-1;
    for(int i=0;i<n;i++) cin>>H[i];
    bool cc=true;
    if(n>2){
        while(p>=1){
            if(H[p]==H[p-1]-1) H[p-1]--;
            else if(H[p]<H[p-1]-1){
                cc=false;
                break;
            }
            p--;
        }
    }
    if(cc) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void solve() {
    ll N, M;
    cin >> N >> M;
    Graph graph(N);
    vector<ll> out(N, 0);
    rep(i, M) {
        ll x, y;
        cin >> x >> y;
        x--;
        y--;
        graph[y].push_back(x);
        out[x] ++;
    }
    queue<ll> que;
    rep(i, N) {
        if (out[i] == 0) {
            que.push(i);
        }
    }
    vector<ll> dp(N, 0);
    while (!que.empty()) {
        ll p = que.front();
        que.pop();
        for (ll rev : graph[p]) {
            out[rev] --;
            if (out[rev] == 0) {
                que.push(rev);
                dp[rev] = dp[p] + 1;
            }
        }
    }
    cout << *max_element(dp.begin(), dp.end()) << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}


Measured memory_bytes: 10156
<?php

list($n, $m) = explode(' ', trim(fgets(STDIN)));

$ans = array();
for ($i=1; $i <= $n; $i++) {
  $ans[$i] = '*';
}

for ($i=0; $i < $m; $i++) {
  list($s, $c) = explode(' ', trim(fgets(STDIN)));

  if ($ans[$s] == '*' || $ans[$s] == $c) {
    $ans[$s] = $c;
  } else {
    echo -1;
    exit;
  }
}

if ($n > 1 && $ans[1] === '0') {
  echo -1;
  exit;
}

foreach ($ans as $k => $v) {
  if ($v === '*') {
    $ans[$k] = 0;
  }
}

if ($n > 1 && $ans[1] == 0) {
  $ans[1] = 1;
}

echo implode('', $ans);


Measured memory_bytes: 4856
using System.Collections.Generic;
using System;

public class P
{
    public int w { get; set; }
    public int L { get; set; }
}

public class Hello
{
    public static void Main()
    {
        while (true)
        {
            string[] line = Console.ReadLine().Trim().Split(' ');
            var n = int.Parse(line[0]);
            var k = int.Parse(line[1]);
            if (n == 0 && k == 0) break;
            var aa = new List<int>();
            var zero = false;
            for (int i = 0; i < k; i++)
            {
                var wa = int.Parse(Console.ReadLine().Trim());
                if (wa == 0) zero = true;
                else  aa.Add(wa);
            }
            var a = aa.ToArray();
            Array.Sort(a);
            Console.WriteLine(zero ?  getAns2(a): getAns1(a));
        }
    }
    public static int getAns2 (int [] a)
    {
        var ps = new List<P>();
        var tmax = 1;       var pre = a[0];   var pres = 0;
        for (int i = 1; i < a.Length; i++)
        {
            if (a[i] == pre + 1) { tmax++; }
            else
            {
                ps.Add(new P { w = a[ pres] - 1,L = tmax });
                ps.Add(new P { w =a[ i -1] + 1, L = tmax });
                pres = i;
                tmax = 1;
            }
            pre = a[i];
        }
        ps.Add(new P { w = a[pres] - 1, L = tmax });
        ps.Add(new P { w = a[a.Length-1] + 1, L = tmax });
        var dret = new Dictionary<int, int>();
        var ret = 0;
        foreach (var x in ps)
        {
            if (dret.ContainsKey(x.w)) dret[x.w] += x.L;
            else dret[x.w] = x.L + 1;
            ret = Math.Max(ret, dret[x.w]);
        }
        return ret;
    }
    public static int getAns1(int[] a)
    {
        var tmax = 1; var pre = a[0]; var ret = tmax;
        for (int i = 1; i < a.Length; i++)
        {
            if (a[i] == pre + 1) { tmax++; }
            else { ret = Math.Max(ret, tmax); tmax = 1; }
            pre = a[i];
        }
        ret = Math.Max(ret, tmax);
        return ret;
    }
}



Measured memory_bytes: 12348
using System;

namespace B___Ordinary_Number
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var pi = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);

            var result = 0;
            for (int i = 1 ;i+1<N;i++) if((pi[i]>pi[i+1] &&pi[i]<pi[i-1])||(pi[i]<pi[i+1]&&pi[i]>pi[i-1])) result +=1;

            Console.WriteLine(result);
        }
    }
}


Measured memory_bytes: 13140
h, w = map(int, input().split())
fld = [list(map(int, input().split())) for _ in range(h)]


def generate_unagi():
    for i in range(h):
        if i % 2 == 0:
            for j in range(w):
                yield (i, j)
        else:
            for j in reversed(range(w)):
                yield (i, j)


ans = []
it = list(generate_unagi())
for (i, j), (i2, j2) in zip(it, it[1:]):
    if fld[i][j] % 2 == 0:
        continue
    fld[i][j] -= 1
    fld[i2][j2] += 1
    ans.append((i+1, j+1, i2+1, j2+1))

print(len(ans))
for row in ans:
    print(*row)

Measured memory_bytes: 48364
EPS = 0.0000000001

class Point:
    
    global EPS
    
    def __init__(self, x = 0, y = 0):
        self.x = x
        self.y = y
        
        
    def __add__(a, b):
        s = a.x + b.x
        t = a.y + b.y
        return Point(s, t)
        
    def __sub__(a, b):
        s = a.x - b.x
        t = a.y - b.y
        return Point(s, t)
            
    def __mul__(self, a):
        s = a * self.x
        t = a * self.y
        return Point(s, t)
        
    def __truediv__(self, a):
        s = self.x / a
        t = self.y / a
        return Point(s, t)
            
            
            
            
    def norm(self):
        return self.x * self.x + self.y * self.y
        
    def abs(self):
        return self.norm() ** 0.5
            
    
            
            
    def __eq__(self, other):
        return abs(self.x - other.y) < self.EPS and abs(self.y - other.y) < self.EPS
            
            
            
    def dot(self, b):
        return self.x * b.x + self.y * b.y
        
    def cross(self, b):
        return self.x * b.y - self.y * b.x
    
    

def isOrthogonal(a, b):
    return a.dot(b) == 0

def isParallel(a,b):
    return a.cross(b) == 0


n = int(input())
for i in range(n):
    nums=list(map(int,input().split()))
    a = Point(nums[0] - nums[2], nums[1] - nums[3])
    b = Point(nums[4] - nums[6], nums[5] - nums[7])

    if isParallel(a,b):
        print(2)
    elif isOrthogonal(a, b):
        print(1)
    else:
        print(0)






























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

int main() 
{
  int A, B;
  int count;
  
  int num = 1;
  
  cin >> A >> B;
  
  while(num < B)
  {
    num += A-1;
    count++;
  }
  
  cout << count << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 9223372036854775807;
const ll half_inf = 0x3f3f3f3f;
const ll inf = 0x7fffffff;
const ll maxn = 200005;
const ll N = 500005;
char s[200005];
ll a[200005],mod[200005],mod2[200005],n,p,sum=0;
map<ll,ll> m;
int main(){  
	cin.tie(0); 
    ios::sync_with_stdio(false);
	scanf("%lld%lld%s",&n,&p,s);
	for(ll i=0;i<n;i++) a[n-i]=s[i]-'0'; // a[1]到 a[n]反向存储字符串(低位在前高位在后) 
	mod[1]=1;
	for(ll i=2;i<=n;i++) mod[i]=mod[i-1]*10%p; // mod[i]存储第 i位在 p下的有效位权 
	mod2[1]=a[1]%p;
	for(ll i=2;i<=n;i++) mod2[i]=(mod[i]*a[i]+mod2[i-1])%p; // mod2[i]存储前 i位数(p下的有效数) 
	if(p==2){ // 特判 2  只看末位即可 
		for(ll i=1;i<=n;i++) if(a[i]%2==0) sum+=n-i+1;
		printf("%lld",sum);
	}
	else if(p==5){ // 特判 5  只看末位即可
		for(ll i=1;i<=n;i++) if(a[i]==0||a[i]==5) sum+=n-i+1;
		printf("%lld",sum);
	}
	else{
		for(ll i=1;i<=n;i++) m[mod2[i]]++;
		for(map<ll,ll>::iterator it=m.begin();it!=m.end();it++){
			ll num=it->second;
			if(it->first==0) sum+=(num+1)*num/2;
			else sum+=(num-1)*num/2;
		}
		printf("%lld",sum);
	}
	return 0;
}


Measured memory_bytes: 5760
# ABC162AB

n = int(input())

total = n * (n + 1) // 2

n3 = n // 3
n5 = n // 5
n15 = n // 15

s3 = n3 * (n3 +1) // 2 * 3
s5 = n5 * (n5 +1) // 2 * 5
s15 = n15 * (n15 +1) // 2 * 15

print(total - s3 - s5 + s15)



Measured memory_bytes: 9204
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		int k = sc.nextInt();

		int n = 0;
		for(int i=100;i>=1;i--) {
			if(a%i == 0 && b%i == 0) {
				n++;
				if(n == k) {
					out.println(i);
				}
			}
		}

		sc.close();

	}

	public static void main(String[] args) {
		new Main()._main(args);
	}

}


Measured memory_bytes: 25044
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int W = Integer.parseInt(sc.next());
        long dp[][] = new long[N+1][W+1];
        for(int i=1;i<=N;i++){
            int w = Integer.parseInt(sc.next());
            long v = Long.parseLong(sc.next());
            for(int j=0;j<=W;j++){
                if(j>=w){
                    if(i==1) dp[i][j] = v;
                    else dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w]+v);
                }else{
                    if(i>1) dp[i][j] = dp[i-1][j];
                }
            }
        }
        System.out.println(dp[N][W]);
    }
}


Measured memory_bytes: 125524
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


s = input()
for i in range(len(s)):
    if (i%2==0 and s[i]=="L") or (i%2==1 and s[i]=="R"):
        ans = "No"
        break
else:
    ans = "Yes"
print(ans)

Measured memory_bytes: 61868
n,a,b,c,d=map(int,input().split())
a,b=sorted([a,b])
for i in range(n-1):
    if max(a+c*(i),b+c*(n-1-i))<=min(b+d*(n-1-i),a+d*(i)):
        print("YES");exit()
print("NO")

Measured memory_bytes: 3064
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
//#include<set>
//#include<iostream>
using namespace std;

int n,q,K;
#define maxn 100011
#define LL long long
struct Edge{int to,next,v;};
struct Tree
{
	Edge edge[maxn<<1];
	LL st[maxn][20],fa[maxn][20];
	int first[maxn],le,dep[maxn];
	LL dis[maxn];
	Tree() {le=2;}
	void in(int x,int y,int v)
	{
		edge[le].to=y;
		edge[le].v=v;
		edge[le].next=first[x];
		first[x]=le++;
	}
	void insert(int x,int y,int v)
	{
		in(x,y,v);
		in(y,x,v);
	}
	void dfs(int x,int f,int v,int cur)
	{
		st[x][0]=v;
		fa[x][0]=f;
		dep[x]=cur;
		dis[x]=dis[f]+v;
		for (int i=first[x];i;i=edge[i].next)
			if (edge[i].to!=f)
				dfs(edge[i].to,x,edge[i].v,cur+1);
	}
	void makest()
	{
		for (int j=1;j<=18;j++)
			for (int i=1;i<=n;i++)
			{
				fa[i][j]=fa[fa[i][j-1]][j-1];
				st[i][j]=st[i][j-1]+st[fa[i][j-1]][j-1];
			}
	}
	LL find(int x,int y)
	{
		int xx=x,yy=y;
		if (dep[x]<dep[y]) swap(x,y);
		for (int j=18;j>=0;j--)
			if (dep[fa[x][j]]>=dep[y]) x=fa[x][j];
		if(x==y) return dis[xx]+dis[yy]-2*dis[x];
		for (int j=18;j>=0;j--)
			if (fa[x][j]!=fa[y][j])
			{
				x=fa[x][j];
				y=fa[y][j];
			}
		int lca=fa[x][0];return dis[xx]+dis[yy]-2*dis[lca];
	}
}t;
int x,y,v;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<n;i++)
	{
		scanf("%d%d%d",&x,&y,&v);
		t.insert(x,y,v);
	}
	t.dfs(1,0,0,1);
	scanf("%d%d",&q,&K);
	t.makest();
	for (int i=1;i<=q;i++)
	{
		scanf("%d%d",&x,&y);
		printf("%lld\n",t.find(x,K)+t.find(K,y));
	}
	return 0;
}

Measured memory_bytes: 40320
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
namespace io
{
	int F()
	{
		int n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
		return F?n:-n;
	}
}
int d[66666],p[6666],pp;
int main()
{
	for(register int i=2;i<=55555;++i)
	{
		if(!d[i])d[i]=p[++pp]=i;
		for(register int j=1,u=dmin(d[i],55555/i);j<=pp&&p[j]<=u;++j)
			d[i*p[j]]=p[j];
	}
	int n=io::F();
	for(register int i=1;i<=pp&&n;++i)
		if(p[i]%5==2)printf("%d ",p[i]),--n;
	return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<functional>
#include<string>
#include<iomanip>
#include<map>
#include<utility>
#include<string>
#include<unordered_map>
#include <queue>

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

using namespace std;

#define min_3(a, b, c) min(a, min(b, c))
#define max_3(a, b, c) max(a, max(b, c))
typedef long long ll;

int main()
{
    int n;
    cin >> n;
    vector<double> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];
    sort(v.begin(), v.end());
    double ans = v[0];
    for(int i = 1; i < n; i++){
        ans = (ans+v[i])/2;
    }
    cout << ans << endl;
    return 0;
}


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

typedef long long ll;

const int N = 3000 + 20;
const ll inf = 1e18;
int r, c, k;
ll  val[N][N];
ll dp[N][N][4];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> r >> c >> k;
	for (int i = 1; i <= r; i++)
		for (int j = 1; j <= c; j++)
			val[i][j] = -inf;
	for (int i = 0; i < k; i++) {
		int R, C, V;
		cin >> R >> C >> V;
		val[R][C] = V;
	}
	dp[1][1][0] = 0;
	dp[1][1][1] = val[1][1];
	dp[1][1][2] = dp[1][1][3] = -inf;
	for (int i = 1; i <= r; i++)
		for (int j = 1; j <= c; j++) {
			if (i > 1 || j > 1) 
				dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = dp[i][j][3] = -inf;
			if (i > 1) { 
				dp[i][j][0] = max({dp[i - 1][j][0], dp[i - 1][j][1], dp[i - 1][j][2], dp[i - 1][j][3]});
				dp[i][j][1] = dp[i][j][0] + val[i][j];
			}
			for (int k = 0; k <= 3; k++) {
				if (j > 1)
					dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k]);
				if (j > 1 && k)
					dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k - 1] + val[i][j]);
			}
		}
	cout << max({dp[r][c][0], dp[r][c][1], dp[r][c][2], dp[r][c][3]}) << "\n";
}


Measured memory_bytes: 357272
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <functional>
#include <stack>
#include <numeric>
typedef long long ll;
using namespace std;
const int MOD = (int)1e9 + 7;
const ll INF = (ll)1e18 + 7;
//#define int long long
#define all(vec) vec.begin(), vec.end()
#define dbg(x) cerr << #x << " = " << (x) << endl
#define yn(b) cout << ((b) ? "Yes" : "No") << endl
#define YN(b) cout << ((b) ? "YES" : "NO") << endl
#define isEven(t) t % 2 == 0

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

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

	int A,B,C,D;
	cin>>A>>B>>C>>D;

	if(A+B>C+D){
		cout << "Left" << endl;
	}
	if(A+B==C+D){
		cout << "Balanced" << endl;
	}
	if(A+B<C+D){
		cout << "Right" << endl;
	}
	return 0;
}

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

int main()
{
    ll n;
    cin >> n;
    map<string, int> S;
    rep(i, n)
    {
        string s;
        cin >> s;
        S[s]++;
    }

    cout << "AC"
         << " x " << S["AC"] << endl;
    cout << "WA"
         << " x " << S["WA"] << endl;
    cout << "TLE"
         << " x " << S["TLE"] << endl;
    cout << "RE"
         << " x " << S["RE"] << endl;
}

Measured memory_bytes: 3632
n = int(input())

if n < 10:
    print(n)
    exit()

t = 10
k = 1
ans = 9
while t <= n:
    if k % 2 == 0:
        ans += t * 9
    t *= 10
    k += 1

#print(k, t, ans)

if k % 2 == 1:
    ans -= t - n - 1

print(ans)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <algorithm>
#define rep(i,w) for (int i = 0;i < (w); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
int INF = 1e9;
int main(){
  int n,m;cin >> n >> m;
  vector<vector<int>> swi(m);
  rep(i,m){
    int k;cin >> k;
    rep(j,k){
      int s;cin >> s;
      --s;
      swi[i].push_back(s);
    }
  }
  vector<int> num(m);
  rep(i,m) cin >> num[i];
  int ans = 0;
  rep(bit,1<<n){
    bool flag = true;
    rep(i,m){
      int cnt = 0;
      rep(j,swi[i].size()) if(bit>>swi[i][j]&1) cnt++;
      if(cnt%2 != num[i]) {
        flag = false;
        break;
      }
    }
    if(flag) ans++;
  }
  cout << ans << endl;


}

Measured memory_bytes: 3644
def find_bill_combination(n, y):
	q, mod = divmod(y, 10000)
	if n * 10000 > y > (n - 1) * 10000 + 5000:
		return '-1 -1 -1'
	else:
		if q == n and mod == 0:
			return '{} 0 0'.format(q)
		else:
			for a in range(q + 1):
				b = int((y - 1000 * n - 9000 * a) / 4000)
				c = int((5000 * n - y + 5000 * a) / 4000)
				if a + b + c == n and a >= 0 and b >= 0 and c >= 0 and 10000 * a + 5000 * b + 1000 * c == y:
					return '{} {} {}'.format(a, b, c)
			else:
				return '-1 -1 -1'


def main():
	n, y = map(int, input().split(' '))
	print(find_bill_combination(n, y))


if __name__ == '__main__':
	main()


Measured memory_bytes: 3064
import java.util.*;
import java.io.*;

class Main {
	public static void main(String[] args) throws IOException {
    	Scanner sc = new Scanner(System.in);
      	int N = Integer.parseInt(sc.next());
      	int cnt = 0;
      	if (N != 0) {
        	String s = sc.next();
  			s = s.replace("ABC", "0");
          	char[] a = s.toCharArray();
          	for (int i = 0; i < a.length; i++) {
            	if (a[i] == '0') { cnt++; }
            }
        }
      	System.out.println(cnt);
    }
}

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

using namespace std;

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    
    if(a<b) swap(a,b);
    if(b<c) swap(b,c);
    if(a<b) swap(a,b);
    
    int cnt = 0;
    cnt += a-b;
    b += cnt;
    c += cnt;

    int res = (b-c)%2;
    cnt += (b-c)/2;
    if(res!=0){
        cnt +=2;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
def main():
    N=int(input())
    A=list(map(int,input().split()))

    L={}
    R={}

    for i in range(N):
        l=(i+1)+A[i]
        r=(i+1)-A[i]
        if (l in L.keys()):
            L[l]+=1
        else:
            L[l]=1
        if r in R.keys():
            R[r]+=1
        else:
            R[r]=1

    res=0
    for key in L.keys():
        if key in R.keys():
            res+=R[key]*L[key]

    print(res)
if __name__=="__main__":
    main()


Measured memory_bytes: 146092
// In the name of Allah the Most Merciful.

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

typedef long long ll;

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

    ll n;
    cin >> n;
    cout << 3LL*n*n << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

int go(string s, char c){
	int v=0;
	int ff=0;
	for (char t:s){
		if (t==c) ff=1;
	}
	if (!ff) return s.size();
	while (1){
		int f=0;
		for (int i=0;i<(int)s.size();i++){
			if (s[i]!=c) {
				f=1;
				break;
			}
		}
		if (!f) return v;
		string ns;
		for (int i=0;i+1<(int)s.size();i++){
			if (s[i]==c||s[i+1]==c){
				ns+=c;
			}
			else{
				ns+='.';
			}
		}
		s=ns;
		v++;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin>>s;
	int v=s.size();
	for (char c='a';c<='z';c++){
		v=min(v, go(s, c));
	}
	cout<<v<<endl;
}

Measured memory_bytes: 256
object Main extends App {
  val in = new java.util.Scanner(System.in)
  val N = in.nextInt
  val Ps, Qs = Array.fill(N)(in.nextInt).mkString
  val ls = (1 to N).mkString.permutations.toList
  println(Math.abs(ls.indexOf(Ps) - ls.indexOf(Qs)))
}

Measured memory_bytes: 37212
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

ll MOD = 998244353;

int main(){
  ll N, M, K;
  cin >> N >> M >> K;

  vl fact(N, 0);
  fact[0] = 1;
  rep2(i, 1, N) fact[i] = i * fact[i - 1] % MOD;
  vl fact_inv(N, 0);
  fact_inv[0] = 1;
  rep2(i, 1, N){
    ll a = 1;
    ll p = fact[i];
    ll e = MOD - 2;
    while(e > 0){
      if(e%2 == 0){
	p = p * p % MOD;
	e /= 2;
      } else{
	a = a * p % MOD;
	e--;
      }
    }
    
    fact_inv[i] = a % MOD;
  }

  ll ans = 0;

  rep(i, K + 1){
    ll a = 1;
    ll p = M - 1;
    ll e = N - 1 - i;
    while(e > 0){
      if(e%2 == 0){
	p = p * p % MOD;
	e /= 2;
      } else{
	a = a * p % MOD;
	e--;
      }
    }
    a  = a * fact[N - 1] % MOD;
    a = a * fact_inv[i] % MOD;
    a = a * fact_inv[N - 1 - i] % MOD;
    ans += a;
    ans %= MOD;
  }

  ans = ans * M % MOD;

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


Measured memory_bytes: 6348
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * Built using CHelper plug-in Actual solution is at the top
 */

public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task solver = new Task();
		solver.solve(1, in, out);
		out.close();
	}

	static class Task {
		public void solve(int testNumber, InputReader in, PrintWriter out) {
			int N = in.nextInt();
			out.println("ABC" + N);
		}
	}
		
	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

Measured memory_bytes: 21460
import math
n, d = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(n)]
count = 0

for i in range(n):
    count = count + 1 if math.sqrt(xy[i][0]**2 + xy[i][1]**2) <= d else count

print(count)


Measured memory_bytes: 45384
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 1000000002486618624LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


std::vector<std::vector<int>> G;

std::vector<int> visit;


void dfs(const int id, int i) {
  for (const auto& k : G[i])
    if (visit[k] == -1) {
      visit[k] = id;

      dfs(id, k);
    }
}


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);

  int N, a, b;

  std::cin >> N;

  G.resize(N + 1);

  for (int i = 0; i < N - 1; i ++) {
    std::cin >> a >> b;

    G[a].push_back(b);
    G[b].push_back(a);
  }

  std::queue<std::pair<int, int>> queue;

  std::vector<int> parent(N + 1, -1);

  queue.emplace(1, 0);

  visit.resize(N + 1);

  visit[1] = 1;

  parent[1] = 0;

  int i, d;

  while (! queue.empty()) {
    std::tie(i, d) = queue.front(); queue.pop();

    for (const auto& k : G[i]) {
      if (! visit[k]) {
        visit[k] = k;

        parent[k] = i;
        
        if (k == N)
          goto end;

        queue.emplace(k, d + 1);
      }
    }
  }

 end:

  std::deque<int> deque;

  std::fill(ALL(visit), -1);

  for (int x = N; x; x = parent[x])
    deque.push_front(x);

  while (1) {
    if (! deque.empty()) {
      visit[deque.front()] = 0;

      deque.pop_front();
    }
    else {
      break;
    }

    if (! deque.empty()) {
      visit[deque.back()] = 1;

      deque.pop_back();
    }
    else {
      break;
    }
  }

  for (int i = 1; i <= N; i ++)
    if (visit[i] != -1)
      dfs(visit[i], i);

  int ca = 0, cb = 0;

  for (int i = 1; i <= N; i ++)
    (visit[i] == 0 ? ca : cb) ++;

  std::cout << (ca > cb ? "Fennec" : "Snuke") << std::endl;

  return 0;
}


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

const int N = 200010;
vector<int> G[N];
vector<int> Count(N);
int n, q;

void dfs(int now, int pre){
    for(int i = 0; i < G[now].size(); i++){
        int to = G[now][i];
        if(to == pre) continue;
        Count[to] += Count[now];
        dfs(to, now);
    }
}

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

    cin >> n >> q;
    
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for(int i = 0; i < q; i++){
        int p, x;
        cin >> p >> x;
        p--;
        Count[p] += x;
    }

    dfs(0, -1);

    for(int i = 0; i < n; i++){
        cout << Count[i] << ' ';
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 26624
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_ ; ++i)
#define drep(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_ ; --i)
#define clear(a, b) memset((a), (b), sizeof(a))
typedef long long LL;
int read() {
	int x = 0, flag = 1;
	char ch = getchar();
	while(!isdigit(ch)) {
		if(ch == '-') flag = -1;
		ch = getchar();
	}
	while(isdigit(ch)) {
		x = (x << 3) + (x << 1) + (ch - 0x30);
		ch = getchar();
	}
	return flag * x;
}
 
#define Maxn 109
int n, a[Maxn];
int vis[Maxn];
int Max, Min;
int main() {
#ifdef Qrsikno
	freopen("e.in","r",stdin);
	freopen("e.out","w",stdout);
#endif
	Max = -0x3f3f3f3f, Min = -Max;
	n = read();
	rep(i, 1, n) a[i] = read(), Max = max(a[i], Max), Min = min(Min, a[i]);
	if(n == 2) {
		if(Min == Max && Min == 1) puts("Possible");
		else puts("Impossible");
		return 0;
	}
	if(Min != (Max + 1) / 2) {
		puts("Impossible");
		return 0;
	}
	rep(i, 1, n) ++vis[a[i]];
	if(Min == 1 && vis[1] != 1) {
		puts("Impossible");
		return 0;
	}
	rep(i, Min, Max) 
		if(!vis[i] || vis[i] < 2 && i != Min) {
			puts("Impossible");
			return 0;
		}
	if((Max & 1) && vis[Min] != 2 || !(Max & 1) && vis[Min] != 1) {
		puts("Impossible");
		return 0;
	}
	puts("Possible");
	return 0;
}

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

int main()
{
#define int long long
    const int INF = 1e18 + 5;
    int n, w;
    cin >> n >> w;

    vector<int> weight(n + 1);
    vector<int> value(n + 1);

    for (int i = 1; i <= n; i++)
    {
        cin >> weight[i];
        cin >> value[i];
    }

    int val_sum = 0;
    for (int i = 1; i <= n; i++)
        val_sum += value[i];

    vector<int> dp(val_sum + 1, INF);
    vector<int> ndp(val_sum + 1, INF);
    dp[0] = 0;
    ndp[0] = 0;

    for (int item = 1; item <= n; item++) // update for every item
    {
        for (int j = val_sum; j >= value[item]; j--) // dp[i] - max cost to get value i exactly
        {
            dp[j] = min(dp[j], weight[item] + dp[j - value[item]]);
        }

        // for (int j = 1; j <= val_sum; j++)
        // {
        //     if (dp[j] == INF)
        //         cout << "X ";
        //     else
        //         cout << dp[j] << " ";
        // }
        // cout << "\n";
        // dp = ndp;
    }

    int best = 0;
    for (int i = 1; i <= val_sum; i++)
        if (dp[i] <= w)
            best = i;

    cout << best << "\n";
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n,y;
  //a+b+c=n
  //10000a+5000b+1000c=y
  //9000a+4000b=y-1000n
  //
  cin>>n>>y;
  for(int i=0;i<=n;i++){
    for(int j=0;j<=n;j++){
      if(9000*i+4000*j+1000*n==y&&n-i-j>=0){
        cout<<i<<" "<<j<<" "<<n-i-j<<endl;
        return 0;
      }
    }
  }
  cout<<-1<<" "<<-1<<" "<<-1<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    ll a, b, c; cin >> a >> b >> c;
    int cnt = 0;
    for(int i=a; i<=b; i++) if(i % c == 0) cnt++;
    cout << cnt;
}

Measured memory_bytes: 3648