akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <queue>

#define CHECK_IMPL1(cond)                \
    if (!(cond)) {                       \
      DEBUG("expected cond: " << #cond); \
      assert(cond);                      \
    }

#define CHECK_IMPL2(cond, message)                                              \
    if (!(cond)) {                                                              \
      DEBUG("expected cond: " << #cond << " failed with message: " << message); \
      assert(cond);                                                             \
    }

#define CHECK_IMPL(_1, _2, NAME, ...) NAME
#define CHECK(...) CHECK_IMPL(__VA_ARGS__, CHECK_IMPL2, CHECK_IMPL1, CHECK_IMPL0)(__VA_ARGS__)

#ifdef __APPLE__
#define DEBUG(message) std::cerr << message << std::endl;
#else
#define DEBUG(message)
#endif

void solve() {
  int n;
  std::cin >> n;

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

  bool pairwise = true;
  std::unordered_map<int, int> primes;
  for (int i = 0; i < n; ++i) {
    auto x = a[i];
    for (int64_t i = 2; i * i <= x; ++i) {
      bool any = false;
      while (x % i == 0) {
        any = true;
        x /= i;
      }
      if (any) {
        ++primes[i];
        if (primes[i] > 1) {
          pairwise = false;
        }
      }
    }
    if (x > 1) {
      ++primes[x];
      if (primes[x] > 1) {
        pairwise = false;
      }
    }
  }

  auto gcd = a[0];
  for (int i = 1; i < n; ++i) {
    gcd = std::gcd(gcd, a[i]);
  }
  bool setwise = gcd == 1;

  if (pairwise) {
    std::cout << "pairwise coprime" << std::endl;
  } else if (setwise) {
    std::cout << "setwise coprime" << std::endl;
  } else {
    std::cout << "not coprime" << std::endl;
  }
}

int main() {
#ifdef __APPLE__
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
#endif
  int t = 1;
  //std::cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}


Measured memory_bytes: 10356
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

using int64 = long long;

#define all(_) begin(_), end(_)
#define rall(_) rbegin(_), rend(_)

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

  int64 x, k, d; cin >> x >> k >> d;
  if (x < 0) x = -x;

  if (k < x / d) {
    cout << x - k * d << endl;
  } else {
    int64 res = k - x / d;
    int64 p = x % d;
    if (res & 1) {
      cout << d - p << endl;
    } else {
      cout << p << endl;
    }
  }

  return 0;
}


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

long long memo[100] = {0}, n;

int main() {
  memo[0] = 2;
  memo[1] = 1;
  for(int i = 2; i < 100; ++i)
    memo[i] = memo[i - 1] + memo[i - 2];
  cin >> n;

  cout << memo[n] << endl;
  return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();

		int h = b-a;

		int sum = 0;

		for(int i = 1; i < h; i++) {
			sum += i;
		}


		System.out.println(sum - a);


	}

}


Measured memory_bytes: 21844
n=int(input())
x=[0]*n
y=[0]*n
for i in range(n):
    X,Y=map(int, input().split())
    x[i]=X
    y[i]=Y

che_x=[0]*n
che_y=[0]*n

for i in range(n):
    che_x[i]=x[i]-y[i]
    che_y[i]=x[i]+y[i]

ans=max(max(che_x)-min(che_x),max(che_y)-min(che_y))

print(ans)

Measured memory_bytes: 80996
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
inline int read()
{
	int x=0,w=1;char f=getchar();
	while((f<'0' || f>'9') && f!='-')f=getchar();
	if(f=='-'){w=-1;f=getchar();}
	while(f>='0' && f<='9') {x=x*10+f-'0';f=getchar();}
	return x*w;
}
int n,cnt;
int main()
{
	n=read();
	int t=1000;
	while(n)
	{
		int a=n/t;
		if(a==2) cnt++;
		n=n%t;
		t/=10;
	}
	printf("%d\n",cnt);
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){

  int n, i, z;

  for(i = 0;i < 50;i++){ 

    scanf("%d", &n);

    if(n == 0)
      break;

    else{

      z = 0;

      while(n != 1){

	if(n % 2 == 0){
	
	  n = n / 2;
	  z += 1;
	
	}else if(n % 2 == 1){
	
	  n = n * 3 + 1;
	  z += 1;
	
	}

      }

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

    }

  }


    return 0;

}

Measured memory_bytes: 600
#define _USE_MATH_DEFINES
#include <iostream>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <set>
#include <array>
#include <stdio.h>
#include <string.h>
#include <random>
using ll = long long;
using ull = unsigned long long;
using namespace std;
#define int long long
#define CONTAINS_VEC(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define ARY_REVERSE(v,a) (reverse((v), (v)+(a)))
#define REP(i, n) for (int (i)=0; (i) < (n); (i)++)
#define REPE(i, n) for (int (i)=0; (i) <= (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()
#define CONTAINS_SET(m, a) (m).find((a)) != m.end()
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }






signed main()
{
	int a, b;
	cin >> a >> b;
	cout << ((a * b % 2 == 0) ? "Even" : "Odd") << endl;
}



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

int n,k;
int a[8000];
int dp[8000];
const int INF = 100000;

int main(){
  cin >> n >> k;
  rep(i,n)cin >> a[i];

  int maxlen = 0;
  for(int i=0;i<n;i++){
    if(a[i] > i+1){
      fill(dp,dp+n,INF);
      for(int j=i;j<a[i];j++){
	if(a[j]>=a[i])*lower_bound(dp,dp+n,a[j]) = a[j];
      }
      maxlen = max(maxlen,(int)(lower_bound(dp,dp+n,INF)-dp));
    }
  }
  
  cout << maxlen+min(n/2-maxlen,k) << endl;
}

Measured memory_bytes: 1224
#include<iostream>
#include<math.h>
#include<vector>
#include<array>
#include<algorithm>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vector<ll>> mat;
typedef pair<int,int> P;
ll mod=pow(10,9)+7;
ll INF=pow(10,18);

int main(){
    int N; scanf("%d",&N);
    vec A(N);
    for(int i=0;i<N;i++) scanf("%lld",&A[i]);
    vec S(N+1),T(N+1); S[0]=T[0]=0;
    for(int i=1;i<=N;i++){
        S[i]=S[i-1]+A[i-1];
        T[i]=T[i-1]+A[N-i];
    }
    ll ans=INF;
    ll E[2],F[2],G[2],H[2];
    for(int m=2;m<N-1;m++){
        int l=distance(S.begin(),lower_bound(S.begin(),S.end(),(S[m]+1)/2));
        E[0]=min(S[l],S[m]-S[l]);E[1]=min(S[l-1],S[m]-S[l-1]);
        F[0]=max(S[l],S[m]-S[l]);F[1]=max(S[l-1],S[m]-S[l-1]);
        int r=distance(T.begin(),lower_bound(T.begin(),T.end(),(T[N-m]+1)/2));
        G[0]=min(T[r],T[N-m]-T[r]);G[1]=min(T[r-1],T[N-m]-T[r-1]);
        H[0]=max(T[r],T[N-m]-T[r]);H[1]=max(T[r-1],T[N-m]-T[r-1]);
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                ans=min(ans,max(F[i],H[j])-min(E[i],G[j]));
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 4992
s = gets.chomp

ans = s.length - 1

("a".."z").each do |c|
  count = 0
  t = s.chars

  until t.uniq.count == 1
    (t.length - 1).times do |i|
      t[i] = [t[i], t[i + 1]].include?(c) ? c : t[i]
    end

    count += 1
    t.pop
  end

  ans = count if count <= ans
end

puts ans


Measured memory_bytes: 1788
/*
 *  Created on: 3 / 5 / 2020
 *  Author:     Eslam Waheed
 */
#include <bits/stdc++.h>
//#include <bits/BIGINT.h>
//#include <bits/Int128.h>
using namespace std;

//#define _CRT_SECURE_NO_WARNINGS
//#define __USE_MINGW_ANSI_STDIO
#define Eslam__Waheed ios_base::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);

#define ll   long long
#define ull  unsigned ll
#define dd   double
#define ld   long dd
#define ss   string

#define pb      push_back
#define all(c)  c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define stp(n)  cout << fixed << setprecision(n);
#define iq(v)   v.resize(unique(v.begin(),v.end())-v.begin())
#define sz(s)   (ll)(s.size())
#define endl    '\n'

#define loop(i,m,n)  for(ll i=m;i<n;i++)

ll gcd(ll a, ll b) { return !b ? abs(a) : gcd(b, a % b); }
ll lcm(ll a, ll b) { return abs(a / gcd(a, b)) * b; }

//const ll mod = 1e9 + 7;
//__int128
/*
 you can ^_^ (•‿•)

( إن الله وملائكته يصلون على النبي يا أيها الذين آمنوا صلوا عليه وسلموا تسليما )
*/
int main()
{
    //stp(0)
    Eslam__Waheed
    ll x; cin >> x;
    vector<ll>v;
    v.push_back(0);
    for (int i = 1; i <= 1000; i++)
    {
        v.push_back(pow(i, 5));
    }
    /*for (auto it : v)
    {
        cout << it << endl;
    }*/
    for (int i = 0; i <= 1000; i++)
    {
        for (int u = 0; u <= 1000; u++)
        {
            if (v[i] - v[u] == x)
            {
                cout << i << ' ' << u ;
                return 0;
            }
        }
    }
    for (int i = 0; i <= 1000; i++)
    {
        for (int u = 0; u < 1000; u++)
        {
            if (v[i] - (-v[u]) == x)
            {
                cout << i << ' ' << -(u);
                return 0;
            }
        }
    }
}

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

int main() {
  int N, K;
  cin >> N >> K;
  int n_A = ceil(log(K) / log(2));
  n_A = min(N, n_A);
  int n_B = N - n_A;
  cout << pow(2, n_A) + n_B * K << endl;
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <iomanip>
#define rep(i,n) for (int i=0; i < (n); ++i)
using namespace std;
typedef long long ll;

int main(){
    int n, k=0;
    double sum=0;
    cin >> n;
    vector<int> p(n);
    rep(i, n) p[i] = i;
    int x[n];
    int y[n];
    rep(i, n) cin >> x[i] >> y[i];
    do{
        rep(i, n-1){
            sum += sqrt(pow((x[p[i]]-x[p[i+1]]), 2) + pow((y[p[i]]-y[p[i+1]]), 2));
        }
        k++;
    }while(next_permutation(p.begin(), p.end()));
    cout << setprecision(9) << sum/k << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(void){
  int a,b,c;
  cin>>a>>b>>c;
  if(a+b==c)cout<<"Yes"<<endl;
  else if(b+c==a)cout<<"Yes"<<endl;
  else if(c+a==b)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}

Measured memory_bytes: 256
// file creato da gio il 2020-04-12 16:32:10.576145

#include <bits/stdc++.h>
#define FAST 

#ifdef FAST
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#endif

#define S second
#define F first
#define PB push_back
using namespace std;

int main(){
	//freopen("output","w",stdout);
	//freopen("input","r",stdin);
#ifdef FAST
	ios::sync_with_stdio(0);
  	cin.tie(0);
#endif

	int n;
	cin >> n;
	int t=0,c=0;
	long sum=0;
	for(int i=1;i<=n;i++){
		t++;
		c++;
		if(t==3)
			t=0;
		if(c==5)
			c=0;
		if(c&&t)
			sum+=i;
	}
	cout <<sum;
}

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

using namespace std;

#define DUMP(x) std::cout << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP(i, k, n) for (int i = (k); i < (int)(n); ++ i)
#define ALL(r) r.begin(), r.end()
#define DUP(x, y) (((x) + (y) - 1) / (y))

using ll = std::int64_t;
using vint = std::vector<int>;
using vll = std::vector<ll>;
using pint = std::pair<int, int>;

constexpr std::int32_t INF = 1001001001;

void Main() {
    int n;
    cin >> n;
    vint h(n);
    rep(i, n) cin >> h[i];

    int ans = 0;
    while (true) {
        int l = -1;
        int r = -1;

        rep(i, n) {
            if (l == -1 && h[i] > 0) {
                l = i;
                continue;
            }
            if (l != -1 && h[i] <= 0) {
                r = i;
                break;
            }
        }
        if (l == -1)break;
        if (r == -1)r = n;
        REP(i, l, r) {
            --h[i];
        }
        ++ans;
    }
    cout << ans << endl;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}



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

int main(){

	// #ifndef ONLINE_JUDGE
 //    	freopen("input", "r", stdin);
 //    	freopen("output", "w", stdout);
	// #endif
	ios_base::sync_with_stdio(false);
   	cin.tie(NULL);

   	int n;
   	cin>>n;

   	int arr[n];

   	int maxval = INT_MIN;
   	int secmax = INT_MIN;

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

   		if(arr[i]>maxval){
   			secmax=maxval;
   			maxval=arr[i];
   		}
   		else if (arr[i]>secmax){
   			secmax=arr[i];
   		}
   	}

   	for(int i=0;i<n;i++){
   		if(arr[i]==maxval){
   			cout<<secmax<<endl;
   		}
   		else{
   			cout<<maxval<<endl;
   		}
   	}
}



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

int main() {
    int N;
    cin >> N;

    if ((N > 0 and N < 4) or N == 5 or N ==6 or N== 9 or N==10 or N==13 or N==17)
    {
        cout << "No";
    }
    else
    {
        cout << "Yes";
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <limits>
#include <cmath>
#include <iomanip>
#include <functional>
#include <random>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using ll = long long;

int main()
{
    // 整数の入力
    string S;
    cin >> S;
    if (S[0] == '7' || S[1] == '7' || S[2] == '7'){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
   return 0;
}

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


int n,r,c;
struct Point{
	int x,y,idx;
	int where(void)const{
		if(x==0)
			return 1;
		if(x==r)
			return 3;
		if(y==c)
			return 2;
		if(y==0)
			return 4;
		return 0;
	}
	bool operator<(const Point& rhs)const{
		if(where()!=rhs.where())
			return where()<rhs.where();
		if(where()==1)
			return y<rhs.y;
		if(where()==2)
			return x<rhs.x;
		if(where()==3)
			return y>rhs.y;
		return x>rhs.x;
	}
}p1,p2;
vector<Point> v;
stack<int> st;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>r>>c>>n;
	for(int i=1;i<=n;i++){
		cin>>p1.x>>p1.y>>p2.x>>p2.y;
		p1.idx=p2.idx=i;
		if(p1.where()&&p2.where()){
			v.emplace_back(p1);
			v.emplace_back(p2);
		}
	}
	sort(v.begin(),v.end());
	for(auto it:v){
		if(st.empty())
			st.push(it.idx);
		else if(it.idx==st.top())
			st.pop();
		else st.push(it.idx);
	}
	if(st.empty())
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;
}


Measured memory_bytes: 6004
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <cmath>
#include <ctime>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector< vector<int> > vvi;
typedef vector<ll> vl;
typedef vector< vector<ll> > vvl;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)
#define forv(i, v) forn(i, v.size())
#define all(v) v.begin(), v.end()
#define mp make_pair
#define pb push_back

int main() {
#ifdef NEREVAR_PROJECT
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int n, L;
    cin >> n >> L;
    vi a(n);
    forn(i, n) scanf("%d", &a[i]);
    vi ans;
    
    int k = -1;
    forn(i, n - 1) {
        if (a[i] + a[i + 1] >= L) {
            k = i;
            break;
        }
    }
    if (k == -1) {
        cout << "Impossible" << endl;
        return 0;
    }
    
    ans.pb(k + 1);
    for (int i = k + 2; i < n; i++) ans.pb(i);
    for (int i = k; i > 0; i--) ans.pb(i);
    reverse(all(ans));
    cout << "Possible" << endl;
    for (int p : ans) {
        printf("%d\n", p);
    }
    return 0;
}


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

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vint;
typedef vector<double> vdbl;
typedef vector<ll> vll;
typedef vector<string> vstr;
typedef vector<vector<int> > vvint;
typedef vector<pair<int, int> > vpii;
typedef vector<pair<ll, ll> > vpll;
typedef priority_queue<int, vector<int>, greater<int> > spqint; //小さい順に取り出し
typedef priority_queue<ll, vector<ll>, greater<ll> > spqll;     //小さい順に取り出し
typedef priority_queue<int, vector<int>, less<int> > bpqint;    //大きい順に取り出し
typedef priority_queue<ll, vector<ll>, less<ll> > bpqll;        //大きい順に取り出し

#define REP(i, n) for (int(i) = 0; (i) < (int)(n); i++)
#define FOR(i, a, b) for (int(i) = a; (i) < (int)b; i++)
#define IREP(i, v) for (auto i = v.begin(); i != v.end(); i++)
#define MOD 1000000007
#define NIL -1
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define PF push_front
#define TS to_string
#define BS binary_search
#define LB lower_bound
#define UB upper_bound
#define NP next_permutation
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) (ll) x.size()
#define SP(x) setprecision((ll)x)

const int INF = 1e9;
const ll LINF = 1e18;
const double EPS = 1e-9;
const double PI = M_PI;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } //最大公約数
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }     //最小公倍数

void yes()
{
    cout << "Yes" << endl;
}
void no()
{
    cout << "No" << endl;
}
//-----------------------------------------
const int MAX = 1000000 ;
long long fac[MAX], finv[MAX], inv[MAX] ;

void pre(){
    fac[0] = fac[1] = 1 ;
    finv[0] = finv[1] = 1 ;
    inv[1] = 1 ;
    for(int i=2;i<MAX;i++){
        fac[i] = fac[i-1]*i%MOD ;
        inv[i] = MOD - inv[MOD%i]*(MOD/i) %MOD ;
        finv[i] = finv[i-1]*inv[i]%MOD ;
    }
}

long long nCk(int n, int k){
    if(n<k){
        return 0 ;
    }
    if(n<0 || k<0){
        return 0 ;
    }
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD ;
}



//-----------------------------------------
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k ;
    cin >> n >> k ;
    pre() ;
    int op = n-k ;
    
    REP(i,k){
        cout << nCk(op+1,i+1)*nCk(k-1,i)%MOD <<endl ;
    }
    

    return 0;
}


Measured memory_bytes: 23808
#include <bits/stdc++.h>
#include <iostream>
#include <numeric>
#include <string>
#include <list>
#include <limits>
#include <type_traits>
#include <vector>

using namespace std;

int main(void) {

    int n ,temp = 0;

    cin >> n;
    
    std::map<int, int> pep;


    for (int i = 0; i < n - 1; i ++ ) {
        cin >> temp;
        pep[temp]++;
    }

     for(int i = 1; i <= n; i++  ){
         cout << pep[i];
         cout << endl;
    }

    
}

Measured memory_bytes: 12976
def main():
    n = int(input())
    a = [0] * n
    b = list(map(int, input().split()))
    a[0] = b[0]
    a[-1] = b[-1]
    for i in range(n-2):
        a[i+1] = min(b[i], b[i+1])
    return sum(a)

if __name__ == "__main__":
    print(main())

Measured memory_bytes: 3064
#include<stdio.h>
inline int getint(){
  int ret = 0,f = 1;
  char c = getchar();
  while(c<'0'||c>'9'){
    if(c=='-')f=-1;
    c = getchar();
  }
  while(c>='0'&&c<='9')
    ret=ret*10+c-'0',c=getchar();
  return ret*f;
}
int N,a,t,s=0;
int main(){
  N=getint();
  while(N--){
    a=getint();
    asm volatile(
      "bsf %0,%1\n\t"
      :"=r"(t)
      :"r"(a)
    );
    s+=t;
  }
  printf("%d\n",s);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

int main(){

    int N;cin>>N;
    LL a[N];REP(i,N)cin>>a[i];

    int cnt[3];
    fill_n(cnt,3,0);
    REP(i,N){
        if(a[i]%4==0)cnt[2]++;
        else if(a[i]%2==0)cnt[1]++;
        else cnt[0]++;
    }
    bool isPossible =true;

    if(cnt[1]==0){
        if(cnt[0]>cnt[2]+1)isPossible=false;
    }else{
        if(cnt[0]>cnt[2])isPossible=false;
    }

    if(isPossible)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include<unordered_map>
#include<algorithm>

/*
*▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
*    ▀▀       ▀▀▀▀▀▀    ▀     ▀▀▀▀▀▀      ▀    ▀
*   ▀  ▀      ▀         ▀     ▀            ▀  ▀
*  ▀    ▀     ▀ ▀ ▀     ▀     ▀ ▀ ▀         ▀
* ▀ ▀▀▀▀ ▀    ▀         ▀     ▀             ▀
*▀        ▀   ▀         ▀     ▀             ▀
*▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
*/
using namespace std;
void afify()
{
	ios::sync_with_stdio(0);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
//===============================================
#define ll long long
#define ld long double
#define mk make_pair
#define loop(i,intial,n)  for(int i=(intial);i<n;i++)
#define loopn(j,n,ends) for(int j=int(n-1);j>=ends;j--)
#define loopm(name)  for(auto it : name)
#define loopm2(name)  for(auto it2 : name)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define all(v) v.begin(),v.end()
#define PI (ld)(3.14159265358979323846)
//===============================================
#define SF(a) scanf("%d",&a)
#define SF2(a,b) scanf("%d %d",&a,&b)
#define SFLL(a) scanf("%lld",&a)
#define SFLL2(a,b) scanf("%lld %lld",&a,&b)
#define PF(a) printf("%d\n",a)
#define PFLL(a) printf("%lld\n",a)
//===============================================
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <ld> vld;
typedef vector <vi> vvi;
typedef vector <vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<vpii> vvpii;
typedef stringstream ss;
const double EPS = 1e-4;
const ll oo = (ll) 10e7 + 7;
const ll N = 1000018; 
const ll mod = 1073741824;
int dx[] = { -1, 0, 0, 1 };
int dy[] = { 0, -1, 1, 0 }; // 4 Direction*/
//int dx[]={1,1,0,-1,-1,-1,0,1};
//int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction*/
//freopen("largest.in", "r", stdin);
//freopen("output.txt", "w", stdout);
//ifstream ifs("input.txt");
//ofstream ofs("output.txt");

int main()
{
	afify();
	int n, m;
	cin >> n >> m;
	n--;
	m --;
	cout << n*m << endl;


	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#include <sstream>
#include <stack>
#include <time.h>
#include <vector>
#include <complex>
#include <map>
#include <set>
#include <iomanip>
#include <math.h>
#include <stdlib.h>
using namespace std;
long long a[200003],s[200006];
int main(){
  long long n;
  cin>>n;
  long long ans=0;
  for (long long i=1;i<=n;i++){
    long long x;
    cin>>x;
    s[i]=s[i-1]+x;
    a[i]=a[i-1]^x;
  }
  long long l=1;
  for (long long i=1;i<=n;i++){
  	for (;(s[i]-s[l-1])!=(a[i]^a[l-1]);l++);
  	ans+=i-l+1;
  }
  cout<<ans;
  return 0;
}

Measured memory_bytes: 3328
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>

using namespace std;

int main(){
   int A[3];
   cin >> A[0] >> A[1] >> A[2];
   sort(A,A+3);
   if(A[2] != A[0]){
      cout << "No"<<endl;
   }
   else{
      cout << "Yes"<< endl;
   }

   return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <complex>
#include <unordered_map>

using namespace std;
using i64 = int_fast64_t;
using u64 = uint_fast64_t;
using i32 = int_fast32_t;
using u32 = uint_fast32_t;

#define int i64

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

	unordered_map<int, int> cnt;

	int a;
	bool res = true;
	for(int i = 0; i < n; i++) {
		cin >> a;
		cnt[a] += 1;
		if(cnt[a] == 2) {
			res = false;
			break;
		}
	}

	if(res) cout << "YES" << endl;
	else cout << "NO" << endl;
	
	return 0;
}


Measured memory_bytes: 8520
#include <bits/stdc++.h>
using namespace std;
int main() {
  
  int n;
  cin >> n;
  
  vector<pair<int , int>> cont(n);
  
  for(int i = 0 ; i < n ; i++){ 
    cin >> cont.at(i).second;
    cin >> cont.at(i).first;
  }
  
  sort(cont.begin() , cont.end());
  
  int64_t sum = 0;
  bool jad = false;
  
  for(int i = 0 ; i < n ; i++){
    
    if(sum + cont.at(i).second > cont.at(i).first){
      break;
    }
    if(i == n-1){
      jad = true;
    }
    sum += cont.at(i).second;
  }
  
  if(jad){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 1920
import math  # noqa: F401
from typing import Dict, List, Optional, Tuple, Union  # noqa: F401


def main(N: int, A: List[int]):
    A = sorted(A, reverse=True)
    if A[-1] == 0:
        print(0)
        return
    ans = 1
    for a in A:
        ans *= a
        if ans > 10 ** 18:
            ans = -1
            break
    print(ans)


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    main(N, A)


Measured memory_bytes: 23708
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=2002020;
char l[N],r[N],s[N];
int main()
{
	scanf("%s",s+1); int len=strlen(s+1);
	int aq; cin>>aq; int topl=0,topr=0,rev=0;
	while(aq--){
		int op; cin>>op;
		if(op==1)rev^=1;
		else{
			int F; cin>>F; char c; cin>>c;
			F=(F-1)^rev;
			if(F)r[++topr]=c;
			else l[++topl]=c;
		}
	}
	if(rev){
		for(int i=topr;i>=1;i--)cout<<r[i];
		for(int i=len;i>=1;i--)cout<<s[i];
		for(int i=1;i<=topl;i++)cout<<l[i];
	} else{
		for(int i=topl;i>=1;i--)cout<<l[i];
		for(int i=1;i<=len;i++)cout<<s[i];
		for(int i=1;i<=topr;i++)cout<<r[i];
	}
	return 0;
}

Measured memory_bytes: 4044
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
typedef long long ll;
const int N = 1e5+10;


int main()
{
    ll m, k;
    cin>>m>>k;
    if((m == 1 && k == 1) || (k >= (1 << m))) cout<<"-1"<<endl;
    else if(m == 1 && k == 0) cout<<"0 0 1 1"<<endl;
    else
    {
        cout<<k;
        for(int i=0; i <(1<<m); i++)
            if(k != i)
                cout<<" "<<i;
        cout<<" "<<k;
        for(int i=(1<<m)-1; i>= 0; i--)
            if(k != i)
                cout<<" "<<i;
        cout<<endl;
    }
}


Measured memory_bytes: 1792
#include<stdio.h>
#include<stdlib.h>

int main(){
  int i,A[100],j,N,mini,temp,count=0,flag=0;
  scanf("%d",&N);
  if (N<1 || N>100){
    printf("N 1-100 ni shiro.\n");
    exit(1);
  }

  for (i=0;i<N;i++){
    scanf("%d",&A[i]);
  }

  for (i=0;i<=N-1;i++){
    mini = i;
    flag=0;
    for (j=i;j<=N-1;j++){
      if (A[j]<A[mini]){
        mini = j;
        flag=1;
      }
    }
    if(flag==1){
      temp=A[i];
      A[i]=A[mini];
      A[mini]=temp;
      count++;
    }
  }

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

Measured memory_bytes: 604
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <vector>

static const int IINF = 1 << 30;
static const long long LINF = 1LL << 60;
static const long long MOD = 1.0e+9 + 7;

template <typename T> std::vector<T> vectors(std::size_t n, T val) {
  return std::vector<T>(n, val);
}

template <typename T, typename... Args>
auto vectors(std::size_t n, Args... args) {
  return std::vector<decltype(vectors<T>(args...))>(n, vectors<T>(args...));
}

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

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

template <class T> inline void chadd(T &a, const T &b) {
  a += b, a %= MOD;
  // TODO minus case
}

template <class T>
std::ostream &operator<<(std::ostream &s, const std::vector<T> &v) {
  if (v.empty())
    return s;
  s << *v.begin();
  for (auto iter = v.begin() + 1; iter != v.end(); ++iter)
    if (std::is_fundamental<T>::value)
      s << " " << *iter;
    else
      s << std::endl << *iter;
  return s;
}

int main() {
  // Input
  long long A, B;
  std::cin >> A >> B;

  if (A == B)
    std::cout << 0 << std::endl;
  else if ((A + B) % 2 == 0)
    std::cout << (A + B) / 2 << std::endl;
  else
    std::cout << "IMPOSSIBLE" << std::endl;

  // Main

  // Output

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pi M_PI
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  int x,y,z;
  cin >> x >> y >> z;
  if((x*100+y*10+z)%4) pr("NO");
  else pr("YES");
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 892
#include <bits/stdc++.h>
#define rt "\n"
#define sp " "
#define test(n) cout << "test" << n << endl;
#define fixsp(n) fixed << setprecision(n)
#define defsp(n) defaultfloat << setprecision(n)
#define kyopro ios::sync_with_stdio(false);cin.tie(NULL)
#define MOD 1000000007
#define iikae auto&
#define zenbu(a) a.begin(), a.end()
#define rzenbu(a) a.rbegin(), a.rend()
#define rep(i, s, N) for(ll i{s}; i < N; i++)
#define rem(i, N, s) for(ll i{N}; i > s; i--)
using namespace std;using ll = long long;using ld = long double;using P = pair<ll,ll>;
template<typename T> T gcd(T a, T b){return b != 0 ? gcd(b, a % b) : a;}
template<typename T> struct UnionFind{vector<T> par;UnionFind(T n) : par(n, -1){}void init(T n){par.assign(n, -1);}T root(T x){if (par[x] < 0) return x;else return par[x] = root(par[x]);}bool issame(T x, T y){return root(x) == root(y);}bool merge(T x, T y){x = root(x); y = root(y);if(x == y) return false;if(par[x] > par[y]) swap(x, y);par[x] += par[y];par[y] = x;return true;}int size(int x) {return -par[root(x)];}};

/* ここからコード開始 */

int main(){
  kyopro;
  ll A, B, C;
  cin >> A >> B >> C;
  cout << min(B / A, C);
}

Measured memory_bytes: 256
// Best practice

#include<bits/stdc++.h>

#define int         long long
#define pb          push_back
#define pf          emplace_front
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()
#define pii 		pair<int,int>
#define psi 		pair<string,int>
#define vi 			vector<int>
#define vpii  		vector<pii>
#define vvi 		vector<vi>
#define sz(x)	    (int)(x).size()
#define x           first
#define y           second
#define endl        '\n'
#define tezz        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MOD         1000000007
#define hell        998244353
#define prec(n) 	fixed<<setprecision(n)
#define in(x) 		scanf("%d", &x)
#define echo(x)		printf("%d", x)
#define inf 		(int)(1e18)
#define ini(a, i) 	memset(a, i, sizeof(a))
#define output(x)   cout << (x ? "YES" : "NO")<<endl;
using namespace std;

#define debug(vec) cout<<(#vec)<<" : [ "; for (auto& i: vec) cout<<i<<" "; cout<< "]" << endl
#define debugp(vec) cout<<(#vec)<<" : [ "; for (auto& i: vec) cout<<"("<<i.x<<","<<i.y<<")"<<" "; cout<< "]" << endl
#define trace(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);cout << endl; }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << "[" << *it << ": " << a << "]\t";
    err(++it, args...);
}

// const int dx[4] = { -1, 1, 0, 0};
// const int dy[4] = {0, 0, -1, 1};
// int dX[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
// int dY[] = { -1, 0, 1, -1, 1, -1, 0, 1 };


// Code from Here -------------------------------------------------------------------------------

void solver(){
	int n,m,K,C=0,ans=0;
	cin >> n >> m >> K;
	vector<string> s(n);
	for(int i=0; i<n; i++){
		cin >> s[i];
		for(int j=0; j<m ;j++){
			if(s[i][j]=='#')C++;
		}
	}
	for(int i=0; i<(1<<n); i++){
		for(int j=0; j<(1<<m); j++){
			int c=0;
			for(int I=0; I<n; I++){
				for(int J=0; J<m; J++){
					if(i&(1<<I) || (j&(1<<J))){
						if(s[I][J]=='#')c++;
					}
				}
			}
			if(C-c==K){
				ans++;
			}
		}
	}
	cout << ans;
}

signed main() {
	tezz


	int t=1;
	// cin >> t;
	while(t--)solver();

	return 0;
}  


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

int main() {
    int w, h, x, y, r;
    cin >> w >> h >> x >> y >> r;
    if (0 <= x - r && x + r <= w && 0 <= y - r && y + r <= h) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 3096
use std::io;
use std::collections::HashSet;


fn main() {
    let mut values = HashSet::new();
    let n: i32 = get_line().parse().unwrap();

    for _ in 0..n {
        let a : i32 = get_line().parse().unwrap();
        if !values.contains(&a) {
            values.insert(a);
        }else{
            values.remove(&a);
        }
    }
    println!("{}", values.len());
}

fn get_line() -> String {
    let mut line = String::new();
    io::stdin().read_line(&mut line).unwrap();
    return String::from(line.trim())
}


Measured memory_bytes: 6396
import java.util.*;
import static java.lang.Math.*;

public class Main {

	class Point{
		double x, y;
		Point(double _x, double _y){ this.x = _x; this.y = _y; }
		Point(){ new Point(0,0); }
		double abs(){ return hypot(this.x,this.y); }
		Point rot(double th){ 
			return new Point(x*cos(th)-y*sin(th),x*sin(th) + y*cos(th));
		}
		Point rotAt(Point a, double th){
			Point t = this.sub(a);
			t = t.rot(th);
			return t.add(a);
		}
		Point sub(Point a){
			return new Point(this.x-a.x, this.y-a.y);
		}
		Point add(Point a){
			return new Point(this.x+a.x, this.y+a.y);
		}
		Point multi(double a){
			return new Point(a*this.x, a*this.y);
		}
		Point div(double a){
			return new Point(this.x/a, this.y/a);
		}
	}
	
	Point left, right;

	void run(){
		Scanner in = new Scanner(System.in);
		for(;;){
			int N = in.nextInt();
			double D = in.nextDouble();
			if(N==0 && D==0) return;
			left = new Point(-D,0);
			right = new Point(D,0);
			for(int i=0; i<N; i++){
				double  lv= in.nextDouble(),
						rv = in.nextDouble(),
						time = in.nextDouble();
				proc(lv*PI/180*time,rv*PI/180*time);
			}
			Point center = right.add(left).div(2.0);
			System.out.printf("%.7f\n%.7f\n",center.x+1e-9, center.y+1e-9);
		}
	}
	
	void proc(double lv, double rv){
		if(lv == rv){
			Point v = right.sub(left).rot(PI/2.0);
			v = v.multi(lv/v.abs());
			left = left.add(v);
			right = right.add(v);
			return ;
		}
		Point center = left.multi(-rv).add(right.multi(lv)).div(lv-rv);
		boolean leftIsNear = left.sub(center).abs() < right.sub(center).abs();
		if(lv!=0)left = left.rotAt(center, (lv*rv<0?-1:leftIsNear?1:-1)*lv/center.sub(left).abs());
		if(rv!=0)right = right.rotAt(center, (lv*rv<0?1:leftIsNear?1:-1)*rv/center.sub(right).abs());
		return;
	}

	public static void main(String args[]){
		new Main().run();
	}
}

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

const int maxn = 1e5+10;
struct Stu
{
	int rank;
	int id;
} stu[maxn];
int N;

bool cmp(Stu a, Stu b)
{
	return a.rank < b.rank;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for(int i = 0; i < N; ++i)
	{
		stu[i].id = i+1;
		cin >> stu[i].rank;
	}
	sort(stu, stu+N, cmp);
	cout << stu[0].id;
	for(int i = 1; i < N; ++i) cout << ' ' <<stu[i].id;
	cout << endl;
}

Measured memory_bytes: 1664
package main

import "fmt"

func main() {
	// Code for B - Theater
	var N int
	fmt.Scanf("%d", &N)

	var l, r int
	var ans int = 0
	for i := 0; i < N; i++ {
		fmt.Scanf("%d %d", &l, &r)
		ans += r - l + 1
	}

	fmt.Println(ans)
}


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

int main(){
	int n;
	string s;
	cin >> n ;
	cin >> s;
	
	
	int i;
	int r = 0,b = 0;
;	for(i=0;i<n;i++){
		if(s[i] == 'R') r++; 
		else b++;
	}
	if(r > b) cout << "Yes"<<endl;
	else cout << "No"<<endl;
	
	return 0; 
} 

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

using namespace std;

typedef long long LL;
#define N 600000

const LL mod=924844033;
LL n,x,y,fac[N],ifac[N],rev[N],a[N],b[N],head[N],tot,sz[N];
struct edge{LL v,nxt;}e[N];

void add(LL x,LL y){
	e[++tot].v=y; e[tot].nxt=head[x]; head[x]=tot;
}

void dfs(LL u,LL fa){
	sz[u]+=1;
	for (LL i=head[u],v;i;i=e[i].nxt)
		if ((v=e[i].v)!=fa){
			dfs(v,u);
			sz[u]+=sz[v];
		}
	if (fa){++a[sz[u]]; ++a[n-sz[u]];}
}

LL pw(LL x,LL k){
	if (k==0) return 1;
	LL tmp=pw(x*x%mod,k>>1);
	return k&1?tmp*x%mod:tmp;
}

LL inv(LL x){
	return x==1?1:(mod-mod/x)*inv(mod%x)%mod;
}

void ntt_init(LL &p){
	LL k=0; for (;1<<k<p;++k);
	p=1<<k; rev[0]=0;
	for (LL i=1;i<p;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
}

void ntt(LL f[],LL n){
	for (LL i=0;i<n;++i) if (i<rev[i]) swap(f[i],f[rev[i]]);
	for (LL i=0;1<<i<n;++i){
		LL t=1<<i,wn=pw(5,(mod-1)/t/2);
		for (LL j=0;j<n;j+=t<<1){
			LL *f1=f+j,*f2=f+j+t,w=1;
			for (LL k=0;k<t;++k){
				LL tmp=f2[k]*w%mod;
				f2[k]=(f1[k]-tmp+mod)%mod;
				f1[k]=(f1[k]+tmp)%mod;
				w=w*wn%mod;
			}
		}
	}
}

int main(){
	scanf("%lld",&n);
	fac[0]=1; for (LL i=1;i<=n;++i) fac[i]=fac[i-1]*i%mod;
	ifac[n]=inv(fac[n]); for (LL i=n-1;~i;--i) ifac[i]=ifac[i+1]*(i+1)%mod;
	for (LL i=1;i<n;++i){
		scanf("%lld%lld",&x,&y);
		add(x,y); add(y,x);
	}
	dfs(1,0);
	for (LL i=0;i<=n;++i){a[i]=a[i]*fac[i]%mod; b[i]=ifac[i];}
	for (LL i=0;i<=n/2;++i) swap(a[i],a[n-i]);
	LL p=n*2+1; ntt_init(p); ntt(a,p); ntt(b,p);
	for (LL i=0;i<p;++i) a[i]=a[i]*b[i]%mod;
	ntt(a,p); reverse(a+1,a+p);
	for (LL i=1,ii=inv(p);i<=n;++i){
		LL t=a[n-i]*ii%mod*ifac[i]%mod;
		b[i]=(n*fac[n]%mod*ifac[i]%mod*ifac[n-i]%mod-t+mod)%mod;
	}
	for (LL i=1;i<=n;++i) printf("%lld\n",b[i]);
	
	return 0;
}
			

Measured memory_bytes: 46976
#include <cstdio>
#include <algorithm>
using namespace std;

void chmin(int &a, int b) {
     a = min(a, b);
}

const int INF = 1 << 25;
int N, M, R;
int dl[210][210], ds[210][210], dist[1010][210], op[1010];

int main() {
    while(scanf("%d%d", &N, &M)) {
        if(N == M && M == 0) break;
        for(int i=0; i<N; i++) {
            fill(dl[i], dl[i] + N, INF);
            fill(ds[i], ds[i] + N, INF);
            dl[i][i] = ds[i][i] = 0;
        }

        for(int i=0; i<M; i++) {
            int x, y, t; char s;
            scanf(" %d%d%d %c", &x, &y, &t, &s);
            x--; y--;
            if(s == 'L') {
                chmin(dl[x][y], t);
                chmin(dl[y][x], t);
            }
            else {
                chmin(ds[x][y], t);
                chmin(ds[y][x], t);
            }
        }

        for(int k=0; k<N; k++) {
            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    chmin(dl[i][j], dl[i][k] + dl[k][j]);
                    chmin(ds[i][j], ds[i][k] + ds[k][j]);
                }
            }
        }

        scanf("%d", &R);
        for(int i=0; i<R; i++) {
            scanf("%d", &op[i]); op[i]--;
            fill(dist[i], dist[i] + N, INF);
        }

        dist[0][op[0]] = 0;
        for(int i=0; i<R-1; i++) {
            for(int j=0; j<N; j++) {
                if(dist[i][j] == INF) continue;
                int cur = op[i], nxt = op[i+1];

                // land only
                chmin(dist[i+1][j], dist[i][j] + dl[cur][nxt]);

                // land + sea
                for(int k=0; k<N; k++) {
                    chmin(dist[i+1][k], dist[i][j] + dl[cur][j] + ds[j][k] + dl[k][nxt]);
                }
            }
        }

        printf("%d\n", *min_element(dist[R-1], dist[R-1] + N));
    }
    return 0;
}


Measured memory_bytes: 3872
program contest
  implicit none

  integer :: n, i, j, p, q

  read(*,*) n
  
  q = 0

  do j = 1, n, 2
     p = 0
     do i = 1, j
        if(mod(j,i)==0) then
           p = p + 1
        end if
     end do
     if(p == 8) then
        q = q + 1
!        write(*,*) j
     end if
  end do

  write(*,*) q
  stop
end program contest


Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	
	void run() {
		FastScanner sc=new FastScanner();
		String str=sc.next();
		int Q=sc.nextInt();
		ArrayDeque<String> dq=new ArrayDeque<>();
		dq.add(str);
		boolean flip=false;
		for(int q=0;q<Q;++q) {
			int t=sc.nextInt();
			if(t==1)flip=!flip;
			else {
				int f=sc.nextInt();
				String c=sc.next();
				if(f==1) {
					if(flip)dq.addLast(c);
					else dq.addFirst(c);
				}else {
					if(!flip)dq.addLast(c);
					else dq.addFirst(c);
				}
			}
		}
		PrintWriter pw=new PrintWriter(System.out);
		if(!flip) {
			while(!dq.isEmpty()) {
				pw.print(dq.pollFirst());
			}
			pw.println();
		}else {
			while(!dq.isEmpty()) {
				char[] cs=dq.pollLast().toCharArray();
				int s=0,t=cs.length-1;
				while(s<t) {
					cs[s]^=cs[t];cs[t]^=cs[s];cs[s]^=cs[t];
					++s;
					--t;
				}
				pw.print(String.valueOf(cs));
			}
			pw.println();
		}
		pw.close();
	}
	
	void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));}
}


class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
    public boolean hasNext() { skipUnprintable(); return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    
    int nextInt() {
    	return (int)nextLong();
    }
}

Measured memory_bytes: 52292
n,m=gets.split.map(&:to_i)
x=gets.split.map(&:to_i).sort
y=[]
(m-1).times do |i|
  y[i] = x[i+1] - x[i]
end
y.sort!.reverse!
if n < m
  p y[n-1..-1].inject(:+)
else
  p 0
end


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

int dp[100010];

int main() {
	dp[0] = 0;
	for (int n = 1; n <= 100000; n++) {
		dp[n] = (int)1e9;
		int power = 1;
		while (power <= n) {
			dp[n] = min(dp[n], dp[n - power] + 1);
			power *= 6;
		}

		power = 1;
		while (power <= n) {
			dp[n] = min(dp[n], dp[n - power] + 1);
			power *= 9;
		}
	}
	int n; cin >> n;
	cout << dp[n] << endl;

	return 0;
}

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

#define SYOKIKA 0

int main (){

int N,M,sub[51][4]={0};
cin>>N>>M;

for (int i=1;i<=N;i++){for (int j=1;j<=M;j++){
char tmp; cin>>tmp;
if (tmp!='W'){sub[i][1]++;}
if (tmp!='B'){sub[i][2]++;}
if (tmp!='R'){sub[i][3]++;}

}}

int WHITEsum=SYOKIKA,BLUEsum=SYOKIKA,REDsum=SYOKIKA,ALLsum=50*50;

for (int i=1;i<=N-2;i++){
        WHITEsum+=sub[i][1];
        BLUEsum=SYOKIKA;
           for (int j=i+1;j<=N-1;j++){
               BLUEsum+=sub[j][2];
               REDsum=SYOKIKA;

           for (int k=j+1;k<=N;k++){REDsum+=sub[k][3];}

       ALLsum=min( ALLsum,WHITEsum+BLUEsum+REDsum);
}}

cout<<ALLsum<<endl;
return 0;
}




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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) (x).begin(),(x).end()
#define endl "\n"

using ll = long long;
using P = pair<int,int>;
using mp =  map<char,int>;

const int MOD = 1e9 + 7;
const int INF = 1001001001;

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

    int n, h, w;
    cin >> n >> h >> w;
  
    int ans = 0;
    rep(i, n){
        int a, b;
        cin >> a >> b;
      
        if(a >= h && b >= w){
            ans++;
        }
    }

  
    cout << ans << endl;

    return 0;
}


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

int main() {
  int N;
  cin >> N;

  int a[N+1];
  for (int i = 1; i <= N; i++) {
    cin >> a[i];
  }

  map<int, int> ball;
  int ansBoxes = 0;
  for (int i = N; i >= 1; i--) {

    int ballSum = 0;
    int j = 2;
    while(i*j<=N) {
      ballSum += ball[i*j];
      j++;
    }
    if (ballSum%2!=a[i]) {
      ball[i] = 1;
      ansBoxes++;
    }
  }

  cout << ansBoxes << endl;
  for (auto b: ball) {
    if (b.second==0) continue;

    cout << b.first << " ";
  }

  return 0;
}

Measured memory_bytes: 11008
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String t = sc.next();
		int count = 0;
		for(int i = 0; i < s.length(); i++) {
			if(!(s.charAt(i) == t.charAt(i))) {
				count++;
			}
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 41272
import java.util.*;
import java.math.BigInteger;
public class Main{
  public static void main(String[] args){
    Scanner sc =new Scanner(System.in);
    int N =sc.nextInt();
    long ans =0;
    for(int i=1;i<N;i++){
      int w =N/i;
      if(N%i==0){w =w-1;}
      ans =ans+w;}
    System.out.println(ans);
  }
}

Measured memory_bytes: 35612