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

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        List<Long> abcde = new ArrayList<>();
        for (int i = 0; i < 5; i++) {
            abcde.add(sc.nextLong());
        }
        long bottleNeckCount = 1;
        for (int i = 0; i < 5; i++) {
            long target = abcde.get(i);
            if (target >= n) {
                continue;
            }
            long ceil = (long) Math.ceil((double) n / target);
            if (bottleNeckCount == 1 || ceil > bottleNeckCount) {
                bottleNeckCount = ceil;
            }
        }
        System.out.println(bottleNeckCount + 4);
    }

}


Measured memory_bytes: 23760
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;

int ok[5100];

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n,k; cin >> n >> k;
	vector<ll> a(n);
	ll sum=0;
	for(int i=0;i<n;i++){
		cin >> a[i];
		sum+=a[i];
	}
	sort(a.begin(),a.end());
	ok[0]=1;
	for(int i=n-1;i>=0;i--){
		bool check=false;
		for(int j=0;j<k;j++){
			if(ok[j]&&j+sum>=k){
				check=true;
				break;
			}
		}
		if(check==false){
			cout << i+1 << endl;
			return 0;
		}
		sum-=a[i];
		for(int j=k-1;j>=a[i];j--){
			ok[j]=ok[j]|ok[j-a[i]];
		}
	}
	cout << 0 << endl;
	return 0;
}

Measured memory_bytes: 384
//code by lynmisakura.wish to be accepted!
/****************************/
#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<bitset>
#include <climits>
#include<set>
#include<bitset>
using namespace std;
/***************************/
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef pair<int,int> pi;
typedef vector<pair<int,int>> vpi;

const long long INF = 1LL << 55;

#define itn int
#define endl '\n'
#define pb push_back
#define mp make_pair
#define ss second
#define ff first
#define dup(x,y) ((x) + (y) - 1)/(y)
#define mins(x,y) x = min(x,y)
#define maxs(x,y) x = max(x,y)
#define all(x) (x).begin(),(x).end()
#define Rep(n) for(int i = 0;i < n;i++)
#define rep(i,n) for(int i = 0;i < n;i++)
#define rrep(i,n) for(int i = n - 1;i >= 0;i--)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
 
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll qp(ll a, ll b) { ll ans = 1; do { if (b & 1)ans = 1ll * ans*a; a = 1ll * a*a; } while (b >>= 1); return ans; }
ll qp(ll a, ll b, int mo) { ll ans = 1; do { if (b & 1)ans = 1ll * ans*a%mo; a = 1ll * a*a%mo; } while (b >>= 1); return ans; }
 
#define _GLIBCXX_DEBUG
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main(void){
   int n,k;cin >> n >> k;
   string s;cin >> s;
   int r = 0;
   int l = 0;
   int x = 0;
   //int h = 0;
   
   for(int i = 1;i < n;i++){
      if(s[i] != s[i-1]) x++;
   }
   int p;
   if(2*k < x){
      p = 2*k;
   }else{
      p = x;
   }
   //int p = min(x/2,k);
   cout << n - x + p - 1 << endl;
   return 0;
}

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

int main(){
    int A,B,C,X,Y;
    int min_c=100000000000;
    cin>>A>>B>>C>>X>>Y;

        for(int i=0;i<=max(X,Y);++i){
            int sum=2*C*i+A*max(0,X-i)+B*max(0,Y-i);
            min_c=min(min_c,sum);
        }
     cout<<min_c;
    

}

Measured memory_bytes: 3156
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
#define rep(begin, i, end) for (ll i = begin; i < (ll)(end); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1000000007;

int main()
{
    string s, t;
    cin >> s >> t;
    ll N = s.size();
    ll ans = 0;
    rep(0, i, N)
    {
        if (s.at(i) != t.at(i))
        {
            ans++;
        }
    }
    cout << ans << endl;
}

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

int main(){
	
	int A1 , B1 , C2 , D2 , area1 , area2;
	
	scanf("%d %d", &A1 , &B1);
	area1= A1 * B1 ;
	
	scanf("%d %d", &C2 , &D2);
	area2= C2 * D2 ;
	
	if(area1 > area2)
	  	printf("%d" , area1);
	else if(area1 < area2)
	    printf("%d" , area2);
	else
	    printf("%d" , area1);    
	
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections.Generic;
namespace Collections
{
	class program
	{
    //static long MAX_LONG = 5000000000000000;
		static void Main(string[] args)
		{

			// 入力
			int N = int.Parse(Console.ReadLine());
      int[] input = Console.ReadLine().Split().Select(p => int.Parse(p)).ToArray();

			int ret = 0;
			for(int i = 0; i<input.Length; i++)
			{
				while(input[i]%2 == 0)
				{
					ret++;
					input[i] /= 2;
				}
			}
			Console.WriteLine(ret + "");
    }
	}
}


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

#define ran 101101

int n, m;
int id;
char res[11];

bool ac[ran];
int cnt[ran];
int tot_a, tot_p;

int main() {
	scanf("%d%d", &n, &m);
	for(int i=0;i<m;i++) {
		scanf("%d%s", &id, res);
		if(res[0]=='W') {
			if(!ac[id]) cnt[id]++;
		} else
		if(res[0]=='A' && !ac[id]) {
			tot_a ++;
			tot_p += cnt[id];
			ac[id] = true;
		}
	}
	printf("%d %d\n", tot_a, tot_p);
	
	return 0;
}

Measured memory_bytes: 768
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<vector>
#include<queue>
#include<cmath>

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n-1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(a, n) sort(a, a+n)
#define VSORT(v) sort(v.begin(), v.end())
#define MAX(a, n) *max_element(a, a+n)

using namespace std;

int main()
{
    int N, W;

    cin >> N >> W;

    long w[N];
    int v[N];

    REP(i, N) {
        cin >> w[i] >> v[i];
    }

    long val[N+1][N*1000+1];
    val[0][0] = (long)0;
    FOR(j, 1, N*1000+1) {
        val[0][j] = 1000000000000;
    }

    long ansval;

    FOR(i, 1, N+1) {
        REP(j, N*1000+1) {
            if(j < v[i-1]) { val[i][j] = (long)val[i-1][j]; }
            else { val[i][j] = (long)min(val[i-1][j], val[i-1][j-v[i-1]] + w[i-1]); }
            if((i == N) && (val[i][j] <= W)) { ansval = (long)j; }
        }
    }

    cout << ansval << endl;

    return 0;
}

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

int main()
{
	string str;
	while (cin >> str, str != "#") {
		long long rsi = 0, rbo = 1;
		int si = 90, bo = 1;
		for (int j = str.length() - 1; j >= 0 ; j--) {
			if (str[j] == 'h') {
				if (rsi != 0) {
					rsi = rsi * bo / rbo - si;
					rbo = bo;
				}
				j -= 4;
			}
			else if (str[j] == 't') {
				if(rsi / rbo != 90) {
					rsi = rsi * bo / rbo + si;
					rbo = bo;
				}
				j -= 3;
			}
			if (si & 1)
				bo *= 2;
			else
				si /= 2;
		}
		if (rbo == 1)
			cout << rsi << endl;
		else
			cout << rsi << "/" << rbo << endl;
	}
	return 0;
}

Measured memory_bytes: 3092
#include<bits/stdc++.h>
#define PB push_back
#define PII pair<int,int>
#define FI first
#define SE second
#define si(a) scanf("%d",&a)
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF = 0x3f3f3f3f;
const double pi=acos(-1),eps=1e-8;
const int maxn = 1<<17;
const int mod = 1e9+7;
const int N = 2e5+5;
int euler[N];
LL gcd(LL a,LL b){
    return b?gcd(b,a%b):a;
    //高精度 return b?gcd(b,a-b):a;
}
LL lcm(LL a,LL b){
    return a*b/gcd(a,b);
}
LL a[N],sum[N];
LL pre[N],pos[N];
int main(){
	int n,m;
	cin>>n;
	m=(n+999)/1000;
	cout<<m*1000-n<<endl;
	return 0;
}

Measured memory_bytes: 3608
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void){
    // Your code here!
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    
    sort(a.begin(), a.end());
    int res = a[n - 1] - a[0];
    cout << res << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<cstring>
//#define Mfc_Tanzim
#define ll long long
#define ull unsigned long long
#define pb push_back
#define ff first
#define ss second
#define all(v) (v.begin(), v.end())
#define pi acos(-1.0)
#define FastRead ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define bug(a) cerr << #a << " : " << a << endl
using namespace std;
const ll mx = 4010;

ll posx[] = {1,-1, 0, 0};
ll posy[] = {0, 0, 1,-1};

int main()
{
    FastRead

#ifdef Mfc_Tanzim
    freopen("input.txt","r", stdin);
    // freopen("output.txt","w", stdout);
#endif /// Mfc_Tanzim

    ll t = 1, n, k, l, r, d;
    //cin >> t;

    while(t--){
        cin >> n;
        ll ans = 0;
        vector<int>v(n);
        for(auto &i: v){
            cin >> i;
        }
        for(ll i=0; i<v.size(); i++){
            if(i%2==0 && v[i]&1){
                ans++;
            }
        }
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 3656
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <ctype.h>
#include <stdlib.h>


using namespace std;


int main(){
    int a,b;
    cin >> a >> b;
    int ans = abs(a - b);
    if(ans % 2 == 0){
        if(a < b){
            cout << abs(a + (ans / 2)  )<< endl;
        }else{
            cout << abs(b + (ans / 2)  )<< endl;
        }
    }else{
        cout << "IMPOSSIBLE" << endl;
    }


}


Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<iomanip>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n - 1);
    vector<int> ans(n);
    for (int i = 0; i < n - 1; i++) {
        cin >> a[i];
        ans[a[i]]++;
    }
    for (int i = 1; i < n; i++) {
        cout << ans[i] << endl;
    }
    cout << 0 << endl;
    return 0;
}

Measured memory_bytes: 4840
#include<iostream>
#include<stdio.h>//printf("%.9f\n",*********);
#include<vector>//文字列.erase(n),vector
#include<algorithm>//next_permutation
#include<set>
#include<string>//char(小文字-32=大文字) to_string,string,char
#include<sstream>
#include<complex>
#include<time.h>
#include<random>
#include<cmath>//min,max
#include<math.h>
#include<queue>
#include<time.h>
#include<iomanip>
#include<locale>
#include<utility>//swap
#define rt "\n"
#define rep(i,n) for(int i=0;i<n;i++)
#define rop(i,n) for(int i=1;i<=n;i++)//start==1
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define drop(i,n) for(int i=n;0<i;i--)//end==1
#define yes(ans) if(ans)cout<<"yes"<<rt;else cout<<"no"<<rt;
#define Yes(ans) if(ans)cout<<"Yes"<<rt;else cout<<"No"<<rt;
#define YES(ans) if(ans)cout<<"YES"<<rt;else cout<<"NO"<<rt;
#define Yay(ans) if(ans)cout<<"Yay!"<<rt;else cout<<":("<<rt;
#define sec(a,b,ans) if(ans)cout<<a<<rt;else cout<<b<<rt;
#define vcin(s,n) rep(i,n)cin>>s[i];//vcin(配列名),(繰り返し回数)
#define sort(s) sort(s.begin(),s.end())//標準=昇順
#define reve(s) reverse(s.begin(),s.end())//反転
#define str string
#define please return
#define AC 0
#define rapid_pleaseAC_fast cin.tie(0);ios::sync_with_stdio(false)
#define pi 3.1415926535897932384626//pi
#define nine 1000000000//10^9

using namespace std;
typedef vector<int> vint;
typedef long double ldouble;
typedef vector<string> vstr;
typedef vector<char> vchar;
typedef vector<double> vdou;
typedef vector<double> vdouble;
typedef long long int llint;
typedef pair<int, int> pint;
typedef pair<llint, llint> pllint;
typedef vector<llint> vllint;
typedef vector<pint> vpint;
typedef vector<pair<llint, llint>> vpllint;
typedef vector<vector<int>> vvint;
typedef vector<vector<char>> vvchar;
typedef vector<vector<double>> vvdouble;
typedef vector<vector<llint>> vvllint;
typedef vector<vector<string>> vvstr;
typedef vector<vector<bool>> vvbool;
typedef vector<vector<pint>> vvpint;
typedef vector<bool> vbool;

long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

long long LCM(long long a, long long b) {
	return a * b / GCD(a, b);
}

unsigned GetDigit(unsigned num) {
	return std::to_string(num).length();
}

int tow(int n) {//2のn乗
	if (n == 0)return 1;
	int x = tow(n / 2);
	x *= x;
	if (n % 2 == 1)x *= 2;
	return x;//@domino
}

int SED(int n) { //Sum of Each Digit
	int sum = 0;
	while (n > 0) {
		sum += n % 10; n /= 10;
	}
	return sum;
}

unsigned ND(unsigned num) {//Number of Digits
	return std::to_string(num).length();//outmax=10
}//stringのほうが効率よくないか？

/*

 (char)toupper(a[n])=文字列のn文字目を大文字で出力

  pow(a,b)=aのb乗

  */


int main(void) {
	rapid_pleaseAC_fast;

	int w, a, b;
	cin >> w >> a >> b;

	if (abs(b - a) <= w) {
		cout << 0 << rt;
		return 0;
	}

	int x = max(a, b);
	int y = min(a, b);

	cout << x - (y + w) << rt;

	please AC;
}

Measured memory_bytes: 256
x, y = map(int, input().split())
a = [1,3,5,7,8,10,12]
b = [4,6,9,11]
c = [2]
if x in a and y in a or x in b and y in b or x in c and y in c:
    ans = "Yes"
else:
    ans = "No"
print(ans)

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

int main(){
  int H,A,c=0;
  cin >> H >> A;
  
  while(H>0){
    H-=A;
    c++;
  }
  cout << c++ << endl;
}

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

int main() {
    ll N, A, B;
    cin >> N >> A >> B;
    ll ans = B * (N - 2) - A * (N - 2) + 1;
    if ((A != B && N == 1) || A > B) ans = 0;
    cout << ans << endl;
}

Measured memory_bytes: 3620
#include<iostream>
#include<stack>

using namespace std;

int main(){

    int N;
    cin>> N;
    string S[N];
    for(int i=0; i<N; i++) cin>> S[i];

    stack<int> s;
    for(int i=0; i<N; i++){
        if(S[i]=="A"){
            s.push(1);
        }else{
            if(s.empty()){
                cout<< "NO"<< endl;
                return 0;
            }
            s.pop();
        }
    }

    cout<< (s.empty()? "YES": "NO")<< endl;

    return 0;
}

Measured memory_bytes: 3168
from copy import copy

while(1):
    n,m_ = [int(i) for i in input().split()]
    if n == 0 and m_ == 0:
        break
    m = m_ -1
    potato = [i+1 for i in range(n)]
    while(1):
        l = len(potato)
        if l == 1:
            print(potato[0])
            break
        pivot = (m+1)%l
        if pivot != 0:
            potato = copy(potato[pivot:] + potato[:pivot-1])
        else:
            potato = copy(potato[:-1])



Measured memory_bytes: 6336
N = int(input())
A = list(map(int,input().split()))
A.insert(0,0)
B = [0 for _ in range(N+1)]
B[N//2+1:] = A[N//2+1:]
for i in range(N//2,0,-1):
    tot = 0
    for j in range(2*i,N+1,i):
        tot += B[j]
    B[i] = (A[i]+tot)%2
C = []
M = 0
for i in range(1,N+1):
    if B[i]==1:
        M += 1
        C.append(i)
print(M)
if M!=0:
    print(*C)

Measured memory_bytes: 14136
#include<stdio.h>
int main()
{
    int n,i,j,s,step,a[100];
    while(scanf("%d",&n)==1)
    {
        step=0;
        for(i=0; i<n; i++)
            scanf("%d",&a[i]);
        for(i=0; i<n; i++)
        {
            for(j=n-1; j>=i+1; j--)
            {
                if(a[j]<a[j-1])
                {
                    s=a[j];
                    a[j]=a[j-1];
                    a[j-1]=s;
                    step++;
                }
            }
        }
        for(i=0; i<n; i++)
        {
            printf("%d",a[i]);
            if(i<n-1)
                printf(" ");
        }

        printf("\n%d\n",step);
    }




    return 0;
}

Measured memory_bytes: 2760
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cmath>
#include <climits>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int) n; i++)
#define rep1(i, n) for(int i = 1; i <= (int) n; i++)
#define all(v) v.begin(),v.end()

int main() {
    ll a,b,c,k;
    cin >> a >> b >> c >> k;
    ll ans = min(a,k);
    k -= (ans+b);
    if (k > 0) {
        ans -= k;
    }
    cout << ans << endl; 
    return 0;
}

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

int main(){
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    sort(a.begin(), a.end());
    ll max_sum = a[n-1];
    ll min_sum = a[0];
    vector<pair<ll, ll>> ans;
    rep(i, n-2) {
        if ( a[i+1] >= 0 ) {
            ans.emplace_back(min_sum, a[i+1]);
            min_sum -= a[i+1];
        }
        else {
            ans.emplace_back(max_sum, a[i+1]);
            max_sum -= a[i+1];
        }
    }
    ans.emplace_back(max_sum, min_sum);
    cout << max_sum - min_sum << endl;
    rep(i, n-1) printf("%lld %lld\n", ans[i].first, ans[i].second);
    return 0;
}


Measured memory_bytes: 4336
n, k = map(int, input().split())
*H, = map(int, input().split())
DP = [0 for i in range(n)]
for i in range(1, n):
    DP[i] = min([DP[i-j]+abs(H[i]-H[i-j]) for j in range(1, min(i, k)+1)])
print(DP[n-1])


Measured memory_bytes: 59232
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int> v[N];
priority_queue<int> q;
int main()
{
    int n,m; cin>>n>>m;
    int a,b;
    for(int i=0;i<n;++i){
    	cin>>a>>b;
    	if(m-a+1<1) continue;
    	v[m-a+1].push_back(b);
    }
    int anx=0;
    for(int i=m;i>=1;--i){
    	for(int j=0;j<v[i].size();++j){
    		q.push(v[i][j]);
    	}
    	if(!q.empty()){
    		anx+=q.top();q.pop();
    	}
    }
    cout<<anx<<"\n";
}

Measured memory_bytes: 8912
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
using namespace std;
#define REP(i, a, n) for(int i=a; i<n; i++)

int main()
{
	string S;
	cin >> S;

	set<char> str;
	REP(i, 0, S.size()) {
		str.insert(S[i]);
	}
	if (S.size() == str.size()) cout << "yes" << endl;
	else cout << "no" << endl;

	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <numeric>
#include <functional>
#include <array>
#include <map>
#include <set>

#define INF 1000000007 //1000000000000000003
#define MOD 1000000007
#define MAX 2000005

#define ll long long

//printf("%.10f", );
//cout << fixed << setprecision(10) << heikin << endl;
//vector<vector<int>> data(3, vector<int>(4, -1));
//left + 1 < top

using namespace std;
using P = pair<int, int>;
using Pc = pair<double, int>;
using T = tuple<int, int, int>;
using edge = struct { int to; long long dist; };
const double PI = 3.141592653589793;
long long fact[MAX], inv[MAX];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };

//////////////////////////////////

vector<vector<int>> bingo(3, vector<int>(3));
vector<vector<int>> tree(100005);
int color[100005];
map<P, int>colorMap;
int m = 0;

struct BridgeInfo {
	int town1;
	int town2;
	int year;
	BridgeInfo(int t1, int t2, int y) {
		town1 = t1;
		town2 = t2;
		year = y;
	}
};

struct People {
	int index;
	int town;
	int year;
	People(int i, int t, int y) {
		index = i;
		town = t;
		year = y;
	}
};

bool compare_by_second(pair<int, int> a, pair<int, int> b) {
	if (a.second != b.second) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}

struct UnionFind {
	vector<int>uf;

	UnionFind(int size) :uf(size, -1) {};

	int root(int target) {
		if (uf[target] < 0)return target;
		else return uf[target] = root(uf[target]);
	}

	void merge(int a, int b) {
		a = root(a);
		b = root(b);
		if (a == b)return;
		if (uf[b] < uf[a])swap(a, b);
		uf[a] += uf[b];
		uf[b] = a;
	}
};

ll CalcPow(ll num, ll power) {
	if (power == 0)return 1;
	if (power % 2 == 0) {
		ll half = CalcPow(num, power / 2);
		return (half * half) % MOD;
	}
	else return (num * CalcPow(num, power - 1)) % MOD;
}

ll combination(ll all, ll select) {
	if (all < select) return 0;
	if (all < 0 || select < 0) return 0;
	return fact[all] * (inv[select] * inv[all - select] % MOD) % MOD;
}

void initCombination(int max) {
	fact[0] = fact[1] = 1;
	for (int i = 2; i <= max; ++i) {
		fact[i] = fact[i - 1] * i % MOD;
	}

	inv[max] = CalcPow(fact[max], MOD - 2);
	for (int i = max - 1; 0 <= i; --i) {
		inv[i] = (inv[i + 1] * (i + 1)) % MOD;
	}
}

vector<ll>ans;
void dfs(string str) {
	if (3234566667 < stoll(str))return;
	char last = str[str.size() - 1];
	char add = last - 1;
	if (48 <= add && add <= 57) {
		string current = str + add;
		ans.push_back(stoll(current));
		dfs(current);
	}
	add = last;
	if (48 <= add && add <= 57) {
		string current = str + add;
		ans.push_back(stoll(current));
		dfs(current);
	}
	add = last + 1;
	if (48 <= add && add <= 57) {
		string current = str + add;
		ans.push_back(stoll(current));
		dfs(current);
	}
}

int main() {

	int K;
	cin >> K;
	for (int i = 1; i <= 9;++i) {
		ans.push_back(i);
		dfs(to_string(i));
	}
	sort(ans.begin(), ans.end());
	cout << ans[K-1] << endl;
}



Measured memory_bytes: 8820
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<cmath>	

using namespace std;

int main() {
	vector<int> hen(3);
	cin >> hen[0] >> hen[1] >> hen[2];

	sort(hen.rbegin(), hen.rend());
	if ((hen[0]) == (hen[2])) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    int H,W;
    while(1){
        cin>>H>>W;
        if(H==0&&W==0)break;
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                if((i+j)%2==0){
                    cout<<"#";
                }else{
                    cout<<".";
                }
            }
            cout<<"\n";
        }
        cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 3088
n, m = map(int, input().split())
a = sorted([list(map(int, input().split())) for i in range(n)])

ans = 0
for i in a:
    if i[1] < m:
        ans += i[0] * i[1]
        m -= i[1]
    else:
        ans += i[0] * m
        m = 0
    if m == 0:
        break
print(ans)

Measured memory_bytes: 28652
#include <iostream>
#define llint long long

using namespace std;

llint N, M, r, Q;
int a[10005][1300];
int S[10005][1300];


int main(void)
{
	while(1){
		cin >> N >> M;
		if(N == 0 && M == 0) break;
		
		for(int i = 1; i <= M; i++){
			for(int j = 0; j <= 1300; j++){
				a[i][j] = 0;
			}
		}
		
		cin >> r;
		llint t, n, m, s;
		for(int i = 1; i <= r; i++){
			cin >> t >> n >> m >> s;
			if(s == 1) a[m][t]++;
			else a[m][t]--;
		}
		for(int i = 1; i <= M; i++){
			for(int j = 1; j <= 1300; j++){
				a[i][j] += a[i][j-1];
			}
			for(int j = 1; j <= 1300; j++){
				if(a[i][j] > 0) a[i][j] = 1;
			}
			for(int j = 1; j <= 1300; j++){
				S[i][j] = S[i][j-1] + a[i][j];
			}
		}
		
		cin >> Q;
		for(int i = 1; i <= Q; i++){
			cin >> s >> t >> m;
			cout << S[m][t-1] - S[m][s-1] << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 101368
char r[99],g[99],d[99];main(c,i,j,k){
	for(;scanf("%s%s%s",r,g,d)>2;puts("")){
		for(i=j=k=0,c=g[j++];i+j<=strlen(r)+strlen(g);)if(c==d[k])k++,c=r[i++];else putchar(c),c=g[j++];
	}
exit(0);}

Measured memory_bytes: 524
n, t = map(int, input().split())
INF = 10**10
min_c = 10**10
for _ in range(n):
    ci, ti = map(int, input().split())
    if ti > t:
        continue
    min_c = min(ci, min_c)
if min_c == INF:
    print('TLE')
    exit()
print(min_c)



Measured memory_bytes: 9176
# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# import re
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
N,K = map(int,input().split())
Nset = set(list(range(1,N+1)))
okasi = []
shojisha = []
for _ in range(K):
    okasi.append(int(input()))
    shojisha.append(list(map(int,input().split())))

for lis in shojisha:
    Nset = Nset - set(lis)

print(len(Nset))
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


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

int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int w = 0, e = 0;
    rep(i, n)
    {
        if (s[i] == 'E')
            e++;
    }
    int ans = 1e9;
    rep(i, n)
    {
        if (s[i] == 'E')
            e--;
        ans = min(ans, w + e);
        if (s[i] == 'W')
            w++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3884
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
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;
}
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}
int main()
{
    int N;
    cin >> N;
    deque<int> b(N);
    for (size_t i = 0; i < N; i++)
    {
        cin >> b[i];
    }
    deque<int> ans;
    while (ans.size() < N)
    {
        for (int i = b.size() - 1; i >= 0; i--)
        {

            if (b[i] == i + 1)
            {
                ans.push_front(i + 1);
                b.erase(b.begin() + i);
                goto L;
            }
        }
        cout<<-1;
        return 0;
        L:;
    }

    for (auto &&i : ans)
    {
        cout << i << endl;
    }

    return 0;
}

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

void solve(int h, int w, int t) {
  for (int i = t; ; ++i) {
    int ah = (i == t ? h + 1 : 1);
    int aw = 151;

    while (ah < aw) {
      aw = 151;
      while (ah * ah + aw * aw > i) {
        aw--;
      }
      if (ah > aw) break;
      if (ah * ah + aw * aw == i) {
        cout << ah << " " << aw << endl;
        return;
      }
      ah++;
    }
  }
}

int main() {
  int h, w;
  while (cin >> h >> w, h) {
    int t = h * h + w * w;
    solve(h, w, t);
  }
}

Measured memory_bytes: 3092
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;

signed main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    int ans = INF;
    // pos - neg
    int sum = 0, cnt = 0;
    for(int i = 0; i < n; i++){
        sum += a[i];
        if(i % 2 == 0){
            if(sum <= 0){
                cnt += abs(sum) + 1;
                sum = 1;
            }
        }else{
            if(sum >= 0){
                cnt += abs(sum) + 1;
                sum = -1;
            }
        }
    }
    ans = min(ans, cnt);
    // neg - pos
    sum = 0;
    cnt = 0;
    for(int i = 0; i < n; i++){
        sum += a[i];
        if(i % 2){
            if(sum <= 0){
                cnt += abs(sum) + 1;
                sum = 1;
            }
        }else{
            if(sum >= 0){
                cnt += abs(sum) + 1;
                sum = -1;
            }
        }
    }
    ans = min(ans, cnt);
    cout << ans << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define CLR(a) memset(a, 0, sizeof(a))
#define DBG(x) cout<<(#x)<<"="<<x<<endl
#define FOR(i, a, b)  for(int i=(a); i<(b); i++)
#define REP(i, a, b)  for(int i=(a); i<=(b); i++)
#define DOWN(i, a, b) for(int i=(a); i>=(b); i--)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1000000009;
const int N= 5e4 +10;

ll a, b, c, k;

int main() {
	cin>>a>>b>>c>>k;
	if (k%2==1) cout<<b-a<<endl;
	else cout<<a-b<<endl;
	//cout<<1.*clock()/CLOCKS_PER_SEC<<"ms"<<"\n";
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
const ll p=1000000007;
int main(){
  ll n;
  cin >> n;
  int y=0;
  string s,t;
  cin >> s >> t;
  ll ans=1;
  int cnt=0;
  rep(i,n){
    int a;
    if(s[i]==t[i]){
      a=1;
      cnt=0;
    }
    else a=2;
    if(y==0&&a==2)ans=ans*6%p;
    else if(y==0&&a==1)ans=ans*3%p;
    else if(y==1)ans=ans*2%p;
    else if(y==2&&a==2&&cnt>0&&cnt%2==0){
      ans=ans*3%p;
    }
    y=a;
    if(y==2)cnt++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
from subprocess import*
with open('Main.java','w')as f:f.write(r"""
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
	public static class Edge {
		int e1, e2;
		public Edge (int e1, int e2) {
			this.e1 = e1;
			this.e2 = e2;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		int m = Integer.parseInt(sc.next());
		Edge[] c = new Edge[m];
		int ans = 0;
		for (int i = 0; i < m; i++)
			c[i] = new Edge(Integer.parseInt(sc.next()), Integer.parseInt(sc.next()));
		for (int i = 0; i < m; i++) {
			Edge[] d = new Edge[m - 1];
			for (int j = 0; j < i; j++)
				d[j] = c[j];
			for (int j = i; j < m - 1; j++)
				d[j] = c[j + 1];
			ans += search(n, d);
		}
		System.out.println(ans);
	}

	public static int search(int n, Edge[] d) {
		int[] already = new int[n + 1];
		Deque<Integer> p = new ArrayDeque<Integer>();
		already[d[0].e1] = 1;
		p.push(d[0].e1);
		int count = 1;
		while(!p.isEmpty()) {
			int here = p.pop();
			for (int i = 0; i < d.length; i++) {
				if (d[i].e1 == here && already[d[i].e2] != 1) {
					already[d[i].e2] = 1;
					p.push(d[i].e2);
					count++;
				}
				else if (d[i].e2 == here && already[d[i].e1] != 1) {
					already[d[i].e1] = 1;
					p.push(d[i].e1);
					count++;
				}
			}
		}
		if (count == n)
			return 0;
		else
			return 1;
	}
}
""")
call(('javac','Main.java'))
call(('java','Main'))

Measured memory_bytes: 59492
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] button = new int[n+1];
        for(int i = 1; i <= n; i++){
            button[i] = sc.nextInt();
        }
        sc.close();

        int count = 0;
        int nextButton = 1;
        boolean success = false;
        for(int j = 0; j < n; j++){
            count++;
            nextButton = button[nextButton];
            if(nextButton == 2){
                success = true;
                break;
            }
        }
        if(!success){
            count = -1;
        }
        System.out.println(count);
    }

}

Measured memory_bytes: 50684
import math
n=int(input())
a=list(map(int,input().split()))
A=max(a)
B=min(a)
C=(math.ceil((A+B)/2))
if abs(A-C) > abs(B-C):
    print(abs(A-C))
elif abs(A-C) < abs(B-C):
    print(abs(B-C))
else:
    print(abs(A-C))


Measured memory_bytes: 5680
#include <iostream>                                             
                                                                
using namespace std;                                            
                                                                
int gcd(int a,int b) {                                          
  if (a<b) {                                                    
    swap(a,b);                                                  
  }                                                             
  if (b==0) {                                                   
    return a;                                                   
  }                                                             
  return gcd(b,a%b);                                            
}                                                               
                                                                
int main(void) {                                                
  int x, y;                                                     
  cin >> x >> y;                                                
  cout << gcd(x,y) << endl;                                     
}                                      

Measured memory_bytes: 3092
#include<stdio.h>
#include<math.h>
int main()
{
  double d,n,ans;
  scanf("%lf %lf",&d,&n);
  if(n<100)ans = pow(100,d)*n;
  if(n==100)ans = pow(100,d)*101;
  printf("%d",(int)ans);
  return 0;
}


Measured memory_bytes: 640
//#include <vector>
#include <iostream>
//#include <algorithm>
#include <math.h>

using namespace std;

int main() {
	int x1, x2, x3, x4, y1, y2, y3, y4, a1, a2;
	cin >> x1 >> y1 >> x2 >> y2;
	a1 = x2 - x1;
	a2 = y2 - y1;

	if (a1 >= 0) {
		if (a2 >= 0) {
			a1 = abs(a1); a2 = abs(a2);
			x3 = x2 - a2; y3 = y2 + a1;
			x4 = x3 - a1; y4 = y3 - a2; }
		if (a2 < 0) {
			a1 = abs(a1); a2 = abs(a2);
			x3 = x2 + a2; y3 = y2 + a1;
			x4 = x3 - a1; y4 = y3 + a2; }	}
	if (a1 < 0) {
		if (a2 >= 0) {
			a1 = abs(a1); a2 = abs(a2);
			x3 = x2 - a2; y3 = y2 - a1;
			x4 = x3 + a1; y4 = y3 - a2;	}
		if (a2 < 0) {
			a1 = abs(a1); a2 = abs(a2);
			x3 = x2 + a2; y3 = y2 - a1;
			x4 = x3 + a1; y4 = y3 + a2;	}	}
	cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <string>
#include <cmath>
#include <map>
#include <cstring>
#include <queue>

#define REP(i, n) for (int i = 0; i < (n); i++)
#define FOR(i, init, n) for (int i = init; i < (n); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define Cout(obj) cout << obj << endl
#define Size(obj) (int)(obj).size()
#define fcout cout << fixed << setprecision(10)
#define fi first
#define se second

using namespace std;
using ll = long long int;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using edge = struct
{
    int to, cost;
};

const int MOD = 1e4;
const int iINF = 1e9;
const long long int llINF = 1e18;
const double PI = acos(-1.0);

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

vector<int> meal;
int dp[110][4][2];
int N, K;

int dfs(int i, int j, bool k)
{
    if (dp[i][j][k] != -1)
        return dp[i][j][k];

    if (i == N + 1)
        return 1;

    int res = 0;

    if (meal[i] != 0)
    {
        if (k && j == meal[i])
            return 0;

        res = dfs(i + 1, meal[i], meal[i] == j);

        return dp[i][j][k] = res % MOD;
    }

    FOR(n, 1, 4)
    {
        if (k && j == n) continue;

        res += dfs(i + 1, n, n == j);
    }

    return dp[i][j][k] = res % MOD;
}

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

    cin >> N >> K;

    meal.resize(N + 1, 0);

    REP(i, K)
    {
        int a, b;
        cin >> a >> b;
        meal[a] = b;
    }

    memset(dp, -1, sizeof(dp));

    Cout(dfs(1, 0, 0));

    return 0;
}


Measured memory_bytes: 3176
#import
#import math
#import numpy as np
modnum = 10 ** 9 + 7
N = int(input())

def mod(num):
    return num % modnum

def pow_k(x, n):
    if n == 0:
        return 1

    k = 1
    while n > 1:
        if n % 2 != 0:
            k *= x
        x = mod(x * x)
        n //= 2

    return mod(k * x)

t1 = pow_k(10, N)
t2 = pow_k(9, N)
t3 = pow_k(8, N)

print(mod(t1 - t3 - (t2 - t3) * 2))


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

using namespace std;

int main(){
  long long int N, M;
  cin>>N>>M;

  long long int answer=0;

  if(N>=M/2){
    answer+=M/2;
  }else if(N<M/2){
    answer+=N;
    answer+=(M-2*N)/4;
  }

  cout<<answer<<endl;

}


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

typedef long long ll;

ll n, p;
int main(){
    while(scanf("%lld%lld", &n, &p)!=EOF){
            if(n==1) {
              printf("%lld\n", p);
                     continue;
               }
           ll res=1;
          for( ll i=2;  i*i<=p; i++){
                    ll pp=0;
                     while(p%i==0){
                                  pp++;
                                     p/=i;
                        }
                         while(pp>=n){
                                  pp-=n;
                                 res*=i;
                         }
      }
               printf("%lld\n", res);
 }
 return 0;
}
                     

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

int main(){
  int N;
  cin >> N;
  
  int y=N,x=0;
  while(y>0){
    x+=y%10;
    y=y/10;
  }
  if(N%x == 0){
    cout << "Yes" << endl;
  }else cout << "No" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

int main() {
    int a, b, k;
    cin >> a >> b >> k;
    set<int> ans;
    for(int i = a; i <= min(a+k-1, b); i++)
        ans.insert(i);
    for(int i = max(b-k+1, a); i <= b; i++)
        ans.insert(i);
    for(int val: ans)
        cout << val << endl;
    return 0;
}



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

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define ALL(v) v.begin(),v.end()
#define FOR(i, j, k) for(ll i=j;i<k;i++)
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cout<<v[i]<<" "

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<ll, ll> P;
typedef long double ld;
struct Edge{ll from, to, cost;};
struct node{ll cost, to;
  bool friend operator>(node a, node b){
    return a.cost>b.cost;
  }
};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

ll modpow(ll a, ll n, ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

ll gcd(ll a, ll b){
  ll r = a%b;
  if(r==0) return b;
  else return gcd(b, a%b);
}

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}


/**************************************
** A main function starts from here  **
***************************************/
int main(){
  ll n;
  cin >> n;
  llvec a(n);
  rep(i, n)cin>>a[i];
  sort(ALL(a));
  ld mv=1e10;
  ll ma;
  rep(i, n){
    if(abs(a[n-1]/2-a[i])<mv){
      mv = fabs(a[n-1]/2.-a[i]);
      ma = a[i];
    }
  }

  cout << a[n-1] << " " << ma << endl;
  return 0;
}


Measured memory_bytes: 1024
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=100+2;
const double pie=acos(-1.);
int n;
int x[maxn],y[maxn];
double st[maxn];
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
	for (int i=1;i<=n;i++){
		int tot=0;
		for (int j=1;j<=n;j++)
			if (i^j) st[++tot]=atan2(x[j]-x[i],y[j]-y[i]);
		sort(st+1,st+tot+1);
		st[0]=st[tot]-2*pie;
		double ans=0;
		for (int j=1;j<=n;j++) ans=max(ans,st[j]-st[j-1]-pie);
		printf("%.18lf\n",ans/2./pie);
	}
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define rep(i, n) for (int i = 0; i < n; i++)
#define rep1(i, n) for (int i = 1; i <= n; i++)

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int INF = 1 << 30;
const long long INFL = 1LL << 62;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 100;

int main() {
	string S,T;cin>>S>>T;
	reverse(S.begin(),S.end());
	reverse(T.begin(),T.end());
	int idx=-1;
	rep(i,S.size()) {
		if(i+T.size()>S.size()) break;
		bool match=true;
		rep(j,T.size()) {
			if(i+j>=S.size()) break;
			if(S[i+j]=='?'||S[i+j]==T[j]) continue;
			else {match=false;break;}
		}
		if(match) {idx=i;break;}
	}
	if(idx==-1) {cout<<"UNRESTORABLE"<<endl;return 0;}
	rep(i,S.size()) {
		if (idx<=i&&i<=idx+T.size()-1) S[i]=T[i-idx];
		else if (S[i]=='?') S[i]='a';
	}
	reverse(S.begin(),S.end());
	cout<<S<<endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	char cont[6];
	int i;
	for(i=0;i<6;i++)
	{
		scanf("%c",&cont[i]);
	}
	if((cont[2]==cont[3]) && (cont[4]==cont[5]))
	{
		printf("Yes");
	}
	else
		printf("No");
	return 0;
}

Measured memory_bytes: 128
#define _USE_MAT_DEFINES
#include<iostream>
#include <iomanip>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <deque>
#include <numeric>
#include <functional>
using namespace std;

#define INF 1e9

int main() {
    vector<vector<int>>c(3, vector<int>(3));
    vector<int>a(3), b(3), max_(3, 0);
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> c[i][j];
            max_[i] = max(max_[i], c[i][j]);
        }
    }

    for (int i = 0; i <= max_[0]; i++) {
        for (int j = 0; j <= max_[1]; j++) {
            for (int k = 0; k <= max_[2]; k++) {
                bool ok = true;
                a[0] = i; a[1] = j; a[2] = k;
                b[0] = c[0][0] - a[0];
                b[1] = c[0][1] - a[0];
                b[2] = c[0][2] - a[0];
                if (b[0] < 0 || b[1] < 0 || b[2] < 0) {
                    ok = false;
                    continue;
                }
                else {
                    for (int l = 1; l < 3; l++) {
                        for (int m = 0; m < 3; m++) {
                            if (c[l][m] != a[l] + b[m])ok = false;
                        }
                        if (!ok)break;
                    }
                }
                if (ok) {
                    cout << "Yes" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
#define MAXN 100005
#define ll long long
#define pb push_back
#define sortv(v) sort(v.begin(),v.end())
#define tc(t) int t;cin>>t;while(t--)
#define copy copy_n
#define fr(i,a,b) for(long long i=a;i<b;i++)
#define frr(i,a,b) for(long long i=a;i>=b;i--)
#define frn(i,a,b,n) for(long long i=a;i<=b;i=i+n)
#define gcd(x,y) __gcd(x,y)
#define ld long double
#define um unordered_map
#define mkp make_pair
#define b_s binary_search
#define des greater<ll>()
#define fi first
#define se second
ll mul(ll a,ll b,ll p=mod){return ((a%p)*(b%p))%p;}
ll add(ll a,ll b,ll p=mod){return (a%p + b%p)%p;}
void input(ll a[],ll sz){fr(i,0,sz) cin>>a[i];}
void print(ll a[],ll sz){fr(i,0,sz){if(i==sz-1) cout<<a[i]<<"\n";else cout<<a[i]<<" ";}}
ll maxr(ll a[],ll sz){ll ma;fr(i,0,sz){if(i==0) ma=a[i];else if(a[i]>ma) ma=a[i];}return ma;}
ll minr(ll a[],ll sz){ll mi;fr(i,0,sz){if(i==0) mi=a[i];else if(a[i]<mi) mi=a[i];}return mi;}
ll isprm(ll n) {
    if (n <= 1)  return 0; 
    if (n <= 3)  return 1; 
    if (n%2 == 0 || n%3 == 0) return 0; 
  
    for (int i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return 0; 
    return 1;}
/*ll spf[MAXN];
void sieve() 
{
    spf[1]=1; 
    for (ll i=2; i<MAXN; i++) 
        spf[i] = i; 
    for (ll i=4; i<MAXN; i+=2) 
        spf[i] = 2; 
  
    for(ll i=3;i*i<MAXN;i++) 
    {
        if (spf[i]==i) 
        {
            for (int j=i*i;j<MAXN;j+=i) 
                if (spf[j]==j) 
                    spf[j]=i; 
        }
    }
}*/
ll power(ll x,ll y,ll p=mod) 
{ 
    ll res = 1;
    x = x % p;
    while (y > 0) 
    {
        if (y & 1) 
            res = (res*x) % p;
        y = y>>1; // y = y/2 
        x = (x*x) % p; 
    } 
    return res; 
} 
ll modInverse(ll n,ll p=mod) 
{ 
    return power(n, p-2, p); 
} 
ll ncrMod(ll n,ll r,ll p=mod) 
{
   if (r==0) 
      return 1;
    ll fac[n+1]; 
    fac[0] = 1; 
    for (ll i=1 ; i<=n; i++) 
        fac[i] = fac[i-1]*i%p; 
    return (fac[n]* modInverse(fac[r], p) % p * 
            modInverse(fac[n-r], p) % p) % p; 
}
//a+b=xor(a,b)+2*(a&b)//
bool comp(const pair<int,int> &a, 
              const pair<int,int> &b) 
{
    if(a.fi==b.fi)
    {
        return (a.se>b.se);//second elem in descending
    }
    return (a.first < b.first);//first elem in ascending 
}
ll n,k,h[100005],dp[100005];
ll solve(ll i)
{
    if(i>=n-1)
    return 0;
    if(dp[i]!=-1)
    return dp[i];
    ll mi=mod;
    fr(j,i+1,min(i+k+1,n))
    {
    ll k=abs(h[i]-h[j])+solve(j);
    mi=min(mi,k);
    }
    dp[i]=mi;
    //cout<<k1<<" "<<k2<<" "<<mi<<"\n";
    return dp[i];
}










int main()
{
	fio;
	cin>>n>>k;
	input(h,n);
	fr(i,0,100005)
	dp[i]=-1;
	ll ans=solve(0);
	cout<<ans<<"\n";
	return 0;
}


Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const ll INF = 1LL << 60; //MAX 9223372036854775807
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A
struct edge
{
  ll to;
  ll cost;
  edge() {}
  edge(ll to, ll cost) : to(to), cost(cost){};
};

vector<ll> bellman_ford(ll s, vector<vector<edge>> &g)
{
  //pair.first=距離,pair.second=点
  vector<ll> dist(g.size(), INF);
  dist[s] = 0;
  //頂点数-1回全ての辺を見る操作を繰り返す
  rep(i, g.size() - 1)
  {
    rep(j, g.size())
    {
      if (dist[j] == INF)
        continue;
      rep(k, g[j].size())
      {
        dist[g[j][k].to] = min(dist[g[j][k].to], dist[j] + g[j][k].cost);
      }
    }
  }
  ll r=dist[g.size()-1];
  //ここで更新があったら負のサイクルがある
  rep(j, g.size())
  {
    if (dist[j] == INF)
      continue;
    rep(k, g[j].size())
    {
      dist[g[j][k].to] = min(dist[g[j][k].to], dist[j] + g[j][k].cost);
    }
  }
  if(r!=dist[g.size()-1])return vector<ll>();
  return dist;
}

int main()
{
  ll n, m;
  cin >> n >> m ; //頂点数,辺数,始点

  vector<vector<edge>> g(n);
  rep(i, m)
  {
    ll a, b, c;
    cin >> a >> b >> c;
    g[a-1].emplace_back(b-1,-c);
  }

  vector<ll> ans = bellman_ford(0, g);

  if (ans.size()>0)
    cout << -ans[n-1] << endl;
  else
    cout << "inf" << endl;

  return 0;
}



Measured memory_bytes: 384