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

#define int long long 
#define double long double

typedef pair<int,int> pi;

typedef vector<int> vi;
typedef vector<pi> vpi;

#define f first
#define s second
#define mp make_pair
#define pb push_back

#define gcd __gcd

const int INF = 1e18+1;
const int MOD = 1e9+7;
const double PI = 3.14159265358979323846264338;

int fast_ex(int a,int n,int m){
  if(n == 0)return 1;
  if(n == 1)return a;
  int x = 1;
    x *= fast_ex(a,n/2,m);
    x %= m;
    x *= x;
    x %= m;
    if(n%2)x*= a;
    x %= m;
    return x;
}

signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  int a,b,c;
  cin >> a >> b >> c;
  int one = a*b*(c/2);
  int two = a*c*(b/2);
  int three = b*c*(a/2);
  int tot = a*b*c;
  int x,y,z;
  x = tot-one;
  y = tot-two;
  z = tot-three;
  int ans = min(abs(x-one),abs(y-two));
  ans = min(ans,abs(z-three));
  cout << ans;
  return 0;
}

Measured memory_bytes: 256
from collections import deque

N, M = [int(x) for x in input().split()]
route = {int(x): [] for x in range(N)}

for _ in range(M):
    a, b = [int(x) - 1 for x in input().split()]
    route[a].append(b)
    route[b].append(a)

queue = deque()
queue.append(0)

all_town = set([int(x) for x in range(N)])

result = 0
while queue:
    pos = queue.popleft()
    all_town.discard(pos)

    for next_pos in route[pos]:
        if next_pos in all_town:
            queue.append(next_pos)

    if not queue:
        if all_town:
            queue.append(all_town.pop())
            result += 1

print(result)


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

int main()
{
	int N;
	scanf("%d", &N);
	std::vector<int> A(N + 1);
	for (auto& e: A) scanf("%d", &e);
	int64_t sum{};
	for (int i{}; i < N; i++)
	{
		int B;
		scanf("%d", &B);
		int diff{std::min(A[i], B)};
		sum += diff;
		B -= diff;
		A[i] -= diff;

		diff = std::min(A[i + 1], B);
		sum += diff;
		B -= diff;
		A[i + 1] -= diff;
	}
	printf("%lld\n", sum);

	return 0;
}

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

class Program{
  public static void Main(){
    
    int k = int.Parse(Console.ReadLine());
    
    var que = new Queue<long>();
    for(int i=1; i<=9; i++){
      que.Enqueue(i);
    }
    
    long dq = 0;
    for(int i=0; i<k; i++){
      dq = que.Dequeue();
      
      if(dq%10 != 0){
        que.Enqueue(10*dq +(dq%10) -1);
      }
      que.Enqueue(10*dq +(dq%10));
      
      if(dq%10 != 9){
        que.Enqueue(10*dq +(dq%10) +1);
      }
    }
  
    Console.WriteLine(dq);
  }
}

Measured memory_bytes: 14816
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
const int maxn = 1e5 + 5;
#define INF 1000000000
const int MOD = 1e9+7;
const double PI = 3.14159265358979323846264338;



int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	fastio
	//ifstream cin (".in");
	//ofstream cout (".out");
	int n;
	cin >> n;
    std::vector<ll> a(n);
    for(int i=0; i<n; i++){
    	cin >> a[i];
    }
    ll ans = 0;
    ll temp = a[0];
    for(int i=0; i<n; i++){
    	if(a[i]<temp){
    		ans+=temp-a[i];
    	}else{
    		temp=a[i];
    	}
    }
    cout << ans << endl;
    return 0;

  }



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

using namespace std;

long long inversion_number(std::vector<int> a) {
  const int n = a.size();
  std::vector<int> ft(n + 1);
  auto add = [&](int k, int v) {
    for (k++; k > 0; k -= k & -k) {
      ft[k] += v;
    }
  };
  auto sum = [&](int k) {
    int ret = 0;
    for (k++; k <= n; k += k & -k) {
      ret += ft[k];
    }
    return ret;
  };
  long long ret = 0;
  for (int i = 0; i < n; i++) {
    ret += sum(a[i]);
    add(a[i], 1);
  }
  return ret;
}

long long match(string s, string t) {
  vector<queue<int>> q(256);
  for (int i = 0; i < s.size(); i++) {
    q[s[i]].push(i);
  }

  vector<int> a;
  for (int i = 0; i < t.size(); i++) {
    a.push_back(q[t[i]].front());
    q[t[i]].pop();
  }

  return inversion_number(a);
}

int main() {
  string s;
  cin >> s;

  const int n = s.size();

  vector<int> f(256);

  for (char c : s) {
    f[c]++;
  }

  int cnt = 0;
  for (int i = 0; i < 256; i++) {
    cnt += f[i] % 2;
  }
  if (cnt >= 2) {
    cout << -1 << endl;
    return 0;
  }

  string L, M, R;
  vector<int> p(256);

  for (int i = 0; i < n; i++) {
    char c = s[i];
    if (p[c] < f[c] / 2) {
      L += c;
    } else if (p[c] >= (f[c] + 1) / 2) {
      R += c;
    } else {
      M += c;
    }
    p[c]++;
  }

  long long ans = 0;
  ans += match(s, L + M + R);

  reverse(R.begin(), R.end());
  ans += match(L, R);

  cout << ans << endl;
}


Measured memory_bytes: 4600
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
 int i,j,n,w;
 cin >> n >> w;
 long long int a[n][2],dp[n+1][w+1];
 for(i=0;i<n;i++)
 cin >> a[i][0] >> a[i][1];
 for(i=0;i<=n;i++)
 {
  for(j=0;j<=w;j++)
  {
   if(i==0 || j==0)
   dp[i][j]=0;
   else if(a[i-1][0]<=j)
   dp[i][j]=max(a[i-1][1]+dp[i-1][j-a[i-1][0]],dp[i-1][j]);
   else
   dp[i][j]=dp[i-1][j];
  }
 }
 cout << dp[n][w];
 return 0;
}

Measured memory_bytes: 79104
#![allow(unused_macros)]

// cf. [Rustで競技プログラミングの入力をスッキリ記述するマクロ - Qiita](https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8)
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        N: usize,
        K: usize,
        A: [usize; N],
    }
    if K == 1 {
        println!("{}", A.into_iter().filter(|&x| x == 1).count());
        return;
    }
    //if N == 1 {
        //let ans = if A[0] % K == 1 { 1 } else { 0 };
        //println!("{}", ans);
        //return;
    //}
    let mut cumsum = Vec::with_capacity(N);
    cumsum.push(0);
    for i in 0..N {
        let prev = *cumsum.last().unwrap();
        cumsum.push(prev + A[i]);
    }
    use std::collections::HashMap;
    let mut map = HashMap::new();
    let mut ans = 0usize;
    for r in (1..(N + 1)).rev() {
        let rhs = (cumsum[r] - r) % K;
        if map.is_empty() {
            for l in ((r + 1).saturating_sub(K)..r).rev() {
                let lhs = (cumsum[l] - l) % K;
                *map.entry(lhs).or_insert(0) += 1;
            }
        } else {
            if r + 1 >= K {
                let l = r + 1 - K;
                let lhs = (cumsum[l] - l) % K;
                *map.entry(lhs).or_insert(0) += 1;
            }
        }
        if let Some(&l_cnt) = map.get(&rhs) {
            ans += l_cnt;
        }

        let tmp = (cumsum[r - 1] - (r - 1)) % K;
        *map.get_mut(&tmp).unwrap() -= 1;
    }
    println!("{}", ans);
}


Measured memory_bytes: 17300
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
ab = [LIST() for _ in range(N-1)]
c = LIST()
c.sort(reverse=True)
tree = [[] for _ in range(N)]
for a, b in ab:
	tree[a-1].append(b-1)
	tree[b-1].append(a-1)

# start=None
# for i in range(N):
# 	if len(tree[i]) == 1:
# 		start = i
# 		break

ans = [0]*N
q = deque()
q.append(0)
ans[0] = c[0]
cnt = 1
while q:
	n = q.popleft()
	for node in tree[n]:
		if ans[node]:
			continue
		ans[node] = c[cnt]
		cnt += 1
		q.append(node)
print(sum(c)-max(c))
print(*ans)


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

typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define pi pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int> >
#define vvl vector<vector<long long> >
#define vl vector<ll>
#define vii vector<pair<int,int> >
#define vll vector<pair<long long,long long> >
#define pb push_back
#define mp make_pair3

const ll mod=1e9+7;
#define MAX 100000

template<typename T>
void max_self(T &a,T b){
    a = max(a,b);
}

template<typename T>
void min_self(T &a,T b){
    a = min(a,b);
}

ll binexpo(ll a,ll b,ll c){

    if(b==0) return 1;
    else if(b%2==0) return binexpo(((a%c)*(a%c))%c,b/2,c)%c;
    else return ((a%c)*(binexpo(((a%c)*(a%c))%c,b/2,c)%c))%c;
}

vector<int> adj[MAX+1];
int dist[MAX+1];
int in_degree[MAX+1];
bool visited[MAX+1];

void dfs(int start){
    if(visited[start] == true) return;
    visited[start] = true;
    for(int b : adj[start]){
        max_self(dist[b],dist[start] + 1);
        in_degree[b]-=1;
        if(in_degree[b] == 0) dfs(b);
    }
}

int main(){

    std::ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,m;
    cin>>n>>m;

    memset(in_degree,0,sizeof(in_degree));
    FOR(i,0,m){
        int x,y;
        cin>>x>>y;
        adj[x].pb(y);
        in_degree[y]+=1;
    }

    memset(visited,false,sizeof(visited));
    memset(dist,0,sizeof(dist));

    FOR(i,1,n+1)
        if(visited[i] == false && in_degree[i] == 0) dfs(i);

    int ans = 0;
    FOR(i,1,n+1) max_self(ans,dist[i]);
    cout<<ans;
    return 0;
}


Measured memory_bytes: 9728
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD (long long)(1e9+7)
int main(){
	ll s,cnt=0;
	cin>>s;
	vector<ll>hoge;
	hoge.push_back(s);
	cnt++;
	while(true){
		ll now=(hoge[cnt-1]%2==0)?hoge[cnt-1]/2:hoge[cnt-1]*3+1;
		bool flag=false;
		for(int i=0;i<cnt;i++){
			if(now==hoge[i])flag=true;
		}
		hoge.push_back(now);
		cnt++;
		if(flag){
			break;
		}
	}
	cout<<cnt<<endl;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Scanner;
 class Main
{
	public static void main (String[] args)
	 {
		Scanner sc=new Scanner(System.in); 
		int i,j;
		int n=sc.nextInt();
		int k=sc.nextInt();
		int sn[]=new int[n+1];
		for(i=0;i<k;i++)
		{
			int d=sc.nextInt();
			for( j=0;j<d;j++)
			{
				sn[sc.nextInt()]=1;
			}
		}
		int count=0;
		for(i=1;i<=n;i++)
			if(sn[i]==0)
				count++;
		System.out.println(count);
		
			
	}
}

Measured memory_bytes: 46460
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;

class Solution {
public:
    long long solve(vector<int>& A) {
        sort(A.begin(), A.end());
        int n = A.size();

        long long res = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1, k = j + 1; j < n; ++j) {
                while (k < n && (k <= j || A[i] + A[j] > A[k])) {
                    ++k;
                }
                res += max(0, k - j - 1);
            }
        }
        return res;
    }
};

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }
    Solution sol;
    cout << sol.solve(A) << "\n";

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define inf (ll)1e9
#define d(x) cerr<<#x<<"="<<x<<endl;

vector<int> vec;

ll k,a,b,c=1;
int main(void){
    cin>>k>>a>>b;
    if(a<b-1){
        rep(i,k){
            if(a>c)c++;
            else if(k-i>=2){
                c=c-a+b;
                i++;
            }
            else c++;
        }
    }
    else{
        c+=k;
    }
    cout<<c<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define rep(i, n) for(ll i=0; i<(ll)(n); i++)
#define repd(i, n) for(ll i=n-1; 0<=i; i--)
#define FOR(i, a, b) for(ll i=a; i<(ll)(b); i++)
#define FORD(i, a, b) for(ll i=b-1; (ll)(a)<=i; i--)
#define ALL(x) x.begin(), x.end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};


int main(){
    ll n, d;    cin >> n >> d;
    ll res=0;
    rep(i, n){
        ll x, y;     cin >> x >> y;
        if(x*x+y*y<=d*d) res += 1;
    }
    cout << res << endl;
}


Measured memory_bytes: 3672
a=[]
u=[]
x=[]
l=0  
num=input().split(' ')
for i in range(0,int(num[0]),1):
    sum=0
    num2=input().split(' ')
    for j in range(0,int(num[1]),1):
        sum=sum+int(num2[j])
        a.append(int(num2[j]))
    a.append(sum)
for k in range(int(num[1])+1):
    u.append(a[k::int(num[1])+1])
for i in range(0,len(u),1):
    sum2=0
    for j in range(0,len(u[i]),1):
        sum2=sum2+u[i][j]
    x.append(sum2)
for i in range(0,int(num[0]),1):
    for j in range(0,int(num[1])+1,1):
        if j==int(num[1]):
            print(a[l])
            l+=1
        else:    
            print(a[l],end=" ")
            l+=1    
for j in range(len(x)):
    if j==len(x)-1:
       print(x[j])
    else:    
       print(x[j],end=" ")


Measured memory_bytes: 6256
import java.util.Scanner;

public class Main {

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

		int count5 = 0;
		int count7 = 0;
		for (int i = 0; i < 3; i++) {
			int n = sc.nextInt();
			if (n == 5)
				count5++;
			if (n == 7)
				count7++;
		}
		sc.close();

		if (count5 == 2 && count7 == 1) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}

	}

}


Measured memory_bytes: 21328
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
  ll N,M;
  cin>>N>>M;
  vector<vector<ll>>G(N);
  vector<ll>H(N);
  for(ll i=0;i<N;i++)cin>>H[i];
  vector<pair<ll,ll>>pr(M);
  for(ll i=0;i<M;i++){
    ll a,b;
    cin>>a>>b;
    a--,b--;
    pr[i]=make_pair(a,b);

  }
  sort(pr.begin(),pr.end());
  pr.erase(unique(pr.begin(),pr.end()),pr.end());
  
  for(ll i=0;i<pr.size();i++){
    ll a=pr[i].first;
    ll b=pr[i].second;
   // cout<<a<<" "<<b<<endl;
    G[a].push_back(H[b]);
    G[b].push_back(H[a]);
  }
  // for(ll i=0;i<N;i++){
  //   cout<<i<<" ";
  //   for(ll j=0;j<G[i].size();j++){
  //     cout<<G[i][j];
  //   }
  //   cout<<endl;
  // }

  ll ans=0;
  for(ll i=0;i<N;i++){
    ll flag=1;
    for(ll j=0;j<G[i].size();j++){
      if(H[i]<=G[i][j])flag=-1;
    }
    if(flag==1){
      ans++;
 //     cout<<i<<endl;
    }
  }
  cout<<ans<<endl;
}

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

//#define int long long
#define ll long long
#define all(v) (v).begin(), (v).end()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

signed main()
{   
    gearup;
    int n; cin >> n;
    string s,t; cin >> s >> t;
    int res = 2*n;
    //sの末尾とtの先頭がどのくらい重複するか
    for(int i=0;i<n;i++){
        bool is_res = true;
        for(int j=i;j<n;j++){
            if(s[j] != t[j-i])is_res = false;
        }
        if(is_res)res=min(res,n+i);
    }
    cout << res << endl;
}


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

using namespace std;

int main(){
    string s;
    cin >> s;

    int st = -1, en = -1;
    for(int i=0; i<s.size(); i++){
        if(st == -1 && s.at(i) == 'A') st = i;
        if(s.at(i) == 'Z') en = i;
    }


    cout << en-st +1 << endl;
}   

Measured memory_bytes: 640
N, K = gets.split.map(&:to_i)
P = gets.split.map(&:to_i)

sum = P[0...K].inject(:+)
max = sum
index = 0

(N - K).times do |i|
  sum = sum - P[i] + P[i + K]
  if sum > max
    max = sum
    index = i + 1
  end
end

ret = 0
K.times do |k|
  t = P[k + index]
  ret += (t + 1) / 2.to_f
end

puts ret


Measured memory_bytes: 14980
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
using tii = tuple<int, int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
//#define INF (ll)1E9
#define INF INT_MAX
#define EPS 1E-9
#define MOD 1000000007
#define PI 3.1415926535897932384

template <class T>ostream &operator<<(std::ostream &o, const vector<T> &v)
{
	rep(i, v.size()) {
		o << (i > 0 ? " " : "") << v[i];
	}
	return o;
}

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

//constexpr ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

int main() {
	int n,in;
	vi v;
	cin >> n;
	rep(i, n) {
		cin >> in;
		v.push_back(in);
	}
	cout << (*max_element(all(v)) - *min_element(all(v))) << endl;
}

Measured memory_bytes: 256
def readinput():
    n=int(input())
    l=list(map(int,input().split()))
    return n,l

def main(n,a):
    MOD=10**9+7
    hist=[0]*61
    bs=[]
    for i in range(n):
        # s=list(reversed(bin(a[i])[2:]))
        # for j in range(len(s)):
        #     if s[j]=='1':
        #         hist[j]+=1
        # bs.append(s)

        s=bin(a[i])[2:]
        for j in range(len(s)):
            if s[j]=='1':
                hist[len(s)-j-1]+=1
        # j=0
        # ai=a[i]
        # while ai>0:
        #     if ai&1==1:
        #         hist[j]+=1
        #     ai = ai >> 1
        #     j+=1


    #print(bs)
    #print(hist)
    sum=0
    # for i in range(n-1):
    #     s=bs[i]
    #     b=1
    #     for j in range(len(s)):
    #         if s[j]=='0':
    #             sum=(sum+hist[j]*b)%MOD
    #         else:
    #             sum=(sum+( n-i-hist[j] )*b)%MOD
    #             hist[j]-=1
    #         b*=2
    #     for j in range(len(s),61):
    #         sum=(sum+hist[j]*b)%MOD
    #         b*=2
    b=1
    for j in range(61):
        sum=(sum+( hist[j]*(n-hist[j])*b )%MOD )%MOD
        b*=2

    return sum

if __name__=='__main__':
    n,l=readinput()
    ans=main(n,l)
    print(ans)


Measured memory_bytes: 50696
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
	char s[105];
	cin >> s;
	if(s[0]=='L')
	{
		cout << "No";
		return 0;
	}
	int flag = 0; 
	for (int i=0;i<strlen(s);i++)
	{
		if(s[2*i+1]=='R')
		{
			cout << "No";
			return 0;
		}
	}
	for (int i=1;i<strlen(s);i++)
	{
		if(s[2*i]=='L')
		{
			cout << "No";
			return 0;
		}
	}
	flag = 1;
	if(flag)
	cout << "Yes";
	
	return 0;
}

Measured memory_bytes: 256
# 解説AC
N,M = map(int, input().split())
X = [int(i) for i in input().split()]
Y = [int(i) for i in input().split()]

MOD = 10 ** 9 + 7

def f(Z):
    ans = 0
    for k,z in enumerate(Z):
        ans = (ans + k * z - (len(Z) - k - 1) * z) % MOD
    return ans

print(f(X) * f(Y) % MOD)

Measured memory_bytes: 18624
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
  ll n,m;
  cin >> n >> m;
  vector<vector<ll>> a(m);
  rep(i,m){
    ll k;
    cin >> k;
    rep(j,k){
      ll x;
      cin >> x;
      x--;
      a.at(i).push_back(x);
    }
  }
  vector<ll> p(m);
  rep(i,m){
    cin >> p.at(i);
  }
  ll ans=0;
  for(int bit=0;bit<(1<<n);bit++){
    bool is=true;
    for(int i=0;i<m;i++){
      int l=a.at(i).size();
      int ct=0;
      for(int j=0;j<l;j++){
        if(bit&(1<<a.at(i).at(j))){
          ct++;
        }
      }
      if(ct%2!=p.at(i)){
        is=false;
      }
    }
    if(is){
      ans++;
    }
  }
  cout << ans;
}
  

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

#define ll long long

ll F(ll A, ll B){
    string bufA = to_string(A), bufB = to_string(B);
    return max(bufA.size(), bufB.size());
}

int main(){
    ll N;
    ll ans = to_string(N).size();
    cin >> N;
    for(ll i = 1; i <= sqrt(N); ++i){
        if(N % i == 0) ans = min(ans, F(i, N/i));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3788
#include<bits/stdc++.h>
using namespace std;
int t=1e6,a[200005];
int main()
{
	int i,k,n,p;
	scanf("%d %d",&k,&n);
	scanf("%d",&a[0]);
	for(i=1;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	sort(a,a+n);
	for(i=1;i<n;i++)
	{
		p=k-a[i]+a[i-1];
		if(p<t)
			t=p;			
	}
	p=a[n-1]-a[0];
	if(p<t)
		t=p;	
	printf("%d",t);
}

Measured memory_bytes: 1024
#include <vector>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <string.h>
using namespace std;

int main()
{
  int i;
  string s;  
  cin >> s;
  
  for (i = 0; i < s.size(); i++)
  {
    if ((i % 2 == 0 && s[i] == 'L') || (i % 2 == 1 && s[i] == 'R'))
    {
      cout << "No";
      return 0;
    }
  }
  
  cout << "Yes";

  return 0;  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define repr(i, n) for (int i = (int)n - 1; i >= 0; --i)
#define ALL(a) (a).begin(), (a).end()
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<ll, ll>;
const int dx[] = {0, -1, 0, 1};
const int dy[] = {1, 0, -1, 0};
const ll mod = 1e9 + 7;
const ll INF = 1e9;
const ll LINF = 1LL << 60;

struct edge {
  ll to, cost;
};

vector<vector<edge>> g;
vector<bool> visited;
vector<ll> dist;

void dfs(int s) {
  visited[s] = true;
  rep(i, g[s].size()) {
    if (visited[g[s][i].to]) continue;
    int to = g[s][i].to, cost = g[s][i].cost;
    dist[to] = dist[s] + cost;
    dfs(to);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //////////////////////////////////////
  ll n;
  cin >> n;
  g.resize(n);
  visited.resize(n);
  dist.resize(n);
  rep(i, n) {
    visited[i] = false;
    dist[i] = LINF;
  }
  rep(i, n - 1) {
    ll a, b, c;
    cin >> a >> b >> c;
    --a;
    --b;
    g[a].push_back(edge{b, c});
    g[b].push_back(edge{a, c});
  }
  ll q, k;
  cin >> q >> k;
  --k;
  dist[k] = 0;
  dfs(k);
  rep(i, q) {
    ll x, y, ans = 0;
    cin >> x >> y;
    --x;
    --y;
    cout << dist[x] + dist[y] << endl;
  }
  return 0;
}


Measured memory_bytes: 14336
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cmath>
#include <iomanip>
#include <string>

typedef long long ll;
using namespace std;
const int mod = 1000000007;

int main() {

    int N; cin >> N;
    vector< pair<string, int> > v(N);
    string s; int t;
    for (int i = 0; i < N; i++) {
        cin >> s >> t;
        v[i] = make_pair(s, t);
    }
    cin >> s;
    int ans = 0;
    int isfind = false;
    for (int i = 0; i < N; i++) {
        if (isfind)
            ans += v[i].second;
        else 
            if (v[i].first == s)
                isfind = true;
    }
    cout << ans << '\n';


}


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

class Solve {
private:
	std::string input;
	using Set = std::set<int>;
	using vs = std::vector<Set>;
	using vvs = std::vector<vs>;

	Set calcFormula(int& s_i)
	{
		vs expressions;
		std::vector<char> operators;
		expressions.push_back(calcExpression(s_i));
		while (s_i < (int)input.size() && input[s_i] != ')')
		{
			operators.push_back(input[s_i]);
			s_i++;
			expressions.push_back(calcExpression(s_i));
		}

		vvs dp(expressions.size(), vs(expressions.size() + 1));
		for (int i{}; i < (int)expressions.size(); i++)
			dp[i][i + 1] = std::move(expressions[i]);
		for (int width{2}; width <= (int)expressions.size(); width++)
			for (int left{}; left + width <= (int)expressions.size(); left++)
			{
				int right{left + width};
				for (int mid{left + 1}; mid < right; mid++)
					for (auto& lhs: dp[left][mid])
						for (auto& rhs: dp[mid][right])
							if (operators[mid - 1] != '/' || rhs != 0)
								dp[left][right].insert(calcOperation(lhs, rhs, operators[mid - 1]));
			}
		return std::move(dp[0][expressions.size()]);
	}

	Set calcExpression(int& s_i)
	{
		Set ret;
		if (input[s_i] == '(')
		{
			s_i++;
			ret = calcFormula(s_i);
			s_i++;
		}
		else
			ret.insert(calcNum(s_i));
		return std::move(ret);
	}

	int calcNum(int& s_i)
	{
		int ret{};
		while (s_i < (int)input.size() && isdigit(input[s_i]))
		{
			ret = 10 * ret + input[s_i] - '0';
			s_i++;
		}
		return ret;
	}

	int calcOperation(int a, int b, char ope)
	{
		if (ope == '+') return a + b;
		if (ope == '-') return a - b;
		if (ope == '*') return a * b;
		if (ope == '/') return a / b;
	}

public:
	bool is_last_query{};
	Solve()
	{
		std::cin >> input;
		if (input == "#")
		{
			is_last_query = true;
			return;
		}
		int s_i{};
		printf("%d\n", calcFormula(s_i).size());
	}
};

int main()
{
	while (!Solve().is_last_query);

	return 0;
}


Measured memory_bytes: 3312
import sys

def solve():
    input = sys.stdin.readline
    N = list(input().strip("\n"))
    DP = [[0, 0] for _ in range(len(N))]
    DP[0][0] = int(N[0])
    DP[0][1] = int(N[0]) - 1
    for i in range(1, len(N)):
        DP[i][0] = DP[i-1][0] + int(N[i])
        DP[i][1] = DP[i-1][1] + 9
        if N[i] != "0": DP[i][1] = max(DP[i][1], DP[i-1][0] + int(N[i]) - 1)
    
    print(max(DP[-1]))
    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 3064
//ModSum

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define irep(i,a) for(auto i = a.begin(); i != a.end(); ++i)
#define nvarep(n,a) int n;cin>>n;vector<int>a(n);rep(i,0,n)cin>>a[i]
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a/__gcd(a, b)*b)
#define range(a) (a).begin(),(a).end() 
#define pb push_back
#define mp make_pair
#define nnn "\n"
#define spa " "
#define cout15(a) printf("%.15f\n",a)
template<class T>inline bool chmin(T& a,T b,bool f){
if(f==1){if(a>b){a=b;return true;}return false;}
else if(f==0){if(a<b){a=b;return true;}return false;}return false;}
typedef pair<int,string> p;
const int inf = 2147483647;//2*10^9
const ll INF = 9223372036854775807;//9*10^18

int main (){
    int n;cin>>n;
    ll ans = 0;
    rep(i,1,n){
        ans += i;
    }
    cout<< ans << nnn;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main() {
	int ans[11], an, n,sai[11],sai1[11];
	string a;
	an = 0;
	while (1) {
		cin >> n;
		if (n == 0) {
			goto a;
		}
		an = an + 1;
		ans[an] = 0;
		for (int i = 1; i <= 6; i++) {
			sai[i] = i;
		}
		for (int i = 1; i <= n; i++) {
			cin >> a;
			for (int z = 1; z <= 6; z++) {
				sai1[z] = sai[z];
			}
			if (a == "North") {
				sai[1] = sai1[2];
				sai[2] = sai1[6];
				sai[6] = sai1[5];
				sai[5] = sai1[1];
			}
			if (a == "East") {
				sai[1] = sai1[4];
				sai[3] = sai1[1];
				sai[6] = sai1[3];
				sai[4] = sai1[6];
			}
			if (a == "West") {
				sai[1] = sai1[3];
				sai[3] = sai1[6];
				sai[6] = sai1[4];
				sai[4] = sai1[1];
			}
			if (a == "South") {
				sai[1] = sai1[5];
				sai[2] = sai1[1];
				sai[6] = sai1[2];
				sai[5] = sai1[6];
			}
			if (a == "Right") {
				sai[2] = sai1[3];
				sai[3] = sai1[5];
				sai[5] = sai1[4];
				sai[4] = sai1[2];
			}
			if (a == "Left") {
				sai[2] = sai1[4];
				sai[3] = sai1[2];
				sai[4] = sai1[5];
				sai[5] = sai1[3];
			}
			ans[an] = ans[an] + sai[1];
		}
	}
a:;
	for (int i = 1; i <= an; i++) {
		cout << ans[i]+1 << endl;
	}
}


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

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = ReadString();
            switch (s)
            {
                case "Sunny":
                    Console.WriteLine("Cloudy");
                    break;
                case "Cloudy":
                    Console.WriteLine("Rainy");
                    break;
                case "Rainy":
                    Console.WriteLine("Sunny");
                    break;
                default:
                    break;
            }
        }

        public static string ReadString()
        {
            return Console.ReadLine();
        }

        public string[] ReadStringArray()
        {
            return ReadString().Split(' ');
        }

        public static int ReadInt()
        {
            return int.Parse(ReadString());
        }
    }
}


Measured memory_bytes: 11092
n, a, b = gets.strip.split.map(&:to_i)

# 各桁の和を求める
def digit_sum(n)
    sum = 0
    while n > 0 do
        sum += n % 10
        n /= 10
    end
    sum
end

answer = (1..n)
        .map { |i| [i, digit_sum(i)] }
        .select { |d| a <= d[1] && d[1] <= b }
        .inject(0) { |sum, d| sum + d[0] }

puts answer

Measured memory_bytes: 2172
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = int(A); I < int(B); ++I)
#define FORR(I,A,B) for(ll I = int((B)-1); I >= int(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;
 

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

	string s;
	cin >> s;
	ll ans=0,c=0;
	FOR(i,0,s.size()){
		if(s[i]=='A'||s[i]=='C'||s[i]=='G'||s[i]=='T'){
			c++;
			ans=max(ans,c);
		}else{
			c=0;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
use std::io;

fn main() {
	let mut buf = String::new();
	io::stdin().read_line(&mut buf).expect("");
	let mut s = buf.trim().chars();
	
	let mut buf = String::new();
	io::stdin().read_line(&mut buf).expect("");
	let mut t = buf.trim().chars();
	let mut cnt = 0;
	for n in 0..3 {
		if s.next().unwrap() == t.next().unwrap() {
			cnt = cnt + 1;
		}
	}
	println!("{}", cnt);
}

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

int main() {

    string s,t;

    cin >> s >> t;

    priority_queue<string,vector<string>,greater<string> > q;

    /*

    for(int i=s.size()-1; i - static_cast<int>(t.size()) >= 0;i--){

        bool flag = true;

        for(int j=0;j<t.size();j++){
            if(s[i-j] != t[t.size()-1-j] && s[i-j] != '?'){
                flag = false;
                break;
            }
        }

        if(flag){

            for(int j=0; j<s.size(); j++){
                if(s[j] == '?'){
                    s[j] = 'a';
                }
            }

            for(int j=0;j<t.size();j++){
                s[i-j] = t[t.size()-1-j];
            }

            q.push(s);

        }

    }*/



    for(int i=0; i + t.size() <= s.size();i++){

        bool flag = true;

        for(int j=0;j<t.size();j++){
            if(s[i+j] != t[j] && s[i+j] != '?'){
                flag = false;
                break;
            }
        }

        if(flag){

            string ans = s;

            for(int j=0; j<ans.size(); j++){
                if(ans[j] == '?'){
                    ans[j] = 'a';
                }
            }

            for(int j=0;j<t.size();j++){
                ans[i+j] = t[j];
            }
            q.push(ans);
        }

    }



    if(q.empty()) {
        cout << "UNRESTORABLE" << endl;
    }
    else{
        cout << q.top() << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int h,w,a,b;
  cin>>h>>w>>a>>b;
  vector<string> ans(h,string(w,'#'));

  for(Int i=0;i<h;i++){
    for(Int j=0;j<w;j++){
      Int x=(i<b)^(j<a);
      ans[i][j]='0'+x;
    }
  }

  for(Int i=0;i<h;i++) cout<<ans[i]<<endl;
  return 0;
}


Measured memory_bytes: 2304
import java.util.*;
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");
  }
}

Measured memory_bytes: 26332
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
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 ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main(void){
    ll x;
    cin >> x;
    x--;
    ll s = 0, d = 1;
    while (26 * (s + 1) <= x){
        s = 26 * (s + 1);
        d++;
    }
    x -= s;
    string ans(d, ' ');
    REP(i,d){
        ans[d - 1 - i] = 'a' + (x % 26);
        x /= 26;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3628
S = input()
Q = [input() for i in range(int(input()))]
rev = 0
l,r = -1,1
res ={0:S}
for q in Q:
  if q == "1":
    rev = (rev+1)%2
  else:
    t,f,c = q.split()
    if int(f) + rev == 2 :
      res[r] = c
      r += 1
    else:
      res[l] = c
      l -= 1

if rev == 0:
  for i in range(l+1,r):
    print(res[i],end="")
else:
  for i in range(r-1,l,-1):
    print("".join(list(reversed(res[i]))),end="")

Measured memory_bytes: 122328
s=input()
t=input()
sl=len(s)
tl=len(t)
dp=[[0]*(sl+1) for _ in range(tl+1)]
for i in range(1,tl+1):
  for j in range(1,sl+1):
    if(t[i-1]==s[j-1]):
      dp[i][j]=dp[i-1][j-1]+1
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])
#print(dp[-1][-1])
i=tl
j=sl
ans=[]
while i>0 and j>0:
  if(t[i-1]==s[j-1]):
    ans.append(t[i-1])
    i=i-1
    j=j-1
  else:
    if(dp[i-1][j]+1>dp[i][j-1]):
      i=i-1
    else:
      j=j-1
#print(ans)
ans.reverse()
print(''.join(ans))

Measured memory_bytes: 144692
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

vector<bool> seen;
vector<int> point;
void dfs(const Graph &G, int v) {
    seen[v] = true;
    
    for (auto next_v : G[v]) {
        if (seen[next_v]) continue;
        point[next_v] += point[v];
        dfs(G, next_v);
    }
}

int main() {
    int n, q;
    cin >> n >> q;
    Graph G(n);
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    point.assign(n, 0);
    for (int j = 0; j < q; ++j) {
        int a, b;
        cin >> a >> b;
        --a;
        point[a] += b;
    }
    seen.assign(n, false);
    dfs(G, 0);
    for (int k : point) cout << k << " ";
    cout << endl;
}


Measured memory_bytes: 23552
def get_map():
  map = []
  while True:
    try:
      tmp = list(raw_input())
      if len(tmp) != 12: break
      map.append(tmp)
    except:
      break
  return map

def remove_island(x, y, map):
  map[x][y] = 0
  move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
  for i, j in move:
    if 0 <= x + i <= 11 and 0 <= y + j <= 11 and map[x + i][y + j] == '1':
      map = remove_island(x + i, y + j, map)
  return map[:]

while True:
  map = get_map()
  if len(map) != 12: break

  count = 0
  for x in range(12):
    for y in range(12):
      if map[x][y] == '1':
        count += 1
        map = remove_island(x, y, map)
  print count

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

using ll = long long;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n;
  cin >> n;
  
  vector<ll> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a.at(i);
    if (i) a.at(i) += a.at(i - 1);
  }
  
  map<ll, ll> mp;
  mp[0]++;
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    ans += mp[a.at(i)];
    mp[a.at(i)]++;
  }
  
  cout << ans << '\n';
}

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

#define FOR(i,b,e) for(int i=(b); i <= (e); ++i)
#define FORD(i,b,e) for(int i=(b); i >= (e); --i)
#define SIZE(c) (int) (c).size()
#define FORE(i,c) FOR(i,0,SIZE(c)-1)
#define FORDE(i,c) FORD(i,SIZE(c)-1,0)

#define pb push_back
#define mp make_pair
#define st first
#define nd second


using namespace std;

typedef long long ll;
typedef pair <int,int> pii;
typedef pair <ll,ll> pll;

typedef vector <int> VI;
typedef vector <bool> VB;
typedef vector <pii> VP;
typedef vector <ll> VL;
typedef vector <pll> VPL;

typedef vector <VI> VVI;
typedef vector <VL> VVL;
typedef vector <VB> VVB;
typedef vector <VP> VVP;

const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000000000000001LL;


ll expo(ll a, ll n, ll mod) {
    ll ans = 1;

    while (n) {
        if (n & 1LL) ans = (ans * a) % mod;

        n >>= 1;
        a = (a * a) % mod;
    }

    return ans;
}

ll revMod(ll a, ll mod) {
    return expo(a, mod - 2, mod);
}

const int N = 100004;

ll fact[N], revFact[N];

void pre() {
    fact[0] = revFact[0] = 1;
    FOR(i,1,N-1) {
        fact[i] = (i * fact[i-1]) % MOD;
        revFact[i] = revMod(fact[i], MOD);
    }
}

ll binom(int n, int m) {
    if (m > n) return 0;

    ll res = (fact[n] * revFact[n-m]) % MOD;
    res = (res * revFact[m]) % MOD;
    
    return res;
}

/*************************************************************************/

int main() {
    ios_base::sync_with_stdio(0);
    pre();
    
    int n;
    cin >> n;
    
    VI cnt(n+1,0), vec(n+1);
    int rep = -1;
    
    FOR(i,0,n) {
        int val;
        cin >> val;
        
        if (cnt[val]) rep = val;
        cnt[val]++;
        
        vec[i] = val;
    }
    
    int st = find(vec.begin(), vec.end(), rep) - vec.begin();
    int nd = find(vec.begin() + st + 1, vec.end(), rep) - vec.begin();
    int rest = (n + 1) - (nd - st + 1);
    
    FOR(k,1,n+1) {
        ll ans = binom(n+1, k) + MOD - binom(rest, k-1);
        if (ans >= MOD) ans -= MOD;
        
        cout << ans << '\n';
    }

    return 0;
}

/*************************************************************************/


Measured memory_bytes: 3584
import java.util.Arrays;

public class Main {
    private static java.util.Scanner scanner = new java.util.Scanner(System.in);

    public static void main(String[] args) {
        int n = scanner.nextInt(), k = scanner.nextInt();
        int[] h = new int[n], dp = new int[n];
        Arrays.fill(dp, 1, n, Integer.MAX_VALUE);
        for (int i = 0; i < n; i++) {
            h[i] = scanner.nextInt();
            for (int j = 1; j <= k; j++)
                if (i >= j)
                    dp[i] = Math.min(dp[i], dp[i - j] + Math.abs(h[i - j] - h[i]));
        }
        System.out.println(dp[n - 1]);
    }
}

Measured memory_bytes: 58400
//????????????????????¢?????????????????°???????????????
#include <stdio.h>
int main(void)
{
	for(;;)
	{
		int n,a,b,c,d,e;
		scanf("%d",&a);
		if(a==0)
		break;
		d=a;
		e=a;
		for(b=0;b<a;b++)
		{
			scanf("%d",&c);
			if(c==0)
			d--;
			if(c<=1)
			e--;
		}
		if(e==0)
		printf("NA\n");
		else
		printf("%d\n",d+1);
	}
	return 0;
}

Measured memory_bytes: 2724
a = int(input())
b = int(input())
c = int(input())
ammount = int(input())


count = 0
for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      if 500*i + 100*j + 50*k == ammount:
        count += 1
  
print(count)

Measured memory_bytes: 3060
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()

typedef long long lint;

using namespace std;

int main(){
  int N,K;
  cin>>N>>K;
  map<char,lint> S;
  cin>>S['s']>>S['p']>>S['r'];
  string T;
  cin>>T;
  lint ans=0;
  REP(k,K){
    bool won=true;
    lint temp=S[T[k]];
    for(int i=k+K;i<N;i+=K){
      if(won and T[i]==T[i-K])won=false;
      else {
        won=true;
        temp+=S[T[i]];
      }
    }
    ans+=temp;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 512
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
f = int(input())

e = max(e,f)
t = min(a,b)
t = min(c,t)
t = min(d,t)

print(a+b+c+d-t+e)


Measured memory_bytes: 5588
def find_prime_factor(num):
    if num & 1 == 0:
        return 2
    for i in range(3, int(num ** (1 / 2)) + 1):
        if num % i == 0:
            return i
    return num


def prime_factorization(num):
    subtract = num
    result = []
    while subtract > 1:
        factor = find_prime_factor(subtract)
        result.append(factor)
        subtract //= factor
    return result


n = int(input())

# prime and prime's power.
power = {}
for i in range(1, n + 1):
    for prime in prime_factorization(i):
        if prime in power:
            power[prime] += 1
        else:
            power[prime] = 1

count75 = sum(1 for count in power.values() if count >= 74)
count25 = sum(1 for count in power.values() if count >= 24)
count15 = sum(1 for count in power.values() if count >= 14)
count5 = sum(1 for count in power.values() if count >= 4)
count3 = sum(1 for count in power.values() if count >= 2)

ans = count75 \
      + count25 * (count3 - 1) \
      + count15 * (count5 - 1) \
      + (count5 * (count5 - 1) * (count3 - 2)) // 2

print(ans)


Measured memory_bytes: 3188
N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
def getnum(P):
  n = 0
  l = list(range(N))
  for i in range(N):
    n *= (N-i)
    p = P[i]
    n += l[p-1]
    for j in range(p, N):
      l[j] -= 1
  return n
#print(getnum(P))
#print(getnum(Q))
r = abs(getnum(P)-getnum(Q))
print(r)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template < typename T > string tost( const T& n ) { ostringstream stm; stm << n; return stm.str();}
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 (a > b) { a = b; return 1;} return 0;}
int const INF = 1001001001;


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

string S;
cin >> S;

if(S == "hi" || S == "hihi" || S == "hihihi" || S == "hihihihi" || S == "hihihihihi") cout << "Yes" << endl;
else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define NUM 1000000007
#define MAX 100001
#define INF LLONG_MAX
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n,tmp;
    cin>>n;
    vector<ll> v;
    for(int i=0;i<n;i++){
        cin>>tmp;
        v.pb(tmp);
    }
    set<set<ll>> st;
    set<ll> tmp1;
    ll ans = 0;
    for(int i=0;i<n-2;i++){
        for(int j=i+1;j<n-1;j++){
            for(int k=j+1;k<n;k++){
                if(v[i]!=v[j] && v[j]!=v[k] && v[i]!=v[k]){
                    if(v[i]+v[j]>v[k] && v[i]+v[k]>v[j] && v[j]+v[k]>v[i]){
                        tmp1.insert(i);
                        tmp1.insert(j);
                        tmp1.insert(k);
                        st.insert(tmp1);
                        tmp1.clear();
                    }
                }
            }
        }
    }
    cout<<st.size()<<endl;
    return 0;
}


Measured memory_bytes: 41360
import java.util.Scanner;
class Main{
 public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
int K=sc.nextInt();
int X=sc.nextInt();
int Y=sc.nextInt();
System.out.println(N<=K ? N*X :K*X+(N-K)*Y);
 }
  }


Measured memory_bytes: 22612