akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<vector>
#include<string>
#include<string.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<cmath>
using namespace std;
#define inf 0x3f3f3f3f
#define fast ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n); i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define sz(a) int((a).size())
#define pb push_back
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pll;
const int N = 1e5+7;
ll n,m,k,x,y,a[N],b[N];
int main(){
    fast;
    cin>>n;
    forn(i,n) cin>>a[i],b[i]=a[i];
    sort(b,b+n);
    forn(i,n){
        if(abs(i-(lower_bound(b,b+n,a[i])-a))%2!=0) x++;
    } cout<<x/2<<endl;
    return 0;
}

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

///////////////////////////////////////////
const long long int INF = INT64_MAX;
//const long long int INF = 1000000;
const long long int Mod = 1000000007;
using ll = long long int;
using ci = const int;
using vi = vector<int>;
using Vi = vector<long long int>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(ll i=0;i<N;i++)
auto max(auto x,auto y){if(x>y){return x;}else{return y;}}
auto min(auto x,auto y){if(x>y){return y;}else{return x;}}
template<class T>bool chmax(T &former, const T &b) { if (former<=b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<=former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
typedef vector<vector<ll> > matrix;
///////////////////////////////////////////////////////////////////////////////////
ll n;string s;
bool mem[101]={false};
int main(){
    cin>>n>>s;
    ll max=0;ll key=0;ll max2=0;
    rep(i,n){
        key=0;
        memset(mem,false,sizeof(mem));
        rep(j,i){
            for(int l=i;l<n;l++){
                if(s[l]==s[j]&&!mem[s[j]-'a']){
                    key++;
                    mem[s[j]-'a']=true;
                    break;
                }
            }
            //chmax(max2,key);
        }
        chmax(max,key);
    }
    cout<<max<<endl;
    return 0;
}

Measured memory_bytes: 256
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def solve(S, n):
    ans = 0

    for i in range(len(S)):
        if int(S[i]) == n:
            pass
        else:
            ans += 1

        n = 1 - n

    return ans


def main():
    S = input()

    print(min(solve(S, 0), solve(S, 1)))


if __name__ == '__main__':
    main()


Measured memory_bytes: 4080
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
    /*
    {
       Md: Saroar Zahan Sojib
       Green University of Bangladesh
       https://web.facebook.com/sojib.bdb
    }
   */


// Driver program to test above function
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

  int n;
  cin>>n;
  int k=n%10;
  if(k==2 || k==4 || k==5 || k==7 || k==9)cout<<"hon"<<endl;
  else if(k==0 || k==1 || k==6 || k==8)cout<<"pon"<<endl;
  else if(k==3)cout<<"bon"<<endl;


    return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define FI first
#define SE second
#define VE vector<int>
#define PB push_back
#define PA pair<int,int>
#define MA make_pair
#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define POS(i) cout<<(i?"POSSIBLE":"IMPOSSIBLE")<<endl
#define Pos(i) cout<<(i?"Possible":"Impossible")<<endl
#define co(i) cout<<i<<endl
#define fcout cout<<fixed<<setprecision(10)
using namespace std;
//
const int INF=1e9+7;
const int MOD=1e9+7;
//
int main(){
	int n; cin>>n;
	int a[300][300];
	int b[300][300];
	FOR(i,0,n){
		FOR(j,0,n){
			cin>>a[i][j];
			b[i][j]=1;
		}
	}
	bool f=true;
	FOR(k,0,n) FOR(i,0,n) FOR(j,0,n){
		if(i==j||j==k||k==i) break;
		if(a[i][k]+a[k][j]<a[i][j]){
			f=false;
		}else if(a[i][k]+a[k][j]==a[i][j]){
			b[i][j]=0;
			b[j][i]=0;
		}
		if(a[i][j]+a[j][k]<a[i][k]){
			f=false;
		}else if(a[i][j]+a[j][k]==a[i][k]){
			b[i][k]=0;
			b[k][i]=0;
		}
		if(a[j][i]+a[i][k]<a[j][k]){
			f=false;
		}else if(a[j][i]+a[i][k]==a[j][k]){
			b[k][j]=0;
			b[j][k]=0;
		}
			
	}
	ll ans=0;
	FOR(i,0,n) FOR(j,0,n) if(b[i][j]) ans+=a[i][j];
	if(f) co(ans/2);
	else co(-1);
	
}


Measured memory_bytes: 896
# -*- coding: utf-8 -*-
"""
Balls and Boxes 1
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_5_A&lang=ja

"""
import sys


def solve(n, k):
    ans = 1
    for _ in range(n):
        ans = (ans * k) % (10**9 + 7)
    return ans


def main(args):
    n, k = map(int, input().split())
    ans = solve(n, k)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])



Measured memory_bytes: 5620
from collections import defaultdict
MOD = 10**9+7
from math import gcd


n = int(input())
ans = 1
C = defaultdict(int)
z = 0
r = 0
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        r += 1
    elif b == 0:
        z += 1
    elif a == 0:
        C[0] += 1
    else:
        g = gcd(abs(a), abs(b))
        a //= g
        b //= g
        if a < 0:
            a, b = -a, -b
        C[(a, b)] += 1
D = tuple(C.items())
used = {0}
for c, v in D:
    if c in used:
        continue
    a, b = c
    if b > 0:
        d, e = b, -a
    else:
        d, e = -b, a
    ans *= pow(2, v, MOD)+pow(2, C[(d, e)], MOD)-1
    ans %= MOD
    used.add((d, e))
ans *= pow(2, C[0], MOD)+pow(2, z, MOD)-1
ans += r
ans -= 1
ans %= MOD
print(ans)

Measured memory_bytes: 116068
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool search(int A[], int n, int key)
{
  int i = 0;
  A[n] = key;
  while (A[i] != key)
    i++;
  return i != n;
}
int main()
{
  int t, s;
  cin >> t;
  int T[t];

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

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

  int count = 0;
  for (int i = 0; i < s; i++)
  {
    count += search(T, t, S[i]);
  }
  cout << count << endl;

  return 0;
}



Measured memory_bytes: 3088
C = [list(map(int,input().split())) for _ in range(3)]
K = C[0][0]
b1,b2 = C[0][1]-K,C[0][2]-K
a1,a2 = C[1][0]-K,C[2][0]-K
if C[1][1]==K+a1+b1 and C[1][2]==K+a1+b2 and C[2][1]==K+a2+b1 and C[2][2]==K+a2+b2:
  print('Yes')
else:
  print('No')

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

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

  int w1;
  vector<int> value[4];
  for(int i=0;i<N;i++){
    int w,v;
    cin >> w >> v;
    if(i==0) w1 = w;
    value[w - w1].push_back(v);
  }

  for(int i=0;i<4;i++){
    sort(value[i].begin(),value[i].end());
    value[i].push_back(0);
    reverse(value[i].begin(),value[i].end());
    for(int j=1;j<value[i].size();j++){
      value[i][j] += value[i][j-1];
    }
  }

  int ans = 0;
  for(int i=0;i<value[0].size();i++){
    for(int j=0;j<value[1].size();j++){
      for(int k=0;k<value[2].size();k++){
        for(int l=0;l<value[3].size();l++){
          ll f = w1*(ll)i + (w1+1)*(ll)j + (w1+2)*(ll)k + (w1+3)*(ll)l;
          if(f <= W){
            ans = max(ans,value[0][i]+value[1][j]+value[2][k]+value[3][l]);
          }
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include <string> 
using namespace std;
int max(int x, int y) {
	if (x > y)return x;
	return y;
}

string s,S;


int main(){
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		S = S + s[i];
		i++;
	}
	cout << S << endl;
	return 0;
}

Measured memory_bytes: 640
import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    S = inputs[0]
    for i in range(len(S)-1):
        new_s = S[:len(S) - i - 1]
        if len(new_s) % 2 != 0:
            continue
        half = len(new_s) // 2
        front = new_s[:half]
        tail = new_s[half:]

        if front == tail:
            return len(new_s)
    return 0


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)


Measured memory_bytes: 38384
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
using namespace std;

#define rep(i, s) for (int i = 0; i < s; ++i)
#define all(v) (v.begin(), v.end())
#define COUT(x) cout << #x << ” = ” << (x) << ” (L” << __LINE__ << “)” << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define VEC(a, n) vector<int>a(n)
#define PQ(a) priority_queue<int>a
#define PQmin(a) priority_queue< int, :vector<int>, greater<int> >a
#define PAIR pair<int, int>
/*
sort(sp.begin(), sp.end(), [](PAIR l, PAIR r){
       return l.first<r.first || (l.first==r.first && l.second > r.second);
       });
*/

typedef long long  ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
   int n;
   cin>>n;
   string s;
   cin>>s;
   int ans=0;
   for(int i=0;i<n-1;i++){
      if(s.at(i)!=s.at(i+1)){
         ans++;
      }
   }
   cout<<ans+1<<endl;

   return 0;
}

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

using namespace std;

const int mod = 1e9 + 7;

int main()
{
  int H, W, K;
  cin >> H >> W >> K;
  vector<vector<int>> dp(H + 1, vector<int>(W, 0));
  dp[0][0] = 1;
  for (int i = 0; i < H; i++)
    for (int j = 0; j < W; j++)
      for (int bit = 0; bit < 1 << (W - 1); bit++)
      {
        bool ok = true;
        for (int k = 0; k < W - 2; k++)
          if (bit & (1 << k) && bit & (1 << (k + 1)))
            ok = false;
        if (!ok)
          continue;
        if (0 < j && (bit & (1 << (j - 1))))
        {
          dp[i + 1][j - 1] += dp[i][j];
          dp[i + 1][j - 1] %= mod;
        }
        else if (j < W - 1 && (bit & (1 << j)))
        {
          dp[i + 1][j + 1] += dp[i][j];
          dp[i + 1][j + 1] %= mod;
        }
        else
        {
          dp[i + 1][j] += dp[i][j];
          dp[i + 1][j] %= mod;
        }
      }
  cout << dp[H][K - 1] << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
    //#include <bits/stdc++.h>
    #include<vector>
    #include<algorithm>
    #include<string>
    #include<math.h>
    #include<sstream>
    using namespace std;
    #define INF 10000000;

    int main(){
      int n,x,cnt = 0;
      
      cin >> n >> x;
      vector<int>a(n);
      for(int i=0;i<n;i++){
        cin >> a[i];
      }

      sort(a.begin(),a.end());
      

      for(int i=0;i<n;i++){
        if(x>=a[i] && i!=n-1){
          x -= a[i];
          cnt++;
        }
        else if(x==a[i] && i==n-1){
          cnt++;
          break;
        }
        else break;
      }
      cout << cnt <<endl;
    }

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

int main() {
	string n;
	cin>>n;
	int a=0;
	for(int i=0; i<n.length(); i++){
		a+=n[i]-'0';
	}
	if(a%9)
		cout<<"No";
	else
		cout<<"Yes";
	return 0;
}

Measured memory_bytes: 3732
#include<iostream>
#include<fstream>
#include<unordered_map>
#include<cmath>
using namespace std;
const int DN=1e5+5;
long long n,a[DN],st,dr,mij,f;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    st=2;
    dr=1e18;
    while(st<dr)
    {
        mij=(st+dr)/2;
        f=mij;
        for(int i=1;i<=n;i++)
            f-=f%a[i];
        if(f<2)
            st=mij+1;
        else
            dr=mij;
    }
    f=st;
    for(int i=1;i<=n;i++)
        f-=f%a[i];
    if(f!=2)
    {
        cout<<-1;
        return 0;
    }
    cout<<st<<' ';
    dr=1e18;
    while(st<dr)
    {
        mij=(st+dr+1)/2;
        f=mij;
        for(int i=1;i<=n;i++)
            f-=f%a[i];
        if(f<=2)
            st=mij;
        else
            dr=mij-1;
    }
    cout<<st;
}


Measured memory_bytes: 1024
import copy

n = int(input())
lst = []
for _ in range(n):
    lst.append(int(input()))
clean_lst = copy.deepcopy(lst)

m1 = max(lst)
lst.remove(m1)
m2 = max(lst)

for i in clean_lst:
    print(m1 if i!=m1 else m2)


Measured memory_bytes: 14568
a,b,c,d,e,f = map(int, input().split())

w  = [False for i in range(f+1)]
s  = [False for i in range(f+1)]
w[0] = True
s[0] = True
for i in range(f+1):
    if not w[i]:
        continue
    if i+(100*a) <= f:
        w[i+(100*a)] = True
    if i+(100*b) <= f:
        w[i+(100*b)] = True
for i in range(f+1):
    if not s[i]:
        continue
    if i+c <= f//2:
        s[i+c] = True
    
    if i+d <= f//2:
        s[i+d] = True

ww = [i for i in range(1, f+1) if w[i]]
ss = [i for i in range(1, f+1) if s[i]]

max_w = a*100
max_s = 0
max_r = 0
for w in ww:
    for s in ss:
        if s <= e*w//100 and s+w <= f and s/(w+s)>max_r:
            max_r = s/(w+s)
            max_s = s
            max_w = w
print(max_w+max_s, max_s)

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

int main()
{
    int n; cin >> n;
    vector<int> a(n,0), b(n,0), c(n,0), fa(n,0), fb(n,0), fc(n,0);
    for (int i=0; i<n; i++) cin >> a[i] >> b[i] >> c[i];
    fa[0] = a[0]; fb[0] = b[0]; fc[0] = c[0];
    for (int i=1; i<n; i++)
    {
        fa[i] = max (fb[i-1], fc[i-1]) + a[i];
        fb[i] = max (fa[i-1], fc[i-1]) + b[i];
        fc[i] = max (fa[i-1], fb[i-1]) + c[i];
    }
    int r = 0;
    r = max (r, fa[n-1]);
    r = max (r, fb[n-1]);
    r = max (r, fc[n-1]);
    cout << r;
    return 0;
}


Measured memory_bytes: 2560
N,Q=map(int,input().split())
S=input()
count=[0]*N
for i in range(1,N):
    count[i]=count[i-1]
    if S[i-1:i+1]=="AC":count[i]+=1
for i in range(Q):
    l,r=map(int,input().split())
    print(count[r-1]-count[l-1])

Measured memory_bytes: 6140
#include<bits/stdc++.h>
using namespace std;
#define inf 1000000000
#define INF 100000000000000
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define EB emplace_back


int n,c;
int d[100][100];
int e[3][100];

signed main(){
  cin>>n>>c;
  rep(i,c){
    rep(j,c){
      cin>>d[i+1][j+1];
    }
  }

  rep(i,n){
    rep(j,n){
      int a;
      cin>>a;
      e[(i+j)%3][a]++;
    }
  }

  int ans=inf;

  FOR(x,1,c+1){
    FOR(y,1,c+1){
      FOR(z,1,c+1){
        if(x==y||y==z||z==x) continue;
        int res=0;
        FOR(i,1,c+1){
          res+=e[0][i]*d[i][x];
          res+=e[1][i]*d[i][y];
          res+=e[2][i]*d[i][z];
        }
      ans = min(ans,res);
      }
    }
  }

  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
int main(){
  int frag =1;
  int N,j,count=0,tmp;
  int *A;
  scanf("%d",&N);
  if(N<1 || N>100) exit(1);
  A = (int *)malloc(N*sizeof(int));
  for(j=0;j<N;j++)
    {
      scanf("%d",&A[j]);
      if(A[j]<0 || A[j]>100) exit(1);
    }
  while(frag == 1)
    {
      frag = 0;
      for(j=N-1;j>0;j--)
	{
	  if(A[j]<A[j-1])
	    {
	      tmp = A[j];
	      A[j] = A[j-1];
	      A[j-1] = tmp;
	      frag =1;
	      count++;
	    }
	}
    }
  for(j=0;j<N-1;j++)
    {
      printf("%d ",A[j]);
    }
  printf("%d\n",A[j]);
  printf("%d\n",count);
  return 0;
}
  
  



Measured memory_bytes: 2140
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define ALLR(v) v.rbegin(),v.rend()
typedef long long ll;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//isPrime
//modpow modinv
//getDigit
int main() {
  cout << fixed << setprecision(10);
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a.at(i);
  sort(ALL(a));
  bool b =true;
  for(int i = 0; i+1<n; i++){
    if(a.at(i)==a.at(i+1)){
      b=false;
    }
  }
  if(b){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
}


Measured memory_bytes: 1024
n, k = map(int, input().split())
sunukes = [0]*(n+1)
for i in range(k):
  d = int(input())
  sunuke = list(map(int, input().split()))
  for j in sunuke:
    sunukes[j] += 1
count = 0
for l in range(1, n+1):
  if sunukes[l] == 0:
    count +=1
print(count)

Measured memory_bytes: 9124
from bisect import bisect
from collections import Counter
n=int(input())
b=sorted(list(map(int,input().split())))
a=Counter(b)
mA=b[-1]
acc=0
dp=[True]*(mA+1)
for i,v in a.items():
  if dp[i]==True and v==1:
    acc+=1
  else:dp[i]=False
  for k in range(mA//i+1):
    dp[k*i]=False
print(acc)

Measured memory_bytes: 134696
//#include <bits/stdc++.h>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

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

    int M, D;

    cin >> M >> D;

    int count = 0;

    for(int i = 1; i <= M; i++)
    {
        for(int j = 1; j <= D; j++)
        {
            if(i == j / 10 * (j - (j / 10) * 10) && j / 10 > 1 && j - (j / 10) * 10 > 1)
            {
                count++;

                //cout << i << " " << j << endl;
            }
        }
    }

    cout << count;
}

Measured memory_bytes: 256
#!/usr/bin/env python
n = int(input())
a = list(map(int, input().split()))
total = sum(a)
ans = float('inf')
tmp = 0
for i in range(n):
    tmp += a[i]
    if i==n-1:
        continue
    ans = min(ans, abs(tmp-(total-tmp)))
print(int(ans))

Measured memory_bytes: 24948
#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define pvec(v) rep(i,v.size()){cout << v[i] << " ";};cout<<endl;
#define pb push_back
#define pf push_front
#define mod 1e9+7
 
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;

const double pi = acos(-1.0);
 
ll gcd(ll x, ll y) { return (y == 0) ? x : gcd(y, x % y); }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

int main()
{
	ll x,y,z,g;
	int k;
	cin >> x >> y >> z >> k;
	vll a,b,c,ans;
	rep(i,x){
		cin >> g;
		a.pb(g);
	}
	rep(i,y){
		cin >> g;
		b.pb(g);
	}
	rep(i,z){
		cin >> g;
		c.pb(g);
	}
	sort(rall(a));
	sort(rall(b));
	sort(rall(c));
	rep(i,x){
		rep(j,y){
			rep(l,z){
				if((i+1)*(j+1)*(l+1)<=k) ans.pb(a[i]+b[j]+c[l]);
			}
		}
	}
	sort(rall(ans));
	rep(i,min(3000,k)) cout << ans[i] << endl;
	return 0;
}

Measured memory_bytes: 1412
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
long long mod = 1000000007;
long long modpow(long long m,long long n){
    long long res = 1;
    if(n > 0){
        res = modpow(m,n / 2);
        if(n % 2 == 0){
            res = (res * res) % mod;
        }
        else{
            res = (((res * res) % mod) * m) % mod;
        }
    }
    return res;
}
ll fac[200001];
ll conbi(ll a,ll b){//aCbをmodで割ったあまりを求める
  ll res = fac[a];
  res *= modpow(fac[b],mod - 2),res %= mod;
  res *= modpow(fac[a - b],mod - 2),res %= mod;
  return res;
}
int main(){
    fac[0] = 1;
    for(int i = 1;i <= 200000;i++){
      fac[i] = fac[i - 1] * i;
       fac[i] %= mod;
}
    ll s;
    cin >> s;
    ll res = 0;
    for(int i = 1;i <= s;i++){
        ll k = s - i * 3;
        if(k < 0)continue;
        res += conbi(k + i - 1,k),res %= mod;
      //cout << i << " " << res << endl;
    }
    cout << res << endl;
}

Measured memory_bytes: 5188
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
map<int,int>maps;
map<int,int>::iterator it;
int n,m;
int ac = 0,wa = 0;
int main(void) {
	void solve();
	cin >> n >> m;
	ac = wa = 0;
	solve();
	return 0;
}
void solve() {
	if(m == 0) {
		cout << 0 << " " << 0 << endl;
		return ;
	}
	int num;
	string vis;
	for(int i = 1; i <= m; i ++) {
		cin >> num >> vis;
		if(maps[num] == -1) continue;
		if(vis == "AC") {
			wa += maps[num];
			ac += 1;
			maps[num] = -1;
			continue;
		}
		maps[num] ++;
	}
	maps.clear();
	cout << ac << " " << wa << endl;
	return ;
}

Measured memory_bytes: 4992
// ProblemURL : https://atcoder.jp/contests/abc105/tasks/abc105_c
// ---------------------------------------------
package main

import (
	"fmt"
	"strconv"
)

func main() {
	var n int
	fmt.Scan(&n)

	if n == 0 {
		fmt.Println("0")
		return
	}
	ans := ""
	for n != 0 {
		r := n % 2
		if r == -1 {
			r += 2
		}
		n = (n - r) / (-2)
		ans = strconv.Itoa(r) + ans
	}
	fmt.Println(ans)
}


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

int main()
{
  string s;
  while(cin>>s){
    int sum1=0,sum2=0;
    for(int i=1;i<s.length()-1;i++){
      if(s[i-1]=='J' && s[i]=='O' && s[i+1]=='I')sum1++;
      if(s[i-1]=='I' && s[i]=='O' && s[i+1]=='I')sum2++;
    }
    cout<<sum1<<endl;
    cout<<sum2<<endl;
  }
  return 0;
}

Measured memory_bytes: 1196
#include <iostream>
#include <queue>

using namespace std;

int main ()
{
    priority_queue <int> gquiz;
    string s;
    int x;
    while (cin>>s,s!="end"){
        if (s=="insert"){
            cin>>x;
            gquiz.push(x);
        }
        if (s=="extract"){
            cout<<gquiz.top()<<'\n';
            gquiz.pop();
        }
    }

    return 0;
}



Measured memory_bytes: 6976
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;


signed main() {
  vector<vector<int>> vec(3, vector<int>(3));
  vector<vector<bool>> ok(3, vector<bool>(3, false));
  int N;
  REP(i, 3){
    REP(j, 3) cin >> vec[i][j];
  }
  cin >> N;
  int a;
  REP(k, N){
    cin >> a;
    REP(i, 3) REP(j, 3) if(vec[i][j] == a) ok[i][j] = true;
  }

  int ans = 0;
  if(ok[0][0] && ok[0][1] && ok[0][2]) ans = 1;
  if(ok[1][0] && ok[1][1] && ok[1][2]) ans = 1;
  if(ok[2][0] && ok[2][1] && ok[2][2]) ans = 1;

  if(ok[0][0] && ok[1][0] && ok[2][0]) ans = 1;
  if(ok[0][1] && ok[1][1] && ok[2][1]) ans = 1;
  if(ok[0][2] && ok[1][2] && ok[2][2]) ans = 1;

  if(ok[0][0] && ok[1][1] && ok[2][2]) ans = 1;
  if(ok[0][2] && ok[1][1] && ok[2][0]) ans = 1;

  if(ans) Yes;
  else No;

  return 0;
}

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

int main(){
    int n;
    cin >> n;
    int m;
    cin >> m;
    int ans = 1;
    rep(i,n-1){
        int p;
        cin >> p;
        if(m >= p) ans++;
        m = min(m, p);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0;i<(n);++i)
#define per(i, n) for(int i=(n)-1;i>=0;--i)
#define repa(i, n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
using ll = long long;
//const ll MOD = (ll)1e9+7;
const ll MOD = 998244353;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}

ll modpow(ll x, ll b){
	ll res = 1;
	while(b){
		if(b&1)res = res * x % MOD;
		x = x * x % MOD;
		b>>=1;
	}
	return res;
}

ll modinv(ll x){
	return modpow(x, MOD-2);
}

bool was_output = false;
template<class t>
void output(t a){
	if(was_output)cout << " ";
	cout << a;
	was_output = true;
}
void outendl(){
	was_output = false;
	cout << endl;
}

int n, m;
using T  = tuple<int, int, int>;
vvector<pii> edges;

int func(int min_val, int start1, int start2){
	vector<char> used(n, false);
	priority_queuer<pii> pq;
	pq.emplace(min_val, start1);
	pq.emplace(min_val, start2);
	int max_val = min_val;
	int cnt = 0;
	while(pq.size()){
		pii d = pq.top();
		pq.pop();
		if(used[d.second])continue;
		used[d.second]=true;
		chmax(max_val, d.first);
		++cnt;
		foreach(i, edges[d.second]){
			if(used[i.first])continue;
			if(i.second<min_val)continue;
			pq.emplace(i.second, i.first);
		}
	}
	if(cnt<n)return INF;
	return max_val - min_val;
}

int main(){
	while(cin>>n>>m&&n){
		edges.assign(n, vector<pii>(0));
		vector<T> line;

		rep(i, m){
			int a, b, c;
			cin >> a >> b >> c;
			--a;
			--b;
			edges[a].emplace_back(b, c);
			edges[b].emplace_back(a, c);
			line.emplace_back(c, a, b);
		}
		sort(all(line));
		int ans = INF;
		foreach(i, line){
			chmin(ans, func(get<0>(i), get<1>(i), get<2>(i)));
		}
		if(ans>=INF){
			cout << -1 << endl;
		}else{
			cout << ans << endl;
		}
	}

	return 0;
}



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

int main() {
  int n;
  cin >> n;
  bool a = false;
  for(int i = 1; i <= 9; i++) {
    for(int j = 1; j <= 9; j++) {
      if(n == i*j) a = true;
    }
  }
  if(a) cout << "Yes" << endl;
  else cout << "No" << endl;
}


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

int main(){
    long N,K;
    cin>>N>>K;
    
    vector<long> A(N);
    for(int i=0;i<N;i++) cin>>A.at(i);
    
    vector<long> naibu(N,0),full(N,0);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(A.at(i)>A.at(j)){
                full.at(i)++;
                if(j>i) naibu.at(i)++;
            }
        }
    }
    
    long ans=0;
    
    for(int i=0;i<N;i++){
        ans+=(naibu.at(i)*K)%MOD;
        ans+=((K*(K-1)/2)%MOD)*full.at(i);
        ans%=MOD;
    }
    
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#![allow(unused_imports)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

pub trait InputValue {
    fn parse(s: &str) -> Self;
}

pub fn read<T: InputValue>() -> T {
    let mut buf = String::new();
    let _ = stdin().read_line(&mut buf);
    T::parse(&buf.trim())
}

pub fn readn<T: InputValue>(n: usize) -> Vec<T> {
    let mut vec = vec![];
    for _ in 0..n {
        vec.push(read());
    }
    vec
}

pub fn readnc<T: InputValue>() -> Vec<T> {
    let mut vec = vec![];
    let line: String = read();
    for token in line.split_whitespace() {
        vec.push(T::parse(token));
    }
    vec
}

macro_rules! parse_single_value {
    ($($t:ty),*) => {
        $(
            impl InputValue for $t {
                fn parse(s: &str) -> $t { s.parse().unwrap() }
            }
        )*
	}
}
parse_single_value!(i32, i64, f32, f64, usize, String);

macro_rules! parse_tuple {
	($($t:ident),*) => {
		impl<$($t),*> InputValue for ($($t),*) where $($t: InputValue),* {
			fn parse(s: &str) -> ($($t),*) {
				let mut tokens = s.split_whitespace();
				let t = ($($t::parse(tokens.next().unwrap())),*);
				t
			}
		}
	}
}
parse_tuple!(A, B);

// ===

fn main() {
    let (n, m): (i64, i64) = read();
    println!("{}", solve(n, m));
}

fn solve(n: i64, m: i64) -> i64 {
    if n > m {
        return solve(m, n);
    }
    if m == 1 {
        1
    } else if n == 1 {
        m-2
    } else if n == 2 {
        0
    } else {
        (n-2)*(m-2)
    }
}


Measured memory_bytes: 4352
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <functional>
#include <sstream>
#include <complex>
#include <climits>
using namespace std;

#define REP(i,a,n) for(int i=(a);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define EPS 1e-8

int main(){
	string in;
	string ap = "apple";
	string pe = "peach";
	
	while(getline(cin,in)){
		vector<int> a,p;
		int id = 0;
		while( (id=in.find("apple",id))!=string::npos ){
			a.push_back(id);
			id++;
		}
		id = 0;
		while( (id=in.find("peach",id))!=string::npos ){
			p.push_back(id);
			id++;
		}
		rep(i,a.size()){
			rep(j,5)in[a[i]+j]=pe[j];
		}
		rep(i,p.size()){
			rep(j,5)in[p[i]+j]=ap[j];
		}
		cout << in << endl;
		//rep(i,a.size())printf("%d,",a[i]); puts("");
		//rep(i,p.size())printf("%d,",p[i]); puts("");
	}
	return 0;
}

Measured memory_bytes: 0
function Main(input) {
    // 1行目がinput[0], 2行目がinput[1], …に入る
    N = Number(input.split("\n")[0]);
    S = input.split("\n")[1].split("");
    K = Number(input.split("\n")[2]);
    answer = ""
    
    letter = S.slice(K-1, K);
    
    for(i = 0; i<N;i++){
        if(S[i] !== String(letter)){
            S[i]="*";
        }
        answer += S[i];
    }
    console.log(answer);
    
}
    


//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 22076
{-# LANGUAGE TypeApplications #-}
import qualified Data.ByteString.Char8 as BS
import qualified Data.ByteString.Char8 as B
import Data.Maybe
import Data.List
import Control.Monad

toInt :: String -> Int
toInt = read

main :: IO ()
main = do
  l <- words <$> getLine
  let a = toInt $ l !! 0
  let b = toInt $ [x | x <- l !! 1, not (elem x ".")]
  print $ div (a * b) 100

Measured memory_bytes: 3916
#k = int(input())
#s = input()
#a, b = map(int, input().split())
#s, t = map(str, input().split())
#l = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
#a = [list(input()) for _ in range(n)]
#a = [int(input()) for _ in range(n)]

n,k = map(int, input().split())
l = list(map(int, input().split()))

l.sort(reverse=True)

ans = 0
for i in range(k):
    ans += l[i]

print(ans)





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

int main(){
  string s;
  cin >> s;
  if ( s.size() == 1) {
    cout << s << endl;
    return 0;
  }
  bool flag = true;
  for ( int i = 1; i < s.size(); ++i ) {
    if ( s[i] != '9' ) {
      flag = false;
      break;
    }
  }
  if( flag ) {
    cout << (s.size() - 1) * 9 + s[0] - '0' << endl;
  } else {
    cout << (s.size() - 1) * 9 + s[0] - '0' - 1 << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <assert.h>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>
#include <numeric>
#include <functional>
#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <bitset>
typedef long long ll;
typedef unsigned long long ull;

#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define DEBUG(vec) for (auto v : vec) { cout << v << " "; } cout << endl;

using namespace std;

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

  int N;
  cin >> N;

  int f = 0;
  int scores[8] = {};
  REP(i, N) {
    int a;
    cin >> a;
    if (a >= 3200) {
      f++;
    } else {
      scores[a / 400]++;
    }
  }
  int ans = 0;
  REP(i, 8) {
    if (scores[i] > 0) ans++;
  }

  cout << max(ans, 1) << " " << ans + f << endl;
  return 0;
}


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

int main() {

	int a; cin >> a;
	int cnt = 1;
	while (true) {
		if (a <= 1000 * cnt) {
			break;
		}
		cnt++;
	}
	cout << 1000 * cnt - a << endl;
	return 0;
}

Measured memory_bytes: 3632
#include <stdlib.h>
#include <stdio.h>

int main(){
    int i;
    int cache=0;
    int x1,x2,x3,x4,x5;
    int arr[5];
    scanf("%d",&x1);
    scanf("%d",&x2);
    scanf("%d",&x3);
    scanf("%d",&x4);
    scanf("%d",&x5);

    arr[0] = x1;
    arr[1] = x2;
    arr[2] = x3;
    arr[3] = x4;
    arr[4] = x5;

    for(i=0;i<5;i++){
        if(arr[i]== 0){
            cache = i+1;
            break;
        }
    }
    printf("%d",cache);
    return 0;
}


Measured memory_bytes: 1648
def solve():
    n = int(input())
    a = []
    b = []
    for _ in range(n):
        A, B = map(int, input().split())
        a.append(A)
        b.append(B)

    ans = b[-1] - a[-1]%b[-1]
    if a[-1]%b[-1] == 0: ans = 0

    for i in range(1, n):
        c = a[-(i+1)]+ans

        if c%b[-(i+1)] == 0: continue

        dis = b[-(i+1)]-c%b[-(i+1)]
        ans += dis

    return ans
    

print(solve())


Measured memory_bytes: 11040
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 100010
using namespace std;
int n,a[MAXN],ans1;
int main(){
	SF("%d",&n);
	for(int i=1;i<=n;i++)
		SF("%d",&a[i]);
	ans1=-1;
	for(int i=-100;i<=100;i++){
		int ans=0;
		for(int j=1;j<=n;j++)
			ans+=(a[j]-i)*(a[j]-i);
		if(ans1==-1)
			ans1=ans;
		else
			ans1=min(ans1,ans);
	}
	PF("%d",ans1);
}

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

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<long> a(n+1,0);
    vector<long> b(m+1,0);

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

    int b_sum = m, max = 0;
    for (int i = 0; i <= n && a[i] <= k; i++) {
        while (a[i] + b[b_sum] > k) b_sum--;
        if (i + b_sum > max) max = i + b_sum;
    }

    cout << max << endl;
}

Measured memory_bytes: 6428
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
const long double PI = acos(-1.0L);
const long long MOD = 1000000007LL;
// const long long MOD = 998244353LL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
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; }
///////////////////////////////////////////////////////////////////////////////////////////////////

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N,M; cin >> N >> M;
    vector<vector<int>> G(N);
    rep(i,M) {
        int A,B; cin >> A >> B;
        A--; B--;
        G[A].emplace_back(B);
    }

    vector<int> dist(N),prev(N),mini(N,1e9);
    vector<vector<int>> circle(N);
    rep(i,N) {
        fill(all(dist),-1);
        fill(all(prev),-1);
        dist[i] = 0;
        queue<int> que;
        que.emplace(i);
        while (!que.empty()) {
            int v = que.front(); que.pop();
            for (auto nv : G[v]) {
                if (nv == i) {
                    mini[i] = dist[v]+1;
                    int r = v;
                    circle[i].emplace_back(i);
                    while (r != i) {
                        circle[i].emplace_back(r);
                        r = prev[r];
                    }
                    goto OUT;
                }
                if (dist[nv] != -1) continue;
                dist[nv] = dist[v]+1;
                prev[nv] = v;
                que.emplace(nv);
            } 
        }
        OUT:;
    }

    if (*min_element(all(mini)) == 1e9) {
        cout << -1 << endl;
        return 0;
    }
    int k = min_element(all(mini)) - mini.begin();
    cout << circle[k].size() << endl;
    for (auto i : circle[k]) cout << i+1 << endl;
}

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

int main()
{
    int a, b;

    cin >> a >> b;

    if ((a >= -1000 && a <= 1000) && (b >= -1000 && b <= 1000)) {
        if (a < b) {
            cout << "a < b" << endl;
        } else if (a > b) {
            cout << "a > b" << endl;
        } else {
            cout << "a == b" << endl;
        }
    }

    return 0;
}


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

int f(int s){
if(s%2==0)
  return s/2;
  else
    return s*3+1;
}
  int main() {
    int s;cin>>s;
    int count=1;
    if(s==1)
      cout<<4<<endl;
    else if(s==2)
      cout<<4<<endl;
    else{
    while(1)
    {
      s=f(s);
      count++;
      if(s==1)
        break;
    }
    cout<<count+1<<endl;
    }
  }
      


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


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

  ll n;
  cin >> n;
  vector<ll> a(n);
  rep(i,n) cin >> a[i];
  rep(i,n){
    if(a[i]==0) {
      cout << 0 << endl;
      return 0;
    }
  }
  ll prod =1;
  rep(i,n){
    if(prod> ((ll)5e18)/a[i]){
      cout << -1 << endl;
      return 0;
    }
    prod *= a[i];
    if(prod > ((ll) 1e18)){
      cout << -1 << endl;
      return 0;
    }
  }
  cout << prod << endl;
  
  return 0;
    

}


Measured memory_bytes: 3992
#include<stdio.h>
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC target("avx")
#define swap(a,b) ((*a!=*b)&&(*a+=*b,*b=*a-*b,*a-=*b))
const int IMIN=(1<<31);
#define rep(i,N) for(int i=0;i<(int)N;i++)
static inline char CH()
{
  static char buf[100000],*ptr1=buf,*ptr2=buf;
  return ptr1==ptr2&&(ptr2=(ptr1=buf)+fread(buf,1,100000,stdin),ptr1==ptr2)?EOF:*ptr1++;
}
static inline int IN(void)
{
  int x=0,f=0,c=CH();while(c<48||c>57){f^=c==45,c=CH();}
  while(c>47&&c<58){x=x*10+c-48,c=CH();}return f?-x:x;
}
static inline void OUT(long x){if(x<0)putchar('-'),x=-x;if(x>=10)OUT(x/10);putchar(x%10+48);}
static inline void Sort(unsigned *from,unsigned *to,unsigned bit)
{
  if(!bit||to<from+1)return;
  unsigned *left=from,*right=to-1;
  for(;;)
  {
    while(left<right&&!(*left&bit))left++;
    while(left<right&&(*right&bit))right--;
    if(left>=right)break;
    swap(left,right);
  }
  if(!(bit&*left)&&left<to)left++;
  bit>>=1;
  Sort(from,left,bit);
  Sort(left,to,bit);
}
static inline void Radix32(int *array,const int len)
{
  unsigned *x=(unsigned*)array;
  //rep(i,len>>1)x[i]^=IMIN,x[len-1-i]^=IMIN;
  Sort(x,x+len,IMIN);
  //rep(i,len>>1)x[i]^=IMIN,x[len-1-i]^=IMIN;
}
int main(void)
{
  int N=IN(),x=CH(),p=0,m=0,z=0,A[N];
  long K=0,count=0,l=-1e18,r=-l,mid;while(x>47&&x<58){K=K*10+x-48,x=CH();}
  rep(i,N){x=IN();if(x>0)A[m+p++]=x;else if(x<0)A[p+m++]=x;else z++;}
  if(K>1l*m*p&&K<1l*m*p+1l*z*(N-1)/2)return puts("0"),0;
  Radix32(A,m+p);
  if(K<=1l*m*p)r=1l;else l=-1l;
  while(l<=r)
  {
    mid=(l+r)/2;count=0;
    if(mid>=0)
    {
      int plus=p-1,minus=m-1;count+=1l*z*(p+m)+1l*z*(z-1)/2+1l*p*m;
      rep(i,plus){while(1l*A[i]*A[plus]>mid){plus--;}if(i>=plus){break;}count+=1l*plus-i;}
      rep(i,minus){while(1l*A[m+p-1-i]*A[m+p-1-minus]>mid){minus--;}if(i>=minus){break;}count+=1l*minus-i;}
    }
    else{int low=0;rep(i,m){while(1l*A[low]*A[p+i]>mid&&low<p){low++;}count+=1l*p-low;}}
    if(count>=K)r=mid-1l;else l=mid+1l;
  }
  return OUT(l),0;
}

Measured memory_bytes: 2236
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>

#include <algorithm>
#include <numeric>
#include <cmath>

using namespace std;
typedef long long ll;
const long double PI = (acos(-1));
const long long MOD = 1000000007;
#define rep(i,n) REP(i,0,n)
#define REP(i,x,n) for(int i=x;i<n;++i)

///////////////////////////////////////////////////
// -------------------- I/O -------------------- //
///////////////////////////////////////////////////
// https://stackoverflow.com/questions/610245/where-and-why-do-i-have-to-put-the-template-and-typename-keywords
template<typename T> void outputVec(const std::vector<T>& vec, const int precision = 0) {
	if (precision > 0) std::cout << std::fixed << std::setprecision(precision);
	for (auto it = vec.begin(); it != vec.end() - 1; ++it) { std::cout << *it << " "; }
	std::cout << *(vec.end() - 1) << "\n";
}
template<typename T> void outputVal(const T& res, const int precision = 0) {
	if (precision > 0) std::cout << std::fixed << std::setprecision(precision);
	std::cout << res << "\n";
}
template<typename T> T inputVal() { T a; std::cin >> a; return a; }
template<typename T> std::vector<T> inputVec(int N) {
	std::vector<T> vec(N);
	for (auto it = vec.begin(); it != vec.end(); ++it) { std::cin >> *it; }
	return vec;
}
template<typename T> void inputVec(std::vector<T>& vec) {
	for (auto it = vec.begin(); it != vec.end(); ++it) { std::cin >> *it; }
}

///////////////////////////////////////////////////
// ------------------- utils ------------------- //
///////////////////////////////////////////////////
// change min/max
template<class T> inline bool chMin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chMax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

///////////////////////////////////////////////////
// ------------------- main -------------------- //
///////////////////////////////////////////////////
void Main() {
	const string S = inputVal<string>();
	bool flg = true;
	rep(i, 3) {
		if (S[i] == S[i + 1]) flg = false;
	}
	outputVal(flg ?"Good":"Bad");
}

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

	double tmp;
	cin >> tmp;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define INF 1145141919
typedef long long int ll;
using namespace std;

template <typename T>
istream &operator>>(istream &is, vector<T> &vec)
{
    for (T &x : vec)
        is >> x;
    return is;
}

//*********************************************************
// 最大公約数（Greatest Common Divisor）を返す。
// 引数に０がある場合は０を返す。
//*********************************************************
ll gcd( ll m, ll n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	// ユークリッドの方法
	while( m != n )
	{
		if ( m > n ) m = m - n;
		else         n = n - m;
	}
	return m;
}//gcd
//*********************************************************
// 最小公倍数（Least Common Multiple）を返す。
// 引数に０がある場合は０を返す。
//*********************************************************
ll lcm( ll m, ll n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}//lcm

int main(){
    ll n,m;
    cin >> n >> m;
    string s,t;
    cin >> s >> t;

    ll res = lcm(n,m);
    //cout << res << endl;
    ll LN = res / n;
    ll LM = res / m;
    ll cnt = max(LN,LM);

    REP(i,res/(LN*LM)+1){
        
        if(s[i*LM%n]!=t[i*LN%m]){
            cout << "-1" << endl;
            return 0;
        }
    }
    cout << res << endl;

    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  long int mod=1e9+7;
  long long int arr[n];
  for(int i=0;i<n;i++)
    cin>>arr[i];
  long long int sum=0;
  for(int i=0;i<n;i++)
    sum=sum+arr[i];
  long long int res=0;
  for(int i=0;i<n-1;i++)
  {
    long long int a=sum-arr[i];
    sum=sum-arr[i];
    long long int p=((arr[i]%mod)*(a%mod))%mod;
    res=res+p;
  }
  long long int x=res%mod;
  cout<<x;
}
    


Measured memory_bytes: 5144
#include<bits/stdc++.h>
#include <array>
using namespace std;
using ULL = unsigned long long;
using UL = unsigned;
using LL = long long;
#define rep(i, n) for(UL i = 0; i < (n); i++)

struct Problem {

	void Solve() {
		deque<UL> S;
		string SS; cin >> SS;
		rep(i, SS.size()) {
			S.push_back(SS[i]);
		}
		deque<UL> Tg = { 'k', 'e', 'y', 'e', 'n', 'c', 'e' };
		while (S.size() && Tg.size()) {
			if (S.front() != Tg.front()) break;
			S.pop_front(); Tg.pop_front();
		}
		while (S.size() && Tg.size()) {
			if (S.back() != Tg.back()) break;
			S.pop_back(); Tg.pop_back();
		}
		if (Tg.size() == 0) cout << "YES" << endl;
		else cout << "NO" << endl;
	}

	Problem();
};
int main() {
	unique_ptr<Problem> p(new Problem());
	p->Solve();
	return 0;
}
Problem::Problem() {
	cout << fixed << setprecision(10);
}

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

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

string S;

int main(){
	cin >> S;
	bool b = 0;
	repp(i,1,S.size()){
		if(S[i-1] == 'A' && S[i] == 'C') b = 1;
	}
	cout << (b ? "Yes" : "No") << endl;
	return 0;
}


Measured memory_bytes: 256
<?php
$n = trim(fgets(STDIN));
$a = explode(' ', trim(fgets(STDIN)));
$swapped = 0;
$flag = true;

for ($i=0; $flag; $i++) {
  $flag = false;

  for ($j=$n - 1; $j >= $i + 1; $j--) {
    if ($a[$j] < $a[$j - 1]) {
      $tmp = $a[$j];
      $a[$j] = $a[$j - 1];
      $a[$j - 1] = $tmp;
      $flag = true;
      $swapped++;
    }
  }
}

echo implode(' ', $a) . PHP_EOL;
echo $swapped . PHP_EOL;


Measured memory_bytes: 9264