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

using namespace std;

#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long int
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vii vector<pii>
#define pb push_back
#define B begin()
#define E end()
#define sz(X) (X).size()
#define F first
#define S second
#define loop(z, v) for(auto &z: v)
#define nl "\n"
#define fat 1000000007

template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x=0, T y=0) : x(x), y(y) {}
bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
P operator+(P p) const { return P(x+p.x, y+p.y); }
P operator-(P p) const { return P(x-p.x, y-p.y); }
P operator*(T d) const { return P(x*d, y*d); }
P operator/(T d) const { return P(x/d, y/d); }
T dot(P p) const { return x*p.x + y*p.y; }
T cross(P p) const { return x*p.y - y*p.x; }
T cross(P a, P b) const { return (a-*this).cross(b-*this); }
T dist2() const { return x*x + y*y; }
double dist() const { return sqrt((double)dist2()); }
// angle to x−axis in interva l [−pi , pi ]
double angle() const { return atan2(y, x); }
P unit() const { return *this/dist(); } // makes d is t ()=1
P perp() const { return P(-y, x); } // rotates +90 degrees
P normal() const { return perp().unit(); }
// returns point rotated ’a ’ radians ccw around the origin
P rotate(double a) const {
return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
friend ostream& operator<<(ostream& os, P p) {
return os << "(" << p.x << "," << p.y << ")"; }
};
typedef Point<double> P;

double ccRadius(const P& A, const P& B_, const P& C) {
return (B_-A).dist()*(C-B_).dist()*(A-C).dist()/
abs((B_-A).cross(C-A))/2;
}

P ccCenter(const P& A, const P& B_, const P& C) {
P b = C-A, c = B_-A;
return A + (b*c.dist2()-c*b.dist2()).perp()/b.cross(c)/2;
}

double mec(vector<P> ps) {
shuffle(ps.B, ps.E, mt19937(time(0)));
P o = ps[0];
double r = 0, EPS = 1 + 1e-8;
for(int i = 0; i < sz(ps); i++) if ((o - ps[i]).dist() > r * EPS) {
    o = ps[i], r = 0;
for(int j = 0; j < i; j++) if ((o - ps[j]).dist() > r * EPS) {
o = (ps[i] + ps[j]) / 2;
r = (o - ps[i]).dist();
for(int k = 0; k < j; k++) if ((o - ps[k]).dist() > r * EPS) {
o = ccCenter(ps[i], ps[j], ps[k]);
r = (o - ps[i]).dist();
}
}
}
return r;
}

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

    vector<P> ps(n);
    loop(z, ps) cin >> z.x >> z.y;

    cout << setprecision(10) << mec(ps) << nl;

    return 0;
}

Measured memory_bytes: 256
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define INF 2000000005
#define maxn 100005
#define LL long long int
using namespace std;
LL A,B;
LL n;
LL line[maxn];
LL temp[maxn];
bool judge(LL x){
	for(LL i=1;i<=n;i++)temp[i]=line[i]-x*B;
	LL tot=0;
	for(LL i=1;i<=n;i++){
		if(temp[i]>0){
			tot+=temp[i]/(A-B)+1;
			if(temp[i]%(A-B)==0)tot--;
		}
	}
	if(tot<=x)return true;
	return false;
}
LL work(LL l,LL r){
	if(l==r)return l;
	LL mid=((r-l)>>1)+l;
	if(judge(mid)) return work(l,mid);
	else return work(mid+1,r);
}
int main(){
	scanf("%lld%lld%lld",&n,&A,&B);
	for(LL i=1;i<=n;i++)scanf("%lld",&line[i]);
	printf("%lld",work(1,INF));
	return 0;
}

Measured memory_bytes: 1664
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in);) {
            solve(sc);
        }
    }

    public static void solve(Scanner sc) {
        int a = sc.nextInt();
        int b = sc.nextInt();

        System.out.println((b * 2) - a);
    }
}

Measured memory_bytes: 22100
#include<cstdio>
#include<algorithm>
using namespace std;
const long long MOD = 1000000007;
const int MAX = 3000 + 10;

int n, m;

long long dpb[MAX][MAX];
long long dps[MAX][MAX];
long long tmpxb[MAX];
long long tmpxs[MAX];
long long tmpyb[MAX];
long long tmpys[MAX];
long long lazy[MAX];

int rec[MAX];

void update(int x) {
    for(int i = 0 ; i < n ; i++) {
        dpb[x][i] *= lazy[x];
        dpb[x][i] %= MOD;
        dps[x][i] *= lazy[x];
        dps[x][i] %= MOD;
    }
    lazy[x] = 1LL;
}

long long inv(int x) {
    if(x == 1) return 2LL;
    long long tmp = inv(x/2);
    if(x&1) return tmp * tmp % MOD * 2 % MOD;
    return tmp * tmp % MOD;
}

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

    for(int i = 0 ; i < n ; i++) {
        scanf("%d", &rec[i]);
    }

    long long ans = 0;

    for(int i = 0 ; i < n ; i++) {
        lazy[i] = 1LL;
        for(int j = 0 ; j < n ; j++) {
            if (rec[j] < rec[i]) {
                dps[i][j]++;
                if (j > i) {
                    ans++;
                }
            } else if (rec[j] > rec[i]) {
                dpb[i][j]++;
            }
        }
    }
    
    long long INV = inv(MOD-2);

    while (m--) {
        int x, y;
        scanf("%d %d", &x, &y);
        x--, y--;
        update(x);
        update(y);
        if (x > y) swap(x, y);

        ans *= 2;
        ans %= MOD;
        
        for(int i = x+1 ; i <= y ; i++) {
            ans += dpb[x][i] - dps[x][i];
            ans %= MOD;
        }

        for(int i = x+1 ; i < y ; i++) {
            ans += dps[y][i] - dpb[y][i];
            ans %= MOD;
        }

        for(int i = 0 ; i < n ; i++) {
            tmpxs[i] = dps[x][i];
            tmpxb[i] = dpb[x][i];
            tmpys[i] = dps[y][i];
            tmpyb[i] = dpb[y][i];
        }

        swap(tmpxs[x], tmpxs[y]);
        swap(tmpxb[x], tmpxb[y]);
        swap(tmpys[y], tmpys[x]);
        swap(tmpyb[y], tmpyb[x]);

        for(int i = 0 ; i < n ; i++) {
            dps[x][i] += tmpys[i];
            dpb[x][i] += tmpyb[i];
            dps[y][i] += tmpxs[i];
            dpb[y][i] += tmpxb[i];
        }

        for(int i = 0 ; i < n ; i++) {
            if(i == x || i == y) continue;
            lazy[i] *= 2;
            lazy[i] %= MOD;

            long tmp = dpb[i][x];
            dpb[i][x] += dpb[i][y];
            dpb[i][y] += tmp;
            dpb[i][x] *= INV;
            dpb[i][x] %= MOD;
            dpb[i][y] *= INV;
            dpb[i][y] %= MOD;

            tmp = dps[i][x];
            dps[i][x] += dps[i][y];
            dps[i][y] += tmp;
            dps[i][x] *= INV;
            dps[i][x] %= MOD;
            dps[i][y] *= INV;
            dps[i][y] %= MOD;
        }
    }
    
    ans = ((ans % MOD) + MOD) % MOD;
    printf("%lld\n", ans);

    return 0;
}


Measured memory_bytes: 141696
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define zero_pad(num) setfill('0') << std::right << setw(num)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

int main() {
	int n, k;
	cin >> n >> k;
	if (n % k == 0) cout << 0 << endl;
	else cout << 1 << endl;

}

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

using namespace std;
using ll = long long;

class Rolling_Hash {
  private:
    int n;
    static constexpr ll base1 = 1007, base2 = 2009;
    static constexpr ll mod1 = (1e9+7), mod2 = (1e9+9);
    vector<ll> hash1, hash2, mpow1, mpow2;
  public:
    Rolling_Hash(const string& s) {
        n=s.size();
        hash1.assign(n + 1, 0);
        hash2.assign(n + 1, 0);
        mpow1.assign(n + 1, 1);
        mpow2.assign(n + 1, 1);
        for(int i = 0; i < n; i++) {
            hash1[i + 1] = (hash1[i]*base1+s[i])%mod1;
            hash2[i + 1] = (hash2[i]*base2+s[i])%mod2;
            mpow1[i + 1] = (mpow1[i]*base1) % mod1;
            mpow2[i + 1] = (mpow2[i]*base2) % mod2;
        }
    }

    //get_hash [l, r)
    auto get(int l, int r) {
        ll lefval = hash1[r] - hash1[l]*mpow1[r-l]%mod1;
        ll rigval = hash2[r] - hash2[l]*mpow2[r-l]%mod2;
        if(lefval<0)lefval += mod1;
        if(rigval<0)rigval += mod2;
        return make_pair(lefval,rigval);
    }

    //最小共通接頭辞を求める
    auto get_LCP(int a,int b){
        int len = min(n-a+1,n-b+1);
        int low=0,high=len;
        while( high-low>1 ){
            ll mid=(high+low)/2;
            if(get(a,a+mid)!=get(b,b+mid))high=mid;
            else low=mid;
        }
        return low;
    }
};
/*
Constructor(string): O(N)
get(l, r): O(1) [l,r)のハッシュを得る
get_LCP(a, b): O(logN) s.substr(a, k) == s.substr(b, k)を満たす最大のkを得る
*/


int main()
{
    int n; string s;
    cin >> n >> s;
    Rolling_Hash rh(s);
    int nax = 0;
    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            nax = max(nax, min(rh.get_LCP(i, j), j - i));
        }
    }
    cout << nax << endl;
}


Measured memory_bytes: 3748
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second

#define pb push_back
#define es erase
#define in insert

#define pii pair<int, int>
#define ll long long
#define lb long double

#define ioss                     \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);

#define m_p(i, j) make_pair(i, j)
#define mem(a, x) memset(a, x, sizeof(a))
#define endl "\n"
#define all(x) x.begin(), x.end()

string s, t;
int solve()
{
    int ma = 0;
    for (int st = 0; st + t.size() <= s.size(); st++) {
        int ed = st + t.size(), cnt = 0;
        for (int i = st; i < ed; i++) {
            int id = i - st;
            if (t[id] == s[i])
                cnt++;
        }
        ma = max(cnt, ma);
    }
    return t.size() - ma;
}
int main()
{
    cin >> s >> t;
    cout << solve() << endl;

    return 0;
}


Measured memory_bytes: 3612
n = int(input())
taro = 0
hanako = 0
for _ in range(n):
    t, h = input().split()
    if t < h:
        hanako += 3
    elif t == h:
        taro += 1
        hanako += 1
    elif t > h:
        taro += 3
print(taro,hanako)


Measured memory_bytes: 5596
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define PI 3.14159265359
#define INF 1000100100
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define P pair<int, int>
#define PP pair<P,P>
using namespace std;
int n;
vector<vector<int> > ki;
vector<int> rw;
vector<int> visitt;
int memo[200006];
stack<P> m;
int ans[2000006];
 
void solve(int now,int p){
    visitt[now]=1;
    int l,r;
    l=0; r=n;
    while(l!=r){
        int c=(l+r)/2;
        //cout << now << ' ' << l << r << ' ' << memo[c] << ' ' << rw[now] << endl;
        if(memo[c]>=rw[now]) r=c;
        else l=c+1;
    }
    //cout << now << ' ' << memo[1] << endl;
    m.push(P(l,memo[l]));
    memo[l]=rw[now];
    //cout << now << ' ' << l << memo[l] << endl;
    ans[now]=max(ans[p],l+1);
    int check=0;
    rep(i,ki[now].size()){
        if(visitt[ki[now][i]]) continue;
        solve(ki[now][i],now);
    }
    int id=m.top().first;
    int dt=m.top().second;
    m.pop();
    memo[id]=dt;
    return;
}
 
int main(){
    cin >> n;
    rw.resize(n+1);
    ki.resize(n);
    visitt.resize(n);
    rep(i,n){
        cin >> rw[i];
        visitt[i]=0;
        memo[i]=INF;
    }
    ans[n]=-1;
    rep(i,n-1){
        int u,v; cin >> u >> v;
        u--; v--;
        ki[u].push_back(v);
        ki[v].push_back(u);
    }
    solve(0,n);
    rep(i,n) cout << ans[i] << endl;
    //rep(i,n) cout << memo[i] << endl;
return 0;
}
 

Measured memory_bytes: 38716
#include <iostream>
#include <math.h>

using namespace std;

int main(){
  	double N, D, dif, dist, calc, ans = 0;
  	cin >> N >> D;
  	double x[10][10];
  	
  	for(int i = 0; i < N; i++){
    	for(int j = 0; j < D; j++){
        	cin >> x[i][j];
        }
    }
  
  	for(int i = 0; i < N-1; i++){
      for(int j = i+1; j < N; j++){
        dist = 0;
        for(int k = 0; k < D; k++){
          	dif = x[i][k] - x[j][k];
          	dif *= dif;
            dist += dif;
        }
      	calc = sqrt(dist);
        //cout << "i:" << i << "j:" << j << endl;
      	//cout << calc << endl;
      	if(calc - (int)calc == 0){
        	ans++;
        }
      }
    }
  
  	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import Control.Monad
import Data.List

readInt = readLn :: IO Int
readInts = map read . words <$> getLine :: IO [Int]
readNInts = flip replicateM readInts

main :: IO ()
main = do
  _ <- getLine
  v <- readInts
  c <- readInts
  print . sum . filter (> 0) $ zipWith (-) v c

Measured memory_bytes: 636
#include <iostream>
#include <iomanip>
#include <ios> 
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;
//const int MAX=1e5+5;

int main(){
	lli N;
	cin>>N;
	lli n;
  	lli H,W;
	
	rep1(i,3500){
		bool OK=false;
		rep1(j,3500){
          	lli h=(lli)i, w=(lli)j;
			lli p=4*h*w-(h+w)*N;
			lli q=h*w*N;
			if(p<=0){
              continue;
            }
          	lli r=q%p;
			if(r==0){
				OK=true;
				n=q/p;
              	H=h;
              	W=w;
				break;
          }
		}
		if(OK)break;
	}
	cout<<H<<" "<<W<<" "<<n;
}

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

using namespace std;

const long long mod = 1e9 + 7;

long long fact[100005];

long long Bin(long long x, long long n) {
	if (n == 0) return 1;
	long long l = Bin(x, n / 2);
	l = l * l % mod * ((n % 2 == 1) ? x : 1) % mod;
	return l;
}

long long rev(long long x) {
	return (Bin(x, mod - 2));
}

void MakeFact(long long n) {
	fact[0] = 1;
	for (long long i = 1; i <= n; i++)
		fact[i] = fact[i - 1] * i % mod;
}

long long cnk(long long n, long long k) {
	if (k > n) return 0;
	return (fact[n] * rev(fact[k]) % mod * rev(fact[n - k]) % mod);
}

void Mod(long long &x) {
	if (x >= 0) {
		x %= mod;
		return;	
	}
	long long k = abs(x) / mod;
	x += k * mod;
	while (x < 0)
		x += mod;
	x %= mod;
}

int main() {
	ios::sync_with_stdio(false);
	long long n, k;
	cin>>n>>k;
	vector < long long > v(n);
	for (long long i = 0; i < n; i++)
		cin>>v[i];
	MakeFact(n);
	sort(v.begin(), v.end());
	long long res = 0;
	for (long long i = 0; i < n; ) {
		long long j = i;
		while (j + 1 < n && v[j + 1] == v[i])
			j++;
			
		//cout<<i<<" "<<j<<endl;
		//cout<<"res += "<<cnk(j + 1, k)<<" - "<<cnk(i - 1, k)<<endl;
		
		long long curr = 0;
		curr += cnk(j + 1, k) - cnk(i, k);
		/*while (curr < 0)
			curr += mod;*/
		//curr %= mod;
		Mod(curr);
		
		//cout<<"res -= "<<cnk(n - i, k)<<" - "<<cnk(n - j, k)<<endl;
		curr -= cnk(n - i, k) - cnk(n - j - 1, k);
		/*while (curr < 0)
			curr += mod;*/
		//curr %= mod;
		Mod(curr);
		
		res += curr * v[i];
		
		/*while (res < 0)
			res += mod;*/
		//res %= mod;
		Mod(res);
		
		i = j + 1;
	}
	cout<<res<<endl;
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>

#define REP(i,n) for(long (i)=0;(i)<(n);(i)++)
#define FOR(i,a,b) for(long (i)=(a);(i)<(b);(i)++)
#define RREP(i,a) for(long (i)=(a)-1;(i)>=0;(i)--)
#define FORR(i,a,b) for(long (i)=(a)-1;(i)>=(b);(i)--)
#define PI acos(-1.0)
#define DEBUG(C) cout<<C<<endl;
#define VI vector<int>
#define VII vector<VI>
#define VL vector<long>
#define VLL vector<VL>
#define VD vector<double>
#define VDD vector<VD>
#define PII pair<int,int>
#define PDD pair<double,double>
#define PLL pair<long,long>
#define ALL(a) (a).begin(),(a).end()
#define SORT(a) sort(ALL(a))
#define REVERSE(a) reverse(ALL(a))
#define MP make_pair
#define FORE(a,b) for(auto &&a:b)

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF=1e9;
const int MOD=INF+7;

long memfact[200100];
long mempow[200100];

long powmod(long a,long p){
    if(p==0) return 1;
    if(p&1) return a*powmod(a,p-1)%MOD;
    long t=powmod(a,p/2);
    return t*t%MOD;
}

void setting(long n){
    memfact[0]=1;
    FOR(i,1,n+1) memfact[i]=(i*memfact[i-1])%MOD;
    REP(i,n+1) mempow[i]=powmod(memfact[i],MOD-2);
}

long calc(int H,int W){
    H--; W--;
    return memfact[H+W]*mempow[H]%MOD*mempow[W]%MOD;
}

int main (void){
    long H,W,A,B; cin>>H>>W>>A>>B;
    long ans=0;
    setting(H+W+10);
    FOR(i,B,W){
        ans+=(calc(H-A,i+1)*calc(A,W-i))%MOD;
        ans%=MOD;
    }
    cout<<ans<<endl;
}


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

#define int long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

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

template<typename T>
void print1(T begin, T end) {
  while (begin != end) {
    cout << (*begin) << " ";
    *begin++;
  }
  cout << endl;
}

template<typename T>
void print2(T Array, int height, int width) {
  for (int i = 0; i < height; i++) {
    for (int j = 0; j < width; j++) {
      cout << " " << Array[i][j];
    }
    cout << endl;
  }
}

void print() { std::cerr << endl; }
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  std::cerr << head << " ";
  print(std::forward<Tail>(tail)...);
}

template<class T>
void Add(T &a, const T &b, const T &mod=1e9+7) {
  int val = ((a % mod) + (b % mod)) % mod;
  if (val < 0) { val += mod; }
  a = val;
}

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

signed main() {
  int n, k;
  cin >> n >> k;
  int cnt = 0;
  for (int i = 1; i <= n; i+=2) {
    cnt++;
  }
  if (cnt >= k) {
    puts("YES");
  } else {
    puts("NO");
  }

  return 0;
}

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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

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

const ll INF = 1e18;
const int Inf = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
	int n;
	cin >> n;
	vector<int> b(n - 1);
	rep (i, n - 1) cin >> b[i];
	int res = b[0] + b[n - 2];
	FOR (i, 1, n - 1) res += min(b[i - 1], b[i]);
	cout << res << endl;
	
    return 0;
}



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

#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define N 1050

int lcs(string X, string Y) {
    int c[N + 1][N + 1];
    int m    = X.size();
    int n    = Y.size();
    int maxV = 0;

    X = ' ' + X;
    Y = ' ' + Y;

    for (int i = 0; i <= m; i++) c[i][0] = 0;
    for (int j = 1; j <= n; j++) c[0][j] = 0;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (X[i] == Y[j]) {
                c[i][j] = c[i - 1][j - 1] + 1;
            } else {
                c[i][j] = max(c[i - 1][j], c[i][j - 1]);
            }
            maxV = max(maxV, c[i][j]);
        }
    }
    return maxV;
}

int main() {
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout << fixed << setprecision(5);

    string s1, s2;
    int    n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> s1 >> s2;
        cout << lcs(s1, s2) << endl;
    }

    return 0;
}



Measured memory_bytes: 7320
#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 n;
   cin >> n;
   int a[n] = {}, b[n] = {};
   for (int i = 1; i < n; ++i){
      cin >> a[i];
      b[a[i] - 1] += 1;
   }  
   rep(i, n){
      cout << b[i] << endl;
   }
   return 0;
}


Measured memory_bytes: 5200
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <cmath>
 
#define rep(i,n) for(int i = 0;i < (n);i++)
#define all(x) (x).begin(),(x).end()
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)

using namespace std;

typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<pair<int, int> > vpi;
typedef vector<pair<ll, ll> > vpl;

class union_find{
private:
  int p[200000];
  int r[200000];


public:
  union_find(int n){
    for(int i=0;i < n;i++){
      p[i] = i;
      r[i] = 0;
    }
  }
  int find(int x){
    if(p[x] == x){
      return x;
    }else{
      return p[x] = find(p[x]);
    }
  }
  void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return;
  
    if(r[x] < r[y]){
      p[x] = y;
    }else{
      p[y] = x;
      if(r[x] == r[y]) r[x]++;
    }
  }
  bool same(int x, int y){
    return find(x) == find(y);
  }
};
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, k, l;
  cin >> n >> k >> l;
  union_find road(n);
  rep(i,k){
    int p, q;
    cin >> p >> q;
    road.unite(p-1, q-1);
  }
  union_find line(n);
  rep(i,l){
    int r, s;
    cin >> r >> s;
    line.unite(r-1, s-1);
  }

  map<int, map<int, int> >mp;
  rep(i,n){
    mp[road.find(i)][line.find(i)]++;
  }
 
  rep(i,n) cout << mp[road.find(i)][line.find(i)] << " ";
  cout << endl;

	return 0;
}


Measured memory_bytes: 29312
#include <iostream>
#include <algorithm>
#include <string>
#include <cctype>
#include <map>
using namespace std;

map<char, char> sym;

void init() {
  sym['('] = ')';
  sym[')'] = '(';
  sym['['] = ']';
  sym[']'] = '[';
  sym['{'] = '}';
  sym['}'] = '{';
}

bool check(string s, string t) {
  int l = s.size();
  int r = t.size();
  if(l != r) return false;
  //cout << s+"iwi"+t << endl; 
  for(int i=0; i<l; i++) {
    if(sym[s[i]] != t[r-i-1] ) return false;
  }
  return true;
}

string makestr(string str, long long S) {
  string ret;
  int n = str.size();
  
  for(int i=0; i<n; i++) {
    if(S>>i & 1) ret += str[i];
  }
  //cout << ret << endl;
  return ret;
}

int main() {
  init();
  
  string str;
  getline(cin, str);
  
  int pos = str.find("iwi");
  string strL = str.substr(0, pos);
  string strR = str.substr(pos+3);
  int l = strL.size(), r = strR.size();
  
  int mx = 0;
  for(long long S=0; S<(1<<l); S++) {
    for(long long T=0; T<(1<<r); T++) {
      string s = makestr(strL, S);
      string t = makestr(strR, T);
      //cout << s+"iwi"+t << endl;
      if(check(s, t)) {
	mx = max(mx, (int)s.size()+(int)t.size()+3);
      }
    }
  }
  
  cout << mx << endl;
  
  return 0;
}

Measured memory_bytes: 1192
from collections import Counter
N = int(input())
Dlist = list(map(int, input().split()))
M = int(input())
Tlist = list(map(int, input().split()))

Dc = Counter(Dlist)
Tc = Counter(Tlist)
for k, v in Tc.items():
    if Dc[k] < v:
        print("NO")
        break
else:
    print("YES")


Measured memory_bytes: 127828
def find_prime_factor(num):
    if num & 1 == 0:
        return 2
    for i in range(3, int(num ** (1 / 2)) + 1):
        if num % i == 0:
            return i
    return num


def prime_factorization(num):
    subtract = num
    result = []
    while subtract > 1:
        factor = find_prime_factor(subtract)
        result.append(factor)
        subtract //= factor
    return result


n, m = map(int, input().split())

prime_factors = prime_factorization(m)
# prime and prime's power.
power = {}
for prime in prime_factors:
    if prime in power:
        power[prime] += 1
    else:
        power[prime] = 1

# enum all divisors.
divisors = [1]
for prime in power:
    divisors += [divisor * prime ** pw
                 for pw in range(1, power[prime] + 1)
                 for divisor in divisors]
divisors.sort()

answer = 0
for divisor in divisors:
    if divisor <= int(m / n):
        answer = divisor
    else:
        break

print(answer)

Measured memory_bytes: 3064
#include <stdio.h>
int main(void){    
	int N,M,i,j,A[1000],c,b[1000],max_count=0,max_game=-1;  
	scanf("%d%d",&N,&M);  
	for(i=0;i<N;i++){  
        scanf("%d",&A[i]);          
	b[i]=0;   
}    
 for(i=0;i<M;i++){   
      scanf("%d",&c);   
      for(j=0;j<N;j++){     
        if(A[j]<=c){
	b[j]++;
	break;
}   
} 
}    
   for(i=0;i<N;i++){        
 if(max_count<b[i]){    
         max_count=b[i];     
        max_game=i;      
   }    
 }      
 printf("%d\n",max_game+1);
return 0;
 } 

Measured memory_bytes: 604
s = input()
s = s.replace('BC', 'D')
lst = list(s)

acount = 0
ans = 0
for i in range(len(s)):
    if s[i] == 'A':
        acount += 1
    elif s[i] == 'D':
        ans += acount
    else:
        acount = 0

print(ans)

Measured memory_bytes: 4840
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <stdio.h>
#include <complex>
#include <cstdint>
#include <tuple>

#define M_PI       3.14159265358979323846

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define MOD 1000000009

int a[3];

int main() {
	REP(i, 3)scanf("%d", &a[i]);
	sort(a, a + 3);
	int f1 = (a[1] - a[0]) % 2;
	int f2 = (a[2] - a[0]) % 2;
	if (f1 == 0 && f2 == 0) {
		cout << (a[2] - a[0]) / 2 + (a[2] - a[1]) / 2 << endl;
		return 0;
	}
	else if(f1 == 0 && f2 == 1){
		a[0]++;
		a[1]++;
		cout << (a[2] - a[0]) / 2 + (a[2] - a[1]) / 2 + 1<< endl;
		return 0;
	}
	else if (f1 == 1 && f2 == 0) {
		a[0]++;
		a[2]++;
		cout << (a[2] - a[0]) / 2 + (a[2] - a[1]) / 2 + 1 << endl;
		return 0;
	}
	else{
		a[1]++;
		a[2]++;
		cout << (a[2] - a[0]) / 2 + (a[2] - a[1]) / 2 + 1 << endl;
		return 0;
	}

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
static const int INF (1<<30);

int main() {
  int N, M; cin >> N >> M;
  priority_queue<double> p;
  //ll ans = 0LL;
  rep(i, N) {
    int a; cin >> a;
    //ans += (ll)a;
    p.push((double)a);
  }

  while(!p.empty() && M > 0) {
    double y = p.top(); 
    p.pop();

    y /= 2.0;
    if (y >= 1.0) p.push(y);
    M--;
  }


  ll ans = 0LL;
  while(!p.empty()) {
    ll y = (ll)p.top();
    p.pop();
    ans += y;
  }

  cout << ans << endl;

  return 0;
}


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

using namespace std;
using vecint = vector<int>;
using ll = int64_t;
using ld = long double;

int main()
{
  ll r,c,n;
  cin>>r>>c>>n;
  vector<tuple<ld, int>> vp;
  REP(i,n) {
    ll x1,x2,y1,y2;
    cin>>x1>>y1>>x2>>y2;
    if (((x1==0||x1==r)||(y1==0||y1==c))
        && ((x2==0||x2==r)||(y2==0||y2==c))) {
      vp.emplace_back(arg(complex<ld>(x1-r/2.0, y1-c/2.0)), i);
      vp.emplace_back(arg(complex<ld>(x2-r/2.0, y2-c/2.0)), i);
    }
  }
  sort(ALL(vp));
  stack<int> s;
  int m = vp.size();
  REP(i,m){
    int v = get<1>(vp[i]);
    if (!s.empty() && s.top() == v) s.pop();
    else s.push(v);
  }
  if (s.empty()) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
  return 0;
}

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

#define ll long long

int main()
{
    ll i, n, k, x, y;
    cin >> n >> k;

    int a[n+1], used[n+1];
    vector <int> v;

    a[0]=0;
    for(i=1; i<=n; i+=1)
        cin >> a[i];
    memset(used, 0, sizeof(used));
    used[0]=1;

    x=1;
    while(!used[x])
    {
        v.push_back(x);
        used[x]=1;
        x=a[x];
    }

    y=v.size();
    k+=1;
    for(i=0; i<y; i+=1)
    {
        k-=1;
        if(k==0)
            break;
        if(v[i]==x)
            break;
    }
    if(v[i]==x)
    {
        x=y-i;
        k%=x;
        cout << v[i+k] << endl;
    }
    else
        cout << v[i] << endl;
}

Measured memory_bytes: 5812
#include<bits/stdc++.h>
using namespace std;
#define rkc ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
#define fl(i,a,b) for(ll i=a;i<b;i++)
#define rfl(i,a,b) for(ll i=a;i>b;i--)
#define pb push_back
#define mp make_pair
#define test ll t;cin>>t;while(t--)
#define lld long double
const ll M = 1e9 + 7;
const double pi  =3.141592653589793238463;
int main()
{
    ll a,b;
    cin>>a>>b;
    if(a>b)
    cout<<2*a-1;
    else if(a<b)
    cout<<2*b-1;
    else
    cout<<a+b;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using Graph = vector<vector<int>>;

int c=0;
vector<bool> seen;
vector<vector<int>> s;

void dfs(const Graph &G, int v) {
    seen.at(v) = 1;
    for(auto nv : G.at(v)) {
        if(seen.at(nv))
            continue;
        s.at(c).push_back(nv);
        dfs(G, nv);
    }
}

int main() {
    int N,M,x,y,r=0;
    cin >> N >> M;
    vector<int> p(N);
    Graph G(N);
    vector<set<int>> st(N);

    rep(i,N)
        cin >> p.at(i);

    rep(i,M) {
        cin >> x >> y;
        --x, --y;
        G.at(x).push_back(y);
        G.at(y).push_back(x);
    }

    seen.assign(N, 0);
    s.assign(N, vector<int>());
    rep(i,N) {
        if(seen.at(i))
            continue;
        s.at(c).push_back(i);
        dfs(G, i);
        ++c;
    }

    rep(i,N) {
        if(s.at(i).size() == 0)
            break;
        rep(j,s.at(i).size())
            st.at(i).insert(p.at(s.at(i).at(j)));
    }
    
    rep(i,N) {
        if(s.at(i).size() == 0)
            break;
        rep(j,s.at(i).size())
            if(st.at(i).count(s.at(i).at(j)+1))
                ++r;
    }

    cout << r << endl;
}

Measured memory_bytes: 22264
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define all(a) (a).begin(),(a).end()

using P = pair<int,int>;

// bool operator<(const P a, const P b) {
//     return a.first != b.first ? a.first < b.first : a.second > b.second;
// }

int main(void){
    int n,m;
    cin>>n>>m;
    vector<P> v(m);
    rep(i,m){
        int a,b;
        cin>>a>>b;
        v[i] = P(a,b);
    }
    sort(all(v));
    priority_queue<int,vector<int>,greater<int>> qu;
    int res = 0;
    rep(i,m){
        int a = v[i].first;
        int b = v[i].second;
        if(qu.size() && qu.top() <= a){
            res++;
            while(qu.size()) qu.pop();
            // while(qu.size() && qu.top() <= a){
            //     qu.pop();
            // }
        }
        qu.push(b);
    }
    cout<<res+1<<endl;
    return 0;
}


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

    class Program
    {
        static void Main(string[] args)
        {
            var ABCD = Console.ReadLine().Split(' ').Select(s=>int.Parse(s)).ToArray();
            Console.WriteLine(Math.Max(ABCD[0]* ABCD[1], ABCD[2]* ABCD[3]));
        }
    }

Measured memory_bytes: 13268
A,B,H,M = map(int,input().split())

import math
angle_a = 2*math.pi*(H+M/60)/12
angle_b = 2*math.pi*M/60


ax = A*math.cos(angle_a)
ay = A*math.sin(angle_a)
bx = B*math.cos(angle_b)
by = B*math.sin(angle_b)

dx = abs(ax-bx)
dy = abs(ay-by)
ans = math.sqrt(dx**2 + dy**2)
print(ans)





Measured memory_bytes: 9576
#include<iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N_MAX = 100001;
typedef pair<int,int> P;
int main()
{
  long long n,m;
  cin >> n >> m;
  P b[N_MAX];
  int c[N_MAX],nc[N_MAX],pc[N_MAX],pi[N_MAX];
  long long res[N_MAX];
  int i1,i2,s1,s2,p,pt;
  long long c1,c2;
  for(int i=0;i<m;i++)
    cin >> b[i].first >> b[i].second;
  for(int i=1;i<=n;i++){
    c[i]=i;
    nc[i]=1;
    pc[i]=i;
    pi[i]=0;
  }
  res[m-1]=n*(n-1)/2;
  for(int i=m-1;i>0;i--){
    i1=b[i].first;
    i2=b[i].second;
    if(c[i1]==c[i2])
      res[i-1]=res[i];
    else{
      s1=c[i1]; s2=c[i2];
      if(nc[s1]<nc[s2]){
        s1=c[i2]; s2=c[i1];
      }
      res[i-1]=res[i]-nc[s1]*nc[s2];
      pt=pc[s1];
      p=pc[s2];
      pc[s1]=p;
      nc[s1]+=nc[s2];
      pc[s2]=0;
      nc[s2]=0;
      while(true){
        c[p]=s1;
        if(pi[p]==0) break;
        p=pi[p];
      }
      pi[p]=pt;
    }
  }
  for(int i=0;i<m;i++)
    cout << res[i] << endl;
  return 0;
}

Measured memory_bytes: 4480
#include <math.h>
#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

using ll = long long;

string s, t;
vector<string> v;

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

    int e = s.size() - t.size() + 1;

    for (int i = 0; i < e; i++) {
        if (s[i] == '?' || s[i] == t[0]) {
            bool b = true;
            for (int j = i + 1, k = 1; j < i + t.size(); j++, k++) {
                if (s[j] == '?' || s[j] == t[k]) { b = true; }
                else { b = false; break; }
            }

            if (b) {
                string temp = s;
                for (int j = i, k = 0; j < i + t.size(); j++, k++) {
                    temp[j] = t[k];
                }

                v.push_back(temp);
            }
        }
    }

    if (v.empty()) {
        cout << "UNRESTORABLE" << endl;
        return 0;
    }

    string ans = v[0];
    for (int i = 1; i < v.size(); i++) {
        string cmp = v[i];
        for (int j = 0; j < cmp.size(); j++) {
            if (cmp[j] < ans[j]) { ans = cmp; break; }
        }
    }

    for (int i = 0; i < ans.size(); i++) {
        if (ans[i] == '?') { ans[i] = 'a'; }
    }
    
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
//1時間
import java.util.Scanner;

public class Main {
//java11
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();

		int[] A = new int[N];
		int[][] x = new int[N][];
		int[][] y = new int[N][];
		for(int i=0; i<N; i++) {
			A[i] = sc.nextInt();
			x[i] = new int[A[i]];
			y[i] = new int[A[i]];
			for(int j=0; j<A[i]; j++) {
				x[i][j] = sc.nextInt();
				y[i][j] = sc.nextInt();
			}
		}

		int ans = 0;
		for(int i=0; i<(1 << N); i++) {
			int honest_n = 0;
			boolean check = true;
			Outside:
			for(int j=0; j<N; j++) {
				if((1 & (i >> j)) == 1) {
					//正直者
					for(int k=0; k<A[j]; k++) {
						if(y[j][k] != (1 & (i >> (x[j][k]-1) ))){
							check = false;
							break Outside;
						}
					}
					honest_n++;
				}

			}

			if(check)
				ans = Math.max(ans, honest_n);
		}

		System.out.println(ans);
	}

}


Measured memory_bytes: 25300
n, m = map(int, input().split())
G = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)

ans = [-1] * n
from collections import deque
d = deque([0])
while d:
    u = d.popleft()
    for v in G[u]:
        if ans[v] == -1:
            ans[v] = u
            d.append(v)

if -1 in ans[1:]:
    print('No')
else:
    print('Yes')
    for v in ans[1:]:
        print(v + 1)


Measured memory_bytes: 98324
n, m = map(int, input().split())
*a, = map(int, input().split())
bc = [list(map(int, input().split())) for _ in range(m)]

a.sort()
bc.sort(key=lambda x:-x[1])
i = 0

for b,c in bc:
    for j in range(i, min(n, i+b)):
        if a[j]<c:
            a[j] = c
    i = i+b
print(sum(a))


Measured memory_bytes: 36172
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in); // ??\???????????????
		StringBuilder out = new StringBuilder(); // ??¨?????¨??¢??°
		StringBuilder output = new StringBuilder(); // #,\n???????´?????????¢??°

		while (true) { // ???????????????
			int H = sc.nextInt(); // ????????\??????
			int W = sc.nextInt(); // ?¨??????\??????

			if (H + W == 0) // ?????¨?¨????0 0????????????
				break;

			for (int i = 0; i < H; i++) {// ????????°???????????????
				for (int j = 0; j < W; j++) {// ?¨??????°???????????????
					if ((i == 0 || i == H - 1) || (j == 0 || j == W - 1)) { // ????????§?±??????????????????????
						out = out.append("#");
					} else {
						out = out.append(".");
					}
				}
				out = out.append("\n");
			}
			output = output.append(out + "\n"); // ????´???????#,\n???????´?
			out.delete(0, out.length()); // ??¨?????¨out????????????
		}
		System.out.print(output); // ??????
		sc.close();
	}

}

Measured memory_bytes: 28076
#include <bits/stdc++.h>
using namespace std;
int n, que[4005], ql, qr;
long long x, a[4005];
int main() {
	scanf("%d%lld", &n, &x);
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), a[i + n] = a[i];
	long long ans = 1ll << 60;
	for (int l = 0; l < n; l++) {
		ql = 1; qr = 0;
		for (int i = n + 1 - l; i <= n; i++) {
			while (ql <= qr && a[que[qr]] >= a[i]) qr--;
			que[++qr] = i;
		}
		long long sum = l * x;
		for (int i = n + 1; i <= 2 * n; i++) {
			while (ql <= qr && a[que[qr]] >= a[i]) qr--;
			que[++qr] = i;
			while (ql <= qr && que[ql] < i - l) ql++;
			sum += a[que[ql]];
		}
		ans = min(ans, sum);
	}
	printf("%lld\n", ans);
	return 0;
}

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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod =(1e9)+7;
using P = pair<ll,ll>;

int main(){
   string s;cin >>s;
   vector<int>direction(4,-1);
   char x[4]={'N','S','W','E'};
    for (int i = 0; i < s.size(); ++i) {
        for (int j = 0; j < 4; ++j) {
            if (s[i] == x[j])direction[j] += 2;
        }
    }
    if(direction[0]*direction[1]<0||direction[2]*direction[3]<0)puts("No");
    else puts("Yes");
   return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <string>
#include <stack> // s.top()
#include <bitset>
#include <queue> // s.front()
using namespace std;
using Graph = vector<vector<pair<int, int> > >;
typedef long long ll;
typedef pair<int, int> P;
#define print(x) cout<<(x)<<endl
#define INF10 10000000000
#define INF5 100000
#define EPS 1e-10
const int MAX = 2100;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}



int main() {
	int K, N; cin >> N >> K;
	COMinit();

	for (int i = 0; i < K; i++) {
		cout << COM(N - K + 1, i + 1) * COM(K - 1, i) % MOD << endl;
	}




	return 0;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for (int i = 0; i < n; i++) {
			String str = sc.next();
			System.out.println(parse(str));
		}
	}

	private static int parse(String s) {
//System.err.println(s);
		if (s.matches("^\\[\\d*\\]$")) {
			int x = Integer.parseInt(s.substring(1, s.length() - 1));
//System.out.println(x);
			return x / 2 + 1;
		} else {
			List<Integer> list = new ArrayList<Integer>();
			int count = 0;
			int start = 1;
			for (int i = 1; i < s.length(); i++) {
				if (s.charAt(i) == '[') {
					count++;
				} else if (s.charAt(i) == ']') {
					count--;
					if (count == 0) {
						int x = parse(s.substring(start, i + 1));
						list.add(x);
						start = i;
					}
				}
			}
			Collections.sort(list);
			int sum = 0;
			for (int i = 0; i < list.size() / 2 + 1; i++) {
				sum += list.get(i);
			}
			return sum;
		}
	}
}

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

#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,m,n) for(int i=m;i<(n);i++)
const int MAX = 101;
int siz[MAX],par[MAX],Rank[MAX];
void init(int n){
    REP(i,n){
        par[i]=i;
        Rank[i]=0;
        siz[i]=1;
    }
}
int find(int x){
    if(par[x]==x)return x;
    else return par[x]=find(par[x]);
}
void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return;
    if(Rank[x]<Rank[y]){
        par[x]=y;
        siz[x]+=siz[y];
        siz[y]=siz[x];
    }
    else{
        siz[y]+=siz[x];
        siz[x]=siz[y];
        par[y]=x;
        if(Rank[x]==Rank[y])Rank[x]++;
    }
}
bool same(int x,int y){
    return find(x)==find(y);
}

void solve(){
    int N;cin>>N;
    if(N==0)exit(0);
    vector<bitset<50>>dp;
    dp.resize(N);
    REP(i,N){
        dp[i][i]=true;
    }
    vector<vector<int>>yote;
    yote.resize(31);
    REP(i,N){
        int K;cin>>K;
        REP(_,K){
            int d;cin>>d;
            yote[d].push_back(i);
        }
    }
    FOR(d,1,31){
        for(auto x:yote[d])for(auto y:yote[d]){
            dp[x]=dp[y]=dp[x]|dp[y];
            if(dp[x].count()==N){
                cout<<d<<endl;;return;
            }
        }

    }
    cout<<-1<<endl;
}
signed main(){
    while(true){
        solve();
    }
}


Measured memory_bytes: 3144
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
const int MOD=1000000007;
#define VAR(type,...) type __VA_ARGS__;in(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);each(x, name)in(x)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(a-1);i>=(b);--i)
#define each(x,v) for(auto &x:(v))
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<(x)<<endl
void in(){} template<class T,class... U> void in(T &t,U &...u){cin>>t;in(u...);}
void solve();
int main(){cin.tie(0);ios::sync_with_stdio(0);solve();}

void solve() {
  VAR(int, N, M);
  print(((N - M) * 100 + M * 1900) * pow(2, M));
}


Measured memory_bytes: 384
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = 0
for i in range(N):
  ans += B[A[i]-1]
  if A[i] - A[max(i-1,0)] == 1:
    ans += C[A[i-1]-1]
  
print(ans)

Measured memory_bytes: 3064
#define  _CRT_SECURE_NO_WARNINGS

#pragma comment(linker, "/STACK:256000000")

#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <deque>
#include <queue>
#include <iomanip>
#include <fstream>
#include <string>

#define ll long long 
#define ld long double 
#define fi(n) for(int i = 0; i < (n); i++)
#define FOR(i, k, n) for(int i = (k); i < (n); i++)

//const int INF = 2147483647;
const int INF = 1e9;
const long long lINF = 9223372036854775807;

using namespace std;

//#define cin in
//#define cout out

ifstream in;
ofstream out;

int main()
{
	in.open("input.txt");
	out.open("output.txt");
	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> s(n), c(m);
	fi(n)
		cin >> s[i].first >> s[i].second;
	fi(m)
		cin >> c[i].first >> c[i].second;
	vector<int> answ(n);
	fi(n)
	{
		ll mindist = lINF;
		FOR(j, 0, m)
		{
			if (mindist > abs(s[i].first - c[j].first) + abs(s[i].second - c[j].second))
				answ[i] = j + 1, mindist = abs(s[i].first - c[j].first) + abs(s[i].second - c[j].second);
		}
	}
	for (auto e : answ)
		cout << e << endl;
	return 0;
}

Measured memory_bytes: 256
main :: IO ()
main = do
  a <- readLn :: IO Int
  b <- readLn :: IO Int
  c <- readLn :: IO Int 
  d <- readLn :: IO Int
  e <- readLn :: IO Int
  k <- readLn :: IO Int

  let ans = calc e a k
  putStrLn ans
  

calc :: Int -> Int -> Int -> String
calc e a k = do
  case e - a > k of
    True -> ":("
    False ->"Yay!"



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

using namespace std;
const int N = 2010;

int n, k, p[N], ans = N;
vector<int> g[N];
bool vis[N];
queue< pair<int, int> > q;

void dfs(int node) {
	for (int v : g[node]) {
		if (p[v] == 0) {
			p[v] = node;
			dfs(v);
		}
	}
	return;
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(NULL);

	cin >> n >> k;

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

	dfs(1);

	for (int i = 1; i <= n; i++) {
		int cur = 0;
		q.push({ i, 0 });
		memset(vis, 0, sizeof(vis));
		if (k % 2 == 1) q.push({ p[i], 0 });
		while (!q.empty()) {
			int node = q.front().first;
			int dist = q.front().second;
			q.pop();
			if (vis[node]) continue;
			vis[node] = true;
			if (dist > k / 2) cur++;
			for (int v : g[node]) {
				if (!vis[v]) q.push({ v, dist + 1 });
			}
		}
		ans = min(ans, cur);
	}

	cout << ans << '\n';

	//system("PAUSE");
	return 0;

}

Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<climits>
#include<vector>
#include<utility>//pair
#include<cmath>//abs,sqrt
#include<cstring>
#include<map>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define prin(arg) cout<<arg<<"\n"
#define prin2(arg1,arg2) cout<<arg1<<" "<<arg2<<"\n"
#define fill(arg,n) memset(arg,n,sizeof(arg))
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int INF=1e+9;
const ll INFLL=1e+17;
int n,m;
int a[200010],b[200010];
struct edge{//辺の情報
  int to,cost;
};
vector<edge> g[200010];
int d[200010];//d[u]は始点から頂点uへの最短距離

void add_edge(int from,int to,int cost){//無向グラフを作成
  g[from].push_back((edge){to,cost});
  g[to].push_back((edge){from,cost});
}

void dijkstra(int s){//始点sからのダイクストラ
  priority_queue<pi,vector<pi>,greater<pi> > q;//pair(コスト、頂点)としてコストの小さい順に並ぶ
  rep(i,n){
    d[i]=INF;//初期化
  }
  d[s]=0;
  q.push(pi(0,s));
  while(!q.empty()){
    pi p = q.top();q.pop();
    int w=p.second;//最新の確定した頂点
    if(d[w]<p.first) continue;//取り出した頂点のコストが最短コストより長かったら破棄
    for(int i=0;i<g[w].size();i++){//取り出した頂点と隣接した頂点を調べる
      int t=g[w][i].to,c=g[w][i].cost;
      if(d[t]>d[w]+c){//頂点tまでの暫定最短距離よりwまでの最短距離+w→tのコストが小さければ更新
	d[t]=d[w]+c;
	q.push(pi(d[t],t));
      }
     }
  }
}


int main(){
  cin>>n>>m;
  rep(i,m){
    cin>>a[i]>>b[i];
    a[i]--;b[i]--;
  }
  rep(i,m){
    add_edge(a[i],b[i],1);
  }
  dijkstra(0);
  if(d[n-1]<=2){
    prin("POSSIBLE");
  }
  else{
    prin("IMPOSSIBLE");
  }

  

  return 0;
}


Measured memory_bytes: 16616
#include<stdio.h>
#include<stdlib.h>
int main(){
    int a[100], l=0;
    char x[100];
    while(scanf("%s", x)!=EOF){
        if(x[0]=='+')a[l-2]+=a[l-1], l--;
        else if(x[0]=='-')a[l-2]-=a[l-1], l--;
        else if(x[0]=='*')a[l-2]*=a[l-1], l--;
        else a[l++]=atoi(x); 
    }
    printf("%d\n", a[0]);
    return 0;
}

Measured memory_bytes: 548