akhauriyash/Code-Regression huggingface dataset:
def main():
    N=int(input())
    ans = [None]*N
    
    print(0)
    s=input()
    if s=="Vacant":return
    ans[0] = s=="Male"
    l=1
    r=N-1
    while l+1<r:
        i = (l+r)//2
        print(i)
        s=input()
        if s=="Vacant":return
        ans[i] = s=="Male"
        if (ans[i]==ans[0]) ^ (i%2!=0):
            l = i
        else:
            r = i
    print(l)
    s=input()
    if s=="Vacant":return
    print(r)
    return

main()

Measured memory_bytes: 4424
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Map.Entry;

import java.util.PriorityQueue;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;


public class Main {
	
	public static void main(String[] args) throws IOException {	
		try(final Scanner sc = new Scanner(System.in)){
			final int N = sc.nextInt();
			final int K = sc.nextInt();
			final double EPS = 1e-15;
			
			long[] as = new long[N];
			for(int i = 0; i < N; i++) {
				as[i] = sc.nextLong();
			}
			
			for(int i = K; i < N; i++) {
				final long p = as[i - K];
				final long n = as[i];
				
				
				if(p < n) {
					System.out.println("Yes");
				}else {
					System.out.println("No");
				}
			}
		}
	}

	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while(!hasNext()){
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
		

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public int[] nextIntArray(int n) throws IOException {
			final int[] ret = new int[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextInt();
			}
			return ret;
		}

		public long[] nextLongArray(int n) throws IOException {
			final long[] ret = new long[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextLong();
			}
			return ret;
		}

		public void close() throws IOException {
			br.close();
		}
	}
}


Measured memory_bytes: 59652
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define max(p,q) ((p)>(q)?(p):(q))
#define min(p,q) ((p)<(q)?(p):(q))
#define chmax(a,b) ((a)=(a)>(b)?(a):(b))
#define chmin(a,b) ((a)=(a)<(b)?(a):(b))
#define abs(p) ((p)>=(0)?(p):(-(p)))
#define MOD 1000000007
ll power(ll a,ll b){ll r=1;rep(i,b){r*=a;}return r;}
#define swap(a,b) do{ll w=(a);(a)=(b);(b)=w;}while(0)
#define swapd(a,b) do{double w=(a);(a)=(b);(b)=w}while(0)

//your code here!

int cmp(const void *a, const void *b){
    ll A=*(ll *)a, B=*(ll *)b;
    if(A==B)return 0;
    else return A>B ? 1:-1;//昇順ソート
}

int main(void){
    ll N, L[10010], ans=0;
    scanf("%lld", &N);
    rep(i, N) scanf("%lld", L+i);
    qsort(L, N, sizeof(ll), cmp);
    for(ll i=N-1; i>=2; i--) {
        ll j=i-1;
        while(j>=1) {
            ll k=j-1;
            while(k>=0) {
                if(L[i]<L[j]+L[k]) ans++;
                else break;
                k--;
            }
            j--;
        }
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 252
def selectionSort(N, A):
    c=  0
    for i in range(N):
        minj = i
        for j in range(i,N):
            if A[j] < A[minj]:
                minj = j
        if i != minj:
            A[i], A[minj] = A[minj], A[i]
            c += 1
    return (A, c)


A, c = selectionSort(int(input()), list(map(int, input().split())))
print(*A)
print(c)

Measured memory_bytes: 7796
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<array>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<numeric>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<unordered_map>
#include<queue>
#include<vector>
using namespace std;

//#define int long long
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define dump(o) {cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) {cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
const int MOD = 1e9 + 7;

signed main() {
	char c[110][110] = {};
	int cnt[110][110] = {};
	for (int H, W; cin >> H >> W&&H;) {
		memset(cnt, 0, sizeof(cnt));
		rep(i, 0, H)rep(j, 0, W)cin >> c[i][j];
		int i = 0, j = 0;
		while (true) {
			cnt[i][j]++;
			if (cnt[i][j] > 10) {
				cout << "LOOP" << endl;
				break;
			}
			else {
				bool flag = false;
				switch (c[i][j])
				{
				case '.':
					cout << j << " " << i << endl;
					flag = true;
					break;
				case '>':
					j++;
					break;
				case '<':
					j--;
					break;
				case '^':
					i--;
					break;
				case 'v':
					i++;
					break;
				default:
					break;
				}
				if (flag)break;
			}
		}
	}
	return 0;
}

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

int main(void) {
    int height, width;
    cin >> height >> width;
    char board[height][width];
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            cin >> board[i][j];
        }
    }

    // # マスの上下左右 4 マスに # マスが存在するか調べる
    int di[4] = {1, -1, 0, 0};
    int dj[4] = {0, 0, -1, 1};
    bool not_exist = false;
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            if (board[i][j] == '#') {
                for (int k = 0; k < 4; k++) {
                    if (i+di[k] < 0 || height <= i+di[k]) {
                        continue;
                    }
                    if (j+dj[k] < 0 || width <= j+dj[k]) {
                        continue;
                    }
                    if (board[i+di[k]][j+dj[k]] == '#') {
                        not_exist = false;
                        break;
                    } else {
                        not_exist = true;
                    }
                }
            }
            if (not_exist) {
                break;
            }
        }
        if (not_exist) {
            break;
        }
    }

    if (not_exist) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }
}

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

int main(void){
    // 変数宣言
    char *result = "No";
    int i, n, m;
    
    int count = 0;
    
    int *points;
    points = ( int* )malloc( sizeof (int) * n );
    double border_point;
    double vote_point;
    double sum = 0.0;

    // 標準入力
    scanf( "%d %d", &n, &m );

    for( i = 0; i < n; i++ ){
        scanf( "%d", &points[i] );
        sum += points[i];
    }

    // 条件判定
    border_point = 1.0 / ( 4.0 * m ) ;
    for( i = 0; i < n; i++ ){
        vote_point = points[ i ] / sum;
        if( border_point <= vote_point ){
            count++;
        }
    }
    
    if( count >= m ){
        result = "Yes";
    }

    // 出力
    puts( result );

    return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
#include<stdlib.h>
int inc(const void *a, const void *b)
{
	return *(int *)a-*(int *)b;
}
int main()
{
	int n,a[10000],l=0,r=1,m,cnt=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&a[i]);
	qsort(a,n,sizeof(int),inc);
	m=2;
	for(int i=0;i<n-2;i++)
	{
		for(int j=i+1;j<n-1;j++)
		{
			for(int k=j+1;k<n;k++)
			{
				if(a[i]+a[j]>a[k])cnt++;
				else break;
			}
		}
	}
	printf("%d\n",cnt);
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>
#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define P pair<int, int>
#define sz(x) x.size()
#define all(x) (x).begin(),(x).end()
#define V vector<int>
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;
}

using namespace std;
typedef long long ll;
using Graph = vector<vector<int>>;
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}


const long long MOD = 1000000007;
const long long INF = 1LL << 60;

// pair -> vector<pair<int,int>> 
//		   AandB.push_back(make_pair(a[i],b[i]))



signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;
	vector<int>d(n); rep(i, n)cin >> d[i];
	set<int>ans;
	rep(i, n)ans.insert(d[i]);
	cout << ans.size() << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
	int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int a,b;
    	cin>>a>>b;
        if(a%b!=0){
        	cout<<a%b<<endl;
		}else cout<<b<<endl;
    }
    return 0;
}

Measured memory_bytes: 1160
#include "bits/stdc++.h"

using namespace std;

using ll = long long int;
using ld = long double;

using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;

const int INF = (1 << 30) - 1;
const ll INF64 = ((ll)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

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

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

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

	int n;
	cin >> n;

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

	ll res = t[0];
	for (int i = 1; i < n; i++) {
		res = lcm(res, t[i]);
	}

	cout << res << endl;
	return 0;
}


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

using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++)
#define REP(i,n) for(int i = 0;i < (n) ; i++)
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
int MOD = 998244353;
signed main(){

    int n;
	cin >> n;
	vll l(n);
	rep(i,n)cin >> l[i];
	l.pb(-1);
	l.pb(INF);
	SORT(l);

	int ans = 0;

	for(int i = 1;i <= n-2;i++){
		for(int j = i+1;j <= n-1;j++){
			int mini = abs(l[i]-l[j]);
			int maxi = l[i]+l[j];
			int L,R;
			ll ok = n+1;
			ll ng = 0;

			while(abs(ok-ng)>1){
				ll mid = (ok+ng)/2;
				if(mini < l[mid]){
					ok = mid;
				}else{
					ng = mid;
				}
			}
			L = ok;

			ok = 0;
			ng = n+1;

			while(abs(ok-ng)>1){
				ll mid = (ok+ng)/2;
				if(l[mid] < maxi){
					ok = mid;
				}else{
					ng = mid;
				}
			}
			R = ok;
			L = max(L,j+1);
			if(R == n+1 || L == 0 || L > R)continue;
			else ans += R-L+1;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <cctype>
#define ll          long long int
#define PB          push_back
#define PII         pair<ll int,ll int>
#define VI          vector<ll int>
#define ALL(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define SZ(x)       (ll int)x.size()
#define hell2        998244353
#define hell9        1000000007
#define FO(i,a,b)    for(i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define BS          binary_search
#define MP          make_pair
using namespace std;
#define fio ios_base::sync_with_stdio(false);cin.tie(0);
/*ll power(ll x, ll y, ll p) 
{ 
    ll res = 1;
    x = x % p;  
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x) % p; 
      y = y>>1; 
        x = (x*x) % p; 
    } 
    return res; 
} 
ll modInverse(ll n, ll p) 
{ 
    return power(n, p-2, p); 
} 
ll fac[500000]={0};
ll done=1;
ll ncrModP(ll n, ll r, ll p) 
{ 
   if (r==0) 
      return 1; 
     
    fac[0] = 1; 
    if(n>done)
    {for (ll i=done ; i<=n; i++) 
        fac[i] = (fac[i-1]*i)%p;}
        done=max(done,n); 
  
    return (fac[n]* modInverse(fac[r], p) % p * 
            modInverse(fac[n-r], p) % p) % p; 

} 
/*ll ncrM(ll n, ll r, ll p) 
{ 
    if (r > n - r) 
        r = n - r; 
    ll C[r + 1]; 
    memset(C, 0, sizeof(C)); 
    C[0] = 1; 
    for (ll i = 1; i <= n; i++) { 
        for (ll j = min(i, r); j > 0; j--) 
      C[j] = (C[j] + C[j - 1]) % p; 
    } 
    return C[r]; 
}
map<ll,ll>f;
ll done=2;
ll fib(ll k)
{
    ll i;f[0]=1;f[1]=1;f[2]=2;
    if(k<=done)return f[k];
    for(i=done;i<=k;i++)f[i]=(f[i-1]%hell9+f[i-2]%hell9)%hell9;
    done=k;
    return f[k]%hell9;
}*/
int main()
{
//  #ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//  #endif
    fio
    ll n,i,k,j;
    cin>>n>>k;
    ll a[n];ll dp[n];
    FO(i,0,n)cin>>a[i];
    dp[0]=0;
    FO(i,1,n)
    {dp[i]=hell9;
        for(j=1;j<=(min(i,k));j++)
        {
        dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));
        }
    }
    cout<<dp[n-1];
    return 0;
}

Measured memory_bytes: 1792
N = int(input())
D,X = map(int, (input().split()))
A=[]
sum=X
for i in range(N):
	A.append(int(input()))
for i in range(len(A)):
	sum=sum+int(D/A[i])+1
	#if isinstance(D/A[i], int):
	if D/A[i]==int(D/A[i]):
		sum=sum-1
print(sum)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
long long N, K, sum;
int main() {
	cin >> N >> K;
	if (K == 0) {
		cout << N * N << endl;
		return 0;
	}
	for (int i = K + 1; i <= N; i++) {
		long long D = (N + 1) / i;
		long long E = D * (i - K);
		long long F = (N + 1) % i;
		long long G = max(0LL, F - K);
		sum += E + G;
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(30);
#define ll long long
#define pi 3.14159265359
using namespace std;

int main()
{
    IOS;
    string s;
    cin>>s;
    int x=s.size()-1;
    if(s[x]=='3') cout<<"bon";
    else if (s[x]=='0' || s[x]=='1' || s[x]=='6' || s[x]=='8') cout<<"pon";
    else cout<<"hon";
    return 0;
}

Measured memory_bytes: 3620
N=int(input())
L=list(map(int,input().split()))
ANS=0
#MIN_L=[L[0]] * N
TMP_MIN = L[0]
#print(MIN_L)
for i in range(0,N):
  #print(TMP_MIN, L[i])
  if TMP_MIN >= L[i]:
    TMP_MIN = L[i]
    ANS += 1    
print(ANS)

Measured memory_bytes: 24744
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define M 1000000007
#define sz(a) (ll)a.size()
#define pll pair<ll,ll>
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define sep(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define mll map<ll,ll>
#define vl vector<ll>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(),a.end()
#define F first
#define S second
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll n,p[11],g,a=0,b=0,c=0;
void f(ll d,ll ans,ll a,ll b,ll c)
{
	if(d==11)
		return;
	if(ans>=1&&ans<=n&&a&&b&&c)
		g++;
	f(d+1,ans+3*p[d],1,b,c);
	f(d+1,ans+5*p[d],a,1,c);
	f(d+1,ans+7*p[d],a,b,1);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    p[0]=1;
    rep(i,1,11)
    p[i]=10*p[i-1];
    cin>>n;
    f(0,0,0,0,0);
    cout<<g;
}


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

using namespace std;
const double pi=acos(-1.0);
const double eps=1e-9;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair <int,int>
#define piii pair < pii, int>
#define pll pair <long long , long long>
#define plll pair <pll , long long>
#define hjsagjfasjg y1
typedef long long ll;



int main()
{
	ios:: sync_with_stdio(false);
	int a,b;
	cin >> a >> b;
	if(a<=0&&b>=0)
	{
		cout << "Zero";
		return 0;
	}
	if(a>0)
	{
		cout << "Positive";
		return 0;
	}
	if((b-a)%2==0)
	{
		cout << "Negative";
		return 0;
	}
	cout << "Positive";
	return 0;
}

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

#ifdef _DEBUG
#define debug(x) cerr << "line: " << __LINE__ << ", func: " << __func__ << " ->  " << #x << " = " << x << endl
#else
#define debug(x)
#endif

#define all(s) begin(s), end(s)
#define rall(s) rbegin(s), rend(s)
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = ((a)-1); i >= (b); i--)
#define pb push_back
#define sz(a) int((a).size())
#define put(a) ((cout) << (a) << (endl))

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i_i = pair<int, int>;
using ll_ll = pair<ll, ll>;
using d_ll = pair<double, ll>;
using ll_d = pair<ll, double>;
using d_d = pair<double, double>;

static constexpr ll LL_INF = 1LL << 60;
static constexpr int I_INF = 1 << 28;
static constexpr double PI = static_cast<double>(3.14159265358979323846264338327950288);
static constexpr double EPS = numeric_limits<double>::epsilon();
static constexpr const char* YES = "Yes";
static constexpr const char* NO = "No";

static map<type_index, const char* const> scanType = {
    {typeid(int), "%d"}, {typeid(ll), "%lld"}, {typeid(double), "%lf"}, {typeid(char), "%c"}};

template <class T> static void scan(vector<T>& v);
[[maybe_unused]] static void scan(vector<string>& v, bool isWord = true);
template <class T> static inline bool chmax(T& a, T b);
template <class T> static inline bool chmin(T& a, T b);
template <class T> static inline T gcd(T a, T b);
template <class T> static inline T lcm(T a, T b);
template <class A, size_t N, class T> static void Fill(A (&arr)[N], const T& val);

int main(int argc, char* argv[]) {
  std::string S;
  std::cin >> S;

  vector<vector<char>> v{{'R', 'U', 'D'}, {'L', 'U', 'D'}};
  rep(i, 0, sz(S)) {
    int index = i % 2;
    bool good = false;
    rep(j, 0, 3) {
      if (S[i] == v[index][j]) {
        good = true;
        break;
      }
    }

    if (!good) {
      put(NO);
      return 0;
    }
  }

  put(YES);
  return 0;
}

template <class T> static void scan(vector<T>& v) {
  auto tFormat = scanType[typeid(T)];
  for (T& n : v) {
    scanf(tFormat, &n);
  }
}

static void scan(vector<string>& v, bool isWord) {
  if (isWord) {
    for (auto& n : v) {
      cin >> n;
    }
    return;
  }

  int i = 0, size = v.size();
  string s;
  getline(cin, s);

  if (s.size() != 0) {
    i++;
    v[0] = s;
  }

  for (; i < size; ++i) {
    getline(cin, v[i]);
  }
}

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

template <class T> inline T gcd(T a, T b) { return __gcd(a, b); }

template <class T> inline T lcm(T a, T b) { return (a * b) / gcd(a, b); }

template <class A, size_t N, class T> void Fill(A (&arr)[N], const T& val) {
  std::fill((T*)arr, (T*)(arr + N), val);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
template<typename key> using ordered_set = tree <key, null_type, less<key>, rb_tree_tag, tree_order_statistics_node_update>; 
 
int h, w;
char arr[1001][1001];
const int mod = 1e9 + 7;
int dp[1001][1001];

int solve(int r, int c) {
   if(r >= h || c >= w)
      return 0;
   if(r == h - 1 && c == w - 1)
      return 1;
   int &rt = dp[r][c];
   if(rt != -1)
      return rt;
   rt = 0;
   if(arr[r + 1][c] == '.')
      rt += solve(r + 1, c);
   if(rt >= mod)
      rt -= mod;
   if(arr[r][c + 1] == '.')
      rt += solve(r, c +  1);
   if(rt >= mod)
      rt -= mod;
   return rt;
}

int main () {
   IO;
   cin >> h >> w;
   for(int i = 0; i < h; i++) {
      for(int j = 0; j < w; j++)
         cin >> arr[i][j];
   }
   memset(dp, -1, sizeof dp);
   cout << solve(0, 0);
   return 0;
}

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

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;

const int INT_INF = 2147483646;
const ll LL_INF = 9223372036854775807;


const int SIZE = 1e5+100;
ll n, k, ans;
ll x[SIZE], po;

int main(){
    po = -1;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> x[i];
        if(x[0]*x[i] <= 0 && po == -1)   po = i;
    }
    if(n == 1){
        cout << abs(x[0]) << endl;
        return 0;
    }

    if(po == -1){
        if(x[0] <= 0){
            cout << abs(x[n-1-(k-1)]) << endl;
            return 0;
        }
        else{
            cout << x[k-1] << endl;
            return 0;
        }
    }

    ans = LL_INF;
    for(ll i = 0; i < min(n-k+1, po+k); i++){
        ll meml = 0, memr = 0;
        if(i + k-1 >= po && i<= po){
           // cout << x[i] << ' ' << x[i+(k-1)] << endl;
            if(x[i]*x[i+(k-1)] < 0){
                meml += abs(x[i]) * 2;
                meml += abs(x[i+(k-1)]);
                memr += abs(x[i+(k-1)]) * 2;
                memr += abs(x[i]);
            }
            else{
                if(x[i] < 0){
                    meml = abs(x[i]);
                    memr = LL_INF;
                }
                else{
                    memr = x[i+(k-1)];
                    meml = LL_INF;
                }
            }

   // cout << memr << ' ' << meml << endl;
            ans = min(ans,min(memr,meml));
        }

    }

    cout << ans << endl;
    

}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (int)(n); i++)

using namespace std;
typedef long long ll;

int main() {
    int a;
    string s;
    cin >> a >> s;
    
    if (a < 3200) {
        s = "red";
    }
    cout << s << endl;
}


Measured memory_bytes: 256
import os
import sys
from io import BytesIO, IOBase
# region fastio

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# ------------------------------

from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL(): return map(int, sys.stdin.readline().rstrip().split())
def RLL(): return list(map(int, sys.stdin.readline().rstrip().split()))
def N(): return int(input())
def comb(n, m): return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0
def perm(n, m): return factorial(n) // (factorial(n - m)) if n >= m else 0
def mdis(x1, y1, x2, y2): return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

# ------------------------------
# f = open('../input.txt')
# sys.stdin = f

def main():
    c = input()
    if c.isupper():
        print('A')
    else:
        print('a')


if __name__ == "__main__":
    main()



Measured memory_bytes: 67216
import java.util.*;class Main{public static void main(String[]z){Scanner s=new Scanner(System.in);for(int t;(t=s.nextInt())>0;){int[]f=new int[7];for(;t-->0;)++f[Math.min(s.nextInt()/10,6)];for(int a:f)System.out.println(a);}}}

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

using namespace std;

#define IOS ios::sync_with_stdio(0);cin.tie(0);

int main(){
	IOS;
	int a,b;
	while(cin>>a>>b){
		if(a > 8 or b > 8){
			cout<<":("<<endl;
		}
		else{
			cout<<"Yay!"<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define what_is(x) cerr << #x << " is " << x << endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
typedef long long ll;
const int N = 1e5+5;
const int INF = 1e9;
const int MOD = 1e9+7;

int n, k;
int h[N];
int f[N];
int main()
{
	IOS
	// freopen("input.txt", "r", stdin);
	cin >> n >> k;
	for(int i=0; i<n; i++)
		cin >> h[i];
	f[0] = 0;
	f[1] = abs(h[1]-h[0]);
	for(int i=2; i<n; i++){
		f[i] = INF;
		for(int j=1; j<=k; j++){
			if (i-j>=0) f[i] = min(f[i], f[i-j] + abs(h[i]-h[i-j]));
		}
	}
	cout << f[n-1] << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using P = pair<int,int>;
using vl = vector<ll>; using vvl = vector<vl>;
#define mp make_pair
#define pb push_back
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,n) for (int i=(n-1);i >= 0;i--)
#define all(v) v.begin(),v.end()
#define sz(v) (int)((v).size())
#define MAX(v) *max_element(all(v))
#define MIN(v) *min_element(all(v))
#define Sort(v) sort(all(v))
#define Rev(v) reverse(all(v))
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);in(name)
#define vv(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define VV(type,name,h,w) vector<vector<type>>name(h,vector<type>(w));in(name)
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cout << H << " ";
    debug_out(T...);
}
#ifdef _DEBUG
#define debug(...) debug_out(__VA_ARGS__)
#else
#define debug(...) 
#endif
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
    for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
    return os;
}
inline void IN(void){return;}
template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){cin >> first;IN(rest...);return;}
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;}
const ll INF = 1LL << 60;
const ll mod = 1000000007;
const int dx[8] = {1,0,-1,0,1,1,-1,-1}; const int dy[8] = {0,1,0,-1,1,1,-1,-1};

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    int x,y;cin >> x >> y;
    bool f = false;
    rep(i,x+1){
        if(2*i+4*(x-i)==y) f=true;
    }
    if(f) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

/*

*/

ll n,a[510][510];

void f(V<ll> &v, ll x){
	ll n = v.size();
	if(n<=1)return;
	V<ll> v1,v2;
	rep(i,n/2)v1.push_back(v[i]);
	reg(i,n/2,n-1)v2.push_back(v[i]);
	for(ll p:v1){
		for(ll q:v2){
			a[p][q]=x;
		}
	}
	f(v1,x+1);
	f(v2,x+1);
}

void init(){
	cin>>n;
}

int main(void){
	init();
	V<ll> v;
	rep(i,n)v.push_back(i);
	f(v,1);
	rep(i,n){
		reg(j,i+1,n-1)cout<<a[i][j]<<" ";
		cout<<endl;
	}
	return 0;
}

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

int main(){
  string s,t;
  cin >> s >> t;
  int ans = 0;
  if(t[0] == s[0])ans += 1;
  if(t[1] == s[1])ans += 1;
  if(t[2] == s[2])ans += 1;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define inf 2123333333
#define pii pair<int,int>

struct node { int t,v,op,next; }a[100010];

queue<int> q;

int ans1[110][110],ans2[110][110];
int num[110][110],head[210],cur[210],level[210],n,m,vs,vt,tot;
bool vis[10010];

inline int rd()
{
	int x=0;char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar());
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

inline void print(int x)
{
	static char s[233];
	if (!x) { putchar('0');putchar(' ');return; }
	int tot=0;
	for (;x;x/=10) s[++tot]=x%10+'0';
	for (;tot;tot--) putchar(s[tot]);
	putchar(' ');
}

inline void add(int x,int y,int z)
{
	a[++tot].t=y;a[tot].v=z;a[tot].op=tot+1;a[tot].next=head[x];head[x]=tot;
	a[++tot].t=x;a[tot].v=0;a[tot].op=tot-1;a[tot].next=head[y];head[y]=tot;
}

inline bool bfs()
{
	while (!q.empty()) q.pop();
	memset(level,0,sizeof(level));
	level[vs]=1;cur[vs]=head[vs];q.push(vs);
	while (!q.empty())
	{
		int x=q.front();q.pop();
		for (int i=head[x];i;i=a[i].next) if (a[i].v)
		{
			int t=a[i].t;
			if (level[t]) continue;
			level[t]=level[x]+1;cur[t]=head[t];
			if (t==vt) return true;
			q.push(t);
		}
	}
	return false;
}

inline int dfs(int x,int y)
{
	if (x==vt||!y) return y;
	int res=0;
	for (int &i=cur[x];i;i=a[i].next) if (a[i].v)
	{
		int t=a[i].t;
		if (level[t]!=level[x]+1) continue;
		int hh=dfs(t,min(y,a[i].v));
		if (!hh) continue;
		res+=hh;y-=hh;
		a[i].v-=hh;a[a[i].op].v+=hh;
		if (!y) break;
	}
	return res;
}

inline void work(int id)
{
	memset(head,0,sizeof(head));tot=0;
	vs=0;vt=n*2+1;
	for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (!vis[num[i][j]]) add(i,(num[i][j]+m-1)/m+n,1);
	for (int i=1;i<=n;i++) add(vs,i,1),add(i+n,vt,1);
	while (bfs()) dfs(vs,inf);
	for (int i=1;i<=n;i++)
	{
		int now=0;
		for (int j=head[i];j;j=a[j].next) if (a[j].t>n&&!a[j].v) now=a[j].t-n;
		for (int j=1;j<=m;j++) if (!vis[num[i][j]]&&(num[i][j]+m-1)/m==now)
		{
			ans1[i][id]=num[i][j];vis[num[i][j]]=true;
			break;
		}
	}
}

int main()
{
	n=rd();m=rd();
	for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) num[i][j]=rd();
	for (int i=1;i<=m;i++) work(i);
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++) print(ans1[i][j]);
		putchar('\n');
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++) for (int k=1;k<=n;k++) if (ans1[k][j]>(i-1)*m&&ans1[k][j]<=i*m) ans2[i][j]=ans1[k][j];
		for (int j=1;j<=m;j++) print(ans2[i][j]);
		putchar('\n');
	}
	return 0;
}

Measured memory_bytes: 768
#include <iostream>
#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>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define SZ(x) ((int)(x).size())
#define m0(x) memset(x,0,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

std::vector<ll> find_prime_factors(ll n)
{
    std::vector<ll> result;
    while (n % 2 == 0) {
      result.push_back(2);
      n = n / 2;
    }
    for (ll i = 3; i <= sqrt(n); i = i+2)
    {
        while (n % i == 0)
        {
            result.push_back(i);
            n /= i;
        }
    }
    if (n > 2) {
      result.push_back(n);
    }
    return result;
}

int main() {
  ll N;
  ll P;
  cin >> N;
  cin >> P;
  if (N > P) {
    cout << 1 << endl;
    return 0;
  }
  if (N == 1) {
    cout << P << endl;
    return 0;
  }
  ll count = 0;
  vector<ll> sosuu = find_prime_factors(P);

  ll ans = 1;
  std::map<ll, ll> mp;
  rep(i, sosuu.size()){
    auto itr = mp.find(sosuu.at(i));
    if (itr != mp.end()) {
      mp[sosuu.at(i)] = mp[sosuu.at(i)] + 1;
    }
    else
    {
      mp[sosuu.at(i)] = 1;
    }
  }
  for (auto itr = mp.begin(); itr != mp.end(); ++itr) {
    while (itr->second >= N){
      ans *= itr->first;
      itr->second -= N;
    }
  }
    cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long a[] = new long[N];
		for(int i=0; i<N; i++){
			a[i] = sc.nextInt();
		}
		long count = 0;
				for(int i=0; i<N; i++){
			if(a[i]%2==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%4==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%8==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%16==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%32==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%64==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%128==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%256==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%512==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%1024==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%2048==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%4096==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%8192==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%16384==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%32768==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%65536==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%131072==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%262144==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%524288==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%1048576==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%2097152==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%4194304==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%8388608==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%16777216==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%33554432==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%67108864==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%134217728==0)count++;
		}		for(int i=0; i<N; i++){
			if(a[i]%268435456==0)count++;
		}
				for(int i=0; i<N; i++){
			if(a[i]%536870912==0)count++;
		}
		System.out.println(count);
	}
}

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

int main(){
    long long int n, x;
    cin>>n>>x;
    long long int t=0;
    t+=n;
    long long int l=x, s=n-x, tmp;
    while(1){
        tmp=l%s;
        t+=(l-tmp)*2;
        if(tmp==0){
            t-=s;
            break;
        }
        l=s;
        s=tmp;
    }
    cout<<t<<endl;
    return 0;
}


Measured memory_bytes: 256
n = gets.to_i
a = gets.chomp.split(" ").map(&:to_i)
max = a.max
arr = Array.new(max+1,0)
2.upto(max) do |x|
  v = x
  while v <= max
    arr[v] = x if arr[v] == 0
    v += x
  end
end
hash = Hash.new(-1)
flg = false
n.times do |i|
  if a[i] != 1
    y = a[i]
    while y != 1
      if hash[arr[y]] != i && hash[arr[y]] != -1
        flg = true
      end
      hash[arr[y]] = i
      y = y / arr[y]
    end
    break if flg
  end
end
if !flg
  puts "pairwise coprime"
else
  gcd = 0
  a.each do |x|
    gcd = gcd.gcd(x)
  end
  if gcd == 1
    puts "setwise coprime"
  else
    puts "not coprime"
  end
end

Measured memory_bytes: 97864
/**
 *    author:  math2do
 *    created: 22.03.2020 17:56:04
**/

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  int ans = n * (n - 1) / 2 + m * (m - 1) / 2;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
S=input()
K=int(input())
N=len(S)

if S.count(S[0])==N:
  ans= K*N//2
else:
  h=0
  for i in range(N):
    if S[i]==S[0]:
      h +=1
    else:
      break
  t=0
  for i in range(N-1,-1,-1):
    if S[i]==S[-1]:
      t +=1
    else:
      break
  ren=1
  cnt=0
  for i in range(h,N-t):
    if S[i]==S[i-1]:
      ren +=1
      if i==N-t-1:
        cnt += ren//2
    else:
      cnt += ren//2
      ren=1    
      
  if S[0]==S[-1]:
    #print(h//2, (K-1)*((h+t)//2), t//2 ,K*cnt)
    ans= h//2 + (K-1)*((h+t)//2) + t//2 + K*cnt
  else:
    #print(h//2,cnt,t//2)
    ans= (h//2 + cnt + t//2)*K
print(ans)

Measured memory_bytes: 3064
import sys

n1, n2  = [int(i) for i in input().split()]

na3 = [int(j) for j in input().split()]

if n1 >= n2:
    print("0")
    sys.exit()

na3.sort()

na4 = []
for i5 in range(n2):
    if i5 != 0:
        na4.append(na3[i5] - na3[i5 -1])

na4.sort(reverse=True)
n6 = 0
for i7 in range(n1 -1):
    n6 += na4[i7]

r7 = sum(na4) - n6

print(r7)

Measured memory_bytes: 13840
#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 treeMi(Node a){
  while(a->left!=NIL)
   a=a->left;
  return a;
}
Node treeMa(Node a){
  while(a->right!=NIL)
    a=a->right;
  return a;
}
Node treeS(Node w, int r){
  while(w!=NIL&&r!=w->key){
    if(r<w->key)w=w->left;
    else w=w->right;
  }
  return w;
}
Node treeM(Node a){
  Node b;
  if(a->right!=NIL)
    return treeMi(a->right);
  b=a->parent;
  while(b!=NIL&&a==b->right){
    a=b;
    b=b->parent;
  }
  return b;
}
void treeN(Node c){
  Node a;
  Node b;
  if(c->left==NIL||c->right==NIL)b=c;
  else
    b=treeM(c);
  if(b->left!=NIL){
    a=b->left;
  }
  else{
    a=b->right;
  }
  if(a!=NIL){
    a->parent=b->parent;
  }
  if(b->parent==NIL){
    root=a;
  }
  else{
    if(b==b->parent->left){
      b->parent->left=a;
    }
    else{
      b->parent->right=a;
    }
  }
  if(b!=c){
    c->key=b->key;
  }
  free(b);
}
void insert(int k){
  Node a = root;
  Node b = NIL;
  Node c;
  c = malloc(sizeof(struct node));
  c->key = k;
  c->left = NIL;
  c->right = NIL;
  while(a!=NIL){
    b=a;
    if(c->key < a->key){
      a=a->left;
    }
    else{
      a=a->right;
    }
  }
  c->parent=b;
  if(b==NIL){
    root=c;
  }
  else{
    if(c->key < b->key){
      b->left=c;
    }
    else{
      b->right=c;
    }
  }
}
void inorder(Node n){
  if(n==NIL)
    return;
  inorder(n->left);
  printf(" %d",n->key);
  inorder(n->right);
}
void outorder(Node n){
  if(n==NIL)
    return;
  printf(" %d",n->key);
  outorder(n->left);
  outorder(n->right);
}
int main(){
  int i,n,a;
  char c[20];
  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%s",c);
    if(c[0]=='f'){
      scanf("%d",&a);
      Node r = treeS(root,a);
      if(r!=NIL)
	printf("yes\n");
      else printf("no\n");
    }
    else if(c[0] ==  'i'){
      scanf("%d",&a);
      insert(a);
    }
    else if(c[0] ==  'p'){
      inorder(root);
      printf("\n");
      outorder(root);
      printf("\n");
    }
    else if(c[0]=='d'){
      scanf("%d",&a);
      treeN(treeS(root,a));
    }
  }
  return 0;
}



Measured memory_bytes: 20512
#include<bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;

int H,W;
char grid[1000][1000];
ll dp[1000][1000];
ll solve(int i,int j){
	
	if(i>=H || i<0 ||j>=W || j<0 ||grid[i][j]=='#')
		return 0;
	if(i==H-1 && j==W-1)
		return 1;
	if(dp[i][j]!=-1)
		return dp[i][j];
	
	return dp[i][j]=(solve(i+1,j)%MOD+solve(i,j+1)%MOD)%MOD;
}


int main(){
	
	cin>>H>>W;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			cin>>grid[i][j];
		}
	}
	memset(dp,-1,sizeof(dp));
	cout<<solve(0,0)<<endl;
	return 0;
}

Measured memory_bytes: 9088
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>

using namespace std;

int main() {
	int i, j, k;
	int a, b;
	string s;

	cin >> a >> b >> s;

	for (i = 0; i < a; i++) {
		if (!isdigit((unsigned char)s[i])) {
			cout << "No" << endl;
			goto label;
		}
	}

	if (s[i] != '-') {
		cout << "No" << endl;
		goto label;
	}
	i++;

	for (i; i < a+b+1; i++) {
		if (!isdigit((unsigned char)s[i])) {
			cout << "No" << endl;
			goto label;
		}
	}


	cout << "Yes" << endl;



	label:


	getchar();
	getchar();
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
using namespace std;

int main(){
    string s;
    cin >> s;
    if(s == "keyence"){
        cout << "YES" << endl;
        return 0;
    }
    int length = s.length();
    string key = "keyence";
    // "keyaaaaence" //11
    for(int i = 0; i < 7; i++){ // remove point
        string tmp = "aaaaaaa";

        for(int j = 0; j < i; j++){
            tmp[j] = s[j];
        }
        for(int j = i+length-7; j < length; j++){
            tmp[j-length+7] = s[j];
        }
        if(tmp == key){
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << 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 ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;

int main(){
    int n; cin >> n;
    vector<int> l(n);
    rep(i,n) cin >> l[i];
    sort(ALL(l));
    int cnt = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(l[i] == l[j]) continue;
            for(int k = j + 1; k < n; k++){
                if(l[j] == l[k]) continue;
                if(l[i] + l[j] > l[k]) cnt++;
            }
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 3632
N,X = list(map(int,input().split()))
x = list(map(lambda x:abs(int(x)-X),input().split()))

def gcd(x):
    if len(x) == 1:
        return x[0]
    m = min(x)
    return gcd([m]+[y%m for y in x if (y%m)>0])

print(gcd(x))

Measured memory_bytes: 14224
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val hList = readLine()!!.split(' ').map(String::toInt)
    val dp = Array(n) { 0L }
    dp[1] = Math.abs(hList[1] - hList[0]).toLong()
    for (i in 2 until n) {
        dp[i] = Math.min(
                dp[i - 1] + Math.abs(hList[i] - hList[i - 1]),
                dp[i - 2] + Math.abs(hList[i] - hList[i - 2])
        )
    }
    println(dp.last())
}

Measured memory_bytes: 48052
K, N = map(int, input().split())
A = [int(i) for i in input().split()]

max_len = 0
for i in range(N - 1):
    max_len = max(max_len, A[i + 1] - A[i])
max_len = max(max_len, (K - A[-1]) + A[0])

print(K - max_len)


Measured memory_bytes: 26420
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>
#include <deque>
#include <queue>
#include <map>
using namespace std;
int main(int argc,char**argv)
{
	int n;
	cin>>n;
	cout<<((n+1000-1)/1000)*1000-n;
	return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <string>
#include <set>
#include <iomanip>
#include <map>
#include <unordered_map>
#include<cstring>
#include<cstdlib>
using namespace std;

const long long mod=1000000007;
const long long inf=mod*mod;
double p[3100];
double dp[3100][3100];
int main(){
        int n;
        cin>>n;
        dp[0][0]=1;
        for(int i=0;i<n;i++) cin>>p[i];
        for(int i=1;i<=n;i++){
            for(int j=0;j<=i;j++){
                if(j) dp[i][j]+=dp[i-1][j-1]*p[i-1];
                dp[i][j]+=dp[i-1][j]*(1-p[i-1]);
            }
        }

        double c=0;
        for(int i=0;i<=n;i++){
            if(i>n-i) c+=dp[n][i];
        }
        printf("%.12f\n",c );
    return 0;
}


Measured memory_bytes: 72320
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <fstream>
#include <chrono>
#include <random>
#include <bitset>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mod 1000000007
using ll = long long;
using namespace std;
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}

int main(){
  int N; cin >> N;
  vector<ll> X(N); rep(i,N) cin >> X[i];
  ll ans = 1e18;
  for(ll i=0; i<=100;i++){
    ll preans = 0;
    rep(j,N){
      preans += (X[j]-i)*(X[j]-i);
    }
    ans = min(ans, preans);
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;

int v[500100], h[500100];
char sir[500100];

void read ()
{
    scanf ("%s", sir + 1), v[0] = strlen (sir + 1);
    for (int i=1; i<=v[0]; i++)
        v[i] = sir[v[0] + 1 - i] - '0';
}

void mul9 ()
{
    int t = 0;
    for (int i=1; i<=v[0]; i++)
    {
        v[i] *= 9, v[i] += t;
        t = v[i] / 10, v[i] %= 10;
    }
    if (t) v[++v[0]] = t;
}

int sumAdd (int ad)
{
    for (int i=0; i<=v[0]; i++)
        h[i] = v[i];
    h[v[0] + 1] = h[v[0] + 2] = h[v[0] + 3] = 0;
    int i = 1, ans = 0;
    h[1] += ad;
    while (h[i] > 9)
        h[i + 1] += h[i] / 10, h[i] %= 10, i ++;
    if (i > h[0]) h[0] = i;
    for (int i=1; i<=h[0]; i++)
        ans += h[i];
    return ans;
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

read ();
mul9 ();
int p = 1, u = v[0] + 1000, mij, ras = -1;
while (p <= u)
{
    mij = (p + u) >> 1;
    if (sumAdd (9 * mij) <= 9 * mij)
        ras = mij, u = mij - 1;
    else
        p = mij + 1;
}
printf ("%d\n", ras);
return 0;
}


Measured memory_bytes: 4608