akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-

def readInts():
  return [int(s) for s in input().split(" ")]

def main():
  N = readInts()[0]

  ans = 0

  nAts = 0
  nBlsAts = 0
  nBls = 0

  for i in range(N):
    s = input()

    if s[0] == "B" and s[-1] == "A":
      nBlsAts += 1
    elif s[0] == "B":
      nBls += 1
    elif s[-1] == "A":
      nAts += 1

    for k in range(len(s) - 1):
      if s[k:k+2] == "AB":
        ans += 1

  if nBlsAts > 0:
    ans += nBlsAts - 1

  if nBlsAts > 0:
    if nAts > 0:
      nAts -= 1
      ans += 1
    if nBls > 0:
      nBls -= 1
      ans += 1

  ans += min(nAts, nBls)

  print(ans)

if __name__ == "__main__":
  main()


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

const int MOD = (int)1e9+7;

int main(){
	vector<int> a(5);
	for(int i=0;i<5;i++)	cin >> a.at(i);

	int x=10;
	for(int i=0;i<5;i++){
		if(a.at(i)%10!=0)	x=min(x,a.at(i)%10);
	}
	int ans=0;
	for(int i=0;i<5;i++){
		ans+=a.at(i);
		if(ans%10!=0)	ans+=10-ans%10;
	}
	cout << ans-10+x << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

int main(void)
{
    int N;
    cin >> N;
    int d = 0;

    int n = N;
    while(n > 0){
        d += n % 10;
        n /=10;
    }
    cout << ((N % d == 0)?"Yes":"No") << endl;


    return 0;
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <cmath>
#include <stdlib.h>

using namespace std;

#define int long long
#define endl "\n"
#define all(v)  v.begin(),v.end()
#define fir first
#define sec second
#define m_p make_pair
#define rep(i,n)  for(int i=0; i<(int) (n); i++)


const double pai = 3.1415926535897;
const int mod = 1000000007;
const int INF = 2000000015;
const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];


int jousu(int x00, int y00) {
	int z00 = 1;
	for (int i = 0; i < y00; i++) {
		z00 *= x00;
	}
	return z00;
}
int keta(int x00) {
	int z00 = x00;
	int w00 = 0;
	while (z00 != 0) {
		z00 /= 10;
		w00++;
	}
	return w00;
}
int krag(double xx) {
	return INF - (int)(INF - xx);
}
//x未満の要素数を返す二分探索関数
int b_s(vector<int>& vec, int xx) {
	int t = -1;
	int f = vec.size();
	while (f - t > 1) {
		int m = (t + f) / 2;
		if (vec[m] < xx) {
			t = m;
		}
		else {
			f = m;
		}
	}
	return f;
}
template<typename T>
void vecout(vector<T>& vec) { for (T t : vec) cout << t << " "; cout << endl; }
template<typename TT>
void vecin(vector<TT>& vec) { 
	for (int i = 0; i < vec.size(); i++) {
		cin >> vec[i];
	}
}


// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}
//n個を1個以上のx組のグループに分ける重複組み合わせはcom(n-1,x-1)
//グループが0個でもいいときはnにxを足す
// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
int modpow(int a, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

int gcd(int xx, int yy) {
	int p = xx;
	int q = yy;
	if (q > p)swap(p, q);
	while (p % q != 0) {
		p %= q;
		swap(p, q);
	}
	return q;
}
int lcm(int xx, int yy) {
	return xx * yy / gcd(xx, yy);
}
bool prime(int xx) {
	if (xx == 1) {
		return 0;
	}
	for (int i = 2; i * i <= xx; i++) {
		if (xx % i == 0) {
			return 0;
		}
	}
	return 1;
}
int n, a,b;

signed main() {
	cin >> n;
	vector<int>vec(n),vec2(n);
	rep(i, n) {
		cin >> vec[i];
		a ^= vec[i];
	}
	rep(i, n) {
		cout << (a ^ vec[i]) << " ";
	}
	cout << endl;
}


Measured memory_bytes: 6364
#include <stdio.h>


int count_combination(int n, int s, int l) {
    int i, cmb;
    if (s < l) return 0;
    if (n <= 0) return 0;
    if (n == 1) {
        if (s <= 9) {
            return 1;
        }
        return 0;
    }

    for (i = l, cmb = 0; i <= s; i++) {
        cmb += count_combination(n - 1, s - i, i + 1);
    }
    return cmb;
}

int main(void) {
    int n, s;
    while (scanf("%d%d", &n, &s) != EOF && (n || s)) {
        printf("%d\n", count_combination(n, s, 0));
    }
    return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
#define ll long long
#define rep(i,l,r) for(int (i)=(l);(i)<(r);i++)
#define erep(i,l,r) for(int (i)=(l);(i)<=(r);i++)
using namespace std;
int main(){
    ll n,k,s;
    cin>>n>>k>>s;
    vector<ll> a(n,1e9);
    if(s==1e9)rep(i,0,n)a[i]=1;
    rep(i,0,k)a[i]=s;
    rep(i,0,n)cout<<a[i]<<" ";
    puts("");
}

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

public class Main {
    private static final int MOD = 1_000_000_007;
    private static final String YES = "Yes";
    private static final String NO = "No";

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] H = new int[N];
        int[] A = new int[M];
        int[] B = new int[M];
        for (int i=0; i<N; i++) {
            H[i] = sc.nextInt();
        }
        for (int i=0; i<M; i++) {
            A[i] = sc.nextInt();
            B[i] = sc.nextInt();
        }

        System.out.println(solve(N, M, H, A, B));
    }

    private static int solve(int N, int M, int[] H, int[] A, int[] B) {
        boolean[] hit = new boolean[N];
        Arrays.fill(hit, true);

        for (int j=0; j<M; j++) {
            int a = H[A[j]-1];
            int b = H[B[j]-1];

            if (a < b) {
                hit[A[j]-1] = false;
            } else if (a > b) {
                hit[B[j]-1] = false;
            } else {
                hit[A[j]-1] = false;
                hit[B[j]-1] = false;
            }
        }

        int count = 0;
        for (int i=0; i<N; i++) {
            if (hit[i]) {
                // System.err.println("hit " + i);
                count++;
            }
        }

        return count;
    }
}

Measured memory_bytes: 60728
// abc100_a
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

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

#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 INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << 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;

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

    int A, B;
    cin >> A >> B;

    if (A <= 8 && B <= 8){
        print("Yay!");
    } else {
        print(":(");
    }

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		switch (n) {
		case 1:
			System.out.println("Hello World");
			break;
		case 2:
			int a = sc.nextInt();
			int b = sc.nextInt();
			System.out.println(a+b);
			break;
		}

	}

}


Measured memory_bytes: 25044
#include<iostream>
using namespace std;
int main()
{
   string s;
   cin>>s;
   for(int i = 0 ;s[i]!='\0';i++){
      if((i+1)%2)
      {
         if(s[i]=='R')
         continue;
         else if(s[i]=='L'){
         cout<<"No"<<endl;
         return 0;}
      }
      else{
         if(s[i]=='L')
         continue;
         else if(s[i]=='R'){
         cout<<"No"<<endl;
         return 0;}
      }
   }
   cout<<"Yes"<<"\n";
   return 0;
}


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

int main() {
  int N;
  cin >> N;
  int A = 1;
  int ans = 0;
  while (A <= N) {
    if ((A%10 > 0 && A/10 == 0) || (A%1000 > 99 && A/1000 == 0) || (A%100000 > 9999 && A/1000000 == 0))
      ans++;
    A++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const unsigned int m = 1000000007; 

int main() {
// #ifndef ONLINE_JUDGE
// 	freopen("input.txt", "r", stdin);
// 	freopen("output.txt", "w", stdout);
// #endif

	int n, k;
	cin >> n >> k;
	int arr[n];
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	sort(arr, arr+n);

	int sum = 0;
	for (int i = 0; i < k; i++)
		sum += arr[i];
	cout << sum;
}




Measured memory_bytes: 3600
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace ABC
{
    class ABC168C
    {
        const string FILE = "/tmp/data.txt";

        static void Main(string[] args)
        {
#if DEBUG
            Console.SetIn(new StreamReader(FILE));
#endif
            string line;
            string[] sa;
            line = Console.ReadLine();
            sa = line.Split(' ');
            int a = int.Parse(sa[0]);
            int b = int.Parse(sa[1]);
            int h = int.Parse(sa[2]);
            int m = int.Parse(sa[3]);


            double radM = m * 2 * Math.PI / 60;
            double radH = h * 2 * Math.PI / 12 + m * 2 * Math.PI / 720;

            double result = Math.Sqrt(a * a + b * b - 2 * a * b * Math.Cos(Math.Abs(radM - radH)));
            Console.WriteLine(result);
#if DEBUG
            Console.WriteLine();
#endif
        }
    }
}


Measured memory_bytes: 27916
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int main(){
    int n, h[100100];
    int dp[100100];
    cin >> n;
    
    for(int i = 0; i < n; i++){
        cin >> h[i];
    }
    dp[0] = 0;
    dp[1] = abs(h[0] - h[1]);
    
    for(int i = 2; i < n; i++){
        dp[i] = min(dp[i-1] + abs(h[i-1] - h[i]), dp[i-2] + abs(h[i-2] - h[i]));
    }
    
    cout << dp[n-1] << endl;
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int numx[8005],numy[8005];
char s[8005];
int dpx[2][16005],dpy[2][16005];
int main()
{
	int x,y;
	scanf("%s",s);
	scanf("%d%d",&x,&y);
	int len=strlen(s);
	int cntx=0,cnty=0;
	int nowd=0,now=0;
	for(int i=0;i<len;i++)
	{
		if(s[i]=='F')now++;
		else
		{
			if(!nowd)numx[cntx++]=now;
			else numy[cnty++]=now;
			//printf("%d\n",now);
			nowd=1-nowd;
			now=0;
		}
	}
	if(now)
	{
		if(!nowd)numx[cntx++]=now;
		else numy[cnty++]=now;
		//printf("%d\n",now);
	}
	//printf("cntx:%d cnty:%d\n",cntx,cnty);
	dpx[0][8000+numx[0]]=1;
	dpy[1][8000]=1;
	for(int i=1;i<cntx;i++)
	{
		memset(dpx[i%2],0,sizeof(dpx[i%2]));
		for(int j=0;j<=16000;j++)
		{
			if(dpx[(i+1)%2][j])
			{
				if(j-numx[i]>=0)dpx[i%2][j-numx[i]]=1;
				if(j+numx[i]<=16000)dpx[i%2][j+numx[i]]=1;
			}
		}
	}
	for(int i=0;i<cnty;i++)
	{
		memset(dpy[i%2],0,sizeof(dpy[i%2]));
		for(int j=0;j<=16000;j++)
		{
			if(dpy[(i+1)%2][j])
			{
				if(j-numy[i]>=0)dpy[i%2][j-numy[i]]=1;
				if(j+numy[i]<=16000)dpy[i%2][j+numy[i]]=1;
			}
		}
	}
	if(dpx[(cntx+1)%2][8000+x]&&dpy[(cnty+1)%2][8000+y])printf("Yes\n");
	else printf("No\n");
	return 0;
}

Measured memory_bytes: 512
import sys
import numpy as np


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


def main():
    n, k = map(int, input().split())
    h = np.array(input().split(), dtype=np.int64)
    dp = np.zeros(n, dtype=np.int64)

    for i in range(1, n):
        j = max(0, i - k)
        dp[i] = np.min(np.abs(h[i] - h[j:i]) + dp[j:i])
    print(dp[n - 1])


if __name__ == "__main__":
    main()


Measured memory_bytes: 21972
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Main {


    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int y = in.nextInt();
        int x = in.nextInt();
        
        String n;
        
        int map[][] = new int[y][x];
        
        int count=0;
        for(int i=0;i<y;i++){
        	n=in.next();
        	for(int j=0;j<x;j++){
        		map[i][j]=(n.charAt(j)=='#'?1:0);
        		count+=map[i][j];
        	}
        	
        }
        
        for(int i=1;i<y;i++)
        	for(int j=0;j<x;j++){
        		if(map[i][j]==1&&map[i-1][j]==1){
        			map[i][j]+=10;
        			map[i-1][j]+=10;
        			count -=2;
        		}else if(map[i][j]==1&&map[i-1][j]==11){
        			map[i][j]+=10;
        			count--;
        		}else if(map[i][j]==11&&map[i-1][j]==1){
        			map[i-1][j]+=10;
        			count--;
        		}
        		if(count==0) break;
        	}
        
        for(int i=0;i<y;i++)
        	for(int j=1;j<x;j++){
        		if(map[i][j]==1&&map[i][j-1]==1){
        			map[i][j]+=10;
        			map[i][j-1]+=10;
        			count -=2;
        		}else if(map[i][j]==1&&map[i][j-1]==11){
        			map[i][j]+=10;
        			count--;
        		}else if(map[i][j]==11&&map[i][j-1]==1){
        			map[i][j-1]+=10;
        			count--;
        		}
        		if(count==0) break;
        	}
        
        if(count==0)
        	System.out.println("Yes");
        else
        	System.out.println("No");
     
    }

}


Measured memory_bytes: 21844
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;

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

int main(){
    string S;
    cin >> S;
    int i;
    int c;
    int flag_0, flag_1, flag_2;

    c = (S.size() - 1) / 2;

    flag_0 = 0;
    for(i=0;i<c;i++){
        if(S[i] != S[c-1-i]){flag_0 = 1;}
    }

    flag_1 = 0;
    for(i=c+1;i<S.size();i++){
        if(S[i] != S[S.size()-1-i]){flag_1 = 1;}
    }

    flag_2 = 0;
    for(i=0;i<c;i++){
        if(S[i] != S[i+c+1]){flag_2 = 1;}
    }

    if(flag_0 == 0 and flag_1 == 0 and flag_2 == 0){cout << "Yes" << endl; return 0;}
    else{cout << "No" << endl; return 0;}


    return 0;
}


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

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end() 
#define MOD 998244353

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

ll INF=LLONG_MAX;
int const mxn = 2e5+5;
vi adj[mxn];

void multi(ll &a, ll b){
	a%=MOD; b%=MOD; a*=b; a%=MOD;
}

ll dfs(int u){
	ll res = 1LL;
	for(auto v:adj[u])
		multi(res, dfs(v));
	return res+1;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int n; cin >> n;
	ii a[n];
	for(int i=0; i<n; i++)
		cin >> a[i].fi >> a[i].se;
	sort(a,a+n);
	stack<ii>s;
	for(int i=n-1; i>=0; i--){
		int dist = a[i].fi + a[i].se;
		while(!s.empty()&&s.top().fi<dist){
			adj[i].eb(s.top().se);
			s.pop();
		}
		s.emplace(a[i].fi,i);
	}
	ll ans = 1LL;
	while(!s.empty()){
		int u = s.top().se;
		multi(ans, dfs(u));
		s.pop();
	}
	cout << ans << endl;
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN


Measured memory_bytes: 22144
#include <bits/stdc++.h>
using namespace std;
int main() {
  int h,n;
  cin >> h >> n;
  long int ans = 0;
  vector<int> move(n);
  for (int i=0; i<n; i++) {
    cin >> move.at(i);
    ans += move.at(i);
  }
  if (h <= ans) {
    cout << "Yes" << endl;
  } else {
  cout << "No" << endl;
  }
}

Measured memory_bytes: 640
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: usize = read();
    let a: i64 = read();
    let b: i64 = read();
    let mut v: Vec<i64> = vec![];

    for _ in 0..n {
        let hi = read();
        v.push(hi)
    }

    let l = -1;
    let r = 1_000_000_005;
    let mut ri = r;
    let mut li = l;
    let mut cnt = 0;
    while li + 1 < ri {
        let c = (ri + li) / 2;
        cnt = 0;
        for i in 0..v.len() {
            let vi = v[i];
            if vi > b * c {
                cnt += (vi - b * c) / (a - b) + if (vi - b * c) % (a - b) != 0 { 1 } else { 0 };
            }
        }
        if cnt <= c {
            ri = c;
        } else {
            li = c;
        }
    }
    println!("{}", ri);
}


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

const int D = 365, T = 26;

vector<int> c(T);
vector<vector<int>> s(D, vector<int>(T));

struct Contest {
    vector<int> t;
    vector<vector<int>> h;
    Contest() : t(D), h(T) {
        for(int t = 0; t < T; ++t) {
            h[t].push_back(-1);
            h[t].push_back(D);
        }
    }
    int calc() {
        int res = 0;
        for(int t = 0; t < T; ++t) {
            for(auto &d : h[t]) {
                if(d == -1 || d == D) continue;
                res += s[d][t];
            }
            for(int d = 0; d < h[t].size() - 1; ++d) {
                int between = h[t][d + 1] - h[t][d] - 1;
                res -= c[t] * between * (between + 1) / 2;
            }
        }
        return res;
    }
    void output() {
        for(int i = 0; i < D; ++i) cout << t[i] + 1 << '\n';
    }
};

Contest best;

void input() {
    int _; cin >> _;
    for(int i = 0; i < T; ++i) cin >> c[i];
    for(int i = 0; i < D; ++i) {
        for(int j = 0; j < T; ++j) cin >> s[i][j];
    }
}

void init() {
    for(int i = 0; i < D; ++i) {
        best.t[i] = max_element(s[i].begin(), s[i].end()) - s[i].begin();
        auto it = lower_bound(best.h[best.t[i]].begin(), best.h[best.t[i]].end(), i);
        best.h[best.t[i]].insert(it, i);
    }
}

int main() {
    input();
    init();
    best.output();
    cerr << best.calc() << '\n';
    return 0;
}


Measured memory_bytes: 3672
#include <iostream>
using namespace std;
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	string S;
	cin >> S ;
	if (S[0] != S[1] && S[1] != S[2] && S[2] != S[0])cout << "Yes\n";
	else cout << "No\n";


	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int h,w;
    cin >> h>>w;
    char a[h][w];
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
        cin>>a[i][j];
      }
    }
  for(int i=0;i<w+2;i++){
    cout<<'#';
  }
  cout<<endl;
   for(int i=0;i<h;i++){
     cout<<'#';
      for(int j=0;j<w;j++){
        cout<<a[i][j];
      }
     cout<<'#'<<endl;
   }
  for(int i=0;i<w+2;i++){
    cout<<'#';
  }
  return 0;
}


Measured memory_bytes: 256
use std::io;
use std::cmp;

// read a line(without line feed)
fn read_line() -> String {
    let mut in_str = String::new();
    io::stdin().read_line(&mut in_str).unwrap();
    return in_str.trim().to_string();
}

// read wods on a line
pub fn read_words_in_line() -> Vec<String> {
    let s = read_line();
    return s.split_whitespace().map(|x| x.to_string()).collect::<Vec<String>>()
}

// read type t on a line
pub fn read_t_in_line<T : std::str::FromStr>() -> Vec<T> {
    let mut v : Vec<T> = Vec::new();
    for e in read_words_in_line().iter().map(|x| x.parse::<T>()) {
        if let Ok(r) = e {
            v.push(r);
        }
        else{
            return Vec::new();
        }
    }
    return v;
}

// sort slice
pub fn sort<T : std::cmp::Ord>(slice : &mut [T]) {
    slice.sort();
}
// sort slice by reverse order
pub fn sort_rev<T : std::cmp::Ord>(slice : &mut [T]) {
    slice.sort_by(|x, y| y.cmp(x));
}

pub fn min<T : std::cmp::Ord>(a : T, b : T) -> T{
    return cmp::min(a, b);
}

pub fn max<T : std::cmp::Ord>(a : T, b : T) -> T{
    return cmp::max(a, b);
}


fn main() {
    let n = read_line().parse::<i32>().unwrap();
    let mut l : Vec<i64>  = vec![2, 1];
    for _ in 2..n+1 {
        let a = l[1] + l[0];
        l[0] = l[1];
        l[1] = a;
    }
    println!("{}", l[1]);
}


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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  string s, t;
  cin >> s >> t;
  if (s.size() < t.size()) {
    cout << "UNRESTORABLE\n";
    return 0;
  }

  vector<int> candidate_offsets;
  for (int i = 0; i <= s.length() - t.length(); ++i) {
    int j = 0;
    for (; j < t.length(); ++j) {
      if (s[i + j] == '?') continue;
      if (s[i + j] != t[j]) break;
    }
    if (j == t.length()) {
      candidate_offsets.push_back(i);
    }
  }
  if (candidate_offsets.size() == 0) {
    cout << "UNRESTORABLE\n";
    return 0;
  }

  set<string> candidates;
  for (auto& c : candidate_offsets) {
    string d(s);
    memcpy(&d[c], t.data(), t.length());
    for (int i = 0; i < d.length(); ++i) {
      if (d[i] == '?') d[i] = 'a';
    }
    candidates.insert(d);
  }
  cout << *candidates.begin() << "\n";
}


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

int main(){
    vector<int> vec{1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int K;
    cin >> K;
    cout << vec.at(K-1) << endl;
}

Measured memory_bytes: 256
# ほぼ解説AC
# n,m<2000
# len(s),len(t)<100000
import sys

input = sys.stdin.buffer.readline

n, m = map(int, input().split())
mod = 10 ** 9 + 7
S = list(map(int, input().split()))
T = list(map(int, input().split()))


dp = [[0] * (m + 2) for _ in range(n + 2)]
sum_dp = [[0] * (m + 2) for _ in range(n + 2)]
# 空集合も要素とみなすのでdp[0][0]は1
dp[0][0] = 0
# i,jを見る時にi,jまでの累積和がほすぃ。
# i,jを見てi+1,j+1を決める。
for i in range(n + 1):
    for j in range(m + 1):
        # 二次元累積和の計算
        sum_dp[i][j] += dp[i][j]
        if i - 1 >= 0:
            sum_dp[i][j] += sum_dp[i - 1][j]
        if j - 1 >= 0:
            sum_dp[i][j] += sum_dp[i][j - 1]
        if i - 1 >= 0 and j - 1 >= 0:
            sum_dp[i][j] -= sum_dp[i - 1][j - 1]
        sum_dp[i][j] %= mod
        if i < n and j < m:
            # 先にsum_dp[i][j]は計算されていないとだめ。↑
            # i-1字目、j-1字目まででできるものに、新たに一致したものを加えたもの(sum_dp)と空集合(+1)
            if S[i] == T[j]:
                dp[i + 1][j + 1] = sum_dp[i][j] + 1
                dp[i + 1][j + 1] %= mod
print((sum_dp[n][m] + 1) % mod)



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

int main (){
string a, b, c;
cin >> a >> b >> c;
char dif='A' - 'a';
printf("%c%c%c\n", a[0] + dif, b[0] + dif, c[0] + dif);
return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
int main()
{
  int N,M;
  int *a,*b;
  int *con;
  
  scanf("%d %d",&N,&M);
  a=(int*)malloc(sizeof(int)*M);
  b=(int*)malloc(sizeof(int)*M);
  con=(int*)malloc(sizeof(int)*(N+1));
  for(int i=0;i<M;i++){
    scanf("%d %d",&a[i],&b[i]); 
    con[a[i]]++;
    con[b[i]]++;
  }
  
  for(int i=1;i<=N;i++)
    printf("%d\n",con[i]);
  
  return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main
{

    public static void main(String args[])
    {
	Scanner sc = new Scanner(System.in);

	int x = sc.nextInt();
	int y = sc.nextInt();
	int z = sc.nextInt();

	x -= z;
	int ans = x / (y + z);

	System.out.println(ans);
    }
    
}


Measured memory_bytes: 21844
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;
constexpr int MOD = 1'000'000'007;
//inline void modAdd(LL &l, LL &r) {l = (l + r) % MOD;}

template<class T> inline T sqr(T x) {return x*x;}

void solve() {
    int m,k;
    cin >> m >> k;
    if (k >= (1<<m) || (m == 1 && k == 1)) {
        cout << -1 << endl;
        return;
    }
    if (k == 0) {
        REP(i,0,1<<m) REP(j,0,2) {
            if (i != 0 || j != 0) cout << " ";
            cout << i;
        }
        cout << endl;
        return;
    }
    cout << k;
    REP(i,0,1<<m) if (i != k) cout << " " << i;
    cout << " " << k;
    RREP(i,0,1<<m) if (i != k) cout << " " << i;
    cout << endl;
}

int main() {
    solve();
    
    return 0;
}

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

int main(){
    int N;
    vector<int> a(100);
    int answer = 0;
    cin >> N;
    rep(i, N) cin >> a[i];
    rep(i, N)if((i%2 == 0) && (a[i] %2 == 1)) answer++;
    cout << answer << endl;

}


Measured memory_bytes: 3628
program main
    implicit none
    integer n
    integer n1, n10, n100,flag
    read(*,*) n
    
    n100 = (n - mod(n,100))/100
    n1 = mod((n - n100*100),10)
    n10 = (n - n100*100 - n1)/10

    flag = 0
    if(n100 == 7) then
        flag = 1
    end if

    if(n10 == 7) then
        flag = 1
    end if

    if(n1 == 7) then
        flag = 1
    end if

    if(flag == 1) then
        write(*,*) "Yes"
    else
        write(*,*) "No"
    end if

end program

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

ll gcd(ll x, ll y) {return y?gcd(y,x%y):x;};

int main() {
    int n;
    cin >> n;
    vector<int> x(n+1);
    rep(i,n+1) cin >> x[i];
    sort(x.begin(),x.end());
    int ans = 0;
    rep(i,n) ans = gcd(x[i+1]-x[i],ans);
    cout << ans << endl;
}

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

int main()
{
    string str;
    cin >> str;
    if (str.at(0) == '7' || str.at(1) == '7' || str.at(2) == '7')
    {
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 3624
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
b.reverse()
c=[0]*(n+1)
for i in a:
  c[i]+=1
for i in b:
  c[i]+=1
if n<max(c):
  print('No')
  exit(0)
l=0
while l<n and a[l]!=b[l]:
  l+=1
i=0
while l<n and a[l]==b[l]:
  while a[i]==b[l] or a[l]==b[i]:
    i+=1
  b[i],b[l]=b[l],b[i]
  l+=1
print('Yes')
print(' '.join([str(i) for i in b]))

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



 string S;
 int ans=0;


 int main () {
      cin >> S ;
      int a[4];
      int high,low;

      string judge = "NA";
      bool judge_a[4][2];
      for(int i=0;i<4;i++)a[i] = S[i] - '0';

      high=stoi(S.substr(0,2));
      low=stoi(S.substr(2,2));


      if(high >0 && high<13 && low >0 && low <13) judge = "AMBIGUOUS";
      else if(high > 0 && high<13) judge = "MMYY";
      else if(low > 0 && low<13) judge = "YYMM" ;

      
      cout << judge <<endl;
 
 }


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define o(a) cout << a << endl
#define int long long
#define first first
#define second se
using namespace std;
typedef pair<int, int> P;
typedef vector<int> vi;

signed main(){
    string s, t = "";
    cin >> s;
    rep(i, 0, s.size()){
        if(s[i] != 'B') t += s[i];
        else t = t.substr(0, t.size() - 1);
    }
    o(t);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define vi vector <int>
#define si set <int>
#define mii map <int,int>
#define pii pair <int,int>
#define endl "\n"
#define ZERO 0ll
#define FOR(P,Q) for(int P=0;P<(Q);P++)
#define FORR(P,Q) for(int P=1;P<=(Q);P++)
#define rep(P,R,Q) for(int P=(R);P<=(Q);P++)
#define repb(P,R,Q) for(int P=(R);P>=(Q);P--)
#define pb push_back
#define eb emplace_back
#define bug(j) cerr<<j<<" "
#define NL cerr<<endl
#define D1(arr,a) rep(i,1,a) bug(arr[i]) 
typedef long long ll;
typedef long double ld;
using namespace std;


    
int32_t main()
{
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	#ifndef ONLINE_JUDGE
	freopen("error.txt","w",stderr);
	#endif
	//change ll to int before using string builtin operations
	int tces=1;
	//cin>>tces;
	while(tces--){
		int x;
		cin>>x;
		FORR(i,1000){
			rep(j,-1000,i){
				if(i*i*i*i*i-j*j*j*j*j==x)
				{
					cout<<i<<" "<<j;
					exit(0);
				}
			}
		}

	}
	
return 0;
}

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

using pii = pair<int,int>;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
#define debug(x) cerr << #x << " : " << x << endl

template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << "\t" << t; return os << endl; }
// pair
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << "<" << v.first << ", " << v.second << ">"; }

const int INF = 1 << 30;
const ll INFL = 1LL << 60;


class Solver {
  public:
    bool solve() {
        ll r, D, X; cin >> r >> D >> X;
        rep(i, 10) {
            X = r * X - D;
            cout << X << endl;
        }
        return 0;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Solver s;
    s.solve();
    return 0;
}


Measured memory_bytes: 256
//Simple Knapsack
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

long long v[4][101];
int sw[4];
long long stdw,tw,ans;
long long sum0,sum1,sum2,sum3;

bool cmp(int a,int b){
	return a > b;
}

int main()
{
	long long n,w;
	scanf("%lld%lld",&n,&w);
	scanf("%lld%lld",&stdw,&v[0][++sw[0]]);
	for(int i = 2;i <= n;i++)
	{
		scanf("%lld",&tw);
		scanf("%lld",&v[tw - stdw][++sw[tw - stdw]]);
	}
	for(int i = 0;i <= 3;i++)
		sort(v[i] + 1,v[i] + sw[i] + 1,cmp);
	for(int i = 0;i <= sw[0];i++)
	{
		sum0 += v[0][i];
		for(int j = 0;j <= sw[1];j++)
		{
			sum1 += v[1][j];
			for(int k = 0;k <= sw[2];k++)
			{
				sum2 += v[2][k];
				for(int t = 0;t <= sw[3];t++)
				{
					sum3 += v[3][t];
					if(w - i * stdw - j * (stdw + 1) - k * (stdw + 2) - t * (stdw + 3) < 0)continue;
					ans = max(ans,sum3 + sum2 + sum1 + sum0);
				}
				sum3 = 0;
			}
			sum2 = 0;
		}
		sum1 = 0;
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 128
#!/usr/bin/env python3
# from itertools import combinations_with_replacement
N, K = map(int, input().split())

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
tmp_N = N + 2  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, tmp_N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

for i in range(1, K + 1):
    ans = cmb(N - K + 1, i, p) * cmb(K - 1, K - i, p) % p
    print(ans)

Measured memory_bytes: 3572
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Diagnostics;
using System.Text;
using System.Threading.Tasks;
using System.Runtime.CompilerServices;
using static System.Math;


class P
{
    static void Main()
    {
        Console.WriteLine(Console.ReadLine().Replace('1', 'x').Replace('9', '1').Replace('x', '9'));
    }
}


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

using namespace std;

#define MOD 1000000007

int main(){
  long long a, b, x;
  cin >> a >> b >> x;
  long long ret = x % MOD;
  if(x < a){
    cout << x % MOD << endl;
    return 0;
  }
  long long d = b - a;
  long long n = (x - a) / -d + 1;
  long long l = x + (n-1)*d;
  //cout << d << " " << n << " " << l << endl;
  ret = (ret +  ((n % MOD) *(b % MOD) % MOD)) % MOD;
  cout << ret << endl;
  return 0;
}



Measured memory_bytes: 3104
from collections import deque
k = int(input())

def dfs(k):
  cnt = 0
  stack = deque()
  for i in range(1, 10):
    stack.append(i)
  while cnt <= k:
    q = stack.popleft()
    ans.append(q)
    cnt += 1
    l = q % 10
    for x in range(max(0, l - 1), min(10, l + 2)):
      stack.append(q * 10 + x)
          
ans = []
dfs(k)
print(ans[k-1])

Measured memory_bytes: 16628
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int b[26] ={0};

int main(void)
{
    char s[101];
    scanf("%s", s);
    int l = strlen(s);
    for (int i = 0; i < l; ++i){
       b[s[i] -'a'] ++;
    }

    for (int j = 0; j < 26; ++j){
        if (b[j]){
            int k = 0;
            int max = 0;
            for (int i = 0; i < l; ++i){
                if (s[i] == j + 'a'){
                    if (k > max){
                        max = k;
                        k = 0;
                    }
                     k = 0;
                }
                else
                    k++;
            }
            if (k > max)
                b[j] = k;
            else
                b[j] = max;
        }
        else
            b[j] = 200;
    }
       
    int min = 200;
    for (int j = 0; j < 26; ++j){
        if (b[j] < min){
            min = b[j];
        }
    }
    printf("%d\n", min);
    return 0;
}

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

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

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

int main(void){

    int n;
    cin >> n;
    cout << (n < 1200 ? "ABC" : "ARC") << endl;

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main() {
	int a;
	char b;
	scanf("%d", &a);
	int i;
	char c[100000];
	int x = 1;
	scanf("%s", c);
	for (i = 0;i < a;i++) {


		if(i!=0){
			if (c[i] != c[i - 1]){
				x++;
			
			}
		}
	}
	printf("%d",x);
	
	
}

Measured memory_bytes: 256
from itertools import accumulate

N = int(input())
A = list(map(int, input().split()))

# Aの累積和 (残っている葉の数) の逆
cA = list(accumulate(A[::-1]))[::-1]

if N == 0:
    if A[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
if A[0]:
    print(-1)
    exit()

# 根から頂点数を確定，根は1
B = [1]
P = 1

for i in range(N):
    # 今の頂点数の2倍を超えられない (葉は)
    if B[i] * 2 < A[i + 1]:
        print(-1)
        exit()
    P += min(2 * B[i], cA[i + 1])
    # 今使う個数と，内点の個数
    B.append(min(2 * B[i], cA[i + 1]) - A[i + 1])
    if B[-1] < 0:
        print(-1)
        exit()

print(P)

Measured memory_bytes: 89808
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int main(){
  int a,b,c,y,m,d;
  cin>>a>>b>>c>>y>>m>>d;
  P h=P(b,c),t=P(m,d);
  int f=0;
  if(a>y&&h>t)f=1;
  if(a<y&&h<t)f=1;
  if(a==y&&h!=t)f=1;
  cout<<abs(a-y)+f<<endl;
  return 0;
}



Measured memory_bytes: 3092
#include<iostream>
#include<algorithm>
#include<queue>
#include<tuple>

using namespace std;

#define int long long

char c[523][523];

template<class A>
void bfs(A &ds,queue<tuple<int,int,int> > que){
  fill(*begin(ds),*end(ds),1e9);
  while(!que.empty()){
    auto cs=que.front();
    que.pop();
    int t=get<0>(cs);
    int y=get<1>(cs);
    int x=get<2>(cs);
    if(ds[y][x]<=t)continue;
    ds[y][x]=t;
    for(int i=0;i<4;i++){
      static const int d[]={0,1,0,-1,0};
      int ny=y+d[i];
      int nx=x+d[i+1];
      if(c[ny][nx]=='.'){
	que.push(make_tuple(t+1,ny,nx));
      }
    }
  }
}

signed main(){
  int W,H;
  cin>>W>>H;
  queue<tuple<int,int,int> > sque,gque;
  int sy,sx;
  int n=0;
  for(int i=0;i<H;i++){
    cin>>c[i];
    for(int j=0;j<W;j++){
      if(c[i][j]=='s'){
	c[i][j]='.';
	sy=i;
	sx=j;
      }else if(c[i][j]=='*'){
	sque.push(make_tuple(0,i,j));
      }else if(c[i][j]=='g'){
	gque.push(make_tuple(0,i,j));
      }
      n+=c[i][j]=='.';
    }
  }
  static int ds[523][523];
  bfs(ds,sque);
  static int dg[523][523];
  bfs(dg,gque);
  int gsum=0,ssum=0;
  int xsum=0;
  int gs[2555]={},ss[2555]={};
  int xs[2555]={};
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(c[i][j]=='.'){
	int cx=min<int> (2500,max<int>(0,dg[i][j]-ds[i][j]));
	gsum+=dg[i][j];
	gs[cx]+=dg[i][j];
	ss[cx]+=ds[i][j];
	xs[cx]++;
      }
    }
  }
  double ans=1e18;
  for(int i=2500;i>=0;i--){
    gsum-=gs[i];
    ssum+=ss[i];
    xsum+=xs[i];
    if(xsum==n)continue;
    ans=min(ans,(dg[sy][sx]-ds[sy][sx]>=i)?ds[sy][sx]+(gsum+ssum)*1./(n-xsum):dg[sy][sx]);
  }
  cout.precision(99);
  cout<<fixed<<ans<<endl;
}

      
  

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

#define REP(i,num) for(int i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

class Combination{
	constexpr static int atcoder_mod = 1000000007;
	vector<ll> fac,finv,inv;
public:
	Combination(ll N){
		fac.resize(N+1);
		finv.resize(N+1);
		inv.resize(N+1);
		fac[0] = fac[1] = 1;
		finv[0] = finv[1] = 1;
		inv[1] = 1;
		for(int i=2;i<=N;i++){
			fac[i] = fac[i-1] * i % atcoder_mod;
			inv[i] = atcoder_mod - inv[atcoder_mod%i] * (atcoder_mod/i) % atcoder_mod;
			finv[i] = finv[i-1] * inv[i] % atcoder_mod;
		}
	}
	ll Caluclation(ll n,ll r){
		if(n < r) return 0;
		if (n < 0 || r < 0) return 0;
		return fac[n] * (finv[r] * finv[n-r] % atcoder_mod) % atcoder_mod;
	}
	ll GetFInv(ll i){
		return finv[i];
	}
};

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

	int N=in();
	vector<int> P=vecin(N+1),C(N,0);
	ll left=0,right=0,same;
	REP(i,N+1){
		C[P[i]-1]++;
		if(C[P[i]-1]>1){
			same=P[i];
			right=N-i;
			break;
		}
	}
	REP(i,N+1){
		if(P[i]==same){
			left=i;
			break;
		}
	}
	Combination Comb(N+1);
	REP(i,N+1){
		out((Comb.Caluclation(N+1,i+1)+atcoder_mod-Comb.Caluclation(left+right,i)+atcoder_mod)%atcoder_mod);
	}

	return 0;
}

Measured memory_bytes: 4480
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    S=ST()
    before = " "
    RLE = []
    for s in S:
        if before != s:
            RLE.append(s)
        before = s
    print(len(RLE)-1)


if __name__ == '__main__':
    main()
    # S=ST()
    # ans = 0
    # for i in range(len(S)):
    #     for it in combinations([i for i in range(len(S))], i):
    #         before = 0
    #         for j in it:
    #             print(int(S[before:j+1]), before,j)
    #             ans += int(S[before:j+1])
    #             before = j+1
    #         try:
    #             ans += int(S[before:])
    #         except:
    #             pass
    #         print(ans)
    # print(ans)

Measured memory_bytes: 73580
#include <bits/stdc++.h>
#define rep(i,a) for(int i=0;i<int(a);++i)
#define rrep(i,a) for(int i=int(a)-1; i>=0;--i)
using ll = long long;
using namespace std;
int main(){
    int h,w;
    cin>>h>>w;
    vector<vector<int>> a(h,vector<int>(w));
    rep(i,h) rep(j,w) cin>>a[i][j];
    bool isOdd=false;
    vector<tuple<int,int,int,int>> ans;
    for(int i=0; i<h; i++){
        if(i%2==1){
            for(int j=w-1; j>=0; j--){
                if(isOdd){
                    if(j==w-1){
                        ans.push_back(make_tuple(i-1,j,i,j));
                    }else{
                        ans.push_back(make_tuple(i,j+1,i,j));
                    }
                }
                if(isOdd&&a[i][j]%2){
                    isOdd=false;
                }else if(a[i][j]%2){
                    isOdd=true;
                }
            }
        }else{
            for(int j=0; j<w; j++){
                if(isOdd){
                    if(j==0){
                        ans.push_back(make_tuple(i-1,j,i,j));
                    }else{
                        ans.push_back(make_tuple(i,j-1,i,j));
                    }
                }
                if(isOdd&&a[i][j]%2){
                    isOdd=false;
                }else if(a[i][j]%2){
                    isOdd=true;
                }
            }
        }
    }
    cout<<ans.size()<<endl;
    rep(i,ans.size()){
        int a,b,c,d;
        tie(a,b,c,d) = ans[i];
        cout<<a+1<<" "<<b+1<<" "<<c+1<<" "<<d+1<<endl;
    }
}

Measured memory_bytes: 5232
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
int n; char c[11][11];
int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; i++) scanf("%s", &c[i]);
	int e = rand() % n + 1, f;
	for(int i = 0; i < 1000; i++) {
		printf("%d\n", e); fflush(stdout);
		scanf("%d", &f);
		if(c[e - 1][f - 1] == 'x') e = rand() % n + 1;
	}
}

Measured memory_bytes: 3320
#include <iostream>
#include <algorithm>
#include <string>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

int main(){
    string s; cin>>s;
    reverse(s.begin(),s.end());
    string a[4]={"maerd","remaerd","esare","resare"};
    string ans="YES";

    while(!s.empty()){
        if(s[0]=='m'){
            rep(i,5){
                if(s[i]!=a[0][i]){
                    ans="NO";
                }
            }
            s.erase(0,5);
        }else if(s[0]=='e'){
            rep(i,5){
                if(s[i]!=a[2][i]){
                    ans="NO";
                }
            }
            s.erase(0,5);
        }else if(s[0]=='r'){
            if(s[2]=='m'){
                rep(i,7){
                    if(s[i]!=a[1][i]){
                        ans="NO";
                    }
                }
                s.erase(0,7);
            }else if(s[2]=='s'){
                rep(i,6){
                    if(s[i]!=a[3][i]){
                        ans="NO";
                    }
                }
                s.erase(0,6);
            }else{
                ans="NO"; break;
            }
        }else{
            ans="NO"; break;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
using UL = unsigned int;
using ULL = unsigned long long;
using LL = long long;
#define rep(i,n) for(UL i=0; i<(n); i++)

UL E[100][100]={};

int main() {
 UL N; scanf("%u",&N);
 rep(i,N){
  UL v; scanf("%u",&v); v--;
  UL c; scanf("%u",&c);
  rep(i,c){
   UL e; scanf("%u",&e); e--;
   E[v][e]=1;
  }
 }
 rep(i,N){
  rep(j,N){
   if(j) printf(" ");
   printf("%u",E[i][j]);
  } printf("\n");
 }
 return 0;
}



Measured memory_bytes: 3252
// https://atcoder.jp/contests/abc133/tasks/abc133_d

fun main() {
    abc133d()
}

fun abc133d() {
    val n = readLine()!!.toInt()
    val dum = readLine()!!.split(" ").map { it.toLong() }
    val rain = LongArray(n) { 0L }
    for (i in 1 until n) {
        rain[i] = dum[i - 1] - rain[i - 1]
    }
    val x = (dum.last() - rain.last()) / 2
    for (i in 0 until n) {
        if (i % 2 == 0) {
            rain[i] = (rain[i] + x) * 2
        } else {
            rain[i] = (rain[i] - x) * 2
        }
    }
    println(rain.joinToString(" "))
}


Measured memory_bytes: 57800
#include<iostream>
using namespace std;
int h,w;
string s[200];
bool used[200][200];
bool nxt[200][200];
bool ns[200][200];
int d[]={0,1,0,-1,0};
main()
{
	cin>>h>>w;
	for(int i=0;i<h;i++)cin>>s[i];
	for(int i=0;i<h;i++)for(int j=0;j<w;j++)used[i][j]=s[i][j]=='$';
	while(1)
	{
		bool flag=false;
		for(int i=0;i<h;i++)for(int j=0;j<w;j++)ns[i][j]=nxt[i][j]=0;
		for(int i=0;i<h;i++)for(int j=0;j<w;j++)
		{
			if(!used[i][j])continue;
			nxt[i][j]=1;
			for(int r=0;r<4;r++)
			{
				int x=i+d[r],y=j+d[r+1];
				if(x<0||x>=h||y<0||y>=w||s[x][y]=='#')continue;
				nxt[x][y]=1;
			}
		}
		for(int i=0;i<h;i++)for(int j=0;j<w;j++)used[i][j]=nxt[i][j];
		for(int i=0;i<h;i++)for(int j=0;j<w;j++)
		{
			if(s[i][j]!='@')continue;
			for(int r=0;r<4;r++)
			{
				int x=i+d[r],y=j+d[r+1];
				if(x<0||x>=h||y<0||y>=w||s[x][y]=='#'||used[x][y])continue;
				if(s[x][y]=='%')
				{
					cout<<"Yes"<<endl;
					return 0;
				}
				ns[x][y]=1;
				flag=true;
			}
			if(!used[i][j])ns[i][j]=1,flag=true;
			s[i][j]='.';
		}
		if(!flag)
		{
			cout<<"No"<<endl;
			return 0;
		}
		for(int i=0;i<h;i++)
		{
			for(int j=0;j<w;j++)if(ns[i][j])s[i][j]='@';
		}
	}
}



Measured memory_bytes: 3360