akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        StringBuilder sb = new StringBuilder();
        HashSet<String> hashSet = new HashSet<>();
        for (int i = 0; i < n; i++) {
            String sp = bf.readLine();
            if (sp.charAt(0)=='i'){
                hashSet.add(sp.substring(7));
            }else {
               sb.append(hashSet.contains(sp.substring(5))?"yes\n":"no\n");
            }
        }
        bf.close();
        System.out.print(sb.toString());
    }
}


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

using namespace std;

#define LL long long
#define u64 unsigned long long
#define u32 unsigned int
#define reg register
#define Raed Read
#define debug(x) cerr<<#x<<" = "<<x<<endl;
#define rep(a,b,c) for(reg int a=(b),a##_end_=(c); a<=a##_end_; ++a)
#define ret(a,b,c) for(reg int a=(b),a##_end_=(c); a<a##_end_; ++a)
#define drep(a,b,c) for(reg int a=(b),a##_end_=(c); a>=a##_end_; --a)
#define erep(i,x) for(reg int i=Head[x]; i; i=Nxt[i])

inline int Read() {
	int res = 0, f = 1;
	char c;
	while (c = getchar(), c < 48 || c > 57)if (c == '-')f = 0;
	do res = (res << 3) + (res << 1) + (c ^ 48);
	while (c = getchar(), c >= 48 && c <= 57);
	return f ? res : -res;
}

template<class T>inline bool Min(T &a, T const&b) {
	return a > b ? a = b, 1 : 0;
}
template<class T>inline bool Max(T &a, T const&b) {
	return a < b ? a = b, 1 : 0;
}

const int N=505,M=1e5+5,mod=1e9+7;

bool MOP1;

int A[N];

struct node {
	int v,p;
	bool operator<(node _)const {
		return v>_.v;
	}
};


priority_queue<node>Q;

int V[N];

bool MOP2;

inline void _main(void) {
	int n=Read(),k=Read(),Sum=0,Ans=0;
	rep(i,1,n)A[i]=Read(),Sum+=A[i];
	for(reg int i=1; i*i<=Sum; i++)if(Sum%i==0) {
			while(!Q.empty())Q.pop();
			int t=0,v=0,r;
			rep(j,1,n)r=A[j]/i,Q.push((node)<%A[j]-r*i,j%>),V[j]=(r+1)*i-A[j],v+=V[j];
			rep(i,1,n) {
				t+=Q.top().v,v-=V[Q.top().p];
				Q.pop();
				if(t==v)break;
			}
			if(t<=k)Max(Ans,i);
			while(!Q.empty())Q.pop();
			t=0,v=0,r;
			int q=Sum/i;
			rep(j,1,n)r=A[j]/q,Q.push((node)<%A[j]-r*q,j%>),V[j]=(r+1)*q-A[j],v+=V[j];
			rep(i,1,n) {
				t+=Q.top().v,v-=V[Q.top().p];
				Q.pop();
				if(t==v)break;
			}
			if(t<=k)Max(Ans,q);
		}
	cout<<Ans;
}

signed main() {
#define offline1
#ifdef offline
	freopen("chessboard.in", "r", stdin);
	freopen("chessboard.out", "w", stdout);
	_main();
	fclose(stdin);
	fclose(stdout);
#else
	_main();
#endif
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
const char nl = '\n';
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> pt;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 101, K = 1e5+10;
inline char get() {
	static char buf[10000], *S = buf, *T = buf;
	if (S == T) {
		T = (S = buf) + fread(buf, 1, 10000, stdin);
		if (S == T) return EOF;
	}
	return *S++;
}
inline void read(int &x) {
	static char c; x = 0; int sgn = 0;
	for (c = get(); c < '0' || c > '9'; c = get()) if (c == '-') sgn = 1;
	for (; c >= '0' && c <= '9'; c = get()) x = x * 10 + c - '0';
	if (sgn) x = -x;
}

int n, k;
int a[N];
bool dp[K];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  read(n); read(k);
  for (int i = 0; i < n; i++) {
    read(a[i]);
  }
  for (int i = 1; i <= k; i++) {
    for (int j = 0; j < n; j++) {
      if (a[j] > i) continue;
      if (!dp[i-a[j]]) {
        dp[i] = 1;
        break;
      }
    }
  }
  puts(dp[k] ? "First" : "Second");
  return 0;
}


Measured memory_bytes: 384
#include <stdio.h>
#include <string.h>

int main(){
	char s[11];
	int ans = 1;
	scanf("%s", s);

	if (s[0] != 'A') {
		ans = 0;
	}
	int coutC = 0;
	for (int i = 2; i < strlen(s) - 1; ++i) {
		if (s[i] == 'C') {
			++coutC;
		}
	}
	if (coutC != 1) {
		ans = 0;
	}
	for (int i = 0; i < strlen(s); ++i) {
		if (s[i] != 'A' && s[i] != 'C') {
			if (s[i]  <=90) {
				ans = 0;
			}
		}
	}

	printf(ans ? "AC" : "WA");

	return 0;
}

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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using pll = pair<ll,ll>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define REV(x) reverse(ALL((x)))
#define ASC(x) sort(ALL((x)))
#define DESC(x) ASC((x)); REV((x))
#define pb push_back
#define eb emplace_back

int main()
{
    ll N, M;
    cin >> N >> M;
    vector<pll> P(N);
    REP(i,0,N) cin >> P[i].first >> P[i].second;

    ASC(P);
    ll cnt = M, sum = 0;
    REP(i,0,N) {
        if(cnt >= P[i].second) {
            cnt -= P[i].second;
            sum += P[i].second * P[i].first;
        }
        else {
            sum += cnt * P[i].first;
            break;
        } 
    }
    PR(sum);

    return 0;
}

/*



*/

Measured memory_bytes: 4756
export const Main = function (input: Array<Array<string>>) {
  const N = parseInt(input[0][0]);
  const S = input[1][0]
  const Z = 'Z'.charCodeAt(0);
  let ans = ''
  for (let i = 0; i < S.length; i++) {
    let charcode = S.charCodeAt(i);
    charcode += N;
    if (charcode > Z) {
      charcode -= 26
    }
    ans += String.fromCharCode(charcode);
  }
  console.log(ans)
}
const parseInput = (input: string) => {
  const lines = input.split("\n");
  if (lines[lines.length - 1] === "") lines.pop();
  return lines.map((el) => (el.split(" ")));
}

Main(parseInput(require("fs").readFileSync("/dev/stdin", "utf8")));


Measured memory_bytes: 9292
#import sys
#input = sys.stdin.readline
def main():
    A, B, K = map( int, input().split())
    if A >= K:
        print(A-K, B)
        return
    K -= A
    if B >= K:
        print(0, B-K)
        return
    print(0, 0)
if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;

int main(void) {
  ll N, Q;
  ll tot;
  cin >> N >> Q;
  map<ll, ll> down, right;
  down[N] = N;
  right[N] = N;
  tot = (N - 2) * (N - 2);
  for (int i = 0; i < Q; i++) {
    ll t, x;
    cin >> t >> x;
    if (t == 1) {  // go vertical
      map<ll, ll>::iterator it = right.lower_bound(x);
      ll len = it->second - 1;
      tot -= (len - 1);
      if (down.find(len) != down.end()) {
        down[len] = min(down[len], x);
      } else {
        down[len] = x;
      }
    } else {  // go horizontal
      map<ll, ll>::iterator it = down.lower_bound(x);
      ll len = it->second - 1;
      tot -= (len - 1);
      if (right.find(len) != right.end()) {
        right[len] = min(right[len], x);
      } else {
        right[len] = x;
      }
    }
  }
  cout << tot << endl;
  return 0;
}

Measured memory_bytes: 9436
#include<stdio.h>
main()
{
	int t,a,b,c,d;
	while(~scanf("%d%d%d%d",&a,&b,&c,&d))
	{
		if(a>d||b<c)
		t=0;
		else 
		{
			if(b>d)
			{
				if(a>c)
				t=d-a;
				else
				t=d-c;
			}
			else
			{
				if(a>c)
				t=b-a;
				else
				t=b-c;
			}
		}
		printf("%d\n",t);
	}
}

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

vector<vector<int>> GetAdjacencyList(int n, int m)
{
	vector<vector<int>> al(n);
	for (int i = 0; i < m; i++) {
		int s, t;
		cin >> s >> t;
		al[s].push_back(t);
		al[t].push_back(s);
	}
	return al;
}

void BFS(int i, const vector<vector<int>>& al, vector<int>& group)
{
	queue<int> q;
	q.push(i);
	group[i] = i + 1;
	while (!q.empty()) {
		int node = q.front(); q.pop();
		for (const auto& item : al[node]) {
			if (group[item]) continue;
			q.push(item);
			group[item] = i + 1;
		}
	}
}

int main()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int>> al = GetAdjacencyList(n, m);
	vector<int> group(n);
	for (int i = 0; i < n; i++) {
		if (!group[i]) BFS(i, al, group);
	}
	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int s, t;
		cin >> s >> t;
		if (group[s] == group[t]) cout << "yes" << endl;
		else cout << "no" << endl;
	}
}



Measured memory_bytes: 8584
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define srt(i) sort(i.begin(), i.end())
#define rvt(i) sort(i.begin(), i.end(), greater<int>())
 
int main()
{
    string s;
    cin >> s;

    if(s=="ABC") cout << "ARC" << endl;
    else cout << "ABC" << endl;
}

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

int main() {
    
    int A,B,C,D,i=0;
    cin >> A >> B >> C >> D;
    while(1){
        if(i %2 ==0){
            C-=B;
            if(C <=0){
                cout << "Yes" <<endl;
                break;
            }
        }
        else{
            A-=D;
            if(A <=0){
                cout << "No" <<endl;
                break;
            }
        }
        i++;
    }
    
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
using namespace std;
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
    int N;

    cin >> N;

    vector<int> V(N);
  
    rep(i, N) cin >> V[i];
  
    vector<int> A(N);

    rep(i, N) A[V[i]-1] = i+1;

    rep(i, N) {cout << A[i] << " ";}

    return 0;
}

Measured memory_bytes: 1664
import sys
sys.setrecursionlimit(100000)

def ins(): return input().split()
def ii(): return int(input())
def iil(): return list(map(int, ins()))
def lin(): return list(input())
def iin(): return map(int, ins())


n = ii()
k = input()
t = ''
ans = 0
for i in k:
    if t!=i:
        ans += 1
        t = i
print(ans)

Measured memory_bytes: 3316
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;

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

template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;

int main() {
	ll a, b, c, k;
	cin >> a >> b >> c >> k;
	if (a >= k) {
		cout << k << endl;
	}
	else if (a + b >= k) {
		cout << a << endl;
	}
	else {
		cout << a - (k-a-b) << endl;
	}
	return 0;
}

Measured memory_bytes: 3628
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

n = ini()
d = factorization(n)
if d[0][0] == 1:
    d = []
ans = 0
for i in range(len(d)):
    j = 1
    while d[i][1] >= j:
        d[i][1] -= j
        j += 1
        ans += 1
print(ans)

Measured memory_bytes: 63516
#include <iostream>
#include <cstring>

using namespace std;

int judge(int a, int b) { // aがbにかつかどうか
//    cout << a << ' ' << b << endl;
    if (a == 1) {
        if (b == 1) return 3;
        if (b == 2) return 1;
        if (b == 3) return 2;
    } 
    if (a == 2) {
        if (b == 1) return 2;
        if (b == 2) return 3;
        if (b == 3) return 1;
    } 
    if (a == 3) {
        if (b == 1) return 1;
        if (b == 2) return 2;
        if (b == 3) return 3;
    }
}


void result(int *h) {
    // 3つ同じ手
    if (h[0] == h[1] && h[1] == h[2] && h[2] == h[3] && h[3] == h[4]) {
        for (int i = 0; i < 5; i++) h[i] = 3;
        return;
    }

    // 3つ違う手
    bool hand_used[3+1];
    memset(hand_used, 0, sizeof(hand_used));
    for (int i = 0; i < 5; i++) {
        hand_used[h[i]] = true;
    }
    if (hand_used[1] && hand_used[2] && hand_used[3]) {
        for (int i = 0; i < 5; i++) h[i] = 3;
        return;
    }

    if (hand_used[1] && hand_used[2]) {
        for (int i = 0; i < 5; i++) {
            if (h[i] == 1) h[i] = judge(1, 2);
            else           h[i] = judge(2, 1);
        }
        return;
    }
    if (hand_used[2] && hand_used[3]) {
        for (int i = 0; i < 5; i++) {
            if (h[i] == 2) h[i] = judge(2, 3);
            else           h[i] = judge(3, 2);
        }
        return;
    }
    if (hand_used[3] && hand_used[1]) {
        for (int i = 0; i < 5; i++) {
            if (h[i] == 3) h[i] = judge(3, 1);
            else           h[i] = judge(1, 3);
        }
        return;
    }
}



int main() {
    int h[5];
    while (cin >> h[0], h[0] != 0) {
        for (int i = 1; i < 5; i++) {
            cin >> h[i];
        }
        result(h);
        for (int i = 0; i < 5; i++) {
            cout << h[i] << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 0
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

ans = 0
cnt = 0
i = 0
while i < N:
    if A[i] == i + 1:
        ans += 1
        i += 1
    i += 1
print(ans)


# for i in range(N):
#     if i + 1 == A[i]:
#         ans += 1
#         cnt += 1
#     else:
#         # print(cnt)
#         if cnt > 1:
#             ans -= 1
#         cnt = 0   
# if cnt > 1:
#     ans -= 1

# print(ans)


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

ll modinv(ll a,ll m){
   ll b=m,u=1,v=0;
   while(b){
      ll t=a/b;
      a-=t*b; 
      swap(a,b);
      u-=t*v; 
      swap(u,v);
   }
   u%=m;
   if(u<0) u+=m;
   return u;
}

ll gcd(ll x,ll y){
   if(y==0) return x;
   else return gcd(y,x%y);
}
ll lcm(ll x,ll y){
   return x/gcd(x,y)*y;
}



int main(){
   int a,b,c,d;
   cin>>a>>b>>c>>d;

   bool f=true;
   do{
      c-=b;
      if(c<=0) break;

      a-=d;
      if(a<=0){
         f=false;
         break;
      }
   }while(1);

   f? cout<<"Yes":cout<<"No"<<endl;

   return 0;
}



Measured memory_bytes: 3648
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<cstring>
#include<stack>
#include<functional>
using namespace std;

void dfs(int n,vector<int> e[26],bool used[26]){
	if(used[n]) return;
	used[n] = true;
	for(int i=0;i<e[n].size();i++){
		dfs(e[n][i],e,used);
	}
	printf("%c",'a'+n);
}

int main(){
	int N;
	cin>>N;
	for(int ds=0;ds<N;ds++){
		vector<int> e[26];
		bool used[26]; fill_n(used,26,true);
		string S;
		cin>>S;
		for(int i=0;i<S.size();i++){
			if(isalpha(S[i])) used[S[i]-'a'] = false;
			int a = S[i-1]-'a', b = S[i+2]-'a';
			if(S[i]=='-' && S[i+1]=='>'){
				e[b].push_back(a);
			}
			else if(S[i]=='<' && S[i+1]=='-'){
				e[a].push_back(b);
			}
		}
		for(int i=0;i<26;i++) if(used[i]==false) dfs(i,e,used);
		puts("");
	}
	return 0;
}

Measured memory_bytes: 1212
def solve(n, h_list):
    inf = 10 ** 4
    dp = [inf] * n
    dp[0], dp[1] = 0, abs(h_list[1] - h_list[0])

    for i in range(1, n):
        dp[i] = min(dp[i - 1] + abs(h_list[i] - h_list[i - 1]),
                    dp[i - 2] + abs(h_list[i] - h_list[i - 2])
                )

    return dp[n - 1]


def main():
    n = int(input())
    h_list = list(map(int, input().split()))

    ans = solve(n, h_list)
    print(ans)


main()


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

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;


int main() {
    ios_base::sync_with_stdio(false);
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == 'A' && s[i+1] == 'C') {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
  int i,list[10];
  for(i=0;i<10;i++){
     cin >> list[i];
  }
  sort(list,list+10);
  for(i=0;i<3;i++){
     cout << list[9-i] << endl; 
  }
    return 0;
}


Measured memory_bytes: 3136
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
REP(i,v.size()){if(i)os<<" ";os<<v[i];}return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
REP(i,v.size()){if(i)os<<endl;os<<v[i];}return os;}

int main() {
    // Write Your Code Below
    string s; cin >> s;
    int size = s.size();
    int tmp=0;
    for(int i=0;i<size;i++){
        if(s[i]=='o') tmp++;
    }
    int rest = 15-size;
    string ans="NO";
    if(tmp+rest>=8) ans = "YES";
    
    cout << ans << endl;

}


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

using namespace std;

int main()
{
    int n, a, s1, s2, s3, s4;
    cin >> n;
    long long Dp[n+1][5], M;
    for (int i = 0; i < 5; i++)
    {
        Dp[0][i] = 0;
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> a;
        Dp[i][0] = Dp[i-1][0] + a;
        s1 = a%2;
        if (a < 2)
        {
            s1 = 2-a;
        }
        M = Dp[i-1][0];
        Dp[i][1] = min(M, Dp[i-1][1]) + s1;
        s2 = (a+1) % 2;
        M = min(M, Dp[i-1][1]);
        Dp[i][2] = min(Dp[i-1][2], M) + s2;
        s3 = s1;
        M = min(M, Dp[i-1][2]);
        Dp[i][3] = min(Dp[i-1][3], M) + s3;
        M = min(M, Dp[i-1][3]);
        Dp[i][4] = min(Dp[i-1][4], M) + a;
    }
    M = Dp[n][0];
    for (int i = 1; i <= 4; i++)
    {
        M = min(Dp[n][i], M);
    }
    cout << M;
    return 0;
}


Measured memory_bytes: 8064
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S = input()
ans = 'x' * len(S)
print(ans)

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

using namespace std;

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

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

    int n, q;
    cin >> n >> q;
    vector<ll> s(n), t(n), x(n);
    vector<P> v; // (s-x, index)
    for (int i = 0; i < n; i++)
    {
        cin >> s[i] >> t[i] >> x[i];
        s[i] -= x[i];
        t[i] -= x[i];
        v.push_back(P(s[i], i));
    }
    sort(v.begin(), v.end());
    int index = 0;
    priority_queue<P, vector<P>, greater<P>> que; // (t-x, index)
    multiset<ll> st;                              // x
    while (q--)
    {
        ll d;
        cin >> d;
        while (index < n && v[index].first <= d)
        {
            int idx = v[index].second;
            ll tt = t[idx], xx = x[idx];
            que.push(P(tt, idx));
            st.insert(xx);
            index++;
        }
        while (!que.empty() && que.top().first <= d)
        {
            int idx = que.top().second;
            ll xx = x[idx];
            que.pop();
            auto e = st.lower_bound(xx);
            assert((*e)==xx);
            st.erase(e);
        }
        if(st.size()==0)
        {
            cout << -1 << endl;
            continue;
        }
        auto itr = st.begin();
        cout << (*itr) << endl;
    }
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
string S;
int C[256];
ll mo=1000000007;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	FOR(i,256) C[i]++;
	FORR(s,S) C[s]++;
	
	ll ret=1;
	FOR(i,256) ret=ret*C[i]%mo;
	cout<<(ret+mo-1)%mo<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 512
use proconio::*;

fn main() {
    input! {
        (n,k):(usize,usize),
        a : [(i32,i32);k],
    };

    const MOD: i64 = 998244353;

    let mut dp = vec![0 as i64; n + 1];
    dp[1] = 1;
    let mut sum = vec![0 as i64; n + 1];
    sum[1] = 1;

    for i in 2..=n {
        for j in 0..k {
            let l = i as i32 - a[j].1;
            let r = i as i32 - a[j].0;
            if r < 0 {
                continue;
            }
            let l = l.max(1);
            dp[i] += sum[r as usize] - sum[l as usize - 1];
            dp[i] = (dp[i] + MOD) % MOD;
        }
        sum[i] = sum[i - 1] + dp[i];
        sum[i] %= MOD;
    }

    println!("{:?}", dp[n]);
}


Measured memory_bytes: 5276
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
#define rall(a) (a).rbegin(),(a).rend()
const int INF = 2e9;
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

int main(){
    int n; cin >> n;
    vector<int> v(n), c(n);

    rep(i,n) cin >> v[i];
    rep(i,n) cin >> c[i];

    ll ans = 0;

    rep(i,n){
        if(v[i] > c[i]){
            ans += v[i] - c[i];
        }
    }

    dunk(ans);

}


Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
rem=0
ans=0
for i in range(n):
    if a[i]>=rem:
        ans+=rem
        a[i]-=rem
        if b[i]>=a[i]:
            ans+=a[i]
            rem=b[i]-a[i]
        else:
            ans+=b[i]
            rem=0
    else:
        ans+=a[i]
        rem=b[i]
ans+=min(rem,a[n])
print(ans)

Measured memory_bytes: 19156
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
dic = {}
for i in a:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1
dic = sorted(dic.items(), key=lambda x: x[1])
#while len(dic) > k:
#    ans += dic[0][1]    
#    del dic[0]
for i in range(len(dic)-k):
    ans += dic[i][1]
print(ans)

Measured memory_bytes: 39932
import java.util.Arrays;
import java.util.Scanner;

public class Main implements Runnable {

    private static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        new Thread(null, new Main(), "", 128 * 1024 * 1024).start();
    }

    public void run() {
        int k = sc.nextInt();
        int ans = 0;
        for (int i = 1; i <= k; i++) {
            ans += (k - i + 1) / 2;
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 25428
from collections import deque

k = int(input())
lun = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

for i in range(k - 1):
    tmp = lun.popleft()
    if tmp % 10 != 0:
        lun.append(tmp * 10 + (tmp % 10 - 1))
    lun.append(tmp * 10 + (tmp % 10))
    if tmp % 10 != 9:
        lun.append(tmp * 10 + (tmp % 10 + 1))

print(lun.popleft())

Measured memory_bytes: 12384
import java.util.Arrays;
import java.util.Scanner;

public class Main implements Runnable {

    private static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        new Thread(null, new Main(), "", 128 * 1024 * 1024).start();
    }

    public void run() {
        int n = sc.nextInt();
        int[] x = new int[n];
        int[] y = new int[n];
        int[] h = new int[n];

        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
            h[i] = sc.nextInt();
        }

        for (int i = 0; i <= 100; i++) {
            for (int j = 0; j <= 100; j++) {
                int ch = -1;
                for (int k = 0; k < n; k++) {
                    if (h[k] > 0) {
                        if (ch == -1) {
                            ch = h[k] + Math.abs(x[k] - j) + Math.abs(y[k] - i);
                        } else {
                            if (ch != h[k] + Math.abs(x[k] - j) + Math.abs(y[k] - i)) {
                                ch = -2;
                                break;
                            }
                        }
                    }
                }
                if (ch >= 0) {
                    for (int k = 0; k < n; k++) {
                        if (h[k] == 0) {
                            if (Math.abs(x[k] - j) + Math.abs(y[k] - i) < ch) {
                                ch = -2;
                                break;
                            }
                        }
                    }
                }
                if (ch >= 0) {
                    System.out.println(j + " " + i + " " + ch);
                }
            }
        }
    }
}

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

int main(){
    int n,count=0,yu = 0;
    cin >> n;
    vector<int> moti(n);

    for(int i = 0;i < n;i++)
        cin >> moti.at(i);

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

    for(int i = 0;i < n;i++){
        if(yu != moti.at(i)){
            yu = moti.at(i);
            count++;
        }
    }

    cout << count << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = 1; i <= n; i++)
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
using P = pair <int, int>;
 
ll MOD = 1000000007;
ll INF =1<<29;
ll dp[100100];
char mas[51][51]; 
int main() {
     int n,m;
     cin>> n>>m;
     int L=-1 ,R=INF;
     rep(i,m){
        int l,r;
        cin >>l>>r;
        if(l>=L) L=l;
        if(r<=R) R=r;
     }
     cout<< max(0,R-L+1)<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
typedef long long ll;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

vector<vector<int>> d(201,vector<int>(201));

int main(){
    int k;
    cin >> k;
    ll ans =0;

    rep(i, 201){
        rep(j, 201) d.at(i).at(j)=-1;
    }

    for(int a=1;a<=k;a++){
        for(int b=1;b<=k;b++){
            int ab;
            if(d[max(a,b)][min(a,b)]==-1) d[max(a,b)][min(a,b)] = gcd(a,b);
            ab = d[max(a,b)][min(a,b)];
            for(int c=1;c<=k;c++){
                int x,y;
                x= max(ab, c);
                y= min(ab, c);
                if(d[x][y]==-1) d[x][y] = gcd(x,y);
                ans+=d[x][y];
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3772
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;


public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		Scanner scan=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		String s="";
		while((s=br.readLine())!=null){
			StringTokenizer st=new StringTokenizer(s," ");
			int x=Integer.parseInt(st.nextToken());
			String ss=st.nextToken();
			if(ss.equals("+")){
				int y=Integer.parseInt(st.nextToken());
				System.out.println(x+y);
			}else if(ss.equals("-")){
				int y=Integer.parseInt(st.nextToken());
				System.out.println(x-y);
			}else if(ss.equals("*")){
				int y=Integer.parseInt(st.nextToken());
				System.out.println(x*y);

			}else if(ss.equals("/")){
				int y=Integer.parseInt(st.nextToken());
				System.out.println(x/y);

			}else{
				break;
			}
		}

	}

}

Measured memory_bytes: 17236
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int rem=n%10;
  if(rem==2||rem==4||rem==5||rem==7||rem==9)
    cout<<"hon\n";
  else if(rem==3)
    cout<<"bon\n";
  else
    cout<<"pon\n";
}


Measured memory_bytes: 3536
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long ;
using P = pair<int, int>;

void solver(int N, string S, int &ans){

    map<char, int> l;
    map<char, int> r;
    int buf{};

    for(int i = 0; i < N; ++i){
        for(int j = 0; j <= i; ++j){
            l[S.at(j)]++;
        }
        for(int k = i+1; k != N; ++k){
            r[S.at(k)]++;
        }

        for(auto p: l){
            auto word = p.first;
            if(r.count(word) != 0) ++buf;
        }
        ans = max(ans, buf);

        buf = 0;
        l.clear();
        r.clear();
    }

    return;
}


int main(){

    int N;
    string S;
    cin >> N >> S;

    int ans = -1;
    solver(N, S, ans);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3600
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	String input1 = scan.next();
	int a = Integer.parseInt(input1);
	String input2 = scan.next();
	int b = Integer.parseInt(input2);
	String input3 = scan.next();
	int c = Integer.parseInt(input3);
	if (a < b && b < c) {
	    System.out.println("Yes");
	} else {
	    System.out.println("No");
	}
    }
}

Measured memory_bytes: 26036
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i < (n);++i)
typedef long long ll;
using namespace std;
 
int main(){
  int a,b;
  cin >> a >> b;
  
  int ans;
  ans = (a-1)*(b-1);
  
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 256
import copy
n,W=map(int,input().split())
l=[0]*(W+1)
for _ in range(n):
	w,v=map(int,input().split())
	d=copy.deepcopy(l)
	for i in range(len(d)):
		if i-w>=0:
			d[i]=max(d[i],l[i-w]+v)
	l=d
	#print(l)

print(l[-1])



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

int dist(string a, string b) {
  int s = 0;
  for (int i = 0; i < a.length(); i ++)
      s += (a[i] != b[i]);
  return s;
}

int main() {
  string a, b; cin >> a >> b;
  int m = 100000000;
  for (int i = 0; i <= a.length() - b.length(); i ++) {
    m = min(m, dist(b, a.substr(i, b.length())));
  }
  cout << m << endl;
}

Measured memory_bytes: 3588
#include <iostream>
#include <iomanip>
#include <math.h>
#include <vector>
#include <map>
using namespace std;
int main() {
  int r, d, x;
  cin >> r >> d >> x;
  for (int i = 1; i <= 10; i++) {
	  x = r * x - d;
	  cout << x << endl;
	}
  return 0;
}


Measured memory_bytes: 256
def main():
    tmp = list(map(int, input().split(" ")))
    a = tmp[0]
    b = tmp[1]
    c = tmp[2]
    d = tmp[3]

    ans = f(b, c, d) - f(a-1, c, d)
    print(ans)


def gcd(c, d):
    big = max(c, d)
    small = min(c, d)
    if small == 0:
        return int(big)
    r = big % small
    return gcd(small, r)


def lcm(c, d):
    return int((c*d) / gcd(c, d))


def f(x, c, d):
    return x - (x//c) - (x//d) + (x // lcm(c, d))


main()

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

#define FILE
#define fr first
#define se second

using namespace std;

const long long N = 2e5 + 7;
const long long inf = 1e9 + 7;
const long long mod = 1e9 + 7;

int n;
int k;
int main()
{
    #ifdef FILEs
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);

    cin >> n >> k;
    cout << k + 100 * (10 - min(10, n)) << "\n";
}



Measured memory_bytes: 256
N = int(input())
h = list(map(int,input().split()))

ml = [10**9]* N

ml[0] = 0
ml[1] = abs(h[1]-h[0])
for i in range(2,N):
    ml[i] = min(abs(h[i]-h[i-1]) + ml[i-1], abs(h[i]-h[i-2]) + ml[i-2])

print(ml[N-1])


Measured memory_bytes: 20368
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int INF = 1LL << 30;
int MOD = 1e9+7;
main(){
    string S,str;
    cin >> S;
    for(char c:S)if(c != 'x')str += c;
    for(int i = 0;i < str.length();i++){
        if(str[i] != str[str.length()-1-i]){
            cout << -1 << endl;
            return 0;
        }
    }
    S = '0' + S + '0';
    int cnt = 0,h = 0,t = S.length()-1;
    while(h < t){
        int dh = h,dt = t;
        h++;t--;
        if(h >= S.length() || t < 0)break;
        while(S[h] == 'x')h++;
        while(S[t] == 'x')t--;
        cnt += abs(abs(h - dh) - abs(t - dt));
    }
    cout << cnt << endl;
}

Measured memory_bytes: 640
import core.bitop;
import std.algorithm;
import std.ascii;
import std.bigint;
import std.conv;
import std.functional;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.random;
import std.typecons;
import std.container;

alias sread = () => readln.chomp();
ulong bignum = 1_000_000_007;
alias SugarWater = Tuple!(long, "swater", long, "sugar");

T lread(T = long)()
{
    return readln.chomp.to!T();
}

T[] aryread(T = long)()
{
    return readln.split.to!(T[])();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}

void main()
{
    long a, b;
    scan(a, b);
    if (a % 2)
        calcans(a, b, a);
    else
    {
        if (b - a < 3)
        {
            long ans = a;
            foreach (e; a .. b)
                ans ^= e + 1;

            ans.writeln();
        }
        else
            calcans(a + 3, b, 0);
    }
}

void calcans(long a, long b, long c)
{
    long skip = (b - a) / 4;
        skip *= 4;
        long start = a + skip, ans = c;
        foreach (e; start .. b)
            ans ^= e + 1;

        ans.writeln();
}

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

typedef long long ll;

const int MAX_N = 1000000;
const int mod = 1000000007;

ll fact[MAX_N];         // 階乗
ll ifact[MAX_N];        // 階乗の逆元

// x^nを求める繰り返し二乗法(累乗の高速化)
// フェルマーの小定理より、逆元を計算するときに用いる。
ll mod_pow(ll x, int n){
    if(n == 0)      return 1;

    ll res = 1;
    while(n > 0){
        if(n & 1)   res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }

    return res;
}

// 階乗とその逆元テーブルを(0-n)まで埋める
void table(int n){
    fact[0] = 1;    // i^0 = 1;
    for(int i = 1; i <= n; ++i){
        fact[i] = fact[i - 1] * i % mod;
    }

    // フェルマーの小定理を利用して、右端の逆元を求める
    // 階乗の(mod-2)乗
    ifact[n] = mod_pow(fact[n], mod - 2);

    // 逆元の性質を利用して、テーブルを埋める
    for(int i = n; i >= 1; --i){
        ifact[i - 1] = ifact[i] * i % mod;
    }
}

// nCrを求める
ll combination(int n, int r){
    if(n < 0 || r < 0 || n < r)     return 0;

    return fact[n] * ifact[r] % mod * ifact[n - r] % mod;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int h, w, a, b;
    cin >> h >> w >> a >> b;
    
    table(h + w);
    
    ll res = 0;
    // 右方向に関する数字
    int pre = b, rear = w - 1 - pre;
    // まず、下方向をiマス選択して、移動禁止区域を回避する。
    // 右方向に関しては、移動禁止区域を回避するためには、まず合計でb本の選択が必須。
    for(int i = 0; i < h - a; ++i){
        ll temp = 1;
        temp = temp * combination(pre - 1 + i, i) % mod;    // *combination(1, 1)(=最後に右を選択)
        temp = temp * combination(rear + h - 1 - i, rear) % mod;
        
        res = (res + temp) % mod;
    }
    
    cout << res << endl;
}

Measured memory_bytes: 5888
#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    double pai=3.141592653589;
    char s[100], p[100];
    string scp,s2,chk;
    scanf("%s %s",&s,&p);
    scp=s;
    chk=p;
    s2=scp+scp;
    if(s2.find(p) != string::npos){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
    return 0;
}

Measured memory_bytes: 3288
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,m,x;
  cin >> n >> m >> x;
  vector<int> a(m);
  for(int i=0; i<m; i++){cin >> a.at(i);}
  int rcost,lcost;
  rcost = lcost = 0;
  for(int i=0; i<m; i++){
    if(a.at(i)<x){
      lcost += 1;
    }
  }
  for(int i=0; i<m; i++){
    if(a.at(i)>x){
      rcost += 1;
    }
  }
  cout << min(lcost,rcost) << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<map>

using namespace std;

int main() {
    int n,i;

    cin>>n;

    for(i=1;i<10;i++){
        if(111*i>=n){
            cout<<111*i;
            break;
        }
    }

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
 int N,M;
  cin >>N>>M;
  vector<int> a(M);
  vector<int> b(M);
  vector<int>count(N);
  for(int i=0 ;i<M;i++)
  {
   cin>>a[i]>>b[i];
      for(int j=0;j<N;j++)
   {
      if(a[i]==j+1||b[i]==j+1) {count[j]++;}
   }
  }
 for(int i=0;i<N;i++)
 {
   cout<<count[i]<<endl;
 }
}

Measured memory_bytes: 256
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

n,k = myinput()
a = list(myinput())

ls = [-1]*n

ls[0] = 0
s = 0
for i in range(n):
    if (i+1)==k:
        s = a[s] - 1
        print(s+1)
        exit()
    else:
        s = a[s] - 1
        if ls[s]<0:
            ls[s] = i + 1
            # print(ls)
        else:
            b = ls[s]
            w = (i+1) - b
            c = (k-b)%w
            g = ls.index(c+b) + 1
            # print(w,c,b)
            print(g)
            exit()

Measured memory_bytes: 93932
#include <bits/stdc++.h>
#include <string>
#define ft first
#define sc second
#define pt(sth) cout << sth << "\n"
#define moca(a, s, b) a=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
template<class T>bool chmax(T &a, const T &b) {if(a<b) {a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if(b<a) {a=b; return 1;} return 0;}
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=998244353;


/*
 for(i=0; i<N; i++)
   cin >> a[i];
*/

ll mopo(ll x, ll n) {
  ll res=1;
  while(n>0) {
    if(n&1) moca(res, *, x);
    moca(x, *, x);
    n>>=1;
  }
  return res;
}

ll fa[MAX*2], rf[MAX*2];

ll C(ll n, ll k) {
  if(n<k||n<0||k<0) return 0;
  if(k==0) return 1;
  if(n==k) return 1;
  return fa[n]*rf[k]%MOD*rf[n-k]%MOD;
}


int main(void) {
  ll i, j, k;
  
  fa[0]=rf[0]=1;
  for(i=1; i<MAX*2; i++) {
    fa[i]=fa[i-1]*i%MOD;
    rf[i]=mopo(fa[i], MOD-2);
  }
  
  ll N, M, K;
  cin >> N >> M >> K;
  
  ll ans=0;
  for(i=0; i<=K; i++) moca(ans, +, M*C(N-1, i)%MOD*mopo(M-1, N-i-1)%MOD);
  pt(ans);
  
  
}


Measured memory_bytes: 6796
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static long[] hi;
        static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            var N = Sarray()[0];
            hi = Sarray();

            var hen = 0L;
            var dflg = false;
            var ans = 0L;
            for (var i = 1; i < hi.Length; ++i)
            {
                if (hi[i - 1] > hi[i]) dflg = true;
                if(dflg && hi[i-1]<hi[i])
                {
                    ans += RangeMax(hen, i - 1) - hi[i - 1];
                    hen = i - 1;
                    dflg = false;
                }
            }
            ans += RangeMax(hen, hi.Length - 1);
            WriteLine(ans);
            //Out.Flush();
        }
        static long RangeMax(long s , long e)
        {
            var max = hi[(int)s];
            for (var i = s; i <= e; ++i)
                max = Max(max, hi[(int)i]);
            return max;
        }
    }
}

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

int main(){
	int N;
	int ans=0,tmp;
	cin >> N;
	for(int loop=1;loop<N;loop++){
		tmp=N/loop;
		if(N%loop==0)tmp--;
		ans+=tmp;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3632
//package abc165.C

import java.io.*
import java.math.*
import java.util.*
import kotlin.math.*

var reader: BufferedReader = System.`in`.bufferedReader()
var writer: PrintWriter = PrintWriter(System.`out`)

fun next() = reader.readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun nextStrings() = next().split(" ")
fun nextInts() = nextStrings().map { it.toInt() }
fun nextLongs() = nextStrings().map { it.toLong() }
fun nextDoubles() = nextStrings().map { it.toDouble() }

fun put(v: Any?) = writer.print(v)
fun puts() = writer.println()
fun puts(v: Any?) = writer.println(v)

var debug = false
fun dp(v: Any?) {
    if (debug) println(v)
}
fun dp() {
    if (debug) println()
}

fun test(case: Int, input: String, expected: String) {
    reader = input.trimIndent().reader().buffered()

    val stringWriter = StringWriter()
    writer = PrintWriter(stringWriter)

    solve()
    writer.flush()

    val actual = stringWriter.toString()

    println("[test $case]")
    if ("${expected}" == actual) {
        println("OK")
    } else {
        println("NG")
        println()
        println("expected: \"${expected}\"")
        println("actual:   \"${actual}\"")
    }
    println()
}

@Suppress("UNUSED_PARAMETER")
fun xtest(case: Int, input: String, expected: String) {}

fun main(args: Array<String>) {
    if ((args.size == 1) && (args[0] == "test")) {
        testAll()
    } else {
        solve()
        writer.flush()
    }
}

///////////////////////////////////////////////////////////

fun testAll() {
    debug = true

    test(1,
    """
    3 4 3
    1 3 3 100
    1 2 2 10
    2 3 2 10
    """,
    "110"
    )
    test(2,
    """
    4 6 10
    2 4 1 86568
    1 4 0 90629
    2 3 0 90310
    3 4 1 29211
    3 4 3 78537
    3 4 2 8580
    1 2 1 96263
    1 4 2 2156
    1 2 0 94325
    1 4 3 94328
    """,
    "357500")
    test(3,
    """
    10 10 1
    1 10 9 1
    """,
    "1")
}

class Score(
    val a: Int,
    val b: Int,
    val c: Int,
    val d: Int
) {
    fun calculate(A: Array<Int>): Int {
        return if (A[b] - A[a] == c) {
            d
        } else {
            0
        }
    }
}

fun calculate(A: Array<Int>, idx: Int, N: Int, l: Int, u: Int, scores: List<Score>): Int {
    if (idx == N) {
        return scores.sumBy {
            it.calculate(A)
        }
    }

    var max = 0
    for (i in l..u) {
        A[idx] = i
        max = max(calculate(A, idx+1, N, i, u, scores), max)
    }
    return max
}

fun solve() {

    val (N, M, Q) = nextInts()

    val scores = mutableListOf<Score>()
    repeat(Q) {
        val (a, b, c, d) = nextInts()
        scores.add(Score(a-1, b-1, c, d))
    }

    val A = Array<Int>(N) { 0 }
    val result = calculate(A, 0, N, 1, M, scores)
    put(result)
}


Measured memory_bytes: 42056
import qualified Data.ByteString.Char8 as BS
import Data.Maybe

readInt = fromIntegral . fst . fromJust . BS.readInteger
readIntList = map readInt . BS.words

getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

play :: Int -> Int -> Int -> Int
play a b c | (a `mod` 2 == 0) && (b `mod` 2 == 0) && (c `mod` 2 == 0) && (a == b) && (b == c) = -1
           | (a `mod` 2 == 0) && (b `mod` 2 == 0) && (c `mod` 2 == 0) = 1 + play ((b+c) `div` 2) ((a+c) `div` 2) ((a+b) `div` 2)
           | otherwise = 0

main = do
  [a, b, c] <- getIntList
  print $ play a b c

Measured memory_bytes: 380
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

constexpr char newl = '\n';
constexpr double eps = 1e-10;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << '\n';
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
template<class T> void Print(vector<T> v) {
  F0R(i, v.size()) {
    cout << v[i] << ' ';
  }
  cout << newl;
}

#if 1

i64 gcd(i64 a, i64 b) { return b ? gcd(b, a % b) : a; }
i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }

// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int x;
  cin >> x;

  cout << (lcm(x, 360) / x);
}
#endif


Measured memory_bytes: 3648
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
using namespace std;
typedef long long ll;

template<class T>T gcd(T a, T b){if(a<b){a^=b;b^=a;a^=b;}return b?gcd(b,a%b):a;}
template<class T>T lcm(T a, T b){return a/gcd(a,b)*b;}

ll N;
ll T[100];

int main(){
    cin>>N;
    rep(i,N) cin>>T[i];

    ll ans;
    rep(i,N){
        if(i==0){
            ans=T[i];
        }else{
            ans=lcm(ans,T[i]);
        }
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 256