akhauriyash/Code-Regression huggingface dataset:
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;

public class Main {

	static PrintWriter out;
	static InputReader ir;

	static void solve() {
		char[] s=ir.next().toCharArray();
		out.println(s[0]=='9'||s[1]=='9'?"Yes":"No");
	}

	public static void main(String[] args) throws Exception {
		ir = new InputReader(System.in);
		out = new PrintWriter(System.out);
		solve();
		out.flush();
	}

	static class InputReader {

		private InputStream in;
		private byte[] buffer = new byte[1024];
		private int curbuf;
		private int lenbuf;

		public InputReader(InputStream in) {
			this.in = in;
			this.curbuf = this.lenbuf = 0;
		}

		public boolean hasNextByte() {
			if (curbuf >= lenbuf) {
				curbuf = 0;
				try {
					lenbuf = in.read(buffer);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (lenbuf <= 0)
					return false;
			}
			return true;
		}

		private int readByte() {
			if (hasNextByte())
				return buffer[curbuf++];
			else
				return -1;
		}

		private boolean isSpaceChar(int c) {
			return !(c >= 33 && c <= 126);
		}

		private void skip() {
			while (hasNextByte() && isSpaceChar(buffer[curbuf]))
				curbuf++;
		}

		public boolean hasNext() {
			skip();
			return hasNextByte();
		}

		public String next() {
			if (!hasNext())
				throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b = readByte();
			while (!isSpaceChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}

		public int nextInt() {
			if (!hasNext())
				throw new NoSuchElementException();
			int c = readByte();
			while (isSpaceChar(c))
				c = readByte();
			boolean minus = false;
			if (c == '-') {
				minus = true;
				c = readByte();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res = res * 10 + c - '0';
				c = readByte();
			} while (!isSpaceChar(c));
			return (minus) ? -res : res;
		}

		public long nextLong() {
			if (!hasNext())
				throw new NoSuchElementException();
			int c = readByte();
			while (isSpaceChar(c))
				c = readByte();
			boolean minus = false;
			if (c == '-') {
				minus = true;
				c = readByte();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res = res * 10 + c - '0';
				c = readByte();
			} while (!isSpaceChar(c));
			return (minus) ? -res : res;
		}

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

		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public long[] nextLongArray(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		public char[][] nextCharMap(int n, int m) {
			char[][] map = new char[n][m];
			for (int i = 0; i < n; i++)
				map[i] = next().toCharArray();
			return map;
		}
	}
}


Measured memory_bytes: 23124
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define dd double
#define endl "\n"
#define pb push_back
#define all(v) v.begin(),v.end()
#define mp make_pair
#define fi first
#define se second
#define fo(i,n) for(int i=0;i<n;i++)
#define fo1(i,n) for(int i=1;i<=n;i++)
ll mod=1000000007;
ll n,k,t,m,q,flag=0;
ll po(ll k ,ll n,ll ans,ll temp,ll ans1){
    if(n==0)return ans;
    while(temp<=n){
        ans*=ans1;ans%=mod;ans1=ans1*ans1;ans1%=mod;n=n-temp;temp*=2;
    }
    return po(k,n,ans,1,k)%mod;
    //eg. po(2,78,1,1,2);
}
ll min(ll a,ll b){if(a>b)return b;else return a;}
ll max(ll a,ll b){if(a>b)return a;else return b;}
ll count0[10][1000];
char a[10][1000];
ll minans;
void findans( vector<ll> v, ll h , ll w){
    ll l=v.size();
    //cout<<l<<" ";
    //fo(i,l)cout<<v[i]<<" ";
    vector<ll> v1=v;
    ll tempans=0;
    v1.pb(h);
    //fo(i,l+1)cout<<v1[i]<<" ";cout<<endl;
    ll temp[v1.size()];
    fo(i,v1.size())temp[i]=0;
    for(int f=0;f<w;f++){
        ll kk=0;
        ll c[v1.size()];
        fo(i,v1.size())c[i]=0;
        fo(j,h){
            if(j<v1[kk]);
            else kk++;
            if(a[j][f]=='1')c[kk]++;
        }
        ll possible=1;
        fo(i,v1.size()){
            if(c[i]>k)possible=0;
        }
        if(possible==0)break;
        flag=0;
        fo(i,v1.size()){
            if(temp[i]+c[i]>k)flag=1;
            temp[i]+=c[i];
        }
        if(flag==1){
            tempans++;
            fo(i,v1.size()){
                temp[i]=c[i];
            }
        }
        if(f==w-1)minans=min(l+tempans , minans);
    }
    

    ll p;
    if(l>0)p=v1[l-1]+1;
    else p=1;
    for( ; p<h;p++){
        v1[v1.size()-1]=p;
        findans(v1, h ,w);
    }

}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    //cin>>t;
    t=1;
    while(t--){
        ll h,w;
        cin>>h>>w>>k;
        fo(i,h)fo(j,w)cin>>a[i][j];
        
        minans=mod;

        vector<ll>v;
        findans(v,h,w);
        cout<<minans;


        
    }

    return 0;
}


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

int main(){
	ios::sync_with_stdio(false);

	int N,x; cin>>N>>x;
	vector<int> a(N),b(N); rep(i,N) cin>>a[i];

	sort(a.begin(),a.end());

	for(int i=0; i<N; i++){
		if(x>=a[i]){
			b[i]=a[i];
			x -= a[i];
		}

		if(i==N-1){
			b[i] += x;
		}
	}
	
	int ct=0;
	for(int i=0; i<N; i++){
		if(a[i]==b[i]) ct++;
	}
	cout << ct << endl;
}


Measured memory_bytes: 3652
import sys
input = sys.stdin.readline
from fractions import gcd
def prime_factorize(n):
    res = []
    for i in range(2, int(n**0.5)+1):
        if n % i != 0:continue
        ex = 0
        while n % i == 0:
            ex += 1
            n = n//i
        res.append((i, ex))
    if n != 1:res.append((n, 1))
    return res
def main():
    A, B = map(int, input().split())
    g = gcd(A, B)
    res = prime_factorize(g)
    ans = len(res) + 1
    print(ans)
if __name__ == "__main__":
    main()

Measured memory_bytes: 64364
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	for(int i=0;i<s.size();i++){
		if((i+1)%2==1&&s[i]=='L'){
			cout<<"No"<<endl;
			return 0;
		}
		if((i+1)%2==0&&s[i]=='R'){
			cout<<"No"<<endl;
			return 0;
		}
	}
	cout<<"Yes"<<endl;
	return 0;
}


Measured memory_bytes: 256
//By Tushar Gautam
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define memreset(a) memset(a,0,sizeof(a))
#define testcase(t) int t;cin>>t;while(t--)
#define forstl(i,v) for(auto &i: v)
#define forn(i,e) for(int i = 0; i < e; i++)
#define forsn(i,s,e) for(int i = s; i < e; i++)
#define rforn(i,s) for(int i = s; i >= 0; i--)
#define rforsn(i,s,e) for(int i = s; i >= e; i--)
#define leadzero(a) __builtin_clz(a) // count leading zeroes
#define trailzero(a) __builtin_ctz(a) // count trailing zeroes
#define bitcount(a) __builtin_popcount(a) // count set bits (add ll)
#define ln "\n"
#define dbgarr(v,s,e) cerr<<#v<<" = "; forsn(i,s,e) cerr<<v[i]<<", "; cerr<<endl
#define inputfile freopen("input.txt", "r", stdin)
#define outputfile freopen("output.txt", "w", stdout)
#define dbg(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); \
stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) { cerr<<endl; }
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << "\t"; err(++it, args...);
}
template<typename T1,typename T2>
ostream& operator <<(ostream& c,pair<T1,T2> &v){
	c<<"("<<v.fi<<","<<v.se<<")"; return c;
}
template <template <class...> class TT, class ...T>
ostream& operator<<(ostream& out,TT<T...>& c){
    out<<"{ ";
    forstl(x,c) out<<x<<" ";
    out<<"}"; return out;
}
typedef long long int  ll;
typedef long double  ld;
typedef pair<ll,ll> p64;
typedef pair<int,int> p32;
typedef pair<int,p32> p96;
typedef vector<ll> v64;
typedef vector<int> v32; 
typedef vector<v32> vv32;
typedef vector<v64> vv64;
typedef vector<p32> vp32;
typedef vector<vp32> vvp32;
typedef map<int,int> m32;
const int LIM = 1e5+5, MOD = 1e9+7;
int t,n,m,k,x,y;
v32 a;
v32 dp;
int solve(int x){
	if(x==0) return 0;
	if(dp[x]!=-1) return dp[x];
	bool poss=1;
	forstl(it,a){
		if(x>=it) poss&=solve(x-it);
	}
	return dp[x]=!poss;
}
int main(){
	fastio;
	cin>>n>>k;
	a.resize(n);
	dp.assign(k+1,-1);
	forn(i,n){
		cin>>a[i];
	}
	auto b=solve(k);
	if(b){
		cout<<"First\n";
	}else cout<<"Second\n";
	return 0;
}

Measured memory_bytes: 5376
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iterator>
#include <limits>
#include <numeric>
#include <utility>
#include <cmath>
#include <cassert>
#include <cstdio>

using namespace std;
using namespace placeholders;

using LL = long long;
using ULL = unsigned long long;
using VI = vector< int >;
using VVI = vector< vector< int > >;
using VS = vector< string >;
using SS = stringstream;
using PII = pair< int, int >;
using VPII = vector< pair< int, int > >;
template < typename T = int > using VT = vector< T >;
template < typename T = int > using VVT = vector< vector< T > >;
template < typename T = int > using LIM = numeric_limits< T >;

template < typename T > inline istream& operator>>( istream &s, vector< T > &v ){ for ( T &t : v ) { s >> t; } return s; }
template < typename T > inline ostream& operator<<( ostream &s, const vector< T > &v ){ for ( int i = 0; i < int( v.size() ); ++i ){ s << ( " " + !i ) << v[i]; } return s; }
template < typename T > inline T fromString( const string &s ) { T res; istringstream iss( s ); iss >> res; return res; }
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); }

#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )
#define FOR( e, c ) for ( auto &&e : c )
#define ALL( c ) begin( c ), end( c )
#define AALL( a, t ) ( t* )a, ( t* )a + sizeof( a ) / sizeof( t )
#define DRANGE( c, p ) ( c ).begin(), ( c ).begin() + ( p ), ( c ).end()

#define SZ( v ) ( (int)( v ).size() )
#define EXIST( c, e ) ( ( c ).find( e ) != ( c ).end() )

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

#define PB push_back
#define EM emplace
#define EB emplace_back
#define BI back_inserter

#define MP make_pair
#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );
	cout << setprecision( 12 ) << fixed;

	string S;
	cin >> S;

	int K;
	cin >> K;

	FOR( c, S )
	{
		const int d = ( 'z' + 1 ) - c;
		if ( c != 'a' && d <= K )
		{
			c = 'a';
			K -= d;
		}
	}

	char &c = S.back();
	const int p = c -'a';
	c = ( p + K ) % 26 + 'a';

	cout << S << endl;

	return 0;
}


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

int main () {
	int a, b;
  	cin >> a >> b;
  	for (int i = 0; i < 1100; i++) {
    if (i * 2 / 25 == a && i / 10 == b) {
    cout << i << endl; 
    break;
    }
    else if (i == 1099) {
    cout << -1 << endl;
    }
    }
  return 0;
}


Measured memory_bytes: 256
package main

import (
    "bufio"
    "os"
//    "strings"
    "strconv"
    "fmt"
)

const WIDTH = 502
const HEIGHT = 502

/*
var nrs = bufio.NewReaderSize(os.Stdin, 1000000)

func readLineToInt() []int {
    buf := make([]byte, 0, 1000000)
    for {
        l, p, e := nrs.ReadLine()
        if e != nil {
            panic(e)
        }
        buf = append(buf, l...)
        if !p {
            break
        }
    }
    line := strings.Split(string(buf), " ")
    var intLine []int
    for _, str := range line {
        n, _ := strconv.Atoi(str)
        intLine = append(intLine, n)
    }
    return intLine
}
*/

/*
var sc = bufio.NewScanner(os.Stdin)

func readLineToInt() []int {
    sc.Scan()
    line := strings.Split(sc.Text(), " ")
    var intLine []int
    for _, str := range line {
        n, _ := strconv.Atoi(str)
        intLine = append(intLine, n)
    }
    return intLine
}
*/
func scanInt(sc *bufio.Scanner) int {
    sc.Scan()
    v, _ := strconv.Atoi(sc.Text())
    return v
}

func main() {
    sc := bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    var m, q int
    var l, r int
    var a, b int
    var mp [HEIGHT][WIDTH]int
    //nmq := readLineToInt()
    _, m, q = scanInt(sc), scanInt(sc), scanInt(sc)
    //sc.Scan()
    //fmt.Sscanf(sc.Text(), "%d %d %d", &n, &m, &q)


    for i := 0; i < m; i++ {
        //lr := readLineToInt()
        //l, r = lr[0], lr[1]
        //sc.Scan()
        //fmt.Sscanf(sc.Text(), "%d %d", &l, &r)
        l, r = scanInt(sc), scanInt(sc)
        mp[l][r] += 1
    }

    for x := 0; x < WIDTH - 1; x++ {
        mp[0][x] += mp[0][x + 1]
    }

    for y := 1; y < HEIGHT; y++ {
        for x := 0; x < WIDTH - 1; x++ {
            mp[y][x + 1] += mp[y][x]
            mp[y][x] += mp[y - 1][x]
        }
    }

    for i := 0; i < q; i++ {
        //ab := readLineToInt()
        //a, b = ab[0], ab[1]
        //sc.Scan()
        //fmt.Sscanf(sc.Text(), "%d %d", &a, &b)
        a, b = scanInt(sc), scanInt(sc)
        fmt.Println(mp[b][b] - mp[b][a - 1] - mp[a - 1][b] + mp[a - 1][a - 1])
    }
}

Measured memory_bytes: 6144
N = int(input())
A = list(map(int, input().split())) 
B = list(map(int, input().split())) 
C = list(map(int, input().split()))

ans = 0
prev = None
for a in A:
    ans += B[a-1]
    if prev is not None and prev+1 == a:
        ans += C[prev-1]
    prev = a

print(ans)

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

using namespace std;

int main()
{
    string n;
    cin >> n;
    if (n[0] != 'A' or n[1] == 'C' or !islower(n[1]) or n[n.size()-1]=='C')
    {
        cout << "WA";
        return 0;
    }
    bool k = true;
    for (int i = 2; i < n.size(); i++)
    {
        if ((n[i] == 'C' and k) or islower(n[i]))
        {
            if (n[i]=='C')
                k = false;
        } else
        {
            cout<<"WA";
            return 0;
        }
    }
    if (k)
    {
        cout<<"WA";
        return 0;
    }
    cout<<"AC";
}


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

const int INF = 2e9;

// -90????????¢
vector<vector<int>> rotate(auto A) {
  auto H = A.size(), W = A.front().size();
  vector<vector<int>> res(W, vector<int>(H));
  for(auto i = 0; i < H; ++i) for(auto j = 0; j < W; ++j) res[j][H-1-i] = A[i][j];
  return res;
}

bool ok(auto A, auto K) {
  auto H = A.size(), W = A.front().size();

  auto x = -INF, y = INF;
  for(auto& i: A) for(auto& j: i) x = max(x, j);
  for(auto& i: A) for(auto& j: i) y = min(y, j);

  auto cur = -1;
  for(auto i = 0; i < H; ++i) {
    for(auto j = cur + 1; j < W; ++j) if(y + K < A[i][j]) cur = j;
    for(auto j = 0; j <= cur; ++j) if(A[i][j] < x - K) return false;
  }
  return true;
};

int main() {
  int H, W;
  cin >> H >> W;

  vector<vector<int>> A(H, vector<int>(W));
  for(auto& i: A) for(auto& j: i) cin >> j;

  auto ans = INF;

  for(auto i = 0; i < 4; ++i) {
    A = rotate(A);
    auto low = -INF, high = INF;
    while(low + 1 < high) {
      auto middle = (low + high) / 2;
      if(ok(A, middle)) high = middle;
      else              low  = middle;
    }
    ans = min(ans, high);
  }

  cout << ans << endl;
}

Measured memory_bytes: 50056
import numpy as np
s = input()
n = len(s)

pop = [0]*n

lastR = 0
for i in range(n):
    if s[i] == "L":
        if (lastR - i)%2 == 1:
            pop[lastR+1] += 1
        else:
            pop[lastR] += 1
    else:
        lastR = i
            
lastL = n
for i in range(n-1, -1, -1):  
    if s[i] == "R":
        if (lastL - i)%2 == 1:
            pop[lastL-1] += 1
        else:
            pop[lastL] += 1
    else:
        lastL = i
        
print(" ".join(map(str, pop)))   

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


int main(){
     long long x,k,d;
     cin>>x>>k>>d;

     x=abs(x);



     if(x==0){
        if(k%2==1)
            cout<<d<<endl;

        else
            cout<<0<<endl;
     }

     else if(x>0){
        long long z=x%d;
        long long y=(x-z)/d;

        if(k<=y){

            long long f= k*d;
            cout<<x-f<<endl;
        }

        else{

           long long f= z-d;
           f=abs(f);

           k=k-y;

           if(k%2==1)
            cout<<f<<endl;

           else
            cout<<z<<endl;
        }



     }















    return 0;







}


Measured memory_bytes: 3588
# -*- coding: utf-8 -*-

# -*- coding: utf-8 -*-


from sys import stdin



############################################

# read data for n sequences.
temp = stdin.readline().split()
N = int(temp[0])

data = []
write = stdin.readline().split()
for i in range(N):
    data.append(int(write[i]))

data = sorted(data)

print(data[int(N/2)] - data[int(N/2)-1])

Measured memory_bytes: 15036
n, p = map(int, input().split())
a = list(map(int, input().split()))

def comb(n, r):
    ans = 1
    if n < 2*r:
        r = n - r
    for i in range(r):
        ans *= (n - i)
        ans //= (i + 1)
    return ans

ev, od = 0, 0
for i in a:
    if i%2 == 0:
        ev += 1
    else:
        od += 1
ans = 0
if p == 0:
    for i in range(0, od+1, 2):
        for j in range(ev+1):
            ans += comb(od, i)*comb(ev, j)
else:
    for i in range(1, od+1, 2):
        for j in range(ev+1):
            ans += comb(od, i)*comb(ev, j) 
print(ans)

Measured memory_bytes: 64284
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// require srand
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()
#define DEBUG 0

using namespace std;

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

int dp[1005][1005];

int main()
{
	ios_base::sync_with_stdio(0);
	int N; cin >> N;
	while (N-- ){
		memset (dp, 0, sizeof (dp ) );
		string s = "", t = "";
		cin >> s >> t;
		int n = s.length();
		int m = t.length();
		
		dp[0][0] = (s[0] == t[0] );

		for (int i = 1; i < n; i++ )
			if (s[i] == t[0] )
				dp[i][0] = 1;
			else
				dp[i][0] = max (dp[i][0], dp[i-1][0] );

		for (int j = 1; j < m; j++ )
			if (s[0] == t[j] )
				dp[0][j] = 1;
			else
				dp[0][j] = max (dp[0][j], dp[0][j-1] );

		for (int i = 1; i < n; i++ ){
			for (int j = 1; j < m; j++ ){
				dp[i][j] = max (dp[i][j], dp[i-1][j-1] + (s[i] == t[j] ) );
				dp[i][j] = max (dp[i][j], dp[i-1][j] );
				dp[i][j] = max (dp[i][j], dp[i][j-1] );
			} // end for
		} // end for
#if (DEBUG )
		rep (i, n ){
			rep (j, m ){
				printf ("%3d", dp[i][j] );
			} // end rep
			printf ("\n" );
		} // end rep
#endif		
		int res = 0;
		rep (i, n ) rep (j, m ) res = max (res, dp[i][j] ); 		
		cout << res << endl;
	} // end loop
		
	return 0;
}

Measured memory_bytes: 5172
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;

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

    ll ans = 0;
    for (int i = 1; i <= N; i++) {
        ll tmp = N / i;
        ans += tmp * (tmp + 1) * i / 2;
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3640
#! /usr/bin/env python3

# from fractions import gcd
from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

A, B, C, K= [int(_) for _ in input().split()]

ct = 0
k = K - A
if k >= 0:
    ct += A
else:
    ct += K

k = k - B
if k > 0:
    ct -= k
print(ct)

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

using namespace std;

typedef long long ll;

#define int long long

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int cnt = 1;
    int p = 1, q = 1;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        int cur = (cnt + x + y - 1) / (x + y);
        int f = (p + x - 1) / x;
        int g = (q + y - 1) / y;
        cur = max({cur, f, g});
        cnt = cur * x + cur * y;
        p = cur * x;
        q = cur * y;
    }
    cout << cnt << '\n';
    return 0;
}

Measured memory_bytes: 256
# A = [list(map(int, input().split())) for _ in range(3)]
# n = int(input())
# B = [int(input()) for _ in range(n)]
# X = list(map(int, input().split()))
n, a, b = map(int, input().split())
total = a+b
diff = n-((n//total)*total)
omake = n//total*a
if a <= diff:
    print(a+omake)
else:
    print(diff+omake)


Measured memory_bytes: 2940
import sys
sys.setrecursionlimit(10000000)


def main():
    K = int(input())
    A, B = map(int, input().split())
    for v in range(A, B + 1):
        if v % K == 0:
            print('OK')
            sys.exit()
    print('NG')


if __name__ == '__main__':
    main()


Measured memory_bytes: 9172
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

    int N;
    E[] g;

    void run() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        g = new E[N];
        for (int i = 0; i < N; i++) g[i] = new E();
        for (int i = 0; i < N - 1; i++) {
            int a = sc.nextInt() - 1, b = sc.nextInt() - 1;
            g[a].add(b);
            g[b].add(a);
        }

        last = 0;
        max = 0;
        dfs(0, 0, new boolean[N]);
        max = 0;
        dfs(last, 0, new boolean[N]);

        if (max % 3 == 1) {
            System.out.println("Second");
        } else {
            System.out.println("First");

        }
    }
    int last, max;
    void dfs(int p, int d, boolean[] visited) {
        visited[p] = true;
        if (max < d) {
            last = p;
            max = d;
        }
        for (int next: g[p]) if (!visited[next]) {
            dfs(next, d + 1, visited);
        }
    }

    class E extends ArrayList<Integer> {}

    void debug(Object...os) {
        System.err.println(Arrays.deepToString(os));
    }

    public static void main(String[] args) {
        new Main().run();
    }
}


Measured memory_bytes: 169860
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, X = MAP()

L = [0]*(N+1) #レベルiにおける全体の枚数
L[0] = 1

P = [0]*(N+1) #レベルiにおけるパティの枚数
P[0] = 1

for i in range(1, N+1):
	L[i] = L[i-1]*2 + 3
	P[i] = P[i-1]*2 + 1

def solve(i, x):  #レベルiの下からX層におけるパティの枚数
	if i == 0:
		if x <= 0:
			return 0
		else:
			return 1

	if x-1 <= L[i-1]:
		return solve(i-1, x-1)
	else:
		return P[i-1] + 1 + solve(i-1, x-L[i-1]-2)

print(solve(N, X))




Measured memory_bytes: 10476
#define _CRT_SECURE_NO_WARNINGS
#define _SCL_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <limits>
#include <numeric>
#include <valarray>
#include <fstream>
#include <array>
#include <random>
#include <unordered_set>
#include <unordered_map>

using namespace std;
using uint = uint32_t;
using LL = int64_t;
using ULL = uint64_t;
using PP = pair<LL, LL>;
template <typename T> using PriorityQ = priority_queue<T, vector<T>, greater<T> >;
#define REP(i, a, n) for(LL i = (a), i##_max_ = (n); i < i##_max_; ++i)
#define REM(i, a, n) for(LL i = (LL)(n) - 1, i##_min_ = (a); i >= i##_min_; --i)
#define FLOAT fixed << setprecision(16)
#define SPEEDUP { cin.tie(NULL); ios::sync_with_stdio(false); }
const int INF = 0x3FFFFFFF;
const LL INFLL = 0x3FFFFFFF3FFFFFFF;
const double INFD = 1.0e+308;
const double EPS = 1.0e-9;

void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
template <class T, class U> istream& operator>>(istream& ist, pair<T, U>& right) { return ist >> right.first >> right.second; }
template <class T, class U> ostream& operator<<(ostream& ost, const pair<T, U>& right) { return ost << right.first << ' ' << right.second; }
template <class T, class TCompatible, size_t N> void Fill(T(&dest)[N], const TCompatible& val) { fill(dest, dest + N, val); }
template <class T, class TCompatible, size_t M, size_t N> void Fill(T(&dest)[M][N], const TCompatible& val) { for (int i = 0; i < M; ++i) Fill(dest[i], val); }
template <class T> T Next() { T buf; cin >> buf; return buf; }
istream& Ignore(istream& ist) { string s; ist >> s; return ist; }
bool Inside(int i, int j, int h, int w) { return i >= 0 && i < h && j >= 0 && j < w; }

#ifdef ONLY_MY_ENVIR
#include "IntMod.h"
#include "Algebraic.h"
#include "BinaryMatrix.h"
#include "BinaryTree.h"
#include "Bipartite.h"
#include "BIT.h"
#include "DynamicMod.h"
#include "Factorization.h"
#include "FFT.h"
#include "FlowSolver.h"
#include "Graph.h"
#include "LazySegmentTree.h"
#include "Math.h"
#include "Matrix.h"
#include "MinCostFlowSolver.h"
#include "MinMax.h"
#include "Numbers.h"
#include "Polynomial.h"
#include "Position.h"
#include "Range.h"
#include "Rational.h"
#include "SegmentTree.h"
#include "SegmentTree2D.h"
#include "SuffixArray.h"
#include "Tree.h"
#include "UnionFind.h"
#endif

#ifdef __GNUC__
typedef __int128 LLL;
istream& operator>> (istream& ist, __int128& val) { LL tmp; ist >> tmp; val = tmp; return ist; }
ostream& operator<< (ostream& ost, __int128 val) { LL tmp = val; ost << tmp; return ost; }
#endif

LL N;
LL a[200000], b[200000];
int main() {
	cin >> N;
	REP(i, 0, N) {
		cin >> a[i] >> b[i];
	}

	LL ans = 0;
	LL dig = 0;
	LL sum = 0;
	REP(i, 0, N) {
		dig += b[i];
		sum += a[i] * b[i];
	}
	ans += dig - 1;
	ans += (sum - 1) / 9;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
#include<math.h>
#include<vector>
using namespace std;
#define MAX 200005
#define MOD 1000000007
#define NINF -1000000000000000000
long long dp[MAX][5];
int a[MAX];
void initialize(int n)
{
    int i,j;
    for(i=0;i<=n+1;i++)
    {
        for(j=0;j<5;j++)
        {
            dp[i][j]=NINF;
        }
    }
}
long long int sum(int index,int skip,int n)
{
    if(dp[index][skip]!=NINF)
    {
        //printf("DP(%d,%d)=%lld\n",index,skip,dp[index][skip]);
        return dp[index][skip];
    }
    if(index>=n)
    {
        if(n%2>0&&skip>1) dp[index][skip]=NINF/100;
        else dp[index][skip]=0;
        //printf("Default(%d,%d)=%lld\n",index,skip,dp[index][skip]);
        return dp[index][skip];
    }
    dp[index][skip]=sum(index+2,skip,n)+a[index];
    if(skip>0)
    {
        dp[index][skip]=max(dp[index][skip],sum(index+1,skip-1,n));
    }
    //printf("Recursion(%d,%d)=%lld\n",index,skip,dp[index][skip]);
    return dp[index][skip];
}
int main()
{
    int n,i,j;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    initialize(n);
    long long int ans=sum(0,1+n%2,n);
    printf("%lld",ans);
    return 0;
}


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

int main(){
  int n;
  cin>>n;
  vector<int> a(n),b(n),c(n);
  rep(i,n) cin>>a[i];
  rep(i,n) cin>>b[i];
  rep(i,n) cin>>c[i];
  sort(ALL(a));
  sort(ALL(c));
  long long ans=0;
  rep(i,n){
    ans+=(lower_bound(ALL(a),b[i])-a.begin())
      *(c.end()-upper_bound(ALL(c),b[i]));
  }
  cout<<ans<<endl;  
}

Measured memory_bytes: 4556
n,a,b = gets.split(" ").map(&:to_i)

count = 0
num = 0
(1..n).each do |i|
    ary = i.to_s.split(//)
    ary.each{|n| num = num + n.to_i}
    count = count + i if num >= a and b >= num
    
    num = 0
end
puts count

Measured memory_bytes: 1916
n, c = map(int, input().split())
stc = [list(map(int, input().split())) for _ in range(n)]
T = 10**5+1
record = [[0]*(T+3) for _ in range(c+1)]
channel = [[] for _ in range(c+1)]
stc.sort()

for s, t, c in stc:
    if not channel[c]:
        channel[c].append([s - 1, t])
        continue
    if channel[c][-1][1] == s:
        channel[c][-1][1] = t
    else:
        channel[c].append([s-1, t])

for i, v in enumerate(channel):
    for s, t in v:
        record[i][s] += 1
        record[i][t] -= 1

for i in record:
    for j in range(T+2):
        i[j+1] += i[j]

ans = 0
for i in range(T+2):
    y = 0
    for r in record:
        y += r[i]
    ans = max(ans, y)
print(ans)

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

int main(){
	int n;
	cin >> n;
	vector<int> p(n);
	for(int i = 0; i < n; i++) cin >> p[i];
	int cnt = 0;
	for(int i = 1; i < n - 1; i++){
		if(p[i] < p[i - 1] && p[i] > p[i + 1]) cnt++;
		else if(p[i] > p[i - 1] && p[i] < p[i + 1]) cnt++;
	}
	cout << cnt << endl;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

N, M = map(int, input().split())

if abs(N - M) >= 2:
    print (0)
    exit()

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0

#以下使い方

c = Factorial(max(N, M) + 2, MOD)

n = c.factorial(N)
m = c.factorial(M)

if (N == M):
    ans = 2 * n * m % MOD
else:
    ans = n * m % MOD

print (ans)

Measured memory_bytes: 11052
def main():
    n, p = map(int, input().split())
    a = list(map(int, input().split()))

    ans = 0
    even, odd = 0, 0
    for i in range(n):
        if a[i] % 2 == 0:
            even += 1
        else:
            odd += 1

    if odd == 0:
        if p == 1:
            print(0)
        else:
            print(2 ** n)
    else:
        print(2**(n - 1))


if __name__ == '__main__':
    main()


Measured memory_bytes: 38512
N = int(input())
a = [ int(s) - 1 for s in input()]

# r! に含まれる 2 の数
twos = {}
twos[0] = 0
for r in range(1, N):

    count = 0
    tmp = r
    while tmp % 2 == 0:
        tmp //= 2
        count += 1
    
    twos[r] = twos[r-1] + count


# {N-1}_C_r の偶数奇数判定
ncr = {}
for r in range(N):
    if twos[N-1] - twos[N-1-r] - twos[r] > 0:
        ncr[r] = 0
    else:
        ncr[r] = 1


# 答えの判定
oe = 0
for r, ai in enumerate(a):
    oe = (oe + ncr[r] * ai) % 2

if oe == 1:
    print(1)
else:
    if 1 in a:
        print(0)
    else:
        oe2 = 0
        for r, ai in enumerate(a):
            oe2 = (oe2 +ncr[r] * ai // 2 ) %2
        if oe2 == 1:
            print(2)
        else:
            print(0)

Measured memory_bytes: 198440
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stdlib.h>
#include <cmath>
#include <set>

using namespace std;
#define mk make_pair
typedef long long ll;
typedef pair<int,int> P;
const int maxn=100100;
const int mod=1000000007;
const ll INF=1000000000;

int a[maxn];

int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    cout<<max(0,c-(a-b))<<endl;
    return 0;
}

/*
 2598708396863
*/


Measured memory_bytes: 256
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int,int>;
using PLL = pair<LL, LL>;
const int INF = 1e9;
const int MXN = 0;
const int MXV = 0;
#define MP  make_pair
#define PB push_back
#define F first
#define S second
#define FOR(i, L, R) for(int i = L; i != (int)R; ++i)
#define FORD(i, L, R) for(int i = L; i != (int)R; --i)
#define IOS cin.tie(nullptr); cout.tie(nullptr); ios_base::sync_with_stdio(false);

LL sol(LL x)
{
    if(x == 1)
    {
        return 1;
    }
    return 2 * sol(x / 2) + 1;
}

int main()
{
    IOS;
    LL h;
    cin >> h;
    cout << sol(h) << '\n';
}


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

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

	int x, y;
	vector <pair <int, int>> W;
	vector <pair <int, int>> X;
	for (int i = 0; i < N; i++) {
		cin >> x >> y;
		W.push_back(make_pair(x, y));
	}
	sort(W.begin(), W.end());
	int a, b;
	for (int j = 0; j < N; j++) {
		for (int k = 0; k < N; k++) {
			if (j != k) {
				a = W[k].first - W[j].first;
				b = W[k].second - W[j].second;
				X.push_back(make_pair(a, b));
			}
		}

	}
	
	sort(X.begin(), X.end());
	int count = 0, max = 0;
	for (int k = 0; k < X.size(); k++) {
		if (k == 0) {
			count = 1;
			max = 1;
		}
		else if (X[k].first == X[k - 1].first && X[k].second == X[k - 1].second) {
			count++;
		}
		else {
			if (max < count) {
				max = count;
			}
			count = 1;
		}
	}

	cout << N - max << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
using namespace std;
const int N = 1000050;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353LL;
clock_t TIME_START, TIME_END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used: %.6lf(s)\n", ((double)TIME_END - TIME_START) / CLOCKS_PER_SEC);
    system("pause");
#endif
}
int n;
int s[N];
multiset<int, greater<int>> S1, S2;
set<int> vis;
int id[N];
int tot;

inline int Query(int x)
{
    auto it = vis.lower_bound(x);
    if (it != vis.begin())
    {
        it--;
        return *it;
    }
    return -1;
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= st(n); ++i)
        scanf("%d", &s[i]);
    for (int i = 1; i <= st(n); ++i)
        vis.insert(s[i]);
    for (int i = 1; i <= st(n); ++i)
        S1.insert(s[i]);
    sort(s + 1, s + st(n) + 1, greater<int>());
    S2.insert(s[1]);
    S1.erase(S1.find(s[1]));
    if (S1.count(s[1]) == 0)
        vis.erase(s[1]);
    int tim = 1;
    vector<int> tmp;
    while (tim <= n)
    {
        // puts("flag");
        tmp.clear();
        for (auto &i : S2)
        {
            int x = Query(i);
            if (S1.empty())
                return puts("Yes"), void();
            if (x == -1 || S1.find(x) == S1.end())
                return puts("No"), void();
            S1.erase(S1.find(x));
            if (S1.find(x) == S1.end())
                vis.erase(x);
            if (S1.empty())
                return puts("Yes"), void();
            tmp.push_back(x);
        }
        for (auto &i : tmp)
            S2.insert(i);
        tim++;
    }
    puts("No");
}

int main()
{
    TIME_START = clock();
    int Test = 1;
    // cin >> Test;
    while (Test--)
        solve();
    TIME_END = clock();
    program_end();
    return 0;
}
/*
3
5 4 4 4 3 3 2 1
*/

Measured memory_bytes: 29568
// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools

#include <bits/stdc++.h>
// #include "atcoder/all"

using namespace std;

using i64 = long long;

const i64 MOD = 1e9 + 7;
const i64 INF = i64(1e18) + 7;


template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}


void solve(std::string s){
    if(s.back() != 's')
        s += "s";
    else
        s += "es";
    cout <<s<<endl;
}


signed main(){
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


Measured memory_bytes: 3576
x_r, y_o, N = map(int, input().split())
a = [list(map(int, input().split())) for i in range(N)]
x_l = 0
y_u = 0
area = x_r * y_o
if area == 0:
    print(area)
else:
    for i in a:
        if i[2] == 1:
            if i[0] <= x_l:
                continue
            else:
                area -= (i[0] - x_l) * (y_o - y_u)
                if i[0] >= x_r:
                    area = 0
                    break
                else:
                    x_l = i[0]
        elif i[2] == 2:
            if i[0] >= x_r:
                continue
            else:
                area -= (x_r - i[0]) * (y_o - y_u)
                if i[0] <= x_l:
                    area = 0
                    break
                else:
                    x_r = i[0]
        elif i[2] == 3:
            if i[1] <= y_u:
                continue
            else:
                area -= (i[1] - y_u) * (x_r - x_l)
                if i[1] >= y_o:
                    area = 0
                    break
                else:
                    y_u = i[1]
        else:
            if i[1] >= y_o:
                continue
            else:
                area -= (y_o - i[1]) * (x_r - x_l)
                if i[1] <= y_u:
                    area = 0
                    break
                else:
                    y_o = i[1]
    print(area)


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

int main()
{
	int K, X;
	cin >> K >> X;

	for( int i = X - (K - 1), j = 0; i < X + K; i++, j++ ) {
		if( j ) cout << " ";
		cout << i;
	}
	cout << endl;
}


Measured memory_bytes: 256
import fractions
n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
  a[i] = a[i] //2
def count_2(k):
  c = 0
  while k % 2 == 0:
    k = k // 2
    c+=1
  return c
count = count_2(a[0])
for i in range(n):
  if count != count_2(a[i]):
    print(0)
    exit()
ans = a[0]
for i in range(1, n):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
print((m // ans +1)//2)


Measured memory_bytes: 16284
#include<bits/stdc++.h>
using namespace std;
#define pi 3.14159265359
#define int long long
#define pii pair<int,int>
const int mod=1e9+7;

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




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


int n;
cin>>n;
cout<<(n+1)/2;

  
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
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; }
int main(){
    ll r;
    cin>>r;
    cout<<r*r<<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 so(v) sort(v.begin(),v.end())
using ll = long long;
using vi=vector<int>;
using vii=vector<vi>;
const int MAX = 510000;
const int MOD = 998244353;
long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main() {
  int n;cin>>n;
  string a;
  set<string> s;
  rep(i,n){
    cin>>a;
    s.insert(a);
  }
  cout<<s.size()<<endl;
}

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

const int MAXN = 1.1e6;
int N;
char S[MAXN];

int cnt[3];

string go() {
	for (int i = 1; i <= N; i++) {
		cnt[S[i] - 'A'] ++;
	}
	vector<pair<int, int>> cnts({{cnt[0], 0}, {cnt[1], 1}, {cnt[2], 2}});
	sort(cnts.begin(), cnts.end());
	const int A = cnts[2].second;
	const int B = cnts[1].second;
	const int C = cnts[0].second;
	cerr << A << ' ' << B << ' ' << C << '\n';

	if (cnt[C] == 0) {
		return "";
	}
	vector<pair<bool, int>> regions; // isA and length
	regions.emplace_back(false, 0);
	for (int i = 1; i <= N; i++) {
		if (S[i] - 'A' == C) {
			regions.emplace_back(false, 0);
		} else {
			assert(S[i] - 'A' == A || S[i] - 'A' == B);
			if (regions.back().second == 0) {
				regions.back().first = (S[i] - 'A' == A);
			}
			regions.back().second++;
		}
	}
	int M = int(regions.size()) - 1;
	assert(M == cnt[C]);
	for (int i = 0; cnt[A] > cnt[B] && i <= M; i++) {
		if (regions[i].second == 0) continue;
		if (regions[i].second == 1 && (i != 0 && i != M)) continue;

		bool startA = regions[i].first;
		bool endA = regions[i].second % 2 == 0 ? (!startA) : startA;
		if (startA) {
			cnt[A] --;
			regions[i].first ^= 1;
			regions[i].second --;
			i--;
			continue;
		} else if (endA) {
			cnt[A] --;
			regions[i].second --;
			i--;
			continue;
		} else {
			// no a's to cut
		}
	}

	{
		// must mean we have a lot of singleton regions
		// just remove those
		vector<pair<bool, int>> nRegions;
		for (int i = 0; i <= M; i++) {
			if (regions[i].first == true && regions[i].second == 1) {
				if (cnt[A] > cnt[B]) {
					cnt[A] --;
					cnt[C] --;
					continue;
				}
			}
			// otherwise add it
			nRegions.push_back(regions[i]);
		}
		regions = nRegions;
		M = int(regions.size()) - 1;
		assert(M == cnt[C]);
		if (M == 0) return "";
		assert(M > 0);
	}

	assert(cnt[A] == cnt[B]);

	// now we just need to delete
	for (int i = 0; cnt[A] > cnt[C] && i <= M; i++) {
		if (regions[i].second <= 1) continue;
		if (regions[i].second == 2 && (i != 0 && i != M)) continue;
		{
			regions[i].second -= 2;
			cnt[A] --;
			cnt[B] --;
			i--;
			continue;
		}
	}
	assert(cnt[A] == cnt[B] && cnt[A] == cnt[C]);

	string res = "";
	for (int i = 0; i <= M; i++) {
		if (i) res += char('A' + C);
		for (int j = 0, d = regions[i].first; j < regions[i].second; j++, d ^= 1) {
			res += (d ? char('A' + A) : char('A' + B));
		}
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	string _S; cin >> _S;
	S[0] = '^';
	for (char c : _S) {
		if (c != S[N]) {
			S[++N] = c;
		}
	}
	S[N+1] = '$';
	S[N+2] = 0;
	
	//cerr << S << '\n';

	cout << go() << '\n';

	return 0;
}


Measured memory_bytes: 12692
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

import collections

N = int(input())

ans = 1
for n in range(2,N):
    a = prime_factorize(n)
    c = collections.Counter(a)
    ans_ = 1
    for i in c.values():
        ans_ *= (i+1)
    ans += ans_
print(ans)

Measured memory_bytes: 69964
import java.util.*;
import java.lang.*;
import java.util.HashSet;

/**
 * Dictionary
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Set<String> set = new HashSet<String>();
        int n = sc.nextInt();

        for (int i = 0; i < n; i++) {
            String pushorpull = sc.next();
            String word = sc.next();

            if (pushorpull.equals("insert")) {
                set.add(word);
            } else {
                if (set.contains(word)) {
                    System.out.println("yes");
                } else {
                    System.out.println("no");
                }
            }
        }
    }
}


Measured memory_bytes: 251652
///Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>

#define                           ll                          long long
#define                           int                         ll
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<ll,ll>
#define                           clr(x)                      memset(x,0,sizeof(x));
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           show(x,y)                   cout<<x<<" : ";for(auto z:y)cout<<z<<" ";cout<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const ll inf=1e18;
const int mod=1e9+7;
const int M=1002;
int n,m;
int x[M],y[M],z[M];
int dp[M][M];
int solve(int pos,int baki,int a,int b,int c)
{
    if(pos>n)
    {
        if(baki==0)return 0;
        else return -inf;
    }
    int &ret=dp[pos][baki];
    if(ret!=(-1))return ret;
    ret=solve(pos+1,baki,a,b,c);
    if(baki==0)return ret;
    int nx=x[pos]*a,ny=y[pos]*b,nz=z[pos]*c;
    int cost=nx+ny+nz;
    ret=max(ret,cost+solve(pos+1,baki-1,a,b,c));
    return ret;
}
 main()

{
    fast
    cin>>n>>m;
    f(i,1,n)cin>>x[i]>>y[i]>>z[i];
    int ses=-inf;
    f(i,-1,1)f(j,-1,1)f(k,-1,1)
    {
        if(i==0 || j==0 || k==0)continue;
        memset(dp,-1,sizeof dp);
        ses=max(ses,solve(1,m,i,j,k));
    }
    cout<<ses<<endl;
    return 0;

}





































Measured memory_bytes: 8192
#include <iostream>
#include <map>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

typedef unsigned long long ull;

int main()
{
    string a, b;
    string s;
    
    cin >> a >> s >> b;
    
    const char *p = s.c_str();
    
    printf("A%cC\n", p[0]);
    
    return 0;
}


Measured memory_bytes: 256