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

template <class t>
using vc = vector<t>;
template <class t>
using vvc = vector<vector<t>>;
typedef long long ll;
typedef vc<int> vi;
typedef vvc<int> vvi;
typedef pair<int, int> pi;

#define uset unordered_set
#define umap unordered_map

#define endl "\n"

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define bg begin()
#define ed end()

#define all(a) a.bg, a.ed

template <class t, class u>
ostream &operator<<(ostream &os, const pair<t, u> &p) {
    return os << "( " << p.first << ", " << p.second << " )";
}

template <class t>
ostream &operator<<(ostream &os, const vc<t> &v) {
    os << "[ ";
    for (int i = 0; i < v.size(); i++) {
        os << v[i];
        if (i != v.size() - 1) {
            os << ", ";
        }
    }
    return os << " ]";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    // cout << fixed << setprecision(18);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // Solution

    //

    string n;
    cin >> n;

    int digits = n.size();
    auto reworked = string(digits, '9');

    if (digits == 1) {
        cout << n;
        return 0;
    } else {
        bool all_nines = true;
        for (int i = 1; i < digits; i++) {
            all_nines = n[i] == '9';
        }
        if (all_nines) {
            reworked = n;
        }
    }

    if (n < reworked) {
        reworked[0] = n[0] - 1;
    }
    ll tot = 0;
    for (auto &c : reworked) {
        tot += c - '0';
    }
    cout << tot;
}


Measured memory_bytes: 3572
#include<bits/stdc++.h>
#define N 40010
using namespace std;
int a[2];
int main(){
	long long n,a,b;
	cin>>n>>a>>b;
	long long sum=0;
	sum+=n/(a+b)*a;
	n%=(a+b);
	sum+=min(n,a);
	cout<<sum<<endl;
}

Measured memory_bytes: 256
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

from fractions import gcd
n = inn()
a = inl()
l = [a[0]]*n
for i in range(1,n):
    l[i] = gcd(l[i-1],a[i])
r = [a[n-1]]*n
for i in range(n-2,-1,-1):
    r[i] = gcd(r[i+1],a[i])
mx = max(l[n-2],r[1])
for i in range(1,n-1):
    mx = max(mx, gcd(l[i-1],r[i+1]))
print(mx)


Measured memory_bytes: 89580
a,b=map(int,input().split())
c=list(map(int,input().split()))
ans=0
c.sort()
c.reverse()
for i in range(b):
    if c[i]>=sum(c)/(4*b):
        ans+=1
        if ans==b:
            print("Yes")
    else:
        print("No")
        exit()


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int  main(){
	char s[100001];
	cin>>s;
	ll i=strlen(s);
	while(i>0){
		if(strncmp(s+i-5,"dream",5)==0)	i-=5;
		else if(strncmp(s+i-7,"dreamer",7)==0) i-=7;
		else if(strncmp(s+i-5,"erase",5)==0) i-=5;
		else if(strncmp(s+i-6,"eraser",6)==0) i-=6;
		else{
			cout<<"NO"<<endl;
			return 0;
		}
	}
	cout<<"YES"<<endl;

return 0;
}


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

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

    bool found = false;
    int cmax = N / 4;
    int dmax = N / 7;

    for (int c=0; c<=cmax; ++c) {
        for (int d=0; d<=dmax; ++d) {
            int v = 4 * c + 7 * d;
            if (v == N) found = true;
        }
    }
    if (found) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 3568
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define For(i,n) for(int i=0;i<n;i++)
#define Fre(i,a,b) for(int i = a; i < b; i++)
#define sf(n) scanf("%d", &n)
#define sff(a,b) scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pfn(n) printf("%d\n", n)
#define pfs(n) printf("%d ", n)
#define ff first
#define ss second
#define mem(a,b) memset(a,b,sizeof(a))
#define READ freopen("in.txt", "r", stdin)
#define WRITE freopen("out.txt", "w", stdout)
#define sz size()
#define number_of_digit(n) __builtin_ffs(n);
#define ll long long
#define T int
#define ld long double
inline void print(T n)
{
	if (n == 0)
	{
		putchar('0');
		putchar('\n');
	}
	else if (n == -1)
	{
		putchar('-');
		putchar('1');
		putchar('\n');
	}
	else
	{
		char buf[11];
		buf[10] = '\n';
		int i = 9;
		while (n)
		{
			buf[i--] = n % 10 + '0';
			n /= 10;
		}
		while (buf[i] != '\n')
			putchar(buf[++i]);
	}
}
int read()
{
       int cc = getc(stdin);
       for (;cc < '0' || cc > '9';)  cc = getc(stdin);
       int ret = 0;
       for (;cc >= '0' && cc <= '9';)
       {
          ret = ret * 10 + cc - '0';
          cc = getc(stdin);
       }
      return ret;
}
ll power(ll num,ll g)
{
	if(g==0)return 1;

	if(g%2==1)return (num*power((num*num)%mod,g/2))%mod;
	return power((num*num)%mod,g/2);
}
ll a[1005][1005],h,w;
string s[1005];
ll solve(int i,int j)
{
	if(i==h-1 && j==w-1)return 1LL;
	if(a[i][j]>-1)return a[i][j];
	//cout<<i<<" "<<j<<endl;
	a[i][j]=0;
	if(i+1<h && s[i+1][j]!='#')a[i][j]+=solve(i+1,j);
	if(j+1<w && s[i][j+1]=='.')a[i][j]+=solve(i,j+1);
	a[i][j]%=mod;
	//cout<<i<<" "<<j<<" "<<a[i][j]<<endl;
	return a[i][j];
}
int main()
{
	ios_base::sync_with_stdio(false);
  	cin.tie(NULL);
  	cout.tie(NULL);

  	cin>>h>>w;
  	For(i,h)cin>>s[i];
  	For(i,h)For(j,w)a[i][j]=-1;
  	cout<<solve(0,0)<<endl;
	return 0;
}

Measured memory_bytes: 9344
#include<bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (int)n; i++)
#define REPvec(itr, mp) for(auto itr = mp.begin();itr != mp.end(); itr ++)
#define all(x) x.begin(), x.end()
#define MOD 1000000007//1e9+7
using namespace std;
typedef long long ll;
typedef vector<int >    vecint;
typedef vector<string > vecstr;
int main()
{
  string s;
  cin >> s;
  int n = s.size();
  string t;
  int i= 0;
  while(i <= n - 1){
    // cout << "s.substr(i,5) = "<< s.substr(i,5) << endl;
    // cout << "s.substr(i,7) = "<< s.substr(i,7) << endl;
    //erase//
    if(s.substr(i, 5) == "erase"){
      // cout << "erase?" << endl;
      // cout << s.substr(i,6)<< endl;
      if(s.substr(i,6) == "eraser"){
	t = t + "eraser";
	i += 6;
      }else{
	t = t+ "erase";
	i += 5;
      }
    }
    //dream//
    else if(s.substr(i, 5) == "dream"){
      // cout << "dream?" << endl;
      if(s.substr(i,7)=="dreamer"){
	if(i + 6 == n - 1){
	  t = t + "dreamer";
	  i += 7;
	}else if(i + 7 <= n - 1){
	  if(s[i + 7] == 'd'||s[i + 7] == 'e'){
	    t = t + "dreamer";
	    i += 7;
	  }else{
	    t = t + "dream";
	    i += 5;
	  }
	}else{
	  t = t + "dream";
	  i += 5;
	}
      }else{
	t = t + "dream";
	i += 5;
      }
    }else{
      cout << "NO" << endl;
      return 0;
    }
    // cout << t << endl;
  }
  cout << "YES" << endl;
} 

Measured memory_bytes: 764
n = int(input())
a = [int(i) for i in input().split()]
ans = 0
for i in range(1, n):
  if a[i] < a[i - 1]:
    ans += a[i - 1] - a[i]
    a[i] += (a[i - 1] - a[i])
print(ans)


Measured memory_bytes: 32180
#include<iostream>
#include<cstdio>
#include<math.h>
#include<algorithm>
using namespace std;
int main()
{
	int t,sum=0;
	for(int i=0;i<4;i++)
	{
		cin>>t;
		sum+=t;
	}
	cout<<sum/60<<endl<<sum%60<<endl;
		
	return 0;
}


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

public class Main {
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        int k = sc.nextInt();
        int x = sc.nextInt();
        List<Integer> list = new ArrayList<>();
        for (int i = -k + 1; i < k; i++) {
            list.add(x + i);
        }
        for (int i = 0; i < list.size() - 1; i++) {
            System.out.print(list.get(i));
            System.out.print(" ");
        }
        System.out.println(list.get(list.size() - 1));
    }
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

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

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        return hasNextByte();
    }

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

    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

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


Measured memory_bytes: 23252
#include<bits/stdc++.h>
using namespace std;
string a;
bool cf[2]={0}; 
int main() 
{
	cin>>a;
	for(int i=0;i<a.length();i++) 
	{ 
		if(a[i]=='C') cf[0]=1;
		if(a[i]=='F'&&cf[0]) cf[1]=1;
	}
	if(cf[1]) cout<<"Yes";
	else cout<<"No";
}

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

using namespace std;

void Solve(){
	int a, b;
	cin>>a>>b;
	cout<<a * b<<endl;
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T = 1;
	//cin>>T;
	while(T--){
		Solve();
	}
}

Measured memory_bytes: 3612
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
using namespace std;

typedef long long ll;

string s;

int main() {
	cin >> s;
	for (int i = 0; i < s.length() - 1; ++i) {
		if (s[i] == 'A' && s[i + 1] == 'C') {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n = read();
    let res:u32 = (0..n)
        .map(|_| read::<u32>().trailing_zeros())
        .min()
        .unwrap();
    println!("{}", res);
}


Measured memory_bytes: 4352
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scan = new Scanner(System.in);
		int s =scan.nextInt();
		int m=0,h=0;
		if(s >= 60) {
			m = s/60;
			s = s%60;
		}
		if(m >= 60) {
			h = m/60;
			m = m%60;
		}
        
        System.out.println(h + ":" + m + ":" + s);
	}

}


Measured memory_bytes: 26224
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
typedef long long int ll;

#define PI (acos(-1))
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define dumparr(x) cerr << #x ; for(auto elem: x){cerr << " " << elem;} cerr << endl;
#define dumppairs(x) cerr << #x ; for(auto elem: x){cerr << "(" << elem.first << " " << elem.second << ") ";} cerr << endl;
#define dumpline cerr << "**********************" << endl;
#define dumpwline(x) cerr << "******** " << #x << "=" << (x) << " ********" << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))



int main(void){
    ll div = 1e9 + 7;
    uint m[100010][13] ;
    REP(i, 100010){
        REP(j, 13){
            m[i][j] = 0;
        }
    }

    vector <int> amaris;
    REP(i, 7){
        amaris.push_back(ll(pow(10, i)) % 13);
    }
    dumparr(amaris)
    string s; cin >> s;
    for(int i=0; i<s.size(); i++){
        auto c = s[s.size()-i-1];
        vector <int> cands;
        if (c == '?'){
            cands = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        } else {
            cands.push_back(c - '0');
        }
        for (auto d: cands){
            if (i==0){
                m[i][d] = 1;
                continue;
            }
            REP(j, 13){
               int amari = (amaris[i % 6]*d + j) % 13;
               m[i][amari] += (m[i-1][j] + div);
               m[i][amari] %= div;
            }
        }
    }
    cout << m[s.size()-1][5] << endl;

    return 0;
}

Measured memory_bytes: 5504
#exec({'RUBY_THREAD_VM_STACK_SIZE'=>'100000000'},'/usr/bin/ruby', $0) if !ENV['RUBY_THREAD_VM_STACK_SIZE']

require 'prime'

def inpf() a=gets.chomp.split(" ").map(&:to_f)end

def inps() a=gets.chomp.split(" ")end

def copy(a) Marshal.load(Marshal.dump(a)) end

def kaijo(n,r = 10**9+7)(n < 2)? 1 : (2..n).inject{|memo,u|memo=(memo*u)%r} end

def na(n,d=0) Array.new(n,d)end

def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end

def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end

def inp() a=gets.chomp.split(" ").map(&:to_i)end

def r_up(a, b) (a+b-1)/b end

def sum(a) a.inject(:+) end

def big(a,b) return (a>b)? a:b end

def small(a,b) return (a<b)? a:b end

n=inp[0]
h = {}
s = []
n.times{|i|
  d = gets.chomp.split
  h[d[0]] = i
  d[1] = d[1].to_i
  s << d
}
x = gets.chomp
ans = -1 * s[h[x]][1]
(h[x]...n).each do |i|
  ans += s[i][1]
end
p ans


Measured memory_bytes: 2044
//#define _USE_MATH_DEFINES
//#include <math.h>
#include <iostream>
//#include <iomanip>
//#include <bits/stdc++.h>

using namespace std;

int main() {
    int H,W;
    for (int i = 0;; i++){
        cin >> H >> W;
        if (H == 0 && W == 0) break;
        for (int k = 0; k < H; k++) {
            for (int j = 0; j < W; j++) cout << "#";
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}



Measured memory_bytes: 3088
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;

int main(){
	ll n,x;cin>>n>>x;
	vector<ll> a(n);
	for(int i = 0; i < n; i++) {
		cin>>a[i];
	}
	sort(ALL(a));
	ll ans =0;
	for(int i = 0; i < n; i++) {
		if (x >= a[i]){
			ans++;
			x -= a[i];
			if (i == n - 1 && x > 0){
				ans--;
			}
		}

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

Measured memory_bytes: 256
import math

def main():
    N = int(input())
    A = list(map(int, input().split()))

    A_sorted = sorted(A, reverse=True)
    ans = 0

    for i in range(math.ceil(N/2) - 1):
        ans += A_sorted[i]

    for i in range(math.ceil(N/2) - 1):
        ans += A_sorted[1+i]
    if N % 2 == 0:
        ans += A_sorted[N//2 - 1]

    print(ans)
    
main()

Measured memory_bytes: 94144
//#define _USE_MATH_DEFINES
//#include <cmath>
#include <iostream>
//#include <stdio.h>
//#include <stdlib.h>
//#include <iomanip>
//#include <vector>
//#include <string>
//#include <algorithm>
//#include <functional>
//#include <time.h>
//#include <sstream>
//#include <queue>
//#include <map>

using namespace std;


int main(){

	int e1, e2, e3;
	char c;
	int ans1 = 0,ans2 = 0;

	while (cin >> e1 >> c >> e2 >> c >> e3){
		if (e1 == e2) ans2++;

		if (e1 * e1 + e2 * e2 == e3 * e3) ans1++;
	}

	cout << ans1 << endl;
	cout << ans2 << endl;

	return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<algorithm>

using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	int temp = 1;
	for (int i = 0; i < m; i++) {
		temp *= 2;
	}
	cout << ((1900 * m) + (n - m) * 100)*temp << endl;

	return 0;
}

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


int main()
{
	int x,y;
	for (int i = 1;;++i) {
		cin >> x>>y;
		if (x == 0 && y==0)
			break;
		else {
			vector<int> v;
			v.push_back(x);
			v.push_back(y);
			sort(v.begin(),v.end());
			cout << v[0] << " " << v[1]<<endl;
		}
	}
	return 0;
}



Measured memory_bytes: 3056
# 解説そのまま
N, Q = map(int, input().split())
S = input()
t=[0]*(N+1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])

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

#define FI(i,a,b) for(int i=(a);i<=(b);i++)
#define FD(i,a,b) for(int i=(a);i>=(b);i--)

#define LL long long
#define Ldouble long double
#define PI 3.1415926535897932384626

#define PII pair<int,int>
#define PLL pair<LL,LL>
#define mp make_pair
#define fi first
#define se second

using namespace std;

LL n;
list<int> L;

int p, q, u[44];

int main(){
	scanf("%lld", &n);
	n++;
	while(n){
		u[p++] = n & 1;
		n >>= 1;
	}
	FD(i, p - 2, 0){
		L.push_back(++q);
		if(u[i]) L.push_front(++q);
	}
	printf("%d\n", q + q);
	FI(i, 1, q) printf("%d ", i);
	FI(i, 1, q){
		printf("%d%c", L.front(), i == q ? '\n':' ');
		L.pop_front();
	}
	return 0;
}


Measured memory_bytes: 256
import numpy as np

def main():
    temp = input().split()
    N = int(temp[0])
    M = int(temp[1])
    k = [] #tukawanai
    s = []
    for m in range(M):
        temp = input().split()
        k.append(int(temp[0]))
        s.append([])
        for x in temp[1:]:
            s[m].append(int(x)-1)
    p = []
    temp = input().split()
    for x in temp:
        p.append(int(x))
    res = 0
    for i in range(2**N):
        suitti = ret_suitti(i,N)
        if(hantei(suitti, s, p)):
            res += 1
    print(res)

def ret_suitti(i,N):
    suitti = []
    shou = i
    for n in range(N):
        amari = shou % 2
        shou = shou // 2
        if(amari == 0):
            suitti.append(0)
        else:
            suitti.append(1)
    return suitti

def hantei(suitti, s, p):
    M = len(p)
    flag = 1
    for m in range(M):
        on_suitti = 0
        for x in s[m]:
            if(suitti[x] == 1):
                on_suitti += 1
        if(on_suitti % 2 != p[m]):
            flag = 0
    if(flag == 1):
        return True
    else:
        return False

if __name__ == "__main__":
    main()


Measured memory_bytes: 12400
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;

long long int ans[114514] = {};
long long int cnt[114514] = {};

int main() {

  long long int n;
  cin >> n;

  vector< vector< long long int > > m;
  vector< vector< long long int > > w;
  for ( long long int i = 0; i < n; i++ ) {
    vector< long long int > mm;
    m.push_back( mm );
    vector< long long int > ww;
    w.push_back( ww );
  }

  for ( long long int i = 0; i < n - 1; i++ ) {

    long long int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    m[a].push_back( b );
    w[a].push_back( c );
    m[b].push_back( a );
    w[b].push_back( c );

  }

  queue< pair< long long int, long long int > > q;
  q.push( make_pair( 0, 0 ) );

  while( q.size() ) {

    pair< long long int, long long int > p = q.front();
    q.pop();

    if ( ans[p.first] > 0 ) continue;
    ans[p.first] = ( p.second % 2 ) + 1;
    for ( long long int i = 0; i < m[p.first].size(); i++ ) {
      long long int j = m[p.first][i];
      if ( ans[j] > 0 ) continue;
      q.push( make_pair( j, p.second + w[p.first][i] ) );
    }

  }

  for ( long long int i = 0; i < n; i++ ) {
    cout << ans[i] - 1 << endl;
  }

  return 0;

}


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

namespace AtCoder
{
	class Program
	{
		static void Main(string[] args)
		{
			var Instance = new Question();
			Instance.Exec();
		}
	}

	public class Question
	{
		public void Exec()
		{
			int n = int.Parse(Console.ReadLine());
			List<int> nlist = new List<int>();
			var array = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
			for (int i = 0; i < n; ++i) {
				nlist.Add(array[i]);
			}


			nlist.Sort();
			int index = n > 2 ? n / 2 : 1;
			int median = nlist[index];
			for (int i = 0; i < n; ++i) {
				if (array[i] < median) {
					Console.WriteLine($"{median}");
				} else {
					Console.WriteLine($"{nlist[index - 1]}");
				}
			}

			Console.Out.Flush();
			Console.ReadKey();
		}
	}
}

Measured memory_bytes: 36188
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(M)]


class UnionFind():
    def __init__(self, SIZE):
        # 1-indexed
        self.root = list(range(N + 1))
        self.size = [0] + [1] * SIZE

    def find(self, x):
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def unite(self, x, y):
        X, Y = self.find(x), self.find(y)
        SX, SY = self.size[X], self.size[Y]
        if SX > SY:
            m = X
        else:
            m = Y
        self.size[m] = SX + SY
        #self.size[X + Y - m] = 0
        self.root[X + Y - m] = m

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    def scan(self):
        for i in self.root:
            self.find(i)


uf = UnionFind(N)
ans = [N * (N - 1) // 2]
for a, b in AB[::-1]:
    if not uf.is_same(a, b):
        ans += [ans[-1] - uf.size[uf.find(a)] * uf.size[uf.find(b)]]
        uf.unite(a, b)
    else:
        ans += [ans[-1]]
print(*ans[-2::-1], sep='\n')


Measured memory_bytes: 31052
#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
#define mem(a,n) memset(a,n,sizeof(a))
typedef long long ll;
const int N=2e5+5;
int cnt[N];
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int n,k;
    while(~scanf("%d%d",&n,&k))
    {
        int x;
        mem(cnt,0);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&x);
            cnt[x]++;
        }
        sort(cnt,cnt+N,cmp);
        int ans=0;
        for(int i=k;cnt[i];i++) ans+=cnt[i];
        printf("%d\n",ans);
    }
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(ll i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
typedef tuple<ll,ll,ll> Tu;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const double PI=3.14151926535;
const ll INFl=(ll)9223372036854775807/2;
const int MAX=10000;
const ll tMOD=(ll)1e9+7;
const ll MOD=(ll)998244353;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int mdx[8]={0,1,0,-1,1,1,-1,-1},mdy[8]={-1,0,1,0,1,-1,1,-1};


template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

struct edge{int to,cost;};
int V;
const int MAX_V=100100;
vector<edge> G[MAX_V];
ll d[MAX_V];

void dijkstra(int s){
	priority_queue<Pi,vector<Pi>,greater<Pi> >que;
	fill(d,d+V,1e15);
	d[s]=0;
	que.push(Pi(0,s));
	while(!que.empty()){
		Pi p=que.top();que.pop();
		int v=p.second;
		if(d[v]<p.first)continue;
		for(int i=0;i<G[v].size();i++){
			edge e=G[v][i];
			if(d[e.to]>d[v]+e.cost){
				d[e.to]=d[v]+e.cost;
				que.push(Pi(d[e.to],e.to));
			}
		}
	}
}

int n,m;
int main(){
	cin>>n>>m;
	V=n;
	for(int i=n-1;i>=1;i--){
		//cout<<i<<endl;
		G[i].push_back(edge{i-1,0});
	}
	for(int i=0;i<m;i++){
		int l,r,c;
		cin>>l>>r>>c;
		l--,r--;
		G[l].push_back(edge{r,c});
		G[r].push_back(edge{l,c});
	}
	dijkstra(0);
	if(d[n-1]==1e15){
		cout<<-1<<endl;
	}else{
		cout<<d[n-1]<<endl;
	}
	return 0;
}

Measured memory_bytes: 10488
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repp(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define rrep(i, n, m) for (int i = n; i >= m; i--)
#define ALL(a) (a).begin(), (a).end()
#define p(a, b) printf(a, b);
#define c(s) cout << (s) << endl;
#define yes cout << "Yes" << endl;
#define no cout << "No" << endl;
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define cyn(c) cout << (c ? "Yes" : "No") << endl;
#define cYN(c) cout << (c ? "YES" : "NO") << endl;
#define pyn(c) printf("%s\n", c ? "Yes" : "No");
#define pYN(c) printf("%s\n", c ? "YES" : "NO");
#define INF 1e18
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL, LL> P;
template <class T>
bool contain(const std::string &s, const T &v)
{
  return s.find(v) != std::string::npos;
}
ULL mod = 1e9 + 7;

int main(){
    ULL n=0,a[5]={},v=0,v2=0;
    cin>>n;
    rep(i,5)cin>>a[i];
    sort(a,a+5);
    if(n<=a[0]){
      cout<<5<<endl;
      return 0;
    }else{
      v = n / a[0];
      v2 = n % a[0];
      if(v2>0){
        v++;
      }
      cout << 5 + v - 1 << endl;
    }
}


Measured memory_bytes: 256
Y,N = "APPROVED","DENIED"

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

f = 1
for i in A:
    if i%2==0 and f==1:
        if i%3==0 or i%5==0:
            pass
        else:
            f=0

print(Y) if f else print(N)



Measured memory_bytes: 3060
n, k = map(int, input().split())

MOD = 10 ** 9 + 7

def factorial(n):
    global fct
    global invfct
    fct = [0] * (n + 1)
    fct[0] = 1
    for i in range(1, n+1):
        fct[i] = fct[i-1] * i % MOD
    invfct = [0] * (n + 1)
    invfct[n] = pow(fct[n], MOD - 2, MOD)
    for i in range(n-1, -1, -1):
        invfct[i] = invfct[i+1] * (i + 1) % MOD

def binomial(n, k):
    return fct[n] * invfct[n-k] % MOD * invfct[k] % MOD

factorial(2 * n)

if k >= n:
    print(binomial(2 * n - 1, n) % MOD)
else:
    answer = 0
    for i in range(k+1):
        answer += binomial(n, i) * binomial(n-1, i)
        answer %= MOD
    print(answer)


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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    vector<double> x(n), y(n);
    vector<int> p(n);
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i], p[i] = i;
    auto cmp = [&](int i, int j) {
        return atan2(x[i], y[i]) < atan2(x[j], y[j]);
    };
    sort(p.begin(), p.end(), cmp);
    auto dist = [&](double x, double y) {
        return sqrt(x * x + y * y);
    };
    double ans = 0;
    for (int i = 0; i < n; i++) {
        double sx = 0, sy = 0;
        for (int j = 0; j < n; j++) {
            sx += x[p[(i+j)%n]], sy += y[p[(i+j)%n]];
            ans = max(ans, dist(sx, sy));
        }
    }
    printf("%.12f\n", ans);
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <stdio.h>
#include <vector>
#include <tuple>

using namespace std;

int main() {
  // https://atcoder.jp/contests/dp/tasks/dp_c

  int N;
  cin >> N;

  vector<int> A(N+1), B(N+1), C(N+1);

  for (auto i = 1; i <= N; i++) {
    cin >> A[i] >> B[i] >> C[i];
  }

  vector<tuple<int, int, int> > P(N+1);

  get<0>(P[1]) = A[1];
  get<1>(P[1]) = B[1];
  get<2>(P[1]) = C[1];

  for (int i =2; i <=N; i++) {
    get<0>(P[i]) = max(  get<1>(P[i-1]) , get<2>(P[i-1]) ) + A[i];
    get<1>(P[i]) = max(  get<0>(P[i-1]) , get<2>(P[i-1]) ) + B[i];
    get<2>(P[i]) = max(  get<0>(P[i-1]) , get<1>(P[i-1]) ) + C[i];
  }

  cout << max(max( get<0>(P[N]), get<1>(P[N])), get<2>(P[N]) ) << endl;

  return 0;
}



Measured memory_bytes: 2560
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

int main()
{
    int n; scanf("%d", &n);
    vector<int> x(n);
    for (int i = 0; i < n; ++i) scanf("%d", &x[i]);

    vector<int> y = x;
    sort(y.begin(), y.end());

    for (int i = 0; i < n; ++i){
        int ans;
        if (x[i] <= y[n/2-1]) ans = y[n/2];
        else ans = y[n/2-1];
        printf("%d\n", ans);
    }

    return 0;
}

Measured memory_bytes: 3712
#include <iostream>
#include <stdio.h>
#include <set>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <limits>

typedef long long int lli;
#define rep(i,s,N) for(int i=s;i<N;i++)
using namespace std;

lli euklid(lli, lli);

int main(void)
{
	int N; cin >> N;
	vector<lli> T(N); rep(i, 0, N)cin >> T[i];
	lli ans = T[0];
	rep(i, 1, N)ans = ans / euklid(ans, T[i])* T[i];
	
	cout << ans << endl;

	return 0;
}

lli euklid(lli a, lli b)
{
	lli x = (a > b) ? a : b;
	lli y = (a <= b) ? a : b;
	lli r = x % y;
	while (r != 0) {
		x = y;
		y = r;
		r = x % y;
	}
	return y;
}



Measured memory_bytes: 256
#include <iostream>
#include <list>
#include <vector>
#include <map>
#include <string>
#include <cmath>
#include <algorithm>

#define REP(i, n) for(int (i)=0;(i)<(n);++(i))
#define MOD 1000000007

typedef long long ll;

using namespace std;
int main(){
    ll N, Q;
    cin >> N >> Q;
    ll parent[200001];
    ll counter[200001];
    for(ll i = 0; i < N - 1; ++i)
    {
    	ll a, b;
    	cin >> a >> b;
    	parent[b] = a;
    }
    for (ll i = 1; i <= N; ++i)
    {
    	counter[i] = 0;
    }

    for (ll q = 0; q < Q; ++q)
    {
    	ll p, x;
    	cin >> p >> x;
    	counter[p] += x;
    }

    for (ll n = 2; n <= N; ++n)
    {
    	counter[n] += counter[parent[n]];
    }

    for (ll n = 1; n <= N; ++n)
    {
    	cout << counter[n] << " ";
    }
}

Measured memory_bytes: 5504
N, M = gets.chomp.split(' ').map{|n| n.to_i}
m = Hash.new { |a, b| a[b] = [] }
M.times do
  a, b = gets.chomp.split(' ').map{|n| n.to_i}
  m[a] << b
  m[b] << a
end

fp = m[1]
f = false
fp.each do |i|
  m[i].each do |j|
    if j == N
      puts "POSSIBLE"
      exit
    end
  end
end

puts "IMPOSSIBLE"

Measured memory_bytes: 30844
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b)) < EPS)

using namespace std;

//????????????
class Point{
  public:
  double x, y;

  Point(double x=0, double y=0): x(x), y(y) {}

  Point operator + (Point p) { return Point(x+p.x, y+p.y); }
  Point operator - (Point p) { return Point(x-p.x, y-p.y); }
  Point operator * (double a) { return Point(a*x, a*y); }
  Point operator / (double a) { return Point(x/a, y/a); }

  double abs() {return sqrt(norm()); }
  double norm() { return x*x+y*y; }

  bool operator < (const Point &p) const{
    return x!=p.x ? x<p.x : y<p.y;
  }

  bool operator == (const Point &p) const{
    return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
  }

};

//(?????¢??????)????????????????????¨????§????????????§??????
typedef Point Vector;

//???????????????
typedef struct Segment{
  Point p1, p2;
}Segment;

//??´??????????§??????????
typedef Segment Line;

//????????????
class Circle{
public:
  Point c;
  double r;
  Circle(Point c = Point(), double r=0.0): c(c), r(r) {}
};

//????§???¢(???????????¨????????????)
typedef vector<Point> Polygon;


//?????????????????????
double dot(Vector a, Vector b){
  return a.x*b.x+a.y*b.y;
}

//?????????????????????
double cross(Vector a, Vector b){
  return a.x*b.y-a.y*b.x;
}

//??´?????????(????????????????????????0????????´???)
bool isOrthogonal(Vector a, Vector b){
  return equals(dot(a,b), 0.0);
}
bool isOrthogonal(Point a1, Point a2, Point b1, Point b2){
  return isOrthogonal(a1- a2, b1-b2);
}
bool isOrthogonal(Segment s1, Segment s2){
  return equals(dot(s1.p2-s1.p1, s2.p2-s2.p1), 0.0);
}

//????????????(??????????????????????????§?????????0????????????)
bool isParallel(Vector a, Vector b){
  return equals(cross(a,b), 0.0);
}
bool isParallel(Point a1, Point a2, Point b1, Point b2){
  return isParallel(a1- a2, b1-b2);
}
bool isParallel(Segment s1, Segment s2){
  return equals(cross(s1.p2-s1.p1, s2.p2-s2.p1), 0.0);
}

//???????????´??????????°???±
Point project(Segment s, Point p){
  Vector base = s.p2 - s.p1;
  double r = dot(p-s.p1, base) / base.norm();
  return s.p1 + base*r;
}

//????°?(??´??????????????????????§°?????????????????????)
Point reflect(Segment s, Point p){
  return p+(project(s,p)-p)*2.0;
}

int main(){
  Segment s;
  cin >> s.p1.x >> s.p1.y >> s.p2.x >> s.p2.y;

  int q;
  scanf(" %d", &q);
  for(int i=0; i<q; ++i){
    Point p;
    cin >> p.x >> p.y;
    Point ans=reflect(s,p);
    printf("%.10lf %.10lf\n", ans.x, ans.y);
  }

}

Measured memory_bytes: 1276
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
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;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef tuple<ll,ll,ll> tlll;
typedef tuple<int,int,int> tiii;
const ll mod=1e9+7;
const ll inf=1ll<<60;

ll dp[110][110];

int main(){
  int n,m;
  cin >> n >> m;
  vector<tiii> edges;
  rep(i,n)rep(j,n) dp[i][j]=inf;
  rep(i,n) dp[i][i]=0;
  rep(i,m){
    int a,b,c;
    cin >> a >> b >> c;
    edges.emplace_back(a,b,c);
    dp[a][b]=c;
  }
  vector<ll> dist(n,inf);
  dist[0]=0;
  bool update=true;
  int step=0;
  while(update){
    update=false;
    rep(i,m){
      int a,b,c;
      tie(a,b,c)=edges[i];
      if(dist[a]+c<dist[b]){
        update=true;
        dist[b]=dist[a]+c;
      }
    }
    step++;
    if(step>n){
      cout << "NEGATIVE CYCLE" << endl;
      return 0;
    }
  }
  rep(k,n){
    rep(i,n){
      rep(j,n){
        if(dp[i][k]!=inf&&dp[k][j]!=inf) chmin(dp[i][j],dp[i][k]+dp[k][j]);
      }
    }
  }
  rep(i,n){
    rep(j,n){
      if(dp[i][j]<inf) cout << dp[i][j];
      else cout << "INF";
      if(j<n-1) cout << " ";
    }cout << endl;
  }
}



Measured memory_bytes: 3300
#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll mod = 998244353;

int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    int S = 0;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        S += A[i];
    }
    vector<vector<ll>> dp(N+1, vector<ll>(S+1, 0));
    dp[0][0] = 2;
    dp[0][A[0]] = 1;
    for (int i = 1; i < N; i++) {
        for (int j = 0; j <= S; j++) {
            dp[i][j] = dp[i-1][j]*2;
            if (j >= A[i]) {
                dp[i][j] += dp[i-1][j-A[i]];
            }
            dp[i][j] %= mod;
        }
    }
    ll ans = 1;
    for (int i = 0; i < N; i++) ans = ans*3%mod;
    for (int i = (S+1)/2; i <= S; i++) {
        ans = (ans + mod - 3*dp[N-1][i]%mod)%mod;
    }
    
    if (S%2 == 0) {
        vector<vector<ll>> dp2(N, vector<ll>(S/2+1, 0));
        dp2[0][0] = 1;
        dp2[0][A[0]] = 1;
        for (int i = 1; i < N; i++) {
            for (int j = 0; j <= S/2; j++) {
                dp2[i][j] = dp2[i-1][j];
                if (j >= A[i]) {
                    dp2[i][j] += dp2[i-1][j-A[i]];
                }
                dp2[i][j] %= mod;
            }
        }
        ans = (ans + 3*dp2[N-1][S/2])%mod;
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 317632
#include<iostream>
using namespace std;
int main()
{
	int h,w;
	char ch[101][101];
	cin>>h>>w;
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			cin>>ch[i][j];
		}
	}
	for(int i=0;i<h+2;i++)
	{
		for(int j=0;j<w+2;j++)
		{
			if(i==0||i==h+2-1)
			{
				cout<<"#";
			}
			else
			{
				if(j==0||j==w+2-1)
				{
					cout<<"#";
				}
				else
				{
					cout<<ch[i-1][j-1];
				}
			}
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
require "set"

n = gets.to_i
m = 10**6
a = gets.split.map(&:to_i).sort
num = a.tally
seen = Set.new # 倍数消込

ans = 0
a.each do |i|
  next if seen === i
  ans += 1 if num[i] == 1

  i.step(m, i) do |j|
    seen << j
  end
end
puts ans


Measured memory_bytes: 74000
int main(void) {
    int n, m, en, i, l;
    int H[100], W[100];
    en = 0;
    for ( n = 0 ; en == 0 ; n++ ) {
        scanf("%d %d", &H[n], &W[n]);
        if ( H[n] == 0 && W[n] == 0 )   en = 1;
    }
    for ( m = 0; m < n - 1 ; m++ ) {
        for ( i = 0; i < H[m]; i++ ) {   
            for ( l = 0; l < W[m]; l++ ) {
                printf("#");
            }
            printf("\n");
        }
    printf("\n");
    }
    return 0;
}


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

using namespace std;

#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define pb push_back
#define fi first
#define se second
typedef long long ll;
const int N = 2e5 + 100;

inline ll rd() {
  ll s = 0, w = 1; char c = getchar();
  while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
  while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
  return s * w;
}

ll n, k, a[N], fst[N], tot, pos;
pair <ll, ll> p[N];
vector <ll> r[N], ans;

inline void calc() {
  rep(i, 1, N - 100) {
    if (!r[i].size()) continue ; int len = r[i].size();
    rep(j, 0, len - 1) {
      if (j != len - 1)
        p[r[i][j]].fi = (r[i][j + 1] + 1) % n,
        p[r[i][j]].se = r[i][j + 1] + 1 - r[i][j];
      else
        p[r[i][j]].fi = (r[i][0] + 1) % n,
        p[r[i][j]].se = n - r[i][j] + r[i][0] + 1;
    }
  }
}

int main() {
  n = rd(), k = rd(); memset(fst, -1, sizeof(fst));
  rep(i, 0, n - 1) r[a[i] = rd()].pb(i);
  calc(); tot = pos = 0; ll s = n * k - 1;
  while (tot + p[pos].se <= s) {
    if (fst[pos] != -1) {
      ll K = tot - fst[pos], h = (n * k - fst[pos]) % K;
      if (h == 1ll) { puts(""); return 0; }
      h = (!h ? K - 1 : h - 1);
      s =  fst[pos] + h, tot = fst[pos];
      break ;
    }
    else fst[pos] = tot;
    tot += p[pos].se, pos = p[pos].fi;
  }
  if (s == tot + p[pos].se - 1) { puts(""); return 0; }
  while (tot <= s) {
    while (tot + p[pos].se <= s) tot += p[pos].se, pos = p[pos].fi;
    if (tot + p[pos].se - 1 == s) break ;
    ans.pb(a[pos]), (++pos) %= n, tot++;
  }
  int len = ans.size(); if (!len) puts("");
  else {
    rep(i, 0, len - 1) printf("%lld ", ans[i]);
    puts("");
  }
  return 0;
}

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

using namespace std;

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

#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

#define dump(x) cerr<<#x<<" = "<<(x)<<endl
#define debug(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl;

template<class T>
ostream &operator<<(ostream &os, const vector <T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}

template<class T, class U>
ostream &operator<<(ostream &os, const pair <T, U> &p) {
    return os << "(" << p.first << " " << p.second << ")";
}

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

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;

const ll MOD = 1e9 + 7;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
const ld eps = 1e-6;

struct edge {
    int to;
    ll cost;
};

vector<ll> dijkstra(const vector<vector<edge>> &g, int s) {
    vector<ll> d(g.size(), LINF);

    using Pi = pair<ll, int>;
    priority_queue<Pi, vector<Pi>, greater<Pi>> que;
    d[s] = 0;
    que.emplace(d[s], s);
    while (!que.empty()) {
        ll cost;
        int v;
        tie(cost, v) = que.top();
        que.pop();
        if (d[v] < cost) continue;
        for (auto &e : g[v]) {
            ll nxt = cost + e.cost;
            if (d[e.to] > nxt) {
                d[e.to] = nxt;
                que.emplace(nxt, e.to);
            }
        }
    }
    return d;
}


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

    int N, M, S;
    cin >> N >> M >> S;

    const int MAXS = 5000;

    vector<vector<edge>> G(N * MAXS);
    REP(i, M) {
        int u, v, a, b; cin >> u >> v >> a >> b;
        --u, --v;
        FOR(s, a, MAXS) {
            G[u * MAXS + s].push_back((edge){
                v * MAXS + s - a, b });
            G[v * MAXS + s].push_back((edge){
                    u * MAXS + s - a, b });
        }
    }
    REP(i, N) {
        int c, d; cin >> c >> d;
        REP(s, MAXS) {
            G[i * MAXS + s].push_back((edge){
                i * MAXS + min(s + c, MAXS-1), d});
        }
    }

    auto dist = dijkstra(G, min(S, MAXS-1));

    vll ans(N, LINF);
    FOR(i, 1, N) {
        REP(s, MAXS) {
            chmin(ans[i], dist[i * MAXS + s]);
        }
        cout << ans[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 44444
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace Tasks
{
    public class D
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var NMaMb = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
            var (N, Ma, Mb) = (NMaMb[0], NMaMb[1], NMaMb[2]);
            var ABC = new (int A, int B, int C)[N];
            (int A, int B, int C) sum = (0, 0, 0);
            for (var i = 0; i < N; i++)
            {
                var abc = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
                var (a, b, c) = (abc[0], abc[1], abc[2]);
                ABC[i] = (a, b, c);
                sum = (sum.A + a, sum.B + b, sum.C + c);
            }

            var dp = new int[2][][];
            var Infinity = (int)1e9;
            var inst = Enumerable.Repeat(Infinity, sum.B + 1);
            for (var i = 0; i < 2; i++)
            {
                dp[i] = new int[sum.A + 1][].Select(x => x = inst.ToArray()).ToArray();
            }
            dp[0][0][0] = 0;
            var t = 1;
            for (var i = 0; i < N; i++)
            {
                t ^= 1;
                for (var a = 0; a <= sum.A; a++)
                {
                    for (var b = 0; b <= sum.B; b++)
                    {
                        if (dp[t][a][b] == Infinity) continue;
                        dp[t ^ 1][a][b] = Math.Min(dp[t ^ 1][a][b], dp[t][a][b]);
                        dp[t ^ 1][a + ABC[i].A][b + ABC[i].B] = Math.Min(dp[t ^ 1][a + ABC[i].A][b + ABC[i].B], dp[t][a][b] + ABC[i].C);
                    }
                }
            }

            var answer = Infinity;
            t ^= 1;
            for (var a = 1; a <= sum.A; a++)
            {
                for (var b = 1; b <= sum.B; b++)
                {
                    if (a * Mb == b * Ma) answer = Math.Min(answer, dp[t][a][b]);
                }
            }
            if (answer == Infinity) answer = -1;

            Console.WriteLine(answer);
        }
    }
}


Measured memory_bytes: 28880
import typing
n = int(input())
a = list(map(int, input().split()))

def gcd(x : int, y : int):
    x, y = min(x, y), max(x, y)
    while True:
        mod = y % x
        if mod == 0:
            break
        y = x
        x = mod

    return x

lcm = a[0]
for i in range(1, n):
    lcm = lcm * a[i] // gcd(lcm, a[i])

res = 0
for i in range(n):
    res += (lcm - 1) % a[i]
print(res)

Measured memory_bytes: 10396
import numpy as np
h,w,k = map(int,input().split())
c = list(list(input()) for i in range(h))
c = np.array(c)
ans = 0
for i in range(2**h):
    for j in range(2**w):
        x = i
        y = j
        s = np.copy(c)
        n = 0
        while x > 0:
            if x % 2 == 1:
                for l in range(w):
                    s[n][l] = '0'
            x = x // 2
            n += 1
        m = 0
        while y > 0:
            if y % 2 == 1:
                for l in range(h):
                    s[l][m] = '0'
            y = y // 2
            m += 1
        p = np.count_nonzero(s == '#')
        if p == k:
            ans += 1
print(ans)

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

# define F first    
# define S second
# define mp make_pair
// everything go according to my plan      
# define pb push_back
# define sz(a) (int)(a.size())
# define vec vector
// shimkenttin kyzdary, dzyn, dzyn, dzyn...
# define y1    Y_U_NO_y1
# define left  Y_U_NO_left
# define right Y_U_NO_right  

using namespace std;

typedef pair <int, int> pii; 
typedef long long ll;
typedef long double ld;

const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const ll MXLL = 4e18;
const int Sz = 1110111;
// a pinch of soul
inline void Read_rap () {
  ios_base :: sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}
inline void randomizer3000 () {
  unsigned int seed;
  asm ("rdtsc" : "=A"(seed));
  srand (seed);
}
void files (string problem) {   
  if (fopen ((problem + ".in").c_str(),"r")) {
    freopen ((problem + ".in").c_str(),"r",stdin);
    freopen ((problem + ".out").c_str(),"w",stdout);
  }
}
int n, m;

vec<int> g[Sz];

bool used[Sz];    

void dfs (int v, vec<int> &p) {
  p.pb (v);
  used[v] = 1;
  for (int to : g[v]) {
    if (!used[to]) {
      dfs (to, p);
      return;
    }
  }
}

int main()
{
  Read_rap();
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int x, y; cin >> x >> y;
    g[x].pb (y);
    g[y].pb (x);
  }  
  vec<int> a, b;
  dfs (1, b), dfs (1, a);
  reverse (a.begin(), a.end());
  a.pop_back();
  cout << sz(a) + sz(b) << endl;
  for (int x : a)
    cout << x << ' ';
  for (int x : b)
    cout << x << ' ';


  return 0;
}






// Coded by Z..


Measured memory_bytes: 33400
#include<bits/stdc++.h>
#define LiangJiaJun main
using namespace std;
int a,b,l;
char s[14];
int LiangJiaJun(){
    scanf("%d%d",&a,&b);
    scanf("%s",s+1);
    l=strlen(s+1);
    for(int i=1;i<=a;i++){
        if(!isdigit(s[i]))return puts("No"),0;
    }
    if(s[a+1]!='-')return puts("No"),0;
    for(int i=a+2;i<=a+b+1;i++)if(!isdigit(s[i]))return puts("No"),0;
    puts("Yes");
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rep1(i, n) for (int i = 1; i < n; ++i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)
ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

void solve() {
  // main coding
  int n,k;
  cin>>n>>k;
  int h;
  int ans=0;
  rep(i,n){
    cin>>h;
    ans+=(h>=k);
  }
  cout<<ans<<endl;
}

int main() {
  solve();
  return 0;
}


Measured memory_bytes: 256