akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        final String[] WEATHER = {"Sunny" , "Cloudy", "Rainy"};

        int index = -1;
        for(int i = 0; i < WEATHER.length; i++) {
        	if(WEATHER[i].equals(s)) {
        		index = i;
        		break;
        	}
        }

        String ans = WEATHER[ (index+1) % WEATHER.length ];
        System.out.println(ans);
	}
}

Measured memory_bytes: 19796
#include<bits/stdc++.h>
using namespace std;
#define il inline 
#define int long long
//int n,m,T;long long P,p[200005],f[200005],a,b,c,d,s=1,inv[2000005],jc[2000005],jcinv[2000005];
il int read()
{
	int k=1,re=0;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')k=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){re=re*10+ch-48;ch=getchar();}
	return re*k;
}
il void write(int x)
{
	if(x<0)return write(-x),void();
	if(x<=9)return putchar(x+48),void();
	return write(x/10),write(x%10),void();
}
vector<int> e[200005];
int n,m,d[200005],vis[200005];
signed main()
{
	n=read();m=read();
	for(int i=1,u,v;i<=m;i++)
	{
		u=read();v=read();
		e[u].push_back(v);
		e[v].push_back(u);
	}
	bool now=0;
	queue<int> q;
	q.push(1);vis[1]=1;
	while(!q.empty())
	{
		int t=q.front();q.pop();
		for(int i=0;i<e[t].size();i++)
		{
			int y=e[t][i];
			if(vis[y])continue;
			d[y]=t;vis[y]=1;q.push(y);
		}
	}
	for(int i=1;i<=n;i++)
		if(!vis[i])now=1;
	if(now)puts("No");
	else
	{
		puts("Yes");
		for(int i=2;i<=n;i++)
			write(d[i]),puts("");
	}
}

Measured memory_bytes: 15984
#include "iostream"
#include <string>
using namespace std;
 
int main(){

  int A, B;
  
  cin >> A >> B;
 
	if(A!=1 && B!=1)  cout << 1;
  	if(A!=2 && B!=2)  cout << 2;
  	if(A!=3 && B!=3)  cout << 3;

  return 0;
  
}

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

int main() {
  int A,B,M;
  
  cin >> A >> B >> M;

  int a[A];
  int b[B];
  int x[M], y[M], c[M];

  for (int i=0;i<A;i++) {
      cin >> a[i];
  }

  for (int i=0;i<B;i++) {
      cin >> b[i];
  }

  for (int i=0;i<M;i++) {
      cin >> x[i] >> y[i] >> c[i];
  }

  int amin=100000;

  for (int i=0;i<A;i++) {
      if (amin > a[i]) amin=a[i];
  }

  int bmin=100000;

  for (int i=0;i<B;i++) {
      if (bmin > b[i]) bmin=b[i];
  }

  int smin=amin+bmin;

  for (int i=0;i<M;i++) {
      if (smin > a[x[i]-1]+b[y[i]-1]-c[i]) smin=a[x[i]-1]+b[y[i]-1]-c[i];
  }
      cout << smin << endl;
}

Measured memory_bytes: 2176
d = input().split()
n = int(input())
r_list = []
i = 0

while n > i:
    t, f = map(str, input().split())
    tf = str(d.index(t)) + str(d.index(f))

    if tf == "12" or tf == "24" or tf == "43" or tf == "31":
        r_list.append(1)
    elif tf == "20" or tf == "03" or tf == "35" or tf == "52":
        r_list.append(2)
    elif tf == "01" or tf == "15" or tf == "54" or tf == "40":
        r_list.append(3)
    elif tf == "10" or tf == "51" or tf == "45" or tf == "04":
        r_list.append(4)
    elif tf == "02" or tf == "30" or tf == "53" or tf == "25":
        r_list.append(5)
    elif tf == "21" or tf == "42" or tf == "34" or tf == "13":
        r_list.append(6)

    i += 1

for r in r_list:
    print(d[r-1])



Measured memory_bytes: 5608
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sn = new Scanner(System.in);
        int n = sn.nextInt();
        int m = sn.nextInt();

        int[][] priceList = new int[n][2];
        for (int i = 0; i < n; i++){
            priceList[i][0] = sn.nextInt();
            priceList[i][1] = sn.nextInt();
        }
        
        Arrays.sort(priceList, (l,r) -> {return l[0] - r[0];});
        
        long sum = 0;
        for (int[] price : priceList){
            if(m - price[1] >= 0) {
                sum += (long)price[0] * price[1];
                m -= price[1];
            } else {
                sum += (long)price[0] * m;
                break;
            }
        }
        
        System.out.println(sum);
    }
}

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

a,b = [int(x) for x in input().split(" ")]

if a <= 0 and b >= 0:
    print("Zero")
elif a > 0:
    print("Positive")
elif (b - a) % 2 == 0:
    print("Negative")
else:
    print("Positive")
    


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

int main() {
    int n;
    cin >> n;
    vector<double>v(n);
    for(int i=0; i<n; ++i){
        cin >> v[i];
    }
    sort(v.begin(),v.end());
    double ans ;
    ans=v[0];
    for(int i=1; i<n; ++i){
        ans += (v[i]+ans)/2 -ans;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int N;
int cnt;
void rec(long num,int flag){
  if(num>N)return;
  if(flag==7 && num<=N){
    cnt++;
  }
  rec(num*10+3,flag|1);
  rec(num*10+5,flag|2);
  rec(num*10+7,flag|4);
}
int main(int argc,char **argv){
  cin>>N;
  int flag=0;
  long num=0;
  rec(num,flag);
  cout<<cnt<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n) ;i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
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; }



int main(int argc, char const *argv[]) {
  int r,D,x;
  cin >> r >> D >> x;
  rep(i,10){
    x=r*x-D;
    cout << x << endl;
  }
  return 0;
}


Measured memory_bytes: 256
function main()
  
  N = parse(Int,readline())
  d = map(x -> parse(Int,x), split(readline()))
  
  ans = 0
  
  for i in 1:N
    for j in 1:N
      
      if j <= i
        continue
      else
        ans += d[i]*d[j]
      end
      
    end
  end
  
  println(ans)
  
end

main()

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

int main() {
  int A[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int k;
  cin >> k;

  cout << A[k-1] << endl;
}


Measured memory_bytes: 256
S = input()
num = 0
bits = format(num , 'b').zfill(len(S) - 1)
ans = 0
for i in range(2 ** (len(S) - 1)):
  index = 0
  for j in range(len(S) - 1):
    if(bits[j] == "1"):
      ans += int(S[index:j + 1])
      index = j + 1
  ans += int(S[index:])
  num += 1
  bits = format(num , 'b').zfill(len(S) - 1)
print(ans)

Measured memory_bytes: 68220
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;
 
public class Main {
 
    void solve() throws IOException {
        int N = ni();
 
        long ans = (N-1)*1L*N/2L;
        out.println(ans);
    }

    final int mod = 1000000007;
    final BigInteger MOD = BigInteger.valueOf(mod);
    int upperBound(ArrayList<Long> list, Long target){
        int i = Collections.binarySearch(list, target, new UpperBoundComparator<Long>());
        return ~i;
    }
    class UpperBoundComparator<T extends Comparable<? super T>> implements Comparator<T>{
        public int compare(T x, T y){
            return (x.compareTo(y) > 0) ? 1 : -1;
        }
    }
    int lowerBound(ArrayList<Long> list, Long target){
        int i = Collections.binarySearch(list, target, new LowerBoundComparator<Long>());
        return ~i;
    }
    class LowerBoundComparator<T extends Comparable<? super T>> implements Comparator<T>{
        public int compare(T x, T y){
            return (x.compareTo(y) >= 0) ? 1 : -1;
        }
    }
    int mul(int x, int y){
        int val = (int)((x * 1L * y) % mod);
        return val>=0 ? val : val+mod;
    }
    int add(int x, int y) {
        x += y;
        if(x < 0) x += mod;
        if(x>=mod) x -= mod;
        return x;
    }
    int sub(int x, int y){
        x = add(x,mod-y);
        if(x < 0) x += mod;
        if(x>=mod) x -= mod;
        return x;
    }
    String ns() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine(), " ");
        }
        return tok.nextToken();
    }
 
    int ni() throws IOException {
        return Integer.parseInt(ns());
    }
 
    long nl() throws IOException {
        return Long.parseLong(ns());
    }
 
    double nd() throws IOException {
        return Double.parseDouble(ns());
    }
 
    String[] nsa(int n) throws IOException {
        String[] res = new String[n];
        for (int i = 0; i < n; i++) {
            res[i] = ns();
        }
        return res;
    }
 
    int[] nia(int n) throws IOException {
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = ni();
        }
        return res;
    }
 
    long[] nla(int n) throws IOException {
        long[] res = new long[n];
        for (int i = 0; i < n; i++) {
            res[i] = nl();
        }
        return res;
    }
 
    static BufferedReader in;
    static PrintWriter out;
    static StringTokenizer tok;
 
    public static void main(String[] args) throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        tok = new StringTokenizer("");
        Main main = new Main();
        main.solve();
        out.close();
    }
}

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

using namespace std;
#define sqr(x) ((x)*(x))
#define cube(x) ((x)*(x)*(x))
#define GCD(a, b) __gcd(a, b)
#define LCM(a, b) ((a)*(b)/GCD(a,b))
#define PI (3.141592653589793238462643383279502884197169399375105820974944)
#define MP make_pair
#define n1 first
#define n2 second
#define ALL(x) (x).begin(), (x).end()
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PDB pair<db,db>
#define SI set<int>
#define SL set<ll>
#define MS multiset
#define MSI multiset<int>
#define MSLL multiset<ll>
#define PB push_back
#define PF push_front
#define VI vector<int>
#define VPI vector<pair<int,int>>
#define VLL vector<ll>
#define VS vector<string>
#define SZ(x) ((int)x.size())

typedef long long ll;

typedef unsigned long long ull;
typedef long double ld;
typedef double db;
const db eps = 0.000001;
const int INF = 1000000007;
const ll LINF = 1000000000000000555;
const int N = 1850555;
const int M = 1155;
const int L = 20;

void solve() {
    string s,t;
    cin >> s >> t;

    int ans = 0;
    for (int i = 0; i < SZ(s); i++){
        if (s[i] != t[i]) ans++;
    }

    cout << ans;


}

int main() {
    ios_base::sync_with_stdio(false);
#ifdef dxz05
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else

#endif

    int T = 1;
    //cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}

Measured memory_bytes: 3944
import bisect

N=int(input())

A=[int(input())for i in range(N)]
#print(A)

L=[0 for i in range(N+1)]

for i in range(N):
    if L[A[i]-1]>0:
        L[A[i]]=(L[A[i]-1]+1)
    else:
        L[A[i]]=1
print(N-max(L))

Measured memory_bytes: 18860
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=1e6+10;
int main()
{
    int a[3];
    for(int i=0;i<3;i++) cin>>a[i];
    sort(a,a+3);
    int ans=(a[2]-a[0])/2;
    a[0]+=(a[2]-a[0])/2*2;
    ans+=(a[2]-a[1])/2;
    a[1]+=(a[2]-a[1])/2*2;
    sort(a,a+3);
    //for(int i=0;i<3;i++) cout<<a[i];
    if(a[0]==a[1] && a[1]==a[2]);
    else if(a[0]==a[1]) ans++;
    else if(a[1]==a[2]) ans+=2;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,n) for(int i=1;i<=n;i++)
int main()
{
    int n,x,ans;

    while(1){

    cin >> n >> x;

    if(n==0 && x==0) return 0;
    
    ans=0;

    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            for(int k=j+1;k<=n;k++){
                if(i+j+k==x) ans++;
            }
        }
    }
    
    cout << ans << endl;

    }

    return 0;

}


Measured memory_bytes: 3056
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
using namespace std;
typedef long long ll;
int main(){
  int a,b,c;
  cin >> a >> b >> c;
  cout << c << " " << a << " " << b << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int dp[110003][3];
int main() {
    ios::sync_with_stdio(false);
    if (fopen("input.in", "r")) {
        freopen("input.in", "r", stdin);
        freopen("output.out", "w", stdout);
    }
    int n;
    int scores[110003][3];
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> scores[i][0] >> scores[i][1] >> scores[i][2];
    for (int i = 0; i < 3; i++) dp[0][i] = scores[0][i];
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j <= 2; j++) {
            for (int k = 0; k <= 2; k++) {
                if (j == k) continue;
                dp[i + 1][k] = max(dp[i + 1][k], scores[i + 1][k] + dp[i][j]);
            }
        }
    }
    cout << max(max(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]) << endl;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
 
int main(void)
{
	int N, i;
	string S;
  	
    cin >> N;
  
  for (i = 0; i < N; ++i)
  {
    cin >> S;
    if (S == "Y")
    {
      cout << "Four" << endl;
      break;
    }
    if (i == N - 1 && S != "Y")
    {
      cout << "Three" << endl;
    }
  }
}

Measured memory_bytes: 3568
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#define rep(i, n) for (int i = 0; i < static_cast<int>(n); i++)

using namespace std;
using ll = int64_t;
int ary[4];

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  int x, y;
  cin >> x >> y;
  ary[x] = 1, ary[y] = 1;
  if (ary[1] == 0)
    cout << 1 << endl;
  else if (ary[2] == 0)
    cout << 2 << endl;
  else
    cout << 3 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); i++)
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using Graph = vector<vector<int>>;  // int <=> ll
using P = pair<int, int>;
const int INFTY = 1e9+7;

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

  int num = (N-2)*(N-1)/2 - K;

  if (num < 0) {
    cout << -1 << endl;
    return 0;
  }

  cout << (N-1) + num << endl;  // M (number of edges)

  for (int i=1; i<N; i++) {  // center vertex is N
    cout << i << " " << N << endl;
  }
  for (int i=1; i<N-1; i++) {
    for (int j=i+1; j<N; j++) {
      if (num == 0) break;
      cout << i << " " << j << endl;
      --num;
    }
    if (num == 0) break;
  }
  return 0;
}


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

using namespace std;

int main() {
    int A, B, C, D;
    cin >> A >> B >> C >> D;

    string s = "";
    while (1) {
        C -= B;
        A -= D;
        if (C <= 0) {
            s = "Yes";
            break;
        } else if (A <= 0) {
            s = "No";
            break;
        }
    }
    cout << s << endl;

}


Measured memory_bytes: 3624
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        String s = scan.next();
        char[] c = s.toCharArray();
        System.out.println((char)((int)c[0] + 1));
    }
}


Measured memory_bytes: 21844
def resolve():
    import heapq
    N = int(input())
    a = list(map(int,input().split()))

    a1 = a[:N]
    heapq.heapify(a1)
    a2 = a[N:N*2]
    a3 = a[N*2:N*3]
    a3 = list(map(lambda x:x*(-1),a3))
    heapq.heapify(a3)
    s1 = [0 for _ in range(N+1)]
    s1[0] = sum(a1)
    for i in range(N):
        s1[i+1] = a2[i] - heapq.heappushpop(a1,a2[i]) + s1[i]
    s3 = [0 for _ in range(N+1)]
    s3[N] = sum(a3)
    for i in range(N,0,-1):
        s3[i-1] = -heapq.heappushpop(a3,a2[i-1]*(-1)) - a2[i-1] + s3[i]
    for i in range(N+1):
        s1[i] += s3[i]
    print(max(s1))   
resolve()

Measured memory_bytes: 122512
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

typedef long long ll;

const int MOD = 998244353;

int add(int a, int b) {
	return (a + b) % MOD;
}

int sub(int a, int b) {
	return (a - b + MOD) % MOD;
}

int mul(int a, int b) {
	return ((ll)a * b) % MOD;
}

int n;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	string s;
	cin >> s;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		a[i] = s[i] - '0';
	}
	vector<int> to(2 * n + 1);
	vector<int> any(2 * n + 1);
	for (int j = 2; j <= 2 * n; j += 2) {
		if ((2 * n) % j == 0) {
			int v = j / 2;
			if ((n / v) % 2 == 0) continue;
			int ans = 0;
			int less = 0;
			for (int i = 0; i < v; i++) {
				less = mul(less, 2);
				less = add(less, a[i]);
			}
			ans = less;
			vector<int> na(n);
			for (int i = 0; i < n; i++) {
				if (i < v) na[i] = a[i];
				else na[i] = na[i - v] ^ 1;
			}
			if (na <= a) ans = add(ans, 1);
			to[j] = ans;
			any[j] = 1;
		}
	}
	for (int i = 1; i <= 2 * n; i++) {
		for (int j = 2 * i; j <= 2 * n; j += i) {
			if (any[j]) to[j] = sub(to[j], to[i]);
		}
	}
	int ans = 0;
	for (int i = 1; i <= 2 * n; i++) {
		ans = add(ans, mul(i, to[i]));
	}
	cout << ans << endl;
}

Measured memory_bytes: 7784
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rrep(i,m,n) for(int i=(m);i<(n);i++)
#define fore(i,a) for(auto &i:a)
#define debug(a,b) cout << "debug : " << a << " , "<< b << endl
using ll=long long;
const ll INF=1LL<<60;
const ll mod=1E9+7;


int main(){
  ll n,m;
  cin >> n >> m;
  vector<ll>h(n+1),ma(n+1,0);
  rrep(i,1,n+1)cin >> h[i];
  rep(i,m){
    ll a,b;
    cin >> a >> b;
    ma[a]=max(ma[a],h[b]);
    ma[b]=max(ma[b],h[a]);
  }
  ll sum=0;
  rrep(i,1,n+1){
    if(ma[i]<h[i])sum++;
  }
  cout << sum;
}



Measured memory_bytes: 4824
n=int(input())
s=list(input())
ans=0
for i in range(1,n):
    if s[i] == "E":
        ans += 1
        
ans_=ans
for i in range(1,n):
    if s[i-1] == "W":
        ans_+= 1
    if s[i] == "E":
        ans_+= -1
    ans = min(ans,ans_)
print(ans)

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

int main(void) {
    
    int x[4];
    rep(i,4)cin>>x[i];
    int l = x[0] + x[1];
    int r = x[2] + x[3];
    if(l>r)cout << "Left" << endl;
    else if(l==r) cout << "Balanced" << endl;
    else cout << "Right" << endl;


    return 0;
}

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

#define MAX 100
#define NIL -1
using namespace std;

struct Node {int p, l, r; };

Node T[MAX];

void preorder(int u) {//先行順巡回
	if (u == NIL) {
		return;
	}

	printf(" %d", u);
	preorder(T[u].l);
	preorder(T[u].r);
}

void inorder(int u) {
	if (u == NIL) {
		return;
	}

	inorder(T[u].l);
	printf(" %d", u);
	inorder(T[u].r);
}

void postorder(int u){

	if (u == NIL) {
		return;
	}

	postorder(T[u].l);
	postorder(T[u].r);
	printf(" %d", u);
}
int main() {
	int n, v, c, l, r;

	//scanf("%d", &n);//節点の個数
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		T[i].p = T[i].l = T[i].r = NIL;
	}

	for (int j = 0; j < n; j++) {
		//cin >> v; //節点番号，子の数
		//scanf("%d %d", &l, &r); //子供の節点番号
		
		cin >> v >> l >> r;


		T[v].l = l;
		T[v].r = r;

		if (T[v].l != NIL) {
			T[l].p = v;
		}
		if (T[v].r != NIL) {
			T[r].p = v;
		}

	}

	int a= 0;
	for (int i = 0; i < n; i++) {
		if (T[i].p == NIL) a = i;
	}

	cout << "Preorder" << endl;
	preorder(a);

	cout << endl << "Inorder" << endl;
	inorder(a);

	cout << endl << "Postorder" << endl;
	postorder(a);

	cout << endl;

	return 0;
}



Measured memory_bytes: 3244
# coding: utf-8
# Your code here!
X,Y,Z,K=map(int,input().split())
A=(list(map(int,input().split())))
B=(list(map(int,input().split())))
C=sorted(list(map(int,input().split())))

ans=max(A)+max(B)+max(C)

temp=[]
for a in A:
    for b in B:
        temp.append(a+b)

temp.sort()

dif=[temp[i]-temp[-1] for i in range(len(temp))[::-1]]
dif_c=[C[i]-C[-1] for i in range(len(C))[::-1]]

dif=dif[:K]

temp=[]
for d in dif:
    for dc in dif_c:
        temp.append(ans+d+dc)
temp.sort()
temp=temp[::-1]

for k in range(K):
    print(temp[k])


Measured memory_bytes: 167172
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;
typedef long long ll;

int main() {
   int N;
   cin >> N;
   ll L[90];
   L[0] = 2;
   L[1] = 1;
   if (N == 1) cout << L[N] << endl;
   else {
      for (int i = 2; i <= N; i++) {
         L[i] = L[i - 1] + L[i - 2];
      }
      cout << L[N] << endl;
   }
   return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

struct knuth_morris_pratt {
  const string& P;
  int m;
  vector<int> fail;
  knuth_morris_pratt(const string& P_)
      : P(P_), m(P_.size()) {
    fail.resize(m + 1, -1);
    for (int i = 1, j = -1; i <= m; ++i) {
      while (j >= 0 && P[j] != P[i - 1]) j = fail[j];
      fail[i] = ++j;
    }
  }
  vector<int> match(const string& S) const {
    int n = S.size();
    vector<int> occur;
    for (int i = 0, k = 0; i < n; ++i) {
      while (k >= 0 && S[i] != P[k]) k = fail[k];
      if (++k == m) {
        /* match at s[i-m+1 ... i] */
        occur.push_back(i - m + 1);
      }
    }
    return occur;
  }
};

struct UnionFind {
  vector<int> parent;  // parent[root] is the negative of the size.
  UnionFind(int n)
      : parent(n, -1){};
  bool unite(int u, int v) {
    u = root(u);
    v = root(v);
    if (u == v) return false;
    if (parent[u] > parent[v]) swap(u, v);
    parent[u] += parent[v];
    parent[v] = u;
    return true;
  }
  bool find(int u, int v) {
    return root(u) == root(v);
  }
  int root(int u) {
    return parent[u] < 0 ? u : parent[u] = root(parent[u]);
  }
  int size(int u) {
    return -parent[root(u)];
  }
};

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  string S, T;
  while (cin >> S >> T) {
    int L = S.size() + T.size() - 1;
    string P = "";
    while (P.size() < L) P += S;
    P.resize(L);
    knuth_morris_pratt kmp(T);
    auto pat = kmp.match(P);
    UnionFind uf(S.size());
    bool inf = false;
    for (int x : pat) {
      assert(x < S.size());
      int y = (x + T.size()) % S.size();
      if (!uf.unite(x, y)) {
        inf = true;
        break;
      }
    }
    if (inf) {
      cout << -1 << endl;
    } else {
      int res = 0;
      for (int i = 0; i < S.size(); i++) res = max(res, uf.size(i) - 1);
      cout << res << endl;
    }
  }
  return 0;
}


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

int main() {
	int h, w;
	cin >> h >> w;
	bool col[w];
	bool row[h];
	char hw[h][w];
	char ret[h][w];
	for(int i = 0; i < w; i++) {
		col[i] = false;
	}
	for(int i = 0; i < h; i++) {
		row[i] = false;
	}
	for(int i = 0; i < h; i++) {
		for(int j = 0; j < w; j++) {
			cin >> hw[i][j];
		}
	}
	for(int i = 0; i < h; i++) {
		row[i] = false;
		for(int j = 0; j < w; j++) {
			char v = hw[i][j];
			if(v == '#') {
				col[j] = true;
				row[i] = true;
			}
		}
	}
	for(int i = 0; i < h; i++) {
		for(int j = 0; j < w; j++) {
			if(col[j] && row[i]) cout << hw[i][j];
		}
		if(row[i]) cout << endl;
	}
	return 0;
}


Measured memory_bytes: 256
def cin; gets.split.map(&:to_i) end
def cout(*x); puts x.join(" ") end

# exit if $0 != __FILE__

class PriorityQueue
  def initialize(&compare)
    @heap = []
    if compare then
      @compare = compare
    else
      @compare = lambda {|a, b| a <=> b}
    end
  end

  def push(elem)
    push_heap(elem)
    self
  end

  def pop
    pop_heap
  end

  private
    def push_heap(elem)
      now = @heap.length
      @heap.push(elem);

      while now != 0
        parent = (now-1) / 2
        # 親と値を入れ替え
        if @compare.call(@heap[parent], @heap[now]) < 0 then
          @heap[parent], @heap[now] = @heap[now], @heap[parent]
        end
        now = parent
      end
    end

    def pop_heap
      return @heap.pop if @heap.length <= 1
      ret = @heap[0]
      @heap[0] = @heap.pop
      length = @heap.length
      now = 0

      while (left_child = 2 * now + 1) < length
        # 値の大きい子を選ぶ
        is_right_prior = 
          (left_child != length - 1 && 
            @compare.call(@heap[left_child+1], @heap[left_child]) > 0)
        swap = is_right_prior ? left_child+1 : left_child
        # 子と値を入れ替え
        if @compare.call(@heap[now], @heap[swap]) < 0 then
          @heap[now], @heap[swap] = @heap[swap], @heap[now]
        end
        now = swap
      end
      ret
    end
end

x, y, z, k = cin
$a = cin.sort.reverse << -10**18
$b = cin.sort.reverse << -10**18
$c = cin.sort.reverse << -10**18
require 'set'
$st = Set.new

def cn(x,y,z)
  r = [x,y,z,$a[x]+$b[y]+$c[z]]
  return [-1,-1,-1,-10**18] if !$st.add?(r)
  r
end

pq = PriorityQueue.new {|a,b| a[3] <=> b[3]}
pq.push(cn(0,0,0))
k.times do
  p = pq.pop
  puts p[3]
  pq.push(cn(p[0]+1,p[1],p[2]))
  pq.push(cn(p[0],p[1]+1,p[2]))
  pq.push(cn(p[0],p[1],p[2]+1))
end

    

Measured memory_bytes: 5240
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 1<<30
#define MOD 1000000007
#define mod 10007
#define REP(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define REPE(i, a, n) for (ll i = a; i <= (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<int,int>Pin;
typedef pair<ll,ll>Pll;
template<class T> using V=vector<T>;
long long GCD(long long a, long long b) {return b?GCD(b,a%b):a;}
long long LCM(long long a, long long b) {return a/GCD(a,b)*b;}
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int ddx[8]={-1,0,1,0,1,1,-1,-1};
int ddy[8]={0,-1,0,1,1,-1,1,-1};
ll cmp(pair<ll,ll>a,pair<ll,ll> b){
        if(a.se!=b.se)
        return a.se<b.se;
        else
        return a.fi<b.fi;
}
//----------------------------------------------------------------------

//----------------------------------------------------------------------
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------  
    //ll begin_time=clock();
    //------------------------------
    string s;cin>>s;
    while(s!="0"){
        int ans=0;
        for(int i=0;i<s.length();i++){
            ans+=s[i]-'0';
        }
        cout<<ans<<endl;
        cin>>s;
    }
    //-------------------------------  
    //ll end_time=clock();cout<<"time="<<end_time-begin_time<<"ms"<<endl;
    //-------------------------------
    return 0;
}
//----------------------------------------------------------------------


































Measured memory_bytes: 3252
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>
#include<map>
#include<set>
#include<cstdlib>
#include<cmath>
#include<numeric>
#include<iomanip>
#include<functional>
#include<cstdlib>
#include<queue>
#include<deque>
#include <iterator>     // std::back_inserter
const double PI = acos(-1);
using namespace std;
using ll =long long;
#define rep(i,n)for(ll i=0;i<(n);i++)
const int mod = 1000000007;
const ll inf = 1e18 + 1;
int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

ll gcd(ll a, ll b) {
	if (a % b == 0) {
		return b;
	}
	else {
		return gcd(b, a % b);
	}
}
ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
};
//fixed << setprecision(2)
template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

/*コンビネーション*/

//ll f[101010], rf[101010];
//ll inv(ll x) {
//	ll res = 1;
//	ll k = mod - 2;
//	ll y = x;
//	while (k) {
//		if (k & 1) res = (res * y) % mod;
//		y = (y * y) % mod;
//		k /= 2;
//	}
//	return res;
//}
//void init() {
//	f[0] = 1;
//	for (ll i = 1; i < 101010;i++) f[i] = (f[i - 1] * i) % mod;
//	for(ll i = 0; i < 101010; i++) rf[i] = inv(f[i]);
//}
////---------------------------------------------------------------------------------------------------
//ll C(int n, int k) {
//	ll a = f[n]; // = n!
//	ll b = rf[n - k]; // = (n-k)!
//	ll c = rf[k]; // = k!
//
//	ll bc = (b * c) % mod;
//
//	return (a * bc) % mod;
//}

/*コンビネーション*/

/*Union Find*/
#define MAX_N 200000
#define MAX_M 200000
vector<ll>par(MAX_N);
vector<ll>ran(MAX_N);
void init(ll N) {
	rep(i, N) {
		par[i] = i;
		ran[i] = 0;
	}
}
ll find(ll x) {
	if (par[x] == x) {
		return x;
	}
	else {
		return par[x] = find(par[x]);
	}
}
//xとyの属する集合を併合
void unite(ll x,ll y) {
	x = find(x);
	y = find(y);
	if (x == y)return;
	if (ran[x] < ran[y]) {
		par[x] = y;

	}
	else {
		par[y] = x;
		if (ran[x] == ran[y])ran[x]++;
	}
}
bool same(ll x, ll y) {
	return find(x) == find(y);
}
/*Union Find*/
//小文字=大文字+32
int main() {
	ll N; cin >> N;
	vector<ll>H(N);
	rep(i, N) {
		cin >> H[i];
	}
	int m = 0;
	int res=0;
	rep(i, N) {
		if (H[i] >= m) {
			m = H[i];
			res++;
		}
	}
	cout << res;

}

Measured memory_bytes: 6208
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,m,n) for(int (i)=(m);(i)<(n);++(i))
#define rREP(i,m,n) for(int (i)=(n)-1;(i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 1000000001;
constexpr ll mod = 1000000007;
constexpr double PI = 3.1415926535897932;
template<class T>inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T>inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

int main() {
	init();

	int A, B, C, D; cin >> A >> B >> C >> D;
	A += B;
	C += D;
	if (A < C)puts("Right");
	else if (A > C)puts("Left");
	else puts("Balanced");

	return 0;
}

Measured memory_bytes: 3588
#include "bits/stdc++.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> Pll;
typedef pair<P,P> PP;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define repr(i,a,n) for(ll i = n-1;i >= a;i--)
#define LINF (ll)1e17
#define INF 1e9
#define MOD (ll)1e9+7
#define sMOD 1e5
#define fs first
#define sc second
#define setprecision(d) cout << fixed << setprecision(d);

ll gcd(ll a,ll b){
	if(!b) return a;
	return gcd(b,a%b);
	
}

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


signed main(){

	string s;
	cin >> s;
	ll n = s.size();

	rep(i,0,n/2){
		//cout << n-i-1 << " " << i << endl;
		if(s[n-i-1] != s[i]){
			cout << "No" << endl;
			return 0;
		}
	}

	rep(i,0,n/4){
		//cout << n/2-i-1 << " " << i << endl;
		if(s[n/2-i-1] != s[i]){
			cout << "No" << endl;
			return 0;
		}
		
	}

	rep(i,0,n/4){
		//cout << n-i-1 << " " << n/2+1+i << endl;
		if(s[n-i-1] != s[n/2+1+i]){
			cout << "No" << endl;
			return 0;
		}
	}

	cout << "Yes" << endl;

    return 0;
}

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

int main(){
  int N,c=1,b=0;
  cin >> N;
  
  vector <int> a(N);
  
  rep(i,N){
    cin >> a.at(i);
  }
  
  rep(i,N){
    if(a.at(i)==c){
      b++;
      c++;
    }
  }

 if(b==0)
   cout << "-1" << endl;
 else
   cout << N-b << endl;
  
}

Measured memory_bytes: 1024
#include <cstdio>

inline int abs(int x)
{
	return (x > 0) ? x : -x;
}

int main()
{
	int N, X[1000], Y[1000];
	int i, j, odd, m = 1;
	long long u, v, tmp, length = 0;

	std::scanf("%d", &N);
	for (i = 0; i < N; i++) {
		std::scanf("%d %d", X + i, Y + i);
		tmp = abs(X[i]) + abs(Y[i]);
		if (tmp > length)
			length = tmp;
	}

	odd = (abs(X[0]) + abs(Y[0])) & 1;
	for (i = 1; i < N; i++)
		if (((abs(X[i]) + abs(Y[i])) ^ odd) & 1) {
			std::printf("-1\n");
			return 0;
		}

	tmp = 1, length -= !odd;
	while (tmp < length) {
		tmp *= 2;
		m++;
	}
	length = tmp;

	std::printf("%d\n", m + !odd);
	for (i = 0; i < m; i++) {
		std::printf("%lld ", tmp);
		tmp >>= 1;
	}
	if (!odd)
		std::printf("1");
	std::putchar('\n');

	for (i = 0; i < N; i++) {
		X[i] -= !odd;
		u = X[i] + Y[i], v = X[i] - Y[i], tmp = length;
		for (j = 0; j < m; j++) {
			if (u > 0) {
				if (v > 0) {
					std::putchar('R');
					u -= tmp, v -= tmp;
				}
				else {
					std::putchar('U');
					u -= tmp, v += tmp;
				}
			}
			else {
				if (v > 0) {
					std::putchar('D');
					u += tmp, v -= tmp;
				}
				else {
					std::putchar('L');
					u += tmp, v += tmp;
				}
			}
			tmp /= 2;
		}
		if (!odd)
			std::putchar('R');
		std::putchar('\n');
	}

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    long long int n;
    cin>>n;
    long long int w;
    cin>>w;
    vector<long long int> W(n+1,0);
    vector<long long int> V(n+1,0);
    for(int i=1;i<=n;i++)
    {
        cin>>W[i]>>V[i];
    }
    vector<vector<long long int>> dp(n+1,vector<long long> (w+1,0));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=w;j++)
        {
            if(W[i]<=j)
            {
                dp[i][j]=max(dp[i-1][j-W[i]]+V[i],dp[i-1][j]);
            }
            else
            {
                dp[i][j]=dp[i-1][j];
            }
        }
        // cout<<dp[i][w];
    }
    cout<<dp[n][w];

}

Measured memory_bytes: 82744
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<ll> A(N);
  FOR(i,0,N) {
    cin >> A[i];
    A[i] -= i + 1;
  }
  sort(A.begin(), A.end());
  int b;
  if(N % 2 == 1){
    b = A[N/2];
  } else {
    b = (A[N/2] + A[N/2-1]) / 2;
  }
  ll ans = 0;
  FOR(i,0,N){
    ans += abs(A[i] - b);
  }
  cout << ans << endl;
}

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

int const maxn = 101;
int const maxv = 1010;
long long const inf = 0x3f3f3f3f3f3f3f3f;

struct Item {
    int w, v;
};

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

    int n, s;
    std::cin >> n >> s;

    std::vector<Item> items(n);
    int maxv = 0;

    for (auto& i  : items) {
        std::cin >> i.w >> i.v;
        maxv += i.v;
    }

    std::vector<long long> dp(maxv+1, inf);
    dp[0] = 0;

    for (auto item : items) {
        for (int i = maxv; i >= item.v; i--) {
            dp[i] = std::min(dp[i], dp[i - item.v] + item.w);
        }
    }

    int ans = 0;
    for (int i = 0; i <= maxv; i++) {
        if (dp[i] <= s) {
            ans = i;
        }
    }

    std::cout << ans << "\n";
}

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

//input
long long int L, R;
vector<long long int> v; 

int main(){
    cin >> L >> R;
    
    for (int i = L; i < min(R + 1, L + 2019); ++i){
        v.push_back(i % 2019);
    }
    
    long long ans = 2019;
    for (int i = 0; i < v.size(); ++i) {
        for (int j = i + 1; j < v.size(); ++j) {
            ans = min(ans, v[i] * v[j] % 2019);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define TRACE(x) cerr << #x << " = " << x << endl
#define REP(i, n) for (int i=0; i<n; i++)
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define _ << " " <<

typedef long long ll;
typedef pair<int, int> P;
#define X first
#define Y second

const int MAX = 2005;

const int MOD = 1e9 + 7;

int add(int a, int b)
{
  a += b;
  if (a >= MOD)
    a -= MOD;
  return a;
}

int sub(int a, int b)
{
  a -= b;
  if (a < 0)
    a += MOD;
  return a;
}

int mul(int a, int b)
{
  return (int) (((ll) a * b) % MOD);
}

int dp[MAX][MAX];
int sum[MAX][MAX];
int n, m, k;
int dp2[MAX][MAX];

int eval_gor(int r, int s)
{
  if (r < 0) return 0;
  if (s < 0) {
    r += s;
    s = 0;
  }

  if (r >= 0 && s >= 0) return sum[r][s];
  return 0;
}

int eval_dol(int r, int s)
{
  if (r >= 0 && s >= 0) return sum[r][s];
  return 0;
}

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

  REP(i, n+1) {
    REP(j, m+1) {
      if (i % (k - 1) == 0 && j % (k - 1) == 0 && i < n && j < m)
	dp[i][j] = 1;

      int raz = k - 1, poc = 0;
      if (i == n && j == m) {
	raz = k;
	poc = 1;
      }
     
      dp[i][j] = add(dp[i][j], eval_gor(i - poc, j - (raz - poc)));
      dp[i][j] = sub(dp[i][j], eval_dol(i - k, j - raz + k));

      sum[i][j] = dp[i][j];
      if (i) sum[i][j] = add(sum[i][j], sum[i-1][j+1]);
    }
  }

  printf("%d\n", dp[n][m]);

  return 0;
}


Measured memory_bytes: 33024
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>

using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;
typedef pair<ll, ll> PLL;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

// --------------------------------------
int k;
ll bfs() {
  queue<ll> que;
  FOR(i, 1, 10) que.push(i);

  int count = 0;
  while(!que.empty()) {
    ll p = que.front(); que.pop();
    count++;
    if(count == k) return p;

    if(p % 10 > 0) que.push(p * 10 + (p % 10) - 1);
    que.push(p * 10 + (p % 10));
    if(p % 10 < 9) que.push(p * 10 + (p % 10) + 1);
  }
}

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

  cin >> k;
  cout << bfs() << endl;
}


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

int main() {
  int64_t N; int64_t syou;
  int amari = 0;
  cin >> N;
  vector<int>vec(0);
  for(int i = 0; i<20; i++){
    syou = (N-1)/26;
    amari = (N-1)%26;
    
    vec.push_back(amari);
    
    N = syou;
    if(N == 0){
      break;
    }
  }
  
  reverse(vec.begin(), vec.end());
  
  for(int i=0; i<vec.size(); i++){
    cout << (char)('a' + vec.at(i));
  }
  
}

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

int main(){
    int n;
    cin>>n;
    int ans = 0;
    rep(i,n){
        int a;
        cin>>a;
        while(a%2==0){
            a/=2;
            ans ++;
        }
    }
    
    
    cout<< ans <<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#define WIDTH (12)
#define HEIGHT (12)
#define BUFSIZE (16)

int solve(int map[HEIGHT][WIDTH]) {
	int x, y, n = 0;
	char set[HEIGHT * WIDTH] = {0};

	for (y = 0; y < HEIGHT; y++) {
		for (x = 0; x < WIDTH; x++) {
			if (!map[y][x]) {
				continue;
			}
			if (y && map[y-1][x]) {
				map[y][x] = map[y-1][x];
			}
			else if (x && map[y][x-1]) {
				map[y][x] = map[y][x-1];
			}
			else {
				n += 1;
				set[n] = 1;
				map[y][x] = n;
			}
		}
		for (x = 10; x >= 0; x--) {
			if (map[y][x] && map[y][x+1] && map[y][x] != map[y][x+1]) {
				set[map[y][x]] = 0;
				map[y][x] = map[y][x+1];
			}
		}
	}
	for (x = y = 0; y < HEIGHT * WIDTH; y++) {
		x += set[y];
	}
	return x;
}

int main(void) {
	int map[HEIGHT][WIDTH], x, y;
	char s[BUFSIZE];

	while (1) {
		for (y = 0; y < HEIGHT; y++) {
			fgets(s, BUFSIZE, stdin);
			for (x = 0; x < WIDTH; x++) {
				map[y][x] = s[x] - '0';
			}
		}
		printf("%d\n", solve(map));
		if (fgets(s, BUFSIZE, stdin) == NULL) {
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 524
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=110;
int n;
int a[maxn];

int main() {
    scanf("%d",&n);
    int mn=1000,mx=0;
    int ans=1e9;
    for (int i=1;i<=n;i++) scanf("%d",&a[i]),mn=min(mn,a[i]),mx=max(mx,a[i]);
    for (int i=mn;i<=mx;i++) {
        int sum=0;
        for (int j=1;j<=n;j++) 
            sum+=(a[j]-i)*(a[j]-i);
        ans=min(ans,sum);
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <string>

using namespace std;

bool can_match(const vector<long long>& water, long long first_rain)
{
  long long rain = first_rain;
  for (long long i = 0; i < (long long)water.size(); i++) {
    rain = 2 * (water.at(i) - rain / 2);
  }
  return first_rain <= rain;
}

int main()
{
  long long n;
  cin >> n;
  vector<long long> water(n);
  for (long long i = 0; i < n; i++) {
    cin >> water.at(i);
  }
  long long ok = 0;
  long long ng = water.at(0)*2+1;
  while (abs(ok - ng) > 1) {
    long long mid = (ok + ng) / 2;
    if (can_match(water, mid)) {
      ok = mid;
    } else {
      ng = mid;
    }
  }
  long long rain = ok;
  cout << rain;
  for (long long i = 0; i+1 < n; i++) {
    rain = 2 * (water.at(i) - rain / 2);
    cout << ' ' << rain;
  }
  cout << '\n';
  return 0;
}


Measured memory_bytes: 2048
/*  CREATED BY
    STREAM_CIPHER
    19-sep-2020
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define double long double
#define debug1(a) cout<<#a<<"="<<(a)<<"\n"
#define debug2(a,b) cout<<#a<<"="<<(a)<<","<<#b<<"="<<(b)<<"\n"
#define debug3(a,b,c) cout<<#a<<"="<<(a)<<","<<#b<<"="<<(b)<<","<<#c<<"="<<(c)<<"\n"
#define fix_precision(n) cout<<fixed<<setprecision(n)
#define all(a) a.begin(),a.end()
const double pi=acos(-1.0);
int inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int mx=5*1000000;//5*64M bit ->5*8M byte ->40MB size for long long int (64 bit)
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        // freopen("output.txt","w",stdout);
    #endif
        string a;
        cin>>a;
        cout<<a;
        if(a[a.size()-1]=='s')
            cout<<"es";
        else
            cout<<"s";
}

Measured memory_bytes: 3616
require 'pp'
require 'set'

N,M = readline.chomp.split.map(&:to_i)

#union find
$par = Array.new(N) {|i| i}
$rank = Array.new(N,0)

def find(x)
  if $par[x] == x 
    return x
  else
    $par[x] = find($par[x])
    return $par[x]
  end
end

def unite(x,y)
  x = find(x)
  y = find(y)
  return if x == y

  if $rank[x] < $rank[y]
    $par[x] = y
  else
    $par[y] = x
    $rank[x] += 1 if $rank[x] == $rank[y]
  end
end

$edges = Array.new(N) { Array.new }
M.times do |i|
  i,j,w = readline.chomp.split.map(&:to_i)
  unite(i-1, j-1)
end

roots = Set.new
N.times do |i|
  roots << find(i)
end

puts roots.size



Measured memory_bytes: 17660
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>
#include <cstdint>



#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rrep(i, n) for(ll i = (ll)(n-1); i >= 0; i--)
#define repi(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rrepi(i,a,b) for(ll i=(ll)(b-1);i>=(ll)(a);i--)

#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n;cin>>n;
  ll res=1e9;
  vector<pair<ll,ll>>ab(n);
  rep(i,n)cin>>ab[i].first;
  rep(i,n)cin>>ab[i].second;
  rep(i,n){
    if(i%2)swap(ab[i].first,ab[i].second);
  }
  vector<bool>bit(n);
  rep(i,n)if(i%2==0)bit[i]=1;
  sort(all(bit));
  do{
    vector<pair<ll,ll>>odd,even;
    ll cnt=0;
    rep(j,n){
      if(bit[j])even.push_back({ab[j].first,j});
      else odd.push_back({ab[j].second,j});
    }
    sort(all(even));
    sort(all(odd));
    vector<pair<ll,ll>>c(n);
    rep(j,n){
      if(j%2){
        c[j]=odd[j/2];
      }
      else {
        c[j]=even[j/2];
      }
      //cout<<"even"<<even[j/2].second<<endl;
    }
    ll f=1;
    rep(j,n-1){
      if(c[j+1].first<c[j].first)f=0;
    }
    rep(j,n){
      repi(k,j+1,n){
        if(c[j].second>c[k].second)cnt++;
      }
    }

    //cout<<i<<endl;


    if(f)chmin(res,cnt);
  }while(next_permutation(all(bit)));
  if(res==1e9)res=-1;

  cout<<res<<endl;
  return 0;

}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;

public class Main {
	static long[][] memo;;
	static int h;
	static int w;
	static String[][] input;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		String[] str = br.readLine().split(" ");
		h = Integer.parseInt(str[0]);
		w = Integer.parseInt(str[1]);
		memo = new long[h][w];
		for (int i = 0; i < h; i++)
			Arrays.fill(memo[i], -1);
		input = new String[h][w];
		for (int i = 0; i < h; i++)
			input[i] = br.readLine().split("");
		out.println(dp(0, 0));
		out.flush();
	}

	public static long dp(int x, int y) {
		if (x == h - 1 && y == w - 1)
			return 1;

		if (x > h - 1 || x < 0  || y > w - 1 || y < 0 || input[x][y].equals("#"))
			return 0;

		if (memo[x][y] != -1)
			return memo[x][y];

		long right = 0, down = 0;

		right = dp(x + 1, y);

		down = dp(x, y + 1);

		long save = (int) 1e9 + 7;

		return memo[x][y] = (right + down)%save;
	}

}


Measured memory_bytes: 118596