akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

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

    vector<int> aji(n);
    int aji_sum = 0;
    for (int i = 0; i < n; ++i)
    {
        int tmp_aji = l + i;
        aji[i] = tmp_aji;
        aji_sum += tmp_aji;
    }
    
    auto iter = min_element(aji.begin(), aji.end(), [](const int &a, const int &b){return (abs(a) < abs(b));});
    int ans = aji_sum - *iter;
    
    cout << ans << endl;

    return 0;
}

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

int main(){
  int n,z,w;
  cin >> n >> z >> w;
  vector<int> a(n);

  rep(i,n) cin >> a[i];
  if (n == 1) cout << abs(a[0] - w) << endl;
  else cout << max(abs(a[n-1]-w),abs(a[n-2]-a[n-1])) << endl; 
  return 0;
}

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

#if __has_include(<local.h>)
#include <local.h>
#endif

using namespace std;

typedef long long int LL;
typedef long long int LLint;

//Faster Program
#define endl "\n"

//Faster Coding
#define ED return
#define GET(a) int a;cin >> a
#define DGET(a) double a;cin >> a
#define SGET(a) string a;cin >> a
#define CGET(a) char a;cin >> a
#define PRINT(a) cout << a << "\n"
#define ANS(a,b) int a;cin >> a;cout << b << "\n"
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define SORT(vec) sort(vec.begin(),vec.end())
#define REV(vec) reverse(vec.begin(),vec.end())
#define ALL(x) (x).begin(),(x).end()

//As Function
#define UP(a,b) ((a+(b-1))/(b))
#define IPOW(x,y) LL(pow(x,y))

//Debug
#ifdef LOCAL_H
#define TEST cout << "OK\n"
#define DEBUG(a) a
#else
#define TEST
#define DEBUG(a)
#endif

#ifdef LOCAL_H
[[maybe_unused]]
#endif
const double PI = M_PI;
#ifdef LOCAL_H
[[maybe_unused]]
#endif
const int INF = int(999999999);
#ifdef LOCAL_H
[[maybe_unused]]
#endif
const LL LL_INF = LL(999999999999999999);
#ifdef LOCAL_H
[[maybe_unused]]
#endif
const long long MOD = int(1000000007);

//Settings
#ifdef LOCAL_H
const bool DO_BENCHMARK = true;
#endif
const int DOUBLE_ACCURACY = 15;
const int RUN_SOLVE = 1;

#ifndef LOCAL_H
const bool DO_BENCHMARK = false;
#endif

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(DOUBLE_ACCURACY);
    for(int do_solve_time = 0;do_solve_time < RUN_SOLVE;do_solve_time++){
        void solve();
        if(DO_BENCHMARK){
            clock_t clock_start = clock();
            solve();
            clock_t clock_end = clock();
            const double time = static_cast<double>(clock_end-clock_start)/CLOCKS_PER_SEC*1000.0;
            cout << "\n------------------------------------\n" << time << "[ms]\n";
        }
        else solve();
    }
}

/*------------------------------↓ここからコード↓----------------------------------*/
void solve(){
    string S;
    cin >> S;
    int ans = 0;
    for(int i = 0;i < 3;i++){
        if(S[i] == 'R'){
            ans++;
        }
    }
    if(ans == 2){
        if(S[1] == 'S'){
            cout << 1 << endl;
        }
        else{
            cout << 2 << endl;
        }
    }
    else{
        cout << ans << endl;
    }
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=(a);i<(n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI (3.1415926535897932384)

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>void tf(bool b,S t,T f){if(b)puta(t);else puta(f);}
void YN(bool b){tf(b,"YES","NO");}
void Yn(bool b){tf(b,"Yes","No");}
void yn(bool b){tf(b,"yes","no");}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1;for(auto s:t){os<<(a?"":" ")<<s;a=0;}return os;}
template<class S>auto&operator>>(istream&is,vector<S>&t){for(S&a:t)cin>>a;return is;}

/*他のライブラリを入れる場所*/


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,q;
    cin>>n>>q;
    vl a(n);
    cin>>a;
    vector<vvl> dp(2,vvl(q+1,vl(n+1,LINF))); // i番目まで見て、j回操作して、i番目の高さをk番目のものに合わせた
    dp[0][0][0]=0;
    rep(i,n){
        ll cur=i%2, nxt=1-cur;
        dp[nxt] = vvl(q+1,vl(n+1,LINF));
        rep(j,q+1)rep(k,i+1)if(dp[cur][j][k]!=LINF){
            ll left = k==0 ? 0 : a[k-1];
            chmin(dp[nxt][j][i+1], dp[cur][j][k] + max(0, a[i]-left));
            if(j+1<=q)chmin(dp[nxt][j+1][k], dp[cur][j][k]);
        }
    }
    ll ans=LINF;
    for(auto&ln:dp[n%2])for(auto&v:ln)chmin(ans,v);
    puta(ans);
    return 0;
}

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

int main()
{
    string s;
    bool ok=true;
    cin>>s;
    for(int i=0;i<s.size();i++){ 
            int cur=i+1;
            if(cur%2==0){ 
                    if(s[i]!='L'&&s[i]!='U'&&s[i]!='D')ok=false;
            } 
            else { 
                    if(s[i]!='R'&&s[i]!='U'&&s[i]!='D')ok=false;
            } } 
            cout<<(ok==true?"Yes":"No")<<"\n";
    return 0;
}


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

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

    int ans = 0;
    for (int i = 0; i < s.length(); i++) {
        char my = i % 2 == 0 ? 'g' : 'p';
        char opp = s[i];

        if (my == 'g' && opp == 'p')
            ans -= 1;
        if (my == 'p' && opp == 'g')
            ans += 1;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 512
/*ANKON GHOSH
  KUET,ECE 2K16*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1e18
#define MAX 4003
#define mod 1000000007
#define sf(a) scanf("%lld",&a)
#define sff(a,b) scanf("%lld %lld",&a,&b)
#define sfff(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define Case(i) cout<<"Case #"<<i<<": "
#define pf(a) printf("%lld\n",a)
#define pfsn printf("NO\n")
#define pfs  printf("YES\n")
#define pff(a,b) printf("%lld %lld\n",a,b)
#define pfff(a,b,c) printf("%lld %lld %lld\n",a,b,c)
#define pffff(a,b,c,d) printf("%lld %lld %lld %lld\n",a,b,c,d)
#define FOR(i,n) for(ll i=0;i<n;i++)
#define FOR1(i,n) for(ll i=1;i<=n;i++)
#define LOOP(x,y) for(ll r=x;r<=y;r++)
#define RFOR(i,n) for(ll i=n-1;i>=0;i--)
#define RFOR1(i,n) for(ll i=n;i>0;i--)
#define RLOOP(x,y) for(ll i=y;i>=x;i--)
#define m_p(a,b) make_pair(a,b)
#define p_b(a) push_back(a)
#define ff first
#define ss second
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL)
map<ll,ll>mp1,mp;
vector<pair<ll,pair<ll,ll> > >vp,vpp1;
vector<pair<ll,ll> >vdp,fin;
vector<ll>v1,v2,dummy;
map<pair<ll,ll>,bool>mbb;
map<ll,bool>mb;
ll n,k,a,b,c,d,ta,sum=0,cnt=0,m,l,req,sz,maxi;
bool sortbysec(const pair<pair<ll,ll>,ll> &a,const pair<pair<ll,ll>,ll> &b)
{
    return (a.second < b.second);
}
vector<ll>power;
int main()
{
    fast;
    cin>>a>>b>>c;
    cout<<c<<" "<<a<<" "<<b<<endl;
    return 0;
}


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

#define int long long
using ll = long long;
using ld = long double;
using intpair = pair<int, int>;
const int MOD = 1e9 + 7;
inline int mod (ll a, int m = MOD) { return (a % m + m) % m; }
struct Fast {Fast(){cin.tie(0);ios::sync_with_stdio(0);}} fast;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define ceiv(a, b) ((ll)((a) + (b) - 1)/(ll)(b))

signed main(){
    int n; cin >> n;
    vector<int> div(n+1, 1);
    
    int ans = 1;
    reps(i,2,n){
        for(int j = i; j <= n; j += i){
            div[j]++;
        }
        ans += i * div[i];
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 81320
#include <cstdio>


typedef long long int lld;

int Aarr[20];
int Barr[4];
int ans[25];
char buf[10];

int main(){

    lld A;
    scanf("%lld ",&A);
    scanf("%s",buf);
    for(int i=0;i<=15;i++){
        Aarr[i]=A%10;
        A=A/10;
    }

    Barr[0]=buf[3]-'0';
    Barr[1]=buf[2]-'0';
    Barr[2]=buf[0]-'0';

    // for(int i=0;i<3;i++) printf("%d\n",Barr[i]);
    for(int base=0;base<3;base++){
        int carry=0;
        for(int bit=0;bit<=17;bit++){
            auto result=Barr[base]*Aarr[bit]+ans[base+bit]+carry;
            ans[base+bit]=result%10;
            carry=result/10;
        }
    }

    int i=24;
    while (i>=0&&ans[i]==0) i--;

    for(int k=i;k>=2;k--) printf("%d",ans[k]);
    if (i<=2) putchar('0');
    putchar('\n');
    return 0;
}

Measured memory_bytes: 1732
#include<stdio.h>
#include<stdlib.h>
 
struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL
 
Node root;
 
Node treeMinimum(Node x){
  while(x->left != NIL){
    x = x->left;
  }
    return x;
}
 
Node treeSearch(Node u, int k){
  if(u == NIL || k == u->key) return u;
  if(k < u->key) return treeSearch(u->left,k);
  else return treeSearch(u->right,k);
 
}
 
Node treeSuccessor(Node x){
  Node y;
  if(x->right != NIL) return treeMinimum(x->right);
  y = x->parent;
  while(y != NIL && x == y->right){
    x = y;
    y = y->parent;
  }
    return y;
}
 
void treeDelete(Node z){
  Node y;
  Node x; 
 
  if(z->left == NIL || z->right == NIL) y = z;
  else y = treeSuccessor(z);
 
  if(y->left != NIL) x = y->left;
  else x = y->right;
 
  if(x != NIL) x->parent = y->parent;
  if(y->parent == NIL) root = x;
  else if(y == y->parent->left) y->parent->left = x;
  else y->parent->right = x;
 
  if(y != z) z->key = y->key;
}
 
void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;
 
  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
 
 while(x != NIL){
   y = x;
   if(z->key < x->key) x = x->left;
   else x = x->right;
 }
  
 z->parent = y;
 if(y == NIL){
   root = z;
 }
 else if(z->key < y->key) {
   y->left = z;
 }
 else {
   y->right = z; 
 }
  
  
}
 
void inorder(Node u){
  if(u->left != NIL)inorder(u->left);
  printf(" %d",u->key);
  if(u->right != NIL)inorder(u->right); 
}
void preorder(Node u){
  printf(" %d",u->key);
  if(u->left != NIL)preorder(u->left);
  if(u->right != NIL)preorder(u->right);
}
 
 
int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);
 
  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ){
        printf("yes");
      puts("");
      }
      else {
        printf("no");
        puts("");
      }
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      puts("");
      preorder(root);
      puts("");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }
 
  return 0;
}



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

int main() {
	int n;
	cin>>n;
	vector<double> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int m=n/2;
	m++;
	double dp[n+1][n+1];
	/*for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			dp[i][j]=0;
		}
	}*/
	memset(dp, 0.0, sizeof(dp));
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=i;j++){
			/*if(i==0){
				dp[i][j]=1;
			}*/
		/*	if(i==0&&j==0){
				continue;
			}*/
			/*if(j>i&&i==0){
				dp[i][j]=0;
			}*/
			if(j==0){
				dp[i][j]=dp[i-1][j]*(1-a[i-1]);
			}
			else{
				dp[i][j]=(a[i-1]*dp[i-1][j-1])+((1-a[i-1])*dp[i-1][j]);
			}
		}
		/*for(int j=0;j<=n;j++){
			cout<<dp[i][j]<<" ";
		}
		cout<<endl;*/
	}
	double s=0.0;
	for(int i=m;i<=n;i++){
		s+=dp[n][i];
	}
	cout<<setprecision(9)<<s;
	return 0;
}

Measured memory_bytes: 70528
n, m = map(int, input().split())
h = list(map(int, input().split()))
ans = [1 for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    if h[a-1] < h[b-1]:
        ans[a-1] = 0
    elif h[a-1] > h[b-1]:
        ans[b-1] = 0
    else:
        ans[a-1] = 0
        ans[b-1] = 0
print(sum(ans))


Measured memory_bytes: 20112
import java.io.*;

class Main{
         private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        private static void swap(String[] A, int i, int j){
                String tmp = A[i];
                A[i] = A[j];
                A[j] = tmp;
        }

        private static void printArray(String[] A){
                for(int i=0; i<A.length; i++){
                        System.out.print(A[i]);
                        if(i!=A.length-1)
                                System.out.print(" ");
                }
                System.out.println();
        }

        private static int getNum(String s){
                return Integer.parseInt(s.substring(1));
        }

        private static int bubbleSort(String[] A){
                int count = 0;
                for(int i=0; i<A.length; i++){
                        for(int j=A.length-1; j>i; j--)
                                if(getNum(A[j])<getNum(A[j-1])){
                                        swap(A, j, j-1);
                                        count++;
                                }

                }
                return count;
        }

        private static int selectionSort(String[] A){
                int count = 0;
                int mini = 0;

                for(int i=0; i<A.length-1; i++){
                        boolean doswap = false;
                        mini = i;
                        for(int j=i+1; j<A.length; j++)
                                if(getNum(A[j]) < getNum(A[mini])){
                                        mini = j;
                                        doswap = true;
                                }
                        if(doswap){
                                swap(A, i, mini);
                                count++;
                        }
                }
                return count;
        }

        private static boolean isStable(String[] A, String[] B){
                boolean stable = true;
                for(int i=0; i<A.length; i++){
                        if(!A[i].equals(B[i])){
                                stable = false;
                                break;
                        }
                }
                return stable;
        }

        public static void main(String[] args) throws IOException{
                int N = Integer.parseInt(br.readLine());
                String[] bubble = br.readLine().split(" ");
                String[] select = bubble.clone();
                bubbleSort(bubble);
                selectionSort(select);
                printArray(bubble);
                System.out.println("Stable");
                printArray(select);
                if(isStable(bubble, select))
                        System.out.println("Stable");
                else
                        System.out.println("Not stable");
        }
}

Measured memory_bytes: 24616
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long N, Li, Li1, Li2 , L0, L1;
  cin >> N;
  L0 = 2;
  L1 = 1;
  
  if(N == 1) {
    Li = L1;
  }
  else {
    Li2 = 2;
    Li1 = 1;
    for(int i = 0; i < N-1 ; i++){
      Li = Li1 + Li2;
      Li2 = Li1;
      Li1 = Li;
    }
  }
  cout << Li << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 998244353;
const int N = 200005;

int a[N], b[N];
LL f[N], c[20];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i];
    }
    f[1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            c[j] += (i - a[j] >= 1 ? f[i - a[j]] : 0) - (i - b[j] - 1 >= 1 ? f[i - b[j] - 1] : 0);

            f[i] = (f[i] + c[j]) % mod;
        }
    }
    cout << (f[n] + mod) % mod << endl;
    return 0;
}


Measured memory_bytes: 5156
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
#include <string>
#include <iostream>
#include <stack>

using namespace std;

int main(){
    int n, k;
    scanf("%d %d", &n, &k);
    double ans = 0.0;
    for(int i = 1; i < min(k, n+1); ++i){
        ans += pow(0.5, ceil(log2((double)k / i)));
    }
    ans /= n;
    if(n >= k){
        ans += (double)(n - k + 1) / n;
    }
    printf("%.12f\n", ans);
    return 0;
}


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

#define NINJA ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define deb(x) cout << #x << " " << x << endl;
#define fo(i,n) for(int i=0;i<n;i++)
#define Fo(i,k,n) for(int i=k;i<n;i++)
#define vi vector<int>
#define ii pair<int,int>
#define vii vector<ii>
#define ll long long
#define pb push_back
#define endl "\n"
#define mp map<int,int>
#define F first
#define S second
#define sz(v) (int)v.size()
#define mod 1000000007

ll n,m,k;
vector<ll> par,szz,ans;

ll find(ll x){
	if(par[x]==x) return x;
	else{
		ll r = find(par[x]);
		par[x] = r;
		return r; 
	}	
}

bool join(int x, int y){
	x = find(x), y = find(y);
	if(x==y) return false;
	if(x>y) swap(x,y);
	par[y] = x;
	szz[x] += szz[y];
	return true;
}

bool same(int x, int y){
	return (find(x)==find(y));
}

int main(){
	NINJA;

	cin >> n >> m >> k;
	fo(i,n){
		par.pb(i);
		szz.pb(1);
		ans.pb(0);
	}

	fo(i,m){
		ll f,s; cin >> f >> s;
		--f,--s;
		join(f,s);
		ans[f]--,ans[s]--;
	}

	fo(i,k){
		ll f,s; cin >> f >> s;
		--f,--s;
		if(same(f,s)){
			ans[f]--,ans[s]--;
		}
	}

	fo(i,n){
		ans[i] += szz[find(i)]-1;
		cout << ans[i] << " ";
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 3424
#pragma region header
#include <bits/stdc++.h>
using namespace std;

#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_CAT_I(x,y) x ## y
//#define CPP_STR(x) CPP_STR_I(x)
//#define CPP_STR_I(args...) #args
//#define ASSERT(expr...) assert((expr))

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;
//using f80 = __float80;
#pragma endregion

#pragma region const
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
#pragma endregion

#pragma region util
#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 ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

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

template<typename T, typename U, typename Comp = less<>>
bool chmax(T& xmax, const U& x, Comp comp = {}) {
	if (comp(xmax, x)) {
		xmax = x;
		return true;
	}
	return false;
}
template<typename T, typename U, typename Comp = less<>>
bool chmin(T& xmin, const U& x, Comp comp = {}) {
	if (comp(x, xmin)) {
		xmin = x;
		return true;
	}
	return false;
}
#pragma endregion

#pragma region init
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;
#pragma endregion

int main()
{
	i64 N, K;
	cin >> N >> K;
	string S;
	cin >> S;

	transform(S.begin() + K - 1, S.begin() + K, S.begin() + K - 1, ::tolower);
	cout << S << endl;
	return 0;
}


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

bool n, w, s, e;
bool solve() {
  string S;
  cin >> S;
  rep(i, S.size()) {
    char c = S[i];
    if (c == 'N')
      n = 1;
    else if (c == 'W')
      w = 1;
    else if (c == 'S')
      s = 1;
    else
      e = 1;
  }
  if ((n && !s) || (!n && s))
    return false;
  if ((w && !e) || (!w && e))
    return false;
  return true;
}

int main() {
  cout << (solve() ? "Yes" : "No") << endl;
  return 0;
}


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

int main() {
	int n;
	int q = 0;
	while (cin >> n) {
		if (q != 0)cout << endl;
		if (n == 0)return 0;
		string w[50];
		for (int i = 0;i < n;i++)cin >> w[i];
		vector<int>v;
		int now = 0;
		for (int i = 0;i < n - 1;i++) {
			for (int j = i;j < n;j++) {
				now += w[j].size();
				if (now == 5) {
					v.push_back(i);
					now = 0;
					break;
				}
				if (now >= 6) {
					now = 0;
					break;
				}
			}
		}
		now=0;
		int k = 0, flag = 0;
		int haiku[5] = { 5,7,5,7,7 };
		for (int i = 0;i < v.size();i++) {
			for (int j = v[i];j < n;j++) {
				now += w[j].size();
				if (now == haiku[k]) {
					k++;
					now = 0;
				}
				if (k == 5) {
					cout << v[i] + 1;
					q++;
					flag = 1;
					break;
				}
			}
			if (flag)break;
			now = 0;
			k = 0;
		}
	}
}


Measured memory_bytes: 3076
#include <bits/stdc++.h>
#define rep3(i, s, n, a) for (int i = (s); i < (int)(n); i += a)
#define rep2(i, s, n) rep3(i, s, n, 1)
#define rep(i, n) rep2(i, 0, n)

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

int main(){
    int n;
    cin >> n;
    vector<int> l;
    rep(i, n){
        int x;
        cin >> x;
        l.push_back(x);
    }
    sort(l.begin(), l.end());
    int cnt=0;
    rep(i, n-2){
        rep2(j, i+1, n-1){
            auto it = lower_bound(l.begin(), l.end(), l[i]+l[j]);
            auto pos = distance(l.begin(), it);
            cnt += max(0, (int)(pos) - j - 1);
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 3600
#include <stdio.h>
 
int main()
{
  int n1,n2,n3;
  
  scanf("%d%d%d", &n1, &n2, &n3);
  
  if(n1==n2 && n1==n3){
    puts("No");
  }else if(n1!=n2 && n1!=n3 && n2!=n3){
    puts("No");
  }
  else
    puts("Yes");
  
  return 0;
}

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    N %= 10;
    if (N == 2 || N == 4 || N == 5 || N == 7 || N == 9) {
        cout << "hon";
    }
    else if (N == 3) {
        cout << "bon";
    }
    else cout << "pon";
    cout << endl;

    return 0;
}

Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000009
main()
{
    int h,w,i,j;
    cin>>h>>w;
    char s[h+1][w+5];
    for(i=0;i<h;i++)
    {
        cin>>s[i];
    }
    int ans[h][w];
    memset(ans,0,sizeof(ans));
    if(s[0][0]=='#')ans[0][0]++;
    int a=1,b=1;
    while(a<h || b<w)
    {
        if(a<h)
        {
            for(i=0;i<=b-1;i++)
            {
                if(i==0)
                {
                    ans[a][i]=ans[a-1][i];
                    if(s[a][i]=='#' && s[a-1][i]=='.')ans[a][i]++;
                }
                else
                {
                    int u,v;
                    u=ans[a-1][i];
                    if(s[a][i]=='#' && s[a-1][i]=='.')u++;
                    v=ans[a][i-1];
                    if(s[a][i]=='#' && s[a][i-1]=='.')v++;
                    ans[a][i]=min(u,v);
                }
            }
        }
        if(b<w)
        {
            for(i=0;i<=b-1;i++)
            {
                if(i==0)
                {
                    ans[i][b]=ans[i][b-1];
                    if(s[i][b]=='#' && s[i][b-1]=='.')ans[i][b]++;
                }
                else
                {
                    int u,v;
                    u=ans[i-1][b];
                    if(s[i][b]=='#' && s[i-1][b]=='.')u++;
                    v=ans[i][b-1];
                    if(s[i][b]=='#' && s[i][b-1]=='.')v++;
                    ans[i][b]=min(u,v);
                }
            }
        }
        if(a<h && b<w)
        {
            int u,v;
            u=ans[a-1][b];v=ans[a][b-1];
            if(s[a][b]=='#' && s[a-1][b]=='.')u++;
            if(s[a][b]=='#' && s[a][b-1]=='.')v++;
            ans[a][b]=min(u,v);
        }
        if(a<h)a++;
        if(b<w)b++;
    }
    /*for(i=0;i<h;i++)
    {
        for(j=0;j<w;j++)
        {
            printf("%d ",ans[i][j]);
        }
        printf("\n");
    }*/
    printf("%d\n",ans[h-1][w-1]);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define input(n,a) int n;cin>>n;int a[n];for(int i=0;i<n;i++)cin>>a[i];
#define ouput(n,a) for(int i=0;i<n;i++)cout<<a[i]<<" ";
#define sort(v) sort(v,v+n);
#define endl "\n"
#define umap unordered_map<int,int>
#define uset unordered_set<int>
void solve()
{
	string s;
	cin>>s;
	int len=s.length();
	if(s[len-1]!='s')
		s.push_back('s');

	else
	{
		s.push_back('e');
		s.push_back('s');
	}
	cout<<s;
}


int32_t main()
{
	int t=1;
	//cin>>t;
	while(t--)
		solve();
}


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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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




void solve() {
    int N; ld D;
    cin >> N >> D;
    ll res = 0;
    rep(i, N){
        ld a, b; cin >> a >> b;
        ld tmp = sqrt(a*a + b*b);
        if(tmp <= D) res++;
    }
    cout << res << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


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

int main(){
int n, a, b, c, x, f, ans;
vector<int> nvec;
	while(1){
		cin >> n >> a >> b >> c >> x;
		if(n == 0 && a == 0 && b == 0 && c == 0 && x == 0) break;

		nvec.clear();
		for(int i = 0; i < n; i++){
			int y;
			cin >> y;
			nvec.push_back(y);
		}

		ans = 0;
		f = 0;
		vector<int>::iterator nit;
		for(nit = nvec.begin(); ; ){
			if((*nit) == x){
				nit++;
				if(nit == nvec.end()){
					ans = f;
					break;
				}
			}
			x = (a * x + b) % c;
			f++;
			if(f > 10000){
				ans = -1;
				break;
			}
		}

		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;
template <class T> inline void chmin(T & a, T const & b) { a = min(a, b); }

template <typename UnaryPredicate>
int64_t binsearch(int64_t l, int64_t r, UnaryPredicate p) {
    assert (l <= r);
    -- l;
    while (r - l > 1) {
        int64_t m = l + (r - l) / 2;  // to avoid overflow
        (p(m) ? r : l) = m;
    }
    return r;
}

int main() {
    // input
    int n; cin >> n;
    vector<ll> a(n);
    REP (i, n) cin >> a[i];

    // solve
    vector<ll> acc(n + 1);
    partial_sum(ALL(a), acc.begin() + 1);
    ll answer = LLONG_MAX;
    REP (m, n + 1) {
        int l0 = binsearch(0, m + 1, [&](int l) {
            ll b = acc[l] - acc[0];
            ll c = acc[m] - acc[l];
            return b >= c;
        });
        int r0 = binsearch(m, n + 1, [&](int r) {
            ll d = acc[r] - acc[m];
            ll e = acc[n] - acc[r];
            return d >= e;
        });
        REP3 (l, max(0, l0 - 3), min(m, l0 + 3) + 1) {
            REP3 (r, max(m, r0 - 3), min(n, r0 + 3) + 1) {
                ll b = acc[l] - acc[0];
                ll c = acc[m] - acc[l];
                ll d = acc[r] - acc[m];
                ll e = acc[n] - acc[r];
                array<ll, 4> bcde = {{ b, c, d, e }};
                chmin(answer, *max_element(ALL(bcde)) - *min_element(ALL(bcde)));
            }
        }
    }

    // output
    cout << answer << endl;
    return 0;
}


Measured memory_bytes: 3328
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define pb(a) push_back(a)

typedef long long ll;
using namespace std;

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

//const int dy[] = { 0, 0, 1, -1 };
//const int dx[] = { 1, -1, 0, 0 };
const int dx[8] = { 1, 0, -1, 0, 1, -1, -1, 1 };
const int dy[8] = { 0, 1, 0, -1, 1, 1, -1, -1 };
ll gcd(ll a, ll b);
ll lcm(ll x, ll y);
ll t[120] = {};

int main()
{
	int n;
	ll ans;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> t[i];
	}

	ans = 1;
	for (int i = 0; i < n; i++) {
		ans = lcm(ans, t[i]);
	}
	cout << ans << endl;
	return 0;
}

ll gcd(ll a, ll b) {
	while (a && b) {
		if (a >= b) {
			a %= b;
		}
		else {
			b %= a;
		}
	}
	return a + b;
}


ll lcm(ll x, ll y) {
	return x / gcd(x, y) * y;//先に割り算をして掛けられる数を小さくして掛け算を行う
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define mk make_pair
using namespace std;
string s1[50],s2[50];
int dx1[]={1,-1,0,0,},dy1[]={0,0,1,-1};
int dx2[]={-1,1,0,0,},dy2[]={0,0,1,-1};
int w,h,gx1,gx2,gy1,gy2;
bool vis[51][51][51][51];
bool bfs(int x1,int y1,int x2,int y2){
  queue<int>q;
  q.push(x1+y1*100+x2*10000+y2*1000000);
  while(!q.empty()){
    int p=q.front();q.pop();
    x1=p%100;y1=p%10000/100;
    x2=p%1000000/10000;y2=p/1000000;
    for(int i=0;i<4;i++){
      int x3=x1+dx1[i],y3=y1+dy1[i];
      int x4=x2+dx2[i],y4=y2+dy2[i];
      if(x3<0)x3=x1;if(x4<0)x4=x2;
      if(y3<0)y3=y1;if(y4<0)y4=y2;
      if(x3>=w)x3=x1;if(x4>=w)x4=x2;
      if(y3>=h)y3=y1;if(y4>=h)y4=y2;
          if(s1[y3][x3]=='#')y3=y1,x3=x1;
          if(s2[y4][x4]=='#')y4=y2,x4=x2;
          if(x1==gx1&&y1==gy1&&x2==gx2&&y2==gy2)return 1;
          if(!(x3==gx1&&y3==gy1&&(x4!=gx2||y4!=gy2)))
          if(!((x3!=gx1||y3!=gy1)&&x4==gx2&&y4==gy2))
          if(!vis[x3][y3][x4][y4]){
            vis[x3][y3][x4][y4]=1;
            q.push(x3+y3*100+x4*10000+y4*1000000);
          }
        }
    }
    return 0;
}
int main(){
  int x1,y1,x2,y2;
  while(cin>>w>>h,w){
    r(i,h)cin>>s1[i]>>s2[i];
    r(i,h)r(j,w){
      if(s1[i][j]=='L')x1=j,y1=i;
      if(s2[i][j]=='R')x2=j,y2=i;
      if(s1[i][j]=='%')gx1=j,gy1=i;
      if(s2[i][j]=='%')gx2=j,gy2=i;
    }
    r(i,51)r(j,51)r(k,51)r(l,51)vis[l][k][j][i]=0;
    vis[x1][y1][x2][y2]=1;
    if(bfs(x1,y1,x2,y2))cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }
}

Measured memory_bytes: 9752
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MOD 1000000007
#define PI 3.141592653589793

int main(){
    vector<int> v(3);
    for(int i = 0; i < 3; i++) cin >> v[i];
    sort(v.begin(), v.end());
    cout << (v[0] + v[1] == v[2] ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
m[5][5];main(T,i,j,k,r,M){
for(scanf("%d",&T);T;printf("%d\n",r),T--){
	for(j=0;j<5;j++)for(r=i=0;i<5;m[j][i]=r,i++)if(scanf("%d",&k),k)r++;else r=0;
	for(r=i=0;i<5;i++)for(j=0;j<5;j++)for(M=9,k=j;k<5;k++){
		if(M>m[k][i])M=m[k][i];
		if(r<M*(k-j+1))r=M*(k-j+1);
	}
}exit(0);}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
const int N=105;
int n,a[N];
int main(){
	cin >> n;
	for (int i=1;i<=n;i++)
		cin >> a[i];
	int tot=0;
	for (int i=1;i<=n;i++)
		tot+=a[i];
	int t=1;
	for (int i=1;i<=n;i++)
		if (abs(a[i]*n-tot)<abs(a[t]*n-tot))
			t=i;
	cout << t-1;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>

int mp[10][10],book[10][10],n,flag,a[10];

int check(int x,int y)
{
	for(int i=0;i<8;i++)//左右
	{
		if(book[x][i]==1) return 0;
	}
	for(int i=0;i<8;i++)//上下
	{
		if(book[i][y]==1) return 0;
	}
	for(int i=x,j=y;i>=0&&j>=0;i--,j--)//左上
	{
		if(book[i][j]==1) return 0;
	}
	for(int i=x,j=y;i<8&&j<8;i++,j++)//右下
	{
		if(book[i][j]==1) return 0;
	}
	for(int i=x,j=y;i<8&&j>=0;i++,j--)//左下
	{
		if(book[i][j]==1) return 0;
	}
	for(int i=x,j=y;i>=0&&j<8;i--,j++)//右上
	{
		if(book[i][j]==1) return 0;
	}
	return 1;
}

void dfs(int x,int cnt)
{
	if(cnt>=8-n)
	{
		flag=1;
		return;
	}
	if(x>8) return;
	for(int i=0;i<8;i++)
	{
		if(a[x]==1)
		{
			dfs(x+1,cnt);
			if(flag) return;
		}

		if(book[x][i]==0&&check(x,i)==1)
		{
			book[x][i]=1;
			mp[x][i]=1;
			dfs(x+1,cnt+1);
			if(flag) return;
			book[x][i]=0;
			mp[x][i]=0;
		}
	}

}

int main()
{
	while(~scanf("%d",&n))
	{
		memset(mp,0,sizeof(mp));
		memset(book,0,sizeof(book));
		memset(a,0,sizeof(a));
		flag=0;
		int x,y;
		for(int i=0;i<n;i++)
		{
			scanf("%d%d",&x,&y);
			a[x]=1;
			mp[x][y]=1;
			book[x][y]=1;
		}

		dfs(0,0);

		for(int i=0;i<8;i++)
		{
			for(int j=0;j<8;j++)
			{
				if(mp[i][j]==0) printf(".");
				else printf("Q");
			}
			printf("\n");
		}
	}
	return 0;
}



Measured memory_bytes: 2112
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
template<class S, class T> inline S max_L(S a,T b){
  return a>=b?a:b;
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  int s=0;
  int m=0;
  char f[10];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(unsigned x){
  int s=0;
  char f[10];
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(long long x){
  int s=0;
  int m=0;
  char f[20];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(unsigned long long x){
  int s=0;
  char f[21];
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(double x){
  printf("%.15f",x);
}
inline void wt_L(const char c[]){
  int i=0;
  for(i=0;c[i]!='\0';i++){
    putchar_unlocked(c[i]);
  }
}
inline void wt_L(string &x){
  int i=0;
  for(i=0;x[i]!='\0';i++){
    putchar_unlocked(x[i]);
  }
}
int main(){
  int A;
  int B;
  rd(A);
  rd(B);
  wt_L(max_L(0, A-2*B));
  wt_L('\n');
  return 0;
}
// cLay varsion 20191027-1

// --- original code ---
// {
//   int A, B;
//   rd(A,B);
//   wt(max(0, A-2B));
// }


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

#define gcd(a,b)		__gcd(a,b)
#define lcm(a,b)		(a*b)/gcd(a,b)
#define ff              first
#define ss              second
#define int             long long
#define pb              emplace_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             INT64_MAX
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define all(x)			x.begin(),x.end()
#define digits(x)		floor(log10(x))+1
#define FIO				ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

class dsu {
private:
	int *id;
	int* sz;

	int root(int i) {
		while (i != id[i]) {
			id[i] = id[id[i]];
			i = id[i];
		}
		return i;
	}
public:
	int n;
	dsu(int v) {
		n = v;
		id = new int[n];
		sz = new int[n];

		for (int i = 0; i < n; i++) {
			id[i] = i;
			sz[i] = 0;
		}
	}

	bool find(int p , int q) {
		return root(p) == root(q);
	}

	void join(int p , int q) {
		int i = root(p);
		int j = root(q);
		if (i == j) {
			return;
		}
		if (sz[i] < sz[j]) {
			id[i] = j ;
			sz[j] += sz[i];
		}
		else {
			id[j] = i;
			sz[i] += sz[j];
		}
	}
};

class BIT {
private:
	int* FT;
	int n;
public:
	void updateBIT(int index , int val) {
		index += 1;
		while (index <= n) {
			FT[index] += val;
			index += (index & (-index));
		}
	}

	int getSum(int index) {
		index += 1;
		int sum = 0 ;
		while (index > 0) {
			sum += FT[index];
			index -= (index & (-index));
		}
		return sum;
	}


	BIT(int* a , int v) {
		n = v ;
		FT = new int[n + 1];
		for (int i = 1 ; i <= n ; i++) {
			FT[i] = 0 ;
		}
		for (int i = 0 ; i < n ; i++) {
			updateBIT(i, a[i]);
		}
	}
};

int nCr(int n , int r ) {
	int p = 1, k = 1;

	if (n - r < r ) {
		r = n - r;
	}
	if (r != 0) {
		while (r != 0) {
			p *= n ;
			k *= r ;
			int m = __gcd(p, k);
			p /= m;
			k /= m;
			n--;
			r--;
		}
	}
	else {
		p = 1;
	}
	return p ;
}

int modPower(int x, int y , int p) {
	//Used to calculate (x^y)%p
	int res = 1;
	if (y == 0) {
		return 1;
	}

	x = x % p;
	if (x == 0) {
		return 0  ;
	}

	while (y > 0) {
		if (y & 1) {
			res = (res * x) % p;
		}

		y >>= 1;
		x = (x * x) % p;
	}
	return res ;

}

void rotate(string& s) {
	string temp = "";
	int n = s.length();
	temp =  s[n - 1];
	for (int i = 0 ; i < n - 1 ; i++) {
		temp = temp + s[i];
	}
	s = temp ;
	return;
}


int32_t main() {
	FIO;

	string s , t;
	cin >> s >> t;
	string c = s ;
	rotate(s);


	bool flag = false;
	while (s != c) {
		if (s == t) {
			flag = true;
			break;
		}
		else {
			rotate(s);
		}
	}
	if (c == t) {
		flag = true;
	}
	flag ? cout << "Yes" : cout << "No";





	return 0;
}


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

#define ll  long long
#define PII pair<ll,ll>
#define VI  vector<ll>
#define VB  vector<bool>
#define VC vector<char>
#define VVI vector<vector<ll>>
#define VVC vector<vector<char>>
#define VS  vector<string>
#define VP  vector<PII>
#define lf(i,a,b) for(ll i=a;i<=b;i++)
#define lr(i,a,b) for(ll i=a;i>=b;i--)
#define lfl(i,v) for(ll i=0;i<v.size();i++)
#define lrl(i,v) for(ll i=(ll)(v.size())-1;i>=0;i--)
#define chk2(a,b) cout<<"check :  "<<a<<" "<<b<<endl
#define chk3(a,b,c) cout<<"check :  "<<a<<" "<<b<<" "<<c<<endl
#define chk4(a,b,c,d) cout<<"check :  "<<a<<" "<<b<<" "<<c<<" "<<d<<endl
#define chk5(a,b,c,d,e) cout<<"check :  "<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<e<<endl
#define l_b(v,k)  lower_bound(v.begin(),v.end(),k)-v.begin()
#define u_b(v,k)  upper_bound(v.begin(),v.end(),k)-v.begin()
#define mod 1000000007
#define sort(v) sort(v.begin(),v.end())
#define p_b push_back
#define p_f push_front
#define m_p make_pair
#define fir first
#define sec second
#define sz size()
ll n,m,k;
VI v;
VI cmprs(VI &ht)
    {   VP vp(n);
        VI ans(n+1);
        lf(i,0,n-1)
        {   vp[i]=m_p(ht[i+1],i+1);
        }
        sort(vp);
        lf(i,1,n)
        {   ans[vp[i-1].sec]=i;
        }
        // cout<<endl;
        // lf(i,1,n)
        //     cout<<ans[i]<<" ";
        // cout<<endl;
        return ans;
    }

vector<ll>tree(800000,0);
ll qry(vector<ll>&tree,ll ti,ll fi,ll ls,ll str,ll end)
    {   ll mid=(ls+fi)/2;
        if(str>ls || end<fi || fi>ls)
            return 0;   
        if(str<=fi && ls<=end)
            return tree[ti];
        else 
            return max(qry(tree,ti*2,fi,mid,str,end),qry(tree,ti*2+1,mid+1,ls,str,end));
    }
void updt(vector<ll>&tree,ll ti,ll fi,ll ls,ll ind,ll val)
    {   if(ind>ls || ind<fi || ls<fi)   
            return ;
        else if(ind<=fi && ls<=ind)
        {   tree[ti]+=val;
        }
        else
        {   ll mid=(ls+fi)/2;
            updt(tree,ti*2,fi,mid,ind,val);
            updt(tree,ti*2+1,mid+1,ls,ind,val);
            tree[ti]=max(tree[ti*2],tree[ti*2+1]);
        }
    }

int main() 
{   cin>>n;
    VI a=VI(n+1);
    VI ht=VI(n+1);
    lf(i,1,n)
    {   cin>>ht[i];
    }
    ht=cmprs(ht);
    lf(i,1,n)
        cin>>a[i];
    VI dp(n+1,0);
    lf(i,1,n)
    {   dp[i]=a[i];
        ll sum=qry(tree,1,0,n+1,1,ht[i]-1);
        dp[i]=max(dp[i],a[i]+sum);
        updt(tree,1,0,n+1,ht[i],dp[i]);
    }

    ll maxi=0;
    lf(i,1,n)
    {    maxi=max(maxi,dp[i]);}//cout<<dp[i]<<" ";}
    cout<<maxi<<endl;
}

Measured memory_bytes: 14336
package main
import (
  "bufio"
  "os"
  "strconv"
  "strings"
  "fmt"
)

func Solve() {
  var N, M, K int
  var A, B []int
  NextInt(&N, &M, &K)
  NextIntSlice(&A)
  NextIntSlice(&B)
  SA := make([]int, N + 1)
  for i, a := range A { SA[i + 1] = SA[i] + a }
  SB := make([]int, M + 1)
  for i, b := range B { SB[i + 1] = SB[i] + b }
  F := func(K int) int {
    if K >= SB[M] { return M }
    gek, ltk := 0, M
    for 1 < ltk - gek {
      med := (ltk + gek) / 2
      if SB[med] > K {
        ltk = med
      } else {
        gek = med
      }
    }
    return gek
  }
  ans := 0
  for i, sa := range SA {
    if sa > K { continue }
    ans = MaxInt(i + F(K - sa), ans)
  }
  Write(ans)
}

func main() {
  Solve()
  Output()
}

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt(A ...*int) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.Atoi(L[i])
  }
}
func NextIntSlice(A *[]int) {
  L := strings.Split(NextLine(), " ")
  (*A) = make([]int, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.Atoi(l)
  }
}
func NextFloat(A ...*float64) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.ParseFloat(L[i], 64)
  }
}
func NextFloatSlice(A *[]float64) {
  L := strings.Split(NextLine(), " ")
  (*A) = make([]float64, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.ParseFloat(l, 64)
  }
}
func Write(S ...interface{}) {
  fmt.Fprintln(writer, S...)
}
func WriteIntSlice(A []int) {
  B := make([]interface{}, len(A))
  for i, a := range A { B[i] = a }
  Write(B...)
}
func Output() {
  _ = writer.Flush()
}
func MaxInt(A ...int) int {
  max := A[0]
  for _, a := range A {
    if max < a { max = a }
  }
  return max
}
func MinInt(A ...int) int {
  min := A[0]
  for _, a := range A {
    if a < min { min = a }
  }
  return min
}
func SumInt(A ...int) int {
  sum := 0
  for _, a := range A {
    sum += a
  }
  return sum
}
func AbsInt(x int) int {
  if x < 0 { x = -x }
  return x
}

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

#ifdef DEBUG
    #define IFD if(true)
#else
    #define IFD if(false)
#endif

#include <vector>

// 要素個数カウント付き Union Find

// 要素の型。int か long あたりを想定
template<typename T_uf_data>

class UnionFind
{
private:
    std::vector<T_uf_data> par; // 親 (parent) を指す
    std::vector<T_uf_data> rnk;
    std::vector<T_uf_data> cnt; // 引数の値が含まれるグループの要素数（ルートノードのみが意味を持つ）

    // その値を持つルートノードを返す
    T_uf_data find_root(int x)
    {
        if(par[x] == x) {
            return x;
        } else {
            return par[x] = find_root(par[x]);
        }
    }

public:

    // コンストラクタの引数で要素数を指定
    UnionFind(int n) : par(n), rnk(n), cnt(n)
    {
        for(int i = 0; i < n; i++) {
            par[i] = i; // 親を持たないノードは自分自身を親としておく
            rnk[i] = 0;
            cnt[i] = 1; // 初期状態ではすべてのノードの要素数は 1
        }
    }

    // 二つの要素をグループ化
    void Unite(int x, int y)
    {
        x = find_root(x);
        y = find_root(y);
        if(x == y) return;

        if(rnk[x] < rnk[y]) {
            // y が親になる
            par[x] = y;
            cnt[y] += cnt[x];
        } else {
            // x が親になる
            par[y] = x;
            cnt[x] += cnt[y];
            if(rnk[x] == rnk[y]) rnk[x]++;
        }
    }

    // x と y が同じグループかを返す
    bool isSameGroup(int x, int y)
    {
        return find_root(x) == find_root(y);
    }

    // x を含むグループの要素数を返す
    int Size(int x)
    {
        return cnt[find_root(x)];
    }
};


int main()
{
    int N, M, A[100001], B[100001];
    long long ans[100001];

    cin >> N >> M;
    UnionFind<int> uf(100001);

    for(int i = 1; i <= M; i++) {
        cin >> A[i] >> B[i];
    }
    ans[M] = (long long)N * (N - 1) / 2;

    for(int i = M - 1; i >= 1; i--) {
        ans[i] = ans[i + 1];
        if(!uf.isSameGroup(A[i + 1], B[i + 1])) {
            ans[i] -= (long long)uf.Size(A[i + 1]) * uf.Size(B[i + 1]);
            uf.Unite(A[i + 1], B[i + 1]);
        }
    }

    for(int i = 1; i <= M; i++) {
        cout << ans[i] << endl;
    }
    
    return 0;
}


Measured memory_bytes: 4096
def main():
    D = ((-1,0), (0,-1), (1,0), (0,1))
    while True:
        n = int(input())
        if n==0:
            exit()
        sx = [0]
        sy = [0]

        for i in range(n-1):
            ni, di = [int(x) for x in input().split()]
            sx.append(sx[ni]+D[di][0])
            sy.append(sy[ni]+D[di][1])
        w = max(sx)-min(sx)+1
        h = max(sy)-min(sy)+1
        print(w,h)

if __name__ == '__main__':
    main()

Measured memory_bytes: 6720