akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define REP(i,x,n) for(int i=x;i<(int)n;i++)
#define rep(i,n) REP(i,0,n)
#define sp(p) cout<<setprecision(16)<<fixed<<p<<endl;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(rall(a))
#define UNIQ(a) unique(all(a))
#define UNIQNUM(a) UNIQ(a)-a.begin()
#define UNIQIT(a) a.erase(UNIQ(a), a.end());
#define VOUT(v,i) rep(i,v.size())cout<<v[i]<<(i==v.size()-1?"\n":" ");
#define vout(v) VOUT(v,z);
#define vdbg(v,i) cout<<#v<<": ";for(int i=0;i<(int)v.size();i++){cout<<v[i]<<" ";}cout<<"\n";
#define vmin(v) *min_element(all(v))
#define vmax(v) *max_element(all(v))
#define vsum(v) accumulate(all(v), 0LL)
#define MOUT(m,r,c) rep(i,r){rep(j,c){cout<<m[i][j]<<" ";}cout<<endl;}
#define mout(m) MOUT(m,m.size(),m[0].size())
#define debg(a) cout<<#a<<": "<<a<<endl;
#define show(a) for(cont &y:a){for(cont &x:y){cout<<x<<" ";}cout<<endl;}
#define digit(a) to_string(a).length();
template<class T>inline int out(const T &t){ print(t); putchar('\n'); return 0; }
// template<class T>inline T gcd(T a,T b){if(b==0)return a; return(gcd(b,a%b));}
// template<class T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
bool is_palindrome(string s){return s == string(s.rbegin(),s.rend());}
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef vector<ll> V;
typedef vector<vector<ll>> VV;
// const long long MOD=1000000007;
const long long INF = 1e18;
#define EPS (1e-7)
#define PI (acos(-1))
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;
}



int main(){
    std::vector<long long> x(5);
    for(int i = 0 ; i < 5 ; i++){
        scanf("%lld",&x[i]);
        if(x[i]==0){
            cout << i+1 << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3672
/*dismint|jjc*/
#include <bits/stdc++.h>
using namespace std;
#define forl(V, S, E) for(ll V = S; V < E; V++)
#define ford(V, S, E) for(int V = S; V >= E; V--)
#define fore(E, X) for(auto &E:X)
#define println(X) cout << X << endl
#define printe(X) for(auto &E:X) cout << E << " "; cout << endl
typedef unordered_map<int, unordered_set<int>> graph;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	ll n; cin >> n;
	vector<ll> nums(n); fore(e, nums) cin >> e;
	ll ans = 0;
	map<ll, ll> occ, occ2;
	forl(i, 0, n) {
		occ[i+1ll+nums[i]]++;
		occ2[i+1ll-nums[i]]++;
	}
	fore(e, occ) {
		ll oth = occ2[e.first];
		ll val = e.second;
		ans += val*oth;
	}
	println(ans);
}


Measured memory_bytes: 39100
'''input
2
1 5
'''
# A coding delight https://ideone.com/m98Hht
from sys import stdin
input = stdin.readline


# main starts
s = input().strip()
if s == 'SUN':
	print(7)
elif s == 'MON':
	print(6)
elif s == 'TUE':
	print(5)
elif s == 'WED':
	print(4)
elif s == 'THU':
	print(3)
elif s == 'FRI':
	print(2)
else:
	print(1)

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

#define PII pair<int, int>
#define VI vector<int>
#define VPII vector<PII>
#define LL long long
#define LD long double
#define f first
#define s second
#define MP make_pair
#define PB push_back
#define endl '\n'
#define ALL(c) (c).begin(), (c).end()
#define SIZ(c) (int)(c).size()
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, b, e) for (int i = (b); i <= (int)(e); i++)
#define FORD(i, b, e) for (int i = (b); i >= (int)(e); i--)
#define ll long long
#define st f
#define nd s
#define pb PB
#define eb emplace_back
#define mp make_pair
#define siz(c) SIZ(c)
const int inf = 1e9 + 7;
const LL INF = 1e18L + 7;

#define sim template<class n
sim, class s> ostream & operator << (ostream &p, pair<n, s> x)
{return p << "<" << x.f << ", " << x.s << ">";}
sim> auto operator << (ostream &p, n y) ->
typename enable_if<!is_same<n, string>::value, decltype(y.begin(), p)>::type
{int o = 0; p << "{"; for (auto c : y) {if (o++) p << ", "; p << c;} return p << "}";}
void dor() {cerr << endl;}
sim, class...s> void dor(n p, s...y) {cerr << p << " "; dor(y...);}
sim, class s> void mini(n &p, s y) {if (p > y) p = y;}
sim, class s> void maxi(n &p, s y) {if (p < y) p = y;}

#ifdef DEB
#define debug(...) dor(__FUNCTION__, ":", __LINE__, ": ", __VA_ARGS__)
#else
#define debug(...)
#endif

#define I(x) #x " = ", (x), " "
#define A(a, i) #a "[" #i " = ", i, "] = ", a[i], " "

#define int ll
const int N = 2e5+7;

int n, ans;

string s;

int dp[N];

int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);

	cin >> s;
	n = siz(s);
	s = '#' + s;

	for(int i = n; i >= 1; --i)
	{
		if(s[i]=='A')
		{
			dp[i] = dp[i+1];
			ans += dp[i];
		}
		else if(s[i]=='B')
		{
			if(s[i+1]=='C')
				dp[i] = 1 + dp[i+2];
			else
				dp[i] = 0;
		}
		else
			dp[i] = 0;
	}

	cout << ans << endl;
}

Measured memory_bytes: 2128
#include<stdio.h>

int zorome(int n)
{

int ans = 0;
while(ans == 0)
{
if(n % 111 == 0)
{
ans = n;
}
n++;
}
return ans;
}

int main()
{
int n = 0,ans = 0;
scanf("%d",&n);

ans = zorome(n);

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

Measured memory_bytes: 128
N, D = list(map(int, input().split()))
X = [list(map(int, input().split())) for i in range(N)]

ans = 0
for i in range(N):
  for j in range(i + 1, N):
    d = 0
    for k in range(D):
      d += pow(X[i][k] - X[j][k], 2)
    if pow(int(d ** 0.5), 2) == d:
      ans += 1

print(ans)

Measured memory_bytes: 38384
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#define fr(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
inline int read(){
	char c=getchar();int fh=0;
	while(!isdigit(c))c=getchar();
	while(isdigit(c))fh=(fh<<1)+(fh<<3)+(c^48),c=getchar();
	return fh;
}

int n,m;
const int N=1e5+5;
const int M=2e5+5;

int head[N],tot;
struct node{int to,nxt,val;}e[2*M];
inline void add(int u,int v,int w){e[++tot]=(node){v,head[u],w};head[u]=tot;}

queue<int> q;
bool use[N];
long long dis[N];
bool spfa(int st){
	while(!q.empty())q.pop();
	dis[st]=0;q.push(st);use[st]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to,w=e[i].val;
			if(dis[v]==1e17){
				dis[v]=dis[u]+w;
				if(!use[v])q.push(v),use[v]=1;
			}
			else if(dis[v]!=dis[u]+w)return 0;
		}
	}
	return 1;
}

int main(){
	n=read(),m=read();
	fill(dis+1,dis+n+1,1e17);
	fr(i,1,m){
		int u=read(),v=read(),w=read();
		add(u,v,w);
		add(v,u,-w);
	}
	fr(i,1,n)
	 if(!use[i]&&!spfa(i))
	  return puts("No"),0;
	puts("Yes");
	return 0;
}

Measured memory_bytes: 6656
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#define int long long
#define iris 1000000009
using namespace std;

string s[64];
int t[64];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	string ouo;
	int n,i,sum;
	cin>>n;
	sum=0;
	for(i=0;i<n;i++)
	{
		cin>>s[i]>>t[i];
		sum+=t[i];
	}
	cin>>ouo;
	for(i=0;i<n;i++)
	{
		sum-=t[i];
		if(ouo==s[i])
			break;
	}
	cout<<sum<<'\n';
	
	
	return 0;
}


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

typedef long long ll;

int n;
int t[111111];
int a[111111];

int m[111111];
bool tk[111111];
bool ak[111111];

int main(void){
  scanf("%d",&n);
  for(int i = 0; i < n; i++)
    scanf("%d",t+i);
  for(int i = 0; i < n; i++)
    scanf("%d",a+i);

  memset(tk,false,sizeof(tk));
  memset(ak,false,sizeof(ak));

  tk[0] = ak[n-1] = true;
  for(int i = 0; i < n; i++){
    if(i && t[i] != t[i-1]){
      tk[i] = true;
    }
    if(i < n-1 && a[i] != a[i+1]){
      ak[i] = true;
    }
    m[i] = min(t[i],a[i]);
  }

  ll ans = 1;
  for(int i = 0; i < n; i++){
    if( (tk[i] && ak[i] && t[i] != a[i]) ||
	(tk[i] && t[i] > a[i]) ||
	(ak[i] && a[i] > t[i]) ){
      cout << 0 << endl;
      return 0;
    }

    if(!tk[i] && !ak[i]){
      ans *= m[i];
    }
    ans %= 1000000007;
  }
  cout << ans << endl;
}


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

using namespace std;

int main()
{
    int n, a[100010] = {};
    cin >> n;
    for (int i=0; i<n; i++)
        cin >> a[i];

    sort(a, a+n);

    int t = -1, cnt = 0, ans = 0;
    for (int i=0; i<=n; i++) {
        if (a[i] != t) {
            ans += cnt % 2;
            cnt = 0;
            t = a[i];
        }
        cnt++;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 640
#include<iostream>

using namespace std;

int main() {
	int num[33] = {0, 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 };
	int k;
	cin >> k;
	cout << num[k];
	return 0;
}

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

using namespace std;

const int maxn = 1e5;
pair<int, int> pos[maxn];
int sum[maxn];

int cost(int i, int j) {
    return abs(pos[i].first - pos[j].first) + abs(pos[i].second - pos[j].second);
}
int main(){
    int H, W, D;
    cin >> H >> W >> D;
    memset(sum, 0, sizeof(sum));

    for(int i = 1; i <= H; i++) {
        for(int j = 1; j <= W; j++) {
            int p;
            cin >> p;
            pos[p] = pair<int, int>(i, j);
        }
    }

    for(int i = D + 1; i <= H * W; i++){
        sum[i] = sum[i - D] + cost(i - D, i);
    }

    int Q;
    cin >> Q;
    while(Q--){
        int L, R;
        cin >> L >> R;
        cout << (sum[R] - sum[L]) << endl;
    }
    return 0;
}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
 using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
 int main(){
  string s;
   int n;
   cin>>n>>s;
   bool ans=true;
   if(n%2==1)
     ans=false;
   else{
   rep(i,n/2){
    if(s.at(i)!=s.at(i+n/2))
      ans=false;
   }
  }
   if(ans)
    cout<<"Yes"<<endl;
   else
    cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
int n,flg,_min=2e9;
LL ans;
int main(){
  scanf("%d",&n);
  for(int i=1;i<=n;i++){
    int x,y; scanf("%d%d",&x,&y);
    ans+=y;
    if(x>y) _min=min(_min,y);
    if(x!=y) flg=1;
  }
  printf("%lld\n",flg?ans-_min:0);
  
  return 0;
}


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

using namespace std;
typedef long long ll;

ll N,K;
ll MOD = 1e9+7;

int main(){
    cin >> N >> K;
    ll sum = 0;
    for(ll i=K;i<=N+1;i++){
        ll a = N * i;
        a %= MOD;
        ll b = i * (i-1);
        b %= MOD;
        sum += a - b + 1;
        sum %= MOD;
        sum += MOD;
        sum %= MOD;
    }
    cout << sum << endl;
    return 0;
}

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

using namespace std;

int main() {
    int N, W;
    cin >> N >> W;
    long long int dp[N + 1][W + 1];
    long long int values[N];
    int weights[N];

    for (int r = 0; r < W + 1; r++)
    {
        dp[0][r] = 0;
    }

    for (int c = 0; c < N + 1; c++)
    {
        dp[c][0] = 0;
    }

    for (int i = 0; i < N; i++)
    {
        scanf("%i %lli", &weights[i], &values[i]);
    }

    for(int item = 1; item <= N; item++)
    {
        for(int capacity = 1; capacity <= W; capacity++)
        {
            long long int maxWithoutItem = dp[item - 1][capacity];
            long long int maxWithItem = 0;

            int weightOfItem = weights[item - 1];

            if (capacity >= weightOfItem)
            {
                maxWithItem = values[item - 1];
                int remainingCapacity = capacity - weightOfItem;
                maxWithItem += dp[item - 1][remainingCapacity];
            }

            dp[item][capacity] = max(maxWithoutItem, maxWithItem);
        }
    }

    cout << dp[N][W];
}


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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair
#define F first
#define S second

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<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


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

    i64 cnt = 0;
    REPS(n, N) {
        if (n % 2 == 0) continue;

        i64 ndiv = 0;
        for (i64 i = 1; i <= n; i += 2) {
            if (n % i == 0) ndiv++;
        }
        if (ndiv == 8) cnt++;
    }
    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 256
//============================================================================
// Name        : ATcoder.cpp
// Author      : Akari Fujii
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cctype>
#include <string>
#include<algorithm>
using namespace std;
typedef long long ll;
int main() {

	string s;
	cin>>s;






	cout<<"2018";

	for(int i=4; i<s.size(); ++i){
		cout<<s[i];
	}
	cout<<endl;



	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MAX = (2e5)+1;
const long long MOD = (1e9)+7;

int n, x, y, c[MAX], w[MAX];
long long ans = 1, fact[MAX];
vector<int> par, el[MAX];
vector<vector<pair<int,int> > > a;

long long modPow(long long b, long long e) {
	long long ret = 1;
	while(e) {
		if(e & 1) ret = (ret*b)%MOD;
		b = (b*b)%MOD;
		e >>= 1;
	}
	return ret;
}

int root(int v) { return (par[v] == v ? v : par[v] = root(par[v])); }

void merge(int u, int v) {
	if((u = root(u)) == (v = root(v))) return;
	if(el[u].size() < el[v].size()) swap(u, v);
	el[u].insert(el[u].end(), el[v].begin(), el[v].end());
	el[v].clear();
	par[v] = u;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> x >> y;
	fact[0] = 1;
	for(int i = 1; i <= n; i++) fact[i] = (fact[i-1]*i)%MOD;
	par.resize(n);
	a.resize(n);
	iota(par.begin(), par.end(), 0);
	for(int i = 0; i < n; i++) {
		cin >> c[i] >> w[i];
		c[i]--;
		a[c[i]].emplace_back(w[i], i);
		el[i].push_back(i);
	}
	for(auto& v: a) sort(v.begin(), v.end());
	sort(a.begin(), a.end(), [] (auto& a, auto& b) {
		if(a.empty()) return false;
		if(b.empty()) return true;
		return a[0].first < b[0].first;
	});
	for(int i = n-1; i >= 0; i--) if(a[i].empty()) a.pop_back(); 
	for(int k = 0; k < a.size(); k++) for(int i = 1; i < a[k].size(); i++) {
		if(a[k][i].first+a[k][0].first <= x || (k && a[k][i].first+a[0][0].first <= y)
				|| (!k && a.size() > 1 && a[k][i].first+a[1][0].first <= y)) merge(a[k][i].second, a[k][0].second);
	}
	for(int k = 1; k < a.size(); k++) if(a[k][0].first+a[0][0].first <= y) merge(a[k][0].second, a[0][0].second);
	for(int rt = 0; rt < n; rt++) if(!el[rt].empty()) {
		map<int,int> f;
		long long res = fact[el[rt].size()];
		for(int v: el[rt]) f[c[v]]++;
		for(auto p: f) res = (res*modPow(fact[p.second], MOD-2))%MOD;
		ans = (ans*res)%MOD;
	}
	cout << ans;
}


Measured memory_bytes: 30628
#include<cstdio>
using namespace std;
const int mod=1e9+7;
int n,k;
long long f[2005][2005],s[2005],ans;
long long ksm(long long a,long long b)
{
  long long ans=1;
  while(b)
  {
  	if(b&1)  ans=ans*a%mod;
  	a=a*a%mod;b>>=1;
  }
  return ans;
}
int main()
{
  //FILE *fi,*fo;
  //fi=fopen("forget.in","r");
  //fo=fopen("forget.out","w"); 
  scanf("%d%d",&n,&k);f[0][n+1]=1;
  for(int i=1;i<=k;i++)
  {
	s[n+1]=f[i-1][n+1];  
	for(int j=n;j>=1;j--)  s[j]=(f[i-1][j]+s[j+1])%mod;
	for(int j=1;j<=n-i+1;j++)  f[i][j]=s[j];
  }
  if(n>k)  ans=(((f[k][1]-f[k-1][1]+mod)%mod)*ksm(2,n-k-1))%mod;
  else  ans=(f[k][1]-f[k-1][1]+mod)%mod;
  printf("%lld",ans);
  return 0;
}

Measured memory_bytes: 30976
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<bitset>
 
#define Vsort(a) sort(a.begin(), a.end())
#define Vreverse(a) reverse(a.begin(), a.end())
#define Srep(n) for(int i = 0; i < (n); i++)
#define Lrep(i,a,n) for(int i = (a); i < (n); i++)
#define Brep(n) for(int bit = 0; bit < (1<<n); bit++)
#define rep2nd(n,m) Srep(n) Lrep(j,0,m)
#define vi vector<int>
#define vi64 vector<int64_t>
#define vvi vector<vector<int>>
#define vvi64 vector<vector<int64_t>>
 
using namespace std;

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  if(b - a == c - b) cout << "YES" << endl;
  else cout << "NO" << endl;
}


Measured memory_bytes: 3576
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<complex>
using namespace std;

int main(){
  while(true){
    int n; cin >> n;
    if(n == 0) break;
    vector<double> a(n);
    double ave = 0;
    for(int i = 0; i < n; i++){
      cin >> a[i];
      ave += a[i];
    }
    ave /= n;
    double t = 0;
    for(int i = 0; i < n; i++){
      t += (a[i] - ave) * (a[i] - ave);
    }
    t /= n;
    double ans = sqrt(t);
    printf("%.10f\n", ans);

  }
  return 0;
}



Measured memory_bytes: 3208
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int A = 1000;
  int request = 0;
  cin >> request;
  int h = request %1000;
  if(h == 0)
  {
    cout << 0;
  }else{
  	int Ans = 1000 - h;
  	cout << Ans;
  }
  return 0;
}

Measured memory_bytes: 3628
//#include <bits/stdc++.h>
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <tuple>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <cmath>
#include <bitset>

using namespace std;
using ll=long long;
using intpair=pair<int,int>;
using intpv=vector<intpair>;
using llpair=pair<ll,ll>;
using llpv=vector<llpair>;
using intvec=vector<int>;
using llvec=vector<ll>;
using intq=queue<int>;
using llq=queue<ll>;
using intmat=vector<intvec>;
using llmat=vector<llvec>;
using pairmat=vector<llpv>;

template<typename T>
using matrix=vector<vector<T>>;
template<typename T>
using pque=priority_queue<T>;
template<typename T>
using lpque=priority_queue<T,vector<T>,greater<T>>;

#define PI 3.141592653589793
#define INTINF 1<<30
#define LLINF 1LL<<60
#define MPRIME 1000000007
#define MPRIME9 998244353

#define len length()
#define pushb push_back
#define fi first
#define se second

#define setpr fixed<<setprecision(15)
#define all(name) name.begin(),name.end()
#define rall(name) name.rbegin(),name.rend()
#define gsort(vbeg,vend) sort(vbeg,vend,greater<>())
#define matin(mat,H,W) for(int i__=0; i__<H; i__++)for(int j__=0; j__<W; j__++) cin>>mat[i__][j__]
#define out(n) cout<<n<<endl

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

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

template<class T>
inline void outmat(T& a, int y, int x) {
	for(int i=0; i<y; i++) {
		for(int j=0; j<x; j++) cout<<a[i][j]<<" ";
		cout<<endl;
	}
}

template<class T>
inline void init(T& v) {
	for(auto &a__: v) cin>>a__;
}
template<class T, class N>
inline void init(T& v, N n) {
	v.resize(n);
	for(auto &a__: v) cin>>a__;
}

template<class N> void resiz(N n) {} // empty
template<class N, class T, class... U>
void resiz(N n, T&& hd, U&&... tl) {
	hd.resize(n);
	resiz(n,forward<U>(tl)...);
}

ll GCD(ll a, ll b) { //最大公約数
	if(a==0||b==0) return 0;
	if(a<b) swap(a,b);
	ll tmp = a%b;
	while(tmp!=0) {
		a = b;
		b = tmp;
		tmp = a%b;
	}
	return b;
}

ll binpow(ll a, ll ex, ll p) { //繰り返し二乗法
	ll result=1;
	while(ex>0) {
		if(ex&1) result=result*a%p;
		ex>>=1;
		a=a*a%p;
	}
	return result;
}

ll Fact(ll x, ll p) { //階乗
	ll f=1;
	for(ll i=2; i<=x; i++) {
		f*=i;
		f%=p;
	}
	return f;
}

int DigitNum(ll n) { //桁数
	int digit=0;
	ll div=1LL;
	while(n/div) {
		digit++;
		div*=10;
	}
	return digit;
}


string S,T;
intmat alp(26);

void input() {
	cin>>S>>T;
}

void solve() {
	for(int i=0; i<S.len; i++) {
		alp[S[i]-'a'].pushb(i+1);
	}

	int nstr=0, npos=0;
	for(int i=0; i<T.len; i++) {
		if(alp[T[i]-'a'].empty()) {
			cout<<-1<<endl;
			return;
		}

		auto itr=upper_bound(all(alp[T[i]-'a']),npos);
		if(itr!=alp[T[i]-'a'].end()) {
			npos=*itr;
		}
		else {
			nstr++;
			npos=alp[T[i]-'a'][0];
		}
	}

	cout<<(ll)nstr*S.len+npos<<endl;
}

int main() {
	while(1) {
		input();
		solve();
		break;
	}
}


Measured memory_bytes: 1216
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int m=1000000007;
bool arr[1005][1005]={0};
int dp[1005][1005]={0};
/*int recurse(int a , int b)
{
    if(arr[a][b]==false)
        return 0;
    if(arr[a][b]==true&&dp[a][b]!=0)
        return dp[a][b];
    else if(b==0||arr[a][b-1]==false)
    {
        dp[a][b]=recurse(a-1,b);
        return dp[a][b];
    }
    else if(a==0||arr[a-1][b]==false)
    {
        dp[a][b]=recurse(a,b-1);
        return dp[a][b];
    }
    else
    {
        dp[a][b]=(recurse(a-1,b)%m+recurse(a,b-1)%m)%m;
        return dp[a][b];
    }

}*/
int main()
{
    int h,w;
    cin>>h>>w;
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            char ch;
            cin>>ch;
            if(ch=='.')
                arr[i][j]=true;
            else
                arr[i][j]=false;
        }
    }
    dp[0][0]=1;
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            if(arr[i][j]!=false)
            {
                if(i==0&&j==0)
                    continue;
                else if(i==0)
                {
                    dp[i][j]=dp[i][j-1];
                }
                else if(j==0)
                {
                    dp[i][j]=dp[i-1][j];
                }
                else
                {
                    dp[i][j]=(dp[i-1][j]%m+dp[i][j-1]%m)%m;
                }
            }
        }
    }
    cout<<dp[h-1][w-1];
}


Measured memory_bytes: 5120
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

const int N = 300;
long double dp[N+1][N+1][N+1];
long long cnt[4];
int n;

long double solve(int a,int b,int c)
{
	// four state to go from curr state[a,b,c]
	// we just use  ExMoves_corrState[a,b,c] = sigma[i=0 to i=3] {  probobility to go ith state  * ExMove_from_(i)_state }
	
	/* from [a,b,c] -> i=0.[a,b,c]             empty plate
	        [a,b,c] -> i=1.[a-1,b,c]           
	        [a,b,c] -> i=2.[a+1.b-1,c]
	        [a,b,c] -> i=3.[a,b+1,c-1]
	*/
	
	if( a==0 && b==0 && c==0 )return 0;
	if( a <0 || b <0 || c <0 )return 0;
	if( dp[a][b][c] != -1 )return dp[a][b][c];
	dp[a][b][c]=0;
	long  double tot = a + b + c;
	
	/*
	  probility to choose from [a,b,c] to empty plate. p = (n-tot)/n;
	  but total prob = [(n-tot)/n] + [(n-tot)/n] * [(n-tot)/n] + [(n-tot)/n] * [(n-tot)/n] * [(n-tot)/n] + ..................
	             = 1/[ 1 - ( n-tot)/n ]
	      p[0]   = n/tot.
	*/
	
	
	/* 
	  probility to choose from [a,b,c] to [a-1,b,c] state. p = a/n.
	  but total prob  = a/n  + [(n-tot)/n] * a/n + [(n-tot)/n * (n-tot)/n] * ( a/n) + ...................
	               = a/n * ( n/tot)
	      p[1]     = a/tot
	             
	*/
	
	
	/* similarily p[2] = b/tot
	 * ...........p[3] = c/tot
	 */
	
	
	// expected moves form curr_state = probility_to_ith_state * expected_moves_from_ith_state
	
	dp[a][b][c]+=((long double)n/(long double)tot)*1;
	dp[a][b][c]+=((long double)a/(long double)tot)*solve(a-1,b,c); 
	dp[a][b][c]+=((long double)b/(long double)tot)*solve(a+1,b-1,c);
	dp[a][b][c]+=((long double)c/(long double)tot)*solve(a,b+1,c-1);
	
	
	return dp[a][b][c];
}
	
	
int32_t main()
{
	IOS
	cnt[1]=cnt[2]=cnt[3]=0;
	for(int i=0;i<=N;i++)
	for(int j=0;j<=N;j++)
	for(int k=0;k<=N;k++)
	dp[i][j][k]=-1;
	
	cin >> n ;
	for(int i=1;i<=n;i++)
	{
		int x;cin>>x;
		cnt[x]++;
	}
	cout << fixed << setprecision(10)  << solve(cnt[1],cnt[2],cnt[3]) << endl;
	
}


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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll n, W;
	cin >> n >> W;

	ll V = 1e5 + 10;

	vl dp(V,oo);
	dp[0] = 0;
	
	while (n--) {
		ll w, v;
		cin >> w >> v;
		FORD(s,v,V+1) dp[s] = min(dp[s], dp[s-v]+w);
	}

	ll res = V-1;
	while (dp[res] > W) res--;
	cout << res << endl;
}



Measured memory_bytes: 1024
using System;

namespace A_abc_of_ABC
{
    class Program
    {
        static void Main(string[] args)
        {
            //値を読み込んでバラして格納
            string num = Console.ReadLine();
            char[] input = new char[3];

            for(int i=0; i<3; i++)
            {
                input[i] = num[i];
            }

            bool flag = false;

            int counter = 0;

            //a～cがひとつだけ入っていたらflagをtrueにする
            for(int i=0; i<3; i++)
            {
                if(input[0] == 'a')
                {
                    counter++;
                }
            }

            if(counter == 1)
            {
                flag = true;
            }
            counter = 0;

            for (int i = 0; i < 3; i++)
            {
                if (input[i] == 'b')
                {
                    counter++;
                }
            }

            if (counter == 1)
            {
                flag = true;
            }
            counter = 0;

            for (int i = 0; i < 3; i++)
            {
                if (input[0] == 'c')
                {
                    counter++;
                }
            }

            if (counter == 1)
            {
                flag = true;
            }

            if(flag == true)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }

        }
        
    }
}


Measured memory_bytes: 13140
public class Main{
  public void run(java.io.InputStream in, java.io.PrintStream out){
    java.util.Scanner sc = new java.util.Scanner(in);
/*answer*/
//want gaisetu cyuusinn and R
    int n;
    double x1, x2, x3, y1, y2, y3, px, py, r;
    int i;
    double ax, ay, bx, by, l1x, l1y, l2x, l2y;

    n = sc.nextInt();
    for(i = 0;i < n;i++){
      x1 = sc.nextDouble();
      y1 = sc.nextDouble();
      x2 = sc.nextDouble();
      y2 = sc.nextDouble();
      x3 = sc.nextDouble();
      y3 = sc.nextDouble();

      ax = (x1 + x2) / 2.0;
      ay = (y1 + y2) / 2.0;
      bx = (x1 + x3) / 2.0;
      by = (y1 + y3) / 2.0;
      l1x = x1 - x2;
      l1y = y1 - y2;
      l2x = x1 - x3;
      l2y = y1 - y3;

      px = ((ax * l1x + ay * l1y) * l2y + (bx * l2x + by * l2y) * (-l1y))
      / (l1x * l2y - l2x * l1y);
      py = ((ax * l1x + ay * l1y) * (-l2x) + (bx * l2x + by * l2y) * l1x)
      / (l1x * l2y - l2x * l1y);
      r = Math.sqrt((px - x1) * (px - x1) + (py - y1) * (py - y1));

      System.out.printf("%.3f %.3f %.3f%n", px, py, r);

    }

    sc.close();
  }
  public static void main(String[] args){
    (new Main()).run(System.in, System.out);
  }
}

Measured memory_bytes: 20740
import std.array;
import std.algorithm;
import std.range;
import std.stdio;

void main() {
    int n;
    readf("%d\n", &n);
    int[] d;
    d.length = n;
    for (int i = 0; i < n; ++i) {
        readf("%d\n", &d[i]);
    }
    writeln(d.sort.uniq.count!"true");
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
typedef long long ll;
using namespace std;
char sz[15];
ll dp[15];
ll num[15];
int len;
int main(){
    scanf("%s",sz+1);
    len=(int)strlen(sz+1);
    dp[0]=0,dp[1]=sz[1]-'0';
    num[0]=1,num[1]=1;
    for(int i=2;i<=len;i++){
        for(int j=0;j<i;j++){
            num[i]+=num[j];
            ll nums=0;
            for(int k=j+1;k<=i;k++) nums=nums*10+sz[k]-'0';
            dp[i]+=(nums*num[j]+dp[j]);
        }
    }
    printf("%lld\n",dp[len]);
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(void){
    int x,a,b,nokori,nokori2,syo;
    cin >> x;
    cin >> a;
    cin >> b;
    
    nokori = x-a;
    syo = nokori/b;
    nokori2 = nokori-(syo*b);
    
    cout << nokori2 << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#define MAX_NUM 100000

int main(void){

    int N,K,i,t=0;
    long int S,ans[MAX_NUM+1];

    scanf("%d %d %ld",&N,&K,&S);

    for(i = 0;i < N;i++){
        if(t <= K-1){
            ans[i] = S;
            t++;
        }else{
            if(S < MAX_NUM){
                ans[i] = MAX_NUM+1;
            }else{
                ans[i] = MAX_NUM-1;
            }
        }
    }

    for(i = 0;i < N;i++){
        printf("%ld ",ans[i]);
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 2048
N=int(input())
A=[0]*(N+1)
B=[0]*(N+1)
C=[0]*(N+1)
#dp=[[0]*(N+1)]*3 #同じインデックスのものが全て更新される
dp=[[0 for _ in range(N+1)] for _ in range(3)]

for i in range(1,N+1):
  a,b,c=map(int,input().split())
  A[i]=a
  B[i]=b
  C[i]=c
#print(A,B,C)

for i in range(1,N+1):
  dp[0][i]=max(dp[0][i],dp[1][i-1]+A[i],dp[2][i-1]+A[i])
  dp[1][i]=max(dp[1][i],dp[0][i-1]+B[i],dp[2][i-1]+B[i])
  dp[2][i]=max(dp[2][i],dp[0][i-1]+C[i],dp[1][i-1]+C[i])
  #print(dp)

print(max(dp[0][N],dp[1][N],dp[2][N]))


Measured memory_bytes: 26880
#include <bits/stdc++.h>  // g++ -std=c++14 -o a a.cpp

using namespace std;

typedef pair<int, int> P;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end()) // ユニークなvectorにする。連続した値を除去して切り出す。
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;

int main() {
  int c[4][4] = {};
  rep(j, 3) {
    rep(i, 3) {
      int cij;
      cin >> cij;
      c[i + 1][j + 1] = cij;
    }
  }

  int s11 = c[1][1] - c[2][1];
  int s12 = c[1][2] - c[2][2];
  int s13 = c[1][3] - c[2][3];
  // DEBUG(s11);
  // DEBUG(s12);
  // DEBUG(s13);

  int s21 = c[2][1] - c[3][1];
  int s22 = c[2][2] - c[3][2];
  int s23 = c[2][3] - c[3][3];
  // DEBUG(s21);
  // DEBUG(s22);
  // DEBUG(s23);

  int s31 = c[3][1] - c[1][1];
  int s32 = c[3][2] - c[1][2];
  int s33 = c[3][3] - c[1][3];
  // DEBUG(s31);
  // DEBUG(s32);
  // DEBUG(s33);

  if( (s11 == s12 && s12 == s13) &&
      (s21 == s22 && s22 == s23) &&
      (s31 == s32 && s32 == s33)
   ) {
     cout << "Yes" << endl;
   } else {
     cout << "No" << endl;
   }  
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;
public class Main {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		PrintWriter out=new PrintWriter(System.out);
		int n=Integer.parseInt(in.next()),q=Integer.parseInt(in.next());
		mylist A[]=new mylist[n];
		for(int i=0;i<n;i++)A[i]=new mylist();
		
		for(int i=0;i<q;i++){
			int query=Integer.parseInt(in.next());
			
			switch(query){
			case 0:
				int t1=Integer.parseInt(in.next()),x=Integer.parseInt(in.next());
				A[t1].ls.add(x);
				break;
				
			case 1:
				int t2=Integer.parseInt(in.next());
				if(A[t2].ls.isEmpty())out.println();
				else{
					for(int j=0;j<A[t2].ls.size()-1;j++)out.print(A[t2].ls.get(j)+" ");
					out.println(A[t2].ls.get(A[t2].ls.size()-1));
				}
				break;
				
			case 2:
				int t3=Integer.parseInt(in.next());
				A[t3].ls.clear();
				break;
			}
		}
		out.flush();
	}

}

class mylist{
	List<Integer> ls;
	
	mylist(){
		ls=new ArrayList<>();
	}
}



Measured memory_bytes: 187676
#include <bits/stdc++.h>
using namespace std;
 
#define fast { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); }
#define pb push_back
#define ll long long
 
#define vi vector<int>
#define vl vector<long>
#define vll vector<long long>
 
#define infi INT_MAX
#define infl LONG_LONG_MAX
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fi(i,a,b) for(ll i=(b-1);i>=a;i--)
#define F first
#define S second
#define G(a,b) get<a>(b)
#define MP make_pair
#define MT make_tuple
#define pll pair<ll,ll> 
#define endl "\n"
#define ALL(v) v.begin(),v.end()
#define nl cout<<"\n";
#define pr(x) cout<<x;
#define pr1(x) cout<<x<<" ";
#define pr2(x,y) cout<<x<<" "<<y;


void func()
{
 string s;
 cin>>s;
 ll n=s.length();
 f(i,0,n/2)
 {
 	if(s[i]!=s[n-1-i])
 	{
 		cout<<"No\n";
 		return;
 	}
 }
 string t=s.substr(0,(n/2));
 n=t.length();
 //cout<<t<<endl;
 f(i,0,n/2)
 {
 	if(t[i]!=t[n-1-i])
 	{
 		cout<<"No\n";
 		return;
 	}
 }
 cout<<"Yes\n";
}

int main() 
{
    fast
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
    
    ll ntc=1;
    //cin>>ntc;

    f(i,1,ntc+1)
    {
      //cout<<"Case #"<<i<<":";
      func();
    }
 
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>


using namespace std;

int count(int n, vector<int> p) {
	vector<int> cur;
	for (int i = 0; i < n; i++) {
		cur.push_back(i + 1);
	}
	int count = 0;
	while(true) {
		bool isOK = true;

		for (int i = 0; i < n; i++) {
			if (cur[i] != p[i]) {
				isOK = false;
			}
		}
		if (isOK == true) {
			break;
		} 
		count++;
		next_permutation(cur.begin(), cur.end());
	}
	return count;
}


int main() {
	int n;
	cin >> n;
	vector<int> p(n), q(n);

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

	int p_count = count(n, p);
	int q_count = count(n, q);


	cout << abs(p_count - q_count) << endl;


	return 0;
}

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

#define reg register
#define pr std::pair<int, int>
#define fi first
#define se second
#define FIN(s) freopen(s, "r", stdin)
#define FOUT(s) freopen(s, "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define lep(i, l, r) for (int i = l; i < r; ++i)
#define irep(i, r, l) for (int i = r; i >= l; --i)
#define ilep(i, r, l) for (int i = r; i > l; --i)
#define Rep(i, n) rep(i, 1, n)
#define Lep(i, n) lep(i, 1, n)
#define IRep(i, n) irep(i, n, 1)
#define ILep(i, n) ilep(i, n, 1)
typedef long long ll;
typedef long double ld;

namespace modular {
    const int MOD = 1000000007;
    inline int add(int x, int y) { return (x += y) >= MOD ? x -= MOD : x; }
    inline void inc(int &x, int y) { (x += y) >= MOD ? x -= MOD : 0; }
    inline int mul(int x, int y) { return 1LL * x * y % MOD; }
    inline int qpow(int x, int y) {
        int ans = 1;
        for (; y; y >>= 1, x = mul(x, x))
            if (y & 1)
                ans = mul(ans, x);
        return ans;
    }
}; // namespace modular

namespace Base {
    template <typename Tp> inline Tp input() {
        Tp x = 0, y = 1;
        char c = getchar();
        while ((c < '0' || '9' < c) && c != EOF) {
            if (c == '-')
                y = -1;
            c = getchar();
        }
        if (c == EOF)
            return 0;
        while ('0' <= c && c <= '9')
            x = x * 10 + c - '0', c = getchar();
        return x *= y;
    }
    template <typename Tp> inline void read(Tp &x) { x = input<Tp>(); }
    template <typename Tp> inline void chmax(Tp &x, Tp y) { x < y ? x = y : 0; }
    template <typename Tp> inline void chmin(Tp &x, Tp y) { x > y ? x = y : 0; }
}; // namespace Base
using namespace Base;
/*----------------------------------------------------------------------------*/

int N;

int sg(int k, int x) {
    if (x < k) return 0;
    if (x % k == 0) return x / k;
    int tmp = x / k + 1;
    return sg(k, x - (x - x / k * (k - 1)) / tmp * tmp);
}

int main() {
#ifdef LOCAL
    FIN("in");
#endif
    read(N);
    int res = 0, a, k;
    Rep(i, N) { 
        read(a), read(k);
        res ^= sg(k, a);
    }
    puts(res ? "Takahashi" : "Aoki");
    return 0;
}


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

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

	int n, w;
	cin >> n >> w;

	vector<long long> dp(w + 1);
	for(int i = 0; i < n; i++)
	{
		int c, v;
		cin >> c >> v;
		for(int j = w; j >= c; j--)
			dp[j] = max(dp[j], dp[j - c] + v);
	}

	cout << dp[w] << "\n";
}


Measured memory_bytes: 1024
x, k, d = gets.split.map(&:to_i)

if x.abs > k * d
  puts x.abs - k * d
  exit
end

n = x.abs / d

if (n - k) % 2 == 0
  puts x.abs - n * d
else
  puts (n+1) * d - x.abs
end


Measured memory_bytes: 14388
#include <algorithm>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cassert>
#include <set>
#include <cstring>

using namespace std;

typedef long long ll;

#define SIZE 100010
#define INF 1000000000
#define mod 1000000007

ll dp[2010][2010];
int posl[26][SIZE], posr[26][SIZE];

int main(){
  char s[2010];
  int n;
  set<int> ss[26], ss_b[26];

  
  
  scanf("%s", s);
  n = strlen(s);

  for(int i=0;i<26;i++){
    for(int j=0;j<=n;j++){
      posl[i][j] = INF;
      posr[i][j] = -INF;
    }
  }
  
  for(int i=0;i<n;i++){
    ss[s[i]-'a'].insert(i);
    ss_b[s[i]-'a'].insert(-i);
    //vec[s[i]-'a'].push_back(i);
    posl[s[i]-'a'][i] = i;
    posr[s[i]-'a'][i] = i;
  }

  for(int k=0;k<26;k++){
    for(int i=0;i<n;i++) posr[k][i+1] = max(posr[k][i], posr[k][i+1]);
    for(int i=n;i>0;i--) posl[k][i-1] = min(posl[k][i], posl[k][i-1]);
  }
  
  for(int i=0;i<26;i++){
    ss[i].insert(INF);
    ss_b[i].insert(INF);
  }

  for(int i=0;i<26;i++){
    int a = *ss[i].begin();
    int b = -*ss_b[i].begin();

    //cerr << a << " " << b << endl;
    
    if(a != b && a != INF && b != -INF){
      dp[a][b]++;
    }
  }

  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      for(int k=0;k<26;k++){
        int nextl = posl[k][i+1]; //*ss[k].lower_bound(i+1);
        int nextr = posr[k][j-1]; //-*ss_b[k].lower_bound(-(j-1));

        //if(i == 0 && j == 6) cerr << " > " << nextl << " " << nextr << endl;
        
        if(nextl < nextr){
          dp[nextl][nextr] = (dp[nextl][nextr] + dp[i][j])%mod;
        }
      }      
    }
  }

  ll ans = 0;
  
  for(int i=0;i<26;i++){
    ans += ss[i].size() >= 2;
  }

  //cerr << ans << endl;
  
  for(int i=0;i<n;i++){
    for(int j=i;j<n;j++){
      //if(dp[i][j]) cerr << i << " " << j << " " << dp[i][j] << endl; 
      ans = (ans + dp[i][j])%mod;

      for(int k=0;k<26;k++){
        if(posl[k][i+1] < j){
          ans = (ans + dp[i][j])%mod;
        }
      }
    }
  }

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



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

#define FOR(i,l,r) for(int i = int(l);i < int(r);i++)
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

int N;
string S [2];
const ll MOD = 1e9 + 7;

int main()
{
	cin >> N >> S [0] >> S [1];

	ll ans = 1;
	int ptr = 0;
	if(S [0] [0] == S [1] [0]){
		ans = 3;
		ptr++;
	}
	else{
		ans = 6;
		ptr += 2;
	}

	while(ptr < N){
		if(S [0] [ptr - 1] == S [1] [ptr - 1]){
			if(S [0] [ptr] == S [1] [ptr]){
				(ans *= 2) %= MOD;
				ptr++;
			}
			else{
				(ans *= 2) %= MOD;
				ptr += 2;
			}
		}
		else{
			if(S [0] [ptr] == S [1] [ptr]){
				ptr++;
			}
			else{
				(ans *= 3) %= MOD;
				ptr += 2;
			}
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair< int, int > iP;
typedef pair< iP, int > iiP;

vector< iP > pp;
int prim(vector< vector< int > > &g) {
    int ret = 0;
    int s = g.size();
    priority_queue< iP, vector< iP >, greater< iP > > q;
    vector< int > v(s, 0);
    q.push(iP(0, 0));
    while(!q.empty()) {
        iP p = q.top(); q.pop();
        if(v[p.second]++) continue;
        ret += p.first;
        int now = p.second;
        for(int i = 0; i < g[now].size(); i++) {
            q.push(iP(min(abs(pp[now].first - pp[g[now][i]].first), abs(pp[now].second - pp[g[now][i]].second)), g[now][i]));
        }
    }

    return ret;
}

int main() {

    int n;
    vector< iiP > g1, g2;
    vector< vector< int > > g0;

    cin >> n;
    g0.resize(n + 1);
    pp.resize(n);
    for(int i = 0; i < n; i++) {
        int x, y; cin >> x >> y;
        pp[i] = iP(x, y);
        g1.push_back(iiP(iP(x, y), i));
        g2.push_back(iiP(iP(y, x), i));
    }
    sort(g1.begin(), g1.end());
    sort(g2.begin(), g2.end());
    for(int i = 0; i < n; i++) {
        int pre = (i - 1 + n) % n;
        int nxt = (i + 1) % n;
        g0[g1[i].second].push_back(g1[pre].second), g0[g1[i].second].push_back(g1[nxt].second);
        g0[g2[i].second].push_back(g2[pre].second), g0[g2[i].second].push_back(g2[nxt].second);
    }

    cout << prim(g0) << endl;
}


Measured memory_bytes: 12332
//                             In The Name Of Allah
#include <bits/stdc++.h>
#define ss second
#define ff first
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ret(n) return cout << n, 0
#define se(n) cout << setprecision(n) << fixed
#define ll long long
#define pb push_back
#define int long long
using namespace std;

const ll N = 1e6 + 100, OO = 1e6 + 10, M = 1e9 + 7, lg = 22;
typedef pair <int, int> pii;
int a[N], b[N], c[N];

int32_t main() {
	int n;
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		a[i]--;	
	}
	for(int i = 0; i < n; i++) {
		cin >> b[i];
	}
	for(int i = 0; i < n - 1; i++) {
		cin >> c[i + 1];
	}
	int x = -1;
	int ans = 0;
	for(int i = 0; i < n; i++) {
		ans += b[a[i]];
		if(x == a[i] - 1) 
			ans += c[a[i]];
		x = a[i];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod=1e9+7;
vector<pair<int,char>>X[200001],Y[200001],xpyu[400001],xpyd[400001],xmyu[400001],xmyd[400001];
signed main(){
    int n,x,y;
    char u;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x>>y>>u;
        if(u=='R'||u=='L')
            X[y].emplace_back(x,u);
        else
            Y[x].emplace_back(y,u);
        if(u=='U'||u=='R')
            xpyu[x+y].emplace_back(y,u);
        else
            xpyd[x+y].emplace_back(y,u);
        if(u=='U'||u=='L')
            xmyu[x-y+200000].emplace_back(y,u);
        else
            xmyd[x-y+200000].emplace_back(y,u);
    }
    int ans=mod;
    for(int i=0;i<=200000;i++){
        sort(X[i].begin(),X[i].end());
        for(int j=0;j+1<X[i].size();j++)
            if(X[i][j].second=='R'&&X[i][j+1].second=='L')
                ans=min(ans,(X[i][j+1].first-X[i][j].first)*5);
    }
    for(int i=0;i<=200000;i++){
        sort(Y[i].begin(),Y[i].end());
        for(int j=0;j+1<Y[i].size();j++)
            if(Y[i][j].second=='U'&&Y[i][j+1].second=='D')
                ans=min(ans,(Y[i][j+1].first-Y[i][j].first)*5);
    }
    for(int i=0;i<=400000;i++){
        sort(xpyu[i].begin(),xpyu[i].end());
        for(int j=0;j+1<xpyu[i].size();j++)
            if(xpyu[i][j].second=='U'&&xpyu[i][j+1].second=='R')
                ans=min(ans,(xpyu[i][j+1].first-xpyu[i][j].first)*10);
    }
    for(int i=0;i<=400000;i++){
        sort(xpyd[i].begin(),xpyd[i].end());
        for(int j=0;j+1<xpyd[i].size();j++)
            if(xpyd[i][j].second=='L'&&xpyd[i][j+1].second=='D')
                ans=min(ans,(xpyd[i][j+1].first-xpyd[i][j].first)*10);
    }
    for(int i=0;i<=400000;i++){
        sort(xmyu[i].begin(),xmyu[i].end());
        for(int j=0;j+1<xmyu[i].size();j++)
            if(xmyu[i][j].second=='U'&&xmyu[i][j+1].second=='L')
                ans=min(ans,(xmyu[i][j+1].first-xmyu[i][j].first)*10);
    }
    for(int i=0;i<=400000;i++){
        sort(xmyd[i].begin(),xmyd[i].end());
        for(int j=0;j+1<xmyd[i].size();j++)
            if(xmyd[i][j].second=='R'&&xmyd[i][j+1].second=='D')
                ans=min(ans,(xmyd[i][j+1].first-xmyd[i][j].first)*10);
    }
    cout<<(ans==mod?"SAFE":to_string(ans))<<endl;
}


Measured memory_bytes: 69000
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<long long> x(n);
	vector<long long> y(m);
	for (auto i = 0; i < n; ++i)
	{
		cin >> x[i];
	}
	for (auto i = 0; i < m; ++i)
	{
		cin >> y[i];
	}

	auto sumX = 0ll;
	auto mod = (long long)1e9 + 7;
	for (auto i = 1; i < n; ++i)
	{
		auto diff = x[i] - x[i - 1];
		sumX += (((diff * i) % mod) * (n - 1 - i + 1)) % mod;
		sumX %= mod;
	}

	auto sum = 0ll;
	for (auto i = 1; i < m; ++i)
	{
		auto diff = y[i] - y[i - 1];
		sum += (((((diff * i) % mod) * (m - 1 - i + 1)) % mod) * sumX) % mod;
		sum %= mod;
	}

	cout << sum << endl;

	return 0;
}

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

int main() {
  ll n, k;
  cin >> n >> k;
  vector<ll> a(n);
  for (auto &e : a) {
    cin >> e;
  }
  ll r = 0;
  for (ll b = 1ll << 60; b != 0; b >>= 1) {
    int t = 0, f = 0;
    for (auto e : a) {
      t += !!(e & b);
      f += !(e & b);
    }
    if (b <= k && t < f) {
      r += f * b;
      k -= b;
    } else {
      r += t * b;
    }
  }
  cout << r << endl;
}


Measured memory_bytes: 1024
(N, M) = gets.split.map(&:to_i)
data = []

N.times do
  data << gets.split.map(&:to_i)
end

data.sort! do |a, b|
  a[0] <=> b[0]
end

count = 0
sum = 0
data.each do |d|
  if count + d[1] > M
    sum += d[0] * (M - count)
    break
  end

  sum += d[0] * d[1]
  count += d[1]
end

puts sum

Measured memory_bytes: 10488
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <set>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
#include <iomanip>
#include <numeric>

using namespace std;

typedef long long ll;

#define forn(i, n) for(int i = 0; i < int(n);++i)
#define pb push_back
#define vi vector<int>
#define pll pair<ll,ll>
#define vb vector<bool>
#define vvi vector<vi>
#define vpll vector<pll>
#define vll vector<ll>
#define vvll vector<vll>
#define sz(x) (int)x.size()
#define ff first
#define ss second

void solve() {

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    double eps = 1e-5;
    ll n; cin >> n;
    vi a(n);
    forn(i,n){ cin >> a[i];}
    double ans = 0;
    double s = 0;
    forn(i,n){
        s += 1/double(a[i]);
    }
    ans = 1/s;
    cout << setprecision(20) << ans;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include<bits/stdc++.h>
#include <utility>

#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,a,b) for(int i = (a); (b) <= i; i--)
#define REP(i,n) for(int i = 0; i < (n); i++)
#define RREP(i,n) for(int i = n; n <= i; i--)
#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))
#define elif else if
#define MOD 1000000007
#define INF (1<<29)

using namespace std;
using ll = long long;
map <int ,int> mpa,mpb;
typedef pair<ll, ll> P;
priority_queue<P, vector<P>, greater<P>> pque;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int A,B;
  cin >> A >> B;
  if(A+B>=10)cout << "error" << endl;
  else cout << A+B << endl;
  return 0;
}


Measured memory_bytes: 256