akhauriyash/Code-Regression huggingface dataset:
use proconio::input;

fn main() {
   input! {
      dn: usize,
      c: [i64; 26],
      s: [[i64;26]; dn],
   }

   let mut last = vec![0; 26];
   for d in 0..dn {
      let mut mx = std::i64::MIN;
      let mut tn = 0;
      for t in 0..26 {
         let mut score = 0i64;
         score += s[d][t];
         for j in 0..26 {
            if j != t {
               score -= c[j] * (d + 1 - last[j]) as i64;
            }
         }
         if score > mx {
            mx = score;
            tn = t;
         }
      }
      last[tn] = d + 1;
      println!("{}", tn + 1);
   }
}


Measured memory_bytes: 2324
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define LLINF 1000000000000000ll
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
int cnt[5];
int main(){
	string s;
	cin >> s;
	for(int i=0;i<s.size();i++)cnt[s[i]-'a']++;
	for(int i=0;i<3;i++){
		if(cnt[i]!=1){
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define pb push_back
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = 5*(int)1e5 + 10;

int n, a[N], x, d[N];

int32_t main(){_

   cin>>n>>x;

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

   int ans = 1;
   for (int i = 2; i <= n+1; ++i)
   {
      d[i] = d[i-1] + a[i-1];
      tr(i, a[i], d[i]);
      if(d[i] <= x)
         ans++;
   }

   cout<<ans;


   return 0;
}

// Common sense: do smth instead of nothing
// Even a single second counts...
// If other's can do it, even I can do it. It wouldn't be that tough. Let me give it a try.
// Mistakes made in past
// -Ques. ask for max-min => think binary_search, DP, greedy
// -not reading question properly / skipping to read & understand all samples properly & wasting time in wrong direction.
// -Using wrong indexing in nested loops something like a[i], when it is supposed to be a[j](WA)
// -value of const int N is not correct (WA/RTE).
// -Did you memset dp to -1 ?
// -check for small edges cases and work on small test cases manually if WA
// -not deallocating memory to pointers can lead to MLE. Use delete :))
// -not reading problem statements of harder problems E,..., thinking it couldn't be solved, but it isn't the case.
// -Avoid using #define int long long as much as possible when it's dp problem and requires high memory say, O(N^2, N=5000) (MLE)
// -Check Bitwise Operator Precedence 
// -Use pragmas to optimize (by constant factor) when necessary..
// -Think before coding & starting to debug. Have patience to look inside code and actually see how it works

Measured memory_bytes: 2304
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();
        int slength = s.length();
        int tlength = t.length();

        String t2 = t.substring(0, slength);
        
        if( tlength - slength ==1 ){
            if(s.equals(t2)){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }
        }else{
            System.out.println("No");
        }

    }
}


Measured memory_bytes: 35720
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define int long long int
using namespace std;

int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      string s;
      cin>>s;
      int n=s.length();
      vector<int> arr;
      vector<bool> Q;
      int cnt=1;
      for(int i=1;i<n;i++){
            if(s[i]==s[i-1]){
                  cnt++;
            }
            else {
                  arr.pb(cnt);
                  cnt=1;
                  Q.pb(s[i-1]=='<');
            }
      }
      arr.pb(cnt);
      Q.pb(s.back()=='<');
      int ans=0;
      vector<int> q;
      q.pb(0);
      for(int i=0;i<arr.size();i++){
            if(Q[i]){
                  for(int j=0;j<arr[i];j++)q.pb(q.back()+1);
            }
            else {
                  if(q.back()<arr[i])q[q.size()-1]=arr[i];
                  q.pb(arr[i]-1);
                  for(int j=1;j<arr[i];j++)q.pb(q.back()-1);
            }
      }
      for(int i=0;i<q.size();i++){
            ans+=q[i];
      }
      cout<<ans;
}


Measured memory_bytes: 7508
#include <bits/stdc++.h>
using std::cout;
using std::endl;
using std::cin;

int main(){
	std::string s; cin >> s;
	
	if((s.front() == s.back()) ^ (s.size() % 2)) cout << "First" << endl;
	else cout << "Second" << endl;
	return 0;
}


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

typedef long double ld;
typedef long long ll;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1e9 + 7;

int main(){
    int64_t N, X[50], Y[50];
    cin >> N;
    std::map<std::pair<ll, ll>, bool> mp;
    for(int i=0; i<N; i++){
        cin >> X[i] >> Y[i];
        mp[{X[i], Y[i]}] = true;
    }
    int ans = N;
    for(int i=0; i<N; i++) for(int j=0; j<N; j++){
        if(i==j) continue;
        int64_t x = X[i] - X[j], y = Y[i] - Y[j];
        int res = N;
        for(int k=0; k<N; k++) if(mp[{X[k]+x, Y[k]+y}] == true) res--;
        ans = min(ans, res);
    }
    cout << ans << endl;
    return 0;
}


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

int main() {
    long H, N;
    cin>>H>>N;
    long tmp;
    long sum = 0;
    for(int i=0;i<N;++i){
        cin>>tmp;
        sum += tmp;
    }
    if(sum >= H)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


Measured memory_bytes: 256
N, M = input().split()

N = int(N)
M = int(M)
a = []
c = []

for i in range(M):

    anew = int(input())
    a.append(anew)

now_a = 0
a.append(-1)
ans = 0

for i in range( N + 1 ):

    if (i == 0):
        c.append(1)
        
    elif (i == 1):

        if (a[now_a] == i):
            c.append(0)
            now_a += 1
        else:
            c.append(1)

    else:

        if (a[now_a] == i):
            c.append(0)
            now_a += 1
        else:
            c.append( c[i - 1] + c[i - 2])
        

ans = c[N] % 1000000007

print (ans)
    


Measured memory_bytes: 460020
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define sz(x) (int)x.size()
typedef pair<int,int>pii;
const int mxN=1e5+10,M=1e9+7;
int n,a,b,d;
int dist[mxN],vis[mxN];
vector<pii>adj[mxN];
void bfs(){
    queue<int>fila;
    fila.push(1);
    vis[1]=true;
    while(!fila.empty()){
        int u=fila.front();
        fila.pop();
        
        for(pii p:adj[u]){
            int d=p.first;
            int v=p.second;
            if(!vis[v]){
                vis[v]=true;
                dist[v]=dist[u]+d;
                fila.push(v);
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<n-1;i++){
        cin>>a>>b>>d;
        adj[a].pb({d,b});
        adj[b].pb({d,a});
    }
    bfs();
    for(int i=1;i<=n;i++){
        cout<<(dist[i]&1)<<"\n";
    }
}

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

typedef long long int ll;
#define rep(i,n) for(int i = 0; i < n; i++)

int main() {
  int n,k;
  cin >> n >> k;
  double ans = 0;
  for (int i = 0; i < n; i++) {
    double cnt = 1 / (double) n;
    ll score = i+1;
    while (score < k) {
      score *= 2;
      cnt = cnt/2;      
    }
    ans += cnt;
  }
  cout << fixed << setprecision(12) << ans << endl;
  return 0;
}

Measured memory_bytes: 3752
# standart input
# n = int(input())
# a = list(map(int, input().split()))

n = int(input())
x = 0
count = 0

while n >= x:
    n_digit = 0
    xx = x
    while xx != 0:
        xx = xx // 10
        n_digit += 1
    if n_digit % 2 == 1:
        count += 1
    x += 1

print(count)


Measured memory_bytes: 2940
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,Q=map(int,input().split())
a=tuple(map(int1,input().split()))
lr=[[0,0,i] for i in range(Q)]
for i in range(Q):
    lr[i][0],lr[i][1]=map(int1,input().split())
lr.sort(key=lambda t: t[1],reverse=1)
class RangeBIT:
    def __init__(self,n):
        self.p=self.BIT(n+1)
        self.q=self.BIT(n+1)
    
    def add(self,s,t,x):
        self.p.add(s,-x*s)
        self.p.add(t,x*t)
        self.q.add(s,x)
        self.q.add(t,-x)
    
    def sum(self,s,t):
        return self.p.sum(t)+self.q.sum(t)*t-self.p.sum(s)-self.q.sum(s)*s
    
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s

b=RangeBIT(N)
lastap=[-1]*N
ans=[-1]*Q
l,r,j=lr.pop()
for i,x in enumerate(a):
    if lastap[x]!=-1:
        b.add(lastap[x],lastap[x]+1,-1)
    b.add(i,i+1,1)
    lastap[x]=i
    while r==i:
        ans[j]=b.sum(l,r+1)
        if lr:
            l,r,j=lr.pop()
        else:
            l,r,j=-1,-1,-1
for x in ans:
    print(x)

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

using namespace std;

#define ll long long
#define ar array

int k;

void solve(){

    cin >> k;
    string s;
    cin >> s;

    if(s.length() <= k){
        cout << s << endl;
    }
    else{

        s = s.substr(0,k);
        s += "...";
        cout << s << endl;
    }

}





int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

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

void out_seat(vector<vector<int>> s, vector<vector<bool>> l){
    rep(i,s.size()){
        rep(j,s.at(i).size()){
            if(l.at(i).at(j)) cout << "x";
            else cout << s.at(i).at(j);
        }
        cout << endl;
    }
}

int main(){
    int n;
    cin >> n;
    vector<int> x(n*n);
    rep(i,n*n) cin >> x.at(i);
    vector<vector<int>> seat(n);
    vector<vector<bool>> lvfl(n);
    rep(i,n){
        rep(j,n){
            int d = min(min(min(i,j),n-i-1),n-j-1);
            seat.at(i).push_back(d);
            lvfl.at(i).push_back(false);
        }
    }
    
    ll tot=0;
    queue<pair<int,int>> q;
    for(int cur: x){
        q.push({(cur-1)%n,(cur-1)/n});
        lvfl.at((cur-1)/n).at((cur-1)%n) = true;
        tot += seat.at((cur-1)/n).at((cur-1)%n);
        while(q.size()){
            auto p = q.front(); q.pop();
            int cx = p.first,cy = p.second;
            // cout << cx << " " << cy << endl;
            pair<int,int> plist[] = { {cx-1,cy}, {cx,cy-1}, {cx+1,cy}, {cx,cy+1} };
            int ofs = lvfl.at(cy).at(cx) ? 0 : 1;
            for(auto pp : plist){
                if(pp.first < 0) continue;
                if(pp.second < 0) continue;
                if(pp.first >= n) continue;
                if(pp.second >= n) continue;

                int tx=pp.first,ty=pp.second;
                if(seat.at(cy).at(cx)+ofs < seat.at(ty).at(tx)){
                    seat.at(ty).at(tx) = seat.at(cy).at(cx)+ofs;
                    q.push(pp);
                }
            }

        }
        // cout << "cur : "<< cur << " (" << (cur-1)%n << " , " << (cur-1)/n << ") " << tot << endl;
        // out_seat(seat,lvfl);
    }
    cout << tot << endl;
    return 0;
}

Measured memory_bytes: 5280
#include <bits/stdc++.h>
#define il inline
#define RG register
#define ll long long

using namespace std;

int a[100010],n;

il int gi(){
  RG int x=0,q=1; RG char ch=getchar();
  while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
  if (ch=='-') q=-1,ch=getchar();
  while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
  return q*x;
}

int main(){
  n=gi();
  for (RG int i=1;i<=n;++i) a[i]=gi();
  sort(a+1,a+n+1),reverse(a+1,a+n+1);
  for (RG int i=1;i<=n;++i)
    if (i+1>a[i+1]){
      RG int res=1;
      for (RG int j=i+1;a[j]==i;++j) res^=1;
      res&=(a[i]-i+1)&1;
      puts(res ? "Second" : "First"); break;
    }
  return 0;
}


Measured memory_bytes: 640
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 21 21:05:17 2020

@author: naoki
"""

N,K = map(int,input().split())
p = list(map(int,input().split())) 
p.sort()
count = 0 
for i in range(K):
    count += p[i]
print(count)

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

int main(){
	int n;
	int i=0;
	int j=0;
	int k=0;
	int cash=1;
	int dp[100010];
	cin>>n;
	dp[0]=0;
	for(i=1;i<n;i++){
		dp[i]=1000000000;
	}
	for(i=1;i<n+1;i++){
		dp[i]=dp[i-1]+1;
		if(i>=6){
			for(j=0;j<n;j++){
				//for(k=0;k<j+1;k++){
					cash=cash*6;
					if(cash>i)break;
				
					if(dp[i]>dp[i-cash]+1){
						dp[i]=dp[i-cash]+1;
					}
				//}
				
				
			}
		//	cout<<cash<<endl;
		}
		cash=1;
		if(i>=9){
			for(j=0;j<n;j++){
			//	for(k=0;k<j+1;k++){
					cash=cash*9;
					if(cash>i)break;
					if(dp[i]>dp[i-cash]+1){
						dp[i]=dp[i-cash]+1;
				
					}
			//	}
				
			}
		//	cout<<cash<<endl;
		}
		cash=1;
	}
	cout<<dp[n]<<endl;
}


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

int main() {
    int n;
    cin >> n;
    vector<int> h(n);
    rep(i,n) cin >> h[i];
    int ans = 0;
    rep(i,n) {
        bool ok = true;
        rep(j,i) {
            if (h[j] > h[i]) {
                ok = false;
                break;
            }
        }
        if (ok) ans++;
    }
    cout << ans << endl;
}

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

struct Button {
  int sx, sy, ex, ey;
  string to;
  bool isHit(int x, int y) {
    return ( sx <= x && x <= ex &&
	     sy <= y && y <= ey );
  }
};

struct Page {
  vector<Button> buttons;
  string click(int x, int y) {
    for(int i = 0; i < buttons.size(); ++i) {
      if(buttons[i].isHit(x,y)) return buttons[i].to;
    }
    return "";
  }
};

int W, H;
map<string, Page> Pages;
vector<string> Buff;
int pi, br;

int main() {
  int n, m;
  string np;
  while(cin >> n && n) {
    Pages.clear();
    np = "";
    cin >> W >> H;
    while(n--) {
      Page p;
      string name;
      int b;
      cin >> name >> b;
      if(np == "") np = name;
      while(b--) {
	Button bn;
	cin >> bn.sx >> bn.sy >> bn.ex >> bn.ey >> bn.to;
	p.buttons.push_back(bn);
      }
      Pages[name] = p;
    }
    cin >> m;
    Buff.resize(m*2);
    Buff[0] = np;
    pi = 0;
    br = 1;
    while(m--) {
      string op;
      cin >> op;
      if(op == "click") {
	int x, y;
	cin >> x >> y;
	string to = Pages[Buff[pi]].click(x,y);
	if(to != "" && Pages.count(to)) {
	  ++pi;
	  Buff[pi] = to;
	  br = pi+1;
	}
      } else if(op == "back") {
	if(pi != 0) {
	  --pi;
	}
      } else if(op == "forward") {
	if(pi+1 != br) {
	  ++pi;
	}
      } else if(op == "show") {
	cout << Buff[pi] << endl;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 0
# ベクトルを既約分数にしてなおかつ方向を第一象限か第二象限に集める

from collections import defaultdict
from math import gcd
N = int(input())
MOD = 10**9 + 7
d = defaultdict(lambda: [0, 0])
zeros = 0
for _ in range(N):
    x, y = map(int, input().split())
    if x == 0 and y == 0:
        zeros += 1
    elif x == 0:
        d[(0, 0)][0] += 1
    elif y == 0:
        d[(0, 0)][1] += 1
    else:
        if y < 0:
            x = -x
            y = -y
        g = gcd(abs(x), abs(y))
        x //= g
        y //= g
        if x < 0:
            d[(y, -x)][0] += 1
        else:
            d[(x, y)][1] += 1
ans = 1
for k, v in d.items():
    ans *= pow(2, v[0], MOD)+pow(2, v[1], MOD)-1
    ans %= MOD
ans = (ans + zeros - 1) % MOD  # 各ベクトル対の組から一つも選ばないパターンを引いてる
print(ans)


Measured memory_bytes: 60760
#include<iostream>
#include<bits/stdc++.h>
#include<iomanip>
#include<math.h>
#include<vector>
#include<cctype>
#include<string>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
std::string line;

int main(){

    int n;
    string s;
    cin >> n;
    cin >> s;

    for(int i=0;i<s.size();i++){
        if( (s[i]+n)>90){
           int buf = s[i] + n - 90;
           s[i] = 64 + buf; 
        }else{
        s[i] = s[i] + n; 
        }
    }

    cout << s << endl;


   return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <set>
#include <map>
#include <utility>
#include <queue>

int main() {
  size_t N, K;
  scanf("%zu %zu", &N, &K);

  char buf[131072];
  scanf("%s", buf);
  std::string s = buf;

  std::vector<int> A{0};
  for (size_t i = 1; i < N; ++i) {
    if (s[i-1] == s[i]) {
      ++A.back();
    } else {
      A.push_back(0);
    }
  }

  for (size_t i = 0; i < K; ++i) {
    // for (size_t i = 0; i < A.size(); ++i)
    //   fprintf(stderr, "%d%c", A[i], i+1<A.size()? ' ': '\n');

    if (A.size() == 1) break;
    if (A.size() == 2) {
      int a0 = A.back();
      A.pop_back();
      A.back() += a0 + 1;
    } else {
      int a0 = A.back();
      A.pop_back();
      int a1 = A.back();
      A.pop_back();
      A.back() += a0 + a1 + 2;
    // } else {
    //   int a0 = A.back();
    //   A.pop_back();
    //   int a1 = A.back();
    //   A.pop_back();
    //   int a2 = A.back();
    //   A.pop_back();
    //   A.back() += a0 + a1 + a2 + 3;
    // }
    }
  }

  printf("%d\n", std::accumulate(A.begin(), A.end(), 0));
}


Measured memory_bytes: 1020
#include<cstdio>
#include<iostream>
#include<ctime>
#include<string>
#include<algorithm>
#include<cmath>
int a[100010],len;
using namespace std;
int main()
{
	int n,now,cnt=0,ans=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	} 
	sort(a,a+n);
	now=a[0];
	for(int i=0;i<n;i++)
	{
		if(a[i]==now)
		{
			cnt++;
		}
		if(a[i]!=now)
		{
			if(cnt%2!=0)
			{
				ans++;
			}
			now=a[i];
			cnt=0;
			i--;
		}
	}
	if(cnt%2!=0)ans++;
	printf("%d",ans);
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main(void){
    string A,B;
    cin >> A >> B;
    if(A.length() == B.length()){
        if(A == B){
            cout << "EQUAL" << endl;
        } else if(A > B){
            cout << "GREATER" << endl;
        }else{
            cout << "LESS" << endl;
        }
    }else if(A.length() > B.length()){
        cout << "GREATER" << endl;
    }else{
        cout << "LESS" << endl;
    }

    return 0;
}

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

int main() {
  int five = 0;
  int seven = 0;
  int x;
  for(int i=0; i<3; i++){
    cin >> x;
    if (x==5) five++;
    if (x==7) seven++;
    else continue;
  }
  if(five==2 && seven==1){
    cout << "YES" << endl;
  }
  else{
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64
#define rep(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define V(T) vector<T>
typedef pair<int, int> P;
typedef pair<P, P> PP;
typedef vector<int> vi;
typedef vector<vi> vvi;
int max(int a, int b) {if(b>a) return b; else return a;}
int min(int a, int b) {if(b<a) return b; else return a;}


signed main() {
    string c1, c2;
    cin >> c1 >> c2;
    
    bool res = true;
    rep(i, 3) {
        if(c1[i] != c2[2-i]) res = false;
    }

    if(res) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define N 10000000
#define M 17
using namespace std;
typedef long long LL;
LL ten[M+1];
vector<LL> a;
long double S(LL n)
{
	int ans = 0;
	while(n>0)
	{
		ans += n%10;
		n /= 10;
	}
	return ans;
}
long double f(LL x)
{
	return x/S(x);
}
vector<LL> snukes;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	ten[0] = 1;
	for(int n = 1; n <= M; n++)
		ten[n] = ten[n-1]*10LL;

	for(int nine_count = 0; nine_count <= M; nine_count++)
		for(LL x = 0; x < ten[min(4,18-nine_count)]; x++)
			if(x%10!=9)
				a.push_back(x*ten[nine_count]+ten[nine_count]-1LL);
	sort(a.begin(),a.end());

	long double best = 1e18;
	for(int i = a.size()-1; i >=0; i--)
		if(f(a[i]) <= best)
		{
			//cout<<f(a[i])<<endl;
			snukes.push_back(a[i]);
			best = f(a[i]);
		}

	reverse(snukes.begin(),snukes.end());

	int k; cin >> k;
	for(int i = 0; i < k; i++)
		cout<<snukes[i]<<endl;

	return 0;
}


Measured memory_bytes: 2420
#include<bits/stdc++.h>
using namespace std;
const int M=4e3+200;
int a[M][M];
int main(){
	long long n;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<n;j++){
			scanf("%d",&a[i][j]);
		}
		a[i][0]=1;
	}
	long long num=n*(n-1)/2;
	int flag=0;
	long long ans=0;
	long long i=0;
	while(1){
		ans++;
		int flag2=0;
		int used[M]={0};
		for(int j=1;j<=n;j++){
			long long k=a[j][0];
			if(k!=n&&!used[j]){
				long long t1=a[j][k];
				long long k2=a[t1][0];
				long long t2=a[t1][k2];
				if(!used[t1]&&t2==j){
					a[t1][0]++;
					a[j][0]++;
					used[t1]=1;
					used[j]=1;
					flag2=1;
					i++;
				}
			}
		}
		if(!flag2){
			flag=1;
			break;
		}
		if(i==num){
			break;
		}
	}
	if(flag){
		printf("-1\n");
	}else{
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 17664
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define fi first
#define se second
typedef pair<int,int> P;
typedef pair<int, P> PP;
const int inf = 1e9+7;
const int INF = 1e18+7;
int mod = 1e9+7;

int a[100010], b[100010];
signed main(){
	int n, T, mx = 0, ans = 0;
	scanf("%lld%lld", &n, &T);
	rep(i,n)scanf("%lld", &a[i]);
	drep(i,n-1,0)b[i] = max(b[i+1], a[i]);
	rep(i,n)mx = max(mx, b[i]-a[i]);
	rep(i,n)if(b[i]-a[i] == mx)ans++;
	printf("%lld\n", ans);
	return 0;
}




Measured memory_bytes: 1792
from itertools import product
H, W, K = map(int, input().split())
MOD = 10**9 + 7

S = [0]*W
S[0] = 1
if W > 1:
    for i in range(H):
        T = [0]*W
        for P in product((0, 1), repeat=W-1):
            if any(P[i] == 1 == P[i+1] for i in range(W-2)):
                continue
            for i in range(W):
                if i < W-1 and P[i]:
                    T[i+1] += S[i]
                    T[i] += S[i+1]
                elif i == 0 or not P[i-1]:
                    T[i] += S[i]
        S = T
        for i in range(W):
            S[i] %= MOD
print(S[K-1])


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

int main(void) {
	string S;
	cin >> S;
	for (int i = 0; i < S.size() - 1; i++) {
		if (S.substr(i, 2) == "AC") {
			cout << "Yes\n";
			return 0;
		}
	}
	cout << "No\n";
	return 0;
}


Measured memory_bytes: 3556
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define mod 1000000007
#define pi  3.1415926535
int main()
{
	ll n,m,i,j,k;
	cin>>n>>k;
	ll a[n];
	for(i=0;i<n;i++)
	{
		cin>>a[i];
	}
	sort(a,a+n);
	ll dp[k+1];
	dp[0]=0;
	for(i=1;i<=k;i++)
	{
		dp[i]=0;
		for(j=0;i>=a[j]&&j<n;j++)
		{
			if(!dp[i-a[j]])
			{
				dp[i]=1;
				break;
			}
		}
	}
	if(dp[k])
	cout<<"First\n";
	else
	cout<<"Second\n";
}


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

string s;
long long k, cnt = 0;

int main() {
  cin >> s >> k;
  while(s[cnt] == '1') ++cnt;
  if(cnt >= k)
    cout << 1 << endl;
  else
    cout << s[cnt] << endl;
  return 0;
}

Measured memory_bytes: 256
#import <stdio.h>
#define MIN(a,b) ((a)<(b)?(a):(b))
int main(){
    int N;
    scanf("%d", &N);
    int min = 200;
    int sum = 0;
    for(int i=0;i<N;i++){
        int s;
        scanf("%d", &s);
        sum += s;
        if (s%10!=0) {
            min = MIN(min,s);
        }
    }
    if (sum%10!=0) {
        printf("%d", sum);
    } else if (min==200) {
        printf("0");
    } else {
        printf("%d", sum - min);
    }
}


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

long long N,A,B;
long long X[100010];
long long ans = 0;

int main()
{
    scanf("%lld%lld%lld",&N,&A,&B);
    for(int i = 0; i < N; i++)
    {
        scanf("%lld",&X[i]);
    }
    for(int i = 0; i < N - 1; i++)
    {
        if((X[i + 1] - X[i]) * A > B)
        {
            ans += B;
        }
        else
        {
            ans += A * (X[i + 1] - X[i]);
        }
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<string>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repn(i, n) for(int i = 1; i <= n; i++)
#define repr(i, n) for(int i = n-1; i >=0; i--)
#define lint long long
#define all(x) (x).begin(), (x).end()


struct union_find{
    vector<int> par;
    vector<int> rank;
    vector<int> size;
    vector<int> count;
    vector<int> pcount;
    union_find(int n) : par(n), rank(n), size(n), count(n), pcount(n){
        for(int i = 0; i < n; i++){
            par[i] = i; rank[i] = 0; size[i] = 1; count[i] = 0; pcount[i] = 0;
        }
    }
    int root (int x){
        if(par[x] == x) return x;
        par[x] = root(par[x]);
        return par[x];
    }
    void unite(int x, int y){
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) { return; }
        if (rank[rx] < rank[ry]){
            par[rx] = ry;
            size[ry] += size[rx];
            count[ry] += count[rx];
            pcount[ry] += pcount[rx];
        }
        else{
            par[ry] = rx;
            size[rx] += size[ry];
            count[rx] += count[ry];
            pcount[rx] += pcount[ry];
            if (rank[rx] == rank[ry]) rank[rx]++;
        }
    }
    bool same(int x, int y){
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
    int get_size(int x){
        int rx = root(x);
        return size[rx];
    }
    int get_count(int x){
        int rx = root(x);
        return count[rx];
    }
    void add_count(int x){
        int rx = root(x);
        count[rx]++;
    }
    void add_pcount(int x){
        int rx = root(x);
        pcount[rx]++;
    }
};


const int MAX_P = 100001;

int main(){
    union_find uf(MAX_P);
    int n; cin>>n;
    vector<int> P[MAX_P];
    rep(i, n){
        int x, y; cin>>x>>y; x--; y--;
        P[x].push_back(y);
    }
    
    rep(x, MAX_P){
        vector<int> Y = P[x];
        if(Y.empty()) continue;
        uf.add_count(Y[0]);
        uf.add_pcount(Y[0]);
        if(Y.size() == 1) continue;
        rep(i, Y.size()-1) {uf.add_pcount(Y[0]); uf.unite(Y[i], Y[i+1]) ;}
    }

    long all = 0;
    rep(x, MAX_P){
        int rx = uf.root(x);
        if (x != rx || uf.size[rx] == 1 || uf.count[rx] == 1) continue;
        all += (long)uf.size[rx] * (long)uf.count[rx] - (long)uf.pcount[rx];
    }

    cout<<all<<endl;
}

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

int main(){
  int c = 0;
  int n;
  string s;
  cin >> n;
  for (int i = 1; i <= n; i++){
    s = to_string(i);
    // cout << s << endl;
    if (s.length() % 2 != 0){
      c += 1;
    }
  }

  cout << c << endl;
}

Measured memory_bytes: 256
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))

counts = [0] * (M + 1)
for a, b in zip(A, A[1:]):
    counts[b] += (b - a) % M
A = np.array(A, dtype=int)
diffs = np.diff(A)
S = (diffs % M).sum()
# お気に入りを1にしたらこれだけ減らせる
reduce = (M - A[:-1][diffs < 0]).sum()
d = (diffs < 0).sum()
ans = S
for x in range(1, M + 1):
    ans = min(ans, S - reduce)
    reduce += d - counts[x]
    if A[0] == x:
        d += 1
    if A[-1] == x:
        d -= 1
print(ans)
# reduces = [0] * N
# s = A[0]
# A[]
# for a in
#
# A[1:].sum()


Measured memory_bytes: 22288
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	int n,W;
	cin >> n >> W ;
	
	ll dp[n+1][W+1];
	ll w[n];
	ll v[n];

	for (int i=0;i<n;i++) cin >> w[i] >> v[i];

	memset(dp,0,sizeof(dp));
	for (int i=1 ; i<=n; i++)
	{
		for (int j=1;j<=W;j++)
		{
			dp[i][j]=dp[i-1][j];
			if (w[i-1]<=j)	dp[i][j]=max(dp[i][j],dp[i-1][j-w[i-1]]+v[i-1]);
		}
	} 
	cout << dp[n][W];
	return 0;
}


Measured memory_bytes: 82460
#include <iostream>
using std::cout;
using std::cin;
using std::endl;

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if (a + b == c + d) {
    cout << "Balanced" << endl;
  } else if (a + b > c + d) {
    cout << "Left" << endl;
  } else {
    cout << "Right" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int main(){
	ll n, k;
	cin >> n >> k;
	ll sum=0;
	for(ll i=k;i<=n+1;i++){
		sum=(sum+i*(n-i+1)+1)%mod;
	}
	cout << sum << endl;
}

Measured memory_bytes: 3640
#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;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-9;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;

long long int gcd(long long int a, long long int b) {
	while (b) {
		a %= b;
		swap(a, b);
	}
	return a;
}

long long int power(long long int x, long long int n, long long int M) {
	long long int ret = 1;
	long long int by = x;
	while (n) {
		if (n & 1) {
			ret *= by;
			ret %= M;
		}
		by *= by;
		by %= M;
		n >>= 1;
	}
	return ret;
}

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

	cin >> N;
	map<pair<long long int, long long int>, map<int,int>>mp;
	long long int zero = 0, xzero = 0, yzero = 0;
	for (int i = 0; i < N; i++) {
		cin >> H >> W;
		long long int g = gcd(abs(H), abs(W));
		if(g)H /= g, W /= g;
		if (!H && !W) {
			zero++;
		}
		else if (!H) {
			yzero++;
		}
		else if (!W) {
			xzero++;
		}
		else {
			if (H > 0 && W > 0) {
				mp[make_pair(abs(H), abs(W))][0]++;
			}
			else if (H > 0) {
				mp[make_pair(abs(W), abs(H))][1]++;
			}
			else if (W > 0) {
				mp[make_pair(abs(W), abs(H))][1]++;
			}
			else {
				mp[make_pair(abs(H), abs(W))][0]++;
			}
		}
	}
	long long int ans = zero;
	long long int non_zero = 1;
	for (auto i : mp) {
		long long int by = power(2, i.second[0], MOD) + power(2, i.second[1], MOD) - 1;
		by %= MOD;
		non_zero *= by;
		non_zero %= MOD;
	}
	ans += non_zero * (power(2, xzero, MOD) + power(2, yzero, MOD) - 1) % MOD;
	ans += MOD - 1;
	ans %= MOD;
	cout << ans << endl;
}

Measured memory_bytes: 34824
// w_1 \le w_i \le w_1 + 3 を有効活用

#include <bits/stdc++.h>
using namespace std;
int N, W;
const int64_t INF = 1e15;
vector<int64_t> w(100), v(100);
// 対象の荷物番号,個数,重さ-w1*個数 -> 価値
int64_t dp[100][100][300];

int64_t recursive(int k, int n, int dw) {
    if(W < n * w[0] + dw) return -INF;
    if(k == N) return 0;
    if(dp[k][n][dw] == -1) {
        dp[k][n][dw] = max(recursive(k + 1, n, dw),
            recursive(k + 1, n + 1, dw + w[k] - w[0]) + v[k]);
    }
    return dp[k][n][dw];
}


int main() {
    #ifdef DEBUG
    std::ifstream in("/home/share/inputf.in");
    std::cin.rdbuf(in.rdbuf());
    #endif
    cin >> N >> W;
    for(int i = 0; i < N; i++) {
        cin >> w[i] >> v[i];
    }
    for(int i = 0; i < 100; i++) {
        for(int j = 0; j < 100; j++) {
            for(int k = 0; k < 300; k++) {
                dp[i][j][k] = -1;
            }
        }
    }
    recursive(0, 0, 0);
    cout << dp[0][0][0] << endl;
    return 0;
}

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

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

const ll MAX=505000;
const ll INF=0x3f3f3f3f3f3f3f;
ll p,q,tmp[MAX],ans[MAX],d[MAX],dtot[MAX],near[MAX],N,D,Q;
int main(){
    scanf("%lld%lld",&N,&D);
    for(ll i=0;i<N;i++) scanf("%lld",&d[i]);
    dtot[0]=D;
    for(ll i=1;i<=N;i++) dtot[i]=min(dtot[i-1],abs(d[i-1]-dtot[i-1]));
    near[N]=0;
    for(ll i=N-1;i>=1;i--) {
        if(near[i+1]*2+1>=d[i]) near[i]=d[i]+near[i+1];
        else near[i]=near[i+1];
    }
    for(ll i=0;i<N;i++) {
        if(near[i+1]>=dtot[i]) ans[i]=1;
        //printf("%lld %lld %lld\n",i,dtot[i],near[i+1]);
    }

    scanf("%lld",&Q);
    for(ll i=0;i<Q;i++){
        ll t1;
        scanf("%lld",&t1);
        if(ans[t1-1]) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}


Measured memory_bytes: 18304
#include<stdio.h>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<math.h>
#include<algorithm>
using namespace std;

#define INF 987654321
#define ll long long

string s;

int main()
{
	cin >> s;
	int n = s.size();

	int res = (n + 1) / 2, lo, hi;
	if (n % 2 == 0) lo = (n - 1) / 2, hi = n / 2;
	else lo = n / 2 - 1, hi = n / 2 + 1;
	while (lo >= 0)
	{
		if (s[lo] != s[hi] || s[lo] != s[lo + 1]) break;
		res++;
		lo--;
		hi++;
	}
	cout << res;
	return 0;
}

Measured memory_bytes: 512
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = 1; i <= (int)(n); i++) 
#define dunk(n) cout << n << endl
#define all(a) (a).begin(),(a).end()
typedef pair<int,int> P;
typedef long long ll;

int main() {
    int n; cin >> n;
    vector<ll> lucas(100,0);
    lucas[0] = 2;
    lucas[1] = 1;
    for(int i = 2; i <= 86; i++){
        lucas[i] = lucas[i-1]+lucas[i-2];
    }
    dunk(lucas[n]);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    int N;
    cin >> N;
    vector<string>a(N);
    for(int i = 0; i < N; i++) {
        cin >> a[i];
    }
    int A[6];
    for(int i = 0; i < 5; i++) {
        A[i] = 0;
    }
    for(int i = 0; i < N; i++) {
        if(a[i][0] == 'M') {
            A[0]++;
        }
        if(a[i][0] == 'A') {
            A[1]++;
        }
        if(a[i][0] == 'R') {
            A[2]++;
        }
        if(a[i][0] == 'C') {
            A[3]++;
        }
        if(a[i][0] == 'H') {
            A[4]++;
        }
    }
    int ans = 0;
    for(int i = 0; i < 5; i++) {
        for(int j = i+1; j < 5; j++) {
            for(int k = j+1; k < 5; k++) {
               ans+=A[i]*A[j]*A[k];
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 6144
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str();}
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EACH(t,i,c) for(t::iretator i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,n-1)
const double EPS = 1e-10;
const double PI = acos(-1.0);

int main() {
	FOR(i, 1, 9) {
		FOR(j, 1, 9) {
			cout << i << "x" << j << "=" << i*j << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 1116
N=int(input())
T,A=map(int,input().split())
h = list(map(int,input().split()))
dist = 10**6
ans = -1
c = 0.006
for i in range(N):
    if abs(T-c*h[i]-A) < dist:
        dist = abs(T-c*h[i]-A)
        ans = i+1
print(ans)


Measured memory_bytes: 3060
#include <stdio.h>
#include <string.h>

int main(){
   char str1[1000], str2[2];
   int num1, sum, k, len_str1;

   scanf("%s", str1);

   while(str1[0] != '0'){
        sum = 0;
        str2[1] = 0;
        len_str1 = strlen(str1);
        for(int k = 0; k < strlen(str1); k++){
                str2[0] = str1[k];
                num1 = atoi(str2);
                sum = sum + num1;
        }
        printf("%d\n", sum);
        scanf("%s", str1);

   }

   return 0;
}



Measured memory_bytes: 2044
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 500010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = (1 << 30) - 1;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

int X, Y, Z, K;
ll A[MAX_N], B[MAX_N], C[MAX_N];

void solve() {
	cin >> X >> Y >> Z >> K;
	rep(i, 0, X) cin >> A[i];
	rep(i, 0, Y) cin >> B[i];
	rep(i, 0, Z) cin >> C[i];
	sort(A, A + X);
	sort(B, B + Y);
	sort(C, C + Z);

	ll ok = 0, ng = A[X - 1] + B[Y - 1] + C[Z - 1] + 1;
	while(abs(ng - ok) > 1) {
		ll m = (ok + ng) / 2;
		int tmp = 0;
		rep(i, 0, X) {
			rep(j, 0, Y) {
				int at = lower_bound(C, C + Z, m - A[i] - B[j]) - C;
				tmp += Z - at;
			}
		}
		if(tmp >= K) ok = m;
		else ng = m;
	}
	vl vec;
	rep(i, 0, X) {
		rep(j, 0, Y) {
			int at = lower_bound(C, C + Z, ok - A[i] - B[j]) - C;
			rep(k, at, Z) {
				vec.pb(A[i] + B[j] + C[k]);
			}
		}
	}
	sort(all(vec)); reverse(all(vec));
	rep(i, 0, K) cout << vec[i] << "\n";
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
    cerr << fixed;
	cerr.precision(6);
	rng.seed(rd());
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
	if(!freopen("in.txt", "rt", stdin)) return 1;
#endif	
	solve();
    cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}



Measured memory_bytes: 137564
using System;

class ITP1
{
    static void Main()
    {
        var str = Console.ReadLine();
        int a = int.Parse(str.Split(' ')[0]);
        int b = int.Parse(str.Split(' ')[1]);
        int c = int.Parse(str.Split(' ')[2]);
        int[,] x = new int[a, b];
        int[,] y = new int[b, c];
        long d;
        for (int i = 0; i < a; i++)
        {
            str = Console.ReadLine();
            for (int j = 0; j < b; j++)
            {
                x[i, j] = int.Parse(str.Split(' ')[j]);
            }
        }
        for (int j = 0; j < b; j++)
        {
            str = Console.ReadLine();
            for (int k = 0; k < c; k++)
            {
                y[j, k] = int.Parse(str.Split(' ')[k]);
            }
        }
        for (int i = 0; i < a; i++)
        {
            for (int k = 0; k < c; k++)
            {
                d = 0;
                for (int j = 0; j < b; j++)
                {
                    d += x[i, j] * y[j, k];
                }
                if (k == c - 1)
                {
                    Console.WriteLine(d);
                }
                else
                {

                    Console.Write(d + " ");
                }
            }
        }
    }
}

Measured memory_bytes: 6004
#include <iostream>

int main(){
   int N;
   std::cin >> N;
   int A[N+2];
   A[0] = 0;
   A[N+1] = 0;
   for(int i=1; i<N+1; ++i)
      std::cin >> A[i];

   long long total = 0;
   long long ans = 0;
   for(int i=1; i<N+2; ++i)
      total += abs(A[i]-A[i-1]);
   for(int i=1; i<N+1; ++i){
      ans = total;
      ans -= abs(A[i]-A[i-1]);
      ans -= abs(A[i+1]-A[i]);
      ans += abs(A[i+1]-A[i-1]);
      std::cout << ans << std::endl;
   }
   return 0;

}


Measured memory_bytes: 1664
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int read()
{
	char ch=getchar();int h=0,t=1;
	while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
	if(ch=='-') t=-1,ch=getchar();
	while(ch>='0'&&ch<='9') h=h*10+ch-'0',ch=getchar();
	return h*t;
}
const int N=2e5+10,P=1e9+7;
struct item{int a,b;}A[N];
int dp[4010][4010],bs=2000;
int n,jc[N],inv[N],Ans;
void add(int &a,int b) {a+=b;if(a>=P) a-=P;}
int C(int n,int k) {return 1ll*jc[n]*inv[k]%P*inv[n-k]%P;}
int main()
{
	n=read();
	for(int i=1;i<=n;i++) A[i].a=read(),A[i].b=read();
	for(int i=1;i<=n;i++) dp[bs-A[i].a][bs-A[i].b]++;
	for(int i=0;i<=bs*2;i++)
		for(int j=0;j<=bs*2;j++)
		{
			if(i) add(dp[i][j],dp[i-1][j]);
			if(j) add(dp[i][j],dp[i][j-1]);
		}
	for(int i=1;i<=n;i++) add(Ans,dp[bs+A[i].a][bs+A[i].b]);
	jc[0]=inv[0]=inv[1]=1;
	for(int i=2;i<=1e5;i++) inv[i]=(P-(1ll*P/i*inv[P%i])%P)%P;
	for(int i=1;i<=1e5;i++) jc[i]=1ll*jc[i-1]*i%P,inv[i]=1ll*inv[i-1]*inv[i]%P;
	for(int i=1;i<=n;i++) add(Ans,P-C(A[i].a+A[i].a+A[i].b+A[i].b,A[i].a+A[i].a));
	cout<<1ll*Ans*inv[2]%P<<endl;
}


Measured memory_bytes: 65408
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <string>

typedef long long ll;

using namespace std;

int main() {
  string N;
  cin >> N;
  ll res = 0;
  for (int i = 0; i < N.size(); ++i) {
    res += N[i] - '0';
  }
  res = max(res, (ll)(max(0, N[0] - '0' - 1) + 9 * (N.size() - 1)));
  for (int i = 1; i < N.size() - 1; ++i) {
    if (N[i] - '0' > 0) {
      ll t = 0;
      for (int j = 0; j < i; ++j) {
        t += N[j] - '0';
      }
      t += N[i] - '0' - 1 + 9 * (N.size() - i - 1);
      res = max(res, t);
    }
  }
  printf("%lld\n", res);
}

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

int main(){
    int s;
    cin >> s;
    if(s == 25){
        cout << "Christmas" << endl;
    }else if(s == 24){
        cout << "Christmas Eve" << endl;
    }else if(s == 23){
        cout << "Christmas Eve Eve" << endl;
    }else{
        cout << "Christmas Eve Eve Eve" << endl;
    }
}

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

int main() {
  int n, l;
  cin >> n >> l;
  int s = n*(l-1)+n*(n+1)/2;
  if(l<-n+1) cout << s-l-n+1 << endl;
  else if(0<l) cout << s-l << endl;
  else cout << s << endl;
}


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

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int x, y;
		x=n*800;
		y=(n/15)*200;
		System.out.println(x-y);
	}

}

Measured memory_bytes: 21716
#include "bits/stdc++.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<int,int> pii;
#define int ll
#define fi first
#define se second
#define Sort(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/4
#define INTINF INT_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
template<class T> inline bool chmax(T &a, T b){if(a < b){a = b;return true;}return false;}
template<class T> inline bool chmin(T &a, T b){if(a > b){a = b;return true;}return false;}
/*----------------------------------------------------------------*/
// const int MOD = 998244353;
// const int MOD = 1000000007;


/*----------------------------------------------------------------*/
signed main(){

	int n;
	cin >> n;

	int cnt = 0;
	int x = n;
	for(int i = 2;i*i <= n;i++){
		int a = 1;
		int b = 1;
		while(x%i==0){
			a--;
			if(a == 0){
				cnt++;
				b++;
				a = b;
			}
			
			x /= i;
		}
	}
	if(x != 1)cnt++;
	cout << cnt << endl;


	return 0;
}
/*----------------------------------------------------------------*/

// g++ -std=gnu++17 code1.cpp
// sudo pip3 install --upgrade online-judge-tools
// rm -r -f test;oj dl https://code-festival-2018-quala.contest.atcoder.jp/tasks/code_festival_2018_quala_c
// rm -r -f test;oj dl https://pakencamp-2019-day3.contest.atcoder.jp/tasks/pakencamp_2019_day3_c
// rm -r -f test;oj dl https://atcoder.jp/contests/abc169/tasks/abc169_b


Measured memory_bytes: 3636