akhauriyash/Code-Regression huggingface dataset:
from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
fw = [0] * n
bw = [0] * n

g = 0
for i in range(n):
    g = gcd(a[i], g)
    fw[i] = g

g = 0
for i in range(n-1, -1, -1):
    g = gcd(a[i], g)
    bw[i] = g

gmax = max(bw[1], fw[n-2])
for i in range(1, n-1):
    g = gcd(fw[i-1], bw[i+1])
    if gmax < g:
        gmax = g

print(gmax)





Measured memory_bytes: 16160
S = input()
K = int(input())
prev = S[0]
compressed = [1]
for c in S[1:]:
    if c == prev:
        compressed[-1] += 1
    else:
        prev = c
        compressed.append(1)
if len(compressed) == 1:
    print(len(S) * K // 2)
else:
    ans = sum(cnt // 2 for cnt in compressed) * K
    if S[0] == S[-1]:
        tmp = (compressed[0] + compressed[-1]) // 2
        tmp -= compressed[0] // 2
        tmp -= compressed[-1] // 2
        ans += tmp * (K - 1)
    print(ans)


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

#define rep(i, n) for(int i=0; i < (n); ++i)
#define ll long long

template<class T> using v = std::vector<T>;
template<class T> using vv = v<v<T>>;

const int mod = 1000000007;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
//const int mod = 998244353;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; }}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 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;}

// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
    vector<mint> fact, ifact;
    combination(int n):fact(n+1),ifact(n+1) {
        assert(n < mod);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
    }
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
};

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

    string s, t; cin >> s>>t;
    if (s == t.substr(0, t.size()-1)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 3644
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

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

using ll = long long;
using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	int a[200000];
	cin >> n;
	ll sum = 0;
	ll ans = 9223372036854775807;
	REP(i, n){
		cin >> a[i];
		sum += a[i];
	}
	ll snk = 0;
	REP(i, n - 1){
		snk += a[i];
		ans = min({abs(snk * 2 - sum), ans});
	}
	cout << ans << "\n";
	return 0;
}


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

int main(){    
  string S,T;
  cin >> S >> T;
  
  int t = 0;
  
  for(int i = 0; i <=2; i++){
   if(S.at(i) == T.at(i)){
     t++;
   }
  }
  cout << t << endl;
  
}


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

using namespace std;


int main()
{
	int n;
	cin >> n;
	int num[n];
	for (size_t i = 0; i < n; i++)
	{
		cin >> num[i];
	}
	sort(num, num + n);
	int big = num[n-1];
	int sm = 0;
	for (size_t i = 0; i < n; i++)
	{
      	if(sm*2-big>0)break;
      	if(abs(sm*2-big)>abs(num[i]*2-big))sm=num[i];
     // cout<<abs(sm-big/2)<<endl;
	}
	cout << big <<" "<< sm << endl;
    return 0;
}



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

int main(){
    int n, m, k;
    cin >> n >> m >> k;
    vector<ll> a(n+1, 0), b(m+1, 0);
    for(int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i-1];
    for(int i = 1; i <= m; i++) cin >> b[i], b[i] += b[i-1];
    int ans = 0;
    for(int i = 0; i <= n; i++){
        if(a[i] > k)    break;
        ans = max(ans, i+(int)(upper_bound(b.begin(),b.end(),k-a[i])-b.begin())-1);
    }
    cout << ans << endl;
    return 0;
}

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

int main()
{
	int N,A;
	cin >> N >> A;
	if (A >= N % 500) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#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=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<(x)<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

constexpr ll MOD=1000000007ll;
// constexpr ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-9;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout<<setprecision(10)<<fixed;
  long double l;
  cin>>l;
  l/=3;
  cout<<l*l*l<<'\n';
  return 0;
}


Measured memory_bytes: 256
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
m=sum(B)
for i in range(N-1):
    if A[i+1]==A[i]+1:
        m+=C[A[i]-1]
print(m)

Measured memory_bytes: 3060
import java.util.*;
import java.util.regex.*;
import static java.lang.Math.*;
import static java.lang.System.out;

// AOJ4
public class Main {
	final Scanner sc=new Scanner(System.in);
	final int[] vx={0,1,0,-1,-1,1,1,-1}, vy={-1,0,1,0,-1,-1,1,1};
	final int[] vvx={0,1,0,-1,-1,1}, vvy={-1,0,1,0,-1,1};
	final int INF=1<<24;
	static class Point{
		int x, y;
		Point(int x, int y){	this.x=x;	this.y=y;}
		Point(){	this.x=0; this.y=0;}
		@Override public String toString(){	return "("+this.x+","+this.y+")";}
		static boolean ok(int x,int y,int X,int Y,int min){	return (min<=x&&x<X)&&(min<=y&&y<Y);}
		static boolean ok(int x,int y,int X,int Y){	return ok(x,y,X,Y,0);}
	}
	public static void main(String[] args) {
		//long s=System.currentTimeMillis();
		new Main().AOJ2252();
		//out.println((System.currentTimeMillis()-s)+"msec");
	}
	
	// 2011MOGI - A 15:02
	void AOJ2252(){
		HashSet<Character> right=new HashSet<Character>();
		right.add('y');	right.add('h');	right.add('n');	right.add('u');	right.add('j');	right.add('m');
		right.add('i');	right.add('k');	right.add('o');	right.add('l');	right.add('p');
		while(sc.hasNext()){
			char[] c=sc.next().toCharArray();
			if(c[0]=='#')	break;
			boolean r=false;
			if(right.contains(c[0]))	r=true;
			int ans=0;
			for(int i=1; i<c.length; i++){
				if(right.contains(c[i])){
					ans+=!r?1:0;
					r=true;
				}else{
					ans+=r?1:0;
					r=false;
				}
			}
			out.println(ans);
		}
	}
	
	// 2012MOGI - A	14:50-14:57
	void AOJ2399(){
		while(sc.hasNext()){
			int N=sc.nextInt();
			if(N==0)	break;
			boolean[][] b=new boolean[N+1][N+1];
			for(int i=1; i<=N; i++){
				int m=sc.nextInt();
				for(int j=0; j<m; j++)	b[i][sc.nextInt()]=true;
			}
			boolean[] ans=new boolean[N+1];
			Arrays.fill(ans, true);
			int k=sc.nextInt();
			for(int i=0; i<k; i++){
				int p=sc.nextInt();
				for(int j=1; j<=N; j++){
					if(!b[j][p])	ans[j]=false;
				}
			}
			int res=-1;
			for(int i=1; i<=N; i++){
				if(ans[i]){
					if(res<0)	res=i;
					else{
						res=-1;
						break;
					}
				}
			}
			out.println(res);
		}
	}
	
	
	// AOJ2254 2011MOGI - B
	void B(){
		while(sc.hasNext()){
			int t=sc.nextInt(),n=sc.nextInt(),ans=0;
			if((t|n)==0)	break;
			boolean[][] b=new boolean[210][210];
			for(int i=0; i<n; i++)	b[sc.nextInt()+100][sc.nextInt()+100]=true;
			int sx=sc.nextInt()+100,sy=sc.nextInt()+100;
			LinkedList<ClassB> open=new LinkedList<ClassB>();
			open.add(new ClassB(sx,sy,0));
			boolean[][] close=new boolean[210][210];
			close[sx][sy]=true;
			while(!open.isEmpty()){
				ClassB now=open.poll();
				ans++;
				if(now.t>=t)	continue;
				for(int i=0; i<6; i++){
					int xx=now.x+vvx[i],yy=now.y+vvy[i];
					//if(!Point.ok(0xx, yy, 100, 100))	continue;
					if(close[xx][yy])	continue;
					if(b[xx][yy])	continue;
					open.add(new ClassB(xx,yy,now.t+1));
					close[xx][yy]=true;
				}
			}
			out.println(ans);
		}
	}
	class ClassB{
		int x,y,t;
		ClassB(int x,int y,int t){this.x=x; this.y=y; this.t=t;}
	}
}

Measured memory_bytes: 12000
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rep1(i, n) for(int i=1; i<=n; i++)
#define repr(i, n) for(int i=n-1; i>=0; i--)
#define repr1(i, n) for(int i=n; i>=1; i--)
#define all(v) v.begin(),v.end()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
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 n, x, y;
ll dist[2010][2010];
ll cnt[2010];

int main() {
    cin >> n >> x >> y;
    x--; y--;
    vector<vector<int>> g(n);
    rep(i, n) {
        if (i > 0) g[i-1].push_back(i);
        if (i < n-1) g[i+1].push_back(i);
    }
    g[x].push_back(y);
    g[y].push_back(x);

    rep(i, n) rep(j, n) dist[i][j] = LLINF;
    rep(i, n) dist[i][i] = 0;
    rep(i, n) {
        priority_queue<pli, vector<pli>, greater<pli>> q;
        q.emplace(0, i);
        while (!q.empty()) {
            pli top = q.top();
            q.pop();
            int u = top.second;
            for (auto v: g[u]) {
                if (chmin(dist[i][v], dist[i][u]+1)) {
                    q.emplace(dist[i][v], v);
                }
            }
        }
    }

    rep(i, n) rep(j, n) {
        if (i >= j) continue;
        cnt[dist[i][j]]++;
    }
    for (int k = 1; k <= n-1; k++) {
        cout << cnt[k] << endl;
    }

}


Measured memory_bytes: 31744
#include <iostream>

using namespace std;

bool func(int in)
{
	int x[5];
	int table[5] = { 10000,1000,100,10,1 };
	int table_2[5] = { 1,10,100,1000,10000 };
	int ans = 0;
	int in2 = in;
	for (int i = 0; i < 5; i++)
	{
		x[i] = in / table[i];
		in %= table[i];
	}
	for (int i = 4; i >= 0; i--)
	{
		ans += table_2[i] * x[i];
	}

	return ans == in2;
}

int main(void)
{
	int a, b;

	cin >> a >> b;

	int num = 0;

	for (int i = a; i <= b; i++)
	{
		if (func(i))
			num++;
	}

	cout << num << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define MIN(a,b) ((a) <= (b) ? (a) : (b))
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort( ALL(v) )

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

int main()
{
    ll h,w; cin>>h>>w;
    if(w==1 || h==1)
    {
        cout<<1<<endl;
        return 0;
    }


    ll first = (h+1)/2;
    ll second = h-first;
    ll mult = (w+1)/2;

    cout<<first*mult + second*(w/2)<<endl;

    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 2000000
#define INFTY (1<<30)

int H, A[MAX+1];

void maxHeapify(int i){
  int l, r, largest;
  l = 2*i;
  r = 2*i+1;

  if(l<=H && A[l] > A[i]) largest = l;
  else largest = i;
  if(r<=H && A[r] > A[largest]) largest = r;
  
  if(largest != i){
    swap(A[i],A[largest]);
    maxHeapify(largest);
  }
}

int extract(){
  int maxv;
  if(H<1) return -INFTY;
  maxv = A[1];
  A[1] = A[H--];
  maxHeapify(1);
  return maxv;
}

void increaseKey(int i, int key){
  if(key < A[i]) return;
  A[i] = key;
  while(i>1 && A[i/2]<A[i]){
    swap(A[i], A[i/2]);
    i=i/2;
  }
}

void insert(int key){
  H++;
  A[H] = -INFTY;
  increaseKey(H,key);
}

int main(){
  int key;
  char com[10];
  while (1)
  {
    scanf("%s",com);
    if(com[0]=='e'&&com[1]=='n') break;
    if(com[0]=='i'){
      scanf("%d",&key);
      insert(key);
      }
    if(com[0]=='e') printf("%d\n",extract());
  }
  
  return 0;
}


Measured memory_bytes: 6572
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#include <numeric>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <functional>
#include <assert.h>
using ll=long long;
#define int ll
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define SZ(x) ((int)x.size())
#define fi first
#define se second
const int INF = 1e15;
using namespace std;

template<class T> using vc=vector<T>;
template<class T> using vvc=vc<vc<T>>;

using pi=pair<int,int>;
using vi=vc<int>;

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

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(20);

    char c; cin >> c;
    if(islower(c)) cout << "a" << endl;
    else cout << "A" << endl;
}

Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
vector< vector<ll> > ans;
vector<vector<ll>> vac;
ll vacation(int N,int i){
  if(N<0){
      return 0;
  }
  if(ans[N][i]!=-1)
  	return ans[N][i];
  for(int j=0;j<3;j++){
    if(i!=j){
      ans[N][i] = max(vac[N][j]+vacation(N-1,j),ans[N][i]);
    }
  }
  return ans[N][i];
}
int main(){
  ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  #ifdef SANS
        freopen("ongoingin.txt","r",stdin);
        freopen("ongoingout.txt","w",stdout);
    #endif
  ll N;
  cin>>N;
  vac.resize(N,vector<ll>(3));
  ans.resize(N);
  for(int i=0;i<N;i++){
    ans[i].resize(3);
  }
  for(int i=0;i<N;i++){
    for(int j=0;j<3;j++){
      ans[i][j] = -1;
    }
  }
  for(int i=0;i<N;i++){
    for(int j=0;j<3;j++){
      cin>>vac[i][j];
      //cout<<vacation[i][j]<<" ";
    }
  }
  int final_ans = max(vacation(N-1,0),max(vacation(N-1,1),vacation(N-1,2)));
  cout<<final_ans<<endl;
  return 0;
  /*
  for(int i=0;i<1e5;i++){
    cout<<i+1<<endl;
  }*/
}


Measured memory_bytes: 21884
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(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;
#define out(a) cout<<fixed<<setprecision((a))


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

	ll N,K;
	cin >> N >> K;
	if(K==1){
		cout << 0 << endl;
		return 0;
	}
	cout << N-K << endl;
	
}


Measured memory_bytes: 256
function Main(input) {
  input=input.split("\n");
  if(input[input.length-1]===''){
    input.pop();
  }
  const C=input[0];
  console.log(String.fromCharCode(1+C.charCodeAt(0)));
}


//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));
  



  


Measured memory_bytes: 29500
#include <stdio.h>

int main(int argc, const char * argv[]) {
    int n, m, l, A[100][100], B[100][100];
    long long C[100][100];
    for(int i=0; i<100; i++){
        for(int j=0; j<100; j++){
            C[i][j] = 0;
        }
    }
    scanf("%d %d %d", &n, &m, &l);
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%d", &A[i][j]);
        }
    }
    for(int i=0; i<m; i++){
        for(int j=0; j<l; j++){
            scanf("%d", &B[i][j]);
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<l; j++){
            for(int k=0; k<m; k++){
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    for(int i=0; i<n; i++){
        printf("%lld", C[i][0]);
        for(int j=1; j<l; j++){
            printf(" %lld", C[i][j]);
        }
        printf("\n");
    }
    return 0;
}



Measured memory_bytes: 2112
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

struct mint{
	ll x;
	mint(ll x=0):x((x%mod+mod)%mod){}
	friend ostream &operator<<(ostream& os,const mint& a){
		return os<<a.x;
	}
	friend istream &operator>>(istream& is,mint& a){
		ll t;
		is>>t;
		a=mint(t);
		return (is);
	}
	mint& operator+=(const mint a){
		if((x+=a.x)>=mod) x-=mod;
		return *this;
	}
	mint& operator-=(const mint a){
		if((x+=mod-a.x)>=mod)x-=mod;
		return *this;
	}
	mint& operator*=(const mint a){
		(x*=a.x)%=mod;
		return *this;
	}
	mint operator+(const mint a) const{
		mint res(*this);
		return res+=a;
	}
	mint operator-(const mint a) const{
		mint res(*this);
		return res-=a;
	}
	mint operator*(const mint a) const{
		mint res(*this);
		return res*=a;
	}
	mint pow(ll t) const{
		if (!t) return 1;
		mint a=pow(t>>1);
		a*=a;
		if(t&1) a*=*this;
		return a;
	}
	// for prime mod
	mint inv() const{
		return pow(mod-2);
	}
	mint& operator/=(const mint a){
		return (*this)*=a.inv();
	}
	mint operator/(const mint a) const{
		mint res(*this);
		return res/=a;
	}
};

struct combination{
  vector<mint> fact,ifact;
  combination(int n):fact(n+1),ifact(n+1){
	assert(n<mod);
	fact[0]=1;
	for(int i=1;i<=n;i++) fact[i]=fact[i-1]*i;
	ifact[n]=fact[n].inv();
	for(int i=n;i>=1;i--) ifact[i-1]=ifact[i]*i;
  }
  mint operator()(int n,int k){
	if (k<0 || k>n) return 0;
	return fact[n]*ifact[k]*ifact[n-k];
  }
};

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	int h,w,a,b;
	cin>>h>>w>>a>>b;
	combination comb(300000);
	mint ans=0;
	FOR(i,b+1,w+1){
		ans+=comb(h-a-1+i-1,h-a-1)*comb(a-1+w-i,a-1);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 4992
#include<iostream>
#include<string>
#include<set>
#include<algorithm>


int main() {
    std::string w;
    std::cin >> w;
    std::set<char> ws;
    
    for (int i = 0; i < w.size(); i++)
    {
        ws.insert(w[i]);
    }

    std::sort(w.begin(), w.end());
    std::string ans = "Yes";
    for (auto itr = ws.begin(); itr != ws.end(); itr++)
    {
        int num = std::upper_bound(w.begin(), w.end(), *itr) - std::lower_bound(w.begin(), w.end(), *itr);

        if(num%2) {
            ans = "No";
        }
    }

    std::cout << ans << "\n";
}

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


int main() {


    int m,n;
    cin >> n >> m;
    int sum=0;

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

    std::sort(a.begin(), a.end(), std::greater<int>() );

    // cout << a[m-1] << endl;
    if(4*m*a[m-1]<sum){
      cout << "No" << endl;
    }else{
      cout << "Yes" << endl;
    }

}


Measured memory_bytes: 256
use std::str::FromStr;
use std::fmt::Debug;

fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn gcm(a: i32, b: i32) -> i32{
    if b == 0{
        a
    }else{
        gcm(b, a%b)
    }
}

fn main(){
    let line: Vec<usize> = read_as_vec();
    let (h, w) = (line[0], line[1]);

    let mut table: Vec<Vec<usize>> = Vec::new();

    for _ in 0..h{
        table.push(read_as_vec());
    }

    let mut ans: Vec<(usize, usize, usize, usize)> = Vec::new();

    for i in 0..h{
        for j in 0..w-1{
            if table[i][j]%2 == 1{
                table[i][j] -= 1;
                table[i][j+1] += 1;
                ans.push((i, j, i, j+1));
            }
        }
    }

    for i in 0..h-1{
        if table[i][w-1]%2 == 1{
            table[i][w-1] -= 1;
            table[i+1][w-1] += 1;
            ans.push((i, w-1, i+1, w-1));
        }
    }

    println!("{}", ans.len());

    for elem in ans{
        println!("{} {} {} {}", elem.0+1, elem.1+1, elem.2+1, elem.3+1);
    }
}


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


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

    int n;
    cin >> n;
    vector<int> a(n);
    rep (i, n) cin >> a[i];
    ll ans=0;
    rep (i, n) {
        while(a[i] > 1) {
            if (a[i] % 2 == 0) {
                a[i] /= 2;
                ans++;
            }
            else break;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3660
result = []
while True:

    s = raw_input()
    if s == "-":
        break
    else:
        m = input()
        for i in xrange(m):
            h = input()
            s = s[h:len(s)] + s[0:h]
        
        result.append(s)

for i in result:
    print i 

Measured memory_bytes: 6384
#include <iostream>
using namespace std;
int ans[50];
int main()
{
	int n,m;
	cin >> n >> m;
	for(int i = 0;i<m;i++)
	{
		int a,b;
		cin >> a >> b;
		ans[a]++;
		ans[b]++;
	}
	for(int i = 1;i<=n;i++)
		cout<<ans[i]<<endl;
	return 0;
}

Measured memory_bytes: 256
n,x,y = map(int,input().split())
ans = [0]*(n-1)


def f(N,X,Y):
  for i in range(1,N):
    for j in range(i+1,N+1):
      if i <= X and j <= X:
        dic = j-i
      elif i >= Y and j >= Y:
        dic = j-i
      elif i <= X and j >= Y:
        dic = (j-i)-(Y-X)+1
      elif X < i < Y and j >= Y:
        dic = min(i-X+1,Y-i)+(j-Y)
      elif i<=X and X < j < Y:
        dic = (X-i)+min(Y-j+1,j-X)
      elif X < i < Y and X < j < Y:
        dic = min(j-i,(i-X+1)+(Y-j))
      ans[dic-1] = ans[dic-1]+1
  
f(n,x,y)
for ret in ans:
  print(ret)

Measured memory_bytes: 3444
#include<bits/stdc++.h>
constexpr long long INFL = 1LL << 60;
constexpr int INF = 1 << 30;

using namespace std;

using ll = long long;
using P = tuple<int, int>;
using iarr = valarray<int>;

int main()
{
    int n;
    cin >> n;
    vector<string> v(n);
    for(int i = 0; i < n; ++i) cin >> v[i];
    int a[26];
    for(int i = 0; i < 26; ++i) a[i] = INF;
    for(auto itr = v.begin(); itr != v.end(); ++itr){
        for(char c = 'a'; c <= 'z'; ++c){
            a[c-'a'] = min(static_cast<int>(count(itr->begin(), itr->end(), c)), a[c-'a']);
        }
    }
    for(int i = 0; i < 26; ++i){
        for(int j = 0; j < a[i]; ++j){
            cout << static_cast<char>('a' + i);
        }
    }
    cout << endl;


    return 0;
}

Measured memory_bytes: 256
num = input()
for bit in range(2 ** 3):
    tmp = int(num[0])
    ans = str(num[0])
    for i in range(3):
        if bit >> i & 1 == 0:
            tmp += int(num[i + 1])
            ans += '+' + num[i + 1]
        else:
            tmp -= int(num[i + 1])
            ans += '-' + num[i + 1]
    if tmp == 7:
        ans += '=7'
        print(ans)
        break


Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  int N;
  long long K;
  std::cin >> N >> K;

  std::vector<int> A_array(N);
  for (int i = 0; i < N; ++i) {
    std::cin >> A_array[i];
    A_array[i] -= 1;
  }

  if (N > K) {
    int index = 0;
    for (int i = 0; i < K; ++i) {
      index = A_array[index];
    }
    std::cout << index + 1 << std::endl;
    return 0;
  }

  std::vector<bool> seen(N, false);

  int next_index = 0;
  bool loop_found = false;
  for (int i = 0; i < N; ++i) {
    if (seen[next_index]) {
      loop_found = true;
      break;
    }
    seen[next_index] = true;
    next_index = A_array[next_index];
  }

  const int loop_start_index = next_index;
  const int loop_end_count = std::count(seen.begin(), seen.end(), true);

  int count = 0;
  next_index = 0;
  for (int i = 0; i < N; ++i) {
    if (next_index == loop_start_index) {
      break;
    }
    count += 1;
    next_index = A_array[next_index];
  }

  const long long loop_num = loop_end_count - count;

  const long long target_index_from_loop_start = (K - count) % loop_num;

  for (int i = 0; i < target_index_from_loop_start; ++i) {
    next_index = A_array[next_index];
  }

  std::cout << next_index + 1 << std::endl;
  return 0;
}


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

using namespace std;

#define sim template <class c
#define ris return *this
#define dor > debug &operator<<
#define eni(x)                                                                        \
	sim > typename enable_if<sizeof dud<c>(0) x 1, debug &>::type operator<<(c i) \
	{
sim > struct rge
{
	c b, e;
};
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c *x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug
{
#ifdef LOCAL
	~debug()
	{
		cerr << endl;
	}
	eni(!=) cerr << boolalpha << i;
	ris;
} eni(==) ris << range(begin(i), end(i));
}
sim, class b dor(pair<b, c> d)
{
	ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d)
{
	*this << "[";
	for (auto it = d.b; it != d.e; ++it)
		*this << ", " + 2 * (it == d.b) << *it;
	ris << "]";
}
#else
	sim dor(const c &)
	{
		ris;
	}
#endif
}
;
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define forn(i, n) for (ll i = 0; i < int(n); i++)
#define rfor(n, i) for (ll i = (n - 1); i >= 0; --i)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
#define len(V) (int)V.size()
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define M_PI 3.14159265358979323846
#define EPS 1e-7

int cnt = 0;

void solve()
{
	int a[3]; cin >> a[0] >> a[1] >> a[2];
	sort(a, a + 3);
	ll res = 0;
	if ((a[1] - a[0]) % 2 == 1) 
	{
		while (a[0] < a[1])
		{
			a[0] += 2;
			res++;
		}
		a[1]++; a[2]++;
		res++;
		cout << res + (a[2] - a[1]);
	}
	else
	{
		res += ((a[1] - a[0]) / 2);
		cout << res + (a[2] - a[1]);
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	solve();
}


Measured memory_bytes: 3648
#include <cstdio>
#include <cmath>
#include <iostream>
#include <ctime>
#include <vector>
#include <cstdlib>
using namespace std;
long long int memo[100];

long long int luka(int n){
    if(n == 0)return 2;
    if (n == 1) return 1;
    if(memo[n] != 0)return memo[n];
    return memo[n] = luka(n-1) + luka(n-2);


}
int main(){
    int n;
    cin >> n;
    cout << luka(n) << "\n";
}


Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;

public static class P
{
    public static void Main()
    {
        var nk = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var n = nk[0];
        var k = nk[1];
        var a = Console.ReadLine().Split().Select(int.Parse).ToArray();
        for (int i = k; i < n; i++)
        {
            Console.WriteLine(a[i - k] < a[i] ? "Yes" : "No");
        }
    }
}


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

#define froop1(a,n) for(int i = a;i < n;i++)
#define froop2(a,n) for(int i = a;i > n;i--)
int main(){
	queue<char> a,b,c;
	string ai;
  cin >> ai;
  froop1(0,ai.length()) a.push(ai[i]); 
    cin >> ai;
  froop1(0,ai.length()) b.push(ai[i]); 
    cin >> ai;
  froop1(0,ai.length()) c.push(ai[i]);
  
  char turn = 'a';
  while(1){
    if(turn == 'a'){
      if(a.empty()){
        cout << 'A' << endl;
        return 0;
      }else{
      turn = a.front();
      a.pop();
      }
    }else if(turn == 'b'){
      if(b.empty()){
        cout << 'B' << endl;
        return 0;
      }else{
      turn = b.front();
      b.pop();
      }
    }else{
      if(c.empty()){
        cout << 'C' << endl;
        return 0;
      }else{
      turn = c.front();
      c.pop();
      }
    }
  }
}

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

int main(){
	
	double n, ans = 0;
	
	cin >> n;
	
	for (int i = 1; i <= n; i++){
		if (i % 2 != 0){
			ans++;
		}
	}
	
	cout << ans/n;
	
}


Measured memory_bytes: 256
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = [0]
y = [0]
for i in range(n):
    x.append(a[i] + x[i])
for j in range(m):
    y.append(b[j] + y[j])
ans = 0
q = m
for p in range(n + 1):
    if x[p] > k:
        break
    while y[q] > k - x[p]:
        q = q - 1
    ans = max(ans, p + q)
print(ans)

Measured memory_bytes: 47532
#include<bits/stdc++.h>
#include <ext/numeric>
#define     __        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define     pi        acos(-1)
#define     ll        long long int
#define     mem(a)    memset(a,0,sizeof(a))
#define     mems(a)   memset(a,-1,sizeof(a))
#define     pii       pair<int,int>
#define     N         20005
using namespace std;

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

        int a,b;

        cin >> a >> b;

        if(a<=5) cout << 0;

        else if(a>5 && a<13) cout << (b/2);

        else cout << b;
   return 0;
}


Measured memory_bytes: 256
fn main() {
    let _: i64 = read();
    let an: Vec<i64> = read_vec();
    let sum_an_by_step2 = {
        let mut res = 0;
        for (i, &a) in an.iter().skip(1).enumerate() {
            if i % 2 == 0 {
                res += a;
            }
        }
        res
    };
    let mut x: i64 = an.iter().sum::<i64>() - 2 * sum_an_by_step2;

    for a in an.iter() {
        print!("{} ", x);
        x = (a - x/2) * 2;
    }
    println!("");

}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}



Measured memory_bytes: 8444
#include<cstdint>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<deque>
#include<stack>
#include<iterator>
#include<stack>
#include<cctype>
#include<climits>
#include<string>
#include<bitset>
#include<cfloat>
#include<iomanip>
#include<numeric>
#include<utility>
#include<initializer_list>


#define repi(i,start,end)for(int64_t (i)=(start);(i)<(end);++(i))
#define rep(i,end) repi((i),0,(end))
#define rfor(x, v) for(auto& (x) : (v))
#define iterate(itr, v) for(auto (itr)=(v).begin();(itr)!=(v).end();++(itr))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vin(v) rep(i,(v).size()) cin >> (v)[i];
#define vpin(v) rep(i,(v).size()) cin >> (v)[i].first >> (v)[i].second

using namespace std;
using Int = int64_t;
using pint = pair<Int, Int>;
using vint = vector<Int>;
using vvint = vector<vint>;
using vpint = vector<pint>;
using vstr = vector<string>;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T>void put_double(T a){if(cout.precision()!=12)cout<<setprecision(12);cout<<a<<"\n";}
template<class T>void println(T a){cout << a << "\n";}
template<class T>void put_line(T &v){iterate(itr,v){cout<<*itr<<((itr==--v.end())?"\n":" ");}}
// auto [x, y] = make_tuple(3, 4); => let (x, y) = (3, 4);

int main(void) {
    string a, b; cin >> a >> b;
    if(a.length() > b.length()) {
        println("GREATER");
        return 0;
    } else if(a.length() < b.length()) {
        println("LESS");
        return 0;
    } else {
        int len = a.length();
        rep(i, len) {
            if(a[i] > b[i]) {
                println("GREATER");
                return 0;
            } else if(a[i] < b[i]) {
                println("LESS");
                return 0;
            }
        }
    }
    println("EQUAL");

    return 0;
}


Measured memory_bytes: 256
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
import fractions as math
from functools import reduce
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def qq(numbers):
    return reduce(lcm_base, numbers, 1)

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

B=[i//2 for i in A]
p=qq(B)
for i in A:
    i//=2
    if (p//i)%2==0:
        print(0)
        exit()
print(m//p - m//(p*2))


Measured memory_bytes: 16316
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
using namespace std;
typedef  long long int lint;
typedef pair<int, int> P;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)

const lint MOD = pow(10, 9) + 7;

/*
vector<char>al(26);
al = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
vector<char>AL(26);
AL = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
vector<char>NUM(10);
	NUM = { '0','1','2' ,'3' ,'4' ,'5' ,'6' ,'7' ,'8' ,'9' };
*/


int main() {
	int N , A ,B;
	cin >> N >> A >> B;
	cout << min(A, B) << ' ' << max(A + B - N,0) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define P(x) cout << (x) << endl
#define p(x) cout << (x)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i));
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a); i>n; --i)
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
ll cnt = 0;
vi G;
inline void insertionSort(vi& a, int n, int g) {
	rep(i, g, n) {
		int v = a[i];
		int j = i - g;
		while(j >= 0 && a[j] > v) {
			a[j + g] = a[j];
			j -= g;
			++cnt;
		}
		a[j + g] = v;
	}
}
inline void shellSort(vi& a, int n) {
	int h = 1;
	while(true) {
		G.push_back(h);
		h = 3 * h + 1;
		if(h > n) break;
	}
	rrep(i, len(G) - 1, -1) {
		insertionSort(a, n, G[i]);
	}
}
int main() {
	int n; cin >> n;
	vi v(n); rep(i, 0, n) cin >> v[i];
	shellSort(v, n);
	P(len(G));
	rrep(i, len(G) - 1, -1) cout << G[i] << (i == 0 ? "\n" : " ");
	P(cnt);
	rep(i, 0, n) P(v[i]);
	return 0;
}

Measured memory_bytes: 6652
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REPL(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
struct edge {
  int to;
  ll cost;
  edge(int t, ll c): to(t), cost(c) {};
};
using P = pair<ll, int>;
int N;
vector<vector<edge>> G;
vector<ll> d;
vector<int> par;
void dijkstra(int s) {
  priority_queue<P, vector<P>, greater<P> > que;
  d = vector<ll>(N, longinf);
  par = vector<int>(N, -1);
  d[s] = 0;
  que.push(P(0, s));
  while (!que.empty()) {
    P p = que.top();
    que.pop();
    int v = p.second;
    if (d[v] < p.first) continue;
    for (int i=0; i<(int)G[v].size(); ++i) {
      edge e = G[v][i];
      if (d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        que.push(P(d[e.to], e.to));
        par[e.to] = v;
      }
    }
  }
}
int main() {
  int M;
  cin >> N >> M;
  G = vector<vector<edge>>(N);
  rep(i, N) if(i) G[i].push_back(edge(i-1, 0));
  rep(i, M) {
    int l, r;
    ll c;
    cin >> l >> r >> c;
    --l; --r;
    G[l].push_back(edge(r, c));
  }
  dijkstra(0);
  cout << (d[N-1]==longinf ? -1 : d[N-1]) << endl;
  return 0;
}


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

#define rep(i, n) for(long long i=0;i<(long long)(n);i++)
#define rep2(i, s, n) for(long long i=(s);i<(long long)(n);i++)
#define repi(i, n) for(int i=0;i<(int)(n);i++)
#define rep2i(i, s, n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define chmax(s, t) s=max(s,t);
#define chmin(s, t) s=min(s,t); 

#define deg2rad(deg) (((deg)/360)*2*M_PI)
#define rad2deg(rad) (((rad)/2/M_PI)*360)

using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;

const ll INF = (1LL<<60);
const int INFi = (1<<29);

/*素数判定*/
bool is_prime(ll n){
    if(n==1) return false;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0) return false;
    }
    return true;
}

/*約数列挙*/
vll enum_divisors(ll n){
    vll l;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            l.push_back(i);
            if(n/i != i) l.push_back(n/i);
        }
    }
   sort(all(l));
   return l;
}

/*素因数分解*/
vector<P> prime_factorize(ll n){
    vector<P> l;
    for(ll i=2;i*i<=n;i++){
        if(n%i!=0) continue;
        ll e = 0;
        while(n%i==0){
            e++;
            n /= i;
        }
        l.push_back({i, e});
    }
    if(n!=1) l.push_back({n, 1});
    return l;
}

/*最小公倍数*/
ll lcm(ll a, ll b){
    return a*b/__gcd(a,b);
}

/*最大公約数*/
ll gcd(ll a, ll b){
    return __gcd(a,b);
}

/*組み合わせ(Combination)*/
const ll CMAX = 1010000;
const ll CMOD = 1e9+7;
ll fac[CMAX], finv[CMAX], inv[CMAX];
// テーブルを作る前処理
void combinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (ll i = 2; i < CMAX; i++) {
		fac[i] = fac[i - 1] * i % CMOD;
		inv[i] = CMOD - inv[CMOD%i] * (CMOD / i) % CMOD;
		finv[i] = finv[i - 1] * inv[i] % CMOD;
	}
}
// 二項係数計算
ll comb(ll n, ll k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % CMOD) % CMOD;
}

/*階乗*/
ll factorial(ll n){
    const ll FMOD = 1e9+7;
    ll ret = n;
    for(ll i=n-1;i>0;i--){
        ret*=i;
        ret%=FMOD;
    }
    return (ret?ret:1);
}


int main(){

    ll n; cin >> n;
    vll a(n); rep(i, n) cin >> a[i];

    if(n%2){
        for(ll i=n-1;i>=0;i-=2){
            cout << a[i] << " ";
        }
        for(ll i=1;i<n;i+=2){
            cout << a[i] << " ";
        }
    }
    else{
        for(ll i=n-1;i>0;i-=2){
            cout << a[i] << " ";
        }
        for(ll i=0;i<n;i+=2){
            cout << a[i] << " ";
        }
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 4768
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <vector>
#include <stdio.h>
#include <iostream>
#include <unordered_set>
#include <algorithm>
#include <bitset>
#include <set>
#include <map>
#include <random>
#include <time.h>
#include <cassert>

#define prev askdnsajd
#define rank asasdmdnasd
#define next lsjndajbs
#define hash asmdklansd
#define index asdklnas
#define right sld
#define left sldl
using namespace std;

typedef long long ll;
typedef long double dbl;

template<class T>
void print(vector<T> s){
    for (T x : s)
        cout << x << " ";
    cout << endl;
}

const int mod = 1e9 + 7;

const int maxn = 2007;

ll c[maxn][maxn];

int main(){
    srand(17);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("a.in", "r", stdin);
    for (int i = 0; i < maxn; i++){
        for (int j = 0; j <= i; j++){
            if (j == 0)
                c[i][j] = 1;
            else{
                c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
                if (c[i][j] >= mod)
                    c[i][j] -= mod;
            }
        }
    }
    int n, k;
    cin >> n >> k;
    if (k == n){
        cout << 1 << " ";
        for (int i = 1; i < k; i++)
            cout << 0 << " ";
    }
    else {
        for (int i = 1; i <= k; i++) {
//        cout << c[k - 1][i - 1] << " " << c[n - k - 1][i] << endl;
            ll cnt = 2 * c[n - k - 1][i - 1] + c[n - k - 1][i];
            if (i > 1)
                cnt += c[n - k - 1][i - 2];
            cout << c[k - 1][i - 1] * cnt % mod << "\n";
//        cout << answer << "\n";
        }
    }
}

Measured memory_bytes: 30336
use std::io::Read;
use std::collections::HashMap;

fn check(cnt: [usize; 3]) -> usize {
    if cnt[2] > 0 || cnt[1] >= 2 { 2 }
    else if cnt[1] == 0 { 1 }
    else { 0 }
}

#[derive(Default)]
struct Solver {
    all : HashMap<usize, [usize; 3]>,
    part : HashMap<(usize, usize), usize>
}

impl Solver {
    fn solve_impl(&mut self, g: &Vec<Vec<usize>>, pos: usize, prev: usize) -> usize {
        let n = g.len();
        if self.part.contains_key(&(pos, prev)) { return self.part[&(pos, prev)]; }
        if prev != n && self.all.contains_key(&pos){
            let mut cnt = self.all[&pos];
            cnt[self.solve_impl(g, prev, pos)] -= 1;
            let res = check(cnt);
            self.part.insert((pos, prev), res);
            return res;
        }
        let mut cnt = [0; 3];
        for &next in &g[pos] {
            if next == prev { continue; }
            cnt[self.solve_impl(g, next, pos)] += 1;
        }
        let res = check(cnt);
        if prev == n { self.all.insert(pos, cnt); }
        self.part.insert((pos, prev), res);
        res
    }

    pub fn solve(&mut self, g: &Vec<Vec<usize>>) -> bool {
        let n = g.len();
        for i in 0..n {
            if self.solve_impl(g, i, n) == 2 { return true; }
        }
        false
    }
}

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).ok();
    let mut it = buf.split_whitespace();
    let n = it.next().unwrap().parse::<usize>().unwrap();
    let mut g = vec![Vec::<usize>::new(); n];
    for _ in 0..n-1 {
        let a = it.next().unwrap().parse::<usize>().unwrap() - 1;
        let b = it.next().unwrap().parse::<usize>().unwrap() - 1;
        g[a].push(b);
        g[b].push(a);
    }
    let mut s = Solver::default();
    println!("{}", if s.solve(&g) { "First" } else { "Second" });
}


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

using namespace std;

typedef long long ll;

int main(){
	ios::sync_with_stdio(false);
	int x;
	cin >> x;
	int pos = 0;
	for(int i=1; ;i++){
		pos += i;
		if(pos >= x){
			cout << i << endl;
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
const ll INF = 1LL<<61;
template<class T>bool chmax(T &a, const T &b) { 
  if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) {
  if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll jou(ll N, ll P){if(P==0) return 1;
  if(P%2==0){ll t = jou(N, P/2);return t*t % mod;
  }return (N * jou(N, P-1)) % mod;}  //jou(n,mod-2)で逆元
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる





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

  if((a/10)%111==0||(a%1000)%111==0){
    cout << "Yes" << endl;
  }
  else cout << "No" << endl;
}

Measured memory_bytes: 256