akhauriyash/Code-Regression huggingface dataset:
def main():
    a, b, k = map(int, input().split())
    from fractions import gcd
    g = gcd(a, b)

    def yakusuu(a):
        yakusuu = set()
        for i in range(1, int(a**0.5)+1):
            if a % i == 0:
                yakusuu.add(i)
                yakusuu.add(a//i)
        yakusuu = sorted(list(yakusuu))
        return yakusuu

    print(yakusuu(g)[::-1][k-1])


main()


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

#define HEAP priority_queue
#define rep(i, n) for(int i = 0, _end_ = (n); i < _end_; ++i)
#define per(i, n) for(int i = (n) - 1; i >= 0 ; --i)
#define forn(i, l, r) for(int i = (l), _end_ = (r); i <= _end_; ++i)
#define nrof(i, r, l) for(int i = (r), _end_ = (l); i >= _end_; --i)
#define FOR(a, b) for(auto (a): (b))
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define X first
#define Y second
#define eps 1e-6
#define pi 3.1415926535897932384626433832795
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(), x.end()

using namespace std;

typedef long long LL;
typedef double flt;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef pair<int,int> pii;
typedef pair<int,LL> pil;
typedef pair<LL,int> pli;
typedef pair<LL,LL> pll;
typedef vector<pil> vil;
typedef vector<pii> vii;
typedef vector<pli> vli;
typedef vector<pll> vll;

const int iinf = 1e9 + 7;
const int oo = 0x3f3f3f3f;
const LL linf = 1ll << 60;
const flt dinf = 1e60;

template <typename T> inline void scf(T &x) {
	bool f = 0;
	x = 0;
	char c = getchar();
	while(c != '-' && (c < '0' || c > '9')) c = getchar();
	if(c == '-') f = 1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	if(f) x = -x;
	return;
}

template <typename T1, typename T2> void scf(T1 &x, T2 &y) {
	scf(x);
	return scf(y);
}

template <typename T1, typename T2, typename T3> void scf(T1 &x, T2 &y, T3 &z) {
	scf(x);
	scf(y);
	return scf(z);
}

template <typename T1, typename T2, typename T3, typename T4> void scf(T1 &x, T2 &y, T3 &z, T4 &w) {
	scf(x);
	scf(y);
	scf(z);
	return scf(w);
}

inline char mygetchar() {
	char c = getchar();
	while(c == ' ' || c == '\n') c = getchar();
	return c;
}

template <typename T> inline bool chkmax(T &x, const T &y) {
	return y > x ? x = y, 1 : 0;
}

template <typename T> inline bool chkmin(T &x, const T &y) {
	return y < x ? x = y, 1 : 0;
}

#ifdef King_George
#define DEBUG
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif

//---------------------------------------------------------head----------------------------------------------------

const int maxn = 1e5 + 10;

int n;
vi g[maxn];
unsigned int dp[maxn];

void dfs(int u = 1, int par = 0) {
	unsigned int s1 = 0, s2 = 0, &s = dp[u];
	for (int v: g[u]) {
		if(v != par) {
			dfs(v, u);
			s2 |= (dp[v] & s1);
			s1 |= dp[v];
		}
	}
	s = 1;
	while(s <= s2) {
		s <<= 1;
	}
	while(s & s1) {
		s <<= 1;
	}
	s = ((s > 1) ? (s1 & ~(s - 1)) : s1) | s;
	return;
}

int main() {
	scf(n);
	rep (i, n - 1) {
		int u, v;
		scf(u, v);
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs();
	unsigned int s = 1;
	int ans = -1;
	while(s <= dp[1]) {
		s <<= 1;
		++ans;
	}
	printf("%d\n", ans);
	return 0;
}

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

using namespace std;

int main(){
    vector<string> v;
    int now = 0;
    string s, s1, s2;
    cin >> s >> s1 >> s2;
    v.push_back(s);
    v.push_back(s1);
    v.push_back(s2);
    while(1){
        if(!now){
            if(s[0] == 'b')now = 1;
            else if(s[0] == 'c')now = 2;
            if(s.size() == 1 && s[0] == 'a'){
                cout << "A";
                return 0;
            }
            if(s.empty()){
                cout << "A";
                return 0;
            }
            s.erase(s.begin());
        }else if(now == 1){
            if(s1[0] == 'a')now = 0;
            else if(s1[0] == 'c')now = 2;

            if(s1.size() == 1 && s1[0] == 'b'){
                cout << "B";
                return 0;
            }else if(s1.empty()){
                cout << "B";
                return 0;
            }
            s1.erase(s1.begin());
        }else if(now == 2){
            if(s2[0] == 'a')now = 0;
            else if(s2[0] == 'b')now = 1;
            if(s2.size() == 1 && s2[0] == 'c'){
                cout << "C";
                return 0;
            }else if(s2.empty()){
                cout << "C";
                return 0;
            }
            s2.erase(s2.begin());
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
    int h , w;
    int i,j;
    
    while(1){
    scanf("%d %d",&h,&w);
     if(h==0 && w==0) break;
     else
        for(i=0;i<h;i++){
            for(j=1;j<=w;j++){ printf("#"); }
            printf("\n");
        }
            printf("\n");
    }
return 0;
}


Measured memory_bytes: 2116
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main(){
	LL n, k, MOD;
	cin >> n >> k >> MOD;
	LL numways[n+1][n+1];
	for(int i = 0; i <= n; i++){
		LL ways[i+1];
		for(int j = 0; j <= i; j++){
			ways[j] = 0;
		}
		ways[0] = 1;
		LL maxa = n-i;
		for(int a = 0; a <= maxa; a++){
			for(int j = 1; j <= i; j++){
				ways[j] += ways[j-1];
				ways[j] %= MOD;
			}
			numways[i][i+a] = ways[i];
			for(int j = 0; j <= i; j++){
				ways[j] *= (j + 1);
				ways[j] %= MOD;
			}
		}
		for(int j = 0; j < i; j++){
			numways[i][j] = 0;
		}
	}
	vector<LL> dp(n+1, 0);
	dp[0] = 1;
	for(int i = 1; i <= k; i++){
		vector<LL> newdp(n+1, 0);
		for(int j = 0; j <= n; j++){
			for(int r = 0; r <= n; r++){
				newdp[r] += dp[j] * numways[j][r];
				newdp[r] %= MOD;
			}
		}
		dp = newdp;
	}
	cout << dp[n] << endl;
}


Measured memory_bytes: 896
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream> 
#include<map>
#include <iomanip>
#include <time.h>
#include <random>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
using namespace std;
#define LONG_INF 10000000000000000
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)
int main() {
#define int long long
	long long n, m;
	cin >> n >> m;
	vector<long long> a, b;
	REP(i, n) {
		long long tmp = 0;
		cin >> tmp;
		a.push_back(tmp);
	}
	REP(i, m) {
		long long tmp;
		cin >> tmp;
		b.push_back(tmp);
	}
	long long hogee = 0;
	for (int i = 0;i < n;++i) {
		hogee += a[i] * (i + 1);
		hogee %= MAX_MOD;
		if (hogee < 0) {
			hogee += MAX_MOD * ((-1 * hogee) / MAX_MOD + 1);
			hogee %= MAX_MOD;
		}
	}
	long long yoko_finality = hogee;
	for (int i = 0;i < n;++i) {
		yoko_finality -= (n - i) * a[i];
		yoko_finality %= MAX_MOD;
		if (yoko_finality < 0) {
			yoko_finality += MAX_MOD * ((-1 * yoko_finality) / MAX_MOD + 1);
			yoko_finality %= MAX_MOD;
		}
	}
	hogee = 0;
	for (int i = 0;i < m;++i) {
		hogee += b[i] * (i + 1);
		hogee %= MAX_MOD;
		if (hogee < 0) {
			hogee += MAX_MOD * ((-1 * hogee) / MAX_MOD + 1);
			hogee %= MAX_MOD;
		}
	}
	long long tate_finality = hogee;
	for (int i = 0;i < m;++i) {
		tate_finality -= (m - i) * b[i];
		tate_finality %= MAX_MOD;
		if (tate_finality < 0) {
			tate_finality += MAX_MOD * ((-1 * tate_finality) / MAX_MOD + 1);
			tate_finality %= MAX_MOD;
		}
	}
	long long ans = tate_finality * yoko_finality;
	ans %= MAX_MOD;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2548
#include <stdio.h>
     
    int main(){
    	int x,y;
    	scanf("%d %d",&x,&y);
    	int a,f=0;
    	for(a=0;a<=x;a++){
    		int z=x+a;
    		if(y==2*z){
    			f++;
    			break;
    		}
    	}
    	if(f>0) printf("Yes\n");
    	else       printf("No\n");
    	return 0;
    }

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

int main() {
	int N;
	cin >> N;
	vector<double> v(N);
	for (double& i : v) cin >> i;
	sort(v.begin(), v.end());
	for (int i = 1; i < N; ++i) v[i] = (v[i - 1] + v[i]) / 2.0;
	cout << v.back();
}

Measured memory_bytes: 256
m,d=map(int,input().split())
flag=0
for i in range(1,m+1):
 for j in range(1,d+1):
  if j > 10:
   if int(str(j)[0]) >= 2 and int(str(j)[1]) >= 2 and int(str(j)[0])*int(str(j)[1])==i:
    flag+=1
print(flag)

Measured memory_bytes: 3060
lis = []
for i in range(5):
    lis.append(int(input()))
k = int(input())

flag_disconnectable = False
for i in range(5):
    for j in range(5):
        if i == j: continue
        if (lis[j]-lis[i]) > k:
            flag_disconnectable = True
            break

if flag_disconnectable:
    print(":(")
else:
    print("Yay!")

Measured memory_bytes: 3060
from collections import Counter


def solve(n, arr):
    if arr[0] != 0:
        return 0

    c = Counter(arr)

    if c[0] != 1:
        return 0

    for i in range(max(c) + 1):
        if i not in c:
            return 0

    c = list(c.items())
    c.sort()

    prev = 1
    ans = 1
    mod = 998244353

    for _, i in c[1:]:
        ans *= prev**i % mod
        ans %= mod
        prev = i

    return ans


n = int(input())
arr = list(map(int, input().split()))

print(solve(n, arr))

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

int main() {
  int64_t H;
  cin >> H;
  
  int n = 0;

  rep(i,100){
    if(H == 1){
      n++;
      break;
    }
    else if(H % 2 == 0){
      H /= 2;
      n++;
    }
    else{
      H = (H-1)/2;
      n++;
    }
  }
  
  int64_t ans = 1;
  
  rep(i,n){
    ans*=2;
  }
  
  cout << ans - 1 << endl;
  
    
    
}

Measured memory_bytes: 256
import sys

N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
A.sort()
A.reverse()

num = [0,2,5,5,4,5,6,3,7,6]

A_num = [(num[a], -a) for a in A]
A_num.sort()

min_A = -A_num[0][1]
min_num = A_num[0][0]
keta_max = N//min_num

DP = [-1] * (N+1)
DP[0] = 0

for i in range(N+1):
    for j in range(M):
        n = num[A[j]]
        if i - n >= 0 and DP[i-n] != -1:
            DP[i] = max(DP[i], DP[i-n] * 10 + A[j])

print(DP[N])

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

int main() {
  int a = 0,b = 0,c = 0;
  string s;
  cin >> s;
  for(int i = 0; i < s.size(); i++){
    if(s.at(i) == 'a'){
      a++;
    }
    else if(s.at(i) == 'b'){
      b++;
    }
    else{
      c++;
    }
  }
  if((a == 1 && b == 1) && c == 1){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using pl = pair<ll, ll>;
const ll INF = ll(1e18);
const ll mod = ll(1e9+7);
const double pi = acos(-1);
#define rep0(i,n) for(ll (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(ll (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(ll (i) = 1; (i) <= (n); ++(i))
#define rrep1(i,n) for(ll (i) = (n); (i) >= 1; --(i))
#define nfor(i,a,b) for(ll (i) = (a); (i) < (b); ++(i))
#define pf(x) cout << (x) << endl
#define all(x) (x).begin(),(x).end()
#define yes pf("Yes")
#define no pf("No")
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int dx[8]={1,0,-1,0,1,1,-1,-1};
const int dy[8]={0,1,0,-1,1,-1,1,-1};

ll gcd(ll a,ll b){
    if(a < b)swap(a, b);
    if(b == 0) return a;
    return gcd(b,a%b);
}

ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return a / g * b;
}

ll factorial(ll n){
    ll ans = 1;
    rep1(i, n){
        ans *= i;
        ans %= mod;
    }
    return ans;
}

ll power(ll a, ll b){
    ll ans = 1;
    a %= mod;
    while(b) {
        if(b & 1LL) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans % mod;
}

//modの値の確認をすること
int main(){
    ll n,ans = 0;
    cin >> n;
    vl dp(n + 1,0);
    rep0(i, n){
        ll a;
        cin >> a;
        dp[a] = dp[a - 1] + 1;
        chmax(ans, dp[a]);
    }
    pf(n - ans);
    return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<algorithm>
#define NMAX 105
#define WMAX 10005
#define DIAGONAL 1
#define TOP 0

using namespace std;

struct Item {
  int value, weight;
};

int N, W;
Item items[NMAX + 1];
int C[NMAX + 1][WMAX + 1], G[NMAX + 1][WMAX + 1];

void compute(int &maxValue, vector<int> &selection) {
  for ( int w = 0; w <= W; w++ ) {
    C[0][w] = 0;
    G[0][w] = DIAGONAL;
  }

  for ( int i = 1; i <= N; i++ ) C[i][0] = 0;

  for ( int i = 1; i <= N; i++ )
    for ( int w = 1; w <= W; w++ ) {
      C[i][w] = C[i - 1][w];
      G[i][w] = TOP;
      if ( items[i].weight > w ) continue;
      if ( items[i].value + C[i - 1][w - items[i].weight] > C[i - 1][w] ) {
        C[i][w] = items[i].value + C[i - 1][w - items[i].weight];
        G[i][w] = DIAGONAL;
      }
    }

  maxValue = C[N][W];
  selection.clear();
  for ( int i = N, w = W; i >= 1; i-- )
    if ( G[i][w] == DIAGONAL ) {
      selection.push_back(i);
      w -= items[i].weight;
    }

  reverse(selection.begin(), selection.end());
}

void input() {
  cin >> N >> W;
  for ( int i = 1; i <= N; i++ )
    cin >> items[i].value >> items[i].weight;
}

int main() {
  int maxValue;
  vector<int> selection;
  input();
  compute(maxValue, selection);

  cout << maxValue << endl;

  return 0;
}


Measured memory_bytes: 10928
from collections import defaultdict
n, c = map(int, input().split())

tp = defaultdict(list)
i_max = 0
for _ in range(n):
    s, t, c = map(int, input().split())
    tp[c].append([s, t])
    i_max = max(i_max, t+1)

for c in tp:
    tp[c].sort()
    x = [tp[c][0]]
    for i in range(1, len(tp[c])):
        if x[-1][1] == tp[c][i][0]:
            x[-1][1] = tp[c][i][1]
        else:
            x.append(tp[c][i])
    tp[c] = x

r = [0] * (i_max + 5)

for c in tp:
    for s, t in tp[c]:
        r[s] += 1
        r[t+1] -= 1

ans = 0
for i in range(1, i_max+1):
    r[i] = r[i-1] + r[i]
    ans = max(ans, r[i])

print(ans)


Measured memory_bytes: 21348
#include<stdio.h>
#define MAX 500000
#define INFTY  2000000000

int L[MAX/2+2], R[MAX/2+2];
int cnt;

void merge(int A[], int left, int mid, int right){
  int i, j, k, n1, n2;

  n1 = mid - left;
  n2 = right - mid;
  for( i = 0 ; i < n1 ; i++ ){
    L[i] = A[left+i];
  }
  for( i = 0 ; i < n2 ; i++ ){
    R[i] = A[mid+i];
  }
  L[n1] = R[n2] = INFTY;
  i = j = 0;
  for( k = left ; k < right ; k++ ){
    cnt++;
    if( L[i] <= R[j] ){
      A[k] = L[i];
      i = i +1;
    }
    else {
      A[k] = R[j];
      j = j + 1;
    }
  }
}

void mergeSort(int A[], int left, int right){
  int mid;
  if( left + 1 < right ){
    mid = ( left + right ) / 2;
    mergeSort(A, left, mid);
    mergeSort(A, mid, right);
    merge(A, left, mid, right);
  }
}

int main(){
  int A[MAX], n, i;
  cnt = 0;

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

  mergeSort(A, 0, n);

  for( i = 0 ; i < n ; i++ ){
    if( i ) printf(" ");
    printf("%d", A[i]);
  }
  printf("\n");
  printf("%d\n", cnt);
  return 0;
}



Measured memory_bytes: 5596
//A.cpp
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const ll mod=1e9+7;

int main(){
  ll a,b;
  cin >> a >> b;
  if((a+b)%2 == 0){
    printf("%lld\n", (a+b)/2);
    return 0;
  }else{
    printf("IMPOSSIBLE\n");
    return 0;
  }
  return 0;
}


Measured memory_bytes: 256
x0,y0=map(int,input().split())
x1,y1=map(int,input().split())
x2,y2=map(int,input().split())
def make_dist(i,j,k,l):
    return ((i-k)**2+(j-l)**2)**0.5
a=y1-y2
b=x2-x1
c=x1*y2-y1*x2
d12=make_dist(x1,y1,x2,y2)
d01=make_dist(x0,y0,x1,y1)
d02=make_dist(x0,y0,x2,y2)
S_double=d12*abs(a*x0+b*y0+c)/(make_dist(a,b,0,0))
r=S_double/(d01+d02+d12)
d=max(d01,d02,d12)
ans=d*r/(2*r+d)
print(ans)

Measured memory_bytes: 3188
object Main {
  def main(args:Array[String]) = {
   // val seq = readLine.split("")
    val input=io.Source.stdin.getLines().mkString("\n")
    println(solve(input).trim())
  }


def solve(aaa:String): String={
  val seq = aaa.split("").takeRight(4)
  var ret ="Good"
  for(i<- 0 to 2) {
    if (seq(i) == seq(i+1)){
      ret = "Bad"
    }
  }
  ret
}
}


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

int main(){
  int n;
  cin >> n;
  vector<pair<string,pair<int,int>>> s(n);
  for(int i = 0; i < n; i++){
    string a;
    int b;
    cin >> a >> b;
    s[i].first = a;
    s[i].second.first = -b;
    s[i].second.second = i+1;
  }
  sort(s.begin(),s.end());
  for(int i = 0; i < n; i++){
    cout << s[i].second.second << endl;
  }
}

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

using namespace std;
typedef long long ll;

int main() {
    ll n;
    cin >> n;
    ll a = 1;
    ll thres = 1e18;
    for (ll i = 0; i < n; i++) {
        ll ta;
        cin >> ta;
        if (ta == 0) {
            a = 0;
            break;
        }
        if (a == -1) {
            continue;
        }
        if (a > thres / ta) {
            a = -1;
            continue;
        }
        a *= ta;
    }
    ll ans = a;
    cout << ans << endl;
    return 0;
}


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

int main(){
int a,b,c,d;
  cin>>a>>b>>c>>d;
  if(b<c||d<a)
    cout<<0<<endl;
  else if(c<=a){
    if(d<b)
      cout<<d-a<<endl;
    else
      cout<<b-a<<endl;
  }
  else{
    if(b<d)
      cout<<b-c<<endl;
  else
      cout<<d-c<<endl;
  }
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        int h,w,i,j;
        while(true){
        h = s.nextInt();
        w = s.nextInt();
        if(h==0&&w==0)break;
        for(i=1;i<=h;i++){
            for(j=1;j<=w;j++){
                if(i==1||i==h||j==1||j==w)System.out.print("#");
                else System.out.print(".");
            }
            System.out.println();
        }
        System.out.println();
    }
    }
}


Measured memory_bytes: 32660
/* ex 9_1
   hangan2020 */

#include <stdio.h>
#include <stdlib.h>
#define SIZE 11

typedef struct stack{
   int size;
   int count;
   char data[SIZE];
   char *top;
} stack;

void initialize_stack(stack *stk){
   stk->count = 0;
   stk->size = SIZE;
   stk->top = &(stk->data[SIZE]);
}

void push(stack *stk, char elem){
   if(stk->count >= stk->size){
      fprintf(stderr, "Error: Stack overflow\n");
      exit(1);
   }
   else{
      stk->top--;
      *(stk->top) = elem;
      stk->count++;
   }
}

void pop(stack *stk){
   //char latest;
   if(stk->count <= 0){
      fprintf(stderr, "Error: Stack underflow\n");
      exit(1);
   }
   else{
      //latest = *(stk->top);
      stk->top++;
      stk->count--;
   }
}

void print_stk(stack *stk){
   char *p;
   p = stk->top;
   for(int i = stk->count; i > 0; i--){
      printf("%c", p[i-1]);
   }
   printf("\n");
}

int main(void){
   stack stk;
   char string[SIZE];
   int i = 0;

   initialize_stack(&stk);
   scanf("%s", &string);
   
   while(string[i] != '\0'){
      if(string[i] == 'B'){
         if(stk.count != 0){
            pop(&stk);
         }
      }else{
         push(&stk, string[i]);
      }
      i++;
   }

   print_stk(&stk);

   return 0;

}

Measured memory_bytes: 1632
#include<math.h>
#include<string.h>
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<sstream> //istringstream stm(string); stm >> x;
#define INF 2139062143
#define inf -2139062144
#define ll long long
using namespace std;
int totcap;
int w[3];
int dp[3005];
double des;
int pack(int water,int cap) {
	int ret = 0;
	for(int i=1; i<=2; i++) {
		for(int j=w[i]; j<=cap; j++) {
			dp[j] = max(dp[j-w[i]]+w[i], dp[j]);
			if(dp[j] + water <= totcap)
				ret = max(ret,dp[j]);
		}
	}
	return ret;
}
int main() {
	int a,b,e;
	scanf("%d%d%d%d%d%d",&a,&b,&w[1],&w[2],&e,&totcap);
	int ans;
	des = -9999999.0;
	int answ = 0,anst = 0;
	for(int i = 0; i<=totcap / (a*100); i++) {
		for(int j=0; j<=totcap/ (b*100); j++) {
			memset(dp,0,sizeof(dp));
			int water = i * 100 * a + j * 100 * b;
			if(water <= totcap) {
				int cap = i * a * e + j * b * e;
				ans = pack(water,cap);
				if(water != 0) {
					double temp = (double) ans / (double)(water + ans);
					if(temp > des) {
						des = temp;
						answ = water + ans;
						anst = ans;
					}
				}
			}
		}
	}
	printf("%d %d\n",answ,anst);
	return 0;
}

Measured memory_bytes: 256
N = int(input())
arr = list(map(int, input().split()))
dp = [[0]*(N+1) for _ in range(N+1)]
for i in range(1, N+1):
    for k in range(N-i+1):
        j = k+i
        if (N-i)%2 == 0:
            dp[k][j] = max(dp[k+1][j]+arr[k], dp[k][j-1]+arr[j-1])
        else:
            dp[k][j] = min(dp[k+1][j]-arr[k], dp[k][j-1]-arr[j-1])
print(dp[0][N])

Measured memory_bytes: 113116
#include<stdio.h>
int main(){
	int a,b,c,d;
  scanf("%d %d %d %d",&a,&b,&c,&d);
  if(a+b>c+d)
    printf("Left");
  else if(a+b<c+d)
    printf("Right");
  else if(a+b==c+d)
    printf("Balanced");
  return 0;
}

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

int main() {
    string s;
    cin >> s;
    int size = s.size();
    string arr[size];
    for (int i = 0; i < size; i++){
        arr[i] = "x";
    }
    for (int i = 0; i < size; i++){
        cout << arr[i];
    }
    cout << endl;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int x = sc.nextInt();
		int m[] = new int[n];
		int sum = 0;
		for(int i=0; i<n; i++){
			m[i] = sc.nextInt();
			sum += m[i];
		}
		int min = m[0];
		for(int i=1; i<n; i++){
			if(m[i] < min)min = m[i];
		}
		System.out.println(n+((x - sum)/min));
	}
}

Measured memory_bytes: 23124
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
#include<iomanip>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
int N, M;
vector<vector<int>>G;
int dp[100010];
int rec(int v) {
	if (dp[v] != -1)return dp[v];
	int res = 0;
	for (int i = 0; i < G[v].size(); ++i) {
		res = max(res, rec(G[v][i]) + 1);
	}
	return dp[v] = res;
}
int main() {
	cin >> N >> M;
	G.assign(N, vector<int>());
	for (int i = 0; i < M; ++i) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		G[x].push_back(y);
	}
	for (int i = 0; i < 100010; ++i) {
		dp[i] = -1;
	}
	int res = 0;
	for (int i = 0; i < N; ++i) {
		res = max(res, rec(i));
	}
	cout << res << endl;
    return 0;
}

Measured memory_bytes: 8192
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

/**
 * Lesson5B　以下のような、たてH cm よこ W cm のチェック柄の長方形を描くプログラムを作成して下さい。
#.#.#.#.#.
.#.#.#.#.#
#.#.#.#.#.
.#.#.#.#.#
#.#.#.#.#.
.#.#.#.#.#


 * @author 前島佑介
 * @version 2014/12/1
 */
class Main {

	/**
	 * プログラムのエントリポイント
	 * @param args
	 */
	public static void main(String[] args) {

		try{

			BufferedReader insBR = new BufferedReader(new InputStreamReader(System.in));

			String strLine = "";

			ArrayList<String> strArray = new ArrayList<String>();

			//入力値をListに全部受け取る
			while(true) {

				strLine = insBR.readLine();

				//終了条件
				if(strLine.equals("0 0")) {

					break;
				}

				strArray.add(strLine);
			}

			//1列づつ処理
			for(int i = 0; i < strArray.size(); i++) {

				//分けた文字列はstrLineAry[0]とstrLineAry[1]に分けられる
				String[] strLineAry = strArray.get(i).split(" ");

				//左の値
				int intNum1 = Integer.parseInt(strLineAry[0]);

				//右の値
				int intNum2 = Integer.parseInt(strLineAry[1]);

				SharpPaint(intNum1, intNum2);
			}

		}catch(IOException e) {

			System.out.println(e);
		}catch(NumberFormatException e) {

			System.out.println("数値で入力して下さい");
		}
	}
	/**
	 * たてintNum1の分よこintNum２の分の長方形を描くプログラム
	 * 1 cm × 1cm の長方形を '#'と'.'で表す
	 * @param intNum1
	 * @param intNum2
	 */
	public static void SharpPaint(int intNum1, int intNum2) {

		//'＃'か'.' trueが'#'
		boolean booSharp = true;

		//たての分　ループ
		for(int i = 0; i < intNum1; i++) {

			//偶数の行は'#'から始める
			if(i % 2 == 0) {

				booSharp = true;

			} else {

				booSharp = false;

			}

			//よこの分　ループ
			for(int j = 0; j < intNum2; j++) {

				//'#'と'.'を交互に表示
				if(booSharp) {

					System.out.print("#");

					booSharp = false;

				} else {

					System.out.print(".");

					booSharp = true;

				}



			}
			//改行
			System.out.println("");
		}

		//改行
		System.out.println("");

	}
}

Measured memory_bytes: 26044
import sys
sys.setrecursionlimit(500*500)
n = int(input())
a = [int(input()) for _ in range(n)]
def search(i, p):
    if p > n:
        print(-1)
        exit()
    elif i == 2:
        print(p)
        exit()
    else:
        search(a[i-1], p+1)

search(1, 0)


Measured memory_bytes: 99344
n,m,q = list(map(int,input().split()));
 
data = [0]*q;
for i in range(q):
    data[i] = list(map(int,input().split()));
 
A = [1]*n;
ans = 0;
As = [A];
 
for i in As :
    A_now = As.pop(-1);
    for j in range(n) :
        if A_now[j] < m :
            A_next = [A_now[j]+1]*n;
            for k in range(j) :
                A_next[k] = A_now[k];
            As.append(A_next);
    ans_now = 0;
    for j in range(q) :
        if A_now[data[j][1]-1] - A_now[data[j][0]-1] == data[j][2] :
            ans_now += data[j][3];
    if ans_now>ans :
        ans = ans_now;
 
 
print(ans);

Measured memory_bytes: 199288
N,K = gets.split.map(&:to_i)
A = [nil] + gets.split.map(&:to_i)
v = []

pos = 1
l = 0
while l < K && !v[pos]
  v[pos] = l
  pos = A[pos]
  l += 1
end

if l < K
  k = (K - l) % (l - v[pos])
  k.times do 
    pos = A[pos]
  end
end

puts pos

Measured memory_bytes: 30608
import sys

input = sys.stdin.readline


def main():
    A, B, C = [int(ele) for ele in input().split()]
    ans = "NO"
    for i in range(10000):
        if (A * i) % B == C:
            ans = "YES"

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 38640
#include<bits/stdc++.h>
using namespace std;
#define INF 2147483647
int main(){
  string a,b;
  int c=0;
  cin>>a;
  for(int i=0;i<a.size();i++){
    if((int)a[i]>=97) a[i]=a[i]-32;
  }
  while(true){
    cin>>b;
    if(b=="END_OF_TEXT") break;
    for(int i=0;i<b.size();i++){
      if((int)b[i]>=97){
	b[i]=b[i]-32;
      }
    }
    if(b==a) c++;
  }
  cout<<c<<"\n";
}



Measured memory_bytes: 3136
program main
 implicit none
 integer N,i,j,ans
 integer,allocatable::d(:)
 
 read(*,*) N
 allocate(d(N))
 read(*,*) d
 
 ans = 0
 do i=1,N-1
  do j=i+1,N
   ans = ans + d(i) * d(j)
  end do
 end do
 write(*,*) ans
end program main

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

int main(){
	int i,j,n,*a;
	long long result=0;
	scanf("%d",&n);
	a=new int[n];
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
		result=result+a[i]-1;
	}
	printf("%lld",result);
	return 0;
	system("pause");
}

Measured memory_bytes: 256
def inpl(): return list(map(int, input().split()))
N = int(input())
W = inpl()
a = 0
b = sum(W)
ans = abs(a-b)
for i in range(N):
    w = W[i]
    a += w
    b -= w
    ans = min(ans, abs(a-b))
print(ans)

Measured memory_bytes: 38384
import java.util.Scanner;

//Bitwise Kingdom
public class Main{

	int n;
	long M;
	char[] r;
	long[][] comb;

	boolean dfs(int k, long L, long R, int c){
		if(!(L<=M&&M<=R))return false;
		if(k==n){
			return c==0;
		}
		if(n-k-1>=c){
			r[k] = '0';
			if(dfs(k+1, L, L+comb[n-k-1][c]-1, c))return true;
		}
		if(c==0)return false;
		r[k] = '1';
		long up = 0;
		if(n-k-1>=c)up += comb[n-k-1][c];
		return dfs(k+1, L+up, R, c-1);
	}

	long[][] comb(int N){
		long[][] r = new long[N+1][N+1];
		r[0][0]=1;
		for(int i=1;i<=N;i++){
			r[i][0]=r[i][i]=1;
			for(int j=1;j<i;j++){
				r[i][j] = r[i-1][j-1]+r[i-1][j];
			}
		}
		return r;
	}

	void run(){
		Scanner sc = new Scanner(System.in);
		comb = comb(60);
		for(;;){
			n = sc.nextInt(); M = sc.nextLong();
			if((n|M)==0)break;
			long s = 0;
			int c = 0;
			for(;c<=n;c++){
				s += comb[n][c];
				if(M<=s)break;
			}
			s -= comb[n][c];
			M -= s;
			r = new char[n];
			dfs(0, 1, comb[n][c], c);
			System.out.println(new String(r));
		}
	}

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

Measured memory_bytes: 12000
cnt = int(input())
numlist = list(map(int,input().split()))
list.sort(numlist, reverse=True)
A = 0
B = 0

for x in range(cnt):
    if x % 2 == 0:
        A += numlist[x]
    else:
        B += numlist[x]

print(A-B)

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

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
    cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args&&... args) {
    const char *comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " : " << arg1 << " | ";
    __f(comma + 1, args...);
}
#define pi 3.141592653589
#define MOD 1000000007
#define to() int t; cin>>t; while(t--)
#define pb push_back
#define in insert
#define mp make_pair
#define ff first
#define ss second
#define si(s) s.size()
#define fori(it,v) for(it=v.begin();it!=v.end(); it++) 
#define for1(low,high,k) for(int i=low;i<high;i+=k)
#define for11(low,high,k) for(int j=low;j<high;j+=k)
#define for2(low,high,k) for(int i=low;i<=high;i+=k)
#define rev(high,low,k)  for(int i=high;i>=low ;i-=k)
#define all(x) x.begin(), x.end()
#define fil(x,i) memset(x,i,sizeof(x));
#define setbits(x) __builtin_popcount(x)
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define read freopen("input.txt","r",stdin)
#define write freopen("output.txt","w",stdout) 
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;


int main()
{
	boost;
	int x; cin>>x;
	int ans=!x;
	cout<<ans<<endl;
	
	

return 0;
}


Measured memory_bytes: 3648
#include<iostream>
#include<stack>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<iomanip>
#include<set>
#include<bitset>
#include<cmath>
#include<numeric>
#include<limits>

#define REP(i, m, n) for(int i = (m); i < (n); i++)
#define rep(i,n) REP(i,0,n)
#define NIL -1
using namespace std;
// typedef long long ll;
static const int MOD = 10000007;
static const int MAX = 1005;
int N, M[MAX];
int A[MAX][MAX], T[MAX], step[MAX];


using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> xs(n),ys(n);
  for(Int i=0;i<n;i++) cin>>xs[i]>>ys[i];
  double ans=0;
  for(Int i=0;i<n;i++){
    Int gx=xs[i],gy=ys[i];
    for(Int k=0;k<4;k++){
      {
        Int nx=-gy,ny=gx;
        gx=nx;
        gy=ny;
      }

      Int sx=0,sy=0;
      Int px=0,py=0;
      Int qx=0,qy=0;

      // auto hoge = [](int huga, int hugi) {return huga + hugi} はラムダ式
      // [&]は参照渡し、[=]なら値渡し（全ての変数について）
      auto dot=[&](Int x1,Int y1,Int x2,Int y2){return x1*x2+y1*y2;}; // 内積
      auto cross=[&](Int x1,Int y1,Int x2,Int y2){return x1*y2-x2*y1;}; // 外積
      for(Int j=0;j<n;j++){
        Int res=dot(xs[j],ys[j],gx,gy);
        if(res<0) continue;
        if(res>0){ // 内積が正なら近い向き
          sx+=xs[j];
          sy+=ys[j];
          continue;
        }
        // 内積が0の時はどちらの方向で直行しているか？
        if(cross(xs[j],ys[j],gx,gy)>0){ // 外積が正ならgはsの時計回り側
          px+=xs[j];
          py+=ys[j];
        }else{ // sを反時計回りに回してgになる
          qx+=xs[j];
          qy+=ys[j];
        }
      }
      // 内積が0のベクトルを足したり足さなかったりを試す。
      // t = 0 : 時計回り＝なし、反時計回り＝なし
      // t = 1 : 時計回り＝あり、反時計回り＝なし
      // t = 2 : 時計回り＝なし、反時計回り＝あり
      // t = 3 : 時計回り＝あり、反時計回り＝あり
      for(Int t=0;t<4;t++){
        double bx=sx,by=sy;
        if(t&1) bx+=px,by+=py; // & is bitwise operator
        if(t&2) bx+=qx,by+=qy; // & represents "and". t&2 is the 2nd least bit.
        chmax(ans,bx*bx+by*by);
      }
    }
  }

  cout<<fixed<<setprecision(12)<<sqrt(ans)<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

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

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

int main(int argc, char const *argv[]) {
    int n; cin>>n;
    vector<ll> a(n);
    ll x = 0;
    rep(i,n) cin>>a[i], x ^= a[i];
    vector<ll> ans;
    rep(i,n) ans.push_back(x^a[i]);
    print(ans);
    return 0;
}

Measured memory_bytes: 6852
import heapq

n, m = map(int, input().split())
a = [-int(x) for x in input().split() ]
heapq.heapify(a)

for _ in range(m):
    tmp = -heapq.heappop(a) // 2
    heapq.heappush(a, -tmp)

print(-sum(a))


Measured memory_bytes: 14380
// بِسمِ اللہِ  الرَّحم?نِ  الرَّ حِیم
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
//code begins
ll arr[10000001];
const ll N=10000000;
void sieve(){
    memset(arr,0,sizeof(arr));
    for(ll i=1;i<=N;i++)
        for(ll j=i;j<=N;j+=i)
            arr[j]++;
    for(ll i=1;i<=N;i++)
    {
        arr[i]*=i;
        if(i>=2)
            arr[i]+=arr[i-1];
    }
}
void solve(){
    sieve();
    ll n;cin>>n;
    cout<<arr[n]<<endl;
}
signed main()
{ 
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);cout.tie(NULL);
  solve();
  return 0;
}


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

int main() {
  int a,b,c;cin>>a>>b>>c;
  if(a<c&&c<b||b<c&&c<a)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 3612
#include<stdio.h>
int N,A[300][300],B[300][300],i,j,k,t,o;
long long a;
int main(){
scanf("%d",&N);
for(i=0;i<N;i++)for(j=0;j<N;j++)scanf("%d",&A[i][j]),B[i][j]=A[i][j];
for(i=0;i<N;i++)for(j=0;j<N;j++)for(k=0;k<N;k++)if(B[j][k]>(t=B[j][i]+B[i][k]))B[j][k]=t;
for(i=0;i<N;i++)for(j=0;j<i;j++)
if(B[i][j]<A[i][j]){printf("-1\n");return 0;}
else{o=1;for(k=0;k<N;k++)if(k!=i&&k!=j&&B[i][j]==B[i][k]+B[k][j])o=0;if(o)a+=A[i][j];}
printf("%lld\n",a);}

Measured memory_bytes: 896
#include <bits/stdc++.h>
#define Phuong_ ios_base::sync_with_stdio(0); cin.tie(0);
#define REP(i,a,b) for(int i=a; i<=b; ++i)

/// easy access -------------
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
typedef pair<int, int> pi;
typedef tuple<bool, int, int> tp;
typedef vector<vector<int> > vv;
///-------------------------



int main()
{
    Phuong_; /// <3333
	int n;
	cin >> n;
	vector<pi> a(n);
	for(pi& x:a){
		cin >> x.first >> x.second;
	}	 		
	sort(a.begin(), a.end());
	int minn;
	int ans =0;
	for(int i=0; i<n; ++i){
		if (i==0){
			minn = a[i].first + a[i].second;
		} else {
			ans = max(ans, a[i].first + a[i].second - minn);
			minn = min(minn, a[i].first + a[i].second);
		}
	}
	for(int i=0; i<n; ++i){
		if (i==0){
			minn = a[i].first - a[i].second;
		} else {
			ans = max(ans, a[i].first - a[i].second - minn);
			minn = min(minn, a[i].first - a[i].second);
		}
	}
	cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 4712
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

var nextString func() string

func init() {
	nextString = newReadString(os.Stdin)
}

func main() {
	n := nextInt()
	var ans int
	for i := 1; i*i <= n; i++ {
		ans = i * i
	}
	fmt.Println(ans)
}

func nextInt() (result int) {
	result, _ = strconv.Atoi(nextString())
	return
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
		}
		return r.Text()
	}
}


Measured memory_bytes: 640
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace	std;

int main(){

  int a,b;
  string s,t,u;

  cin>>s>>t>>a>>b>>u;

  if(u==s){
    a--;
  }else{
    b--;
  }

  printf("%d %d\n",a,b);

  return 0;
}

Measured memory_bytes: 256
using System;

class Program
{
 public static void Main()
 {
   var output = Console.ReadLine().Split(' '); 
   
   var n = int.Parse(output[0]);
   var d = int.Parse(output[1]);
   
   var cost = (d * 2) + 1;
   var persones = n / cost;
   persones += ( (n % cost) > 0 ? 1 : 0);
   
   Console.WriteLine(persones);
 }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr long double EPS = 1e-15;
const long double PI = acos(-1);
constexpr int inf = 1e9;
constexpr ll INF = 2e18;
constexpr ll MOD = 1e9+7;
constexpr ll MOD1 = 998244353;
typedef pair<ll,ll> P;
//#define all(v) (v).begin(), (v).end()
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
//#define mp make_pair

int k;

void input() {
    cin >> k;
}

void solve() {
    int n = k;
    if (n == 3) {
        cout << "2 5 63" << endl;
        return;
    }
    queue<int> v[10];
    vector<int> ans;
    ans.pb(2);
    ans.pb(3);
    for (int i = 4; i <= 30000; i++) {
        if (i % 6 == 0) {
            v[6].push(i);
        } else if (i % 4 == 0) {
            v[4].push(i);
        } else if (i % 3 == 0) {
            v[3].push(i);
        } else if (i % 2 == 0) {
            v[2].push(i);
        }
    }
    ans.pb(v[4].front());
    v[4].pop();
    ans.pb(v[3].front());
    v[3].pop();
    n -= 4;
    while (n > 2 && !v[2].empty()) {
        ans.pb(v[2].front());
        ans.pb(v[4].front());
        v[2].pop();
        v[4].pop();
        n -= 2;
    }
    while (n > 2 && !v[3].empty()) {
        ans.pb(v[3].front());
        v[3].pop();
        ans.pb(v[3].front());
        v[3].pop();
        n -= 2;
    }
    while (n > 0 && !v[6].empty()) {
        ans.pb(v[6].front());
        v[6].pop();
        n--;
    }
    REP(i,k) {
        cout << ans[i] << " \n"[i == k - 1];
    }
}

int main(int argc, char *argv[]){
    input();
    solve();
    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
ll arr[500005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    map<int,int> mp;
    mp[1]=31;
    mp[2]=28;
    mp[3]=31;
    mp[4]=30;
    mp[5]=31;
    mp[6]=30;
    mp[7]=31;
    mp[8]=31;
    mp[9]=30;
    mp[10]=31;
    mp[11]=30;
    mp[12]=31;
    int x,y;
    char c;
    int x1,y1;
    cin>>x>>y>>x1>>y1;
    if(mp[x]==y) cout<<1<<endl;
    else cout<<0<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main() {
    char n[200000];
    unsigned long sum = 0;
    gets(n);
    for(int i = 0;n[i] != '\0';i++){
        sum += n[i] - '0';
    }
    printf((sum % 9)? "No\n" : "Yes\n");
    return 0;
}


Measured memory_bytes: 1716
#include <bits/stdc++.h>
using namespace std;
const long INF=1000000000000000;

int main() {
    string s;
    cin>>s;
    set<char> alp;
    for(int i=0;i<26;i++) alp.insert('a'+i);
    for(int i=0;i<s.size();i++) alp.erase(s.at(i));
    if(alp.size()==0) cout<<"None"<<endl;
    else cout<<*alp.begin()<<endl;
}

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

int main(){
  
  int m;
  
  cin >> m;
  
  int h = m / 100;
  
  int j = (m - h * 100) / 10;
  
  int i = m - h * 100 - j * 10;
  
  cout << h + j + i
    << endl;
  
  return 0;
  
}

Measured memory_bytes: 3560
#include <bits/stdc++.h>
#define ld long double
#define int long long
using namespace std;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const int inf = 1e17;
int dx[] = {0,0,-1,1,-1,-1,1,1};
int dy[] = {1,-1,0,0,1,-1,-1,1};
int dp[N], arr[N];
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); 
	cout.tie(0);
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> arr[i];
	}
	arr[0] = 1e17;
	for(int i = 2; i <= n; i++){
		dp[i] = min(dp[i - 1] + fabs(arr[i] - arr[i - 1]), dp[i - 2] + fabs(arr[i] - arr[i - 2]));
	}
	cout << dp[n];
}

Measured memory_bytes: 1792
# include <iostream>
# include <algorithm>
# include <iomanip>

const int MAX_N = 100;
const int MAX_M = 100;

int n, m;
double dp[MAX_N][MAX_M];

double board[MAX_M][MAX_M];

int main() {
	while (1) {
		std::cin >> m >> n;
		if (n == 0 && m == 0)
			break;
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < m; ++j)
				dp[i][j] = 0;
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < m; ++j)
				std::cin >> board[i][j];
		}
		std::fill(dp[0], dp[0] + m, 1.0);
		for (int i = 1; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				for (int k = 0; k < m; ++k) {
					dp[i][j] = std::max(dp[i][j], dp[i - 1][k] * board[k][j]);
				}
			}
		}
		double res = 0;
		for (int i = 0; i < m; ++i)
			res = std::max(res, dp[n - 1][i]);
		std::cout << std::fixed << std::setprecision(2) << res << std::endl;
	}
	return 0;
}

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

int main(){
  int N , K , num;
  cin >> N >> K;
  num = 1;
  for (int i=0; i < N; i++){
    if (num < K){
      num *= 2;
    }
    else{
      num += K;
    }
  }
  cout << num << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
  long long int n;
  cin>>n;
  vector<long long int> a(n);
  long long int all=0;
  for(long long int i=0; i<n; i++){
    cin>>a.at(i);
    all^=a.at(i);
  }

  for(long long int i=0; i<n; i++){
    long long int ans=(all^a.at(i));
    cout<<ans;
    if(i!=n-1){
      cout<<" ";
    }else{
      cout<<endl;
    }
  }
}

Measured memory_bytes: 4840
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = ll(1e9)+7;

int main(){
    ll N;
    cin >> N;
    set<ll> detected;
    vector<ll> T(N);
    detected.insert(0);
    for(int i=0;i<N;i++){
        cin >> T[i];
        if(i>0&&T[i]>T[i-1]){
            detected.insert(i);
        }
    }
    vector<ll> A(N);
    for(int i=0;i<N;i++){
        cin >> A[i];
        if(detected.find(i) != detected.end() && T[i] >A[i]){
            cout << 0 << endl;
            return 0;
        }
    }
    if(A[N-1] >T[N-1]){
        cout << 0 << endl;
        return 0;
    }
    detected.insert(N-1);
    
    vector<ll> mAT(N);
    for(int i=0;i<N-1;i++){
        if(A[i]>A[i+1]){
            if(A[i] > T[i]){
                cout << 0 << endl;
                return 0;
            }
            detected.insert(i);
        }
        mAT[i] = min(A[i],T[i]);
        // cerr << mAT[i]<< endl;
    }
    
    ll ans =1;
    for(int i=0;i<N;i++){
        if(detected.find(i) == detected.end()){
            ans *= mAT[i];
            ans %= MOD;
        }else{
            // cerr <<"detected"<< endl;
        }
    }
    cout<< ans << endl;




    return 0;
}

Measured memory_bytes: 7296
n = int(input())

l = [1]
i = 1
while 6 ** i <= 100000:
    l.append(6 ** i)
    i += 1
i = 1
while 9 ** i <= 100000:
    l.append(9 ** i)
    i += 1
l.sort()

dp = [float('inf')] * (n+1)
dp[0] = 0
for i in range(1, n+1):
    for v in l:
        if v > i:
            break
        dp[i] = min(dp[i], dp[i-v] + 1)

print(dp[n])

Measured memory_bytes: 74584
def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b

from collections import Counter
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1 for i in range(n)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.size[x] += self.size[y]
            self.size[y] = 0

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)



n,m = getMN()

bridges = []

for i in range(m):
    a,b = getMN()
    bridges.append([a,b])

bridges.reverse()

uf = UnionFind(n)
ans = n*(n-1)//2
answers = [ans]
for query in bridges:
    x,y = query
    if not uf.same_check(x-1,y-1):
        #print(uf.size,x,y)
        ans -= uf.size[uf.find(x-1)]*uf.size[uf.find(y-1)]
        #print(uf.find(x-1))
        uf.union(x-1,y-1)

    answers.append(ans)

for fa in answers[:-1][::-1]:
    print(fa)


Measured memory_bytes: 29736
#include <iostream>
#include <string>
using namespace std;
int main(){
  string s;
  cin >>s;
  long long int sum,n,ans=0,ss=s.size();
  for(int i=0;i<(1<<(ss-1));i++){
      sum=0;
      n=s[0]-'0';
      for(int j=0;j<ss-1;j++){
        if(i&(1<<j)){
          sum+=n;
          n=0;
        }
        n=n*10+s[j+1]-'0';
      }
      sum+=n;
      ans+=sum;
  }
  cout <<ans<<endl;
}


Measured memory_bytes: 256
#####segfunc######
def segfunc(x,y):
    return max(x,y)

def init(init_val):
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res
    
n,k = map(int,input().split())
a = [int(input()) for i in range(n)]
#n = int(input())
#a = tuple(map(int,input().split()))

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(max(a)-1).bit_length()
seg=[ide_ele]*2*num
#init(a)

ans = 0
max_a = max(a)

for i in range(n):
    tmp = query(max(0,a[i]-k),min(a[i]+k+1,max_a+1))
    #print(i,a[i],max(0,a[i]-k),min(a[i]+k,max(a)))
    update(a[i],tmp+1)
    #print(tmp)
    #print(st.query(0, max(a)))
    #ans = max(ans,tmp+1)
    #print(seg[0],k)
#print(seg)
#print(query(0,max(a)),seg[0])
print(seg[0])

Measured memory_bytes: 134124