akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cmath>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long int ll;
const ll INF = 1000000009LL;

vector<ll> comb;
vector<ll> A;
ll N;
ll M, D;

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


void makeComb(){
    for(ll i = 0; i <= (1<<M); i++){
        comb[i] = 1LL;
        for(ll j = 0; j < M; j++){
            if(comb[i] >= INF) break;
            if((i >> j) & 1) comb[i] = lcm(comb[i], A[j]);
        }     
    }
    return;
}

int main () {
    cin >> N >> M >> D;
    comb = vector<ll>((1<<M)+1, 0);
    A = vector<ll>(M);
    for(ll i = 0; i < M; i++) cin >> A[i];
    makeComb();
    ll pre = N;
    
    for(ll i = 0; i < D; i++){
        ll ret = 0LL;
        vector<ll> R(M);
        ll exist = 0;
        for(ll j = 0; j < M; j++){
            cin >> R[j];
            if(R[j] != -1) exist |= 1<<j;
        }
        bool update = false;

        ll step = 1LL;
        ll use = 0;
        for(ll j = 0; j <= comb[exist]; j+=step){
            ll f = 0;
            for(ll k = 0; k < M; k++){
                if(R[k] != -1 && (j % A[k]) != R[k]) f = 1;
                else if(R[k] != -1 && (j % A[k]) == R[k]){
                    if((use>>k) & 1) continue;
                    use |= (1<<k);
                    step = lcm(step, A[k]);
                }
            }
            if(f) continue;
            if(pre < j) continue;
            update = true; 
            ret = max(ret, ((pre - j) / comb[exist]) * comb[exist] + j);
        }
        if(!update){
            //if(D != 2) while(1){}
            cout << -1 << endl;
            return 0;
        }
        pre = ret;
    }
    cout << pre << endl;
    return 0;
}

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

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

const int MAX = 2e5 + 10;
const int INF = 1e9;
const int MOD = 1e9 + 7;

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int N, M, Q;
int L[MAX], R[MAX];
int p[MAX], q[MAX];
int sum[510][510];

int main() {
  // 入力
  scanf("%d %d %d", &N, &M, &Q);
  for (int i = 0; i < M; i++) scanf("%d %d", L + i, R + i);
  for (int i = 0; i < Q; i++) scanf("%d %d", p + i, q + i);

  for (int i = 0; i < M; i++) sum[L[i]][R[i]]++;
  // 累積和をとる
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      sum[i][j] += sum[i-1][j];
      sum[i][j] += sum[i][j-1];
      sum[i][j] -= sum[i-1][j-1];
    }
  }

  for (int i = 0; i < Q; i++) {
    printf("%d\n", sum[q[i]][q[i]] - sum[p[i]-1][q[i]] - sum[q[i]][p[i]-1] + sum[p[i]-1][p[i]-1]);
  }
  return 0;
}


Measured memory_bytes: 4608
#include <bits/stdc++.h>
#define l_ength size
using ll = long long;
const int mod = 1000000007;
const ll infll = (1ll<<60);
using namespace std;

ll dp[110][100010];
ll sum[100010];

int main(){
	int n, k; cin >> n >> k;
	vector<ll> a(n);
	for( auto &k : a ) cin >> k;
	dp[0][0] = 1;
	for( int i = 0; i <= k; ++i ){
		sum[i+1] = ( sum[i] + dp[0][i] ) % mod;
	}
	for( int i = 0; i < n; ++i ){
		for( ll j = 0; j <= k; ++j ){
			dp[i+1][j] = ( sum[j+1] - sum[ max( 0ll, j-a[i] ) ] + mod ) % mod;
		}
		for( int j = 0; j <= k; ++j ){
			sum[j+1] = ( sum[j] + dp[i+1][j] ) % mod;
		}
	}
	cout << dp[n][k] << endl;
}

Measured memory_bytes: 79360
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
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; }
typedef long long ll;
typedef pair<int,int> P;

int main(){
    int n;
    cin >> n;
    vector<string> v[20];
    for(int i=1;i<10;i++)v[1].push_back(to_string(i));
    for(int i=2;i<13;i++){
        for(auto s:v[i-1]){
            if(s[i-2]!='0')v[i].push_back(s+(char)(s[i-2]-1));
            v[i].push_back(s+s[i-2]);
            if(s[i-2]!='9')v[i].push_back(s+(char)(s[i-2]+1));
        }
    }
    int id = n;
    for(int i=1;i<13;i++){
        if(id<v[i].size()){
            cout << v[i][id-1] << endl;
            return 0;
        }
        else {
            id -= v[i].size();
        }
    }
}


Measured memory_bytes: 125672
/*
START BY THE NAME OF ALMIGHTY ALLAH
THIS WONT BE ACCEPTED
STOP_GIVING_UP

██╗███████╗████████╗██╗ █████╗ ██╗  ██╗
██║██╔════╝╚══██╔══╝██║██╔══██╗██║ ██╔╝
██║███████╗   ██║   ██║███████║█████╔╝
██║╚════██║   ██║   ██║██╔══██║██╔═██╗
██║███████║   ██║   ██║██║  ██║██║  ██╗
╚═╝╚══════╝   ╚═╝   ╚═╝╚═╝  ╚═╝╚═╝  ╚═╝




*/
#include<bits/stdc++.h>
#define l(i,a,n)for(int i=a;i<n;i++)
#define pb push_back
#define in insert
#define mp make_pair
#define lw(v) sort(v.begin(),v.end());
#define hi(v) sort(v.begin(),v.end(),greater<long long>());
#define all(v) v.begin(),v.end()
#define filein freopen ("input.txt", "r", stdin)
#define fileout freopen ("output.txt", "w", stdout)
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long t,r=1,r1=0,r2=0,k=0,a,b,c=1,m,d=0,n,e,f,x=0,g,p=0,q=0,y=0,z=0;
    vector<long long>v;
    vector<long long>u;
    set<long long>s;
    std::vector<int>::iterator it;
    string  s1,s2,s3,s4;
    cin>>s1;
l(i,0,3)
{
    if(s1[i]==s1[i+1])
    {
        cout<<"Bad";
        return 0;
    }
}
cout<<"Good";
}


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

int main()
{
  int n, k;
  cin >> n >> k;
  
  vector <int> nums(n, 0);
  for (int i = 0; i < n; i++){
    int m;
    cin >> m;
    m--;
    nums.at(m)++;
  }
  sort(nums.begin(), nums.end());
  
  int first = 0;
  while (nums.at(first) == 0) first++;
  
  int l;
  l = max(n - first - k, 0);
  
  int ans = 0;
  for (int i = first; i < first + l; i++){
    ans += nums.at(i);
  }
  cout << ans << endl;
}

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

int main() {
	int N;
    cin >> N;
    string color, ans;
    ans = "Three";
  
    for (int i = 0; i < N; i++) {
      cin >> color;
      
      if (color == "Y") {
        ans = "Four";
        break;
      }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
n, c, k = map(int, input().split())
T = sorted([int(input()) for _ in range(n)])
bus = 0
cus = 0
lmt = T[0] + k
for t in T:
    if cus == 0 or t > lmt:
        bus += 1
        cus = 1
        lmt = t + k
    else:
        cus +=1
    
    if cus == c:
        cus = 0
print(bus)


Measured memory_bytes: 8280
#include <bits/stdc++.h>
#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 equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }



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

  ll n, m, v, p;
  cin >> n >> m >> v >> p;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

  sort(a.begin(), a.end(), greater<ll>());
  ll ans = p;
  ll cnt1 = n, cnt2 = 0;
  ll sum = 0;
  FOR(i, p, n) {
    cnt1--, cnt2++;
    sum += a[i - 1];
    if (a[p - 1] > a[i] + m) break;
    ll res = cnt1 * m + (a[i] + m) * cnt2 - sum;
    if (res < m * v) break;
    ans++;
  }
  cout << ans << '\n';




  
  return 0;
}

Measured memory_bytes: 1024
S = input()
Q = int(input())



front = ''
back = ''

r_flg = False
for i in range(Q):
    q = input()
    if q == '1':
        r_flg = False if r_flg else True
        continue
        
    t,f,c = q.split()
    if not r_flg:
        if f == '1':
            front += c
        else:
            back += c
    else:
        if f == '1':
            back += c
        else:
            front += c
    
if not r_flg:
    print(front[::-1]+S+back)
else:
    print(back[::-1] + S[::-1] + front)

Measured memory_bytes: 4340
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int (i) = (a);(i) < (b);++(i))
#define REP(i,n) FOR(i,0,n)

int main(){
  int n;
  cin >> n;
  int odd,four;
  ll x;
  REP(i,n){
    cin >> x;
    if(x % 2 == 1)odd++;
    else if(x % 4 == 0)four++;
  }
  if(odd+four == n){
    if(odd-four <= 1)cout << "Yes" << endl;
    else cout << "No" << endl;
  }else{
    if(odd-four <= 0)cout << "Yes" << endl;
    else cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
using ll = long long;
using P = pair<int,int>;
using T = tuple<string,int,int>;
const ll inf = 1LL<<60;

int cnt(int x){
  int cnt = 0;
  for(int i = 1; i*i <= x; i++){
    if(x / i == 0) cnt += 2;
  }
  return cnt;
}

int main(){
  string s; cin >> s;
  char c[4] = {'A', 'T', 'C', 'G'};
  int ans = 0;
  for(int i = 0; i < s.size(); i++){
    int cnt = 0;
    for(int j = i; j < s.size(); j++){
      if(s[j] == 'A' || s[j] == 'T' || s[j] == 'C' || s[j] == 'G'){
        cnt++;
      }else break;
    }
    ans = max(ans, cnt);
  }
  cout << ans << endl;
  return 0;
}

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

int main(){
    string s,t;
    cin >> s >> t;
    int N=s.size();
    int M=t.size();
    int dp[N+1][M+1];
    for(int i=0;i<=N;i++) dp[i][0]=0;
    for(int j=0;j<=M;j++) dp[0][j]=0;

    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            if(s[i-1]==t[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
            }else{
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    //cout << dp[N][M] << endl;
    string ans="";
    int i=s.size();
    int j=t.size();
    while(i>0&&j>0){
        if(dp[i][j]==dp[i-1][j]) i--;
        else if(dp[i][j]==dp[i][j-1]) j--;
        else{
            ans+=s[i-1];
            i--,j--;
        }
    }
    reverse(ans.begin(),ans.end());
    cout << ans << endl;
}

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

using namespace std;
long long mod = 998244353;
long long dp[3030][3030][3];
int main()
{

int n,s;
cin >> n >> s;
vector <int> a(n);
for (int i=0; i<n; i++) cin >> a[i];



dp[0][0][0] = 1;
for (int i=0; i<n; i++)
        for (int j=0; j<=s; j++)
{
    (dp[i+1][j][0]+=dp[i][j][0]) %=mod;
    (dp[i+1][j][1] += dp[i][j][0] + dp[i][j][1]) %=mod;
    (dp[i+1][j][2] += dp[i][j][0] + dp[i][j][1]+ dp[i][j][2]) %=mod;
    if (j+a[i]<=s)
        {
            (dp[i+1][j+a[i]][1] += dp[i][j][0] + dp[i][j][1]) %=mod;
            (dp[i+1][j+a[i]][2] += dp[i][j][0] + dp[i][j][1]) %=mod;
        }
}

cout << dp[n][s][2];
}

/*
dp[i][s][t] = The number of combinations chosen from the first i elements, such that the sum of elements is s and
L has not been added to the tuple yet (When t = 0)
L has been added but R has not been added yet(When t = 1)
both L and R has been added to the tuple(When t = 2)

*/








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

using namespace std;
using i64 = int64_t;

i64 dp[105][100005];

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  i64 N, W;
  cin >> N >> W;
  vector<i64> w(N), v(N);
  for(int i=0;i<N;i++)cin >> w[i] >> v[i];
  for(int i=0;i<=N;i++)
    for(int j=0;j<=W;j++)
      dp[i][j] = -1;
  dp[0][0] = 0;
  for(int i=0;i<N;i++){
    for(int j=0;j<=W;j++){
      if(dp[i][j] < 0)
        continue;
      dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
	  if(j + w[i] <= W)
      	dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]], dp[i][j] + v[i]);
    }
  }
  i64 ret = 0;
  for(int i=0;i<=W;i++)ret = max(ret, dp[N][i]);
  cout << ret << endl;
}

Measured memory_bytes: 80128
#include <iostream>
#include <vector>
using namespace std;
int main() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  int sum_a = 0;
  for (int i = 0; i < n; ++i) {
    int a_i;
    cin >> a_i;
    a.at(i) = a_i;
    sum_a += a_i;
  }
  
  int x = 0;
  for (int i = 0; i < n; ++i) {
    if (a.at(i) * 4 * m >= sum_a) {
      ++x;
    }
  }
  if (x >= m) {
    puts("Yes");
  } else {
    puts("No");
  }
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int fibonacci(int n){
  int num1=1,num2=1,temp=1;
  int i;

  for(i=1;i<n;i++){
    temp = num1 + num2;
    num1 = num2;
    num2 = temp;
  }
  return temp;
}

int main(){
  int a,n;
  scanf("%d",&n);
  a=fibonacci(n);

  printf("%d\n",a);

  return 0;
}


Measured memory_bytes: 2036
#include <iostream>
#include <algorithm>

using namespace std;
int main(){
  const int MAX_num = 9;
  const int min_num = 0;
  int n = 0;
  for(int i=1;cin.eof()==false;i++){
    int count =0;
    n = -1;
    cin >> n;
    if(n==-1) break;
    for(int a = min_num; a < MAX_num+1; a++){
      for(int b = min_num; b < MAX_num+1; b++){
	for(int c = min_num; c < MAX_num+1; c++){
	  for(int d = min_num; d < MAX_num+1; d++){
	    if(a+b+c+d==n){
	      count++;
	    }
	  }
	}
      } 
    }
    cout << count<<endl;
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
typedef long long i64;
using std::cout;
using std::endl;
using std::cin;

int main(){
	int X, k, Q; cin >> X >> k; std::vector<int> r(k + 2, (1 << 30));
	for(int i = 0; i < k; i++) cin >> r[i + 1]; r[0] = 0;
	cin >> Q;
	
	int tap = 0, lis = X; // 潰れヴァリュー
	int low = 0, high = X; // 潰れ判定
	int cnt = 0, sum = 0;
	
	for(int i = 0; i < Q; i++) {
		int t, a; cin >> t >> a;
		
		while(r[cnt + 1] <= t) {
			int d = r[cnt + 1] - r[cnt];
			
			if(cnt % 2) {
				int uku = std::max(0, lis + d - X);
				high -= uku;
		
				tap = std::max(0, std::min(X, tap + d));
				lis = std::max(0, std::min(X, lis + d));
			} else {
				int luz = std::max(0, -(tap - d));
				low += luz;
				
				tap = std::max(0, std::min(X, tap - d));
				lis = std::max(0, std::min(X, lis - d));
			}
			
			cnt += 1;
		}
		
		int d = t - r[cnt];
		if(cnt % 2) {
			if(low <= a and a <= high) cout << std::max(0, std::min(X, tap + a - low + d)) << endl;
		 	else if(a < low) cout << std::max(0, std::min(X, tap + d)) << endl;
			else cout << std::max(0, std::min(X, lis + d)) << endl;
		} else {
			if(low <= a and a <= high) cout << std::max(0, std::min(X, tap + a - low - d)) << endl;
			else if(a < low) cout << std::max(0, std::min(X, tap - d)) << endl;
			else cout << std::max(0, std::min(X, lis - d)) << endl;	
		}
	}
	return 0;
}


Measured memory_bytes: 1664
#include <stdio.h>
int main(void) {
 long long int Q,H,S,D,N,twoL,Sum=0,YJ,oneL;
 scanf("%ld%ld%ld%ld",&Q,&H,&S,&D);
 scanf("%ld",&N);
 oneL=S;
if(oneL>2*H){oneL=2*H;};
if(oneL>4*Q){oneL=4*Q;};
if(2*oneL>D){twoL=D;}
else{twoL=2*oneL;}
Sum=(N-(N%2))/2*twoL+N%2*oneL;
 printf("%ld\n",Sum);
 return 0;
 }

Measured memory_bytes: 128
class UnionFind:
    def __init__(self, n):
        self.par =[i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

n,m,k=map(int,input().split())
A=UnionFind(n)

friend=[0 for i in range(n+1)]
blocked={i:[] for i in range(1,n+1)}
for i in range(m):
    a,b=map(int,input().split())
    friend[a]+=1
    friend[b]+=1
    A.union(a,b)
    
    
for j in range(k):
    x,y=map(int,input().split())
    
    blocked[x].append(y)
    blocked[y].append(x)
    
for i in range(1,n+1):
    A.find(i)
    
parent=A.par

howmany={i:0 for i in range(n+1)}

for i in range(1,n+1):
    x=parent[i]
    howmany[parent[i]]+=1
    
#howmanyに同じグループが何個あるか

lists=[]
for i in range(1,n+1):
    sums=howmany[parent[i]]-1-friend[i]
    for some in blocked[i]:
        if parent[i]==parent[some]:
            sums-=1
    lists.append(sums)
print(*lists)   


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

int top,s[100];

void push(int x)
{
    s[top++]=x;
    return;
}
int pop()
{
    int x=s[--top];
    return x;
}
int main()
{
    top=0;
    int a,b;
    char c;
    while(scanf("%c",&c)!=EOF)
    {
        if(c=='+')
        {
            a=pop();
            b=pop();
            push(a+b);
        }
        if(c=='-')
        {
            b=pop();
            a=pop();
            push(a-b);
        }
        if(c=='*')
        {
            a=pop();
            b=pop();
            push(a*b);
        }
        if(c>='0' && c<='9')
        {
            int num=c-'0';
            while(1)
            {
                scanf("%c",&c);
                if(c>='0'&&c<='9')
                    num=num*10+c-'0';
                else
                    break;
            }
            push(num);
        }
    }
    cout<<pop()<<endl;
    return 0;

}



Measured memory_bytes: 3168
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int N;
  cin>>N;
  vector<ll> A(N), B(N);
  for(int i=0;i<N;++i) cin>>A[i]>>B[i];
  sort(A.begin(), A.end());
  sort(B.begin(), B.end());
  ll tmpa, tmpb;
  if(N%2==0) {
    tmpa = A[N/2-1]+A[N/2];
    tmpb = B[N/2-1]+B[N/2];
    cout<<tmpb-tmpa+1<<endl;
  }
  else {
    tmpa = A[N/2];
    tmpb = B[N/2];
    cout<<tmpb-tmpa+1<<endl;
  }
}



Measured memory_bytes: 6368
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
long long n;
long long a[1000000],b[5];
int main()
{
    scanf("%lld",&n);
    int l=1;
    for(int i=0; i<n; i++)
    {
        scanf("%lld",&a[i]);
    }
    sort(a,a+n);
    b[0]=-1;
    for(int i=n-1;i>=0;i--)
    {
       if(a[i]==a[i-1])
       {
           b[l++]=a[i];
            i--;
       }
       if(l==3)  break;
    }
    if(l==3)
        printf("%lld\n",b[1]*b[2]);
    else
        printf("0\n");
    return 0;
}
/*

*/




Measured memory_bytes: 1024
#include<stdio.h>
int main(){
  int i,j,N,A[100],minj,count=0,temp;

  scanf("%d",&N);
  for(i=0;i<N;i++) scanf("%d",&A[i]);
  
  for(i=0;i<N;i++){
    minj=i;
    for(j=i;j<N;j++){
      if(A[j]<A[minj]) {
	minj=j;
      }
    }
    if(minj!=i){
      temp=A[i];
      A[i]=A[minj];
      A[minj]=temp;
      count++;
    }
  }
  
  for(i=0;i<N-1;i++) printf("%d ",A[i]);
  printf("%d\n",A[N-1]);
  printf("%d\n",count);
  
  return 0;
}

Measured memory_bytes: 600
from collections import Counter

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

l = []
for i in range(M):
    l.append(AB[i][0])
    l.append(AB[i][1])
cnt = Counter(l)

for i in range(N):
    print(cnt[i+1])

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

using namespace std;

#define N 220000

int n,cnt[200],c[200][N],a[N],bit[N];
long long ans;
char s[N],s1[N],s2[N];

void add(int x){for (int i=x;i<=n;i+=i&(-i)) bit[i]++;}

int qry(int x){int ret=0; for (int i=x;i;i-=i&(-i)) ret+=bit[i]; return ret;}

int main(){
    scanf("%s",s+1); n=strlen(s+1);
    for (int i=1;i<=n;i++) cnt[s[i]]++;
    bool fl=!(n&1);
    for (int i='a';i<='z';i++) if (cnt[i]&1){if (fl){puts("-1"); return 0;} fl=1;}
    char ch='?'; for (int i='a';i<='z';i++){if (cnt[i]&1) ch=i; ++cnt[i]/=2;}
    int xb=0,xb2=0;
    for (int i=1;i<=n;i++)
        if (cnt[s[i]]>0){
            if (ch==s[i] && cnt[s[i]]==1){s2[++xb2]=s[i]; cnt[s[i]]--;}
            else{cnt[s[i]]--; s1[++xb]=s[i]; ans+=i-xb;}
        }
        else s2[++xb2]=s[i];
    memset(cnt,0,sizeof cnt);
    for (int i=1;i<=xb;i++) c[s1[i]][++cnt[s1[i]]]=xb-i+1;
    memset(cnt,0,sizeof cnt);
    for (int i=xb2;i>=1;i--) a[i]=c[s2[i]][++cnt[s2[i]]]+1;
    for (int i=1;i<=xb2;i++){
        ans+=qry(n)-qry(a[i]); add(a[i]);
    }
    printf("%lld\n",ans);

    return 0;
}


Measured memory_bytes: 25984
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <iomanip>

using namespace std;

#define FAST       			ios_base :: sync_with_stdio(false); cin.tie(NULL); 
#define endl "\n"

typedef long long int  ll;
typedef unsigned long long int ull;

int count(int n)
{
	int ans = 0;
	while(n%2 == 0)
	{
		n = n/2;
		ans++;
	}

	return ans;
}

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


	int maxNum = -1;
	int maxCount = -1;
	for(int i=1 ; i<=n ; i++)
	{
		int ans = count(i);
		if(ans > maxCount)
		{
			maxCount = ans;
			maxNum = i;
		}
	}

	cout << maxNum;
	return 0;
}

Measured memory_bytes: 256
using System;

class Program
{
    static void Main(string[] args)
    {
        var abq = Console.ReadLine().Split();
        var A = int.Parse(abq[0]);
        var B = int.Parse(abq[1]);
        var Q = int.Parse(abq[2]);

        var s = new long[A];
        for (int i = 0; i < A; i++)
            s[i] = long.Parse(Console.ReadLine());

        var t = new long[B];
        for (int i = 0; i < B; i++)
            t[i] = long.Parse(Console.ReadLine());

        var x = new long[Q];
        for (int i = 0; i < Q; i++)
            x[i] = long.Parse(Console.ReadLine());

        for (int i = 0; i < Q; i++)
        {
            var ans = Math.Min(
                m1(s, t, x[i]),
                m1(t, s, x[i]));

            Console.WriteLine(ans);
        }
    }

    static long m1(long[] x, long[] y, long p)
    {
        var min = long.MaxValue;
        var a = search(x, p);
        foreach (var i in new[] { a, a - 1 })
        {
            if (i < 0 || x.Length <= i) continue;

            var b = search(y, x[i]);
            foreach (var j in new[] { b, b - 1 })
            {
                if (j < 0 || y.Length <= j) continue;

                min = Math.Min(min,
                    Math.Abs(p - x[i]) + Math.Abs(x[i] - y[j]));
            }
        }
        return min;
    }

    static int search(long[] x, long n)
    {
        return search(x, n, 0, x.Length);
    }

    static int search(long[] d, long n, int x, int y)
    {
        if (x == y) return x;
        var k = (x + y) / 2;
        if (d[k] < n) return search(d, n, k + 1, y);
        else return search(d, n, x, k);
    }
}


Measured memory_bytes: 18492
#include<string>
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<map>
#include<functional>
using namespace std;
typedef long long int llint;
typedef bool izryt;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
const int big=1e9;
const int mod=1e9 + 7;
int main(void){
	llint r,c,n,i,j,q,w;cin>>n;
	vector<tuple<llint,llint,llint>> road(2*(n-1));
	vector<pair<llint,llint>>xs(n);
	vector<pair<llint,llint>>ys(n);
	vector<llint> go(n);
	vector<llint> ufr(n);
	for(i=0;i<n;i++){
		cin>>q>>w;
		xs[i]=mp(q,i);
		ys[i]=mp(w,i);
	}
	sort(xs.begin(),xs.end());
	sort(ys.begin(),ys.end());
	for(i=0;i<n-1;i++){
		road[i]=mt(xs[i+1].fir-xs[i].fir,xs[i].sec,xs[i+1].sec);
	}
	for(i=0;i<n-1;i++){
		road[i+n-1]=mt(ys[i+1].fir-ys[i].fir,ys[i].sec,ys[i+1].sec);
	}
	sort(road.begin(),road.end());
	for(i=0;i<n;i++){go[i]=i;}
	llint ren=n,ans=0;
	for(i=0;ren>1;i++){
		llint tqg=get<1>(road[i]);
		llint twg=get<2>(road[i]);
		while(tqg!=go[tqg]){tqg=go[tqg];}
		while(twg!=go[twg]){twg=go[twg];}
		if(tqg==twg){continue;}
		if(ufr[tqg]<ufr[twg]){swap(tqg,twg);}
		go[twg]=tqg;
		if(ufr[tqg]==ufr[twg]){ufr[tqg]++;}
		ans+=get<0>(road[i]);
		ren--;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 9600
max_number = 10 ** 18
len_number = int(input())
number_list = list(map(int, input().split()))

if 0 in number_list:
    print(0)
    exit(0)

number_list.sort(reverse=True)

is_over_max = False
answer = 1
for n in number_list:
    answer *= n
    if max_number < answer:
        is_over_max = True
        break

if is_over_max:
    print(-1)
else:
    print(answer)


Measured memory_bytes: 21588
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define sz(c) c.size()
#define all(c) c.begin(), c.end()

constexpr int MOD = 1e9 + 7;

int dp[310][310][310];

signed main() {
    int N, M;
    cin >> N >> M;
    unordered_map<int, vector<tuple<int, int, int>>> query;
    rep(i, 0, M) {
        int l, r, x;
        cin >> l >> r >> x;
        query[r].push_back(make_tuple(l, r, x));
    }

    dp[0][0][0] = 1;
    rep(r, 0, N + 1) {
        rep(g, 0, N + 1) {
            rep(b, 0, N + 1) {
//                fprintf(stderr, "r:%lld, g:%lld, b:%lld\n", r, g, b);
                int mx = max({r, g, b});
                int nxt = mx + 1;
                for (auto &tpl : query[mx]) {
                    int L, R, X;
                    tie(L, R, X) = tpl;
                    int cnt = 0;
                    if (L <= r) cnt++;
                    if (L <= g) cnt++;
                    if (L <= b) cnt++;
                    if (cnt != X) dp[r][g][b] = 0;
                }
                (dp[nxt][g][b] += dp[r][g][b]) %= MOD;
                (dp[r][nxt][b] += dp[r][g][b]) %= MOD;
                (dp[r][g][nxt] += dp[r][g][b]) %= MOD;
            }
        }
    }
    int ans = 0;
    rep(i, 0, N + 1) {
        rep(j, 0, N + 1) {
            (ans += dp[N][i][j]) %= MOD;
            (ans += dp[i][N][j]) %= MOD;
            (ans += dp[i][j][N]) %= MOD;
        }
    }
    cout << ans << endl;
}




Measured memory_bytes: 227584
/*"Success isn't permanent, failure isn't fatal,
                                      it's the courage to continue that counts"*/
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define ll long long 
#define scn(n) scanf("%d",&n)
#define lscn(n) scanf("%lld",&n)
#define lpri(n) printf("%lld",n)
#define pri(n) printf("%d",n)
#define pln() printf("\n")
#define priln(n) printf("%d\n",n)
#define lpriln(n) printf("%lld\n",n)
#define rep(i,init,n) for(int i=init;i<n;i++)
#define pb push_back     
#define mp make_pair
#define F first
#define S second
#define gcd __gcd
#define inf INT_MAX
#define ninf INT_MIN
const int mod=1e9+7;         
const int N=2e5+4;

ll fac[N],infac[N];
 
ll me(ll a,ll b)
{
    ll res=1;
 
    while(b)
    {
        if(b&1)
        res=(res*a)%mod;
 
        b>>=1;
 
        a=(a*a)%mod;
    }
 
    return res;
}
 
ll mi(ll a)
{
    return me(a,mod-2);
}
 
void factorial()
{
   fac[0]=1;
 
   for(ll i=1;i<N;i++)
   fac[i]=(i*fac[i-1])%mod;
 
   infac[N-1]=mi(fac[N-1]);
 
   for(ll i=N-1;i>=1;i--)
   infac[i-1]=(i*infac[i])%mod;
}
 
ll ncr(ll n,ll r)
{
    if(n<r)
    return 0;
 
    ll val=fac[n];
 
    val=(val*infac[r])%mod;
 
    val=(val*infac[n-r])%mod;
 
    return val;
}

ll sz[N],dp[N];

int n;

vector<int> v[N];

void dfs(int node,int par)
{
	sz[node]=1;

	int sum=n-1;

	for(int it:v[node])
	if(it!=par)
	{
		dfs(it,node);

		sum-=sz[it];

		sz[node]+=sz[it];
	}

	dp[node]=fac[sz[node]-1];

	for(int it:v[node])
	if(it!=par)
	{
		dp[node]=(dp[node]*infac[sz[it]])%mod;
		
		dp[node]=(dp[node]*dp[it])%mod;
	}
}
 
ll ans[N];

void dfs_reroot(int node,int par)
{
	ans[node]=dp[node];
	//ans[node]=(from_children[node]*dp[node])%mod;

	//cout<<node<<" "<<dp[node]<<endl;

	for(int it:v[node])
	if(it!=par)
	{
		dp[node]=(dp[node]*fac[sz[it]])%mod;

		dp[node]=(dp[node]*fac[n-1-sz[it]])%mod;

		dp[node]=(dp[node]*infac[n-1])%mod;

		dp[node]=(dp[node]*mi(dp[it]))%mod;

		dp[it]=(dp[it]*fac[n-1])%mod;

		dp[it]=(dp[it]*infac[sz[it]-1])%mod;

		dp[it]=(dp[it]*infac[n-sz[it]])%mod;

		dp[it]=(dp[it]*dp[node])%mod;

		dfs_reroot(it,node);

		dp[it]=(dp[it]*fac[sz[it]-1])%mod;

		dp[it]=(dp[it]*fac[n-sz[it]])%mod;

		dp[it]=(dp[it]*infac[n-1])%mod;

		dp[it]=(dp[it]*mi(dp[node]))%mod;

		dp[node]=(dp[node]*fac[n-1])%mod;

		dp[node]=(dp[node]*infac[sz[it]])%mod;

		dp[node]=(dp[node]*infac[n-1-sz[it]])%mod;

		dp[node]=(dp[node]*dp[it])%mod;
	}
}

int main()
{
	factorial();

	scn(n);

	rep(i,0,n-1)
	{
		int a,b;

		scn(a); scn(b);

		v[a].pb(b); v[b].pb(a);
	}

	dfs(1,-1);

	dfs_reroot(1,-1);

	rep(i,1,n+1)
	lpriln(ans[i]);

    return 0;
}

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

pair=[]
for _ in range(M):
    inp=list(map(int,input().split()))
    pair.append(inp)

loser=[]
for i in range(M):
    if h[pair[i][0]-1]<h[pair[i][1]-1]:
        loser.append(pair[i][0])
    elif h[pair[i][0]-1]>h[pair[i][1]-1]:
        loser.append(pair[i][1])
    else:
        loser.append(pair[i][0])
        loser.append(pair[i][1])

set_loser=set(loser)
ans=N-int(len(set_loser))
print(ans)

Measured memory_bytes: 34520
a = []
b = []

for i in range(3):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)

for i in range(3):
    for j in range(3):
        if not i == j:
            for k in range(3):
                if not j == k:
                    if not i == k:
                        if a[i] == a[j]:
                            if (b[j] == a[k]) or (b[j] == b[k]):
                                print("YES")
                                quit()
                        if a[i] == b[j]:
                            if (a[j] == a[k]) or (a[j] == b[k]):
                                print("YES")
                                quit()
                        if b[i] == a[j]:
                            if (b[j] == a[k]) or (b[j] == b[k]):
                                print("YES")
                                quit()
                        if b[i] == b[j]:
                            if (a[j] == a[k]) or (a[j] == b[k]):
                                print("YES")
                                quit()

print("NO")


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

if K > (N-1)*(N-2)//2:
    print(-1)
else:
    ans = []
    for i in range(N - 1):
        ans.append([i+1, N])
    add = (N-1)*(N-2)//2 - K
    edge = []
    for i in range(N - 1):
        for j in range(i):
            edge.append([i+1, j+1])
    for i in range(add):
        ans.append(edge[i])
    print(len(ans))
    for i in ans:
        print(i[0], end=' ')
        print(i[1])

Measured memory_bytes: 4148
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define int long long
#define all(a) a.begin(), a.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    rep(i, 0, n){
        cin >> h[i];
    }
    sort(h.begin(), h.end());
    int ans = INF;
    rep(i, 0, n - k + 1){
        int MIN = h[i];
        int MAX = h[i + k - 1];
        chmin(ans, MAX - MIN);
    }
    cout << ans << endl;
}

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

int main(){
    int h, w, n;
    cin >> h >> w >> n;
    char cake[300][300];
    bool cake_found[300];
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> cake[i][j];
            if(cake[i][j] == '#') cake_found[i] = true;
        }
    }
    int now = 0;
    int ans[300][300];
    for(int i = 0; i < h; i++){
        if(cake_found[i] == false){
            for(int j = 0; j < w;j++){
                ans[i][j] = 0;
            }
        }else{
            now++;
        bool next = false;
        for(int j = 0; j < w; j++){
            if(cake[i][j] == '#'){
                if(next) now++;
                next = true;
            }
            ans[i][j] = now;            
        }
        }
    }
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w;j++){
                
                if(ans[i][j] == 0){
                    for(int k = i+1; k < h; k++){
                        if(ans[k][j] != 0){
                            ans[i][j] = ans[k][j];
                            break;
                        }
                    }
                }
                
                if(ans[i][j] == 0){
                    for(int k = i-1; k >= 0; k--){
                        if(ans[k][j] != 0){
                            ans[i][j] = ans[k][j];
                            break;
                        }
                    }
                }
                        
                cout << ans[i][j] << " ";               
            }
            cout << endl;
        }
        
}


Measured memory_bytes: 1152
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<queue>
#include<deque>
#include<map>

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

using namespace std;
using ll = 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;}

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


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



int main() {
    int n; cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    ll ans = 0;
    ll mod = 1e9+7;
    for (int i = 0; i <= 60; i++) {
        int cnt = 0;
        for (int j = 0; j < n; j++)
        {
            if ((1ll << i) & a[j]) cnt++;
        }
        ans = (ans + (1ll<<i)%mod*cnt%mod*(n-cnt))%mod;
        // cout << ans << endl;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
const int mod = 1e9 + 7;
const int maxn = 100005;

void go() {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll ans = -1e18;
    ans = max(ans, b * d);
    ans = max(ans, b * c);
    ans = max(ans, a * c);
    ans = max(ans, a * d);
    if (a <= 0 && b >= 0) {
        ans = max(ans, 0LL);
    }
    if (c <= 0 && d >= 0) {
        ans = max(ans, 0LL);
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int c = 0;
    int t;
    if (!c) {
        t = 1;
    }
    else {
        cin >> t;
    }
    while (t--) {
        go();
    }
    
}

Measured memory_bytes: 3656
#include <cstdio>
#include <cstring>
#include <algorithm>

using LL = long long;

char str[20];

LL ans = 0;
int len;

void dfs(int i, LL acc, LL prev) {
    if (i == len) {
        ans += acc + prev;
        return ;
    }

    int dig = str[i]-'0';
    dfs(i+1, acc, prev*10 + dig);
    dfs(i+1, acc+prev, dig);
}

LL jizz() {
    len = strlen(str);

    dfs(1, 0, str[0]-'0');
    return ans;
}

int main() {
    scanf("%s", str);

    printf("%lld\n", jizz());

    return 0;
}


Measured memory_bytes: 128
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <iterator>
//#include <cmath>
#include <set>
#include <deque> 
#include <string>


using namespace std;

int n, m;
int a[10010];

int main()
{
	scanf("%d%d", &n, &m);
	int sum = 0;
	for (int i = 0 ; i < m ; i++) {
		scanf("%d", &(a[i]));
		sum = sum + a[i];
	}
	
	int left = n - sum;
	if (left < 0)
		left = -1;
	
	printf("%d\n", left);
		
		
	
	
	return 0;
}

Measured memory_bytes: 1760
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


# 初項s, 交差dのn個の数列の和
def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def main():
    N, M = map(int, input().split())
    state = []
    for _ in range(M):
        S = list(map(int, input().split()))

        v = [0] * N
        for s in S[1:]:
            v[s - 1] = 1
        state.append(v)
    P = list(map(int, input().split()))

    ans = 0
    for pattern in product([0, 1], repeat=N):
        all_on = True
        for i in range(M):
            num_on = 0
            for j in range(N):
                if state[i][j] == 1 and pattern[j] == 1:
                    num_on += 1

            if num_on % 2 != P[i]:
                all_on = False
                break

        ans += all_on

    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3948
#include <bits/stdc++.h>
#define repeat(i, n) for(ll i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

int N, Y, x = 0, y = 0, z = 0;
bool get_calc() {
	return (x * 10000 + y * 5000 + z * 1000) == Y && (x + y + z) == N;
}

int main() {
	bool is_exist = false;
	cin >> N >> Y;
	
	for(int i = 0; i <= N; i++) {
		for(int j = 0; j <= N - i; j++) {
			for(int k = 0; k <= N - i - j; k++) {
				is_exist = get_calc();
				if (is_exist) break;
				z++;
			}
			if (is_exist) break;
			z = 0;
			y++;
		}
		if (is_exist) break;
		y = 0;
		x++;
	}

	if (!is_exist) {
		x = y = z = -1;
	}
	cout << x << endl;
	cout << y << endl;
	cout << z << endl;
	return 0;
}


Measured memory_bytes: 256
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;

namespace mine
{
    typedef long long ll;
    const ll MOD=998244353;
	ll bin[4100];
	
    /*ll qpower(ll x,ll e)
    {
    	ll ans=1;
    	while(e>0)
    	{
    		if(e&1) ans=ans*x%MOD;
    		x=x*x%MOD;e>>=1;
		}
    	return ans;
	}
	ll inv(ll x) {return qpower(x,MOD-2);}
	ll fac[4100],facinv[4100];
	ll C(int n,int m) {return fac[n]*facinv[m]%MOD*facinv[n-m]%MOD;}
	*/
	
	ll c[4100][4100];
	ll C(int n,int m) {return c[n][m];}
	
	ll C2(int n,int m) {return C(n-1+m,n-1);}
	ll solve(int i,int K,int n)
	{
		ll tot=(i-1<=K)?(i-1):(2*K-i+1);
		tot=floor( (double)tot/2 );
		ll oth=K-tot*2-((i%2)==0);
		
		ll ans=0;
		for(int k=0;k<=tot;k++) ans+=C(tot,k)*C2(oth+k,n-k)%MOD*bin[k]%MOD,ans%=MOD;
		return (ans+MOD)%MOD;
	}
    void main()
    {
    	bin[0]=1;
		//fac[0]=1;facinv[0]=1;
		c[0][0]=1;
    	for(int i=1;i<4100;i++)
    	{
    		bin[i]=bin[i-1]*2%MOD;
    		//fac[i]=fac[i-1]*i%MOD;
			//facinv[i]=inv(fac[i]);
			c[i][0]=1;
			for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD;
		}
    	
		int K,n;scanf("%d%d",&K,&n);
		for(int i=2;i<=2*K;i++)
			if(i%2==0) printf("%lld\n",(solve(i,K,n)+solve(i,K,n-1))%MOD);
			else printf("%lld\n",solve(i,K,n));
    }
};

int main()
{
    mine::main();
}

Measured memory_bytes: 129920
# -*- coding: utf-8 -*-


class Node():
    def __init__(self, key, parent=None, left=None, right=None):
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right


class BinarySearchTree(list):
    def __init__(self):
        list.__init__(self)
        self.root = None

    def insert(self, z):
        z = Node(z)
        y = None
        x = self.root

        while x is not None:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y

        if y is None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def preorder(self):
        def preParse(u):
            if u == None:
                return
            print(" " + str(u.key), end="")
            preParse(u.left)
            preParse(u.right)
        preParse(self.root)
        print("")

    def inorder(self):
        def inParse(u):
            if u == None:
                return
            inParse(u.left)
            print(" " + str(u.key), end="")
            inParse(u.right)
        inParse(self.root)
        print("")

    def print(self):
        self.inorder()
        self.preorder()

    def find(self, k):
        x = self.root
        while x is not None and k != x.key:
            if k < x.key:
                x = x.left
            else:
                x = x.right
        return x

if __name__ == '__main__':

    n = int(input())
    command = [input().split(" ") for _ in range(n)]
    T = BinarySearchTree()

    for c in command:
        if c[0] == "insert":
            T.insert(int(c[1]))
        elif c[0] == "find":
            f = T.find(int(c[1]))
            if f is None:
                print("no")
            else:
                print("yes")
        else:
            T.print()


Measured memory_bytes: 226136
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;

ll a, b, x;

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin >> a >> b >> x;
	cout << max(0LL, b/x-(a+x-1)/x+1) << endl;
	return 0;
}

Measured memory_bytes: 256
# https://atcoder.jp/contests/abc145/tasks/abc145_d
from math import factorial
x, y = map(int, input().split())
mod = 10 ** 9 + 7

# two_steps = x // 2
# one_steps = x % 2
# ans = 0
# while two_steps:
#     if one_steps * 2 + two_steps * 1 == y:
#         ans += (factorial(one_steps + two_steps) * (pow(factorial(one_steps), mod - 2, mod) * pow(factorial(two_steps), mod - 2, mod))) % mod
#     two_steps -= 1
#     one_steps += 2
# print(ans)

MAX = 10 ** 6 + 1

def com_init(MAX, mod):
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv

fac, finv = com_init(MAX, mod)

def nCr(n, r):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod 

if (x + y) % 3 == 0:
    a = (-x + 2 * y) // 3
    b = (2 * x - y) // 3
    ans = nCr(a + b, a)
    # ans = (factorial(a + b) * (pow(factorial(a), mod - 2, mod) * pow(factorial(b), mod - 2, mod))) % mod
else:
    ans = 0

print(ans)

Measured memory_bytes: 121716
H,W = list(map(int, input().split()))
moji = ''
char = {}
for i in range(H):
    moji += input()
for m in moji:
    if m in char:
        char[m] += 1
    else:
        char.update({m:1})

four = 0
two = 0
one = 0
for c in char:
    four += int(char[c] / 4)
    two += int(char[c]%4/2)
    one += int(char[c]%2)

ans = [(H//2)*(W//2), (H//2)*(W%2)+(H%2)*(W//2), (H%2)*(W%2)]
four -= ans[0]
while(four > 0):
    four -= 1
    ans[1] -= 2
if two == ans[1] and one == ans[2]:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
n, k = map(int, input().split())
p = list(map(int,input().split()))
b = [(1 + p[i])/2 for i in range(n)]
 
ttl = sum(b[:k])
res = ttl
for i, v in enumerate(b[k:]):
    ttl += v - b[i]
    res = max(res, ttl)
 
print("{:.10f}".format(res))

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

lint gcd(lint x, lint y) {
  if(x == 0) { return y; }
  else { return gcd(y%x,x); }
}

lint lcm(lint x, lint y) { return x/gcd(x,y)*y; }

lint C(lint n, lint k) {
  if(n == k) { return 1; }
  else if(n < k) { return 0; }
  else if(k == 0) { return 1; }
  else if(k == 1) { return n; }
  else return C(n-1,k-1) + C(n-1,k);
}

lint P(lint n, lint k) {
  if(k == 1) { return n; }
  return (n*(P(n-1,k-1)%1000000007)%1000000007);
}


int main() {
  int x; cin >> x;
  cout << 10 - x/200 << endl;

  return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#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 equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const int INF = 1000000005;
const long double EPS = 1e-10;

int main() {
  int n, k;
  string s;
  cin >> n >> k >> s;

  int cnt = 0, cntc = 0;
  if (s[0] == 'L') cntc++;
  if (s[n - 1] == 'R') cntc++;
  rep(i, n - 1) {
    if (s[i] == 'R' && s[i + 1] == 'L') cnt++;
  }

  int t = min(cnt, k);
  k -= t;
  cnt -= t;
  if (cnt == 0 && cntc == 0) cntc++;
  if (k > 0 && cntc == 2) cntc--;

  cout << n - 2 * cnt - cntc << endl;


  

  
  return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repp(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define INF (1ll<<60)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
const lint MOD =1000000007;
const lint MAX = 10000000;
using Graph =vector<vector<lint>>;
typedef pair<lint,lint> P;

 
lint fac[MAX], finv[MAX], inv[MAX];

void COMinit() // 二項係数を求める時は前処理としてCOMinit()をする
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (lint i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
// 二項係数計算
long long COM(lint n, lint k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

lint primary(lint num)
{
    if (num < 2) return 0;
    else if (num == 2) return 1;
    else if (num % 2 == 0) return 0; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return 0;
        }
    }

    // 素数である
    return 1;
}
    //累積和をとり、同じ数の個数を求めそのコンビネーションの和で解く
  int main(){
      lint N;
      lint sum=0;
      lint ans=0;
      map<lint,lint> m;
      cin >>N; lint A[N];
      m[0]=1;
      rep(i,N){
        cin>>A[i];
        sum+=A[i];
        m[sum]++;
      }
      for(auto x:m){
          lint y=x.second;
          ans+=(y*(y-1)/2);
      }
      cout<<ans;
    }
     
  


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

using ll = long long;
static const ll MOD = 1e9 + 7;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n, m;
  cin >> n >> m;
  
  vector<ll> x(n), y(m);
  for(int i = 0; i < n; i++) cin >> x.at(i);
  for(int i = 0; i < m; i++) cin >> y.at(i);
  
  ll ansx = 0, ansy = 0, keep;
  for(int i = n - 1; i >= 0; i--){
    keep = x.at(i) * (i - (n - i - 1));
    if(keep >= 0){
      keep %= MOD;
    }
    else{
      keep += MOD * 1e5;
      keep %= MOD;
    }
    ansx += keep;
    ansx %= MOD;
  }
  
  for(int i = m - 1; i >= 0; i--){
    keep = y.at(i) * (i - (m - i - 1));
    if(keep >= 0){
      keep %= MOD;
    }
    else{
      keep += MOD * 1e5;
      keep %= MOD;
    }
    ansy += keep;
    ansy %= MOD;
  }
  
  cout << (ansx * ansy) % MOD << '\n';
}

Measured memory_bytes: 1792