akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>
ostream& operator<<(ostream &os, vector<T> &v){
	string sep = " ";
	if(v.size()) os << v[0];
	for(int i=1; i<v.size(); i++) os << sep << v[i];
	return os;
}

#ifdef DBG
void debug_(){ cout << endl; }
template<typename T, typename... Args>
void debug_(T&& x, Args&&... xs){
	cout << x << " "; debug_(forward<Args>(xs)...);
}
#define dbg(...) debug_(__VA_ARGS__)
#else
#define dbg(...)
#endif

int main() {
	ios_base::sync_with_stdio(false);
	cout << setprecision(20) << fixed;

	int n; cin >> n;
	vector<pair<ll, ll>> ab(n);
	vector<pair<ll, ll>> ba(n);
	for(int i=0; i<n; i++){
		cin >> ab[i].first >> ab[i].second;
		ba[i].first = ab[i].second;
		ba[i].second = ab[i].first;
	}

	sort(ab.begin(), ab.end());
	sort(ba.rbegin(), ba.rend());

	if(n%2){
		ll lb = ab[n/2].first;
		ll ub = ba[n/2].first;

		cout << ub - lb + 1 << endl;
	} else {
		ll lb1 = ab[n/2-1].first;
		ll ub1 = ba[n/2].first;

		ll lb2 = ab[n/2].first;
		ll ub2 = ba[n/2-1].first;

		dbg(lb1, ub1, lb2, ub2);

		cout << ub1+ub2 - lb1-lb2 + 1 << endl;
	}

	return 0;
}


Measured memory_bytes: 9596
package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getInt()
	}
	return ret
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

//---------------------------------------------
// priority queue
//---------------------------------------------
type pqi struct{ cnt, val int }

type priorityQueue []pqi

func (pq priorityQueue) Len() int      { return len(pq) }
func (pq priorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq priorityQueue) Less(i, j int) bool {
	if pq[i].cnt == pq[j].cnt {
		return pq[i].val > pq[j].val
	}
	return pq[i].cnt > pq[j].cnt
}
func (pq *priorityQueue) Push(x interface{}) { *pq = append(*pq, x.(pqi)) }
func (pq *priorityQueue) Pop() interface{} {
	x := (*pq)[len(*pq)-1]
	*pq = (*pq)[0 : len(*pq)-1]
	return x
}

const maxN = 201000

func main() {
	sc.Split(bufio.ScanWords)
	N := getInt()
	A := make([]int, N)
	a := make([]int, maxN)
	b := make([]int, maxN)
	for i := 0; i < N; i++ {
		x := getInt()
		A[i] = x
		a[x]++
	}
	for i := 0; i < N; i++ {
		x := getInt()
		b[x]++
	}

	pq := priorityQueue{}
	for i := 0; i < maxN; i++ {
		if a[i]+b[i] > N {
			out("No")
			return
		}
		if b[i] != 0 {
			heap.Push(&pq, pqi{b[i], i})
		}
	}

	ans := make([]int, N)
	for i := 0; i < N; i++ {
		p0 := pq[0]
		heap.Pop(&pq)
		if p0.val != A[i] {
			ans[i] = p0.val
			p0.cnt--
			if p0.cnt > 0 {
				heap.Push(&pq, p0)
			}
		} else {
			if len(pq) == 0 {
				for j := 0; j < N-1; j++ {
					// out(A[j], A[i], ans[j], p0.val)
					if A[j] != p0.val && A[i] != ans[j] {
						ans[j], ans[i] = p0.val, ans[j]
						break
					}
				}
				p0.cnt--
				if p0.cnt > 0 {
					heap.Push(&pq, p0)
				}
				continue
			}
			p1 := heap.Pop(&pq).(pqi)
			ans[i] = p1.val
			heap.Push(&pq, p0)
			p1.cnt--
			if p1.cnt > 0 {
				heap.Push(&pq, p1)
			}
		}
	}

	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()
	fmt.Fprintln(w, "Yes")
	for i := 0; i < N; i++ {
		fmt.Fprint(w, ans[i], " ")
	}
	fmt.Fprintln(w)
}


Measured memory_bytes: 23128
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define se second
#define fi first
#define rep(i, l, r) for (ll i = (ll)(l); i < (ll)(r); i++)
#define print(v) for (const auto itr : v){cout << itr << ' ';} cout << endl;
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
#define endl "\n"
#define inf 1e18
using namespace std;
const ll INF = 1e18L + 5;
const ll maxn = 1e6+5, maxn1=2e5+3;
#define MAXN 200005
ll ceel(ll a, ll b)
{
   if (a % b == 0)
       return a / b;
   return a / b + 1;
}
ll modneg(ll a,ll m)
{
    a = a % m;
    if(a<0)
        a=a+m;
    return a;
}
ll powermod(ll x, unsigned 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 lcm(ll a, ll b) { return (a * b) / __gcd(a, b); };



int main()
{

ll n,i,j,k,a,b,c,d,test,cnt=0;
cin>>n;
vector <ll> v,v1;
rep(i,0,n)
{
    cin>>a>>b;
    v.pb(a);
    v1.pb(b);
}
sort(v.begin(),v.end());
sort(v1.begin(), v1.end());
if(n%2)
{
    k=n/2;
    ll l=v[k],r=v1[k];
    cout<<r-l+1;
}
else
{
    k=n/2;
    ll l=(v[k-1]+v[k]);
    ll r=(v1[k-1]+v1[k]);
    cout<<(r-l)+1;
}
return 0;
}



Measured memory_bytes: 6616
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
//#include<queue>
#include<algorithm>
//#include<iostream>
//#include<assert.h>
using namespace std;
 
int q;
#define LL long long
#define double long double
int main()
{
	scanf("%d",&q);
	while (q--)
	{
		int a,b; scanf("%d%d",&a,&b);
		if (a==1 && b==1) {puts("0"); continue;}
		if (a>b) a^=b^=a^=b; LL c=1ll*a*b-1,d=(LL)(sqrt((double)c));
		if (d*d>c) d--;
		LL ans=2*d-1;
		if (a==b) ans++;
		if (d==c/d) ans--;
		if (c/d==a && d!=a) ans--;
		printf("%lld\n",ans);
	}
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <bitset>
#include <cmath>
#define ff first
#define ss second
#define MAXN 300005
#define INF 1000000001000000001LL
#define int long long

using namespace std;

const int mod = 998244353; //1000000007;
int n, ans, i, j, k, m, a[105][105], b[105][105], mt[105];
bool used[105], f[105][105];
vector <int> g[105];

bool dfs(int v){
    int to, i;

    used[v] = true;

    for(i = 0; i < g[v].size(); i++){
        to = g[v][i];

        if(mt[to] == -1 || (!used[mt[to]] && dfs(mt[to]))){
            mt[to] = v;
            return 1;
        }
    }

    return 0;
}

main(){
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios_base :: sync_with_stdio(false);
    cin.tie();
    cin >> n >> m;

    for(i = 0; i < n; i++){
        for(j = 0; j < m; j++)
            cin >> a[i][j], a[i][j]--;
    }

    for(i = 0; i < m; i++){
        for(j = 0; j < n; j++){
            g[j].clear();
            mt[j] = -1;
        }

        for(j = 0; j < n; j++){
            for(k = 0; k < m; k++){
                if(!f[j][k])
                    g[a[j][k] / m].push_back(j);
            }
        }

        for(j = 0; j < n; j++){
            fill(used, used + n, 0);
            dfs(j);
        }

        for(j = 0; j < n; j++){
            //cout << mt[j] << " ";
            for(k = 0; k < m; k++){
                if(!f[j][k] && a[j][k] / m == mt[j])
                    break;
            }

            f[j][k] = true;
            b[j][i] = a[j][k];
        }
        //cout << endl;
    }

    for(i = 0; i < n; i++){
        for(j = 0; j < m; j++)
            cout << b[i][j] + 1 << " ";
        cout << endl;
    }

    for(i = 0; i < m; i++){
        for(j = 0; j < n; j++){
            for(k = j + 1; k < n; k++){
                if(b[j][i] > b[k][i])
                    swap(b[j][i], b[k][i]);
            }
        }
    }

    for(i = 0; i < n; i++){
        for(j = 0; j < m; j++)
            cout << b[i][j] + 1 << " ";
        cout << endl;
    }

    return 0;
}







Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

ll a[11],n,ans;
bool b[11];
void cal(){
	ll sum=a[0];
	for(int i=1;i<n;i++){
		if(b[i-1]){
			ans+=sum;
			sum=a[i];
		}
		else{
			sum=sum*10+a[i];
		}
	}
	ans+=sum;
}
void dep(ll now){
	if(now==n-1){
		cal();
		return;
	}
	b[now]=true;dep(now+1);
	b[now]=false;dep(now+1);
}
int main() {
	string s;
	cin>>s;
	n=s.size();
	for(int i=0;i<n;i++){
		ll now=s[i]-'0';
		a[i]=now;
	}
	dep(0);
	cout <<ans;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#define M 1500000
#define NIL -1
#define L 13

char A[M][L];

int getChar(char c) {
	if (c == 'A')return 1;
	else if (c == 'C')return 2;
	else if (c == 'G')return 3;
	else if (c == 'T')return 4;
	else return 0;
}

int getKey(char str[]) {
	int i, total = 0, p = 1;
	for (i = 0; i < strlen(str); i++) {
		total += p * (getChar(str[i]));
		p *= 5;
	}
	return total;

}

int h1(int key) {
	return key % M;
}
int h2(int key) {
	return 1 + (key % (M - 1));
}

int find(char str[]) {

	int key, h, i;
	key = getKey(str);
	i = 0;
	while (1) {
		h = (h1(key) + i * h2(key)) % M;
		if (strcmp(A[h], str) == 0)return 1;
		else if (strlen(A[h]) == 0)return 0;
		i++;
	}
	return 0;

}

int insert(char str[]) {


	int key, i, h;
	key = getKey(str);
	i = 0;
	while (1) {
		h = (h1(key) + i * h2(key)) % M;
		if (strcmp(A[h], str) == 0)return 1;
		else if (strlen(A[h]) == 0) {
			strcpy(A[h], str);
			return 0;

		}
		i++;
	}
	return 0;

}


int main() {
	int i, h, n;
	char str[L], com[9];
	for (i = 0; i < M; i++)A[i][0] = '\0';
	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		scanf("%s %s", com, str);
		if (com[0] == 'i') {
			insert(str);
		}
		else {
			if (find(str)) {
				printf("yes\n");
			}
			else {
				printf("no\n");
			}
		}

	}

	return 0;
}


Measured memory_bytes: 20820
#include<cstdio>
const int MaxN=100010;
int N,A[MaxN];
long long S[MaxN];
char op[MaxN];
void cmax(long long&a,long long b){b>a?a=b:1;}
int main(){
	scanf("%d%d",&N,A);
	for(int i=1;i<N;i++)scanf("%s%d",op+i,A+i);
	long long ans=0,cur=0;
	for(int i=0;i<N;i++){
		S[i+1]=S[i]+A[i];
		ans+=op[i]=='-'?-A[i]:A[i];
	}
	for(int i=0,j;i<N;i++){
		if(op[i]=='-'){
			for(j=i+1;j<N&&op[j]!='-';j++);
			cmax(ans,cur+S[N]-S[j]*2+S[i]);
			cur-=A[i];
		}
		else cur+=A[i];
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 1408
def main(plan):
    #現在地の初期化
    p0 = [0,0,0]
    #1つ目
    if not CanReach(p0, plan[0]):
        return False
    #2つ目以降
    for i in range(1,len(plan)):
        if not CanReach(plan[i-1], plan[i]):
            return False
    return True

#p1->p2へt秒で移動可能か判断
def CanReach(p1, p2):
    #移動時間
    t = p2[0] - p1[0]
    #最短でかかる秒数
    t_min = abs(p1[1] - p2[1]) + abs(p1[2] - p2[2])
    #t秒以内に到達可能かつ余りが偶数ならOK
    if t_min <= t and (t-t_min) % 2 == 0:
        return True
    return False


n = int(input())
plan = list(list(map(int,input().split())) for _ in range(n))
print("Yes" if main(plan) else "No")

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

int main(){
    string S;
    cin >> S;
    bool flag = true;
    for(int i=0;i<S.size();++i){
        if(i%2==0 && !(S[i]=='R' || S[i]=='U' || S[i]=='D')) flag = false;
        else if(i%2==1 && !(S[i]=='L' || S[i]=='U' || S[i]=='D')) flag = false;
    }
    if(flag) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define a(v) (v.begin(), v.end())
#define ll long long
#define vi vector<int>
#define vii vector<vi>
#define vl vector<ll>
#define vll vector<vl>
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define per(i, a, b) for (ll i = a; i > b; i--)
#define intlimit 2e9 + 100
#define longlimit 8e18 + 100
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
using namespace std;
int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ll a, b, c;
  cin >> a >> b >> c;
  ll x = 2 * a * b + 2 * a * c + 2 * b * c;
  ll y = a * a + b * b + c * c;
  if (c - b - a <= 0)
  {
    cout << "No\n";
    return 0;
  }
  if (x < y)
  {
    cout << "Yes\n";
  }
  else
  {
    cout << "No\n";
  }
}

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

int main(void){
    int Y,X;
    cin >> Y >> X;
    vector<string> s(Y);
    vector<int> cnt(X);
    rep(y,Y) {
        cin >> s[y];
        rep(x,X){
            if (s[y][x] == '#') {
                cnt[x]++;
            }
        }
    }
    rep(y,Y){
        if (count(all(s[y]), '#') == 0) {
            continue;
        }
        rep(x,X){
            if (cnt[x] == 0) continue;
            cout << s[y][x];
        }
        cout << endl;
    }
    return 0;
}


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

int solve(vector<int>& ht,int n) {
    vector<int>dp(n,0);
    dp[0]=0;
    dp[1]=abs(ht[1]-ht[0]);

    for(int i=2;i<n; i++) {
        dp[i]= min((dp[i-1]+abs(ht[i]-ht[i-1])),(dp[i-2]+abs(ht[i]-ht[i-2])));
    }
    return dp[n-1];
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("input.txt","r",stdin);
    vector<int>ht;
    int n;
    cin>>n;
    for(int i=0; i<n; i++) {
        int a;
        cin>>a;
        ht.push_back(a);
    }

    cout<<solve(ht,n)<<endl;



}


Measured memory_bytes: 1144
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::Read;
#[allow(dead_code)]
fn getline() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok().unwrap();
    ret
}
fn get_word() -> String {
    let mut stdin = std::io::stdin();
    let mut u8b: [u8; 1] = [0];
    loop {
        let mut buf: Vec<u8> = Vec::with_capacity(16);
        loop {
            let res = stdin.read(&mut u8b);
            if res.unwrap_or(0) == 0 || u8b[0] <= b' ' {
                break;
            } else {
                buf.push(u8b[0]);
            }
        }
        if buf.len() >= 1 {
            let ret = String::from_utf8(buf).unwrap();
            return ret;
        }
    }
}

#[allow(dead_code)]
fn get<T: std::str::FromStr>() -> T { get_word().parse().ok().unwrap() }

fn solve() {
    loop {
        let n: usize = get();
        if n == 0 { break; }
        let s: Vec<_> = get_word().chars().collect();
        let mut set = vec![0; n + 1];
        let mut self_broken = false;
        for (i, ch) in s.into_iter().enumerate() {
            set[i + 1] = match ch {
                'u' => 0,
                x => {
                    let u = x as u8 - b'0';
                    if (set[i] & 1 << u) != 0 {
                        self_broken = true;
                        0
                    } else {
                        set[i] | 1 << u
                    }
                },
            }
        }
        if self_broken {
            println!("UNSAFE");
            continue;
        }
        let mut nxt_cand = [0; 1 << 10];
        for i in 1 .. n {
            if set[i] != 0 {
                nxt_cand[set[i - 1]] |= set[i] ^ set[i - 1];
            }
        }
        let mut ok = true;
        // TODO O(2^30) -> O(2^20)
        for bits in 1 .. 1 << 10 {
            let mut dp = vec![0; bits + 1];
            dp[0] = 1;
            let mut sub1iter = (bits - 1) & bits;
            loop {
                let sub1 = bits - sub1iter;
                let mut sub2 = sub1;
                loop {
                    if sub2 == 0 { break; }
                    if (nxt_cand[sub2] & bits) != 0 {
                        dp[sub1] |= dp[sub1 ^ sub2];
                    }
                    sub2 = (sub2 - 1) & sub1;
                }
                if sub1iter == 0 { break; }
                sub1iter = (sub1iter - 1) & bits;
            }
            if dp[bits] > 0 {
                ok = false;
                break;
            }
        }
        println!("{}", if ok { "SAFE" } else { "UNSAFE" });
    }
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}



Measured memory_bytes: 9084
import java.io.*;
import java.util.*;

public class Main{
    public static void main(String args[]) throws Exception{
    	BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
    	Deque<Character> par= new LinkedList<Character>();
    	String str= new String();
    	while( !(str= br.readLine()).equals(".") ){
        	boolean balanced= true;
        	par.clear();
    		for(int i=0;i<str.length();i++){
        		if( str.charAt(i)=='(' ){
        			par.addFirst('(');
        		} else if( str.charAt(i)=='[' ){
        			par.addFirst('[');
        		}
        		else if( str.charAt(i)==')' ){
        			if( par.isEmpty() || par.remove()!='(' ){
        				balanced= false;
        				break;
        			}
        		} else if( str.charAt(i)==']' ){
        			if( par.isEmpty() || par.remove()!='[' ){
        				balanced= false;
        				break;
        			}
        		}
    		}
    		balanced= balanced && par.isEmpty();
    		if(balanced){ System.out.println("yes"); }
    		else{ System.out.println("no"); }
    	}
    }
}

Measured memory_bytes: 25288
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

typedef vector<int> VI;
typedef vector<bool> VB;

const int SIZE = 1000001;

VI memo( SIZE, -2 );
VB visited( SIZE, false );

int dfs ( int num )
{
	if ( memo[num] != -2 ) {
		return memo[num];
	}
	if ( memo[num] == -2 && visited[num] ) {
		return memo[num] = -1;
	}
	if ( num < 10 ) {
		return memo[num] = 0;
	}
	int m = 10,
		next = 0,
		res = -1;
	visited[num] = true;
	while ( num >= m ) {
		next = max( next, ( num / m ) * ( num % m ) );
		m *= 10;
	}
	res = dfs( next );
	res += res != -1;
	return memo[num] = res;
}

int main ( void )
{
	int q;
	while ( cin >> q ) {
		for ( int i = 0; i < q; ++i ) {
			int n;
			cin >> n;

			cout << dfs( n ) << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 5220
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
#define tll tuple<ll, ll, ll>
#define all(c) c.begin(),c.end()

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
 
const ll inf = 1000000001;
const ll INF = 1e18;
const ll MOD = 1000000007;

char albt[26] = {'a','b','c','d','e','f','g','h','i','j','k','l',
                 'm','n','o','p','q','r','s','t','u','v','w','x',
                 'y','z'};

//vector<ll> g[202020];
//fill(score, score+202020, 0);
//vector<ll> v;

int main(){
  ll n, m;
  cin >> n >> m;
  
  ll cost[m];
  vector<ll> ky[m];
  for (int i=0;i<m;i++){
    ll a, b;
    cin >> a >> b;
    cost[i] = a;
    for (int j=0;j<b;j++){
      ll tmp;
      cin >> tmp;
      ky[i].push_back(tmp);
    }
  }
  //for (int j=0;j<ky[2].size();j++) cout << ky[2][j] << endl;
  
  ll dp[(1 << n)];
  fill(dp, dp+(1 << n), INF);
  dp[0] = 0;
  for (int i=0;i<m;i++){
    ll poss = 0;
    for (int j=0;j<ky[i].size();j++) poss |= (1 << (ky[i][j]-1));
    //cout << "poss" << " " << poss << endl;
    
    for (int j=0;j<(1 << n);j++){
      ll cand = dp[j] + cost[i];
      if (dp[j | poss] > cand) dp[j | poss] = cand;
    }
    //for (int j=0;j<(1 << n);j++) cout << dp[j] << endl;
  }
  
  if (dp[(1 << n) - 1] == INF) dp[(1 << n) - 1] = -1;
  cout << dp[(1 << n) - 1] << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <random>
#include <complex>
#include <assert.h>

using namespace std;
typedef long long ll;
#define endl '\n'

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

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

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

	int N; cin >> N;
	vector<int> v(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}

	int c = 0;
	for (int i = 0; i < N; i++) {
		if (i % 2 == 0 && v[i] % 2 == 1) {
			c++;
		}
	}

	cout << c << endl;

	return 0;
}

Measured memory_bytes: 3192
import sys
readline = sys.stdin.readline
L = int(input())
dp = [0] * 5
for a in map(int, (readline() for _ in range(L))):
    back = a % 2 if a > 0 else 2
    through = (a + 1) % 2
    dp[4] = min(dp[:5]) + a
    dp[3] = min(dp[:4]) + back
    dp[2] = min(dp[:3]) + through
    dp[1] = min(dp[:2]) + back
    dp[0] += a
print(min(dp))


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;

typedef long long ll;
typedef unsigned long long llu;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<string, int> psi;
typedef pair<char, int> pci;
typedef pair<int, char> pic;
const ll MOD = 998244353;
const long double PI = 3.141592653589793238462643383279502884197;

ll fac[1] = {1}, inv[1] = {1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll mp(ll a,ll b){ll ret=1;while(b){if(b&1)ret=ret*a%MOD;a=a*a%MOD;b>>=1;}return ret;}
ll cmb(ll r, ll c) {return (c>r||c<0) ? 0:fac[r] * inv[c] % MOD * inv[r - c] % MOD;}

// 일단, 구간합?
// 이 구간을 d로 덮어야 한다는 레이지에 대한 저장.
// 각 자리마다 어떤 할당되는 배수 같은 게 있는데.
// 이제 그거의 합을 또 모아놓아야 할듯?
// 이제... 음, 원래의 구간합하고.
// 덮여진 레이지 정보에 대해서.
// 구간의 합을 "대체"...

ll btree[1<<19];
ll tree[1<<19];
ll lazy[1<<19];
int szz=1<<18;

void prop(int i) {
    if (!lazy[i]) return;
    tree[i] = btree[i] * lazy[i] % MOD;

    if (i < szz) {
        lazy[i * 2] = lazy[i];
        lazy[i * 2 + 1] = lazy[i];
    }
    lazy[i] = 0;
}

void upd(int i, int l, int r, int le, int ri, int val) {
    prop(i);
    if (l > ri || r < le) return;
    if (l <= le && ri <= r) {
        lazy[i] = val;
        prop(i);
        return;
    }
    upd(i*2,l,r,le,(le+ri)/2,val), upd(i*2+1,l,r,(le+ri)/2+1,ri,val);
    tree[i] = (tree[i*2] + tree[i*2+1]) % MOD;
}

/*
int find(int i, int l, int r, int le, int ri) {
    if (l > ri || r < le) return 0;
    if (l <= le && ri <= r) return tree[i];
    return max(find(i*2,l,r,le,(le+ri)/2), find(i*2+1,l,r,(le+ri)/2+1,ri));
}
void upd(int i, int val) {
    i += szz;
    tree[i] = max(tree[i], val);
    while (i/=2) tree[i] = max(tree[i*2], tree[i*2+1]);
}*/

void binit(int i) {
    if (i >= szz) return;
    binit(i*2); binit(i*2+1);
    btree[i] = (btree[i*2] + btree[i*2+1]) % MOD;
    tree[i] = (tree[i*2] + tree[i*2+1]) % MOD;
}

int main() {
    int n,q;
    scanf("%d %d",&n, &q);

    ll now = 1;
    for (int i = 0; i < n; i++) {
        btree[n-i-1+szz] = now; // 요 자리부터 1이다.
        tree[n-i-1+szz] = now;
        now = now * 10 % MOD;
    }
    binit(1);

    while (q--) {
        int l,r,d;
        scanf("%d %d %d", &l, &r, &d);
        l--; r--;
        upd(1, l, r, 0, szz - 1, d);
        printf("%lld\n", tree[1]);
    }
}


// author: rdd6584


Measured memory_bytes: 14188
A = [[int(i) for i in input().split()] for _ in range(3)]
N = int(input())
B = [int(input()) for _ in range(N)]

result = [[0] * 3 for _ in range(3)]

for b in B:
    for i in range(3):
        for j in range(3):
            if b == A[i][j]:
                result[i][j] = 1

flg = False

for i in range(3):
    if sum([result[i][j] for j in range(3)]) == 3:
        flg = True

for j in range(3):
    if sum([result[i][j] for i in range(3)]) == 3:
        flg = True

if sum([result[i][i] for i in range(3)]) == 3:
    flg = True

if sum([result[i][2-i] for i in range(3)]) == 3:
    flg = True

if flg:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
#define hyperspeed ios::sync_with_stdio(false);cin.tie(NULL);
#define ll long long  
#define ull unsigned long long
#define ui unsigned int
#define li long int
#define uli unsigned long int
#define pb push_back
#define ld long double
#define vi vector<int>
#define vvi vector<vector<int>>
#define vli vector<li>
#define vll vector<ll>
#define all(v) v.begin(),v.end()
#define pi pair<int,int>
#define FOR(i,s,n) for(auto i=s;i<n;++i)
#define FORN(i,s,n) for(auto i=s;i<=n;++i)
#define FORR(i,s,n) for(auto i=s;i>=n;--i)
#define FORE(i,a) for(auto i : a)
#define mp make_pair
const int MOD = 1e9+7;

void solve() {
    ll h;
    cin >> h;
    ll cnt = 0;
    while(h>1) {
        h/=2;
        cnt++;
    }
    ll hits = 1;
    ll mul = 1;
    FORN(i,1,cnt) {
        hits = hits + (2 * mul);
        mul*=2;
    }
    cout << hits << endl;
}

int32_t main()
{
    hyperspeed
    int test=1;
    // cin >> test;
    while(test--) {
        solve();
    }
    return 0;
}

//--n1m5


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

int main( )
{
    map<string, int> mp;
    string s[7] = { "SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT" };
    for (int i = 0; i < 7; i++)
        mp[s[i]] = i;
    string ss; cin >> ss;
    int i = mp[ss] + 1; int c = 1;
    while ((s[i++ % 7] != "SUN"))
        c++;
    cout << c << '\n';
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,  x,  y) for(int i = x; i <= y; i ++)
#define ll unsigned long long
#define X first
#define Y second
#define ls rt << 1
#define rs rt << 1 | 1
#define INF 0x3f3f3f3f
#define mod 1000000007
using namespace std;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
int n;
map<int, int> mp;
int main() 
{
	n = read();
	rep(i, 1, n)
	{
		int a = read();
		mp[a] ++;
	}
	long long ans = 0;
	for (auto it = mp.begin(); it != mp.end(); it ++) 
	{
		int a = (*it).second;
		int val = (*it).first;
		if (val > a) ans += a;
		else ans += a - val;
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 4736
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
using namespace std;
using ll = long long;
 
int main(){
  int n;
  cin >> n;
  int x=0;
  x=n/1000;
  if(x*1000==n)
    cout << 0 << endl;
  else
    cout << 1000*(x+1)-n << endl;
}

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

int main() {
    int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int ans;
	ans = a[0];
	for (int i = 0; i < n ; i++) {
		ans = min(ans, a[i]);
	}
	int b;
	b = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] == ans) {
			b = i;
			break;
		}
	}
	cout << b + 1 << endl;
}


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

int isPalindrome(string s)
{
    string t = s;
    reverse(t.begin(), t.end());
    return s == t;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    int l,r,ans;
    while(cin >> l >> r)
    {
        ans = 0;
        for(int i = l; i <= r; i++)
            ans += isPalindrome(to_string(i));
        cout << ans << '\n';
    }
    return 0;
}

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

using namespace std;

int main()
{
    while (true) {
        int n, m, a, b, c, t;
        cin >> n >> m >> a >> b >> c >> t;
        if (n == 0 && m == 0 && a == 0 && b == 0 && c == 0 && t == 0) {
            return 0;
        }
        using Vector = vector<int>;
        Vector v;
        v.reserve(n);
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            v.push_back(x);
        }

        using Matrix = vector<Vector>;
        auto generateMatrix = [](size_t size) {
            return Matrix(size, Vector(size, 0));
        };
        auto binaryMatrixMultiplication = [generateMatrix, m](const Matrix& x,
                                                              int n) {
            auto matrixMultiplication = [generateMatrix, m](const Matrix& a,
                                                            const Matrix& b) {
                const auto n = a.size();
                auto c = generateMatrix(n);
                for (size_t i = 0; i < n; ++i) {
                    for (size_t j = 0; j < n; ++j) {
                        for (size_t k = 0; k < n; ++k) {
                            c[i][j] += a[i][k] * b[k][j];
                        }
                        c[i][j] %= m;
                    }
                }
                return c;
            };
            auto x_ = x;
            auto result = generateMatrix(x.size());
            for (int i = 0; i < x.size(); ++i) {
                result[i][i] = 1;
            }
            while (n != 0) {
                if ((n & 1) != 0) {
                    result = matrixMultiplication(result, x_);
                    n -= 1;
                }
                x_ = matrixMultiplication(x_, x_);
                n /= 2;
            }
            return result;
        };
        auto multiplyMatrixVector = [m](const Matrix& matrix, const Vector& v) {
            Vector result(v.size(), 0);
            for (int i = 0; i < v.size(); ++i) {
                for (int j = 0; j < v.size(); ++j) {
                    result[i] += matrix[i][j] * v[j];
                }
                for (int j = 0; j < v.size(); ++j) {
                    result[i] %= m;
                }
            }
            return result;
        };
        auto matrix = generateMatrix(v.size());
        for (int i = 0; i < v.size(); ++i) {
            if (i - 1 >= 0) {
                matrix[i][i - 1] = a;
            }
            matrix[i][i + 0] = b;
            if (i + 1 < v.size()) {
                matrix[i][i + 1] = c;
            }
        }
        matrix = binaryMatrixMultiplication(matrix, t);
        auto r = multiplyMatrixVector(matrix, v);
        for (int i = 0; i < v.size(); ++i) {
            if (i != 0) {
                cout << ' ';
            }
            cout << r[i];
        }
        cout << endl;
    }
}


Measured memory_bytes: 3088
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

namespace AtCoder124
{
    class Program
    {
        public static void Main(string[] args)
        {
            string[] s = Console.ReadLine().Split(' ');
            int N = int.Parse(s[0]);
            int K = int.Parse(s[1]);
            string S = Console.ReadLine();
            int[] resblacks = new int[100001];
            int[] black = new int[100001];
            int[] white = new int[100001];
            int blackcount = 0;
            int whitecount = 0;
            int startidx = 0;
            int finishidx = 0;
            char bef = S[0];
            if (S[0] == '0')
            {
                black[blackcount] = 0;
                resblacks[blackcount] = 0;
                blackcount++;
            }
            for (int i = 0; i < N; i++)
            {
                if (S[i] == bef)
                {
                    finishidx = i;
                }
                else
                {
                    if (bef == '0')
                    {
                        white[whitecount] = finishidx - startidx + 1;
                        whitecount++;
                    }
                    else
                    {
                        black[blackcount] = finishidx - startidx + 1;
                        resblacks[blackcount] = finishidx - startidx + 1;
                        blackcount++;
                    }
                    startidx = i;
                    finishidx = i;
                    bef = S[i];
                }
            }
            if (bef == '0')
            {
                white[whitecount] = finishidx - startidx + 1;
                whitecount++;
                black[blackcount] = 0;
                resblacks[blackcount] = 0;
                blackcount++;
            }
            else
            {
                black[blackcount] = finishidx - startidx + 1;
                resblacks[blackcount] = finishidx - startidx + 1;
                blackcount++;
            }
            int res = black[0];
            for (int i = 0; i < Math.Min(whitecount, K); i++) res += black[i + 1] + white[i];
            int resbef = res;
            int firsti = 0;
            for (int i = K; i < blackcount - 1; i++)
            {
                int restemp = resbef - black[firsti] - white[firsti] + white[i] + black[i + 1];
                firsti++;
                resbef = restemp;
                res = Math.Max(res, restemp);
            }
            Console.WriteLine(res);
        }
    }
}

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

long long int gcd(long long int a, long long int b)
{
  if (b == 0)
    return a;
  return gcd(b, a%b);
}

int main()
{
  int a1, m1, a2, m2, a3, m3;
  while (cin >> a1 >> m1 >> a2 >> m2 >> a3 >> m3) {
    if ((a1|m1|a2|m2|a3|m3) == 0)
      break;

    int x = 1, y = 1, z = 1;
    long long cntX = 0, cntY = 0, cntZ = 0;

    do {
      ++cntX;
      x = (a1 * x) % m1;
    } while (x != 1);

    do {
      ++cntY;
      y = (a2 * y) % m2;
    } while (y != 1);

    do {
      ++cntZ;
      z = (a3 * z) % m3;
    } while (z != 1);

    long long int ans = cntX / gcd(cntX, cntY) * cntY;
    ans = ans / gcd(ans, cntZ) * cntZ;
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 0
#n = int(input())
#L = list(map(int, input().split()))
import math
import sys
import heapq
import fractions
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = 0

for i in range(N):
    if B[i]>A[i]:
        if B[i] >= A[i+1]+A[i]:
            ans += A[i]+A[i+1]
            A[i+1] = 0
        else:
            A[i+1] -= B[i]-A[i]
            ans += B[i]
    else:
        ans += B[i]

print(ans)

Measured memory_bytes: 20748
#include <iostream>
#include <stdio.h>
using namespace std;
int calc1(int a,char op,int b){
	if(op=='+'){
		return a + b;
	}else if(op=='-'){
		return a - b;
	}else if(op=='*'){
		return a * b;
	}else{
		return a / b;
	}
}

int main()
{
	int a,b;
	char op;
	cin>>a;
	cin>>op;
	cin>>b;
	while(op != '?'){
		cout<<calc1(a,op,b)<<endl;
		cin>>a;
		cin>>op;
		cin>>b;
	}
	return 0;
}

Measured memory_bytes: 3112
#include<iostream>
#include<algorithm>
using namespace std;
int  *a_heap;
int main(){
    int n1,n2;
    int sum = 0;
    cin >> n1 >> n2;
    a_heap = new int[n1];
    for(int i = 0; i < n1;i++){
        int n;
        cin >> n;
        a_heap[i] = n;
    }
    sort(a_heap,a_heap+n1);
    for(int i = 0; i < n2;i++){
        sum += a_heap[i];
    }
    cout << sum;
}

Measured memory_bytes: 3636
#include<iostream>
using namespace std;
int main() {
  
  long k, x;
  cin>>k>>x;
  
  long left = max(-1000000L, x - k + 1L ), right = min(1000000L, x + k - 1L) ;
  
  for(int i = left; i<=right; i++)
    cout<<i<<" ";
  
  return 0;
}
  


Measured memory_bytes: 256
#include<stdio.h>
#define pmodml(RHS,LHS,MODN)  (1ll * (RHS) * (LHS) % (MODN))
#define pmodadd(RHS,LHS,MODN) (((long long)(RHS) + (long long)(LHS)) % (MODN))

static inline long pmodpow(long num,long ind,long modn){
    unsigned long cnt = ind;
    long res = 1;
    while (cnt){
        if(cnt & 1ul)res = pmodml(res,num,modn);
        num = pmodml(num,num,modn);
        cnt >>= 1;
    }
    return res;
}

static inline long long nck2(long n){
    return 1ll * n * (n-1) / 2;
}

int main(void){
    register int i;
    int n,p;
    scanf("%d %d",&n,&p);
    char str[n];
    scanf("%s",str);

    if(p == 2 || p == 5){
        long ans = 0;
        for(i = 0;i < n;i++)if(!((str[i] - '0') % p))ans += i + 1;
        printf("%ld",ans);
    }else{
        unsigned long long ans = 0;
        int nums[n];
        for(i = 0;i < n;i++)nums[i] = str[n-i-1] - '0';
        int surp[n+1];
        surp[0] = 0;
        for(i =0;i < n;i++)surp[i+1] = pmodadd(surp[i],pmodml(nums[i],pmodpow(10,i,p),p),p);
        int sk[p];
        for(i = 0;i < p;i++)sk[i] = 0;
        for(i = 0;i <= n;i++)sk[surp[i]]++;
        for(i = 0;i < p;i++)ans += nck2(sk[i]);
        printf("%lld",ans);
    }
}

Measured memory_bytes: 1920
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T>inline bool chmax(T& a,T b) { if(a < b) { a = b; return true;
  }return false;}
template<class T>inline bool chmin(T& a,T b) { if(a > b) { a = b; return true;
  }return false;}

const ll INF = 1e18;
const int MX = 2005;

double dp[3010][3010];

int n;
vector<double> p;

int main() {
  cin >> n;
  p.resize(n);
  rep(i,n) cin >> p[i];
  
  dp[0][0] = 1.0;
  rep(i,n){
    rep(j,i+1){
      dp[i+1][j+1] += p[i] * dp[i][j];
      dp[i+1][j] += (1.0 - p[i]) * dp[i][j];
    }
  }
  double res = 0.0;
  for(int i = (n+1)/2 ; i <= n ; i++){
    res += dp[n][i];
  }
  cout << fixed << setprecision(10) << res << endl;
}

Measured memory_bytes: 69120
#include <iostream>
using namespace std;
int main(){
    int a,b,c,x;
    cin >> a >> b >> c >> x;
    int cnt = 0;
    for(int i = 0; i < a+1; i++){
        for(int j = 0; j < b+1; j++){
            for(int k = 0; k <c+1;++k){
                int sum = 500*i+100*j+50*k;
                if(sum == x) cnt++;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 3636
N, Y = map(int, input().split())

def solve() :
    for i in range(N + 1) :
        for j in range(N + 1 - i) :
            k = N - i - j
            if i * 10000 + j * 5000 + k * 1000 == Y :
                return (i, j, k)
    return (-1, -1, -1)
    
print(*solve())

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

using ll = long long;
using P = pair<int, int>;

const int INF = 1e9;
const int MOD = 1e9 + 7;
const int MAX = 2e5;

int N, Q;
string s;
char t[MAX+10], d[MAX+10];

int simulate(int idx) {
  for (int i = 0; i < Q; i++) {
    if (t[i] != s[idx]) continue;

    (d[i] == 'L' ? idx-- : idx++);
    if (idx < 0 || idx >= N) break;
  }

  return idx;
}

bool isLeftFall(int idx) {
  return simulate(idx) < 0;
}

bool isRightFall(int idx) {
  return simulate(idx) >= N;
}

int main() {
  cin >> N >> Q >> s;
  for (int i = 0; i < Q; i++) cin >> t[i] >> d[i];

  // 二分探索で左の境界を探す
  int l = 0, r = N;
  while (r - l > 1) {
    int mid = (l + r) / 2;

    if (isLeftFall(mid)) {
      l = mid;
    } else {
      r = mid;
    }
  }

  // 二分探索で右の境界を探す
  int l2 = 0, r2 = N;
  while (r2 - l2 > 1) {
    int mid = (l2 + r2) / 2;

    if (isRightFall(mid)) {
      r2 = mid;
    } else {
      l2 = mid;
    }
  }

  cout << max(l2 - r + 1, 0) << endl;
  return 0;
}


Measured memory_bytes: 900
#include <bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using gpp_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename L> using gpp_map = tree<T, L, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using gpp_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define Return(ans) { cout << (ans) << endl; return 0; }
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }
 
using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;
 
//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};
 
const int mod = 1000000007;
//const int mod = 998244353;
//#define Add(x, y) x = (x + (y)) % mod
//#define Mult(x, y) x = (x * (y)) % mod

#include <bits/stdc++.h>
using namespace std;
signed main(){
    int N; cin>>N;
    string S;
    vec Count (26,INF);
    REP(i,N){
        cin>>S;
      vec temp (26,0);
        REP(j,S.size()){
            temp[S[j]-'a']++;
        }
      REP(i,26) Count[i]=min(temp[i],Count[i]);
    }
  string ans;
  REP(i,26){
    while(Count[i]>0){
      ans.push_back(i+'a');
      Count[i]--;
    }
  }
  Out(ans);
}


Measured memory_bytes: 256
#!usr/bin/env python3
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
def LIR(n): return [LI() for i in range(n)]
mod = 1000000007

#A
"""
a,b,c = LI()
s = a+b+c
s /= 2
ans = (s*(s-a)*(s-b)*(s-c))**(1/2)
print(int(ans))
"""

#B
s = int(input())
m = 1
lis = [True for i in range(1000001)]

while lis[s]:
    lis[s] = False
    if s % 2 == 1:
        s = 3*s+1
    else:
        s //= 2
    m += 1
print(m)
#C

#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T


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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	vector<int>h(n); for(auto&&i:h)cin>>i;
	vector<int64_t>dp(n); dp.at(1)=abs(h.at(0)-h.at(1));
	for(int i=2;i<n;++i){
		dp.at(i)=min(dp.at(i-2)+abs(h.at(i)-h.at(i-2)),dp.at(i-1)+abs(h.at(i)-h.at(i-1)));
	}
	cout<<dp.back()<<"\n"s;
}

Measured memory_bytes: 1408
using System;
using System.Linq;
using System.Collections.Generic;

namespace MyApp
{
    class Program
    {
        static void Main(string[] args)
        {
            long n = int.Parse(Console.ReadLine());
            string[] s = Console.ReadLine().Split(' ');
            int[] a = new int[n];

            long ans = 0;
            long sum = 0;
            long xor = 0;
            int r = 0;

            for (int i = 0; i < n; i++)
            {
                a[i] = int.Parse(s[i]);
            }

            for (int l = 0; l < n; l++)
            {
                while (r < n && ((sum + a[r]) == (xor ^ a[r])))
                {
                    sum += a[r];
                    xor ^= a[r];
                    r++;
                }
                ans += r - l;
                sum -= a[l];
                xor ^= a[l];
            }
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 32604
class Queue():

    def __init__(self, max_size):
        self.head = 0
        self.tail = 0
        self.max = max_size + 1
        self.q = [None for _ in range(self.max)]

    def is_empty(self):
        return self.head == self.tail

    def is_full(self):
        return self.head == (self.tail + 1) % self.max

    def enqueue(self, x):
        if self.is_full():
            print("Error: Overflow")
        self.q[self.tail] = x
        if self.tail + 1 == self.max:
            self.tail = 0
        else:
            self.tail += 1

    def dequeue(self):
        if self.is_empty():
            print("Error: Underflow")

        x = self.q[self.head]
        if self.head + 1 == self.max:
            self.head = 0
        else:
            self.head += 1

        return x


n, q = [int(x) for x in input().split()]
names = Queue(n)
time = Queue(n)

for _ in range(n):
    data = input().split()
    names.enqueue(data[0])
    time.enqueue(int(data[1]))

t = 0
while not names.is_empty():
    process = names.dequeue()
    process_time = time.dequeue()

    if process_time > q:
        names.enqueue(process)
        time.enqueue(process_time - q)
        t += q
    else:
        t += process_time
        print(process, t)



Measured memory_bytes: 10492
#include<stdio.h>
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <map>
#include <functional>
#include <stdio.h>
#include <array>
#include <algorithm>
#include <string>
#include <string.h>
#include <assert.h>
#include <stdio.h>
#include <queue>
#include<iomanip>
#include<bitset>
#include<stack>
#include<set>
#include<limits>
#include <complex>
#include<cstdlib>
using namespace std;

bool isso(long long int a) {
	if (a == 1||a==0)return false;
	for (long long int i = 2; i*i <= a; ++i) {
		if ((a%i)) {
		}
		else {
			return false;
		}
	}
	return true;
}

struct edge {
	int from;
	int to;
	long double time;
};
struct aa {
	int now;
	long double time;
	bitset<8>tickets;
};

class Compare {
public:
	//keiroが昇順に並ぶ
	bool operator()(const aa&l, const aa&r) {
		return l.time> r.time;
	}
};

long long int powint(long long int a, long long int b) {
	assert(b >= 0);
	if (b == 0)return 1;
	if (b == 1)return a;
	long long int ans = 1;
	long long int aa = powint(a, b / 2);
	ans *= aa*aa;
	if (b % 2)ans *= a;
	return ans;
}

int fizznum[15] = { 0,0,1,1,1,2,2,2,3,3,3,4,4,4,4 };
int buzznum[15] = { 0,0,0,0,1,1,1,1,1,2,2,2,2,2,2 };
int fibunum[15] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 };
long long int memo[18];

string makefb(long long int num) {
	string st;
	if (!(num % 3)) {
		st+=("Fizz");
	}
	if (!(num % 5)) {
		st+=("Buzz");
	}
	if (st.size() == 0) {
		st = to_string(num);
	}
	return st;
}

string getans(long long int rest, long long int from) {
	string ans;
	long long int now(from);
	while (1) {
		string ast(makefb(now));
		if (rest <= ast.size()) {
			ans+=(ast.substr(rest, int(ast.size() - rest)));
			rest = 0;
		}
		else {
			rest -= ast.size();
		}
		now++;
		if (ans.size() >= 20) {
			return ans.substr(0, 20);
		}
	}
}
int main() {
	memo[0] = 0;
	memo[1] = 21;
	long long int prefizznum = 3;
	long long int prebuzznum = 1;
	long long int prefibunum = 0;
	for (int i = 2; i <= 17; ++i) {

		long long int fiz = (powint(10, i) - 1) / 15 * 4;
		fiz += fizznum[(powint(10, i) - 1) % 15 - 1] - prefizznum;

		long long int buz = (powint(10, i) - 1) / 15 * 2;
		buz += buzznum[(powint(10, i) - 1) % 15-1]-prebuzznum;

		long long int fibu = (powint(10, i) - 1) / 15;
		fibu += fibunum[(powint(10, i) - 1) % 15 - 1] - prefibunum;

		memo[i] = memo[i - 1] + buz * 4 + fiz * 4 + fibu * 8 + i*(powint(10, i - 1) * 9 - buz - fiz - fibu);

		prefizznum += fiz;
		prebuzznum += buz;
		prefibunum += fibu;
	}

	long long int s; cin >> s; s--;
	int keta;
	for (int i = 1; i < 18; ++i) {
		if (s < memo[i]) {
			keta = i;
			break;
		}
	}
	if (s < memo[keta - 1] + (20 + keta * 4)) {
		long long int rest = s - memo[keta - 1];
		string ans(getans(rest, powint(10, keta-1)));
		cout << ans << endl;
	}
	else {
		long long int now = powint(10, keta - 1) + 6;
		long long int rest = s - memo[keta - 1] - 16 - keta * 3;
		long long int jump = rest / (32 + keta * 8);
		now += jump * 15;
		rest -= jump*(32 + keta * 8);
		string ans(getans(rest, now));
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3272