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

//#include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
// using cint = cpp_int;
//#pragma GCC optimize("", on)
//#pragma GCC optimization_level 3

// Define
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const ll MOD = 1e9 + 7;
const ll INF = LONG_MAX;
const ull MAX = ULONG_MAX;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define endl '\n'
#define space ' '
#define def inline auto
#define func inline constexpr ll
#define run __attribute__((constructor)) def _
#define all(v) begin(v), end(v)
#define input(a) scanf("%lld", &(a))
#define print(a) printf("%lld\n", (a))

// Debug
#define debug(...)                                                             \
    {                                                                          \
        cerr << __LINE__ << ": " << #__VA_ARGS__ << " = ";                     \
        for (auto &&X : {__VA_ARGS__}) cerr << "[" << X << "] ";               \
        cerr << endl;                                                          \
    }

#define dump(a, h, w)                                                          \
    {                                                                          \
        cerr << __LINE__ << ": " << #a << " = [" << endl;                      \
        rep(i, h) {                                                            \
            rep(j, w) cerr << a[i][j] << space;                                \
            cerr << endl;                                                      \
        }                                                                      \
        cerr << "]" << endl;                                                   \
    }

#define lldump(a, n) dump(vector<vector<ll>>{a}, 1, n)

// Loop
#define inc(i, a, n) for (ll i = (a), _##i = (n); i <= _##i; ++i)
#define dec(i, a, n) for (ll i = (a), _##i = (n); i >= _##i; --i)
#define each(i, a) for (auto &&i : a)
#define rep(i, n) inc(i, 0, n - 1)
#define loop() for (;;)

// Stream
#define fout(n) cout << fixed << setprecision(n)
#define fasten cin.tie(0), ios::sync_with_stdio(0)

// Speed
run() { fasten, fout(10); }
#pragma GCC optimize("O3")
#pragma GCC target("avx")

// Math
func gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
func lcm(ll a, ll b) { return a * b / gcd(a, b); }
func sign(ll a) { return a ? abs(a) / a : 0; }

def in() {
    ll A;
    cin >> A;
    return A;
}

ll N, M;
signed main() { cin >> N >> M, cout << ((N * M) & 1 ? "Odd" : "Even") << endl; }

// for compilation: g++ -Ofast -march=native -o _ _.cpp -std=c++17


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
   string s;
   long long int x=0,max=0,a,b,n;
   cin>>n>>s;
   
   for(a=0;a<=n;a++)
   {
       if(s[a]=='I')
       x=x+1;
       else
       x=x-1;
       if(x>max)
       max=x;
   }
   cout<<max;
}

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

int main(){
  long long i,j;
  long double sum,max;
  long long N,K;

  cin>>N>>K;
  
  vector<int> vec(N);
  for (i = 0; i < N; i++) {
    cin>>vec.at(i);
  }
  
  vector<double> kitai(N);
   for (i = 0; i < N; i++) {
	  kitai.at(i)=vec.at(i)*(vec.at(i)+1)/2.0/vec.at(i);
     //cout<<kitai.at(i)<<endl;
  }
  
  sum=0;
  for(i=0;i<K;i++){
    sum+=kitai.at(i);
  }
  max=sum;
  for(i=K;i<N;i++){
    sum-=kitai.at(i-K);
    sum+=kitai.at(i);
    if(sum>max){
      max=sum;
    }
  }
  cout<<fixed;
  cout<<setprecision(15)<<max<<endl;
}


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

int main() {
    int n;
    cin >> n;
    n %= 10;
    if(n == 3) {
        puts("bon");
    } else if(n == 0 || n == 1 || n == 6 || n == 8) {
        puts("pon");
    } else {
        puts("hon");
    }
    return 0;
}

Measured memory_bytes: 3620
#include<iostream>
#include<stdlib.h>
#include<vector>
//##..##
using namespace std;

int main() {

	int A, B, T, i = 1, X = 0;
	cin >> A >> B >> T;
	while ((A * i) < T+0.5) {
		X += B;
		i++;
	}
	cout << B * (i-1) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int s,n,c,i,j;
	while(cin>>n,n){
		c=0;for(i=1;i<n/2+1;i++){s=i;for(j=1;s<n;j++){s+=(i+j);if(s==n){c++;break;}}}
		cout<<c<<endl;
	}
}

Measured memory_bytes: 3072
#include<bits/stdc++.h>
#define ll long long 
#define ld long double
#define X first
#define Y second
#define pb push_back
#define max_el(x) max_element(x.begin(),x.end())-x.begin()
#define min_el(x) min_element(x.begin(),x.end())-x.begin()
#define mp make_pair
#define endl '\n'
#define fastread ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
// DONT USE MEMSET, USE VECTORS

int main(){
	fastread;
	int n,m;
	cin>>n>>m;
	cout<<((n*(n-1))/2+(m*(m-1))/2)<<endl;
	return 0;
}


Measured memory_bytes: 256
N,M = map(int,input().split())
order = {}
if N==1 and M==0:
  print(0)
else:
  for i in range(M):
    s,c = map(int,input().split())
    if order.get(s,-1)==-1:
        order[s]=c
    elif order.get(s,-1)!=-1 and order[s]!=c:
        print(-1)
        break
  else:
    moji = [1]+[0]*(N-1)
    for k in order.keys():
        moji[k-1]=order[k]
    if N!=1 and moji[0]==0:
      print(-1)
    else:
      print(''.join([str(a) for a in moji]))


Measured memory_bytes: 3064
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi acos(-1.0)
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

string conv(string s, string a, string b){
	string t;
	int n = a.length();
	REP(i,s.length()){
		if (s.substr(i,n) == a){
			t += b;
			i += n-1;
		}else{
			t += s[i];
		}
	}
	return t;
}

int main(){
	int n;
	while (cin >> n && n){
		vector<string> a(n), b(n);
		REP(i,n) cin >> a[i] >> b[i];
		string s, t;
		cin >> s >> t;
		queue<string> que;
		map<string, int> mp;
		que.push(s);
		mp[s] = 1;
		int ans = -1;
		while (!que.empty() && ans == -1){
			string s = que.front();
			que.pop();
			REP(i,n){
				string next;
				next = conv(s, a[i], b[i]);
				if (next == t){
					ans = mp[s];
					break;
				}
				if (mp[next] > 0 || next.length() > t.length()) continue;
				mp[next] = mp[s] + 1;
				que.push(next);
			}
		}
		cout << ans << endl;
	}

    return 0;
}

Measured memory_bytes: 3332
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
typedef pair<int,int> P;
struct edge{int to, id;};
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mod 1000000007

int main(){
    int n;
    cin >> n;
    if(n % 1000 == 0) cout << 0 << endl;
    else{
        int ans = n % 1000;
        cout << 1000 - ans << endl;
    }
    return 0;
}

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

#define FOR(i,a,b) for(int i=(a);i<(int)(b);i++)
#define rep(i,n) FOR(i,0,n)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int)(x).size()
#define pb push_back

bool is_prime(int n) {
    if(n < 2) return false;
    else if(n == 2) return true;
 
    if(n % 2 == 0) return 0;
    for(int i=3; i*i<=n; i+=2) if(n % i == 0) return false;
    return true;
}

int M(int n, int p) {
    vector<int> primes;
    FOR(i,n+1,n+500) if(is_prime(i)) primes.pb(i);
    vector<int> sums;
    rep(i,SZ(primes)) FOR(j,i,SZ(primes)) sums.pb(primes[i] + primes[j]);
    sort(ALL(sums));
    return sums[p-1];
}

int main() {
    int n,p;
    while(cin>>n>>p) {
        if(n==-1 and p==-1) break;
        cout << M(n,p) << "\n";
    }
    return 0;
}

Measured memory_bytes: 3128
// 2013/05/12 Tazoe

#include <iostream>
#include <vector>
using namespace std;

bool isSequence(vector<int>& t)
{
	for(int i=0; i<t.size()-2; i++){
		if(t[i+1]-t[i]!=t[i+2]-t[i+1])
			return false;
	}

	return true;
}

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

		if(n==0)
			break;

		vector<int> h(n+1);
		for(int i=0; i<n+1; i++){
			cin >> h[i];
		}

		for(int i=0; i<n+1; i++){
			vector<int> tmp = h;
			tmp.erase(tmp.begin()+i);

			if(isSequence(tmp)){
				cout << h[i] << endl;
				break;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 1220
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> T;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
int N;
ll s[100100];
vector<ll> dp[100100];
int main(){
	cin >> N;
	for(int i=0;i<N;i++){
		cin >> s[i];
	}
	ll ans = 0ll;
	for(int i=1;i<N-1;i++){
		dp[i].resize(N/i+5);
		fill(all(dp[i]),0);
	}
	for(int i=1;i<N-1;i++){
		for(int j=1;i*j<N-1;j++){
			dp[i][j]=dp[i][j-1]+s[N-1-j*i]+s[j*i];
			int a = N-1-i*j;
			if(a<=i)continue;
			if(a%i==0&&a/i<=j)continue;
			ans = max(ans,dp[i][j]);
			//cout << dp[i][j] << ' ';
		}
		//cout << endl;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 17792
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    int n;
    cin >> n;
    vector <int> a(n), start(n);
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sum += a[i];    
    }   
    if (sum % ((n + 1) * n / 2)) {
        cout << "NO" << endl;
        exit(0);
    }   
    int k = sum / ((n + 1) * n / 2);
    for (int i = 0; i < n; ++i) {
        int r = (i + 1) % n;
        if (a[r] > a[i] + k) {
            cout << "NO" << endl;
            exit(0);
        }   
        if ((a[i] + k - a[r]) % n) {
            cout << "NO" << endl;
            exit(0);
        }   
        start[r] = (a[i] + k - a[r]) / n;
    }   

    int tot = 0;
    for (int e : start)
        tot += e;

    if (tot == k)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;

}

Measured memory_bytes: 1792
from bisect import bisect_right

def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    ass.sort()
    return ass 

N,M = map(int,input().split())
a = M//N

li = divisor(M)

x = bisect_right(li,a)

print(li[x-1])


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

main()
{
    string s;
    cin>>s;
    for(char &c: s) c='x';
    cout << s << "\n";

    // int k,n; cin>>n>>k;
    // vector<int> acc(n+1);
    // int ans{};
    // for(int i=1; i<=n; ++i)
    // {
    //     int p; cin>>p;
    //     acc[i]=acc[i-1]+p;
    //     if(i<k) continue;
    //     int tmp=acc[i]-acc[i-k];
    //     if(tmp>ans) ans=tmp;
    // }
    // cout << double(ans+k)/2 << "\n";
}

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

a, b, c = MAP()

if a+b+c <= 21:
    print('win')
else:
    print('bust')


Measured memory_bytes: 3064
import java.util.Scanner;
public class Main{
	public void solve(){
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		for(int r=0;r<N;r++){
			int nr=sc.nextInt();
			int pr=sc.nextInt();
			int ns=sc.nextInt();
			int ps=sc.nextInt();
			int goukei=nr*ns+pr*ps;
			if(ns>=5&&ps>=2){
				goukei=(nr*ns+pr*ps)*4/5;
			}else{
				if(ns<5){
					ns=5;
				}
				if(ps<2){
					ps=2;
				}
				int wari=(nr*ns+pr*ps)*4/5;
				if(goukei>=wari){
					goukei=wari;
				}
			}
			System.out.println(goukei);
		}
	}
	public static void main(String[]args){
		Main obj=new Main();
		obj.solve();
	}
}

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

using namespace std;

void Main() {
    int n;
    cin >> n;
    int nOrg = n;

    map<int, int> fact;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            fact.insert(make_pair(i, 0));
            while (n % i == 0) {
                n /= i;
                fact[i] += 1;
            }
        }
    }
    if (n != 1) {
        fact.insert(make_pair(n, 1));
    }

    cout << nOrg << ":";
    for (auto e : fact) {
        for (int i = 0; i < e.second; ++i) {
            cout << " " << e.first;
        }
    }
    cout << endl;
}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}



Measured memory_bytes: 3112
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let a: isize = iterator.next().unwrap().parse().unwrap();
    let b: isize = iterator.next().unwrap().parse().unwrap();
    let c: isize = iterator.next().unwrap().parse().unwrap();

    if a == b {
        return c.to_string();
    }

    if b == c {
        return a.to_string();
    }

    return b.to_string();
}


Measured memory_bytes: 2120
#include<iostream>
using namespace std;
#include<set>
#include<vector>
set<string> s;
void function(int initial,int final,vector<int> &v)
{
	if(initial>final)
	{
		string str="";
		for(int x:v)
		{
			char y=char(x);
			str+=y;
		}
		s.insert(str);
	}
	else
	{
		int m=v[0];
		for(int j=1;j<v.size();j++)
		{
			m=max(m,v[j]);
		}
		for(int j=97;j<=m+1;j++)
		{
			v.push_back(j);
			function(initial+1,final,v);
			auto it=v.end();
			it--;
			v.erase(it);
		}
	}
}
int32_t main()
{
    int n;
    cin>>n;
    vector<int> v;
    v.push_back(97);
    function(1,n-1,v);
    for(string str:s)
        cout<<str<<endl;
}


Measured memory_bytes: 14208
#!venv/bin/python
#from collections import defaultdict 
from itertools import combinations
from collections import defaultdict
from pprint import pprint
import math
import datetime
import sys

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
B.append(0)

ans = 0
for i in range(N):
    a = A[i]
    b = B[i]
    en = min(a,b)
    ans += en
    if a < b:
        en = min(A[i+1],(b-a))
        A[i+1] -= en
        ans += en
print(ans)


Measured memory_bytes: 19108
#include<iostream>
#include<algorithm>
#include<math.h>
#define _USE_MATH_DEFINES

using namespace std;

int a, b, c = 0;

int main(){
	cin >> a >> b;

	if (a <= b) {
		c = a;
	}
	else {
		c = a - 1;
	}

	cout << c << endl;

	return 0;
}

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

int main() {
    string s; cin >> s;
    int cnta=1, cntb=0;
    bool turn = false;
    for(int i=0; i<s.size()-1; i++){
        if(s.at(i)!=s.at(i+1) && !turn) cnta++;
        else if(s.at(i)!=s.at(i+1) && turn) cntb++;
        else if(s.at(i)==s.at(i+1)) {
            if(turn){
                cnta++;
                turn = !turn;
            }
            else{
                cntb++;
                turn = !turn;
            }
        }
    }

    int ans = s.size() - max(cnta, cntb);
    cout << ans << endl;
}


Measured memory_bytes: 512
n = gets.to_i
numbers = []
n.times do
  numbers << gets.to_i
end
colors = []
colors << -1
numbers.each do |number|
  if number > colors.first
    colors[0] = number
    next
  elsif number < colors.last
    colors << number
    next
  end

  index = colors.bsearch_index { |x| number > x }
  if index
    colors[index] = number
  else
    colors << number
  end
end
puts colors.length

Measured memory_bytes: 3764
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		StringTokenizer st;
		StringBuilder sb;
		int start, time;

		while ((line = br.readLine()) != null) {
			st = new StringTokenizer(line);
			sb = new StringBuilder();
			start = time = 0;
			start = Integer.parseInt(st.nextToken());
			time -= Integer.parseInt(st.nextToken()) * 60;
			time -= Integer.parseInt(st.nextToken());
			time += (Integer.parseInt(st.nextToken()) - start) * 3600;
			time += Integer.parseInt(st.nextToken()) * 60;
			time += Integer.parseInt(st.nextToken());
			sb.append((time / 3600) + " ");
			time %= 3600;
			sb.append((time / 60) + " ");
			time %= 60;
			sb.append(time);
			System.out.println(sb.toString());
		}
	}
}

Measured memory_bytes: 16876
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a =scan.nextInt();
		int b =scan.nextInt();
		int c =scan.nextInt();
		if(a<b &&b<c)System.out.println("Yes");
		else System.out.println("No");
        scan.close();
	}

}


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

#define REP(i, n) for(int (i)=0;(i)<(n);++(i))
#define REPV(iter, v) for(auto (iter)=(v).begin(); (iter)!=(v).end();++(iter))
#define ALL(v) (v).begin(),(v).end()

#define MOD 1000000007

using namespace std;

typedef long long ll;

int main()
{
    ll N, M;
    cin >> N >> M;
    vector<ll> a(M), b(M), bitKey(M);
    REP(i, M)
    {
        cin >> a[i] >> b[i];
        bitKey[i] = 0;
        REP(j, b[i])
        {
            ll c;
            cin >> c;
            c--;
            bitKey[i] |= 1 << c;
        }
    }

    ll dp[M + 1][1 << N];
    ll INF = 1e12;
    REP(i, M + 1)
    {
        REP(j, 1 << N)
        {
            dp[i][j] = INF;
        }
    }
    dp[0][0] = 0;

    for (ll i = 1; i <= M; ++i)
    {
        REP(j, 1 << N)
        {
            ll bitNow = j | bitKey[i - 1];
            dp[i][bitNow] = min(dp[i][bitNow], dp[i - 1][j] + a[i - 1]);
            dp[i][j] = min(dp[i - 1][j], dp[i][j]);
        }
    }
    ll ans = dp[M][(1 << N) - 1] == INF ? -1 : dp[M][(1 << N) - 1];

    cout << ans << endl;
}

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

int main()
{
        long long a, b;
        cin >> a >> b;
        long long ans1 = a / b;
        long long ans2 = a % b;
        double ans3 = (double)a / b;
        printf("%d %d %.5lf\n", ans1, ans2, ans3);



}



Measured memory_bytes: 3224
#include <iostream>
#define MAX 1000000005
using namespace std;

int n;
int a[200005];
long long cnt=0;
int l[100005];
int r[100005];

void merg(int s,int e){
    int i,mid=(s+e)/2;
    int n1=mid-s+1;
    int n2=e-mid;
    for(i=0;i<n1;i++)l[i]=a[s+i];
    for(i=0;i<n2;i++)r[i]=a[mid+1+i];
    l[n1]=r[n2]=MAX;
    int l_i=0,r_i=0;
    for(i=0;i<=e-s;i++){
        if(l[l_i]<r[r_i])a[s+i]=l[l_i++];
        else {
            cnt+=r_i-i+n1;
            a[s+i]=r[r_i++];
        }
    }
}

void mergesort(int s,int e){
    if(s<e){
        int mid=(e+s)/2;
        mergesort(s,mid);
        mergesort(mid+1,e);
        merg(s,e);
    }
}

int main()
{
    cin>>n;
    int i;
    for(i=0;i<n;i++){cin>>a[i];}
    mergesort(0,n-1);
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 4656
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
#define REP(i, limit) for(int i=0; i< limit; ++i)
#define LINT long long

const int N=(int)100000;
bool isprime[N+1];
int psum[N+1];


int main(){
  for(int i=0; i<N+1; i=i+2){
    isprime[i]=false;
  }
  isprime[2]=true;
  isprime[1]=false;
  isprime[3]=true;
  isprime[5]=true;
  isprime[7]=true;

  bool wp;
    for(int i=9; i<N; i=i+2){
    wp=true;
    for(int j=3; j<=sqrt(i); j=j+2){
      if(i%j==0){
      wp=false;
      break;
      }
    }
    isprime[i] = wp ? true : false;
  }

  psum[0]=0;
  psum[1]=0;
  for(int i=1; i<N+1; i=i+2){
    psum[i-1]=psum[i-2];
    psum[i] = psum[i-2] + ((isprime[i] && isprime[(i+1)/2]) ? 1 : 0);
  }


  int Q;
  cin>>Q;
  int l, r;
  REP(i, Q) {
    cin >> l >> r;
    cout << psum[r]-psum[l-1]<<endl;;
  }





  return 0;
}


Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define LONG_LONG_MAX    9223372036854775807LL
#define LONG_LONG_MIN    (-LONG_LONG_MAX-1)


/*
3
0 1 1
1 0 1
1 1 1
*/

vector<vector<int> >v;
vector<vector<int> >dp;
int n;

int ways(int men,int women){
    if(dp[men][women]!=-1){
        return dp[men][women];
    }
    int w=0;
   for(int i=0;i<n;i++){
        if((women&(1<<i)) && v[men][i]==1){
            w += ways(men+1,(women&(~(1<<i))));
            w %=mod;
        }
   }
   return dp[men][women] = w;
}

void solve(){
   cin>>n;
   v.resize(n,vector<int>(n,0));
   for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        cin>>v[i][j];
    }
   }
   int men = (1<<n)-1;
   int women = (1<<n)-1;
   dp.resize(n+1,vector<int>(women+1,-1));
   dp[n][0]=1;
   cout<<ways(0,women)<<"\n";

}

int main(){
//    cin.tie(0);
//    cout.tie(0);
//    cin.sync_with_stdio(0);
//    cout.sync_with_stdio(0);

    cout.precision(10);
    int t=1;//cin>>t;
    while(t--){

        solve();
    }
    return 0;
}


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

using namespace std;

int main()
{

    int y, m , ym = 0 , my = 0 , yy = 0 , mm = 0;
    string s;

    cin >> s;

    for(int i = 0; i < s.size(); i++)
    {
        if(i <= 1)
        {
            y = yy * 10 + s[i] - 48;
            yy = y;
            //cout << y << endl;
        }

        else
        {
            m = mm * 10 + s[i] - 48;
            mm = m;

        }

    }

    //cout << y << m << endl;

    if(y >= 0 && m >= 1 && m <= 12 )
    {
        ym = 1;
    }

    if(y >= 1 && y <= 12 && m >= 0)
    {
        my = 1;
    }

    if(ym && !my )
       cout << "YYMM"<< endl;
    else if(!ym && my)
    {
         cout << "MMYY"<< endl;
    }

    else if(my && ym)
    {
        cout << "AMBIGUOUS" << endl;
    }

    else
       cout << "NA" << endl;



    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vs = vector<string>;
using vll = vector<long long>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long>>;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

int dp[105][2][4];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string s;
    cin >> s;
    int n = s.size();
    int k;
    cin >> k;
    dp[0][0][0] = 1;
    rep(i, n) {
        int x = s[i] - '0';
        rep(j, 2) {
            // 0でない数字が何個か
            rep(k, 4) {
                // 次に入れる数字
                rep(l, j?10:x+1) {
                    if (k+(l?1:0)<=3) {
                        dp[i+1][j||(l<x)][k+(l?1:0)] += dp[i][j][k];
                    }
                }
            }
        }
    }
    cout << dp[n][0][k] + dp[n][1][k] << endl;
}

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

typedef long long ll;
typedef pair<ll,ll> ii;
typedef long double ld;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
const int INF=2012345678;
const ll LLINF=4012345678012345678LL;
const ll MOD=1000000007;
const ld PI=3.1415926535898;
const ld EPS=1e-9;
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(b==0)return a;return gcd(b,a%b);}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline ll expo(ll b,ll p,ll m){ll res=1; while(p){if(p&1)res=(res*b)%m; b=(b*b)%m; p>>=1;} return res;}
inline ll modinv(ll a,ll m){return expo(a,m-2,m);}

ll n,a,b,d;
pair<ii,int> arr[100005];
ll deg[100005];

ll ft1[100005],ft2[100005];
void upd(int x,int y){
    for(int i=x;i<=n;i+=(i&(-i))){
        ft1[i]++;
        ft2[i]-=(x-1);
    }
    for(int i=y+1;i<=n;i+=(i&(-i))){
        ft1[i]--;
        ft2[i]+=y;
    }
    return;
}
ll qry(int x,int y){
    ll ans=0;
    for(int i=y;i;i-=(i&(-i))){
        ans+=y*ft1[i]+ft2[i];
    }
    for(int i=x-1;i;i-=(i&(-i))){
        ans-=((x-1)*ft1[i]+ft2[i]);
    }
    return ans;
}

ll par[100005],rnk[100005];
int root(int x){return par[x]==x?x:root(par[x]);}
void init(){for(int i=0;i<n;i++){par[i]=i;rnk[i]=1;}}
void join(int x,int y){
	int rx=root(x),ry=root(y);
	if(rx==ry)return;
	if(rnk[rx]>rnk[ry])par[ry]=rx;
	else if(rnk[ry]>rnk[rx])par[rx]=ry;
	else{par[rx]=ry;rnk[ry]++;}
}

void build(int t){
	int x,y;
	for(int i=0;i<n;i++){
		x=lower_bound(arr,arr+n,mp(mp(arr[i].fi.fi+d,arr[i].fi.se-d),0))-arr;
		y=lower_bound(arr,arr+n,mp(mp(arr[i].fi.fi+d,arr[i].fi.se+d+1),0))-arr-1;
		if(t){
			if(arr[x].fi.se==arr[i].fi.se-d)x++;
			if(arr[y].fi.se==arr[i].fi.se+d)y--;
		}
		if(x>y)continue;
		deg[arr[i].se]++;
		deg[arr[x].se]++;
		join(arr[i].se,arr[x].se);
		//printf("%d %d\n",arr[i].se,arr[x].se);
		if(x<y)upd(x+1,y);
	}
	for(int i=1;i<n;i++){
		ll q=qry(i,i);
		if(q){
			join(arr[i-1].se,arr[i].se);
			deg[arr[i-1].se]+=q;
			deg[arr[i].se]+=q;
		}
	}
}

int main(){
	scanf("%d%d%d",&n,&a,&b); a--;b--;
	int x,y;
	for(int i=0;i<n;i++){
		scanf("%d%d",&x,&y);
		arr[i].fi.fi=x+y;
		arr[i].fi.se=x-y;
		arr[i].se=i;
	}
	init();
	d=max(abs(arr[a].fi.fi-arr[b].fi.fi),abs(arr[a].fi.se-arr[b].fi.se));
	sort(arr,arr+n);
	build(0);
	memset(ft1,0,sizeof(ft1));memset(ft2,0,sizeof(ft2));
	for(int i=0;i<n;i++)swap(arr[i].fi.fi,arr[i].fi.se);
	sort(arr,arr+n);
	build(1);
	int r=root(a);
	ll ans=0;
	for(int i=0;i<n;i++){
		if(root(i)==r)ans+=deg[i];
	}
	printf("%lld",ans/2LL);
}


Measured memory_bytes: 6528
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
 
using namespace std;
int MOD = 1000000007;
signed main(){
 
    int n,k;
    cin >> n >> k;

    int a[41] = {0};
    rep(j,n){
        int t;
        cin >> t;
        int i = 0;
        while(t != 0){
            a[i] += t%2;
            t /= 2;
            i++;
        }
    }
    int ans = 0;
    int pow2[41] = {0};
    pow2[0] = 1;
    for(int i = 1;i <= 40;i++) pow2[i] = 2*pow2[i-1];
    int x = 0;
    for(int i = 40;i >= 0;i--){
        if((n%2 && a[i] <= n/2) || (!(n%2) && a[i] < n/2)){
            if(x + pow2[i] > k){
                ans += a[i]*pow2[i];
            }else{
                x += pow2[i];
                ans += (n-a[i])*pow2[i];
            }
        }else{
            ans += a[i]*pow2[i];
        }
        //cerr << i << " " << ans << endl;
    }
    cout << ans << endl;

    

    return 0;   
}
// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://ddcc2019-final.contest.atcoder.jp/tasks/ddcc2019_final_a
// rm -r -f test;oj dl http://abc117.contest.atcoder.jp/tasks/abc117_d

Measured memory_bytes: 256
/*
  ∧,,∧
( 'ω' )つ ＜WA,またお前か！！　
（m9 ＼ 　　
　 ＼　 ＼
　 　 ) ) ＼
　 ／／ ＼ ＼
　 (＿） 　 (＿)
*/

#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(),(x).end()
#define rep(x, y) for (int x = 0; x < y; x++)
#define MOD 1000000007

typedef long long LL;
typedef long double LD;

bool compare_by_b(pair<int, int> a, pair<int, int> b)
{
    if (a.second != b.second) {
        return a.second < b.second;
    } else {
        return a.first < b.first;
    }
}

ostringstream oss_global;
string s_global = oss_global.str();

int main()
{
    long a, b, n;
    cin >> n >> a >> b;

    if (a > b) swap(a, b);

    long ans;
    if ((b-a) % 2 == 0) {
        ans = (b - a) / 2;
    } else {
        long x = a + (b-a-1)/2;
        long y = n - b + 1 + (b-a-1)/2;
        ans = min(x, y);
    }

    cout << ans << endl;
    return 0;
}


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

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

int main(){
    int n, r, i;
    cin >>  n;
    int x[n+1], dx[n];
    for(i=0; i<=n; i++){
        cin >> x[i];
    }
    sort(x, x+n+1);
    r = x[1] - x[0];
    for(i=1; i<n; i++){
        r = gcd(r, x[i+1]-x[i]);
    }
    cout << r;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define pb push_back
#define fs first
#define sc second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef pair<ll, int> plli;
typedef vector<pii> vpii;
typedef tree<pii, null_type, less<pii>, rb_tree_tag,
    tree_order_statistics_node_update> ost;

const int N=3100;
const int P=1e9+7;
int t[2][2*N][N];

int main() {
    int i, j, k, n, m;
    scanf("%d%d", &n, &m);
    for(k=0; k<2; k++) {
        for(j=0; j<=n-k; j++)
            t[k][0][j]=1;
        for(i=1; i<=2*m; i++) for(j=0; j<=n-k-(i&1); j++) {
            t[k][i][j]=t[k][i-1][j];
            if(i&1) t[k][i][j]+=t[k][i-1][j+1];
            else if(j>0) t[k][i][j]+=t[k][i-1][j-1];
            if(t[k][i][j]>=P) t[k][i][j]-=P;
        }
    }
    ll ans=t[0][2*m][0];
    for(i=1; i<2*m; i+=2)
        ans=(ans+t[0][2*m-i][0]*1LL*t[1][i-1][0])%P;
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 149760
#include <iostream>
#include <cstring>

using namespace std;

int main(void){
	int qs[3][50000];
	bool decided[2][50000];
	
	int h,w,q;
	while(cin >> h >> w >> q){
		if(!(h|w|q)) break;
		
		memset(qs,0,sizeof(qs));
		memset(decided, false, sizeof(decided));
		long long ret = 0;
		int nrow = 0 ,ncol = 0;
		for(int i=0;i<q;i++){
			cin >> qs[0][i] >> qs[1][i] >> qs[2][i];
		}
		
		for(int i=q-1;i>=0;i--){
			if(qs[0][i] == 0){
				//query for a row
				if(decided[0][qs[1][i]]) continue;
				if(qs[2][i] == 1) ret += w - ncol;
				decided[0][qs[1][i]] = true;
				nrow++;
			}else{
				//query for a col
				if(decided[1][qs[1][i]]) continue;
				if(qs[2][i] == 1) ret += h - nrow;
				decided[1][qs[1][i]] = true;
				ncol++;
			}
		}
		cout << ret << endl;
	}
}

Measured memory_bytes: 1548
import std.stdio, std.conv, std.string, std.algorithm,
       std.math, std.array, std.container, std.typecons;

void main() {
  int n = readln.chomp.to!int;
  string[] s = new string[n];
  DList!string slist;
  int maxcount = 1;
  int count = 1;
  for(int i=0; i<n; i++) s[i] = readln.chomp;
  std.algorithm.sort(s);
  slist.insert(s[0]);
  for(int i=1; i<n; i++) {
    if(s[i-1]==s[i]) count++;
    else count=1;
    if(count>maxcount) {
      slist.clear;
      maxcount = count;
    }
    if(count==maxcount) slist.insert(s[i]);
  }
  while(!slist.empty) {
    writeln(slist.front);
    slist.removeFront;
  }
}



Measured memory_bytes: 18044
#include<iostream>
#include<vector>
#include<bitset>
#include<string>
#include<cmath>
#include<algorithm>
#include<stack>
#include<list>
#include<queue>
#include<map>
#include<numeric>
#include<set>
#include<iterator>
using namespace std;
#define rep(i,x) for(int i=0;i<x;i++)
#define re(i,x,y) for(int i=x;i<y;i++)
int INF=1e9;
const long long mod=1e9+7;
typedef long long ll;
int main(){
    int n;
    set<int>a,b;
    cin>>n;
    while(n--){
        int x;
        cin>>x;
        a.insert(x);
    }
    cin>>n;
    while(n--){
        int x;
        cin>>x;
        b.insert(x);
    }
    vector<int>c;
    set_symmetric_difference(a.begin(),a.end(),b.begin(),b.end(),back_inserter(c));
    for(int i=0;i<c.size();i++)cout<<c[i]<<endl;
    return 0;
}


Measured memory_bytes: 23728
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define inf 1000000000
#define md 1000000007
#define pb push_back
#define li 100005
#define lo long long
using namespace std;
int n,m,vis[25][25],d[25][25][25][25];
char A[25][25];
bool ok(int go1,int go2){
	if(go1>=1 && go1<=n && go2>=1 && go2<=m && A[go1][go2]=='.') return true;
	return false;
}
void bfs(int x,int y){
	queue< pair<int, pair<int,int> > > q;
	q.push(mp(0,mp(x,y)));
	memset(vis,0,sizeof(vis));
	while(!q.empty()){
		int cst=q.front().fi;
		int xx=q.front().se.fi;
		int yy=q.front().se.se;
		q.pop();
		if(vis[xx][yy]==1) continue;
		vis[xx][yy]=1;
		d[x][y][xx][yy]=cst;
		if(ok(xx+1,yy)) q.push(mp(cst+1,mp(xx+1,yy)));
		if(ok(xx-1,yy)) q.push(mp(cst+1,mp(xx-1,yy)));
		if(ok(xx,yy+1)) q.push(mp(cst+1,mp(xx,yy+1)));
		if(ok(xx,yy-1)) q.push(mp(cst+1,mp(xx,yy-1)));
	}
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf(" %c",&A[i][j]);
		}
	}
	int mx=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(A[i][j]!='#'){
				bfs(i,j);
			}
			for(int k=1;k<=n;k++){
				for(int t=1;t<=m;t++){
					mx=max(mx,d[i][j][k][t]);
				}
			}
		}
	}
	printf("%d\n",mx);
	return 0;
}




Measured memory_bytes: 1280
def get_match_list(num_list, num_num):
    match_num_list = set()
    match_dic = [2,5,5,4,5,6,3,7,6]
    for num in num_list:
        match_num_list.add(match_dic[num-1])
    match_num_list = list(match_num_list)
    match_num_list.sort()
    return match_num_list

def get_dp(use_match_list, match_nun):
    dp = [-1 for i in range(match_nun + 1)]
    dp[0] = 0
    for i in range(2, match_nun + 1):
        for macth_bar in use_match_list:
            if dp[i-macth_bar] >= 0:
                dp[i] = dp[i-macth_bar] + 1
                break
    return dp

def print_ans(dp, match_nun, num_list):
    match_dic = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    max_ketasuu = dp[match_nun]
    ans = ''
    while match_nun > 0:
        for num in num_list:
            use_match_num = match_dic[num - 1]
            if match_nun - use_match_num < 0:
                continue
            if dp[match_nun - use_match_num] == max_ketasuu - 1:
                ans += str(num)
                match_nun -= use_match_num
                max_ketasuu -= 1
                break
    print(ans)



def main():
    match_nun, num_num = map(int, input().split())
    num_list = list(map(int, input().split()))
    num_list.sort(reverse=True)
    use_match_list = get_match_list(num_list, num_num)
    dp = get_dp(use_match_list, match_nun)
    print_ans(dp, match_nun, num_list)


if __name__ == '__main__':
    main()

Measured memory_bytes: 3324
#define _USE_MATH_DEFINES
#define INF 100000000

#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>

using namespace std;

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

static const double EPS = 1e-8;

int calc(int Y,int M,int D){
	int res = 0;
	for(int y=1;y<=Y;y++){
		int ubm = 10;
		if(y==Y) ubm = M;
		for(int m=1;m<=10;m++){
			int ubd = 19;
			if(m % 2) ubd = 20;
			if(y % 3 == 0) ubd = 20;
			if(y==Y && m==M) ubd = D;

			for(int d=1;d<=ubd;d++){
				if(y==Y && m==M && d==D) goto found;
				res++;
			}
		}
	}
found:;

	return res;
}

int main(){
	int n;
	int mil = calc(1000,1,1);
	while(~scanf("%d",&n)){
		for(int i=0;i<n;i++){
			int Y,M,D;
			scanf("%d %d %d",&Y,&M,&D);
			printf("%d\n",mil-calc(Y,M,D));
		}
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;
using ll = long long;
using ull = unsigned long long;
using vll = vector<long long>;
using pll = pair<ll, ll>;
#define FOR(i, begin, end) \
    for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) \
    for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define VREP(s, ite) for (auto ite = s.begin(); ite != s.end(); ++ite)
#define FI first
#define SE second
#define ALL(v) v.begin(), v.end()
//#define endl "\n"
#define ciosup  \
    cin.tie(0); \
    ios::sync_with_stdio(false);
#define eb emplace_back
#define vint vector<int>
constexpr ll INF = 1e15 + 7LL;
constexpr ll MOD = 1e9 + 7LL;
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
    for (int i = 0; i < v.size(); ++i) {
        is >> v[i];
    }
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    for (int i = 0; i < v.size() - 1; ++i) {
        os << v[i] << " ";
    }
    if (v.size() > 0) {
        os << v[v.size() - 1] << endl;
    }
    return os;
}

int main() {
    int x,y;
    cin >> x >> y;
    FOR(i,0, x+1){
        if (i *2 + (x - i)*4 == y){
            cout << "Yes"<<endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

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

int main(){
  int n;
  string cha,str;

  cin >> cha >> n;

  int count = 0;

  for(int q=0;q<n;q++) {
    cin >> str;
    int m = str.size();

    int flg = count;
    for(int i=0;i<m;i++) {
      for(int j=0;j<cha.size();j++){
	if(str[(j+i)%m] != cha[j]) break;
	if(j == cha.size()-1) count++;
      }
      if(count != flg) break;
    }

  }

  cout << count << endl;
  return 0;
}

Measured memory_bytes: 1204
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define f(i,n) for(int i=0;i<n;i++)
#define f1(i,n) for(int i=1;i<n;i++)
#define PI 3.14159265358979323846
double tick(){static clock_t oldt,newt=clock();double diff=1.0*(newt-oldt)/CLOCKS_PER_SEC;oldt=newt;return diff;}

using namespace std;

void solve(){
  int x,n,temp,a,b;
  set<int,greater<int>> s;
  cin>>x>>n;
  int p[n];
  f(i,n){
    cin>>temp;
    s.insert(temp);
  }
  s.insert(x);
  if(s.size()==n+1){
    cout<<x;
    return;
  }
  a=x-1;
  b=x+1;
  while(1){
    s.insert(a);
    if(s.size()==n+1){
      cout<<a;
      return;
    }
    else a--;
    s.insert(b);
    if(s.size()==n+1){
      cout<<b;
      return;
    }
    else b++;
  }
	//cout<<tick()<<endl;	
}

int32_t main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  int t;
  // cin>>t;
  // while(t--)
    solve();
  return 0;
}

Measured memory_bytes: 3660
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

# とりあえず二項係数を答えにぶち込む
fact = [1]
for i in range(1, N + 2):
    fact.append(fact[-1] * i % mod)


ans = [0] * (N + 2)
fN = fact[N + 1]
for i in range(1, N + 2):
    div = fact[i] * fact[N - i + 1] % mod
    value = fN * pow(div, mod - 2, mod) % mod
    ans[i] = value

# 数列Aの中に2つあるやつx
# xの左側、右側にあるやつをカウントする
x = Counter(A).most_common()[0][0]
left = A.index(x)
right = N - A.index(x, left + 1)
M = left + right

for i in range(0, M + 1):
    num = fact[M]
    div = fact[i] * fact[M - i] % mod
    comb = num * pow(div, mod - 2, mod) % mod
    ans[i + 1] = (ans[i + 1] - comb + mod) % mod

print(*ans[1:], sep="\n")


Measured memory_bytes: 29976
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<ll> vl;
typedef vector<vector<int, int> > vvi;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define in insert
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = 1e9 + 5;
int main(){
    int n;
    cin >> n;
    string s;
    cin>>s;
    int x = 0;
    int max = 0;
    for(int i = 0; i < s.size(); i++){
        if(s[i]=='I'){
            x++;
            if(max<x) max = x;
        }
        else if(s[i]=='D'){
            x--;
        }
    }
    cout << max;
}

Measured memory_bytes: 256
S=list(input())
year=int(''.join(S[0:4]))
month=int(''.join(S[5:7]))
day=int(''.join(S[8:10]))
if year<2019:
    print('Heisei')
elif year==2019 and month<=4:
    print('Heisei')
else:
    print('TBD')

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

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;

const double PI=3.14159265358979323846;

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

template<class T> void dump(const vector<T> &v)
{
	REP(i, SZ(v)-1){ cout << v[i] << " "; }
	cout << v[SZ(v)-1] << endl;
}

template<class T> void dump(int w, int h, const vector<T> &v)
{
	REP(j, h){
		REP(i, w-1){ cout << v[j * w + i] << " "; }
		cout << v[j * w + w-1] << endl;
	}
}

template<class T> struct Matrix
{
	T w, h;
	vector<T> A;
	Matrix(T w_, T h_) : w(w_), h(h_), A(w * h) {}
	T get(T x, T y) const { return A[y * w + x]; }
};

template<class T> void input(Matrix<T> &m)
{
	REP(j, m.h){
		REP(i, m.w){
			cin >> m.A[j * m.w + i];
		}
	}
}

template<class T> Matrix<T> prod(const Matrix<T> &a, const Matrix<T> &b)
{
	Matrix<T> m(b.w, a.h);

	REP(j, m.h){
		REP(i, m.w){
			ll c = 0;
			REP(k, a.w){
				c += a.A[j * a.w + k] * b.A[k * b.w + i];
			}
			m.A[j * m.w + i] = c;
		}
	}

	return m;
}

void dump(const Matrix<ll> &m)
{
	REP(j, m.h){
		REP(i, m.w-1){ printf("%lld ", m.A[j * m.w + i]); }
		printf("%lld\n", m.A[j * m.w + m.w-1]);
	}
}

void dump(const Matrix<double> &m)
{
	REP(j, m.h){
		REP(i, m.w-1){ printf("%f ", m.A[j * m.w + i]); }
		printf("%f\n", m.A[j * m.w + m.w-1]);
	}
}

int main()
{
	for(;;){
		string s;
		getline(cin, s);

		if(s == "0")
			break;
		
		int sum = 0;

		REP(i, s.length()){
			sum += s[i] - '0';
		}

		cout << sum << endl;
	}


	return 0;
}



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

using namespace std;

vector<vector<int>> G(8,vector<int>(8));
vector<bool> visited(8,false);
int ans;
int n, m;

/*
目的: 頂点を受け取り, 条件を満たすかどうかを探索する. 何も返さない.
*/

void dfs(int v){
    
    bool allVisited = true;
    for (int i = 0; i < n; i++) if (i != v && visited[i] == false) allVisited = false;
    
    if (allVisited){
        ans++;
        return;
    }
    
    visited[v] = true;
    
    for (auto p : G[v]){
        if (!visited[p]) dfs(p);
    }
    
    visited[v] = false;
}

int main(void){
    cin >> n >> m;
    
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--,b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    ans = 0;
    visited[0] = true;
    dfs(0);
    
    cout << ans << endl;
    return 0;
    
}


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

using namespace std;

#define pb push_back
#define mp make_pair
#define fs first
#define fst first
#define sc second
#define snd second
#define sz(X) (int)(X).size()
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define fornr(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define forab(i, a, b) for(int i = int(a); i < int(b); i++)
#define all(X) X.begin(), X.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef double dbl;
typedef long double ld;
typedef vector<int> vi;

const int N = 1e6;
const int LOG = 21;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LLMOD = 998244353;
const ll LLINF = 1e18;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vi a(n), b(n);
    forn(i, n) cin >> a[i];
    forn(i, n) cin >> b[i];
    set<pii> q;
    forn(i, n) q.insert({b[i], i});
    ll ans = 0;
    while (!q.empty()) {
        int i = q.rbegin()->second;
        q.erase(*q.rbegin());
        int neighbors = b[(i + n - 1) % n] + b[(i + 1) % n];
        int d = b[i] - a[i];
        if (d % neighbors == 0) {
            ans += d / neighbors;
            b[i] = a[i];
        } else {
            if (neighbors >= b[i]) {
                cout << "-1\n";
                return 0;
            }
            ans += b[i] / neighbors;
            b[i] %= neighbors;
            if (b[i] < a[i]) {
                cout << "-1\n";
                return 0;
            }
            q.insert({b[i], i});
        }
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 11264
#include <iostream>
#include <vector>
#include <fstream>
#include <numeric>
#include <unordered_set>
#include <sstream>
#include <cassert>
#include <tuple>
#include <iomanip>
#include <random>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <chrono>
#include <stack>
#include <string>
#include <bitset>
#include <unordered_map>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>

using namespace std;

#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x.size())
#define pb push_back
#define pii pair <int, int>
#define print(x) for(auto it : x) cout << it << ' ';
#define endl "\n" // TODO: remove
#define int long long

const int N = (1e6) + 322;
const int inf = (int)(2e9);
const int mod = (int)(1e9) + 7; // check modulo

int n, cnt[N];
vector <int> v[N];

int get(int x) {
    return (x) * (x + 1) / 2;
}

void solve() {
    cin >> n;
    for(int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        if (x > y) swap(x, y);
        cnt[y]++;
        v[x].pb(y);
    }
    int sum = 0;
    for(int i = 1; i <= n; ++i) {
        cnt[i] += cnt[i - 1];
        sum += cnt[i];
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i) {
        ans += (get(n - i + 1) - sum);
        for(auto to : v[i]) {
            sum -= (n - to + 1);
        }
    }
    cout << ans;
}

signed main () {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
//    int test; cin >> test;
//    for(int t = 1; t <= test; ++t) {
        solve();
//    }
    return 0;
}


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

using namespace std;

#define int long long

main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	string s;
	cin >> s;
		
	int nr = 0;
	int p = 0;
	
	for(int i = 0; i < s.size(); i++)
		if(s[i] == 'A')
			p++;
		else
		{
			if(i + 1 < s.size() && s[i] == 'B' && s[i + 1] == 'C')
			{
				nr += p;
				i++;
			}
			else
				p = 0;
		}
	
	cout << nr;
}


Measured memory_bytes: 720
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector as V
import qualified Data.ByteString.Char8 as C
import Debug.Trace
import Data.List
import Control.Monad
import Control.Arrow
import Data.Ord
import qualified Data.IntSet as IS


r :: Int -> IO (U.Vector Int)
r n = U.unfoldrN n (C.readInt . C.dropWhile (==' ')) <$> C.getLine

r' :: IO [Int]
r'  =   unfoldr    (C.readInt . C.dropWhile (==' ')) <$> C.getLine



main :: IO ()
main = do
    [a,b,c,k] <- r'
    print $ if k <= a then k else if k <= a+b then a else a - (k - (a+b))


Measured memory_bytes: 3772
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int a, b;
    cin >> a >> b;
    if  (a%2 == 1 && b%2 == 1){
        cout << "Odd" << endl;
    }
    else {
        cout << "Even" << endl;
    }
}

Measured memory_bytes: 256