akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;using vvi=vector<vi>;using vl=vector<ll>;
using P=pair<int,int>;using PL=pair<ll,ll>;using vp=vector<P>;
const int INF=1<<30,MOD=1000000007;const ll LINF=1ll<<60;
#define _ol3(_1,_2,_3,name,...) name
#define _rep(i,n) _repi(i,0,n)
#define _repi(i,a,b) for(int i=a,i##_l=(b);i<i##_l;++i)
#define REP(...) _ol3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)
#define REPR(i,n) for(int i=n-1;i>=0;--i)
#define REPA(i,v) REP(i,v.size())
#define all(v) (v).begin(),(v).end()
#define bit(n) (1ll<<(n))
#define clamp(n,mi,ma) max(min(n,ma),mi)
#define uniq(v) sort(all(v));v.erase(unique(all(v)),v.end())
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define cho(n,a,b) cout<<((n)?a:b)<<endl
#define YES(n) cho(n,"YES","NO")
#define Yes(n) cho(n,"Yes","No")
#define Poss(n) cho(n,"Possible","Impossible")
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(a>b){a=b;return 1;}return 0;}
template<class T>ostream&operator<<(ostream&o,const vector<T>&v){for(const T&i:v)o<<i<<' ';return o;}
template<class T>istream&operator>>(istream&i,vector<T>&v){for(T&j:v)i>>j;return i;}
template<class T,class U>ostream&operator<<(ostream&o,const pair<T,U>&p){return o<<p.F<<' '<<p.S;}
template<class T,class U>istream&operator>>(istream&i,pair<T,U>&p){return i>>p.F>>p.S;}
template<class T>ostream&operator<<(ostream&o,const set<T>&v){for(const T&i:v)o<<i<<' ';return o;}
template<class T>ostream&operator<(ostream&o,const T&t){return o<<t;}
template<class T>istream&operator>(istream&i,T&t){return i>>t;}
#ifndef LOCAL
struct ostdmy{
template<class T>ostdmy&operator<<(const T&t){return*this;}
template<class T>ostdmy&operator<(const T&t){return*this;}};ostdmy cer_;
#define cerr cer_
#endif
template<typename T>
T gcd(T a,T b){ // log N
    while((a%=b)&&(b%=a));
    return a|b;
}
template<typename T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
ll solve(){
    ll n,m;
    cin>n>m;
    ll l=lcm(n,m);
    string s,t;
    cin>s>t;
    REP(i,n){
        //if(i*m%n==0)cerr<i<' '<i*m/n<endl;
        if(i*m%n==0 && s[i]!=t[i*m/n])return -1;
    }
    return l;
}
int main(){
    cin.tie(0);ios::sync_with_stdio(0);
    cout<solve()<endl;
    return 0;
}


Measured memory_bytes: 640
// prosto beresh i bahaesh'

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <ctime>
#include <cassert>

#define pb push_back
#define mp make_pair

#define f first
#define s second

using namespace std;

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

const int N = (int) 2e6 + 7;
const int MOD = (int) 1e9 + 7;

const double eps = 1e-7;

int n;
int x[N];

int t[N];

void build(int v = 1, int tl = 0, int tr = n - 1) {
  if (tl == tr) t[v] = x[tl] - 2 * tl;
  else {
    int mid = (tl + tr) / 2;
    build(v + v, tl, mid);
    build(v + v + 1, mid + 1, tr);
    t[v] = min(t[v + v], t[v + v + 1]);
  }
}

int gmin(int l, int r, int v = 1, int tl = 0, int tr = n - 1) {
  if (l > tr || r < tl) return MOD;
  if (l <= tl && tr <= r) return t[v];
  int mid = (tl + tr) / 2;
  return min(gmin(l, r, v + v, tl, mid), gmin(l, r, v + v + 1, mid + 1, tr));
}

bool good(int l, int r) {
  bool res = 1;
  if (l < r)
    res &= (gmin(l, r - 1) > - 2 * l);
  res &= (x[r] >= 2 * (r-l));
  return res;
}

int main() {
  #ifdef LOCAL
  freopen("in.txt", "r", stdin);
  #endif

  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &x[i]);
  }
  sort(x, x + n);
  build();
  ll res = 1;
  for (int i = 1; i < n; i++) {
    int ans = i - 1;
    int l = 0, r = i - 1;
    while (l <= r) {
      int mid = (l + r) / 2;
      if (good(mid, i)) {
        ans = mid;
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    }
    int how = i - ans;
    res *= (how + 1);
    res %= MOD;
  }
  cout << res;
  return 0;
}

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

int main()
  {
    int n,x,t;
    cin>>n>>x>>t;
    
    int ans=0;
    int z=0;
    while(z<n)
    {
      z=z+x;
      ans+=t;
    }
    cout<<ans;
  }

Measured memory_bytes: 3620
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;

int main(void)
{
	int N,i,j,ians=0;
	double ans=0;

	cin >> N;

	int x[N]={},y[N]={};

	for(i=0;i<N;i++)
	{
		cin >> x[i] >> y[i];
	}

	for(i=0;i<N-1;i++)
	{
		for(j=i+1;j<N;j++)
		{
			ians=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
			ans+=sqrt(ians);
		}
	}
	
	ans=ans*2.0/(double)N;

	cout << fixed << setprecision(10) << ans << endl;

	return 0;
}


Measured memory_bytes: 256
/**
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 */

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

#define DEBUG
#ifndef DEBUG
#define endl "\n"
#define log(args...)
#else
#define log(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); logf(_it, args); }
void logf(istream_iterator<string> it) {
}
template<typename T, typename ... Args>
void logf(istream_iterator<string> it, T a, Args ... args) {
	cout << *it << " = " << a << endl;
	logf(++it, args...);
}
#endif

#define forn(i,k,n) for(ll i=(k); i<(n); i++)

const double PI = acos(-1);
typedef long long ll;
#define fori(n) for(ll i=0; i<(n); i++)

#define cins(s) string s; cin>>s;
#define cini(i) int i; cin>>i;
#define cinll(l) ll l; cin>>l;
#define cind(d) double d; cin>>d;
#define cinai(a, n) vi a(n); fori(n) { cin>>a[i]; }
#define cinall(a, n) vll a(n); fori(n) { cin>>a[i]; }
#define cinas(s, n) vs s(n); fori(n) { cin>>s[i]; }
#define cinad(a, n) vd a(n); fori(n) { cin>>a[i]; }

typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<string> vs;
typedef vector<ll> vll;

const int MOD = 1e9 + 7;
int mul(const int v1, const int v2, int mod = MOD) {
	return (int) ((1LL * v1 * v2) % mod);
}

int toPower(int a, int p, int mod = MOD) {
	int res = 1;
	while (p != 0) {
		if (p & 1)
			res = mul(res, a, mod);
		p >>= 1;
		a = mul(a, a, mod);
	}
	return res;
}

int pl(int v1, int v2, int mod = MOD) {
	int res = v1 + v2;

	if (res < 0)
		res += mod;

	else if (res >= mod)
		res -= mod;

	return res;
}

int inv(const int x, const int mod = MOD) {
	return toPower(x, mod - 2);
}

const int N = 1000000;
vector<int> fac(N);

void initFac(int mod = MOD) {
	fac[1] = 1;
	for (int i = 2; i < N; i++) {
		fac[i] = mul(fac[i - 1], i, mod);
	}
}

int nCr(int n, int k) {
	if (k > n - k)
		k = n - k;

	int ans = 1;
	for (int i = 0; i < k; i++) {
		ans = mul(ans, n - i);
		ans = mul(ans, inv(i + 1));
	}
	return ans;
}

void solve() {
	cinll(n);
	cinll(a);
	cinll(b);

	/* Property: sum(nCr(n,k), 0, n) == 2^n
	 * ans== 2^n - nCr(n,a) - nCr(n,b)
	 * How to calc nCr(n,a) for n up to 1e9?
	 * Note that we can divide by multiplication with inverse.
	 */
	int ans = toPower(2, n);
	ans = pl(ans, -1);
	ans = pl(ans, -nCr(n, a));
	ans = pl(ans, -nCr(n, b));

	cout << ans << endl;
}

int main() {
	cin.tie(nullptr);
	initFac();
	std::ios::sync_with_stdio(false);
	solve();
}



Measured memory_bytes: 4224
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <climits>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
//#include <tuple>

#define INF INT_MAX>>1 
#define SIZE 100010
#define MOD 1000000007
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define rep2(i, from, to) for(int i=(from); i<(int)(to); i++)
#define all(obj) (obj).begin(), (obj).end()
#define lpair pair<ll, ll>
#define vint vector<ll>
#define vinput(name) for(int i=0; i<(int)(name.size()); i++) cin >> name[i];
#define voutput(name) for(int i=0; i<(int)(name.size()); i++) cout << name[i] << endl;
typedef long long ll;

using namespace std;

ll ans = 0;

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

	return 0;
}

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

using namespace std;

typedef long long int64;

int64 memo[1111][1111];

 

int64 dfs(int i,int cnt);

string t,b;

 

int main(){

  for(int i = 0;i < 1111;i++){

    for(int j = 0;j < 1111;j++){

      memo[i][j] = -1;

    }

  }

  t += '0';

  string a;

  cin >> a >> b;

  t += a;

  cout << dfs(0,0) << endl;

  return 0;

}

 

int64 dfs(int i,int cnt){

  int rec = 0;

  if(cnt == b.size())return 1;

  if(memo[i][cnt] != -1)return memo[i][cnt];

  for(int j = i + 1;j < t.size();j++){

    if(t[j] == b[cnt])rec = (rec + dfs(j,cnt + 1)) % 1000000007;

  }

  return memo[i][cnt] = rec % 1000000007;

}

Measured memory_bytes: 12832
#include<iostream>
#include<iomanip>
//#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
const ll INF = 1e17;
const ll P = 1e9+7;
const int Mmax = 2000000;
int N, M, S, T;
int U[Mmax], V[Mmax];
ll D[Mmax];

int main(){
	cin >> N >> M;
	cin >> S >> T;
	S--; T--;
	for(int i=0; i<M; i++){
		cin >> U[i] >> V[i] >> D[i];
		U[i]--;
		V[i]--;
	}

	vector<vector<pair<int, ll> > > graph(N);
	for(int i=0; i<M; i++){
		graph[U[i]].push_back(make_pair(V[i], D[i]));
		graph[V[i]].push_back(make_pair(U[i], D[i]));
	}

	vector<ll> dist(N, INF);
	priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > que;
	que.push(make_pair(0, S));
	dist[S] = 0;
	while(!que.empty()){
		ll d = que.top().first;
		int v = que.top().second;
		que.pop();
		for(int i=0; i<graph[v].size(); i++){
			int u = graph[v][i].first;
			int du = graph[v][i].second;
			if(d + du < dist[u]){
				dist[u] = d+du;
				que.push(make_pair(dist[u], u));
			}
		}
	}

	vector<pair<ll, int> > vec(N);
	for(int i=0; i<N; i++){
		vec[i] = make_pair(dist[i], i);
	}
	sort(vec.begin(), vec.end());

	vector<ll> dps(N);
	dps[S] = 1;
	for(int i=0; i<N; i++){
		int v = vec[i].second;
		for(int j=0; j<graph[v].size(); j++){
			int u = graph[v][j].first;
			ll du = graph[v][j].second;
			if(dist[u] != dist[v]+du) continue;
			dps[u] = (dps[u]+dps[v])%P;
		}
	}

	vector<ll> dpt(N);
	dpt[T] = 1;
	for(int i=0; i<N; i++){
		int v = vec[N-i-1].second;
		for(int j=0; j<graph[v].size(); j++){
			int u = graph[v][j].first;
			ll du = graph[v][j].second;
			if(dist[u]+du != dist[v]) continue;
			dpt[u] = (dpt[u]+dpt[v])%P;
		}
	}

	ll exclude = 0;
	for(int i=0; i<N; i++){
		int v = vec[i].second;
		if(2*dist[v] == dist[T]){
			//cout << v << endl;
			exclude += ((dps[v]*dps[v])%P)*((dpt[v]*dpt[v])%P);
			exclude %= P;
		}
		for(int j=0; j<graph[v].size(); j++){
			int u = graph[v][j].first;
			ll du = graph[v][j].second;
			if(dist[u] != dist[v]+du) continue;
			if(2*dist[u] > dist[T] && dist[T] > 2*dist[v]){
				//cout << v << " " << u << endl;
				//cout << dps[v] << " " << dpt[u] << endl;
				exclude += ((dps[v]*dps[v])%P)*((dpt[u]*dpt[u])%P);
				exclude %= P;
			}
		}
	}

	//cout << dps[T] << endl;
	cout << ((dps[T]*dps[T])%P - exclude + P)%P << endl;

	return 0;
}


Measured memory_bytes: 25460
k=int(input())
l=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

print(l[k-1])


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

using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLDLD;

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

const double eps=1e-5;
const long long INF=(LL)(1e9)*(LL)(1e9);

int gcd(int x,int y)
{
    if(y==0)
        return x;
    else
        return gcd(y,x%y);
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    FOR(i,1,3501)
    FOR(j,1,3501)
    {
        //cout<<i<<" "<<j<<endl;
        LL g=gcd(i*j, n);
        LL l=i*j/g*n;
        LL m=4*i*j/g-(i+j)*n/g;
        //cout<<g<<l<<m<<endl;
        if(m<=0) continue;
        if(l%m==0)
        {
            cout<<i<<" "<<j<<" "<<(l/m)<<endl;
            return 0;
        }
    }
}


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

#define ll long long

using namespace std;

ll popcount(ll n){
  if(n == 0) return 0;
  else return 1 + popcount(n & (n-1));
}

ll f(ll n){
 ll times = 0;
  
  while(n){
    n %= popcount(n);
    times++;
  }
  
  return times;
}

ll toggleBit(ll n, ll k){
  return (n ^ (1 << (k-1)));
}

ll binaryToDecimal(string x) 
{ 
    string num = x; 
    ll dec_value = 0; 
  
    ll base = 1; 
  
    ll len = num.length(); 
    for (ll i = len - 1; i >= 0; i--) { 
        if (num[i] == '1') 
            dec_value += base; 
        base = base * 2; 
    } 
  
    return dec_value; 
} 

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  int k;
  cin >> k;
  
  if(k%2 == 0 || k%5 == 0){
    cout << "-1";
    return 0;
  }
  
  else{
    ll s = 0;
    int i = 1;
    while(i <= (1e7)){
	  s = (s*10 + 7)%k;
      if(!s){
        cout << i;
        return 0;
      }
      i++;
    }
  }
  
  cout << "-1";
  
  return 0;
}



Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define is(a, b) a == b
#define len(v) ll(v.size())

//vector書き出し
template <class T>
void cout_vec(const vector<T> &vec1){
  rep(i,len(vec1)){
    cout<<vec1[i]<<' ';
  }
  cout<<'\n';
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;

int n,q;
string s;
vector<char> t(200010),d(200010);

bool left(int x){
  int now=x;
  rep(i,q){
    if(s[now]==t[i]){
      if(d[i]=='L') now--;
      else now++;
    }
    if(now==-1) return true;
  }
  return false;
}

bool right(int x){
  int now=x;
  rep(i,q){
    if(s[now]==t[i]){
      if(d[i]=='L') now--;
      else now++;
    }
    if(now==n) return true;
  }
  return false;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>q>>s;
    rep(i,q) cin>>t[i]>>d[i];
    int low=0,high=n,mid;
    while(high-low>1){
      mid=(low+high)/2;
      if(left(mid)) low=mid;
      else high=mid;
    }
    int low2=0,high2=n,mid2;
    while(high2-low2>1){
      mid2=(low2+high2)/2;
      if(right(mid2)) high2=mid2;
      else low2=mid2;
    }
    if(low>=high2) cout<<0<<endl;
    else cout<<n-(low+1)-(n-high2)<<endl;
}


Measured memory_bytes: 1104
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int Nmax=200010;

int main() {
	int A,B,C,X,cnt=0;
	cin >> A >> B >> C >> X;
	for(int i=0;i <= A;i++){
		for(int j=0;j <= B;j++){
			for(int k=0;k <= C;k++){
				if(500*i+100*j+50*k==X) cnt++;
			}
		}
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
from operator import add


class SegTree():
    def __init__(self, N, e, operator_func=add):
        self.e = e # 単位元
        self.size = N
        self.node = [self.e] * (2*N)
        self.operator_func = operator_func # 処理(add or xor max minなど)

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.operator_func(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size-1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.operator_func(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        # [l, r) についてqueryを求める
        x = self.e
        l += self.size
        r += self.size

        while l<r:
            if l&1:
                x = self.operator_func(x, self.node[l-1])
                l += 1
            if r&1:
                r -= 1
                x = self.operator_func(x, self.node[r-1])
            l >>= 1
            r >>= 1
        return x


N, K = map(int, input().split())
*P, = map(int, input().split())
INF = 10**12

tree_max = SegTree(N, -INF, operator_func=max)
tree_max.set_list(P)
tree_min = SegTree(N, INF, operator_func=min)
tree_min.set_list(P)
tree_monoinc = SegTree(N, INF, operator_func=min)
for i in range(N):
    tree_monoinc.update(i, P[i]-P[i-1] if i else 0)

def isMonoinc(l, r):
    # [l, r)
    l += 1
    return tree_monoinc.get(l, r)>=0

ans = N-K+1
orig = 0

for i in range(N-K+1):
    if isMonoinc(i, i+K):
        orig = 1
        ans -= 1
    elif i+K<N and tree_max.get(i, i+K+1)==P[i+K] and tree_min.get(i, i+K+1)==P[i]:
        ans -= 1

ans += orig
print(ans)


Measured memory_bytes: 104132
#include <stdio.h>
int main(void){
    int a, b, c;
    
    scanf("%d %d %d", &a, &b, &c);
    
    if(a == b && b == c){
        printf("1\n");
    }else if(a == b || b == c || a == c){
        printf("2\n");
    }else if(a != b && b != c && a != c){
        printf("3\n");
    }
    
}


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

using namespace std;

int main()
{
	int n, h, w;
	cin >> n >> h >> w;

	vector<int> a(n);
	vector<int> b(n);

	for(int i = 0; i < n; ++i){
		cin >> a[i] >> b[i];
		//cout << a[i] << ' ' << b[i] << "\n";
	}

	int counter = 0;

	for(int i = 0; i < n; ++i){
		if(h <= a[i] && w <= b[i]) ++counter;
		else continue;
	}

	cout << counter << "\n";

	return 0;
	
}

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

const MOD: i64 = 1_000_000_007;

fn main() {
    let mut sc = Scanner::new(std::io::stdin());
    let n: usize = sc.next().unwrap();
    let a: usize = sc.next().unwrap();
    let b: usize = sc.next().unwrap();
    let c = a^b;
    if c.count_ones() % 2 == 0 {
        println!("NO");
        return;
    }
    println!("YES");
    let res = recur(c, n);

    for i in 0..(1<<n)-1 {
        if (res[i] ^ res[i+1]).count_ones() != 1 {
            panic!();
        }
    }

    let mut first = true;
    for r in res.into_iter() {
        if !first {
            print!(" ");
        }
        print!("{}", r ^ a);
        first = false;
    }
    println!();

}

fn recur(c: usize, n: usize) -> Vec<usize> {
    if c >= (1<<n) {
        panic!("{} {}", c, n);
    }
    if c == 0 {
        panic!("zero");
    }
    if n == 1 {
        return vec![0, 1];
    }
    let mut pos = n;
    let mut nc = c;
    for i in 0..n {
        if ((c >> i) & 1) == 1 {
            pos = i;
            nc = (c & ((1<<i)-1)) | ((c >> i + 1) << i);
            break;
        }
    }
    let mut last = recur(nc ^ 1, n-1);
    for i in 0..1<<n-1 {
        last[i] ^= 1;
    }
    let first = recur(last[0], n-1);

    let mut res = vec![0; 1<<n]; 
    for i in 0..1<<n {
        if i < 1<<n-1 {
            res[i] = first[i];
        } else {
            res[i] = last[i - (1<<n-1)] ^ (1<<n-1);
        }
    }
    for i in 0..1<<n {
        res[i] = ((res[i] & ((1<<n-1)-1)) >> pos << (pos + 1)) | (res[i] >> n-1 << pos) | (res[i] & ((1<<pos)-1));
    }
    res
}


/// Scanner
///
/// # Example
/// ```
/// use contest::io::scanner;
/// let mut sc = scanner::Scanner::new("1 2 \n\n \r\t \n 3.5".as_bytes());
/// assert_eq!("1".to_string(), sc.next::<String>().unwrap());
/// assert_eq!(2, sc.next());
/// assert_eq!(3.5, sc.next());
/// assert_eq!(None, sc.next::<i32>());
/// ```

pub struct Scanner<R: io::Read> {
    br: io::BufReader<R>,
    // Read tokens are stored in reversed order per line.
    buf: Vec<String>,
}

impl<R: io::Read> Scanner<R> {
    pub fn new(r: R) -> Scanner<R> {
        Scanner {
            br: io::BufReader::new(r),
            buf: vec![],
        }
    }
    #[inline]
    pub fn next<T>(&mut self) -> Option<T>
        where T: std::str::FromStr,
              T::Err: std::fmt::Debug
    {
        self.next_string().map(|s| s.parse::<T>().expect("Parse failed: "))
    }
    fn next_string(&mut self) -> Option<String> {
        self.buf.pop().or_else(|| match self.update() {
            true => self.next_string(),
            false => None,
        })
    }
    #[inline]
    fn update(&mut self) -> bool {
        let mut s = String::new();
        let res = self.br.read_line(&mut s);
        match res.expect("I/O error.") {
            0 => false,
            _ => {
                self.buf = s.split_whitespace().map(|x| x.to_string()).rev().collect();
                true
            }
        }
    }
}


Measured memory_bytes: 7164
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  int N;cin >> N;
  vector<int> v(N);
  rep(i,N)cin >> v[i];
  vector<int> ans;
  rep(i,N){
    if(i==0 || ans[ans.size()-1] >= v[i]) ans.push_back(v[i]);
    else{
      int s = -1, e = ans.size()-1;
      while(e-s>1){
        int mid = (s+e)/2;
        if(ans[mid] < v[i])e = mid;
        else s = mid;
      }
      ans[e] = v[i];
    }
  }
  cout << ans.size() << endl;
  return 0;
}


Measured memory_bytes: 1276
#include<bits/stdc++.h>
#define FOR0(i,n) for(ll i=0;i<n;i++)
#define FOR1(i,n) for(ll i=1;i<=n;i++)
#define FORl(i,l,n) for(ll i=l;i<n;i++)
using namespace std;
#define pi pair<ll,ll>
#define pb push_back
#define ll long long
#define ld long double
#define ff first
#define ss second
#define mp make_pair
#define mst0(x) memset(x,0,sizeof(x));
#define vi vector<ll>
#define sync ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define sp <<" "<<
#define intmax 1e14
ll power(ll num,ll g,ll mod){
  if(g==0)return 1;
  if(g%2==1)return (num*power((num*num)%mod,g/2,mod))%mod;
  return power((num*num)%mod,g/2,mod);
}

int main(){
	int n;
	cin >> n;
	ll a[n];
	FOR0(i,n) cin >> a[i];
	ll dp[n+1][n+1];
	mst0(dp);
	ll prefix[n+1];
	mst0(prefix);
	FOR1(i,n) prefix[i] = prefix[i-1] + a[i-1];
	//dp[0][0] = 1;
	//int mod = 1e9 + 7;
	//int lim = 0;
	for (int l = n-1; l>=0 ;l-- ){
		for(int r = l; r < n; r++){
			if (l==r) dp[l][r] = 0;
			else{
				dp[l][r] = intmax;
				ll sum = prefix[r+1] - prefix[l];
				for (int i = l; i <= r; i++) dp[l][r] = min(dp[l][r], dp[l][i] + dp[i+1][r] + sum);
			}
		}
		// cout << endl;
		// cout << dp[i][0] << endl;
	}
	cout << dp[0][n-1] << endl;

}

Measured memory_bytes: 1536
/*May The Force Be With Me*/
#include <bits/stdc++.h>
#include <stdio.h>
#include <ctype.h>
#pragma GCC optimize ("Ofast")
#define ll long long
#define MOD 1000000007
#define endl "\n"
#define vll vector<long long>
#define mll map<long long,long long>
#define pll pair<long long, long long>
#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define pb push_back
#define f first
#define s second
#define inf INT_MAX
#define size_1d 10000000
#define size_2d 1000
//Snippets: delta, sieve, fastexp, dfs, bfs, dijkstra, floodfill

using namespace std;

char ch;

void Input() {
	cin >> ch;
}

void Solve() {
	if (isupper(ch))cout << "A";
	else cout << "a";
}

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

	ll T = 1;
	//cin >> T;
	//ll t = 1;
	while (T--) {
		Input();
		//cout << "Case " << t << ": ";
		Solve();
		//t++;
	}
	return 0;
}

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

using namespace std;

using int64 = long long;

int64 dp[87];

int64 rec(int idx)
{
  if(idx == 0) return (2);
  if(idx == 1) return (1);
  if(dp[idx]) return (dp[idx]);
  return (dp[idx] = rec(idx - 1) + rec(idx - 2));
}

int main()
{
  int N;
  cin >> N;
  cout << rec(N) << endl;
}


Measured memory_bytes: 256
import itertools
n,m,q = map(int,input().split())
qset = [list(map(int, input().split())) for i in range(q)]

aa=list(itertools.combinations_with_replacement(range(1,m+1), r=n))

ans=0

for i in range(len(aa)):
  score = 0
  for n in range(len(qset)):
    a=aa[i]
    abcd=qset[n]
    if a[abcd[1]-1]-a[abcd[0]-1]==abcd[2]:
      score=score+abcd[3]
  if ans<score:
    ans=score
print(ans)

Measured memory_bytes: 21492
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1'000'000'007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define REP(i, n) for(ll i=0; i<(ll)(n); i++)
#define REPD(i, n) for(ll i=n-1; 0<=i; i--)
#define FOR(i, a, b) for(ll i=a; i<(ll)(b); i++)
#define FORD(i, a, b) for(ll i=a; (ll)(b)<=i; i--)
#define ALL(x) x.begin(), x.end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main(){
    ll n, m, k; cin >> n >> m >> k;
    vector<ll> a(n+1, 0), b(m+1, 0);
    REP(i, n){
        ll x;   cin >> x;
        a[i+1] = a[i]+x;
    }
    REP(i, m){
        ll x;   cin >> x;
        b[i+1] = b[i]+x;
    }
    ll ac = upper_bound(ALL(a), k) - a.begin();
    ll res=0;
    REP(i, ac){
        ll times = a[i];
        ll bc = upper_bound(ALL(b), k-times) - b.begin();
        if(0<bc)
            res = max(res, i+bc-1);
    }
    cout << res << endl;
}


Measured memory_bytes: 6360
#include <iostream>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;

    int x, dist = 0;
    for (int i = 0; i < n; i++) {
        cin >> x;
        dist += min(2*x, 2*(k-x));
    }

    cout << dist << endl;
}


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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define what_is(x) cerr << #x << " is " << x << endl;
#define MT make_tuple
#define eb emplace_back
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

#define REP(i,a,b) for (int i = a; i <= b; i++)
#define FOR(i,n) for (int i=0;i < n ; i++)
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}
ll INF=1e9+7;
int main(){
	ll h , w,a,b,c;
	cin >> h >> w;
	ll ans=INF;
	for(ll i=1; i <h; i++){
		a=i*w;
		b=(w/2) *(h-i);
		c=w*h-a-b;
		ll x=min(min(a,b),c);
		ll y=max(max(a,b),c);
		ans=min(ans,y-x);
		b=(h-i)/2 * w;
		c=w*h-a-b;
		x=min(min(a,b),c);
		y=max(max(a,b),c);
		ans=min(ans,y-x);
	}
	for(ll j=1; j <w;j++){
		a=j*h;
		b=(h/2) *(w-j);
		c=w*h-a-b;
		ll x=min(min(a,b),c);
		ll y=max(max(a,b),c);
		ans=min(ans,y-x);
		ans=min(ans,w*h-3*h*(w/3));
		b=(w-j)/2 * h;
		c=w*h-a-b;
		x=min(min(a,b),c);
		y=max(max(a,b),c);
		ans=min(ans,y-x);
	}
	if(h%3==0 || w%3==0) ans=0;
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;

ll dp[100005][13];

int main() {
	string s;
	cin >> s;
	int n = s.size();
	dp[0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 13; j++) {
			if (s[i] == '?') {
				for (int d = 0; d < 10; d++) {
					dp[i+1][(j * 10 + d) % 13] += dp[i][j];
					dp[i+1][(j * 10 + d) % 13] %= MOD;
				}
			} else {
				int D = s[i] - '0';
				dp[i+1][(j * 10 + D) % 13] += dp[i][j];
				dp[i+1][(j * 10 + D) % 13] %= MOD;
			}
		}
	}
	cout << dp[n][5] << endl;
}

Measured memory_bytes: 13908
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 3e3 + 5;
const double eps = 1e-9;
char s[MAXN], t[MAXN], ans[MAXN];
int dp[MAXN][MAXN];
pii par[MAXN][MAXN];

int main()
{
    scanf("%s %s", s, t);
    int n = strlen(s), m = strlen(t);
    dp[0][0] = s[0] == t[0];
    if (s[0] == t[0])
        par[0][0] = {-1, -1};
    for (int i = 1; i < m; i++) {
        dp[0][i] = max(s[0] == t[i] ? 1 : 0, dp[0][i - 1]);
        if (s[0] == t[i])
            par[0][i] = {-1, i - 1};
        else
            par[0][i] = {0, i - 1};
    }
    for (int i = 1; i < n; i++) {
        dp[i][0] = max(s[i] == t[0] ? 1 : 0, dp[i - 1][0]);
        if (s[i] == t[0])
            par[i][0] = {i - 1, -1};
        else
            par[i][0] = {i - 1, 0};
    }
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = max(dp[i - 1][j - 1] + (s[i] == t[j]), max(dp[i - 1][j], dp[i][j - 1]));
            if (dp[i][j] == dp[i - 1][j])
                par[i][j] = {i - 1, j};
            else if (dp[i][j] == dp[i][j - 1])
                par[i][j] = {i, j - 1};
            else
                par[i][j] = {i - 1, j - 1};
        }
    }
    int i = n - 1, j = m - 1, len = dp[i][j];
    while (i > -1 && j > -1) {
        if (par[i][j].fi != i && par[i][j].se != j)
            ans[--len] = s[i];
        if (i == 0 && j == 0)
            break;
        tie(i, j) = par[i][j];
    }
    printf("%s\n", ans);
    return 0;
}


Measured memory_bytes: 105984
def e_who_says_a_pun():
    N = int(input())
    S = input()

    def z_algorithm(string):
        n = len(string)
        ret = [0] * n
        i, j = 1, 0
        while i < n:
            while i + j < n and string[j] == string[i + j]:
                j += 1
            ret[i] = j
            if j == 0:
                i += 1
                continue
            k = 1
            while i + k < n and k + ret[k] < j:
                ret[i + k] = ret[k]
                k += 1
            i += k
            j -= k
        return ret

    ans = 0
    for i in range(N):
        t = S[i:N]
        lcp = z_algorithm(t)  # Longest Common Prefix
        for j in range(len(t)):
            ans = max(ans, min(lcp[j], j))
    return ans

print(e_who_says_a_pun())

Measured memory_bytes: 49120
#include"bits/stdc++.h"
using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;

struct _ { ios_base::Init i; _() { cin.sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10); } } ___;
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');
	cerr.write(names, comma - names) << " : " << arg1 << " | ";
	__f(comma + 1, args...);
}

#define pii pair<int,int>
#define oset tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ff first
#define ss second
#define endll '\n'
#define rep(i,n) for(int i=0;i++<n;)
#define scl(i) scanf("%lld",&i);
#define int long long int
#define all(n) n.begin(),n.end()
#define mem(n,i) memset(n,i,sizeof n);
//vector<vector<int>>arr(n + 5, vector<int>(m + 5,0));

signed main()
{

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int a, b; cin >> a >> b;
	if (b & 1) cout << "No";
	else if (b > (a << 2)) cout << "No";
	else if (b < (a << 1)) cout << "No";
	else cout << "Yes";
}

Measured memory_bytes: 3648
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b)-1);i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int, int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))

int main(void){
	int n, x; scanf("%d%d", &n, &x);
	lli ans = 0;
	int a[n];
	rep(i, n) scanf("%d", &a[i]);

	rep(i, n-1) if(a[i] + a[i+1] > x){
		ans += (a[i+1] + a[i] - x);
		if(a[i] <= x){
			a[i+1] = x - a[i];
		}else{
			a[i+1] = 0;
			a[i] = x;
		}
	}
	
	cout << ans << endl;
	return 0;
}

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

int main() {
    int N, K, C;
    string S;
    cin >> N >> K >> C >> S;
    int l[K], r[K], idx = 0;
    for (int i = 0; i < N; i++) {
        if (S[i] == 'x') continue;
        l[idx++] = i;
        if (idx == K) break;
        i += C;
    }
    idx = K - 1;
    for (int i = N - 1; i >= 0; i--) {
        if (S[i] == 'x') continue;
        r[idx--] = i;
        if (idx < 0) break;
        i -= C;
    }
    for (int i = 0; i < K; i++) {
        if (l[i] == r[i]) cout << l[i]+1 << endl;
    }
}

Measured memory_bytes: 3332
#include "bits/stdc++.h"
using namespace std;
#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define PI 3.1415926535
typedef long long ll;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<Pll> vPll;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<double>> vvd;
typedef vector<vector<Pi>> vvPi;
typedef priority_queue<int, vector<int>, greater<int>> pqli;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi>> pqlP;
string YN(bool y) { return (y?"YES":"NO"); }
string yn(bool y) { return (y?"Yes":"No"); }
string ON(bool y) { return (y?"OK":"NG"); }
int main(void)
{
	bool flag=true;

	vvi c(3, vi(3));

	rep(i, 3){
		rep(j, 3) cin>>c[i][j];
	}
	if(c[0][0]-c[0][1]!=c[1][0]-c[1][1]||c[1][0]-c[1][1]!=c[2][0]-c[2][1]) flag=false;

	if(c[0][1]-c[0][2]!=c[1][1]-c[1][2]||c[1][1]-c[1][2]!=c[2][1]-c[2][2]) flag=false;

	if(c[0][0]-c[0][2]!=c[1][0]-c[1][2]||c[1][0]-c[1][2]!=c[2][0]-c[2][2]) flag=false;

	if(c[0][0]-c[1][0]!=c[0][1]-c[1][1]||c[0][1]-c[1][1]!=c[0][2]-c[1][2]) flag=false;

	if(c[1][0]-c[2][0]!=c[1][1]-c[2][1]||c[1][1]-c[2][1]!=c[1][2]-c[2][2]) flag=false;

	if(c[0][0]-c[2][0]!=c[0][1]-c[2][1]||c[0][1]-c[2][1]!=c[0][2]-c[2][2]) flag=false;

	cout<<yn(flag)<<endl;
}

Measured memory_bytes: 256
r,c = map(int,input().split())
l=[]
SY = 0
for i in range(r):
    a = list(map(int,input().strip().split()))
    l.append(a)
for j in l:
    j.append(0)
l.append([0]*(c+1))

for i in range(r):
    sx = 0 
    for j in range(c):
        sx +=l[i][j]
    l[i][c] = sx
   
for j in range(c):
    sy = 0
    for i in range(r):
        sy +=l[i][j]
    l[r][j] =sy
    SY +=sy
l[r][c] = SY

for k in l:
    print(*k)


Measured memory_bytes: 6228
N, X = map(int, input().split())
L = [int(l) for l in input().split()]
if sum(L) <= X:
  print(N+1)
  exit()
D = 0
ans = 1
for i in range(N):
  D += L[i]
  if D <= X:
    ans += 1
  else:
    print(ans)
    exit()


Measured memory_bytes: 3064
#include<cstdio>
#include <iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include <string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
using namespace std;

int main() {
	int h, w;
	cin >> h >> w;
	string s[110];
	rep(i, h) cin >> s[i];
	rep(i, w+2) cout << "#";
	cout << endl;
	rep(i, h) {
		cout << "#" << s[i] << "#" << endl;
	}
	rep(i, w+2) cout << "#";
	cout << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define FIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef pair<int, int> PII;

ll getAns(ll mn, vector<ll>& v){
    if(v.size() == 0){
        return (ll)-2;
    }
    ll start = 0, en = v.size()-1, ans = -1;
    while(start <= en){
        ll mid = start + en;
        mid >>= 1;
        if(v[mid] >= mn){
            ans = v[mid];
            en = mid - 1;
        }else{
            start = mid + 1;
        }
    }
    return ans;
}

int main(){
    FIO;
    string s, t;
    cin >> s >> t;
    vector<ll> alpha[30];
    for(ll i = 0 ; i < s.size() ; i++){
        alpha[s[i] - 'a'].push_back(i);
    }
    ll ans = 1, prev = -1;
    for(ll i = 0 ; i < t.size() ; i++){
        ll x = t[i] - 'a';
        ll nxt = getAns(prev + 1, alpha[x]);
        if(nxt == -2){
            cout << -1 << endl;
            return 0;
        }
        if(nxt == -1){
            prev = -1;
            ll index = getAns(prev+1, alpha[x]);
            prev = index;
            ans++;
        }else{
            prev = nxt;
        }
    }
    ans *= s.size();
    ans -= (s.size() - prev - 1);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1736
#include<stdio.h>
#define NIL -1 /*???????????¶?§???????*/
#define MAX 100
#define WHITE 1
#define GRAY 2
#define BLACK 3

struct node{
 int list2[MAX];  
  int color;
  int number;
};


typedef struct node  Node;/*list1??????????????????????????????*/

void dfs(Node *);
void visit(Node *,int);

Node list1[MAX];          /*?????????1?§???????*/

int num,degree,time,d[MAX],f[MAX];
main()
{
  int i,j;
  scanf("%d",&num);
  for(i=1;i<=num;i++)
    {
      scanf("%d",&list1[i].number);
      scanf("%d",&degree);
      list1[i].list2[degree+1] = NIL;  /*???list???degree??????????????????NIL?????\??????*/
      if(degree != 0)
	{
      for(j=1;j<=degree;j++)
		{
	  scanf("%d",&list1[i].list2[j]);
		}
	}/*if degree ?????¨???*/
    }/*????????§?????????????????????*/

  dfs(list1);
  

  for(i=1;i<=num;i++)
    {
      printf("%d %d %d\n",i,d[i],f[i]);
    }
  return 0;
}

void dfs(Node* list1)
{
  int i,j;
  for(i=1;i<=num;i++)
    {
      list1[i].color = WHITE;
      time = 0;
    }

  for(j=1;j<=num;j++)
    {
      if(list1[j].color==WHITE) visit(list1,j);

    }
}

void visit(Node* list1, int j)
{
  int i;
  list1[j].color = GRAY;
  d[j] = ++time;
  for(i=1;i<=MAX;i++)
    {
      if(list1[j].list2[i]==NIL)break;
      else if(list1[list1[j].list2[i]].color == WHITE) visit(list1,list1[j].list2[i]);
    }
  
  list1[j].color = BLACK;
  f[j] = ++time;
    
  
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int gcd(int x, int y) { return (x % y) ? gcd(y, x % y) : y; }
const double PI = 3.14159265358979323846;
int main() {
  string s, t;
  cin >> s >> t;
  int size = s.size();
  // cout << size << endl;
  int f = 0;
  for (int i = 0; i < size; i++) {
    if (s[i] != t[i]) f++;
  }
  if (f == 0) cout << "Yes";
  if (f != 0) cout << "No";
  return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define repeat(i, n) for(int (i) = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const double EPS = numeric_limits<double>::epsilon();

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; }

ll f(ll x, ll c, ll d) {
	ll result = x;
	result -= x / c;
	result -= x / d;
	result += x / lcm(c, d);
	return result;
}

int main() {
	ll A, B, C, D;
	cin >> A >> B >> C >> D;

	ll result = f(B, C, D) - f(A-1, C, D);

	cout << result << endl;
	return 0;
}


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

using namespace std;
using ll = long long;

//container util
#define SORT(c) sort((c).begin(),(c).end())
#define all(a) (a).begin(), (a).end()

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

//print
#define pv(val) cerr << #val << '=' << (val) << endl

const int INF = 1e9;

int main(void){

	int N, M; cin >> N >> M;

	vector<int> L(M);
	vector<int> R(M);
	REP(i,M) cin >> L[i] >> R[i];

	REP(i,M) L[i]--;
	REP(i,M) R[i]--;

	vector<int> cnt(N+1, 0);

	REP(i,M){
		cnt[L[i]]++;
		cnt[R[i]+1]--;
	}

	FOR(i,1,N+1){
		cnt[i] += cnt[i-1];
	}

	int ans = 0;
	REP(i,N+1){
		if(cnt[i] == M) ans++;
	}

	cout << ans << endl;


	return 0;

}


Measured memory_bytes: 1408
// All Heil Fire Lord Zuko

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

const int N = 100 * 1000 + 19;

string s;
int n;
int a[N];

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
    int ans = 0;
	for (int i = 0; i < n; i++) {
		int x = i, y = i;
		while (a[x] <= a[x + 1]) {
			x++;
			if (x == n)
				break;
		}
		while (a[y] >= a[y + 1]) {
			y++;
			if (y == n)
				break;
		}
		i = max(x, y);
		ans++;
	}
	cout << ans;
    return 0;
}


Measured memory_bytes: 640
N=int(input())
h=list(map(int,input().split()))
INF=10**9+1
dp=[INF]*(N)
dp[0]=0
dp[1]=abs(h[1]-h[0])
for i in range(2,len(h)):
  dp[i]=min(dp[i-2]+abs(h[i]-h[i-2]),dp[i-1]+abs(h[i]-h[i-1]))
print(dp[N-1])

Measured memory_bytes: 13928
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
#include<sstream>
#include<algorithm>
#include<stack>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define rep(i,n) for(int i=0;(i)<(n);i++)
#define rep1(i,n) for(int i=1;(i)<=(n);i++)
#define mst(a,b) memset(a,b,sizeof(a))
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define dbg(a) cout<<"* "<< #a <<" : "<<a<<endl
#define fr first
#define se second
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ls x<<1
#define rs x<<1|1
#define lowbit(x) x&(-x)
#define ac cout<<ans<<endl
//#define DEBUG 0
using namespace std;
const double pi=acos(-1.0);
const double eps=1e-6;
const ull hashp=1e7+19;
const ll INF=0x3f3f3f3f3f3f3f3fll;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int maxn=300+100;
int a[maxn];
ll dp[maxn][maxn];
void solve()
{
	int n,k;
	scdd(n,k);
	rep1(i,n)scd(a[i]);
	mst(dp,inf);
	dp[0][k]=0;
	n++;
	rep1(i,n){
		rep(u,k+1){
			rep(j,i){
				if(u+i-j-1>k)continue;
				dp[i][u]=min(dp[i][u],dp[j][u+i-j-1]+1ll*max(0,a[i]-a[j]));
				//if(u<k)dp[i][u]=min(dp[i][u],dp[i-1][u+1]);
			}
		}
	}
	//dbg(dp[1][1]);
	ll ans=INF;
	rep(i,k+1)ans=min(ans,dp[n][i]);
	ac;
}
int main(){
    //IOS;
    //freopen("D://data.txt","r",stdin);
    solve();
    return 0;
}


Measured memory_bytes: 1536
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <math.h>
#include <deque>
using ll = long long;
using namespace std;

int main(){
    ll n, k, ans = 1;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        if(!i) ans *= k;
        else ans *= k-1;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#pragma warning(disable:4786)
#pragma warning(disable:4996)
#include<list>
#include<bitset>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<functional>
#include<string>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<utility>
#include<fstream>
#include<sstream>
#include<cmath>
#include<stack>
#include<assert.h>
using namespace std;

#define MEM(a, b) memset(a, (b), sizeof(a))
#define CLR(a) memset(a, 0, sizeof(a))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define ABS(X) ( (X) > 0 ? (X) : ( -(X) ) )
#define S(X) ( (X) * (X) )
#define SZ(V) (int )V.size()
#define FORN(i, n) for(i = 0; i < n; i++)
#define FORAB(i, a, b) for(i = a; i <= b; i++)
#define ALL(V) V.begin(), V.end()
#define IN(A, B, C)  ((B) <= (A) && (A) <= (C))

typedef pair<int,int> PII;
typedef pair<double, double> PDD;
typedef vector<int> VI;
typedef vector<PII > VP;

#define AIN(A, B, C) assert(IN(A, B, C))

//typedef int LL;
typedef long long int LL;
//typedef __int64 LL;

int n;
int ma, mb;
struct Prod {
	int a, b, c;
};
Prod p[100];

int dp[41][401][401];

int main()
{
	scanf("%d %d %d", &n, &ma, &mb);
	for (int i = 0; i < n; i++) {
		scanf("%d %d %d", &p[i].a, &p[i].b, &p[i].c);
	}

	MEM(dp, -1);

	dp[0][0][0] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= 400; j++) {
			for (int k = 0; k <= 400; k++) {
				if (dp[i][j][k] == -1) continue;
				int cost = dp[i][j][k] + p[i].c;
				if (dp[i + 1][j + p[i].a][k + p[i].b] == -1) dp[i + 1][j + p[i].a][k + p[i].b] = cost;
				else dp[i + 1][j + p[i].a][k + p[i].b] = MIN(dp[i + 1][j + p[i].a][k + p[i].b], cost);

				cost = dp[i][j][k];
				if (dp[i + 1][j][k] == -1) dp[i + 1][j][k] = cost;
				else dp[i + 1][j][k] = MIN(dp[i + 1][j][k], cost);
			}
		}
	}

	int ans = -1;
	for (int i = 1; i <= 400; i++) {
		for (int j = 1; j <= 400; j++) {
			if (i * mb == j * ma && dp[n][i][j] != -1)
			{
				if (ans == -1) ans = dp[n][i][j];
				else ans = MIN(ans, dp[n][i][j]);
			}
				
		}
	}

	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 26112
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <queue>


using namespace std;
#define INF 0x3f3f3f3f3f
#define ll long long
#define pr(x) (cerr << #x << ' ' << x << ' ')
#define prln(x) (cerr << #x << ' ' << x << endl)


int main()
{
	#ifdef LOCAL
		freopen("in.txt", "r", stdin);
	#endif // LOCAL
	string str;
	cin >> str;
	int cnt = 0;
	for (const auto &ele : str) {
		if (ele == '+') {
			++cnt;
		}else {
			--cnt;
		}
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256