akhauriyash/Code-Regression huggingface dataset:
// abc137_e
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;


template<typename T>
struct BellmanFord{
    struct edge {
        int u, v;
        T w;
        edge() {}
        edge(int u, int v, T w) : u(u), v(v), w(w) {}
        friend ostream& operator<<(ostream& os, const edge& e) {cout << "(" << e.u << "->" << e.v << "," << e.w << ")"; return os;}
    };

    int n;
    vector< vector<int> > G;
    vector<bool> used, reach;
    vector<edge> edges;
    vector<T> ds;
    T INF;

    explicit BellmanFord(int n) : n(n), G(n), used(n, 0), reach(n, 0) { INF = numeric_limits<T>::max(); }

    void add_edge(int u, int v, T c) {
        edges.emplace_back(u, v, c);
        G[u].emplace_back(v);
    }

    void dfs(int v){
        if(used[v]) return;
        used[v]=true;
        for(int u:G[v]) dfs(u);
    }

    T get_shortest_path(int s, int t, bool &neg_loop){
        // 各ノードがtにたどり着けるかどうか
        for (int i = 0; i < n; i++) {
            fill(used.begin(), used.end(), 0);
            dfs(i);
            reach[i] = used[t];
        }

        ds.assign(n, INF);
        ds[s] = 0;

        for (int j = 0; j < n; j++) {
            bool update = false;
            for (auto e:edges) {
                if(!reach[e.u]||!reach[e.v]||ds[e.u]==INF) continue;

                if (ds[e.u] + e.w < ds[e.v]) {
                    ds[e.v] = ds[e.u] + e.w;
                    update = true;
                }
            }

            if (!update) break;

            if (j == n - 1) {
                neg_loop = true;
                return INF;
            }
        }
        neg_loop = false;
        return ds[t];
    }
};

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    int N, M, P;
    cin >> N >> M >> P;

    BellmanFord<ll> g(N);
    map<pair<int, int>, ll> mp;
    REP(i, M){
        int a, b; ll c;
        cin >> a >> b >> c; a--; b--;
        g.add_edge(a, b, P - c);
//        mp[make_pair(a,b)] += c;
    }

//    for (auto p: mp){
//        int a = p.first.first;
//        int b = p.first.second;
//        ll c = p.second;
//        g.add_edge(a, b, P - c);
//    }

    bool negloop;
    ll ans =  g.get_shortest_path(0, N-1, negloop);

    if (negloop){
        print(-1);
    } else {
        print(max(-ans, 0ll));
    }


    return 0;
}


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

int gcd(int a,int b){
  if(a%b==0) return b;
  else return gcd(b,a%b);
}

int main(){
  int N;
  cin>>N;
  vector<int>x(N);

  for(int i=0;i<N;i++){
    cin>>x[i];
  }
  int ans=x[0];
  for(int i=1;i<N;i++){
    ans=gcd(ans,x[i]);
  }
  cout<<ans<<endl;
  return 0;
}



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

int main()
{
	int n, m;
	int ans = 0;
	std::cin >> n >> m;
	std::vector<std::vector<int> > S;
	for (int i = 0; i < m; i++)
	{
		int k;
		std::vector<int> switches;
		std::cin >> k;
		for (int j = 0; j < k; j++)
		{
			int s;
			std::cin >> s;
			s--;
			switches.push_back(s);
		}
		S.push_back(switches);
	}
	std::vector<int> P;
	for (int i = 0; i < m; i++)
	{
		int p;
		std::cin >> p;
		P.push_back(p);
	}
	
	for (int bit = 0; bit < (1 << n); bit++)
	{
		bool flag = true;
		for (int i = 0; i < m; i++)
		{
			int count = 0;
			for (int j = 0; j < S.at(i).size(); j++)
			{
				if (bit & (1 << S.at(i).at(j)))
					++count;
			}
			if (count % 2 != P.at(i))
			{
				flag = false;
				break;
			}
		}
		if (flag)
			++ans;
	}
	std::cout << ans << '\n';
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 19 15:35:41 2020

@author: ybt07
"""

class SegmentTreeMax():
    def __init__(self,n,init):
        # n = 7 のとき
        # offset = 2 ** 3 = 8
        # 実際のデータは tree[0+8], tree[1+8],,,, に入る
        # tree[0～8] は区間の値を入れるために使われている
        self.offset = 2 ** ((n-1).bit_length())  # セグメント木を配列で行玄する際のオフセット量
        self.tree = [init] * (2 * self.offset)
        self.init = init

    def update(self, pos, val): # pos番目の要素を覆う要素すべてについて値を更新する
        pos += self.offset
        self.tree[pos] = val  # n=7, pos=5 のとき tree[5+8] に val が入る
        while pos > 1:
            pos = pos // 2  # 13 // 2 = 6
            # tree[6] に tree[12],tree[13] の大きい方が入る
            self.tree[pos] = max(self.tree[2 * pos],self.tree[2 * pos + 1])

    def query(self, left, right): # 区間[l,r]での最大値を求める
        # 例のごとく、オフセット
        left += self.offset
        right += self.offset
        ret = self.init  # 再帰的に書くので、初期値を設定
        while left <= right:
            ret = max(ret, self.tree[right])
            right = (right - 1) // 2
            ret = max(ret, self.tree[left])
            left = (left + 1) // 2
        return ret

mod=998244353
n=int(input())
xd = [list(map(int,input().split())) for _ in range(n)]
xd = sorted(xd,key=lambda x:x[0]) #X座標の小さい順にソートする

st = SegmentTreeMax(n,0)
ranges = []

for i in range(n):
    r = xd[i][0] + xd[i][1] #各ロボットが到達できる最大の位置
    left = -1
    right = n
    
    #2分探索によりどのロボットまで影響するかを求める(0-indexed)
    while right - left != 1:  # right と left の間が 1 （隣り合う） 行う
        mid = (left + right) // 2
        if xd[mid][0] >= r:  # index 上で中間の要素に届くか？
            right = mid  # ぶつからないところにいれば、もっと左を探す（さがす範囲を更新）

        else:
            left = mid  # ぶつかるところにいれば、もっと右を探す（さがす範囲を更新）
            
    ranges.append(right - 1)  # i 番目のロボットが right - 1 番目のロボットまで影響することを記録する
    st.update(i, right - 1) # セグメント木のi番目の要素を right - 1に更新する

for i in range(n-1,-1,-1):
    # x の大きい側から求めていくことで、玉突きでどこまで影響するか？の数字が求められる
    # j番目 = ranges[i] が影響する 範囲が、既にrange[j] に入っている
    ranges[i] = st.query(i,ranges[i]) # 区間[i,k]での番号の最大値を求める
    st.update(i, ranges[i]) # セグメント木のi番目の要素を上記の最大値に更新する

dp = [0] * (n+1)
dp[-1] = 1 #DPの初期値は1(すべてのロボットを除いた場合に相当する)

for i in range(n-1,-1,-1):
    j = ranges[i] + 1  # j : i の動作が影響を及ぼさない、右側にある、最小の j
    dp[i] = dp[i+1] + dp[j] #後ろから順にDP[i]=DP[i+1]+DP[j]として更新する
    dp[i] %= mod

print(dp[0])

Measured memory_bytes: 109400
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    n = int(input())
    A = [int(input()) for i in range(n)]

    ans = 0
    seq_cnt = 0
    for i in range(n):
        if A[i] != 0:
            seq_cnt += A[i]
        else:
            ans += seq_cnt // 2
            seq_cnt = 0
    ans += seq_cnt // 2

    print(ans)


resolve()

Measured memory_bytes: 44252
#include <iostream>
#include <string>
#include <queue>

typedef long long int ll;

using namespace std;

// グローバル変数
int N;
int table[5002][5002];
string str;

int main()
{
	cin >> N;
	cin >> str;
	
	// 動的計画法
	for (int i = 0; i < N + 1; i++)
	{
		for (int j = 0; j < N + 1; j++)
		{
			table[i][j] = 0;
		}
	}
	int max = 0;

	// 動的計画法
	for (int i = N - 2; i >= 0; i--)
	{
		for (int j = N - 1; j > i; j--)
		{
			if (str[i] == str[j])
			{
				table[i][j] = min(table[i + 1][j + 1] + 1, j - i);
				if (table[i][j] > max)
				{
					max = table[i][j];
				}
			}
		}
	}
	if (max == 1)
	{
		cout << 0;
	}
	else
	{
		cout << max;
	}
}

Measured memory_bytes: 97920
#include <bits/stdc++.h>
#define int long long
#define ll long long
using ull = unsigned long long;
using namespace std;
const int INF = 1e10;
const int MOD = 1e9 + 7;
#define dump(x)                             \
    if (dbg) {                              \
        cerr << #x << " = " << (x) << endl; \
    }
#define overload4(_1, _2, _3, _4, name, ...) name
#define FOR1(n) for (ll i = 0; i < (n); ++i)
#define FOR2(i, n) for (ll i = 0; i < (n); ++i)
#define FOR3(i, a, b) for (ll i = (a); i < (b); ++i)
#define FOR4(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FORR(i, a, b) for (int i = (a); i <= (b); ++i)
template <class T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return 1;
    } else
        return 0;
}
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    } else
        return 0;
}
void Yes(bool flag = true) {
    if (flag)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}
void No(bool flag = true) {
    Yes(!flag);
}
void YES(bool flag = true) {
    if (flag)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
void NO(bool flag = true) {
    YES(!flag);
}
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(), (v).end()
#define SZ(x) ((int)(x).size())
#define P pair<int, int>
#define V vector<int>
//#define S set<int>
#define itn int
bool dbg = false;

itn N, K, a[200];
int memo[101010];

bool f(int k) {
    if (memo[k] != -1)
        return memo[k];
    if (k == 0) {
        return false;
    }
    bool flag = false;
    FOR(N) {
        if (k - a[i] >= 0) {
            flag = flag | !f(k - a[i]);
        }
    }
    return memo[k] = flag;
}

void solve() {
    memset(memo, -1, sizeof(memo));
    if (f(K))
        cout << "First" << endl;
    else
        cout << "Second" << endl;
}

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

    cin >> N >> K;
    FOR(N)
    cin >> a[i];

    solve();
    return 0;
}


Measured memory_bytes: 4224
/*
* @Author: 王文宇
* @Date:   2018-03-17 20:00:26
* @Last Modified by:   王文宇
* @Last Modified time: 2018-03-17 20:57:21
*/
#include <bits/stdc++.h>
using namespace std;
int n,m,k;
int main(int argc, char const *argv[])
{
	cin>>n>>m>>k;
	if(n+m<k)cout<<"No"<<endl;
	else cout<<"Yes"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cctype>
#include<climits>
#include<string>
#include<bitset>
#include<cfloat>
#include<iomanip>
#include<numeric>

using namespace std;
using ll =  long long;
using pint =  pair<int,int>;
using vint = vector<int>;
using vvint = vector<vint>;
using vpint = vector<pint>;
#define repi(i,start,end) for(int (i)=(start),TemPNuM=(int)(end);(i)<TemPNuM;++(i))
#define rep(i,end) repi((i),0,(end))
#define rfor(x,v) for(auto& (x) : (v))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fsort(v,lambda) sort(all((v)),(lambda))
#define vin(v) rep(i,(v).size())cin >> (v)[i];
#define vpin(v) rep(i,(v).size())cin>>v[i].first>>v[i].second
//#define int long long
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<class T>void println(T a){if(cout.precision()!=12)cout<<setprecision(12);cout<<a<<endl;}
//lambda: [](int x, int y){return x<y;}

signed main(void) {
    set<int> color;
    rep(i, 3) {
        int t; cin >> t;
        color.insert(t);
    }
    cout << color.size() << endl;


    return 0;
}


Measured memory_bytes: 256
package main

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

const (
	initialBufSize = 100000
	maxBufSize     = 1000000
)

var sc *bufio.Scanner

func initScanner(r io.Reader) *bufio.Scanner {
	buf := make([]byte, initialBufSize)

	sc := bufio.NewScanner(r)
	sc.Buffer(buf, maxBufSize)
	sc.Split(bufio.ScanWords) // bufio.ScanLines
	return sc
}

func main() {
	sc = initScanner(os.Stdin)
	fmt.Println(resolve(parseProblem()))
}

func parseProblem() (int, []int) {
	n := scanInt(sc)
	as := nextIntSlice(sc, n)
	return n, as
}

func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	a, _ := strconv.Atoi(sc.Text())
	return int(a)
}

func nextString(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func nextIntSlice(sc *bufio.Scanner, n int) (a []int) {

	a = make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = nextInt(sc)
	}
	return a
}

type info struct{ cost, size int }

var dp [][]info

func resolve(n int, as []int) int {
	initDP(n)
	return _rec(as, 0, len(as)).cost
}

func _rec(as []int, l, r int) info {
	if dp[l][r].cost != 0 { // no 0-size slime
		return dp[l][r]
	}
	if l == r {
		return info{}
	}
	if l+1 == r {
		dp[l][r] = info{cost: 0, size: as[l]}
		return dp[l][r]
	}
	dp[l][r] = info{cost: math.MaxInt64, size: -1}
	for i := l + 1; i < r; i++ {
		cand := fusion(_rec(as, l, i), _rec(as, i, r))
		if cand.cost < dp[l][r].cost {
			dp[l][r] = cand
		}
	}
	return dp[l][r]
}

func fusion(x, y info) info {
	return info{
		cost: x.size + y.size + x.cost + y.cost,
		size: x.size + y.size,
	}
}

func initDP(n int) {
	dp = make([][]info, n+1)
	for i := range loop0(n + 1) {
		dp[i] = make([]info, n+1)
	}
}

func loop0(n int) chan int {
	return loop(0, n-1, 1)
}

func loop1(n int) chan int {
	return loop(1, n, 1)
}

func loop(s, e, d int) chan int {
	ch := make(chan int)
	go func() {
		for i := s; i <= e; i += d {
			ch <- i
		}
		close(ch)
	}()
	return ch
}

// snip-scan-funcs
func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return int(i)
}
func scanString(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 4368
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = 0
pre = -1

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

Measured memory_bytes: 3064
N, M = input().split(' ')
N = int(N)
M = int(M)
K1 = input().split(' ')
Like = [int(K1[i]) for i in range(1, len(K1))]
Like = set(Like)
for i in range(N-1):
  K = input().split(' ')
  K = [int(K[i]) for i in range(1, int(K[0])+1)]
  K = set(K)
  Like &= K
print(len(Like))

Measured memory_bytes: 9144
#include <iostream>
#include <queue>
#include <algorithm>
#include <set>
#include <vector>
#include <string>

using namespace std; using ll=long long; const int INF=1e9; using P=pair<int,int>;

int main() {
  int n; cin>>n;
  int a[2]={};
  for(int i=0;i<n;i++) {
    int b; cin>>b; a[b%2]++;
  }
  if (a[1]%2) cout<<"NO"<<endl;
  else cout<<"YES"<<endl;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define all(v) (v).begin() , (v).end()
#define popcnt(x) __builtin_popcount(x)
#define inf 0x3f3f3f3f
#define watch(x) cout << (#x) << " is " << (x) << endl
#define rand() (rand() << 15 | rand())
using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long  ll;
#define EPS 1e-9
#define PI acos(-1.0)
const int MOD = 1e9 + 7;



int main() {
   ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
   int a , b;
   cin >> a >> b;
   cout << 1ll * a * (b / __gcd(a , b)) << "\n";
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <climits>
#include <queue>
#include <map>
using namespace std;

typedef map<int, int>::iterator mitr;

map<int, int> w[10000];
int d[10000];
char pos[10000];

priority_queue<pair<int,int> > others;
pair<int,int> p;

void findPath(){
    p = others.top();
    others.pop();
    while(pos[p.second]){
        p = others.top();
        others.pop();
    }
    pos[p.second]=1;

    int tmpu = p.second;
    int tmpd = -p.first;

    for(mitr i=w[tmpu].begin();i!=w[tmpu].end();i++){
        if(tmpd + i->second < d[i->first]){
            d[i->first] = tmpd + i->second;
            others.push(make_pair(-d[i->first],i->first));
        }
    }
}

int main(){
    int i,j,u,k,n,v,c;

    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d %d",&u,&k);
        for(j=0;j<k;j++){
            scanf("%d %d",&v,&c);
            w[u][v] = c;
        }
    }

    memset(pos,0,sizeof(char)*100);
    for(i=0;i<n;i++)d[i]=INT_MAX;
    d[0] = 0;
    others.push(make_pair(0,0));
    for(i=0;i<n;i++)findPath();
    for(i=0;i<n;i++)printf("%d %d\n",i,d[i]);

    return 0;
}



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

namespace abc131_d
{
  class Program
  {
    static void Main(string[] args)
    {
      var n = CIn.ReadInt();

      var jobs = new Job[n];

      for (var i = 0; i < n; i++)
      {
        jobs[i] = new Job(CIn.ReadInt(), CIn.ReadInt());
      }

      Array.Sort(jobs, (a, b) => a.Deadline - b.Deadline);

      var sum = 0;

      foreach (var e in jobs)
      {
        sum += e.RequiredTime;

        if (sum > e.Deadline)
        {
          Console.WriteLine("No");
          return;
        }
      }

      Console.WriteLine("Yes");
    }
  }

  class Job
  {
    public int RequiredTime;
    public int Deadline;

    public Job(int r, int d)
    {
      RequiredTime = r;
      Deadline = d;
    }
  }

  class CIn
  {
    private static readonly Queue<string> fieldBuffer = new Queue<string>();

    public static string Read()
    {
      if (fieldBuffer.Count == 0)
      {
        foreach (var field in Console.ReadLine().Split())
        {
          fieldBuffer.Enqueue(field);
        }
      }

      return fieldBuffer.Dequeue();
    }

    public static int ReadInt() => int.Parse(Read());
    public static long ReadLong() => long.Parse(Read());
    public static double ReadDouble() => double.Parse(Read());

    public static string[] ReadStringArray(long n)
    {
      var array = new string[n];

      for (var i = 0; i < n; i++)
      {
        array[i] = Read();
      }

      return array;
    }

    public static int[] ReadIntArray(long n)
    {
      var array = new int[n];

      for (var i = 0; i < n; i++)
      {
        array[i] = ReadInt();
      }

      return array;
    }

    public static long[] ReadLongArray(long n)
    {
      var array = new long[n];

      for (var i = 0; i < n; i++)
      {
        array[i] = ReadLong();
      }

      return array;
    }
    public static double[] ReadDoubleArray(long n)
    {
      var array = new double[n];

      for (var i = 0; i < n; i++)
      {
        array[i] = ReadDouble();
      }

      return array;
    }
  }
}

Measured memory_bytes: 23468
#include <bits/stdc++.h>
#define sf sacnf
#define pf printf
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define ii pair <int,int>
#define iii pair <int,ii>
#define pll pair <ll,ll>
#define plll pair <ll,pll>
#define Ziru 0
using namespace std;

int main(){
    int a,b;

    while(cin>>a>>b, a&&b){
        for(int i=0; i<a; i++){
            for(int j=0; j<b; j++){
                cout<<"#";
            }
            cout<<endl;
        }
        cout<<endl;
    }
    return Ziru;
}



Measured memory_bytes: 3100
N,K = map(int,input().split())

hogelist = [0] * N

for i in range(K):
    d = int(input())
    tmplist = list(map(int,input().split()))
    for j in tmplist:
        hogelist[j-1] = 1

count = 0
for i in hogelist: 
    if i == 0:
        count += 1

print(count)

Measured memory_bytes: 9204
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for (int i=(a); i>=(b); --i)
#define REP(i,b) for (int i=0; i<(b); ++i)
#define endl '\n'
#define sz(x) (int) x.size()
#define mod %
#define fillchar(x,y,z) memset(x,z,y)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define sqr(x) ((x)*(x))
typedef long long int64;
typedef unsigned long long qword;
using namespace std;
const int maxn=1e5+5;
vector<int> adj[maxn];
vector<int64> f[maxn];
int st[maxn],par[maxn],id[maxn];
int64 L[maxn],R[maxn];
int base,n;
void Input()
{
    cin >> n >> base;
    FOR(i,1,n-1) {
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}
void DFS(int u)
{
    int top=0;
    f[u].back()=1;
    for (int v:adj[u]) {
        if (par[u]==v) continue;
        ++top;
        id[v]=top;
        par[v]=u;
        DFS(v);
        f[u].back()=f[u].back()*(f[v].back()+1) mod base;
    }
    top=0;
    for (int v:adj[u]) if (par[v]==u){
        st[++top]=f[v].back()+1;
    }
    L[0]=R[top+1]=1;
    FOR(i,1,top)
        L[i]=L[i-1]*st[i] mod base;
    FORR(i,top,1) {
        f[u][i]=L[i-1]*R[i+1] mod base;
        R[i]=R[i+1]*st[i] mod base;
    }
}
void GetRes(int u)
{
    int tmp=1;
    if (u!=1) {
        int pos=id[u];
        tmp=(f[par[u]][pos]+1) mod base;
        f[u].back()=f[u].back()*tmp mod base;
    }
    for (int v:adj[u]) {
        if (par[u]==v) continue;
        int pos=id[v];
        f[u][pos]=(f[u][pos]*tmp) mod base;
        GetRes(v);
    }
}
void Solve()
{
    FOR(i,1,n)
        f[i].resize(adj[i].size()+1+(i==1));
    DFS(1);
    GetRes(1);
    FOR(i,1,n) cout << f[i].back() << endl;
}
int main()
{
    #ifdef meomeomeooooo
        freopen("input.txt","r",stdin);
        //freopen(".out","w",stdout);
    #endif // meomeomeooooo
    iostream::sync_with_stdio(false);
    cin.tie(0);
    Input();
    Solve();
    return 0;
}


Measured memory_bytes: 20224
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

int main()
{
    int N, i, alice, bob;
    int a[100];

    cin >> N;

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

    sort(a, a + N, greater<int>());

    alice = 0;
    bob = 0;

    for (i = 0; i < N; i++)
    {
        if (i % 2 == 0)
            alice += a[i];
        else
            bob += a[i];
    }

    cout << alice - bob << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <list>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
#include <string>
#define N 100005
#define INF (1 << 30)
typedef long long ll;
using namespace std;
 
vector<int> child[N];
int parent[N];
int GetDepth(int idx)
{
    int ret = 0;
    while (parent[idx] != -1)
    {
        ++ret;
        idx = parent[idx];
    }
    return ret;
}
const char *str[3] = { "root", "internal node", "leaf" };
int main()
{
    int n;
    scanf("%d", &n);
    fill(parent, parent + n, -1);
    int id, k, c;
    for (int i = 0; i < n; ++i)
    {
        scanf("%d %d", &id, &k);
        for (int j = 0; j < k; ++j)
        {
            scanf("%d", &c);
            parent[c] = id;
            child[id].push_back(c);
        }
    }
    for (int i = 0; i < n; ++i)
    {
        int depth = GetDepth(i);
        int status;
        if (depth == 0)
            status = 0;
        else if (child[i].size())
        {
            status = 1;
        }
        else
            status = 2;
        printf("node %d: parent = %d, depth = %d, %s, ", i, parent[i], depth, str[status]);
        printf("[");
int size = child[i].size();
        for (int j = 0; j < size; ++j)
        {
            if (j)
                printf(", ");
            printf("%d", child[i][j]);
        }
        printf("]\n");
    }
    return 0;
}

Measured memory_bytes: 6756
#include<stdio.h>
int main(){
	int s[9000],n,m,t,f,i;
	while(scanf("%d%d",&n,&m)&&n)
		for(i=t=f=1;i<=n+m;i++){
			scanf("%d",&s[i]);
			if(i>n){t+=s[t+=s[i]];
				if(t>=n&f==1){
					printf("%d\n",i-n);
					f=0;
			}
		}}
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin >> n >> m;
  vector<int> a(m),b(m);
  vector<int> c(n,0);
  for(int i=0;i<m;i++){
    cin >> a[i] >> b[i];
    c[a[i]-1]++;
    c[b[i]-1]++;
  }
  for(int i=0;i<n;i++){
    cout << c[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
template <class T>
using Vec2 = vector<vector<T>>;
#define REP(i, m, n) for(ll i = (m); i < (n); ++i)
#define REPN(i, m, n) for(ll i = (m); i <= (n); ++i)
#define REPR(i, m, n) for(ll i = (m)-1; i >= (n); --i)
#define REPNR(i, m, n) for(ll i = (m); i >= (n); --i)
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define fs first
#define sc second
template <class T1, class T2>
bool chmax(T1 &a, const T2 b){if(a < b){a = b; return true;} return false;}
template <class T1, class T2>
bool chmin(T1 &a, const T2 b){if(a > b){a = b; return true;} return false;}
ll pow2(const int n){return (1LL << n);}
void co() { cout << endl; }
template <class Head, class... Tail>
void co(Head&& head, Tail&&... tail) {
    cout << head << ' ';
    co(forward<Tail>(tail)...);
}
void ce() { cerr << endl; }
template <class Head, class... Tail>
void ce(Head&& head, Tail&&... tail) {
    cerr << head << ' ';
    ce(forward<Tail>(tail)...);
}
void sonic(){ios::sync_with_stdio(false); cin.tie(0);}
void setp(const int n){cout << fixed << setprecision(n);}
constexpr int INF = 1e9+1;
constexpr ll LINF = 1e18L+1;
constexpr ll MOD = 1e9L+7;
constexpr ll MOD_N = 998244353;
constexpr ld EPS = 1e-11;
const double PI = acos(-1);

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

    ll ans = -LINF * 2;
    chmax(ans, a * c);
    chmax(ans, a * d);
    chmax(ans, b * c);
    chmax(ans, b * d);
    co(ans);

    return 0;
}


Measured memory_bytes: 3636
/*  -*- coding: utf-8 -*-
 *
 * b.cc: B: Stone Monument
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

/* typedef */

/* global variables */

/* subroutines */

/* main */

int main() {
  int a, b;
  scanf("%d%d", &a, &b);

  int n = b - a;
  printf("%d\n", n * (n + 1) / 2 - b);
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string s;
  int ans = 0;
  cin >> s;
  if (s[1] == 'S'){
    for (int i = 0; i < 3; i++){
      if(s[i] == 'R') ans = 1;
    }
  }else{
    for (int i = 0; i < 3; i++){
      if(s[i] == 'R') ans += 1;
    }
  }  
    cout << ans << endl; 
  return 0;
} 

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

int main(){
    int64_t N, K;
    cin >> N >> K;
    int64_t amari = N % K;
    int64_t hanten = K - amari;
    if(amari < hanten) cout << amari << endl;
    else cout << hanten << endl;
}

Measured memory_bytes: 256
Module Program
  Sub Main
    Dim a = GetInts()(0)
    Dim b = GetInts()(0)
    Dim c = GetInts()(0)
    Dim d = GetInts()(0)
    Dim ans=Math.Min(a,b)+Math.Min(c,d)
    Console.WriteLine(ans)
  End Sub
  
  '/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/
  Function Gets() As String()
    Gets = Console.ReadLine().Split(" "c)
  End Function
  Function GetInts() As Integer()
    Dim s = Gets(), r(UBound(s)) As Integer
    For i As Integer=0 To UBound(s): r(i)=s(i): Next i
    GetInts = r
  End Function
End Module

Measured memory_bytes: 20432
n = gets.to_i

edges = []
g = Array.new(n+1){ [] }
(n-1).times do |i|
  a, b = gets.split.map(&:to_i)
  a, b = b, a if a > b # 辺は頂点 i < j の形で入れる。
  g[a] << b+i*100_001 # 隣接リストに
  g[b] << a+i*100_001 # 反対向きにも隣接リストに.無向グラフなので
  # gに隣接頂点だけでなく、何番目の辺の情報をいれることもある。
  edges << a+b*100_000 # 辺リストにいれる。辺が識別されてて、最後に辺リストから辺を回して色をとりだす。
end

colors = Array.new(n-1) # Esge => color # 辺についてO(1)で使った色を見れる。O(1)はホントに?
colors_used = Hash.new # 頂点と色についてO(1)で使ったか確かめられる。
used = Array.new(n){false} # 頂点について探索済みかどうかO(1)でわかる。
que = [1] # 頂点1から見ていくので0が入っている # 探索待ちの未探索の頂点リスト

k = g.map(&:size).max # 答えとなる色の数
while v = que.shift # queにある頂点を取り出す. 破壊的メソッドなので先頭は削除される。なければnilを返す
  # k = g[v].size if k < g[v].size  # 隣接する頂点数より色数が小さければ色数を更新
  cur = 1 # 使ってない色がわからないので、とりあず色1から見ていく。
  g[v].each do |tmp| # vの隣接頂点wを見ていく。
    w = tmp % 100_001
    idx = tmp / 100_001
    next if used[w] #trueで、探索済みの頂点なら見ない。
    v<w ? (i,j = v,w) : (i,j = w,v) # i < jの並びで頂点を捉える。
    cur += 1 while colors_used[v+cur*100_000] == true # v周りの頂点で色をつかっていれば次の色に更新していく。塗る前に使ってない色にする。
    colors_used[v+cur*100_000] = true # vに色を使ったので記録する。
    colors_used[w+cur*100_000] = true # wに色を使ったので記録する。
    colors[idx] = cur # 辺に使った色をいれる。
    que.push(w) #探索待ちの未探索頂点リストに頂点wを入れる。
  end
  used[v] = true # 頂点vを探索済みにする。
end

puts k, colors

Measured memory_bytes: 27644
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[300001],s[300001];
inline int sum(int l,int r){return s[r]-s[l-1];}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld",a+i),s[i]=s[i-1]+a[i];
	int ans=1ll<<60;
	for(int i=2,l=1,r=3;i<n-1;i++)
	{
		r=max(r,i+1);
		while(l<i-1&&abs(sum(l+1,i)-sum(1,l))>abs(sum(l+2,i)-sum(1,l+1)))l++;
		while(r<n-1&&abs(sum(r+1,n)-sum(i+1,r))>abs(sum(r+2,n)-sum(i+1,r+1)))r++;
		ans=min(ans,max(max(sum(1,l),sum(l+1,i)),max(sum(i+1,r),sum(r+1,n)))-min(min(sum(1,l),sum(l+1,i)),min(sum(i+1,r),sum(r+1,n))));
	}
	printf("%lld\n",ans);
	return 0;
}


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

int main(){
    int N, M;
    cin >> N >> M;
    vector<int> k(M);
    vector<vector<int>> s(M, vector<int>(N));
    for(int x = 0; x < M; x++){
        cin >> k.at(x);
        for(int y = 0; y < k.at(x); y++){
            cin >> s.at(x).at(y);
        }
    }
    vector<int> p(M);
    for(int i = 0; i < M; i++){
        cin >> p.at(i);
    }
    int ans = 0;
    for(int bit = 0; bit < (1 << N); bit++){
        bool judge = true;
        for(int i = 0; i < M; i++){
            int count = 0;
            for(int j = 0; j < s.at(i).size(); j++){
                if(bit & (1 << s.at(i).at(j))){
                    count++;
                }
            }
            if(count % 2 != p.at(i)){
                judge = false;
                break;
            }
        }
        if(judge) ans++;
    }
    cout << ans << endl;

}

Measured memory_bytes: 256
#122-C
n,q=map(int,input().split())
s=input()
l=[list(map(int,input().split())) for i in range(q)]
m=[0]*(n+1)
for i in range(len(s)-1):
    
    if s[i]=='A' and s[i+1]=='C':
        m[i+1]=m[i]+1
    else:
        m[i+1]=m[i]

for i in l:
    print(m[i[1]-1]-m[i[0]-1])

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

int main() {
    int time[5];
    int ans = 0;
    int last_dish;
    int last_dish_time = 0;
    int fixed_time[5];
    for (int i = 0; i < 5; i++) {
        cin >> time[i];
    }
    for (int i = 0; i < 5; i++) {
        if (time[i] % 10 == 0) {
            fixed_time[i] = time[i];
        } else {
            fixed_time[i] = 10 * (time[i] / 10 + 1);
        }
        if (last_dish_time < fixed_time[i] - time[i]) {
            last_dish_time = fixed_time[i] - time[i];
            last_dish = i;
        }
    }
    for (int i = 0; i < 5; i++) {
        if (i == last_dish) {
            ans += time[i];
        } else {
            ans += fixed_time[i];
        }
    }
    cout << ans << endl;
}


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

#define int long long
 
// loop
#define FOR(i, a, b) for (int i = (a); i < (b); i++) 	// a ~ b-1	(ascending)
#define REP(i, n) FOR(i, 0, n)							// 0 ~ n-1
#define NREP(i, n) FOR(i, 1, n + 1)						// 1 ~ n
#define RFOR(i, a, b) for (int i = (a); i >= (b); i--)	// a ~ b	(descending)
#define RREP(i, n) RFOR(i, n, 0)						// n ~ 0
#define RNREP(i, n) RFOR(i, n, 1)						// n ~ 1
 
// container operation
#define EACH(i, c) for (auto i = (c).begin(); i != (c).end(); i++)
#define ASORT(c) std::sort((c).begin(), (c).end())
#define DSORT(c) std::sort((c).begin(), (c).end(), std::greater<typeof((c).front())>())
#define SIZE(x) ((int)(x).size())
 
// debug
#define check(x) std::cout << #x << " = " << x << '\n'
 
// print
#define cout(x) std::cout << x << '\n'
 
// type alias
using VI = std::vector<int>;
using VII = std::vector<VI>;
using VB = std::vector<bool>;
using VBB = std::vector<VB>;
using VS = std::vector<std::string>;
using PII = std::pair<int, int>;

std::string yes = "Yes\n";
std::string no = "No\n";

void solve();

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  solve();
  return 0;
}

void solve() {
  int x, a, b;
  std::cin >> x >> a >> b;
  int absa = abs(a - x);
  int absb = abs(b - x);
  if (absa < absb) {
    cout('A');
  } else {
    cout('B');
  }
}


Measured memory_bytes: 256
n = int(input())
s = str(input())

l = list(s)

c_color = l[0]
slimes = []
count = 0
for item in l:
    if not item == c_color:
        slimes.append(c_color)
        count += 1
        c_color = item

slimes.append(c_color)
count += 1
c_color = item

print(count)

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

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

typedef long long ll;
typedef pair<int, int> P;

#define MAX 100005
#define INF 1001001001

int main(int, char**)
{
  int n, q;
  cin >> n >> q;
  vector< priority_queue<int> > a(n);

  vector<int> ans;
  rep(i,q) {
    int command;
    cin >> command;
    if (command == 0) {
      int t, x; cin >> t >> x;
      a[t].push(x);
    } else if (command == 1) {
      int t; cin >> t;
      if (!a[t].empty()) ans.push_back(a[t].top());
    } else {
      int t; cin >> t;
      if (!a[t].empty()) a[t].pop();
    }
  }
  for (auto a : ans) cout << a << endl;

  return 0;
}



Measured memory_bytes: 4224
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
static class Program{
	const int mod=998244353;
	static void Main(){
		Sc sc=new Sc();
		int n=sc.I;
		int[][][] dp=new int[n+1][][];
		dp[0]=new int[1][];
		dp[0][0]=new int[]{1,0,0,0};
		int m=0,g=0;
		long[][] dp2=new long[n+1][];
		dp2[0]=new long[]{1,0,0,0};
		int[] a=new int[n];
		for(int i=0;i<n;i++){
			a[i]=sc.I;
			g+=a[i];
		}
		g=g/2+(g%2);
		for(int i=0;i<n;i++){
			dp[i+1]=new int[g+1][];
			for(int j=0;j<=g;j++){dp[i+1][j]=new int[4];}
			for(int j=0;j<=m;j++){
				for(int k=0;k<4;k++){
					if(dp[i][j][k]==0){continue;}
					dp[i+1][Math.Min(j+a[i],g)][k]=(dp[i+1][Math.Min(j+a[i],g)][k]+dp[i][j][k])%mod;
					dp[i+1][j][k|1]=(dp[i+1][j][k|1]+dp[i][j][k])%mod;
					dp[i+1][j][k|2]=(dp[i+1][j][k|2]+dp[i][j][k])%mod;
				}
			}
			m=Math.Min(m+a[i],g);
			dp2[i+1]=new long[4];
			for(int j=1;j<=3;j++){dp2[i+1][j]=(((dp2[i][j]*j)%mod)+((dp2[i][j-1]*j)%mod))%mod;}
		}
		Console.WriteLine("{0}",(dp2[n][3]-(((long)dp[n][g][3]*3)%mod)+mod)%mod);
	}
}

public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()).Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
}

Measured memory_bytes: 765068
input = gets.to_s
arrayOfInput = []
arrayOfInput << input.split(" ")[0].to_i
arrayOfInput << input.split(" ")[1].to_i
arrayOfInput << input.split(" ")[2].to_i
arrayOfInput << input.split(" ")[3].to_i

if arrayOfInput.include?(1) && arrayOfInput.include?(7) && arrayOfInput.include?(9) && arrayOfInput.include?(4) then
    puts "YES"
else
    puts "NO"
end

Measured memory_bytes: 1788
import sys
input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    cake = [[0]*W for _ in range(H)]
    sb = []
    for y in range(H):
        s = input().strip()
        for x, c in enumerate(s):
            if c == "#":
                sb.append((y, x))
    for i, (y, x) in enumerate(sb):
        cake[y][x] = i+1

    import collections
    for i, s in enumerate(sb):
        Q = collections.deque()
        Q.appendleft(s[1])
        y = s[0]
        while Q:
            x = Q.pop()
            if x-1 >= 0 and cake[y][x-1] == 0:
                cake[y][x-1] = i+1
                Q.appendleft(x-1)
            if x+1 <= W-1 and cake[y][x+1] == 0:
                cake[y][x+1] = i+1
                Q.appendleft(x+1)

    for y in range(1, H):
        for x in range(W):
            if cake[y][x] == 0:
                cake[y][x] = cake[y-1][x]
    for y in range(H-2, -1, -1):
        for x in range(W):
            if cake[y][x] == 0:
                cake[y][x] = cake[y+1][x]

    for c in cake:
        print(*c)


if __name__ == '__main__':
    main()


Measured memory_bytes: 14552
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, n) for(ll i = 1; i < n + 1; i++)
#define PI 3.14159265359
#define EPS 0.0000000001
#define MOD 1000000007
//cout << std::fixed << std::setprecision(15) << y << endl;


vector<bool> isPrime; // maxまでの全整数に対し素数かどうかの表
vector<ll> primes; // 素数が順に格納
ll primesP; // primesのアクセス用

void sieve(ll max){
    if(max + 1 > isPrime.size()){ // resizeで要素数が減らないように
        isPrime.resize(max + 1, true); // IsPrimeに必要な要素数を確保
    } 
    isPrime[0] = false; // 0は素数ではない
    isPrime[1] = false; // 1は素数ではない

    for(ll i = 2; i * i <= max; i++){ // 0からsqrt(max)まで調べる
        if(isPrime[i]){ // iが素数ならば
            for(ll j = 2; i * j <= max; j++){ // (max以下の)iの倍数は
                isPrime[i * j] = false; // 素数ではない
            }
        }
    }

    for(ll i = 0; i <= max; i++){ // 素数の数列を作成
        if(isPrime[i]){
            primes.push_back(i);
        }
    }
}

int main(){
    ll X;
    cin >> X;

    sieve(1000000);

    primesP = 0;
    while(primes[primesP] < X){
        primesP++;
    }

    cout << primes[primesP] << endl;

    return 0;
}

Measured memory_bytes: 4420
require 'pp'
IS_DEBUG = true
# IS_DEBUG = false
def dputs str
	if(IS_DEBUG)
		puts str
	end
end
def dpp str
	if(IS_DEBUG)
		pp str
	end
end

N,d=gets.chomp.split(' ').map{|n| n.to_i}
C=gets.chomp.split(' ').map{|n| n.to_i}
1.upto(N-1){|i|
	C[i] += C[i-1]
}
min = 99999999999999999999
0.upto(N-2){|i|
	val = ((C[N-1]-C[i])-C[i]).abs
	if(min > val)
		min = val
	end
}
puts min


Measured memory_bytes: 16776
S=input()
if S=='SUN':
  print(7)
elif S=='MON':
  print(6)
elif S=='TUE':
  print(5)
elif S=='WED':
  print(4)
elif S=='THU':
  print(3)
elif S=='FRI':
  print(2)
elif S=='SAT':
  print(1)




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

int H,W;
int main() {
	while(true) {
		cin >> H >> W;
		if(H == 0 && W == 0) break;
		for (int i = 0; i < H; ++i) {
			for(int k=0; k<W; ++k) {
				if(i>0 && i < H-1 && k>0 && k < W-1) cout << ".";
				else cout << "#";
			}
			cout << endl;
		}
		cout << endl;
	}
}

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

#define MOD_1000000007 (1000000007LL)
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define rep1(i, n) for (long long i = 1; i < (long long)(n); i++)
#define rep0c(i, n) for (long long i = 1; i <= (long long)(n); i++)
#define rep1c(i, n) for (long long i = 1; i <= (long long)(n); i++)
#define rep2c(i, n) for (long long i = 2; i <= (long long)(n); i++)
#define repc0(n, i) for (long long i = (long long)(n); i >= 0; i--)

using namespace std;
typedef long long ll;

namespace cnt {
  int64_t mod = 0;

  std::map<std::pair<int64_t, int64_t>, int64_t> memo_C;

  int64_t C(int64_t n, int64_t r) {
    std::pair<int64_t, int64_t> key = std::make_pair(n, r);
    if(memo_C.find(key) != memo_C.end()) return memo_C[key];
    if(r == n || r == 0) return memo_C[key] = 1;
    memo_C[key] = C(n-1, r-1) + C(n-1, r);
    if(mod > 0) memo_C[key] %= mod;
    return memo_C[key];
  }
};

ll N, K;

void solve() {
  ll blue = K, red = N-K, mod;
  cnt::mod = mod = MOD_1000000007;
  printf("%lld\n", red+1);
  rep2c(i, blue) {
    ll res = 0LL;
    for(ll j = i-1; j <= red; j++) {
      res = (res + cnt::C(j-1, i-2) * (red-j+1)) % mod;
    }
    if(res > 0) {
      res = (res * cnt::C(blue-1, i-1)) % mod;
    }
    printf("%lld\n", res);
  }
  return;
}

int main() {
  scanf("%lld %lld", &N, &K);
  solve();
  return 0;
}

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

using namespace std;

using ll = long long;

class Matching{
    public:
    ll size;
    vector<vector<ll> > g;
    vector<ll> match;
    vector<bool> checked;

    Matching(ll n){
        size = n;
        g = vector<vector<ll> >(size);
        match = vector<ll>(size, -1);
        checked = vector<bool>(size, false);
    }

    void add_edge(ll u, ll v){
        g[u].push_back(v);
        g[v].push_back(u);
    }

    bool dfs(ll v){
        checked[v] = true;
        for(ll u: g[v]){
            ll m = match[u];
            if(m < 0 || !checked[m] && dfs(m)){
                match[v] = u;
                match[u] = v;
                return true;
            }
        }
        return false;
    }

    ll bipartite_matching(){
        ll res = 0;
        for(ll v=0;v<size;v++){
            if(match[v] < 0){
                fill(checked.begin(), checked.end(), false);
                if(dfs(v)){
                    res++;
                }
            }
        }
        return res;
    }
};

// GRL_7_A: verified
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    ll nx, ny, ne; cin >> nx >> ny >> ne;
    Matching mat(nx + ny);
    for(ll i=0;i<ne;i++){
        ll x, y; cin >> x >> y;
        mat.add_edge(x, nx + y);
    }
    cout << mat.bipartite_matching() << endl;
}


Measured memory_bytes: 3340
import java.util.*;
public class Main {
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        Object[] result = Arrays.stream(a.split(""))
        						.filter(s->s.equals("1"))
        						.toArray();
        System.out.println(result.length);
	}
}

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

const int MOD = 1000000007;
const int INF = 1e9;

int gcd(int a, int b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}

bool IsPrime(long long n){
  if(n == 1) return false;
  for(long long i = 2; i * i < n; i++){
    if(n%i == 0) return false;
  }
  return true;
}

vector<long long> EnumDivisors(long long n){
  vector<long long> res;

  for(long long i = 1; i * i <= n; i++){
    if(n % i == 0){
      res.push_back(i);
      if(n/i != i) res.push_back(n/i);
    }
  }
  sort(res.begin(), res.end());
  return res;
}

vector<pair<long long, long long>> PrimeFactorize(long long n){
  vector<pair<long long, long long>> res;

  long long a = 0;
  long long b = 0;

  for(long long i = 2; i * i <= n; i++){
    a = 0;
    if(n%i == 0){
      if(IsPrime(i)){
        while(n % i == 0){
          n /= i;
          a++;
        }
        res.push_back(make_pair(i, a));
      }
    }
  }

  if(n!= 1) res.push_back(make_pair(n, 1));

  return res;

}

int main(){
  int n;
  const int max_n = 1e6;
  long long a[max_n + 1];
  cin >> n;
  for(int i = 0; i < n; i++) cin >> a[i];

  vector<int> list(max_n + 1, 0);
  bool flag1 = 0;
  bool flag2 = 0;
  for(int i = 0; i < n; i++){
    vector<pair<long long, long long>> res;
    res = PrimeFactorize(a[i]);
    for(int j = 0; j < res.size(); j++){
      int num = res[j].first;
      if(list[num] > 0) flag1 = 1;
      list[num] ++;
    }
  }
  for(int i = 0; i < n; i++){
    if(list[i] == n) flag2 = 1;
  }

  string ans = "not coprime";
  if(flag2 == 0) ans = "setwise coprime";
  if(flag1 == 0) ans = "pairwise coprime";

  cout << ans << endl;
  

  return 0;
}

Measured memory_bytes: 14596
h,w = map(int,input().split())

s = ['-'*(w+2)]
for i in range(h):
    s += ['-'+input()+'-']
s += ['-'*(w+2)]

for hi in range(1,h+1):
    ans = ''
    for wi in range(1,w+1):
        if s[hi][wi] == '#':
            ans += '#'
        else:
            c = [s[hi-1][wi-1],s[hi][wi-1],s[hi+1][wi-1],s[hi-1][wi],s[hi+1][wi],s[hi-1][wi+1],s[hi][wi+1],s[hi+1][wi+1]]
            ans += str(c.count('#'))
    print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cctype>
#include<cstdlib>
#include<algorithm>
#include<bitset>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<complex>
#include<functional>
#include<climits>
#include<cassert>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
using namespace std;

int n;
deque<long long int> v;

vector<long long int> vv;
deque<long long int> d;

vector<long long int> mini;
vector<long long int> maxi;
bool flag[100002];
long long int calc(bool turn = false) {
	d = v;
	vv.clear();
	bool old = turn;
	mini.clear();
	maxi.clear();
	for (int i = 0; i < n; i++) {
		flag[i] = turn;
		if (turn == false) {
			mini.push_back(d.front());
			d.pop_front();
		}
		else {
			maxi.push_back(d.back());
			d.pop_back();
		}
		turn ^= true;
	}
	long long int ans = 0;
	for (auto el : mini) {
		ans -= el * 2LL;
	}
	for (auto el : maxi) {
		ans += el * 2LL;
	}
	if (flag[0] == false) {
		ans += mini.back();
		mini.pop_back();
	}
	else {
		ans -= maxi.back();
		maxi.pop_back();
	}
	if (flag[n-1] == false) {
		ans += mini.back();
		mini.pop_back();
	}
	else {
		ans -= maxi.back();
		maxi.pop_back();
	}
	return ans;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		long long int a;
		//scanf("%lld", &a);
		cin >> a;
		v.push_back(a);
	}
	int num = v.size() / 2;
	long long int ans = 0;
	for (int i = 0; i < num; i++) {

	}
	sort(v.begin(), v.end());
	printf("%lld\n", max(calc(0), calc(1)));
	return 0;
}

Measured memory_bytes: 2772
import sys
from collections import defaultdict

# sys.stdin = open('c1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def pos(X, Y):
    if Y == 0:
        return X
    if X == r:
        return r + Y
    if Y == c:
        return r + c + r - X
    if X == 0:
        return r + c + r + c - Y


r, c, n, = read_int_list()
x = [0, 0]
y = [0, 0]
a = []
for i in range(n):
    x[0], y[0], x[1], y[1] = read_int_list()
    if (x[0] in [0, r] or y[0] in [0, c]) and (x[1] in [0, r] or y[1] in [0, c]):
        for k in range(2):
            a.append((pos(x[k], y[k]), i))
m = len(a) // 2
a.sort()

res = 'YES'
started = set()
s = []
for p, i in a:
    if i not in started:
        started.add(i)
        s.append(i)
    else:
        if s[-1] != i:
            res = 'NO'
            break
        s.pop()

print(res)


Measured memory_bytes: 34036