akhauriyash/Code-Regression huggingface dataset:
N, K = map(int, input().split())
S = input()
 
counts = [0]
if S[0] == "0":
	counts.append(0)
last_char = S[0]
for s in S:
	if s == last_char:
		counts[-1] += 1
	else:
		counts.append(1)
		last_char = s
if S[-1] == "0":
	counts.append(0)
l, r = 0, K * 2 + 1
max_count = last_count = sum(counts[l:r])
while True:
	l, r = l + 2, r + 2
	if len(counts) < r:
		break
	count = last_count - (counts[l - 1] + counts[l - 2]) + (counts[r - 1] + counts[r - 2])
	max_count = max(max_count, count)
	last_count = count
print(max_count)


Measured memory_bytes: 4596
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <iomanip>
#include <complex>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define SIZE 100005

using namespace std;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
typedef pair<int,ll> pill; typedef pair<ll,int> plli; 
typedef pair<double, int> pdi;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
typedef complex<double> P;
long long int MOD = 1000000007;
ll A,B,C,D;
int N;
int main()
{
	cin>>N>>A>>B>>C>>D;
	N--;
	A=2*A,B=2*B,C=2*C,D=2*D;
	ll x=(C+D)/2,y=(D-C)/2;
	bool flag=false;
	for(int i=0;i<=N;i++){
		ll hoge=(ll)(N-2*i);
		hoge=hoge*x;
		if(A+hoge+N*y>=B&&A+hoge-N*y<=B)flag=true;
	}
	if(flag)cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
}

Measured memory_bytes: 764
/*************************************************************************
    > File Name: C.cpp
    > Author: Roundgod
    > Mail: wcysai@foxmail.com 
    > Created Time: 2018-09-02 12:12:50
 ************************************************************************/

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define MAXN 100005
#define INF 1000000000
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
ll n,k,a[MAXN];
int main()
{
    scanf("%lld%lld",&n,&k);
    ll ans=0;
    ans=(n/k)*(n/k)*(n/k);
    if(k%2==0)
    {
        if(n>=k/2)
        {
            ll cnt=(n-k/2)/k+1;
            ans+=cnt*cnt*cnt;
        }
    }
    printf("%lld\n",ans);
    return 0;
}



Measured memory_bytes: 256
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi  vector<int> 
#define   dbg(x)  cerr << #x << " = " << x << '\n'
#define   sz(x)  (int)x.size()
#define   all(a) (a.begin(),a.end())
#define   ff   first
#define   ss   second
#define   pii  pair<int,int> 
#define   lcm(a,b) (a*b)/__gcd(a,b) 
using namespace std;

int g[105][105],a[10005],h,w,n; 
inline void solve(){
    cin>>h>>w>>n; 
    for (int i=1;i<=n;i++)  cin >> a[i] ; 
    for (int in=1,i=1,j=1;in<=n;in++){
        int cnt=a[in];
        while (cnt--){
            g[i][j]=in;
            j++;
            if (j>w) j=1,i++;
        }
    }
    for (int i=1;i<=h;i++){
        for (int j=(i&1)?1:w;j>0 and j<=w;j+=(i&1)?1:-1)
            cout << g[i][j] << " ";
        cout << endl;
    }
}

signed main()
{
    int n=1; // cin>>n;
    while (n--) solve();
    return 0;
}


Measured memory_bytes: 3700
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <map>
#include <iomanip>
#include <limits.h>
#include <cmath>

using namespace std;    
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const bool DEBAG = false;


// xを二進数に変換
vector<ll> to2(ll x){
    vector<ll> ret;
    while(x > 0){
        if(x % 2){
            ret.push_back(1);
        }
        else{
            ret.push_back(0);
        }
        x /= 2;        
    }
    return ret;
}

ll myPow(ll x, ll n){
    vector <ll> r = to2(n);
    vector <ll> v(r.size()); // v[0] = v^1 v[1] = v^2, v[2] = v^4, v[3] = v^8, 

    ll tmp = 1;
    for(ll i = 0; i < r.size(); i++){ 
        if(i == 0) v[i] = x;
        else v[i] = v[i-1] * v[i-1];

        if(r[i] == 1){
            tmp *= v[i];
        }
    }
    return tmp;

}

int main(){

    ll N, P;
    cin >> N >> P;

    if(N == 1 || P == 1) {
        cout << P << endl;
        return 0;
    }

    ll logMax = log(P) / N + 1;

    ll left = 1;
    ll right = P;

    while(right - left >= 2){
        ll mid = (right + left) / 2;
        if( log(mid) <= logMax ){
            left = mid;
        }
        else{
            right = mid;
        }
    }

    
    for(ll i = right; i >= 1; i--){
        if(myPow(i , N) <= 0) continue;
        if( P % myPow(i , N) == 0 ){
            cout << i << endl;
            return 0;
        }
    }
    

}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define ll long long
#define ull unsigned long long
#define ld long double
#define vl vector<long long>
#define vvl vector<vector<long long>>
#define rbf(a, x) for (auto& a : x)
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define drep(i, x) for (ll i = ((ll)(x)-1); i >= 0; i--)
#define pll pair<long long,long long>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define vvc vector<vector<char>>
#define vc vector<char>
#define vvb vector<vector<bool>>
#define vb vector<bool>
#define Maxe(x) *max_element(all(x))
#define Mine(x) *min_element(all(x))
#define Size(x) ((ll)(x).size())
#define umap unordered_map
const long long INF = 1LL << 60;
const long double pi = 3.1415926535897932;
#define Fi first
#define Se second
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

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

//lis,modpow,uf,modncr,soinsubunkai,yakusurekkyo
//mint,dijkstra,gyakugen

    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        ll n;
        cin>>n;
        ll a=0;
        vl A(n);
        rep(i,n){
            cin>>A[i];
            a=a^A[i];
        }
        rep(i,n){
          	ll c=a^A[i];
          	cout<<c<<' ';
        }
        cout<<endl;
    }

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

int main() {
  int count = 0;
  int N;
  cin >> N;
  for (int i = 0; i < N; i++) {
  if((0 <= i && i < 9 )||( 99 <= i && i < 999 )||( 9999 <= i && i < 99999))
  {
    count++;
  }
}
  cout << count << endl;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

const int MAX = INT_MAX / 10;
int m, n;
int get_hash(vi &v) {
	int n = v.size();
	int ret = 0;
	REP(i,n) {
		ret *= 3;
		ret += v[i];
	}
	return ret;
}
int dfs(vs &o, vi &v, vi &memo) {
	int hash = get_hash(v);
	if (memo[hash] != -1) {
		return memo[hash];
	}
	/*
	cerr << "v:" << endl;
	REP(i,m) {
		cerr << v[i];
	}
	cerr << endl;
	*/
	int cnt = 0;
	vi ok(n, 1);
	REP(i,m) {
//		cerr << i << " --> " << endl;
		if (v[i] != 2) {
			cnt++;
			REP(j,n) {
//				cerr << (v[i] ^ (o[j][i] - '0'));
				if ((v[i] ^ (o[j][i] - '0')) == 1) {
					ok[j] = 0;
				}
			}
//			cerr << endl;
		}
	}
	int ok_cnt = 0;
//	cerr << "ok:" << endl;
	REP(i,n) {
//		cerr << ok[i] << endl;
		if (ok[i]) {
			ok_cnt++;
		}
	}
	if (ok_cnt == 1) {
		/*
		if (cnt == 1) {
			cerr << "AAAAA" << endl;
			REP(i,m) {
				cerr << v[i];
			}
			cerr << "," << ok_cnt << endl;
		}
		*/
		return cnt;
	}
	int ret = MAX;
	REP(i,m) {
		if (v[i] == 2) {
			int tmp = 0;
			REP(j,2) {
				vi nv(v);
				nv[i] = j;
				tmp = max(tmp, dfs(o, nv, memo));
			}
			ret = min(ret, tmp);
		}
	}
	return memo[hash] = ret;
}
int main() {
	while (cin >> m >> n, m | n) {
		vs o(n);
		REP(i,n) {
			cin >> o[i];
		}
		vi v(m, 2);
		vi memo(get_hash(v) + 1, -1);
		cout << dfs(o, v, memo) << endl;
	}
}

Measured memory_bytes: 1956
# 正整数 N が与えられるので、
# 1 以上 N 以下の整数のうち、最も 2 で割れる回数が多いものを求めてください。
n = gets.chomp.to_i

check_num, check_val = 0, 1
(1..n).each do |v|
  next if (v%2) != 0
  
  num, test = 0, v
  while test >  1
   test = test/2
   num += 1
  end
  
  if check_num < num
    check_num = num
    check_val = v 
  end
end

p check_val

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

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;
using lint=long long;

vector<lint> res;

void dfs(vector<int>& a){
	int n=a.size();
	if(n>10) return;

	lint num=0;
	rep(i,n) num=10*num+a[n-i-1];
	if(a[n-1]!=0) res.emplace_back(num);

	rep(d,10) if(abs(a[n-1]-d)<=1) {
		a.emplace_back(d);
		dfs(a);
		a.pop_back();
	}
}

int main(){
	rep(d,10){
		vector<int> a(1,d);
		dfs(a);
	}

	sort(res.begin(),res.end());

	int k; scanf("%d",&k);
	printf("%lld\n",res[k-1]);

	return 0;
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
//typedef vector<vector<ll>> Graph;

const ll mod = 1e9 + 7;
//const ll mod = 998244353;

#define REP(i,n) for(ll i=0;i<(ll)n;i++)
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define spa << " " <<
#define fi first
#define se second

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 S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

template<typename T> void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cerr<<v[i][0];for(ll j=1;j<w;j++)cerr spa v[i][j];cerr<<endl;}};
template<typename T> void debug(vector<T>&v,ll n){if(n!=0)cerr<<v[0];
for(ll i=1;i<n;i++)cerr spa v[i];
cerr<<endl;};

string num2bit(ll num, ll len){
    string bit = "";
    REP(i, len){
    bit += char('0'+(num>>i & 1));
    }
    return bit;
}

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

    char X;
    cin >> X;
    if(X-'a'>=0 and X-'a'<=26) cout << 'a' << endl;
    else cout << 'A' << endl;

    return 0;
}

Measured memory_bytes: 3616
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int>P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-6;
const ld pi = acos(-1.0);
typedef vector<vector<ll>> mat;
typedef vector<ll> vec;

void debug(vec &v) {
	int n = v.size();
	rep(i, n) {
		if (i > 0)cout << " ";
		cout << v[i];
	}
	cout << "\n";
}

int n;
bool e[1000][1000];
int id[1000][1000];
bool ans[200000];


vector<int> G[1000];

vector<int> cG[1000];
bool used[1000];

void dfs(int id) {
	rep(j, cG[id].size()) {
		int to = cG[id][j];
		if (!used[to]) {
			used[to] = true;
			dfs(to);
		}
	}
}

void solve(){
	int m; cin >> n >> m;
	rep(i, n)rep(j, n)id[i][j] = -1;
	vector<int> a(m), b(m);
	rep(i, m) {
		cin >> a[i] >> b[i]; a[i]--; b[i]--;
		id[a[i]][b[i]] = i;
		G[a[i]].push_back(b[i]);
	}
	rep(i, n) {
		queue<int> q;
		q.push(i);
		e[i][i] = true;
		while (!q.empty()) {
			int id = q.front(); q.pop();
			rep(j, G[id].size()) {
				int to = G[id][j];
				if (e[i][to])continue;
				q.push(to);
				e[i][to] = true;
			}
		}
	}
	rep(i, n) {
		rep(j, n)cG[j].clear();
		fill(used, used + n, false);
		used[i] = true;
		rep(j, m) {
			if (a[j] != i)cG[a[j]].push_back(b[j]);
		}
		sort(G[i].begin(), G[i].end());
		vector<int> cnt(G[i].size(),0);
		rep(j, G[i].size()) {
			int to = G[i][j];
			if (used[to])cnt[j]++;
			else dfs(to);

		}
		fill(used, used + n, false);
		used[i] = true;
		per(j, G[i].size()) {
			int to = G[i][j];
			if (used[to])cnt[j]++;
			else dfs(to);

		}
		rep(j, G[i].size()) {
			int to = G[i][j];
			if (cnt[j] < 1 && e[to][i])ans[id[i][to]] = true;
			else if (cnt[j] >= 1 && !e[to][i])ans[id[i][to]] = true;
		}
	}
	rep(i, m) {
		if (ans[i]) {
			cout << "diff" << endl;
		}
		else {
			cout << "same" << endl;
		}
	}
}


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(12);
	//init();
	//int t; cin >> t; rep(i, t)solve();
	solve();
	stop
	return 0;
}


Measured memory_bytes: 11008
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	if((a==b&&b!=c)||(a==c&&b!=c)||(c==b&&a!=c)){
		printf("Yes");
	}
	else printf("No");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define MOD 1000000007
#define ll long long int
#define pi pair <ll,ll>
#define vi vector <ll>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i,a,b) for (int i = a; i < b; i++)
#define SQ(a) (a)*(a)
#define ordered_set tree<ll, null_type,greater_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>       //greater_equal<ll> or less<ll>
// find_by_key()   order_of_key()
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
/*bool comp(string a, string b) {
if (a.size() != b.size()) return a.size() < b.size();
return a < b;
}*/
 
int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    /*freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);*/
    ll i,j,m,l=0,x,prev=0,max1=0,flag=0,cnt=0,y,min1,q,sum=0,r,n,k,p,flag2=0,ind=0,t,a,b,c;
    ll dp[1000004]={0};
    cin>>n;
    if(n==1){
        cout<<0<<endl;
        return 0;
    }
    t=sqrt(n);
    for(i=2;i<=t;i++){
        while(n%i==0){
            dp[i]++;
            n=n/i;
        }
    }
   // cout<<n<<endl;
    if(n!=1){
        cnt+=1;
    }
    for(i=2;i<1000004;i++){
        k=(-1+sqrt(1+(-4)*(-2*dp[i])))/2;
        cnt+=k;
    }
    cout<<cnt<<endl;
    
    return 0;
}

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

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

    int n;
    cin >> n;
    vector<int> A(n), B(n);
    for(int i = 0; i < n; i++){
        cin >> A[i];
        B[i] = A[i];
    }

    sort(A.begin(), A.end());

    int d = 0;
    for(int i = 0; i < n; i++){
        if(A[i] != B[i]) d++;
    }

    if(d <= 2) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <climits>
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define srep(i, begin, end) for (__typeof(end) i = begin; i != end; i++)
#define si(x) int x = scanInt();
#define sll(x) LL x = scanLong();
#define sci(x) int x; scanf("%d", &x);
#define scll(x) LL x; scanf("%lld", &x);
#define pi(x) printf("%d ", x)
#define pll(x) printf("%lld ", x)
#define nl printf("\n")
#define clr(a) memset(a, 0, sizeof(a))
#define PB push_back
#define MP make_pair
using namespace std;
typedef unsigned int UI; // 32 bit integer
typedef long int LI; // 32 bit integer
typedef unsigned long int ULI; // 32 bit unsigned integer
typedef long long int LL; // 64 bit integer
typedef unsigned long long int ULL; // 64 bit unsigned integer
typedef long double LD;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef deque<int> DI;
typedef deque<LL> DLL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const LL MOD = 1e9+7;

/* Fast I/O */
inline int scanInt() {
	int n = 0;
	char ch = getchar();
	int sign = 1;
	while(ch < '0' || ch > '9') {
		if(ch == '-')	sign = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		n = (n<<1)+(n<<3)+(int)(ch-'0');
		ch = getchar();
	}
	return n*sign;
}

inline LL scanLong() {
	LL n = 0;
	char ch = getchar();
	LL sign = 1;
	while(ch < '0' || ch > '9') {
		if(ch == '-')	sign = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		n = (n<<1)+(n<<3)+(LL)(ch-'0');
		ch = getchar();
	}
	return n*sign;
}

int main() {
	sll(a); sll(b);
	if(a <= 5)	puts("0");
	else if(a <= 12)	pll(b/2);
	else	pll(b);
}


Measured memory_bytes: 256
#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() {
    int d,t,s;
    cin >> d >> t >> s;
 
    if(t*s>=d) cout << "Yes" << endl;
    else cout << "No" << endl;
 
    return 0;
}

Measured memory_bytes: 3616
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
 #define int long long

#define all(X) (X).begin(), (X).end()
#define reset(X) memset(X, 0, sizeof(X))
#define mp(a, b) make_pair(a, b)
#define pb push_back
#define endl '\n'
#define fi first
#define se second



using namespace __gnu_pbds;
using namespace std;
// const int mod=1e9+7;
 const int mod=998244353;
 // const int mod=1e9+9;
const int INF=4e18+10;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define read(n) int n; cin>>n;
#define readv(x, n) vector<int> x(n); for(auto &i:x) cin>>i; 
int multiply(int a, int b, int in_mod){return (a*b)%in_mod;} 
int mult_identity(int a){return 1;}


auto power(auto a, int b, int in_mod)
{
    auto prod=mult_identity(a);
    auto mult=a%in_mod;
    while(b!=0)
    {
        if(b%2)
        {
            prod=multiply(prod,mult, in_mod);

        }
        mult=multiply(mult, mult,in_mod);
        b/=2;
    }
    return prod;
}
int mod_inv(int q, int in_mod)
{

    return power(q, in_mod-2,in_mod);
}


const int MAXN=5e5+10;
vector<int> fac(MAXN);
vector<int> infac(MAXN);
void build_factorial()
{
    fac[0]=1;
    infac[0]=1;
    for(int i=1;i<MAXN;i++)
    {
        fac[i]=(fac[i-1]*i)%mod;
        infac[i]=mod_inv(fac[i], mod);
    }
}


void solve()
{ 
    build_factorial();
    int n, m, k;
    cin>>n>>m>>k;   

    int ans=0;
    for(int i=0;i<=k;i++)
    {
        int calc = fac[n-1]*infac[i]%mod *infac[n-i-1]%mod;
        calc = calc*power(m-1,n-i-1, mod)%mod*m%mod;;
        ans= (ans+calc)%mod;
    }
    cout<<ans<<endl;
}

signed main()

{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  
    cout.tie(NULL);
    #ifndef ONLINE_JUDGE
    if(fopen("INPUT.txt","r"))
    {
        freopen ("INPUT.txt" , "r" , stdin);
        freopen ("OUTPUT.txt" , "w" , stdout);
    }
    #endif
    auto clk=clock(); 
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    // -------------------------------------Code starts here---------------------------------------------------------------------     

    int t=1;
    // cin>>t;
    for(int test=1;test<=t;test++)
    {
        // cout<<"Case #"<<test<<": ";
        solve();
        // cout<<endl;

    }

    // -------------------------------------Code ends here------------------------------------------------------------------


    clk = clock() - clk;
    cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << "\n";
    return 0;
}


Measured memory_bytes: 10976
a = [list(map(int, input().split())) for _ in range(3)]
s = [[False] * 3 for _ in range(3)]
n = int(input())
for _ in range(n):
    b = int(input())
    for i in range(3):
        for j in range(3):
            if b == a[i][j]: s[i][j] = True

for i in range(3):
    if all(s[i]) or (s[0][i] and s[1][i] and s[2][i]):
        print("Yes")
        break
else:
    if all([s[i][i] for i in range(3)]) or all([s[i][2-i] for i in range(3)]):
        print("Yes")
    else: print("No")


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

#define FOR(i, a, b) for (int i = a; (i) < (b); ++(i))
#define REP(i, n) FOR(i, 0, n)

using namespace std;

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

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

using ll = long long;
using ld = long double;

#define ALL(x) (x).begin(), (x).end()
template<class T>
using vc = vector<T>;
using vi = vc<int>;
using vvi = vc<vi>;

template<class T>
using va = valarray<T>;
using vad = va<ld>;

vi Read(ll n) {
    auto      v = vi(n);
    for (auto i = std::size_t(0); i < n; ++i) {
        cin >> v[i];
    }
    return v;
}

template <class T>
void Dump(const T& A){
    REP(i, A.size() - 1) cout << A[i] << " ";
    cout << A[A.size() - 1] << "\n";
}

void insertionSort(vi& A, int N){
    FOR(i, 1, N){
        Dump(A);
        const auto v = A[i];
        auto j = i - 1;
        while (j >= 0 && A[j] > v){
            A[j+1] = A[j];
            --j;
        }
        A[j+1] = v;
    }
}

int main() {
    int N;
    cin >> N;
    auto A = Read(N);

    insertionSort(A, N);
    Dump(A);
}



Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using ull = unsigned long long;
//#define int ll
using vb = vector<bool>; using vvb = vector<vb>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
template<class T> using V = vector<T>;
template<class T> using VV = vector<V<T>>;
#define fi first
#define se second
#define maxs(x,y) (x=max(x,y))
#define mins(x,y) (x=min(x,y))
using pii = pair<int,int>; using pll = pair<ll,ll>;
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(ll i = (ll)(b)-1;i >= a;--i)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define eb(val) emplace_back(val)
const double PI = acos(-1), EPS = 1e-10;
const ll MOD = 1e9+7;
template<class T> istream& operator>>(istream &is,vector<T> &st){
  for(size_t i=0;i<st.size();++i) is >> st[i];
  return is;
}
template<class T> istream& operator>>(istream &is,vector<vector<T>> &st){
  for(size_t i=0;i<st.size();++i) is >> st[i];
  return is;
}
template<class T> ostream& operator<<(ostream &os, const vector<T> &st){
  for(size_t i=0;i<st.size();++i){
    if(i==st.size()-1) os << st[i];
    else os << st[i] << " ";
  }
  return os;
}
template<class T> ostream& operator<<(ostream &os, const vector<vector<T>> &st){
  for(size_t i=0;i<st.size();++i){
    os << st[i];
    if(i!=st.size()-1) os << endl;
  }
  return os;
}
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  V<pii> a(n);
  REP(i,n){
    cin >> a[i].se >> a[i].fi;
  }
  sort(ALL(a));
  ll t = 0;
  REP(i,n){
    if((t+=a[i].se)>a[i].fi){
      puts("No");
      return 0;
    }
  }
  puts("Yes");
}


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

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

const string YES = "Yes";
const string NO = "No";

void func(std::vector<std::vector<long long>> A, long long N, std::vector<long long> b){
    std::vector<std::vector<int>> Bingo(3, std::vector<int>(3));
    for (auto b_num : b) {
        rep(i,3) {
            rep(j,3) {
                if (A[i][j] == b_num) {
                    Bingo[i][j] = 1;
                }
            }
        }
    }
    bool bingo = false;
    if (Bingo[0][0] + Bingo[0][1] + Bingo[0][2] == 3) bingo = true;
    if (Bingo[1][0] + Bingo[1][1] + Bingo[1][2] == 3) bingo = true;
    if (Bingo[2][0] + Bingo[2][1] + Bingo[2][2] == 3) bingo = true;
    if (Bingo[0][0] + Bingo[1][0] + Bingo[2][0] == 3) bingo = true;
    if (Bingo[0][1] + Bingo[1][1] + Bingo[2][1] == 3) bingo = true;
    if (Bingo[0][2] + Bingo[1][2] + Bingo[2][2] == 3) bingo = true;
    if (Bingo[0][0] + Bingo[1][1] + Bingo[2][2] == 3) bingo = true;
    if (Bingo[0][2] + Bingo[1][1] + Bingo[2][0] == 3) bingo = true;

    cout << (bingo? YES:NO) << endl;
}

int main(){
    // cout << fixed << setprecision(5);

    std::vector<std::vector<long long>> A(3, std::vector<long long>(3));
    for(int i = 0 ; i < 3 ; i++){
        for(int j = 0 ; j < 3 ; j++){
            scanf("%lld",&A[i][j]);
        }
    }
    long long N;
    scanf("%lld",&N);
    std::vector<long long> b(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&b[i]);
    }
    func(std::move(A), N, std::move(b));
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main()
{
int in,a,b,c,i;
a=b=c=0;
for(i=0;i<10;i++){
    scanf("%d",&in);
if(in>a)
{
	int t=a;
a=in;
in =t;
}
if(in>b)
{int t=b;
b=in;
in =t;}
if(in>c)
{int t=c;
c=in;
in =t;
}
}
printf("%d\n%d\n%d\n",a,b,c);
return 0;
}

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

int N,K;
set<int> G[500];

int main(){
  cin>>N>>K;
  for(int i=0;i<K;i++){
    for(int j=0;j<N/2;j++){
      int k;
      cin>>k;
      k--;
      G[i].insert(k);
    }
  }
  vector<int> t(N);
  for(int i=0;i<N;i++)t[i]=i;
  int cc=0;
  while(cc<1000000){
    cc+=N;
    random_shuffle(t.begin(),t.end());
    vector<int> sum(K,0);
    for(int i=0;i<N/2;i++){
      int id=t[i];
      for(int j=0;j<K;j++){
        sum[j]+=G[j].count(id);
      }
    }
    int mini=1e9,maxm=0;
    for(int i=0;i<K;i++){
      mini=min(mini,sum[i]);
      maxm=max(maxm,sum[i]);
    }
    if(N/8<=mini&&maxm<=N/8*3){
      vector<int> ans(N,0);
      for(int i=0;i<N/2;i++)ans[ t[i] ]=1;
      for(int i=0;i<N;i++)cout<<ans[i];
      cout<<endl;
      break;
    }
  }
  return 0;
}

Measured memory_bytes: 14840
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>

using namespace std;
#define int long long int
const int INF = 1001001001001001LL;
const int MOD = 1000000007;


int plus(int, int, vector<vector<char> > &);
int dot(int, int, vector<vector<char> > &);



int f(int i, int j, vector<vector<char> > &a, int op){
        
    
    if(op == 0){
    int ret = 0;
    int e = 0;
    while(a[i][j] != 'Z'){
        
        
        if(a[i][j] == '+') ret += f(i + 1, j + 1, a, 0);
        else if(a[i][j] == '*') ret += f(i + 1, j + 1, a, 1);
        else if(a[i][j] == '.') ret += e;
        else ret += a[i][j] - '0';
        i++;
    }
    return ret;
    }else{

    int ret = 1;
    int e = 1;
    while(a[i][j] != 'Z'){
        if(a[i][j] == '+') ret *= f(i + 1, j + 1, a, 0);
        else if(a[i][j] == '*') ret *= f(i + 1, j + 1, a, 1);
        else if(a[i][j] == '.') ret *= e;
        else ret *= a[i][j] - '0';
        i++;
    }

    return ret;
    }
}

int calc(int i, int j, vector<vector<char> > &a){
    
    if(a[i][j] == '+') return f(i + 1, j + 1, a, 0);
    else if(a[i][j] == '*') return f(i + 1, j + 1, a, 1);
    else return a[i][j] - '0';
}


signed main(){
    
    while(1){
        int n; cin >> n;
        if(!n) break;
        vector<vector<char> > a(n + 1, vector<char> (15, 'Z'));

        for(int i = 0; i < n; i++){
            string s; cin >> s;
            for(int j = 0; j < (int)s.size(); j++){
                a[i][j] = s[j];
            }
        }
        
        
        cout << calc(0, 0, a) << endl;


    }
    return 0;
}



Measured memory_bytes: 3052
n = input()

a, b = map(int, raw_input().split()), [abs(x - (n - x - 1)) for x in xrange(n)]
a.sort()
b.sort()
if a != b:
	print '0'
	exit(0)

n >>= 1
s, e = 1, 2
MOD = 10 ** 9 + 7
while n > 0:
	if (n & 1) == 1:
		s = s * e % MOD
	e = e * e % MOD
	n >>= 1
print s


Measured memory_bytes: 11328
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
use {
    proconio::{marker::*, *},
    std::{cmp::*, collections::*, mem::*},
};
fn main() {
    input! {//
        mut s:Chars,
    }
    let n = s.len();
    let mut prevaCnt = 0i64;
    let mut ans = 0i64;
    let mut i = 0usize;
    loop {
        if i + 2 >= n {
            break;
        }
        if s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C' {
            ans += 1;
            ans += prevaCnt;
            i += 2;
            if i < n {
                s[i] = 'A';
            } else {
                break;
            }
        } else {
            if s[i] == 'A' {
                prevaCnt += 1;
            } else {
                prevaCnt = 0;
            }
            i += 1;
        }
        if i + 2 >= n {
            break;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 2980
import numpy as np

class SieveOfEratosthenes:
    def __init__(self, V):
        self.is_prime = np.ones(V + 1, dtype=bool)
        self.is_prime[4::2] = False
        self.is_prime[9::3] = False
        self.is_prime[25::5] = False
        self.primes = [2, 3, 5]
        for i in range(7, V + 1, 2):
            if self.is_prime[i]:
                self.primes.append(i)
                if i * i < V + 1:
                    self.is_prime[i * i::i] = False
    
    def factorize(self, x):
        assert x >= 1
        if x == 1:
            return [(1, 1)]
        result = []
        for p in self.primes:
            exp = 0
            while x % p == 0:
                exp += 1
                x = x // p
            if exp > 0:
                result.append((p, exp))
            if p * p > x:
                break
        if x > 1:
            result.append((x, 1))
        return result


N = int(input())
M = 10**9 + 7
A = list(map(int, input().split()))

sieve = SieveOfEratosthenes(10**3)
F = [dict(sieve.factorize(a)) for a in A]

lcm = F[0]
for i in range(1, len(F)):
    for p, e in F[i].items():
        if p in lcm:
            lcm[p] = max(lcm[p], e)
        else:
            lcm[p] = e

val = 1
for p, e in lcm.items():
    val = val * pow(p, e, M) % M
# print(val)

B = [val * pow(a, M - 2, M) % M for a in A]
print(sum(B) % M)
    

Measured memory_bytes: 30588
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define PI acos(-1)
#define EPS 1e-5
#define sz(v) ((int)(v).size())
#define all(v) v.begin(),v.end()
#define forn(i, n) for(ll i=0;i<(ll)n;i++)
#define fi first
#define se second
 

int main() {
	set<string> ss;
	int n;
	cin >> n;
	forn(i, n) {
		string s;
		cin >> s;
		ss.insert(s);
	}
	cout << sz(ss) << endl;
	return 0;
}



Measured memory_bytes: 19152
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define int int64_t
#define double long double
#define rep(i, N) for(int i=0; i<N; i++)
#define repr(i, N) for(int i=N-1; i>=0; --i)
#define all(v) v.begin(),v.end() 
using namespace std;
//using pr = pair<int, int>;
using tup  = tuple<int, int, int>;
using vec  = vector<int>;
using vvec = vector<vec>;

//プロトタイプ宣言
//int myfunc(int, vvec);

//グローバル変数
//int N, M;
//vvec data(N, vec(M));

//関数：
int gcd(int mx, int mn) {
	if(mn == 0) return(mx);
	else gcd(mn, mx%mn);
}

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

	int n; cin >> n;
	int m;
	if(n%2 == 1) m = n/2;
	else m = n/2 - 1;
	
	cout << m << endl;
	return 0;
}
//std::string str;
//str = std::to_string(int i);
//bitset<3> s(N);
//int ans = (char)grid - '0';

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

#ifdef DEBUG
void debug() { cerr << "\n"; }
template <class T> void debug(const T &x) { cerr << x << "\n"; }
template <class T, class... Args> void debug(const T &x, const Args &... args) {
    cerr << x << " ";
    debug(args...);
}
template <class T> void debugVector(const vector<T> &v) {
    for(const T &x : v) {
        cerr << x << " ";
    }
    cerr << "\n";
}
#else
template <class T, class... Args>
void debug(const T &x, const Args &... args) {}
template <class T> void debugVector(const vector<T> &v) {}
#endif

using ll = long long;
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
constexpr int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int ans;
    if(s == "RRR") {
        ans = 3;
    } else if(s == "SSS") {
        ans = 0;
    } else if(s == "SRR" || s == "RRS") {
        ans = 2;
    } else {
        ans = 1;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3600
using System;
using System.Linq;

public class AtCoder_153_E
{
    public static void Main()
    {
        //var exStdIn = new System.IO.StreamReader("input.txt");
        //System.Console.SetIn(exStdIn);

        int[] lines = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
        int h = lines[0];
        int n = lines[1];

        int[] a = new int[n];
        int[] b = new int[n];

        int[] mps = new int[10001];
        for (int i = 0; i < mps.Length; i++)
        {
            mps[i] = 100000001;
        }

        for (int i = 0; i < n; i++)
        {
            int[] line = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            a[i] = line[0];
            b[i] = line[1];
        }

        mps[0] = 0;
        for (int i = 0; i <= h; i++)
        {
            for (int j = 0; j < n; j++)
            {
                int prev = Math.Max(0, i - a[j]);
                mps[i] = Math.Min(mps[prev] + b[j], mps[i]);
            }
        }

        Console.WriteLine(mps[h]);
    }
}


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

using namespace std;

#define fastio cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(0)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> matrix;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(c) c.begin(),c.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
const int MAX = 1e6+1;
const int INF = 0x3f3f3f3f;

int n;

int main(){
	fastio;
	int a, b;

	cin>> a>> b;

	if(1 <= a && a<=9 && 1<= b && b<=9) cout<< a*b<< endl;
	else cout << -1<< endl;

	return 0;
}


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

// 1 <= a <= n 
// a - [a / b] * b >= K

int main() {
    int n, K;
    scanf("%d%d", &n, &K);
    LL ret = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= n; j += i) {
            ret += min(j + i, n + 1) - min(min(j + i, n + 1), j + K);
        }
    }
    if (K == 0) ret -= n;
    return printf("%lld\n", ret), 0;
}

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

int a[114][514];

int main() {
	int w, h,n;
	cin >> w >> h>>n;
	for (int b = 0; b < n; b++) {
		int x, y, d;
		cin >> x >> y >> d;
		if (d == 1) {
			a[0][0]++;
			a[x][0]--;
			a[0][h]--;
			a[x][h]++;
		}
		if (d == 2) {
			a[x][0]++;
			a[x][h]--;
			a[w][0]--;
			a[w][h]++;
		}
		if (d == 3) {
			a[0][0]++;
			a[0][y]--;
			a[w][0]--;
			a[w][y]++;
		}
		if (d == 4) {
			a[0][y]++;
			a[0][h]--;
			a[w][0]--;
			a[w][h]++;
		}
	}
	for (int i = 0; i <= w; i++) {
		for (int j = 0; j <= h; j++) {
			a[i + 1][j] += a[i][j];
		}
	}
	for (int i = 0; i <= w; i++)
		for (int j = 0; j <= h; j++)a[i][j + 1] += a[i][j];
	int ans = 0;
	for (int i = 0; i < w; i++) {
		for (int j = 0; j < h; j++) {
			if (!a[i][j])ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 384
n = int(input())
suretsu = list(map(int,input().split()))

wa = 0
minimum = suretsu[0]
maximum = suretsu[0]

for i in range(n):
    wa += suretsu[i]
    if suretsu[i] > maximum:
        maximum = suretsu[i]
    if suretsu[i] < minimum:
        minimum = suretsu[i]
    
print (minimum,maximum,wa)

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

int main(){
  int n,m,ans=0; cin>>n>>m;
  vector<int> num(n,1);
  vector<bool>  flag(n,false);
  flag[0]=true;
  for(int i=0;i<m;i++){
    int a,b; cin>>a>>b;
    a--; b--;
    if(flag[a]){
      flag[b]=true;
    }
    num[a]--; num[b]++;
    if(num[a]==0){
      flag[a]=false;
    }
  }
  for(int i=0;i<n;i++){
    if(num[i]>0 && flag[i]){
      ans++;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 640
n = int(input())
l=list(map(int,input().split()))
d={}
s=0
for i in range(n):
    s+=l[i]
    if (l[i] in d):
        d[l[i]]+=1
    
    else:
        d[l[i]]=1
    
k = int(input())
for j in range(k):
    a,b=(map(int,input().split()))
    if a in d:
        s=s-d[a]*a+d[a]*b
        if b in d:
            d[b]+=d[a]
        else:
            d[b]=d[a]
        d.pop(a)
        print(s)
    else:
        print(s)



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

int main(){
  int a[3];
  for(int i=0;i<3;i++) cin >> a[i];
  sort(a,a+3);
  if(a[0] == 5 && a[1] == 5 && a[2] == 7) cout <<"YES"<<endl;
  else cout << "NO" << endl;
}
  


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

int s(int n) {
	if (n == 0) return 0;
	return n % 10 + s(n / 10);
}

int main() {
    
	int n;
	cin >> n;
	if (n % s(n)) {
		cout << "No" << endl;
	}
	else {
		cout << "Yes" << endl;
	}
	
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip> // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple> // get<n>(xxx)
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set> // S.insert(M);
// if (S.find(key) != S.end()) { }
// for (auto it=S.begin(); it != S.end(); it++) { }
// auto it = S.lower_bound(M);
#include <random> // random_device rd; mt19937 mt(rd());
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib> // atoi(xxx)
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.
// insert #if<tab> by my emacs. #if DEBUG == 1 ... #end

typedef long long ll;

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

// const int C = 1e6+10;
// const ll M = 1000000007;

int N, K;
ll a[100];

int main () {
  cin >> N >> K;
  for (auto i = 0; i < N; ++i) {
    cin >> a[i];
  }
  ll res = 100000000000000;
  for (auto i = 0; i < (1 << N); ++i) {
    int cnt = 0;
    for (auto j = 0; j < N; ++j) {
      if (((i >> j) & 1) == 1) ++cnt;
    }
    if (cnt == K) {
      ll now = 0;
      ll ans = 0;
      for (auto j = 0; j < N; ++j) {
        if (((i >> j) & 1) == 1) {
          if (now < a[j]) {
            now = a[j];
          } else {
            ans += now + 1 - a[j];
            ++now;
          }
        } else {
          now = max(now, a[j]);
        }
      }
      res = min(ans, res);
    }
  }
  cout << res << endl;
}


Measured memory_bytes: 256
n = int(input())
h = list(map(int, input().split()))
hmax = max(h)
ans = 0
f = False

for i in range(1, hmax+1):
    for j in range(n):
        if f and (h[j] < i):
            ans += 1
        f = h[j] >= i
    if f:
        ans += 1
    f = False

print(ans)


Measured memory_bytes: 9176
#include <cstdio>
#include <cstdlib>

int w,h,n;
int main(void){
	scanf("%d%d%d",&w,&h,&n);
	
	int ma,mb,a,b,c;
	int ans=0;
	scanf("%d%d",&ma,&mb);
	for(int i=0;i<n-1;i++){
		scanf("%d%d",&a,&b);
		if((a-ma)*(b-mb)>0){
			if(a-ma>0){
				c=(a-ma<b-mb)?(a-ma):(b-mb);
				ans+=c;
				ma+=c;mb+=c;
			}
			else{
				c=(ma-a<mb-b)?(ma-a):(mb-b);
				ans+=c;
				ma-=c;mb-=c;
			}
		}
		
		ans+=abs(ma-a);
		ans+=abs(mb-b);
		ma=a;
		mb=b;
	}
	
	printf("%d\n",ans);
	return 0;
}

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

ll N, M;
vector<ll> k, p;
vector<vector<ll>> s;

bool light(int bit, int a) {
  ll res = 0;
  for (int j = 0; j < k[a]; j++) {
    if (bit & (1 << s[a][j])) {
      res++;
    }
  }
  if (res % 2 == p[a]) {
    return true;
  } else {
    return false;
  }
}

void solve() {
  ll cnt, res = 0;
  for (ll bit = 0; bit < (1 << N); bit++) {
    cnt = 0;
    for (int i = 0; i < M; i++) {
      if (light(bit, i)) {
        cnt++;
      }
    }
    if (cnt == M) {
      res++;
    }
  }
  cout << res << "\n";
}

int main() {
  cin >> N >> M;
  k.resize(M);
  s.resize(M, vector<ll>(N));
  p.resize(M);
  for (int i = 0; i < M; i++) {
    cin >> k[i];
    for (int j = 0; j < k[i]; j++) {
      cin >> s[i][j];
      s[i][j]--;
    }
  }
  for (int i = 0; i < M; i++) {
    cin >> p[i];
  }
  solve();
  return 0;
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.stream.IntStream;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        DWall solver = new DWall();
        solver.solve(1, in, out);
        out.close();
    }

    static class DWall {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int h = in.nextInt(), w = in.nextInt();
            int[][] c = new int[10][];
            for (int i = 0; i < 10; i++) {
                c[i] = IntStream.range(0, 10).map(x -> in.nextInt()).toArray();
            }

            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < 10; j++) {
                    for (int k = 0; k < 10; k++) {
                        c[j][k] = Math.min(c[j][k], c[j][i] + c[i][k]);
                    }
                }
            }

            long ans = 0;
            for (int i = 0; i < h * w; i++) {
                int a = in.nextInt();
                if (a >= 0) {
                    ans += c[a][1];
                }
            }
            out.println(ans);
        }

    }
}



Measured memory_bytes: 47940
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
<url:https://agc019.contest.atcoder.jp/tasks/agc019_b>
問題文============================================================
 英小文字からなる文字列 A=A1A2…An があります。
 
 あなたは 1≤i≤j≤n であるような任意の二つの添字 i,j を選び、
 A のうち部分文字列 AiAi+1…Aj を反転することができます。
 
 この操作は一回まで行うことができます。
 
 これによって得られる文字列は何通りあるでしょうか？
=================================================================

解説=============================================================

================================================================
*/
ll solve(){
    ll ret = 1;
    string S; cin >> S;
    int alpha[26] = {};
    for(int i = (int)S.length()-1; i >= 0;i--){
        for(int j = 0; j < 26;j++){
            if(j == S[i]-'a')continue;
            ret += alpha[j];
        }
        alpha[S[i]-'a']++;
    }
    return ret;
}
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    cout << solve() << endl;
	return 0;
}


Measured memory_bytes: 720
#coding: utf-8
N, K = (int(n) for n in input().split())
A = [int(n) for n in input().split()]

def is_ok(X):
    ret = 0
    for log in A:
        ret += -(-log//X) - 1
    return ret <= K

def meguru_bisect(ng, ok):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

print(meguru_bisect(0, max(A)+1))


Measured memory_bytes: 30820
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <assert.h>
#include <stack>
#include <ctype.h>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

const ll MOD = 1e+9 + 7;
char str[1000010];

stack<char> cst;
stack<pair<int, int> > nst;
void calc() {
  ll t = nst.top().first;
  ll f = nst.top().second;
  nst.pop();
  while (true) {
    char c = cst.top();
    cst.pop();
    if (c == '(') {
      break;
    } else if (c == '~') {
      swap(t, f);
    } else if (c == '&') {
      ll nt = t * nst.top().first % MOD;
      ll nf = ((t + f) * (nst.top().first + nst.top().second) - nt + MOD) % MOD;
      t = nt;
      f = nf;
      nst.pop();
    } else if (c == '|') {
      ll nf = f * nst.top().second % MOD;
      ll nt = ((t + f) * (nst.top().first + nst.top().second) - nf + MOD) % MOD;
      t = nt;
      f = nf;
      nst.pop();
    }
  }
  nst.push(make_pair(t, f));
}

int main() {
  while (scanf("%s", str) > 0) {
    while (!cst.empty()) { cst.pop(); }
    while (!nst.empty()) { nst.pop(); }
    int pos = 0;
    cst.push('(');
    cst.push('(');
    cst.push('(');
    cst.push('(');
    while (str[pos]) {
      char c = str[pos];
      if (c == '(') {
        cst.push(c);
        cst.push(c);
        cst.push(c);
        cst.push(c);
      } else if (c == '&') {
        calc();
        cst.push(c);
        cst.push('(');
      } else if (c == '|') {
        calc();
        calc();
        cst.push(c);
        cst.push('(');
        cst.push('(');
      } else if (c == ')') {
        calc();
        calc();
        calc();
        calc();
      } else if (c == '~') {
        cst.push(c);
      } else if (c == 'x') {
        nst.push(make_pair(1, 1));
      } else {
        assert(isdigit(c));
      }
      pos++;
    }
    calc();
    calc();
    calc();
    calc();
    printf("%d\n", nst.top().first);
  }
}

Measured memory_bytes: 3660