akhauriyash/Code-Regression huggingface dataset:
import sys

input = lambda :sys.stdin.readline().rstrip()

def main():
    n, m, Q = map(int, input().split())
    Train= [[0 for _ in range(n)] for _ in range(n)]
    
    for i in range(m):
        l, r = map(int, input().split())
        l, r = l - 1, r - 1
        Train[l][r] += 1
    
    P_Train = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(n):
        for j in range(n):
            P_Train[i + 1][j + 1] = P_Train[i][j + 1] + P_Train[i + 1][j] + Train[i][j] - P_Train[i][j]
    
    #print(*P_Train, sep = '\n')

    for i in range(Q):
        p, q = map(int, input().split())
        p, q = p - 1, q - 1
        ans = solve(P_Train, p, q)
        print(ans)

def solve(P_Train, p, q):
    ans = 0
    ans = P_Train[q + 1][q + 1] -P_Train[p][q + 1] - P_Train[q + 1][p] + P_Train[p][p]
    return ans


if __name__ == '__main__':
    main()

Measured memory_bytes: 15784
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;

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

struct point_t {
    int f;
    int s;
};

const point_t points[] = {
    {1, 0},
    {0, 1},
    {-1, 0},
    {0, -1},
};

int max_dist;
int H, W, i, j;

bool is_in_field(int H, int W, const point_t &point) {
    const int f = point.f;
    const int s = point.s;
    return (0 <= f && f < H && 0 <= s && s < W);
}

int main() {

    cin >> H >> W;
    vector<vector<int>> dist(H, vector<int>(W, -1));
    queue<point_t> q;

    char buf;
    REP(i, H) {
        REP(j, W) {
            cin >> buf;
            if(buf == '#') {
                dist[i][j] = 0;
                q.push({i, j});
            }
        }
    }

    while(!q.empty()) {
        point_t cur = q.front();
        q.pop();
        for(const point_t &point : points) {
            point_t next = {cur.f + point.f, cur.s + point.s};
            if(!is_in_field(H, W, next)) continue;
            if(dist[next.f][next.s] == -1) {
                dist[next.f][next.s] = dist[cur.f][cur.s] + 1;
                q.push(next);
            }
        }
    }

    int max_dist = 0;
    REP(i, H) {
        REP(j, W) {
            if(max_dist < dist[i][j]) {
                max_dist = dist[i][j];
            }
        }
    }

    cout << max_dist << endl;
}


Measured memory_bytes: 12432
import std.stdio, std.string, std.conv, std.range;
import std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, std.random, core.bitop;

void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}



enum inf = 1_001_001_001;
enum infl = 1_001_001_001_001_001_001L;


void main() {
    int N, Q;
    scan(N, Q);
    auto a = readln.split.to!(int[]).assumeSorted;

    auto kogo = new long[](N + 1);
    kogo[1] = (N % 2 ? a[0] : 0);
    kogo[2] = (N % 2 == 0 ? a[1] : 0);
    foreach (i ; 2 .. N + 1) {
        kogo[i] = kogo[i - 2] + a[i - 1];
    }

    auto as = new long[](N + 1);
    foreach (i ; 1 .. N + 1) {
        as[i] = as[i - 1] + a[i - 1];
    }

    // tkが上から連続してk個取れるか？
    bool check(int x, int k) {
        if (a[N - k] <= x) {
            return false;
        }
        if (k + k - 1 > N) {
            return false;
        }

        auto d = abs(a[N - k] - x);
        int c = a.lowerBound(x + d).upperBound(x - d - 1).length.to!int;
        return c >= k - 1;
    }

    long f(int x) {
        int ok = 0, ng = N;
        while (abs(ok - ng) > 1) {
            auto mid = (ok + ng) / 2;
            (check(x, mid) ? ok : ng) = mid;
        }
        debug {
            writeln("ok: ", ok);
        }
        auto ans = as[N] - as[N - ok] + kogo[max(0, N - 2*ok)];
        return ans;
    }

    foreach (_ ; 0 .. Q) {
        int xi;
        scan(xi);
        auto ans = f(xi);
        writeln(ans);
    }
}


Measured memory_bytes: 9384
# frozen_string_literal: true

def show(x)
  puts case x
       when 1 then 'Left'
       when -1 then 'Right'
       else 'Balanced'
       end
end

def solve(xs)
  xs[0] + xs[1] <=> xs[2] + xs[3]
end

show solve gets.split.map(&:to_i)


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

int main() {
  int N, K; cin >> N >> K;
  vector<int> A(N); for (auto &x : A) cin >> x;
  sort(A.begin(), A.end(), greater<int>());
  int ans = 0;
  for (int i = 0; i < K; i++) {
    ans += A[i];
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <queue>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<29;

// dice<hoge> di(arr); ÈÇÆé¾·é
// ±ÌÆ«AarrÍ hoge di[6];Åé¾³êÄ¨èAid ÌlÌÉÊÌlªi[³êÄ¢éKvª éB
// á¦ÎAid[TOP] = 3 ÈçÎAdi[3] ÌlªTOPÉÝè³êéB
// TCRÆµÄµ¢©Ç¤©Ì»èÉ equivalent_to ðg¤B
enum FACE { TOP, BOTTOM, FRONT, BACK, LEFT, RIGHT };
template <class T>
class dice {
public:
  dice(T *v) {
    id[TOP] = 0; id[FRONT] = 1; id[LEFT] = 2;
    id[RIGHT] = 3; id[BACK] = 4; id[BOTTOM] = 5;
    REP(i,6)
      var[i] = v[i];
  }
  T& operator[] (FACE f) { return var[id[f]]; }
  const T& operator[] (FACE f) const { return var[id[f]]; }
  bool operator==(const dice<T>& b) const {
    const dice<T> &a = *this;
    return a[TOP] == b[TOP] && a[BOTTOM] == b[BOTTOM] &&
           a[FRONT] == b[FRONT] && a[BACK] == b[BACK] &&
           a[LEFT] == b[LEFT] && a[RIGHT] == b[RIGHT];
  }
  void roll_x() { roll(TOP, BACK, BOTTOM, FRONT); }
  void roll_y() { roll(TOP, LEFT, BOTTOM, RIGHT); }
  void roll_z() { roll(FRONT, RIGHT, BACK, LEFT); }
  vector<dice> all_rolls() {
    vector<dice> ret;
    for (int k = 0; k < 6; (k&1?roll_y():roll_x()),++k)
      for (int i = 0; i < 4; roll_z(), ++i)
        ret.push_back(*this);
    return ret;
  }
  bool equivalent_to(const dice& di) {
    for (int k = 0; k < 6; (k&1?roll_y():roll_x()),++k)
      for (int i = 0; i < 4; roll_z(), ++i)
        if (*this == di) return true;
    return false;
  }
private:
  void roll(FACE a, FACE b, FACE c, FACE d) {
    int tmp = id[a];
    id[a] = id[b]; id[b] = id[c];
    id[c] = id[d]; id[d] = tmp;
  }
  T var[6];
  int id[6];
};


int main() {
  int arr[] = {1,2,4,3,5,6};
  int n;
  while(cin >> n, n) {
    dice<int> di(arr);
    int res = 0;
    REP(i,n) {
      string s;
      cin >> s;
      if (s == "North") {
        di.roll_x();di.roll_x();di.roll_x();
      } else if (s == "East") {
        di.roll_y();
      } else if (s == "West") {
        di.roll_y();di.roll_y();di.roll_y();
      } else if (s == "South") {
        di.roll_x();
      } else if (s == "Right") {
        di.roll_z();
      } else {
        di.roll_z();di.roll_z();di.roll_z();
      }
      res += di[TOP];
    }
    cout << res+1<< endl;
  }
}

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

int main(){
    using ull = unsigned long long;
    ull money;
    cin >> money;

    ull present = 100;
    int year = 0;
    while(present < money){
        present = (ull)(present * 1.01);
        year++;
    }

    cout << year << endl;
}

Measured memory_bytes: 3592
#include <stdio.h>

int main()
{
	int m, n, tmp;
	scanf("%d %d", &m, &n);
	if (m < n)
	{
		tmp = m;
		m = n;
		n = tmp;
	}
	for (;;)
	{
		tmp = m % n;
		m = n;
		n = tmp;
		if (n == 0) break;
	}
	printf("%d\n", m);
	return 0;
}



Measured memory_bytes: 2104
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,N) for(i=0;i<N;i++)

int N,M;
int main(void){
  int C;
  cin >> N >> M >> C;
  int i,j,sum,num = 0;
  int B[M];
  FOR(j,M) cin >> B[j];
  int A[N][M];
  FOR(i,N)FOR(j,M) cin >> A[i][j];
  FOR(i,N){
    sum=C;
    FOR(j,M){
      sum += B[j]*A[i][j];
    }
    if(sum > 0) num++;
  }
  cout << num << endl;
  return 0;
}

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

using namespace std;

bool sosuu(int n) {
	for(int i = 2; i <= sqrt(n); i++) {
		if(n % i == 0) {
			return false;
		}
	}
	return true;
}

int main(void) {
	int num;
	while(1) { 
		cin >> num;
		if(num == 0) {
			break;
		}

		int sum = 0;
		for(int i = num + 1; i <= num * 2; i++) {
			if(sosuu(i)) {
				sum++;
			}
		}

		cout << sum << endl;
	}
	return 0;
}
			

Measured memory_bytes: 3088
/*
    Created by Ezio112
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define inf ll(10e16)
#define mod ll(10e8+7)
#define ff first
#define ss second
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    ll t;
    //cin>>t;
    t=1;
    while(t--)
    {
        ll a,b,n;
        cin>>a>>b>>n;
        ll i=min(b-1,n);
        cout<<(a*i)/b-a*(i/b)<<endl;
    }
    return 0;
}


Measured memory_bytes: 3604
'use strict';
function main(input) {
    input = input.split("\n");
    const num = input[0];
    const students = input[1].split(" ");
    const visited = [];
    for(let i=0; i<num; i++) {
        visited[students[i]-1] = i+1;
    }

    let res = "";
    for(let i=0; i<num; i++) {
        res += visited[i] + ' ';
    }

    return res;
}

var input = require("fs").readFileSync("/dev/stdin", "utf8");
console.log(main(input));

Measured memory_bytes: 34788
package main

import(
  "fmt"
  "bufio"
  "os"
  "strconv"
)

func main() {
  //fmt.Print("Input :")
  sc := bufio.NewScanner(os.Stdin)
  sc.Split(bufio.ScanWords)

  var h int
  var w int

  for {
    if sc.Scan() { h, _ = strconv.Atoi(sc.Text()) }
    if sc.Scan() { w, _ = strconv.Atoi(sc.Text()) }

    if h == 0 && w == 0 { break }
    for i := 0; i < h; i++ {
      for j := 0; j < w; j++ {
        fmt.Print("#")
      }
      fmt.Println()
    }
    fmt.Println()
  }
}



Measured memory_bytes: 1096
#include <iostream>
#include <stdio.h>
using namespace std;

int main(){
	char c[1200];
	fgets(c,1200,stdin);
	for (int i = 0;i<1200;i++){
			if (c[i] == '\n') break;
			if (islower(c[i])) c[i] = toupper(c[i]);
			else if (isupper(c[i])) c[i] = tolower(c[i]);
			printf("%c",c[i]);
		
			
	}
	printf("\n");
	/*
	char c;
		while(1){
		scanf("%c",&c);
			if (c == '\n') break;
			if (islower(c)) c = toupper(c);
			else if (isupper(c)) c = tolower(c);
			printf("%c",c);s
		
			
	}
	printf("\n");*/
	return 0;
}

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

constexpr int MAX = 500010;

struct Node{
  int key;
  int priority;
  Node* left;
  Node* right;
  Node* p;
};

Node gT[MAX];
Node* gRoot = nullptr;

Node* Delete( Node* t, int key );
Node* _Delete( Node* t, int key );

Node* RotateRight( Node* t ){
  Node* s = t->left;
  t->left = s->right;
  s->right = t;
  return s;
}

Node* RotateLeft( Node* t ){
  Node* s = t->right;
  t->right = s->left;
  s->left = t;
  return s;
}

Node* MakeNode( int k, int p ){
  Node* x = new Node;
  x->key = k;
  x->priority = p;
  x->left = x->right = x->p = nullptr;
  return x;
}

Node* Insert( Node* t, int key, int priority ){
  if( t == nullptr ){
    Node* x;
    return x = MakeNode( key, priority );
  }
  if( key == t->key ){
    return t;
  }

  if( key < t->key ){
    t->left = Insert( t->left, key, priority );
    if( t->priority < t->left->priority ){
      t = RotateRight( t );
    }
  }else{
    t->right = Insert( t->right, key, priority );
    if( t->priority < t->right->priority ){
      t = RotateLeft( t );
    }
  }
  return t;
}

Node* Find( int k ){
  Node* x = gRoot;
  while( x != nullptr ){
    if( k == x->key ) return x;
    if( k < x->key ) x = x->left;
    else x = x->right;
  }
  return nullptr;
}

Node* Delete( Node* t, int key ){
  if( t == nullptr ) return nullptr;
  if( key < t->key ) t->left = Delete( t->left, key );
  else if( key > t->key ) t->right = Delete( t->right, key );
  else return _Delete( t, key );
  return t;
}

Node* _Delete( Node* t, int key ){
  if( t->left == nullptr && t->right == nullptr ) return nullptr;
  else if( t->left == nullptr ) t = RotateLeft( t );
  else if( t->right == nullptr ) t = RotateRight( t );
  else{
    if( t->left->priority > t->right->priority ){
      t = RotateRight( t );
    }else{
      t = RotateLeft( t );
    }
  }
  return Delete( t, key );
}


void Inorder( Node* s ){
  if( s == nullptr ) return;

  Inorder( s->left );
  cout << " " << s->key;
  Inorder( s->right );
}

void Preorder( Node* s ){
  if( s == nullptr ) return;

  cout << " " << s->key;
  Preorder( s->left );
  Preorder( s->right );
}

int main(){
  for( int i = 0; i < MAX; i++ ){
    gT[i].left = gT[i].right = gT[i].p = nullptr;
  }
  
  int m; cin >> m;
  for( int i = 0; i < m; i++ ){
    char cmd[10]; cin >> cmd;
    if( cmd[0] == 'i' ){
      int key, p; cin >> key >> p;
      gRoot = Insert( gRoot, key, p );
    }else if( cmd[0] == 'p' ){
      Inorder( gRoot ); cout << endl;
      Preorder( gRoot ); cout << endl;
    }else if( cmd[0] == 'f' ){
      int key; cin >> key;
      if( Find( key ) != nullptr ) cout << "yes" << endl;
      else cout << "no" << endl;
    }else if( cmd[0] == 'd' ){
      int key; cin >> key;
      gRoot = Delete( gRoot, key );
    }
  }
}



Measured memory_bytes: 28112
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pint = pair<int, int>;
using vi = vector<lint>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

const int MOD = 1000000007;
const int INF = 1 << 30;

int main() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, n) cin >> a[i];

    sort(all(a));

    lint ai = a[n-1];
    lint aj;
    double h = ai;
    h /= 2;

    double mi = INF;
    rep(i, n-1) {
        mi = min(mi, abs(a[i] - h));
    }

    rep(i, n-1) {
        if (mi == abs(a[i] - h)) {
            aj = a[i];
            break;
        }
    }

    printf("%lld %lld\n", ai, aj);
    return 0;
}


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

int main()
{   
    int a,b,c;
    cin>>a>>b>>c;
    int cnt5=0;
    int cnt7=0;
    if(a==5) cnt5++;
    else cnt7++;
    if(b==5) cnt5++;
    else cnt7++;
    if(c==5) cnt5++;
    else cnt7++;
    
    if(cnt5==2 && cnt7==1) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//cout << fixed << setprecision(17) << res << endl;
 
int main() {
    ll x;
    cin >> x;
    ll i = 0;
    ll c = 100;
    while (c < x) {
        c = c + c/100;
        ++i;
    }
    cout << i << endl;
}


Measured memory_bytes: 3640
using System;
using System.Text;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
class Program
{
    static void Main(string[] args)
    {
		string[] input = Console.ReadLine().Split(' ');
		decimal W = decimal.Parse(input[0]);
		decimal H = decimal.Parse(input[1]);
		decimal x = decimal.Parse(input[2]);
		decimal y = decimal.Parse(input[3]);

		decimal Smax = H * W / 2;
		int judge = 0;

        if(H%2==0 && W%2==0 && W/2==x && H / 2 == y)
		{
			judge = 1;
		}

		Console.WriteLine("{0}" + " " + "{1}", Smax, judge);
        
	}
}





Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

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

  int x;
  cin >> x;

  int l = 0;
  int r = 0;
  while (l <= x) {
    if (l <= x && x <= r) {
      cout << 1 << endl;
      return 0;
    }
    l += 100;
    r += 105;
  }

  cout << 0 << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
int main(){
    int h,w,a,b;cin>>h>>w>>a>>b;
    cout<<(h*w)-((a*w)+(b*(h-a)))<<endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=1000000007;
inline void add(int &x,int y){(x+=y)>=mod?x-=mod:0;}
inline int pl(int x,int y){return (x+=y)>=mod?x-mod:x;}
int n,m,dp[5050],po[5050],ipo[5050];
int main()
{
	scanf("%d %d",&n,&m);
	po[0]=1;ipo[0]=1;
	for(int i=1;i<=m;++i)po[i]=2*po[i-1]%mod,ipo[i]=500000004ll*ipo[i-1]%mod;
	for(int i=1;i<=m;++i)dp[i]=1;
	for(int i=1;i<=n;++i)
	{
		int sum=0,tmp;
		for(int j=1;j<=m;++j)
		{
			tmp=dp[j];
			dp[j]=(1ll*dp[j]*(j+1)+1ll*sum*po[j-1])%mod;
			sum=(sum+1ll*tmp*j%mod*ipo[j])%mod;
		}
	}
	printf("%d",dp[m]);
	return 0;
}

Measured memory_bytes: 1784
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        Integer[] cards = new Integer[count];

        for (int i = 0; i < count; i++) {
            cards[i] = sc.nextInt();
        }

        // 降順にする
        Arrays.sort(cards, Collections.reverseOrder());

        int score = 0;
        for (int i = 0; i < cards.length; i++) {
            if (i % 2 == 0) {
                score += cards[i];
            } else {
                score -= cards[i];
            }
        }

        System.out.println(score);
    }
}


Measured memory_bytes: 23760
#include <iostream>
#include <vector>
using namespace std;
using Graph = vector<vector<int>>;

vector<int> counters;
vector<bool> visited;
vector<int> ans;

void dfs(const Graph &G, int v, int counter) {
    visited[v] = true;
    ans[v] = counter + counters[v];
    for (auto u: G[v]) {
        if (visited[u]) continue;
        dfs(G, u, ans[v]);
    }
}

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

    counters.assign(N, 0);

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

    visited.assign(N, false);
    ans.assign(N, 0);
    dfs(G, 0, 0);

    cout << ans[0];
    for (int i = 1; i < N; i++) {
        cout << ' ' << ans[i];
    }
    cout << endl;
}



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

int main(){
  int a, b, c, d, e, k;
  cin >> a >> b >> c >> d >> e >>k;
  
  if(e - a > k){
    cout << ":(" << endl;
  }
  
  else {
    cout << "Yay!" << endl;
  }
}

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

signed main(){
	int N; cin>>N;
	vector<int> a(N),b(0);
	for(int i=0;i<N;i++)cin>>a[i];
	for(int i=N-1;i>=0;i-=2){
		b.push_back(a[i]);
	}
	for(int i=(N%2==0 ? 0 : 1);i<N;i+=2){
		b.push_back(a[i]);
	}
	for(int i=0;i<N;i++)cout<<b[i]<<" ";
	cout<<endl;

}

Measured memory_bytes: 5488
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define dup(x,y) (((x)+(y)-1)/(y))
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pii;
const double EPS = 1e-10;
const int INF = 1e9;
const ll LINF = 1e15;
const int MOD = 1000000007;
const double PI = acos(-1);
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

int main() {
	int n, m;
	cin >> n >> m;
	string s;
	cin >> s;
	reverse(ALL(s));

	vector<int> ans;
	for (int i = 0; i < n;) {
		int ni = min(n, i + m);
		while (s[ni] == '1') ni--;
		if (ni == i) {
			cout << -1 << endl;
			return 0;
		} else {
			ans.push_back(ni - i);
			i = ni;
		}
	}
	reverse(ALL(ans));
	rep(i,ans.size()) {
		if (i != 0) cout << " ";
		cout << ans[i];
	}
	cout << endl;
}

Measured memory_bytes: 4068
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> query;
typedef vector<vector<ll>> matrix;

struct edge {
  int to;
  int cap;
  edge* rev;
};

vector<edge*> edges[20005];
void addEdge(int from, int to, int cap) {
  edge* fwd = new edge;
  edge* rev = new edge;
  fwd->to = to;
  fwd->cap = cap;
  fwd->rev = rev;
  rev->to = from;
  rev->cap = 0;
  rev->rev = fwd;
  edges[from].push_back(fwd);
  edges[to].push_back(rev);
}

int dp[20005];
int iter[20005];
edge* used[20005];
const int INF = 1 << 14;

int maxFlow(int s, int t) {
  int ret = 0;
  for(int qq = 1; ret < INF; qq++) {
    queue<int> q;
    q.push(s);
    dp[s] = INF;
    dp[t] = 0;
    while(!q.empty() && dp[t] == 0) {
      int curr = q.front();
      q.pop();
      for(edge* out: edges[curr]) {
        if(out->cap == 0) continue;
        if(qq == iter[out->to]) continue;
        dp[out->to] = min(dp[curr], out->cap);
        iter[out->to] = qq;
        used[out->to] = out;
        q.push(out->to);
      }
    }
    if(dp[t] == 0) break;
    ret += dp[t];
    int curr = t;
    while(curr != s) {
      int par = used[curr]->rev->to;
      used[curr]->cap -= dp[t];
      used[curr]->rev->cap += dp[t];
      curr = par;
    }
  }
  return ret;
}

const char START_CHAR = 'S';
const char END_CHAR = 'T';
const char INTERMEDIATE = 'o';
string g[105];

bool canUse(int x, int y) {
  return g[x][y] == START_CHAR || g[x][y] == END_CHAR || g[x][y] == INTERMEDIATE;
}

void solve() {
  int r, c;
  cin >> r >> c;
  for(int i = 0; i < r; i++) {
    cin >> g[i];
  }
  /*
  construction is
  0 to r-1 is row
  r to r+c-1 is col
  r+c is source
  r+c+1 is sink
  */
  for(int i = 0; i < r; i++) {
    for(int j = 0; j < c; j++) {
      if(!canUse(i, j)) continue;
      if(g[i][j] == START_CHAR) {
        addEdge(r+c, i, INF);
        addEdge(r+c, r+j, INF);
      }
      else if(g[i][j] == END_CHAR) {
        addEdge(i, r+c+1, INF);
        addEdge(r+j, r+c+1, INF);
      }
      else {
        addEdge(i, r+j, 1);
        addEdge(r+j, i, 1);
      }
    }
  }
  int ret = maxFlow(r+c, r+c+1);
  if(ret >= INF) ret = -1;
  cout << ret << "\n";
}

void casesolve() {
  int t;
  cin >> t; cin.ignore();
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
  // casesolve();
}


Measured memory_bytes: 2432
#include<iostream>
#include<iomanip>
#include<stdio.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<algorithm>
#include<functional>
#include<math.h>
#include<unordered_set>
using namespace std;

int read(int n) {
	string s;
	cout << n << endl;
	cin >> s;

	if (s == "Male")return 1;
	if (s == "Female")return -1;
	return 0;
}

int main() {
	int N = 0;

	cin >> N;

	int begin = 0;
	int end = N;
	int S = 0;

	S = read(0);

	while (S) {
		int mid = (begin + end) / 2;
		int s = read(mid);

		if (s == 0)return 0;
		if ((s == S) ^ ((mid - begin) & 1)) {
			begin = mid + 1;
			S = -s;
		}
		else {
			end = mid;
		}
	}
	
	return 0;
}

Measured memory_bytes: 852
x_1, y_1, x_2, y_2 = [int(x) for x in input().split()]
delta_x = x_2 - x_1
delta_y = y_2 - y_1
x_3 = x_2 - delta_y
y_3 = y_2 + delta_x
x_4 = x_3 - delta_x
y_4 = y_3 - delta_y
print(str(x_3) + ' ' + str(y_3) + ' ' + str(x_4) + ' ' + str(y_4))



Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define rp(i,s,e) for(int i=(s);i<(e);++i)
#define irp(i,s,e) for(int i=(s);i>(e);--i)

int N,M,Q;
vector<pair<int,int>> LR;
vector<pair<int,int>> PQ;

void solve(){

	vvi VV(N+1, vi(N+1, 0));
	for(auto lr:LR){
		int l,r; tie(l,r) = lr;
		VV[l][r]++;
	}

	// for(auto v:VV){for(auto x:v){cout<<x<<" ";}puts("");};puts("---");//

	rp(l, 1, (int)VV.size()){
		rp(r, 1, (int)VV.size()){
			VV[l][r] += VV[l][r-1];
		}
	}

	// for(auto v:VV){for(auto x:v){cout<<x<<" ";}puts("");};puts("---");//

	rp(r, 1, (int)VV.size()){
		rp(l, 1, (int)VV.size()){
			VV[l][r] += VV[l-1][r];
		}
	}

	// for(auto v:VV){for(auto x:v){cout<<x<<" ";}puts("");};puts("---");//

	for(auto pq:PQ){
		int p,q; tie(p,q) = pq;
		int c = 0;

		// if(p==3 && q==8){
		// 	cout<<p<<" "<<q<<"\n";//
		// 	cout<<"("<<N<<","<<q<<") ("<<p-1<<","<<q<<")\n";//
		// }
		c = VV[N][q] - VV[p-1][q];

		cout<< c <<endl;
	}

}

int main(){
	cin>>N>>M>>Q;
	rp(i, 0, M){
		int l,r; cin>>l>>r;
		LR.emplace_back(l,r);
	}
	rp(i, 0, Q){
		int p,q; cin>>p>>q;
		PQ.emplace_back(p,q);
	}
	solve();
}


Measured memory_bytes: 4336
# -*- coding: utf-8 -*-
import sys

n, x = map(int,input().split())
m = list()
min_m = sys.maxsize
count = 0

for i in range(n):
 m.append(int(input()))
 x -= m[i]
 count += 1
 if m[i] < min_m:
  min_m = m[i]

while(min_m<=x):
 x -= min_m
 count += 1

print(count)

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

typedef long long ll;

#define REP(i, n) for (int i = 0; i < (n); i++)
#define INF (1LL<<30)

ll N, A, B;
vector<ll> h;

bool enough(ll T) {
	vector<ll> b;
	for (ll i = 0; i < N; i++) {
		if(h[i] > B*T) b.push_back(h[i]-B*T);
	}
	ll cnt=0;
	for (ll i = 0; i < b.size(); i++) {
		if(b[i]%(A-B)==0) cnt += b[i]/(A-B);
		else cnt += b[i]/(A-B)+1;
	}
	return cnt <= T;
}

ll binary_search() {
	ll ng = 0;
	ll ok = INF;

	while (abs(ok - ng) > 1) {
		//cout << ok <<" "<< ng << endl;
		ll mid = (ok + ng) / 2;

		if (enough(mid)) ok = mid;
		else ng = mid;
	}
	return ok;
}


int main() {
	cin >> N >> A >> B;
	
	for (ll i = 0; i < N; i++) {
		int a; cin >> a;
		h.push_back(a);
	}

	ll ans = binary_search();
	printf("%lld\n", ans);
}



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

#define ll long long 
#define pb push_back
#define MOD 1000000007
#define all(x) (x).begin(), (x).end()

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

	string s;
	cin >> s;
	ll c = 0;
	for (auto x: s) {
		c += (x - '0');
	}
	if (c % 9 == 0) {
		cout << "Yes\n";
	}
	else {
		cout << "No\n";
	}

	return 0;
}

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

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

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

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

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

const long long mod = 1000000007;

int main(){
    int n;
    cin >> n;
    vi a(n);
    rep(i, n) cin >> a[i];
    vi sum(n+1);
    rep(i, n) sum[i+1] = (sum[i] + a[i]) % mod;
    int ans = 0;
    rep(i, n-1) ans = (ans + (ll)a[i] * (sum[n] - sum[i+1] + mod)) % mod;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4780
#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<queue>
#include<set>
#include<map>
#include<random>
#include<functional>
#include<utility>

#define rep(i,n) for(int i=0; i<n; i++)
#define pb push_back
#define P pair<int, int>
#define PLI pair<ll, int>

using namespace std;

typedef long long ll;


int H, N;
int f[4][10000] = {};
int dp[10000][1<<4];

bool check(int bit, int shift) {
	if (bit >> shift & 1) return false;
	if (bit >> (shift + 1) & 1) return false;
	return true;
}

int dfs(int now, int b) {
	if (now == H - 1) return 0;
	if (dp[now][b] != -1) return dp[now][b];

	int nx = 0;
	rep(i, 4) {
		nx |= f[i][now+1] << i;
	}

	int ret = 0;
	ret = max(ret, dfs(now + 1, nx));

	rep(i, 3) {
		if (check(b, i) && check(nx, i)) {
			int t = nx;
			t |= 1 << i;
			t |= 1 << (i + 1);
			ret = max(ret, dfs(now + 1, t) + 1);
		}
	}

	if (b == 0 && nx == 0) {
		ret = max(ret, dfs(now + 1, 15) + 2);
	}

	return dp[now][b] = ret;
}

int main() {
	cin >> H >> N;
	rep(i, N) {
		int x, y;
		cin >> x >> y;
		f[x][y] = 1;
	}

	rep(i, H) {
		rep(j, 1<<4) {
			dp[i][j] = -1;
		}
	}

	int s = 0;
	rep(i, 4) {
		s |= f[i][0] << i;
	}

	cout << dfs(0, s) << endl;

	return 0;
}



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

int main() {
	int n;
	cin >> n;
	int list[] = {1, 2, 4, 8, 16, 32, 64};
	for(int i = 6; i >= 0; i--){
		if(list[i] <= n){
			cout << list[i] << endl;
			return 0;
		}
	}
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define il inline
unordered_map<int,int>mp;
int sz[2];
int main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		mp[x]++;
	}
	for(auto p:mp){
		sz[p.se%2]++;
	}
	int ans=0;
	ans+=sz[1]+sz[0]/2*2; 
	cout<<ans;
	return 0;
}

Measured memory_bytes: 7332
a,b,c,d,e,f = map(int,input().split())

num = int(input())

def dice1(x):
  if x == b:
    return c
  elif x == c:
    return e
  elif x == d:
    return b
  else:
    return d
  
def dice2(x):
  if x == a:
    return d
  elif x == c:
    return a
  elif x == d:
    return f
  else:
    return c
  
def dice3(x):
  if x == a:
    return b
  elif x == b:
    return f
  elif x == e:
    return a
  else:
    return e

def dice4(x):
  if x == a:
    return e
  elif x == b:
    return a
  elif x == e:
    return f
  else:
    return b

def dice5(x):
  if x == a:
    return c
  elif x == c:
    return f
  elif x == d:
    return a
  else:
    return d
  
def dice6(x):
  if x == b:
    return d
  elif x == c:
    return b
  elif x == d:
    return e
  else:
    return c
  
for i in range(num):
  j,k=map(int,input().split())
  if j == a:
    print(dice1(k))
  elif j == b:
    print(dice2(k))
  elif j == c:
    print(dice3(k))
  elif j == d:
    print(dice4(k))
  elif j == e:
    print(dice5(k))
  else:
    print(dice6(k))
    


Measured memory_bytes: 5612
#include <bits/stdc++.h>
using namespace std;
const int MN = 2005;
 
int N, A[MN];

vector<int> G[MN];
 
int vis[MN];
void DFS(int u) {
	vis[u] = 1;
	for (int v = 1; v <= N; ++v)
		if (!vis[v] && std::__gcd(A[u], A[v]) > 1)
			G[u].push_back(v), DFS(v);
}
 
int main() {
	cin >> N;
	for (int i = 1; i <= N; ++i) cin >> A[i];
	std::sort(A + 1, A + N + 1);
	std::priority_queue<int> q;
	for (int i = 1; i <= N; ++i) if (!vis[i]) DFS(i), q.push(i);
	while (!q.empty()) {
		int u = q.top(); q.pop();
		cout << A[u] << ' ';
		for (int v : G[u]) q.push(v);
	}
	return 0;
}

Measured memory_bytes: 3872
#include<bits/stdc++.h>
#define ci const int&
using namespace std;
struct edge{
	int t,nxt;
}e[500010];
int n,m,u,v,ed[710][710],cnt,be[710],vis[710],b[2][710],col[710],dp[710],sz;
void add(ci x,ci y){
	e[++cnt].t=y,e[cnt].nxt=be[x],be[x]=cnt;
}
void dfs(ci x){
	++b[col[x]][sz],vis[x]=1;
	for(int i=be[x];i;i=e[i].nxt){
		if(!vis[e[i].t])col[e[i].t]=col[x]^1,dfs(e[i].t);
		else if(col[e[i].t]==col[x])exit((puts("-1"),0));
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)scanf("%d%d",&u,&v),ed[u][v]=ed[v][u]=1;
	for(int i=1;i<=n;++i)for(int j=i+1;j<=n;++j)!ed[i][j]?add(i,j),add(j,i),0:0;
	for(int i=1;i<=n;++i)!vis[i]?++sz,dfs(i),0:0;
	dp[0]=1;
	for(int i=1;i<=sz;++i)for(int j=n;j>=0;--j)dp[j]=(j>=b[0][i]?dp[j-b[0][i]]:0)|(j>=b[1][i]?dp[j-b[1][i]]:0);
	for(int i=(n>>1);i>=0;--i)if(dp[i])return printf("%d",(i*(i-1)>>1)+(((n-i)*(n-i-1))>>1)),0;
	return 0;
}

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

using ll = long long;
using vi = vector<int>;
using vll = vector<long long>;

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

constexpr long long mod = 1000000007;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k, t;
    cin >> k >> t;
    vi a(t);
    rep(i, t) cin >> a[i];

    int m = *max_element(a.begin(), a.end());

    cout << max(m - 1 - (k - m), 0) << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
const ll INF = 1LL<<61;
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; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll jou(ll N, ll P){if(P==0) return 1;
  if(P%2==0){ll t = jou(N, P/2);return t*t % mod;
  }return (N * jou(N, P-1)) % mod;}  //jou(n,mod-2)で逆元
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる





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

  vector<ll> p(n);
  ll sum=0;
  rep(i,n){
    cin>>p[i];
    sum+=p[i];
  }

  sort(all(p));

  ll ans=sum;
  rep(i,n){
    if(2*i+1<n){
      sum-=2*(p[2*i]+p[2*i+1]);
      chmax(ans,sum);
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 1024
use std::io;
use std::cmp::max;

fn main() {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    let mut iter = buf.trim().split_whitespace();
    let n = iter.next().unwrap().parse::<i64>().unwrap();
    let k = iter.next().unwrap().parse::<i64>().unwrap();
    let mut ans = 0;
    for b in 1..n+1 {
        ans += n / b * max(0, b - k) + max(0, n % b - k + 1);
        if k == 0 { ans -= 1; }
    }
    println!("{}", ans);
}


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

bool solve();

int main()
{
	if (solve()) printf("YES\n");
	else printf("NO\n");

	return 0;
}

bool solve()
{
	int a, b, c;
	scanf("%d%d%d", &a, &b, &c);
	while (a)
	{
		b %= a;
		std::swap(a, b);
	}
	if (c % b) return false;
	else return true;
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/abc061/tasks/abc061_d
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

long long v[1000][1000], d[1000];

void solv(long long n, long long m) {
  long long i, j, max = LLONG_MIN, a, b, c, updated, count;

  for (i = 0; i < n; i++) {
    d[i] = LLONG_MIN;
    for (j = 0; j < n; j++) {
      v[i][j] = LLONG_MAX;
    }
  }
  for (i = 0; i < m; i++) {
    scanf("%lld %lld %lld", &a, &b, &c);
    v[a - 1][b - 1] = c;
  }

  d[0] = 0;
  for (count = 0, updated = 1; updated && count < n; count++) {
    updated = 0;
    for (i = 0 ; i < n; i++) {
      if (d[i] == LLONG_MIN) {
        continue;
      }
      for (j = 0; j < n; j++) {
        if (v[i][j] == LLONG_MAX) {
          continue;
        }
        if (d[j] < d[i] + v[i][j]) {
          d[j] = d[i] + v[i][j];
          updated = 1;
          if (count == n - 1 && j == n - 1) {
            puts("inf");
            return;
          }
        }
      }
    }
  }

  printf("%lld\n", d[n - 1]);
}

int main(int argc, char **argv) {
  long long n, m;

  while (scanf("%lld %lld", &n, &m) != EOF) {
    solv(n, m);
  }

  return 0;
}


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

int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
vector<long long int> adj[200001];
bool vis[200001];
#define ll long long int
#define ull unsigned long long int
#define MAX 1000000007
#define MOD 998244353

#define pll pair<ll,ll>
#define pii pair<int,int>
#define IO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define FO ifstream fin("a.in");ofstream fout("a.out");
#define TEST ll t;cin>>t;while(t--)
#define all(x) (x).begin(),(x).end()
#define mset0(x) memset((x), 0, sizeof((x)));
#define mset1(x) memset((x), -1, sizeof((x)));

ll power(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a;
        b/=2;
        a=a*a;
    }
    return(ans);
}
ll f(ll b,ll n){
    ll ans=0;
    while(n>=b){
        ans+=n%b;
        n=n/b;
    }
    ans+=n;
    return(ans);
}
int main(){
    IO
    ll n,ans=0,x;
    cin>>n;
    ll arr[n+1];
    for(ll i=1;i<=n;i++){
        cin>>arr[i];

    }
    for(ll i=1;i+1<=n;i++){
        if(i==arr[i]) {swap(arr[i],arr[i+1]);ans++;}
    }
    if(arr[n]==n) ans++;
    cout<<ans;
    return(0);
}

Measured memory_bytes: 5760
import java.util.Scanner;
public class Main
{
    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a =sc.nextInt();
    int b =sc.nextInt();
    int c =a*(a-1)/2 + b*(b-1)/2;
    System.out.println(c);
}
}

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

ll dp[13] = {1};

int main(){
    string s;
    cin >> s;
    rep(i,s.size()){
        ll temp[13] = {0};
        rep(j,13){
            if(s[i] != '?') temp[(j*10+s[i]-'0')%13] += dp[j];
            else rep(k,10) temp[(j*10+k)%13] += dp[j];
        }
        rep(j,13) dp[j] = temp[j] % mod;
    }
    printf("%lld\n", dp[5]);
}


Measured memory_bytes: 512
#include <math.h>
#include <stdio.h>
#define MOD 1000000007
typedef long long ll;
ll modpow(ll a, ll n) {
	if (n == 0)
		return 1;
	if (n == 1)
		return (a % MOD);
	if (n % 2 == 1)
		return (a * modpow(a, n - 1) % MOD);
	ll t = modpow(a, n / 2);
	return (t * t % MOD);
}
ll comb(ll n, ll r) {
	ll res = 1;
	for (int i = n; i > n - r; i--) {
		res *= i;
		res %= MOD;
	}
	ll y = 1;
	for (int i = 2; i <= r; i++) {
		y *= i;
		y %= MOD;
	}
	y = modpow(y, MOD - 2);
	res = res * y % MOD;
	return res;
}

int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= k; i++) {
		printf("%lld\n", comb(n - k + 1, i) * comb(k - 1, i - 1) % MOD);
	}
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ll long long
#define inf (1LL<<61)
#define MOD 1000000007
const ll N=2e5+5;
template<typename T> T gcd(T a,T b) { if(a==0) return b; return gcd(b%a,a); }
template<typename T> T pow(T a,T b, long long m){T ans=1; while(b>0){ if(b%2==1) ans=(ans*a)%m; b/=2; a=(a*a)%m; } return ans%m; }
ll n,k;

ll a[100005];
ll b[100005];
ll c[100005];
ll cache[100005][3];
ll dp(ll i,ll j)
{
    if(i==n)
    {
        if(j==0)
            return max(b[n],c[n]);
        if(j==1)
            return max(a[n],c[n]);
        if(j==2)
            return max(a[n],b[n]);
    }
    
    ll &ans=cache[i][j];
    if(ans!=-1)
        return ans;
    ans=0;
    if(j==0)
    {
        ans=max(ans,dp(i+1,1)+b[i]);
        ans=max(ans,dp(i+1,2)+c[i]);
    }
    if(j==1)
    {
        ans=max(ans,dp(i+1,0)+a[i]);
        ans=max(ans,dp(i+1,2)+c[i]);
    }
    if(j==2)
    {
        ans=max(ans,dp(i+1,0)+a[i]);
        ans=max(ans,dp(i+1,1)+b[i]);
    }
    
    return ans;
}
int main()
{
    IOS;
    cin>>n;
    for(ll i=1;i<=n;i++)
        cin>>a[i]>>b[i]>>c[i];
    memset(cache,-1,sizeof(cache));
    
    ll ans=max(dp(1,0),max(dp(1,1),dp(1,2)));
    
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 8064
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <numeric>
#include <set>

using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(int i = 1;i <= n;i++)
#define INF 999999999
#define MINF -999999999
#define ALL(n) n.begin(),n.end()
#define ll long long
#define MOD 1000000007


ll n, m, s[1100][3], ans = 0;
int main() {
	cin >> n >> m;
	REP(i, n) {
		REP(j, 3)cin >> s[i][j];
	}
	REP(k, 8) {
		ll sum = 0;
		vector<ll> u;
		REP(i, n) {
			ll a = 0;
			REP(j, 3) {
				if (k & (1 << j)) a += s[i][j];
				else a -= s[i][j];
			}
			u.push_back(a);
		}
		sort(ALL(u), greater<ll>());
		REP(i, m) {
			sum += u[i];
		}
		ans = max(ans, sum);
	}
	cout << ans << endl;
}



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

#define rep(i,N) for(int i=0;i<N;i++)
#define rep2(i,N) for(int i=1;i<=N;i++)
using namespace std;
long long  INF=1e18;
long long mod=1e9+7;
#define SIZE 1e5+1
//素数のベクトル
vector<int>prime;
vector<int>cnt(SIZE,0);
vector<int>sum(SIZE,0);
set<int>P;
//status unsolved
void make_prime(){
    prime.emplace_back(2);
    for(int i=3;i<SIZE;i+=2){
        prime.emplace_back(i);
    }
    
    for(int i=0;i<prime.size();i++){
        int now=prime[i];
        for(int k=i+1;k<prime.size();k++){
            if(prime[k]%now==0){
                prime.erase(prime.begin()+k);
            }
        }
    }


    return;
}

void check(){
    rep(i,prime.size()){
        P.emplace(prime[i]);
    }
    rep(i,prime.size()){
        if(P.find((prime[i]+1)/2)!=P.end()){
            cnt[prime[i]]=1;
        }
    }

    return;
}

void count_like(){
    for(int i=1;i<SIZE;i++){
        sum[i]=sum[i-1]+cnt[i];
    }
    return;
}


int main(){
    
    int q;
    cin>>q;
    make_prime();
    
    check();

    count_like();

    rep(i,q){
        int l,r;
        cin>>l>>r;
        cout<<sum[r]-sum[l-1]<<endl;
    }
    


    return 0;

}
/*


*/


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

int main() {
  string n; cin >> n;
  int m=n.size();
 if(n[m-1]=='2' || n[m-1]=='4' || n[m-1]=='5' || n[m-1]=='7' || n[m-1]=='9'){
   cout << "hon" << endl;
 }
 else if(n[m-1]=='3'){
   cout << "bon" << endl;
 }
 else cout << "pon" << endl;
}


Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
using namespace std;


int main(){
    string s;
    cin >> s;
    
    long long ans = 0;
    int last_non_a = -1;
    for(int i = 0; i < (long long) s.size() - 2; i++){
        if(s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C'){
            ans += (i - last_non_a);
            last_non_a += 2;
            s[i + 2] = 'A';
            i += 1;
        } else if(s[i] != 'A'){
            last_non_a = i;
        }
        //cout << ans << endl;
    }
    cout << ans << endl;
    /*
    stack <char> st;
    for(int i = 0; i < 3; i++){
        st.push(s[i]);
    }
    for(int i = 3; i < N; i++){
        char first = st.top();
        st.pop();
        char second = st.top();
        st.pop();
        char third = st.top();
        st.pop();
    }
    */
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <array>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <bitset>
#include <tuple>
#include <cmath>
#include <complex>
#include <algorithm>
#include <utility>
#include <regex>
#include <cstdint>
#include <numeric>
#include <functional>
#include <cassert>

using namespace std;
using ll = int64_t;
using ull = uint64_t;

constexpr ll INF = 1000000000;/* 1e+9a */

void solve(istream &cin) {
    ll A, B, C;
    cin >> A >> B >> C;
    if(!cin) return;
    ll ans = min(A+B+1, C);
    ans += B;
    cout << ans << endl;

}

int main(int argc, char *argv[]) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << setprecision(16) << scientific;
#ifdef DEBUG
    cerr << "DEBUG MODE" << endl;
    string test_cases = "test.txt";
    auto fs = fstream(test_cases, fstream::in);
    while(fs) {
        solve(fs);
    }
#else
    solve(cin);
#endif
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
#include <cassert>
#include <random>
#include<iostream>
#include<cmath>

struct Lunch {
	int id, weight, strongth;
	bool operator<(const Lunch that) const { return id < that.id; }
};

bool is_not_crash(const std::vector<Lunch>& lunch) {
	int sum_weight = 0;
	for (auto r = lunch.rbegin(); r != lunch.rend(); ++r) {
		if (sum_weight > r->strongth) return false;
		sum_weight += r->weight;
	}
	return true;
}
double cal_center(const std::vector<Lunch>& lunch) {
	double denominator = 0, numerator = 0;
	for (auto i = 0; i < lunch.size(); ++i) {
		denominator += lunch[i].weight;
		numerator += lunch[i].weight * (i + 1.0);
	}
	return numerator / denominator;
}
int factorial(const int n) {
	int result = 1;
	for (auto i = 2; i <= n; ++i) {
		result *= i;
	}
	return result;
}
int main() {
	while (true) {
		int n; std::cin >> n; if (n == 0) break;
		std::vector<std::string> names(n);
		std::vector<Lunch> lunches(n), result; 
		for (auto i = 0; i < n; ++i) {
			lunches[i].id = i;
			std::cin >> names[i] >> lunches[i].weight >> lunches[i].strongth;
		}
		double min_center = DBL_MAX;
		for (auto i = factorial(n); i > 0; --i) {
			if (is_not_crash(lunches)) {
				auto temp = cal_center(lunches);
				if (temp < min_center) {
					min_center = temp;
					result = lunches;
				}
			}
			std::next_permutation(lunches.begin(), lunches.end());
		}
		for (const auto i : result) {
			std::cout << names[i.id] << '\n';
		}
	}
}


Measured memory_bytes: 3032
#include <bits/stdc++.h>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)

using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using ull= unsigned long long;
const ll K_MAX=1e5+5;
const ll Lmax=ll(1e18);
const ll INF=1e15+4;
const int Nmax=2e5+1;
const int Nd=61;



int main(){
  int n;cin>>n;
  ll k; cin>>k;
  vector<ll> p(n),c(n),g(n,-1),t(n),sc(n);

  rep(i,n){
    ll test;
    cin>>test;
    test--; p[i]=test;
  }
  rep(i,n){
    cin>>c[i];
  }
  ll gname=0;
  //group nameをつける 0,1,2,...
  rep(i,n){
    if(g[i]==-1){// noname
      g[i]=gname;
      int i2=p[i];
      t[gname]=1;// 周期
      sc[gname]=c[i2];
      while(i2!=i){//1周するまで
        g[i2]=gname;
        i2=p[i2];
        t[gname]++;
        sc[gname]+=c[i2];
      }
      gname++;
    }
  }

  int ng=gname; //グループ数
  ll now;
  ll ans1=0;
  ll ans=0;

  rep(i,n){// 始点-iで考える
    if(k>t[g[i]] && sc[g[i]]>0){// 1周以上かつ sc>0の場合
      ll t2=k/t[g[i]]-1;//周回
      now=sc[g[i]]*t2; //t2周目のスコア．
      ans1=now;
      ll jmax=k-t2*t[g[i]];
      int i2=i;
      for(ll j=0;j<jmax;j++){
        i2=p[i2];
        now+=c[i2];
        if(j==0 && t2==0) ans1=now;
        ans1=max(ans1,now);
      }
    }else{//そうでない(1周回らない or sc<0 回るほど損の場合)
      now=0; //2t周目のスコア．
      ans1=now;
      ll jmax=min(t[g[i]],k);
      int i2=i;
      for(ll j=0;j<jmax;j++){
        i2=p[i2];
        now+=c[i2];
        if(j==0) ans1=now;
        ans1=max(ans1,now);
      }
    }
    if(i==0) ans=ans1;
    ans=max(ans,ans1);
  }
  cout<<ans<<endl;









}


Measured memory_bytes: 3788