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

// C - Traveling
// https://atcoder.jp/contests/abc086/tasks/arc089_a
public class Main {

    /**
     * 最短で移動できるか移動して距離的に可能か、
     * かつ t 時間に指定位置に行けるか (残り時間が偶数か)
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = Integer.parseInt(scanner.next());
        int[] T = new int[N];
        int[] X = new int[N];
        int[] Y = new int[N];

        for (int i = 0; i < N; i++) {
            T[i] = Integer.parseInt(scanner.next());
            X[i] = Integer.parseInt(scanner.next());
            Y[i] = Integer.parseInt(scanner.next());
        }
        scanner.close();

        int currentX = 0;
        int currentY = 0;

        for (int i = 0; i < N; i++) {
            int t = T[i];
            int x = X[i];
            int y = Y[i];

            int diff = Math.abs(currentX - x) + Math.abs(currentY - y);
            if (diff > t) {
                // 到達不可
                System.out.println("No");
                return;
            }

            int diffT = t - diff;
            if (diffT % 2 != 0) {
                // ターン合わせが出来ないので到達不可
                System.out.println("No");
                return;
            }
        }

        System.out.println("Yes");
    }
}


Measured memory_bytes: 61000
#include<stdio.h>
#include<ctype.h>
int main(){
  int c;
  int cnt[500]={0};
  while(c!=EOF){
    c=getchar();
    if(islower(c)){
      cnt[c]++;
    }else{
      cnt[c+32]++;
    }
  }
  for(c='a';c<='z';c++){
    printf("%c : %d\n",c,cnt[c]);
  }
  return 0;
}

Measured memory_bytes: 2680
#pragma GCC optimize("-Ofast")

#include <bits/stdc++.h>

using namespace std;

#define ll long  long

struct light{
    int k;
    vector<int> s;
    int p;
};

/* flagの状態においてlがついているか確認する */
bool check(int f,light* l){
    int c = 0;
    for (auto s : l->s)
        if ((f >> (s - 1)) & 1)
            c++;
    return (c & 1) == (l->p & 1);
}

signed main(){
    int n,m;
    cin >> n >> m;
    vector<light> lights(m);
    for (int i = 0;i < m;++i){
        light* l = &lights[i];
        cin >> l->k;
        for (int j = 0;j < l->k;++j){
            int s;
            cin >> s;
            l->s.push_back(s);
        }
    }
    for (int i = 0;i < m;++i){
        int p;
        cin >> p;
        lights[i].p = p;
    }

    ll ans = 0;
    int Max = (int)pow(2,n);
    for (int flag = 0;flag < Max;++flag){
        bool is_ok = true;
        for (int i = 0;i < m;++i){
            is_ok = is_ok && check(flag,&lights[i]);
            if (!is_ok) break;
        }
        if (is_ok) ans++;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000001
#define VMAX 10000

int main(){
  unsigned short *A, *B;
  int C[VMAX+1];
  int n, i, j;

  scanf("%d", &n);

  A = malloc(sizeof(short)*n+1);
  B = malloc(sizeof(short)*n+1);

  for(i=0;i<=VMAX;i++) C[i]=0;
  
  for(i=1;i<=n;i++){
    scanf("%d",&A[i]);
    C[A[i]]++;
  }

  for(i=1;i<=VMAX;i++)
    C[i]=C[i]+C[i-1];

  for(j=n;j>=1;j--){
    B[C[A[j]]]=A[j];
    C[A[j]]--;
  }

  for(i=1;i<=n;i++){
    if(i>1) printf(" ");
    printf("%d",B[i]);
  }
  printf("\n");
  
  return 0;
}



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

#define REP(i,n) for(auto i=0;i<n;++i)
#define REPR(i,n) for(auto i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(auto i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define ll long long
#define INF 999999999
#define MOD 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair
#define SV(n,v) {int tmp;for(int i=0;i<n;++i){scanf("%d",&tmp);v.push_back(tmp);}}

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

using namespace std;

typedef pair<int,int> pii;

int main(){

  llong x;
  cin >> x;

  llong ans = 0;
  ans += 1000 * (x / 500);
  x = x % 500;

  ans += 5 * (x / 5);

  cout << ans << endl;
  return 0;

}





Measured memory_bytes: 3192
#include <iostream>
#include <vector>

using namespace std;

int main(){
  int n, i, ain, flag = 1, tmp, cnt = 0;
  vector<int> a;

  cin >> n;
  for(i = 0;i < n;++i){
    cin >> ain;
    a.push_back(ain);
  }

  while(flag){
    flag = 0;
    for(i = n - 1;i >= 1;--i){
      if(a[i] < a[i-1]){
	tmp = a[i];
	a[i] = a[i-1];
	a[i-1] = tmp;
	flag = 1;
	++cnt;
      }
    }
  }
  for(i = 0; i < n;++i){
    cout << a[i];
    if(i != n-1)cout << " ";
  }
  cout << "\n" <<cnt << endl;
  return 0;
}


Measured memory_bytes: 3160
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps=1e-8;
const int inf=0x3f3f3f3f;
ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); } 
int main()
{
	char ch;
	scanf("%c",&ch);
	if(ch>='a'&&ch<='z') cout<<"a";
	else if(ch>='A'&&ch<='Z') cout<<"A";
	return 0;
}

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

typedef char                SINT8;
typedef unsigned char       UINT8;
typedef short               SINT16;
typedef unsigned short      UINT16;
typedef int                 SINT32;
typedef unsigned int        UINT32;
typedef long long           SINT64;
typedef unsigned long long  UINT64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))


SINT32 main() {
    SINT32 a;
    scanf("%d",&a);
    SINT32 ans;

    a = (a-1) / 111;

    ans = (a+1) * 111;



    printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
using namespace std;

#define min(a,b) (a<b?a:b)
#define mem(a,n) memset(a,sizeof(a),n)
typedef long long ll;
const int mod=1e9+7;
const int N=1e5+5;
const int INF=0x3f3f3f3f;
bool vis[N][100];

int digit_sum(int x)
{
    int sum=0;
    while(x)
    {
        sum+=(x%10);
        x/=10;
    }
    return sum;
}
int n;
void dfs(int x,int sum)
{
    if(sum>=80||vis[x][sum]) return;
    vis[x][sum]=1;
    for(int i=0; i<10; i++)
        dfs((10*x+i)%n,sum+i);
}

int main()
{
    while(~scanf("%d",&n))
    {
       // printf("n=%d\n",n);
        mem(vis,0);
        for(int i=0; i<n; i++)
            dfs(i,digit_sum(i));
        int ans=INF;
       // printf("%d\n",ans);
        for(int i=1; i<80; i++)
            if(vis[0][i])
                ans=min(ans,i);
        printf("%d\n",ans);
    }
    return 0;
}
/**
2
1 5
2 4
3 6
3
1 1 1
2 2 2
3 3 3
6
3 14 159 2 6 53
58 9 79 323 84 6
2643 383 2 79 50 288
**/


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

using namespace std;

typedef long long ll;
typedef complex<double> point;
#define mapii map<int, int>
#define debug(a) cout << #a << ": " << a << endl
#define debuga1(a, l, r) fto(i, l, r) cout << a[i] << " "; cout << endl
#define fdto(i, r, l) for(int i = (r); i >= (l); --i)
#define fto(i, l, r) for(int i = (l); i <= (r); ++i)
#define forit(it, var) for(__typeof(var.begin()) it = var.begin(); it != var.end(); it++)
#define forrit(rit, var) for(__typeof(var.rbegin()) rit = var.rbegin(); rit != var.rend(); rit++)
#define ii pair<int, int>
#define iii pair<int, ii>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define maxN 105
#define MOD 1000
#define oo 1000000000000000007LL
#define sz(a) (int)a.size()

const double PI = acos(-1.0);

template <class T>
T min(T a, T b, T c) {
    return min(a, min(b, c));
}

template <class T>
T max(T a, T b, T c) {
    return max(a, max(b, c));
}

int n, par[maxN], dist[maxN], child[maxN], maxChild[maxN];
int rad;
ll minLeaf;
vector<int> g[maxN];

void DFS(int u) {
    for(int v: g[u]) {
        if (par[u] == v) continue;
        par[v] = u;
        dist[v] = dist[u]+1;
        ++child[u];
        DFS(v);
    }
}

ll Solve(int u) {
    ll leaf = 1;

    memset(par, 0, sizeof par);
    memset(dist, 0, sizeof dist);
    memset(maxChild, 0, sizeof maxChild);
    memset(child, 0, sizeof child);
    DFS(u);

//    printf("Solve: %d\n", u);
//    fto(u, 1, n) printf("%d %d\n", dist[u], child[u]);

    fto(u, 1, n) maxChild[dist[u]] = max(maxChild[dist[u]], child[u]);
//    fto(i, 0, rad-2) printf("%d %d\n", i, maxChild[i]);

    fto(i, 0, rad-2) leaf *= maxChild[i];

    return leaf;
}

ll Solve(int u, int v) {
    ll leaf = 2;

    memset(par, 0, sizeof par);
    memset(dist, 0, sizeof dist);
    memset(maxChild, 0, sizeof maxChild);
    memset(child, 0, sizeof child);
    par[u] = v;
    par[v] = u;
    DFS(u);
    DFS(v);

    fto(u, 1, n) maxChild[dist[u]] = max(maxChild[dist[u]], child[u]);
//    printf("Solve: %d %d\n", u, v);
//    fto(u, 1, n) printf("%d %d\n", dist[u], child[u]);

    fto(i, 0, rad-2) leaf *= maxChild[i];
//    fto(i, 0, rad-2) printf("%d %d\n", i, maxChild[i]);

    return leaf;
}

int main () {
    scanf("%d", &n);
    fto(i, 1, n-1) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].pb(v); g[v].pb(u);
    }

    DFS(1);

    int s = max_element(dist+1, dist+n+1)-dist;

    memset(par, 0, sizeof par);
    memset(dist, 0, sizeof dist);
    DFS(s);

    int t = max_element(dist+1, dist+n+1)-dist;

//    debug(s);
//    debug(t);

    int u = t;
    fto(i, 1, dist[t]/2) u = par[u];

    rad = dist[t]/2 + 1;
//    debug(rad);
    memset(child, 0, sizeof child);
    minLeaf = oo;
    if (dist[t]%2 == 1) {
        int v = par[u];
        minLeaf = min(minLeaf, Solve(u, v));
    } else {
        minLeaf = min(minLeaf, Solve(u));
        for(int v: g[u]) {
            minLeaf = min(minLeaf, Solve(u, v));
        }
    }

    cout << rad << " " << minLeaf;

    return 0;
}


Measured memory_bytes: 256
/*
	  Chase
	   Your
	  Legend

	英雄志逐传奇
*/

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <math.h>
#include <stdio.h>

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


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

	vector<int>vec(N);
	rep(i, N) {
		cin >> vec[i];
	}

	for (int i = 0; i < N - 1; i++) {
		if (vec[i] < vec[i + 1]) {
			vec[i + 1] = vec[i + 1] - 1;
		}
	}
	
	int M = 1;
	for (int i = 0; i < N - 1; i++) {
		if (vec[i] > vec[i + 1]) {
			M++;
		}
		else {
			M = M + 0;
		}
	}
	if (M == 1) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}


Measured memory_bytes: 640
#include <stdio.h>
int main(void){
  int x,a,b,c,i,j,t,s,ans=0;
  scanf("%d%d%d%d",&a,&b,&c,&x);
  for (i=0;i<=a&&i*500<=x;i++){
    s=x-i*500;
    for (j=0;j<=b&&j*100<=s;j++){
      t=s-j*100;
      if (c*50>=t) ans++;
    }
  }
  printf("%d\n",ans);
  return 0;
}

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

int64_t MOD;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
void mul(int64_t& a, int64_t b){
    a = a*b % MOD;
}

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

    int64_t pow[302][302] = {0};
    for(int i=1; i<=301; i++){
        pow[i][0] = 1;
        for(int j=1; j<=301; j++) pow[i][j] = pow[i][j-1] * i % MOD;
    }

    int64_t sub[302][302] = {0};
    sub[0][0] = 1;
    for(int i=1; i<=301; i++) for(int j=0; j<=301; j++) for(int k=0; j+k<=301; k++) add(sub[i][j+k], sub[i-1][j] * pow[i][k]);

    int64_t dp[301][301] = {0};
    dp[0][0] = 1;
    for(int i=1; i<=300; i++) for(int j=0; j<=300; j++) for(int k=0; j+k<=300; k++) add(dp[i][j+k], dp[i-1][j] * sub[j+1][k]);

    cout << dp[K][N] << endl;
    return 0;
}


Measured memory_bytes: 2432
sx, sy, tx, ty = map(int,input().split())
keiro = ""
for i in range(ty-sy):
    keiro += "U"
for i in range(tx-sx):
    keiro += "R"
keiro0 = keiro
keiro = ""
for i in range(ty-sy):
    keiro += "D"
for i in range(tx-sx):
    keiro += "L"
keiro1 = keiro

ans = keiro0+keiro1+"LU"+keiro0+"RDRD"+keiro1+"LU"

print(ans)

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

using namespace std;

int main(void) {
	int N;
	cin >> N;
	int sum = 0;
	vector<int> a(N);
	for (int i = 0; i < N; ++i) {
		cin >> a[i];
		sum += a[i];
	}
	sort(a.begin(),a.end());
	int asum = 0;
	for (int i = N-1; i >= 0; i-=2) {
		asum += a[i];
	}
	cout << asum-(sum-asum) << endl;
	return 0;
}



Measured memory_bytes: 256
fun main(args: Array<String>) {

    val s = readLine()!!

    if (isPalindrome(s) &&
            isPalindrome(s.substring(0 until ((s.length - 1) / 2))) &&
            isPalindrome(s.substring(((s.length + 3) - 1) / 2 until s.length))) {
        println("Yes")
    } else {
        println("No")
    }

}

fun isPalindrome(s: String) = s == s.reversed()


Measured memory_bytes: 35952
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=1e9+7;
int main()
{
    int n, m; cin>>n>>m;
    string s; cin>>s;
    int j=0;
    vector<int> v;
    bool nuo=1;
    for(int i=1; i<m; i++){
        if(s[i]!=s[0]){
            nuo=0;
            v.push_back(i-j);
            j=i+1;
        }
    }
    if(nuo){
        ll dp[2][200002]={};
        dp[0][0]=1;
        for(int i=1; i<n; i++){
            dp[1][i]+=dp[0][i-1];
            dp[0][i]+=(dp[0][i-1]+dp[1][i-1]);
            dp[0][i]%=MOD;
            dp[1][i]%=MOD;
        }
        ll ans=dp[0][n-1]+dp[1][n-1];
        fill(dp[0], dp[0]+n+1, 0);
        fill(dp[1], dp[1]+n+1, 0);
        dp[1][0]=1;
        for(int i=1; i<n; i++){
            dp[1][i]+=dp[0][i-1];
            dp[0][i]+=(dp[0][i-1]+dp[1][i-1]);
            dp[0][i]%=MOD;
            dp[1][i]%=MOD;
        }
        ans+=dp[0][n-1];
        ans%=MOD;
        cout<<ans<<endl;
        return 0;
    }
    if(n%2==1){
        cout<<0<<endl;
        return 0;
    }
    int mx=v[0]+1-v[0]%2;
    for(int i=1; i<v.size(); i++){
        if(v[i]&1) mx=min(mx, v[i]);
    }
    ll dp[200002]={}, sum[200002];
    dp[0]=1;
    sum[0]=1;
    for(int i=1; i<=n; i++){
        if(i&1) sum[i]=sum[i-1];
        else{
            if(i-mx-3>=0) dp[i]=(sum[i-2]-sum[i-mx-3]+MOD)%MOD;
            else dp[i]=sum[i-2];
            sum[i]=(sum[i-1]+dp[i])%MOD;
        }
    }
    ll ans=0;
    for(int i=1; i<=min(mx, n-1); i+=2){
        ans+=(ll)(i+1)*dp[n-i-1];
        ans%=MOD;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 5372
// デバッグ実行：Ctrl+F5

using System;

class Program
{
    static void Main(string[] args)
    {
        String line;
        line = Console.ReadLine();
        String[] words = line.Split(' ');
        int N = int.Parse(words[0]);
        int K = int.Parse(words[1]);
        if ((N+1) / 2 >= K)
        {
            Console.WriteLine("YES");
        }
        else
            Console.WriteLine("NO");
    }
}

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

int main() {
	int n = 0;
	cin >> n;
	string s;
	cin >> s;

	vector<string> char_s(n);
	for (size_t i = 0; i < n; ++i) {
		char_s.at(i) = s.at(i);
	}

	vector<int> w_i(n);
	vector<int> e_i(n);

	for (int i = 1; i < n; ++i) {
		if (char_s.at(i - 1) == "W") {
			w_i.at(i) = w_i.at(i - 1) + 1;
		}
		else {
			w_i.at(i) = w_i.at(i - 1);
		}
	}

	for (int i = n - 2; i >= 0; --i) {
		if (char_s.at(i + 1) == "E") {
			e_i.at(i) = e_i.at(i + 1) + 1;
		}
		else {
			e_i.at(i) = e_i.at(i + 1);
		}
	}

	vector<int> all(n);
	for (int i = 0; i < n; ++i) {
		all.at(i) = w_i.at(i) + e_i.at(i);
	}

	int min = *min_element(all.cbegin(), all.cend());

	cout << min << endl;
}

Measured memory_bytes: 20484
dishes = []
5.times do |i|
  dishes << gets.chomp.to_i
end
min = 10 
total = 0
dishes.each do |d|
  min = (d % 10 > 0 && d % 10 < min) ? d % 10 : min
  total += d + (d % 10 > 0 ? (10 - d % 10) : 0)
end
puts total - (10 - min)


Measured memory_bytes: 1788
import math
def gcd(x,y):
    if x < y:
        x, y = y, x
    if y == 0:
        return x
    if  x % y == 0:
        return y
    else:
        return gcd(y, x%y)


a, b = list(map(int, input().split()))
d = gcd(a, b)
if d == 1:
    print(1)
    quit()
li = []
while True:
    for i in range(2, int(math.sqrt(d)) + 1):
        if d % i == 0:
            if not i in li:
                li.append(i)
                d = d // i
                break
            else:
                d = d // i
                break
    else:
        if d != 1:
            li.append(d)
            break

print(len(set(li)) + 1)


Measured memory_bytes: 3064
using System;
using System.Linq;
using System.Text;
using System.Collections;
using System.Collections.Generic;

namespace AtCoder
{
	class Program
	{
		static void Main(string[] args)
		{
			var n = ReadLineIntSplit();
			int a = n[0];
			int b = n[1];

			int i = 1;
			while (true)
			{
				if (i > 1250) break;
				if ((int)(i * 0.08) == a && (int)(i * 0.1) == b) break;
				i++;
			}

			if (i < 1250)
			Console.WriteLine(i);
			else Console.WriteLine("-1");

		}

		public static int nCm(int n, int m)
		{
			if (n == 0) return 0;
			if (m == 0) return 1;
			return n * nCm(n - 1, m - 1) / m;
		}

		public static string ReadLine()
		{
			return Console.ReadLine();
		}

		public static int ReadLineInt()
		{
			return int.Parse(ReadLine());
		}

		public static string[] ReadLineStringSplit(char s = ' ')
		{
			return ReadLine().Split(s).ToArray();
		}

		public static int[] ReadLineIntSplit(char s = ' ')
		{
			return ReadLine().Split(s).Select(x => int.Parse(x)).ToArray();
		}

		public static long[] ReadLineLongSplit(char s = ' ')
		{
			return ReadLine().Split(s).Select(x => long.Parse(x)).ToArray();
		}
	}
}

Measured memory_bytes: 13396
#include <stdio.h>
#include <stdlib.h>
#define int long long

typedef struct {
	int a;
	int b;
	int c;
}edge;

typedef struct {
	int N;
	int *u;
	int *u_rank;
	int *u_val;
}union_find;

union_find *make_union_find(int N, int val){
	int i;
	union_find *uf = (union_find *)malloc(sizeof(union_find));
	uf->N = N;
	uf->u = (int *)malloc(sizeof(int) * N);
	uf->u_rank = (int *)malloc(sizeof(int) * N);
	uf->u_val = (int *)malloc(sizeof(int) * N);
	for(i = 0; i < N; i++){
		(uf->u)[i] = i;
		(uf->u_rank)[i] = 1;
		(uf->u_val)[i] = val;
	}
	return uf;
}

int root_uf(int x, union_find *uf){
	int *u = uf->u;
	int *u_val = uf->u_val;
	if(u[x] == x){
		return x;
	}
	else if(u[u[x]] == u[x]){
		return u[x];
	}
	else{
		int x_root = root_uf(u[x], uf);
		u_val[x] += u_val[u[x]];
		u[x] = x_root;
		return u[x];
	}
}

void combine_uf(int x, int y, union_find *uf){
	int x_root = root_uf(x, uf);
	int y_root = root_uf(y, uf);
	int *u = uf->u;
	int *u_rank = uf->u_rank;
	int *u_val = uf->u_val;
	if(x_root == y_root){
		return;
	}
	else if(u_rank[x_root] < u_rank[y_root]){
		u[x_root] = y_root;
		u_rank[y_root] += u_rank[x_root];
		u_rank[x_root] = 0;
		u_val[x_root] -= u_val[y_root];
	}
	else{
		u[y_root] = x_root;
		u_rank[x_root] += u_rank[y_root];
		u_rank[y_root] = 0;
		u_val[y_root] -= u_val[x_root];
	}
}

//xとyが同じ集合に属していれば1を,そうでなければ0を返す
int is_same_union_uf(int x, int y, union_find *uf){
	if(root_uf(x, uf) == root_uf(y, uf)){
		return 1;
	}
	else{
		return 0;
	}
}

void add_val_uf(int x, int val, union_find *uf){
	int x_root = root_uf(x, uf);
	uf->u_val[x_root] += val;
}

//xが属する集合の要素数を返す
int rank_uf(int x, union_find *uf){
	return (uf->u_rank)[root_uf(x, uf)];
}

int val_uf(int x, union_find *uf){
	int x_root = root_uf(x, uf);
	int *u_val = uf->u_val;
	if(x == x_root){
		return u_val[x];
	}
	else{
		return u_val[x_root] + u_val[x];
	}
}

signed compare(const void *x, const void *y){
	return ((edge *)y)->c - ((edge *)x)->c;
}

signed main(){
	int N, i;
	scanf("%lld", &N);
	edge *es = (edge *)malloc(sizeof(edge) * (N - 1));
	for(i = 0; i < N - 1; i++){
		scanf("%lld%lld%lld", &es[i].a, &es[i].b, &es[i].c);
		es[i].a--;
		es[i].b--;
	}
	qsort(es, N - 1, sizeof(edge), compare);
	union_find *uf = make_union_find(N, 0);
	int a, b, c, a_rank, b_rank;
	for(i = 0; i < N - 1; i++){
		a = es[i].a;
		b = es[i].b;
		c = es[i].c;
		a_rank = rank_uf(a, uf);
		b_rank = rank_uf(b, uf);
		add_val_uf(a, c * b_rank, uf);
		add_val_uf(b, c * a_rank, uf);
		combine_uf(a, b, uf);
	}
	for(i = 0; i < N; i++){
		printf("%lld\n", val_uf(i, uf));
	}
	return 0;
}

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

int q(const int *a,const int *b)
{
    return *a-*b;
}

int main(void)
{
    int n[3];
    scanf("%d%d%d",&n[0],&n[1],&n[2]);
    qsort(n,3,4,q);
    puts(n[0]+n[1]==n[2]?"Yes":"No");
    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include <cmath>
#include <limits>
#include<set>
#include <iomanip>
#include <queue>
#pragma GCC optimize("Ofast")
using namespace std;
const long long INF=20000000000;
//setprecision(2) <<

const int MOD = 1000000007;

long long max(long long a,long long b){
	if(a<b)return b;
	else return a;	
}
long long min(long long a,long long b){
	if(a>b)return b;
	else return a;	
}

int A[100006];
int N;

int f(double n){
	int ret=0;
	bool a = (n<A[0]);
	for(int i=0;i<N-1;i++){
		if((A[i]-n)*(A[i+1]-n)<0){
			if(a){
				ret++;
				a=false;
			}
			else a=true;
		}
	}
	if(a)ret++;
	//cout<<n<<" "<<ret<<endl;
	return ret;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N;
	cin>>N;
	double ans=(double)((int)N/2)/N;
	if(N%2==0)cout<<0.5<<endl;
	else cout<<(double)(1-ans)<<endl;
}
	


Measured memory_bytes: 256
n,m=[int(i) for i in input().split()]
P=[[int(i) for i in input().split()] for j in range(n)]

for i in range(n):
    del P[i][0]
    
K = set(P[0])
L = {}
for i in range(1,n):
    L = set(P[i])
    K = K & L
print(len(K))

Measured memory_bytes: 3064
//#include "debug.h"
#include <string.h>
#include <limits.h>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 100000
typedef long long i64;

int n;
char s[MAXN+1];
int len;

int input() {
	if (scanf("%s", s) < 0) return 0;
	return 1;
}

void init() {
}

int solve() {
	n = strlen(s);
	for (int i=0; i<n-1; i++) {
		if (s[i]==s[i+1]) {
			len = 2;
			return i;
		}
		if (i<n-2 && s[i]==s[i+2]) {
			len = 3;
			return i;
		}
	}
	return -1;
}

void output(int ans) {
	if (ans < 0) printf("-1 -1\n");
	else printf("%d %d\n", ans+1, ans+len);
}

void cleanup() {
}

int main() {
	//precalc();
	//int ca; scanf("%d", &ca);
	while (input()) {
		init();
		output(solve());
		cleanup();
		//break;
	}
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll ZERO = 0;
const int Inf = 1e9;
const ll INF = 9223372036854775807;
const ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<int,int> P;

ll dp[110][100010];

int main() {
    int N,W;
    cin >> N >> W;
    vector<int> w(N);
    vector<int> v(N);
    for(int i = 0;i < N;i++) {
        int A,B;
        cin >> A >> B;
        w.at(i) = A;
        v.at(i) = B;
    }
    for(int i = 0;i < W;i++) {
        dp[0][i] = 0;
    }
    for(int i = 0;i < N;i++) {
        for(int j = 0;j <= W;j++) {
            if(j < w.at(i)) {
                dp[i + 1][j] = dp[i][j];
            }
            else {
                dp[i + 1][j] = max(dp[i][j],dp[i][j - w.at(i)] + v.at(i));
            }
        }
    }
    cout << dp[N][W] << endl;
}

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

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

int N,M,A[1010],B[1010],counter[1010];


int main(){
  cin >> N >> M;
  rep(i,N)cin>>A[i];
  rep(i,M){
    cin >> B[i];
    rep(j,N)if(A[j]<=B[i]){
      counter[j]++;
      break;
    }
  }

  int ans = 0;
  rep(i,N)if(counter[i]>counter[ans])ans = i;
  cout << ans+1 << endl;

  return 0;
}

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

#define INF 1000010000
#define nl '\n'
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pdd pair<double,double>
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define sz(c) (c).size()
#define rep(i,n) for( int i = 0; i < n; ++i )
#define repi(i,n) for( int i = 1 ; i <= n; ++i )
#define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
#define repf(j,i,n) for( int j = i ; j < n ; ++j )
#define die(s) {std::cout << s << nl;}
#define dier(s) {std::cout << s; return 0;}
#define dbg(var) {std::cout << #var << "  = " << var << nl;}
#define vi vector<int>
typedef long long ll;

using namespace std;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.precision(0); 

	int w , h;
	cin >> h >> w;
	
	vector<string> v(h);
	rep(i , h) cin >> v[i];
	
	rep(i , h){
		rep(j , w){
			if(v[i][j] == '.') continue;
			bool solo = true;
			if(i - 1 >= 0 && v[i - 1][j] == '#') solo = false;
			if(i + 1 < h && v[i + 1][j] == '#') solo = false;
			if(j - 1 >= 0 && v[i][j - 1] == '#') solo = false;
			if(j + 1 < h && v[i][j + 1] == '#') solo = false;
			if(solo){
				dier("No");
			}
		}
	}
	
	cout << "Yes\n";

	return 0;
}

Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    TA = []
    for _ in range(N):
        t, a = map(int, input().split())
        TA.append((t, a))

    A, B = 1, 1
    for i in range(N):
        x, y = TA[i]
        n = max((A + x - 1) // x, (B + y - 1) // y,)
        A = n * x
        B = n * y

    ans = A + B
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
// フェルマーの小定理
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const (
	p = 1000000007
)

var (
	fac []int
)

func mpow(x int, n int) int {
	result := 1
	for n != 0 {
		if n&1 == 1 {
			result = result * x % p
		}
		x = x * x % p
		n >>= 1
	}
	return result
}

func mcomb(n int, k int) int {
	if n == 0 && k == 0 {
		return 1
	}
	if n < k || k < 0 {
		return 0
	}
	return (fac[n] * mpow(fac[n-k], p-2) % p) * mpow(fac[k], p-2) % p
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	defer flush()

	N := readInt()
	K := readInt()

	n := max(K, N-K+1)
	fac = make([]int, n+1)
	fac[0] = 1
	for i := 0; i < n; i++ {
		fac[i+1] = fac[i] * (i + 1) % p
	}

	for i := 1; i <= K; i++ {
		println(mcomb(K-1, i-1) * mcomb(N-K+1, i) % p)
	}
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}

var stdoutWriter = bufio.NewWriter(os.Stdout)

func flush() {
	stdoutWriter.Flush()
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdoutWriter, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdoutWriter, args...)
}


Measured memory_bytes: 640
#include <cmath>
#include <vector>
#include <map>
#include <functional>
#include <queue>
#include <iostream>
#include <string>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <cstdint>
#include <climits>
#include <unordered_set>
#include <sstream>

using namespace std;

#define ll long long int
#define ti4 tuple<int,int,int,int>
#define pii pair<ll,ll>
#define REP(x,n) for(int x = 0;x < n;x++)

struct UnionFind {
    vector<ll> data;
    UnionFind(ll size) : data(size, -1) { }
    bool unionSet(ll x, ll y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }
    bool findSet(ll x, ll y) {
        return root(x) == root(y);
    }
    ll root(ll x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    ll size(ll x) {
        return -data[root(x)];
    }
};

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

ll lcm(ll a, ll b)
{
    ll temp = gcd(a, b);
    
    return temp ? (a / temp * b) : 0;
}

int main()
{
    string s;
    cin >> s;
    int n = (int)s.length();
    bool cFound = false;
    for(int i = 0;i < n;i++)
    {
        if(s[i] == 'C')
        {
            cFound = true;
        }
        else if(s[i] == 'F')
        {
            if(cFound)
            {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;    
}

Measured memory_bytes: 256
n = int(input())
a = [int(input()) for _ in range(n)]

#n = 10
#a = [10,0,2,3,4,5,6,7,8,9]

a.insert(0,0)
i = 1
ans = 0
for _ in range(n+1):
  ans += 1
  i = a[i]
  if i == 2:
    break
else:
  ans = -1

print(ans)


Measured memory_bytes: 7084
#include<bits/stdc++.h>
const int N=305;
long long ans;
int H,W,a[N][N],b[N*2][N*2],c[N*2][N*2],i,j,d;
char cc[N];
int main(){
	scanf("%d%d",&H,&W);
	for(i=1;i<=H;++i)for(scanf("%s",cc+1),j=1;j<=W;++j)if(cc[j]=='#')
		a[i][j]=b[i-j+W][i+j-1]=c[i+j-1][i-j+W]=1;
	for(i=1;i<N*2;++i)for(j=1;j<N*2;++j)b[i][j]+=b[i][j-1],c[i][j]+=c[i][j-1];
	for(d=1;d<=std::min(H,W);d++){
		for(i=1;i<=H-d;++i)for(j=1;j<=W-d;++j)if(a[i][j]==1 && a[i+d][j+d]==1){
			int x=i-j+W,y=i+j-1;
			if(x>d*2)ans+=b[x-d*2][y+d*2]-b[x-d*2][y-1];
			if(x+d*2<N*2)ans+=b[x+d*2][y+d*2]-b[x+d*2][y-1];
		}
		for(i=1;i<=H-d;++i)for(j=d+1;j<=W;++j)if(a[i][j]==1 && a[i+d][j-d]==1){
			int x=i-j+W,y=i+j-1;
			if(y>d*2)ans+=c[y-d*2][x+d*2]-c[y-d*2][x-1];
			if(y+d*2<N*2)ans+=c[y+d*2][x+d*2]-c[y+d*2][x-1];
		}
		for(i=1;i<=H;++i)for(j=1;j<=W;++j)if(a[i][j]){
			int p=i>d && j>d?a[i-d][j-d]:0,q=i>d && j+d<=W?a[i-d][j+d]:0,
				r=i+d<=H && j+d<=W?a[i+d][j+d]:0,s=i+d<=H && j>d?a[i+d][j-d]:0;
			ans-=p*q+q*r+r*s+s*p;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 3456
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
const int MaxN = 100;

char a[MaxN + 5][10],b[MaxN + 5][10];

int main()
{
	int ans[MaxN + 5];
	int n,m;
	char lj;
	while(~scanf("%d",&n))
	{
		memset(ans,0,sizeof(ans));
		for(int i = 1;i <= n;i++) scanf("%c%s",&lj,a[i]);
		scanf("%d",&m);
		for(int i = 1;i <= m;i++) scanf("%s",b[i]);
		for(int i = 1;i <= n;i++)
		{
			for(int j = 1;j <= n;j++)
			{
				if(strcmp(a[i],a[j])==0) ans[i]++;
			}
			for(int j = 1;j <= m;j++)
			{
				if(strcmp(a[i],b[j])==0) ans[i]--;
			}
		}
		sort(ans+1,ans+1+n);
		if(ans[n]>=0) printf("%d\n",ans[n]);
		else printf("0\n");
	}
	return 0;
}

Measured memory_bytes: 128
using System;

namespace AtCoder.Abc
{
    class QuestionB
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            var sp = Console.ReadLine().Split(' ');
            var a = int.Parse(sp[0]);
            var b = int.Parse(sp[1]);
            var c = int.Parse(sp[2]);
            var d = int.Parse(sp[3]);


            long max = (long)a * (long)c;
            long cal = (long)a * (long)d;
            if (max < cal) max = cal;
            cal = (long)b * (long)c;
            if (max < cal) max = cal;
            cal = (long)b * (long)d;
            if (max < cal) max = cal;

            Console.WriteLine(max);

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 27508
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        String wrongA;
        String wrongB;

        Scanner scanner = new Scanner(System.in);
        wrongA = scanner.nextLine();
        wrongB = scanner.nextLine();
        scanner.close();

        if (!"1".equals(wrongA) && !"1".equals(wrongB)) {
            System.out.println("1");
        } else if (!"2".equals(wrongA) && !"2".equals(wrongB)) {
            System.out.println("2");
        } else if (!"3".equals(wrongA) && !"3".equals(wrongB)) {
            System.out.println("3");
        }

    }
}

Measured memory_bytes: 20948
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

using namespace std;

int main()
{
	int n,right,i=0;
	vector<int> train;
	while(cin>>n)
	{
		vector<int>::iterator it = train.begin();
		while(it!=train.end()) ++it;
		if(n==0)
		{
			--it;
			right = *it;
			cout<<right<<endl;
			train.pop_back();
			i++;
		}
		else
		train.push_back(n);
	}
	return 0;
}

Measured memory_bytes: 1208
// 素因数分解して冪数/Nをかけていくのでどうだ
// サンプル4がありがたい

package main

import "fmt"

func main() {
	var N, P int
	fmt.Scan(&N, &P)
	dividers := make(map[int]int)
	for i := 2; i*i <= P; i++ {
		tmp := 0
		_P := P
		_pow := i
		for _P%i == 0 {
			_pow *= i
			tmp++
			_P /= i
		}
		if tmp > 0 {
			dividers[i] = tmp
			P /= (_pow / i)
		}
	}
	if P > 0 {
		dividers[P] = 1
	}

	ans := 1
	for k, v := range dividers {
		if v/N > 0 {
			ans *= pow(k, v/N)
		}
	}
	fmt.Println(ans)
}

func pow(a, b int) (ret int) {
	ret = a
	for i := 0; i < b-1; i++ {
		ret *= a
	}
	return
}


Measured memory_bytes: 512
unittest
{
	assert( [ "4", "west", "east", "wait" ].parse.expand.solve == 3 );
	assert( [ "9", "different", "different", "different" ].parse.expand.solve == 0 );
	assert( [ "7", "zenkoku", "touitsu", "program" ].parse.expand.solve == 13 );
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	input.popFront;
	auto a = input.front;
	input.popFront;
	auto b = input.front;
	input.popFront;
	auto c = input.front;
	return tuple( a, b, c );
}

auto solve( string a, string b, string c )
{
	auto ans = 0L;
	foreach( ac, bc, cc; lockstep( a, b, c ) )
	{
		if(      ac != bc && bc != cc && cc != ac ) ans += 2;
		else if( ac != bc || bc != cc || cc != ac ) ans += 1;
	}
	return ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a,b,c;
int main()
{
	scanf("%d%d%d",&a,&b,&c);
	if((a==b&&b!=c)||(a==c&&c!=b)||(b==c&&c!=a)) printf("Yes");
	else printf("No");
	return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using Pair = pair<int, int>;
using Vec = vector<int>;
using Graph = vector<Vec>;

int		main(void)
{
	int n;
	cin >> n;
	Vec d(n);
	for (int i = 0; i < n; i++)
		cin >> d.at(i);
	int sum = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			sum += d.at(i) * d.at(j);
		}
	}
	cout << sum << endl;
}


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

// definition {{{ 1

// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)

#define Scll(x) scanf("%llu", &x)
#define Scll2(x,y) scanf("%llu%llu", &x, &y)
#define Scll3(x,y,z) scanf("%llu%llu%llu", &x, &y, &z)

#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2

// constants {{{ 2
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
// }}} 2

// systems {{{ 2
#define Rep(x,y) for(int x = 0; x < y; x++)
#define Repe(x,y,z) for(int x = z; x < y; x++)
// }}} 2

// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n");
// }}} 2

// }}} 1

int main() {

    int n;
    static int a[200002];
    ll X = 0;
    ll ans = INF * 10900012 + 3;

    Scd(n);
    Rep(i,n){
        Scd( a[i] );
        X += a[i];
    }

    for (int i = 0; i < n-1; i++){
        X-= a[i] * 2;
        ans = min<ll>( ans , abs(X) );
    }

    printf ("%lld\n", abs(ans));

    return 0;
}



Measured memory_bytes: 1024
def LIS(A):
    dp = deque([A[0]])
    for a in A[1:]:
        if a <= dp[0]:
            dp.appendleft(a)
        else:
            dp[bisect_left(dp, a)-1] = a
    return len(dp)

##################################################################################################################

import sys
input = sys.stdin.readline
from collections import deque
from bisect import bisect_left

N = int(input())

A = [int(input()) for _ in range(N)]

print(LIS(A))

Measured memory_bytes: 79404
n,k = map(int,input().split())
s = input()
x = len(s)
lst = [0]
ans = 0
if s[0] == "1" and s[x-1] == "0":
    s = s[::-1]
for i in range(1,x):
    if s[i-1] != s[i]:
        lst.append(i)
lst.append(x)
if s[0] == "0" and s[x-1] == "1":
    if 2*k >= len(lst):
        ans = x
    else:
        i = 1
        while i+2*k+1 <= len(lst)-1:
            ans = max(ans,lst[i+2*k+1]-lst[i])
            i += 2
        ans = max(ans,lst[2*k])
if s[0] == "0" and s[x-1] == "0":
    if 2*k >= len(lst):
        ans = x
    else:
        i = 1
        while i+2*k+1 <= len(lst)-1:
            ans = max(ans,lst[i+2*k+1]-lst[i])
            i += 2
        ans = max(ans,lst[2*k])
        ans = max(ans,x-lst[len(lst)-2*k-1])
if s[0] == "1" and s[x-1] == "1":
    if 2*k+1 >= len(lst):
        ans = x
    else:
        i = 0
        while i+2*k+1 <= len(lst)-1:
            ans = max(ans,lst[i+2*k+1]-lst[i])
            i += 2
print(ans)

Measured memory_bytes: 45680
from collections import Counter, deque, defaultdict


def main():
    n, x, y = map(int, input().split())
    v = defaultdict(list)
    for i in range(n):
        if i + 1 < n: v[i].append(i + 1)
        if i - 1 >= 0: v[i].append(i - 1)
    v[x - 1].append(y - 1)
    v[y - 1].append(x - 1)

    cnt = Counter()
    for start in range(n):
        dist = [-1] * n
        q = deque()
        q.append([start, 0])
        while q:
            c, d = q.popleft()
            for next in v[c]:
                if dist[next] == -1:
                    q.append([next, d + 1])
                    dist[next] = d + 1
        cnt += Counter(dist[start + 1:])

    for i in range(1, n):
        print(cnt[i])


if __name__ == '__main__':
    main()

Measured memory_bytes: 107356
#include<bits/stdc++.h>
#define ford(i,a,b) for(int i=(a);i>=b;i--)
#define rep1(i,a,b) for(int i=(a);(i)<=(b);(i)++)
#define rep(i,a,b) for(int i=(a);(i)<(b);(i)++)
#define ll long long
#define mpi map<int,int>
#define N 200005
#define pql priority_queue<ll>
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define str stringstream
using namespace std;
ll x,y,z,k;
vector<ll> ans,a(N),b(N),c(N);
int main() {
	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(rall(a)); sort(rall(b)); sort(rall(c));
	rep(i,0,x)
		rep(j,0,y)
			rep(l,0,z){
				if(i*j*l>k)break;
				ans.push_back(a[i]+b[j]+c[l]);
			}
	sort(rall(ans));
	rep(i,0,k)cout<<ans[i]<<"\n";
	return 0;
}


Measured memory_bytes: 39780
N = int(input())
P = []

for _ in range(N):
    P.append(list(map(int, input().split())))

dp = [[0 for _ in range(3)] for _ in range(10**5)]

for i in range(N):
    for j in range(3):
        for k in range(3):
            if k == j:
                continue
            dp[i][k] = max(dp[i][k], dp[i-1][j] + P[i][k])
            
print(max(dp[N-1]))

Measured memory_bytes: 47264
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

const ll dx[4] = {1, 0, -1, 0};
const ll dy[4] = {0, 1, 0, -1};
 
int main() {
    ll h, w;
    cin >> h >> w;
    
    vector<string> board(h);
    rep(i, h) {
        cin >> board[i];
    }

    rep(x, h) {
        rep(y, w) {
            if(board[x][y] == '.') {
                continue;
            }
            bool ok = false;
            rep(dir, 4) {
                ll nx = x + dx[dir];
                ll ny = y + dy[dir];
                if(nx < 0 || h <= nx || ny < 0 || w <= ny) {
                    continue;
                }
                if(board[nx][ny] == '#') {
                    ok = true;
                }
            }
            if(ok == false) {
                out("No");
                re0;
            }
        }
    }
    
    out("Yes");
    re0;
}

Measured memory_bytes: 256
import java.util.Scanner;
 
public class Main {
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
 
        long x = scan.nextInt();
 
        for (long a = -150; a < 150; a++) {
            for (long b = -150; b < 150; b++) {
                if (Math.pow(a, 5) - Math.pow(b, 5) == x) {
                    System.out.println(a + " " + b);
                    return;
                }
            }
        }
    }
}

Measured memory_bytes: 38936
#include <bits/stdc++.h>
#define REP(i,s,e) for(int i=(s); i<(e);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1e9;
const LL LLINF = 1e16;

int main(){
    fastcin();

    int n;
    cin >> n;
    string col_L, col_R;
    string buff;
    cout << "? ";
    rep(i, n) cout << i+1 << (i==n-1 ? "":" ");
    cout << endl;
    cin >> buff;
    assert(buff != "-1");
    col_L = buff;
    col_R = (col_L=="Red" ? "Blue" : "Red");

    int L = 0, R = n;
    while (abs(L - R) > 1) {
        int mid = (L + R) / 2;
        cout << "? ";
        REP(i, mid, n+mid) cout << i+1 << (i==n+mid-1 ? "":" ");
        cout << endl;
        cin >> buff;
        assert(buff != "-1");
        if(buff == col_L) L = mid;
        else R = mid;
    }
    R = L+n;
    vector<char> ans(2*n, '.');
    rep(i, 2*n){
        if(i == L) ans[i] = col_L[0];
        else if(i == R) ans[i] = col_R[0];
        else if(L < i && i < R){
            cout << "? " << i+1 << " ";
            REP(j, R+1, 2*n+L) cout << j%(2*n)+1 << (j==2*n+L-1 ? "":" ");
            cout << endl;
            cin >> buff;
            assert(buff != "-1");
            ans[i] = buff[0];
        }else{
            cout << "? " << i+1 << " ";
            REP(j, L+1, R) cout << j+1 << (j==R-1 ? "":" ");
            cout << endl;
            cin >> buff;
            assert(buff != "-1");
            ans[i] = buff[0];
        }
    }
    cout << "! ";
    repe(i, ans) cout << i;
    cout << endl;
}

Measured memory_bytes: 724
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    System.out.println(b-a==c-b ? "YES" : "NO");
  }
}


Measured memory_bytes: 35644
#include<bits/stdc++.h>
using namespace std;
int a[53],c,n,k,s;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);
for(int i=n;i>=1;i--){
s++;
if(s>k) break;
c+=a[i];}
cout<<c;}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define dump(x) cout << (x) << '\n';
typedef int64_t Int;
Int mod = 1e9+7;
Int INF = 1e9+18;

int main() {
    ios::sync_with_stdio(false);
    Int a, b, c;
    cin >> a >> b >> c;
    dump(a == b && b == c ? "Yes" : "No");
    return 0;
}

Measured memory_bytes: 256
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7

# 2^n mod (10^9+7)
s = pow(2, n, mod) - 1

x, y = 1, 1
for i in range(1, b + 1):
    x = x * (n - i + 1) % mod
    y = y * i % mod
    if i == a or i == b:
        s -= x * pow(y, mod - 2, mod)
        
print(s%mod)

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

#define INF 1e9
using namespace std;

#define REPR(i, n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

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

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

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

typedef long long ll;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }


int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> v(N+1, vector<int>());
    REP(i, M) {
        int a, b;
        cin >> a >> b;

        v[a].push_back(b);
    }

    // prepare for bfs
    queue<int> que;
    for (const auto &it:v[1]) {
        que.push(it);
    }

    // bfs?
    while(!que.empty()) {
        int relay_point = que.front(); que.pop();
        for (const auto &it:v[relay_point]) {
            if (it == N) {
                cout << "POSSIBLE" << endl;
                return 0;
            }
        }
    }
    cout << "IMPOSSIBLE" << endl;

    return 0;
}


Measured memory_bytes: 8824
#include<stdio.h>
#define N 250

typedef struct{
  int parent;
  int left;
  int right;
  int key;
}Node;


Node node[N];

int parent(int i){
  return i/2;
}
int left(int i){
  return 2*i;
}
int right(int i){
  return 2*i+1;
}

int main(){
  int i, j, n;
  scanf("%d", &n);
  for(i = 1;i < n+1;i++){
    scanf("%d", &node[i].key);
    if(i == 1) node[i].parent = -1;
    else node[i].parent = parent(i);
    if(2*i > n) node[i].left = node[i].right = -1;
    else{
      node[i].left = left(i);
      if(2*i+1 > n) node[i].right = -1;
      else node[i].right = right(i);
    }
  }
  for(i = 1;i < n+1;i++){
    printf("node %d: key = %d, ", i, node[i].key);
    if(node[i].parent != -1) printf("parent key = %d, ", node[node[i].parent].key);
    if(node[i].left != -1) printf("left key = %d, ", node[node[i].left].key);
    if(node[i].right != -1) printf("right key = %d, ", node[node[i].right].key);
    printf("\n");
  }
  return 0;
}

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

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = ReadArrayInt();
            var N = input[0];
            var D = input[1];
            var cnt = 0;
            var chk = 0;
            do
            {
                cnt++;
                chk += 1 + D * 2;
            } while (chk < N);

            Console.WriteLine(cnt++);
            Console.ReadLine();
        }

        static string Read() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Read()); }
        static long ReadLong() { return long.Parse(Read()); }
        static int[] ReadArrayInt() { return Read().Split(' ').Select(s => int.Parse(s)).ToArray(); }
        static long[] ReadArrayLong() { return Read().Split(' ').Select(s => long.Parse(s)).ToArray(); }
    }
}

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

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

const ll INF = 1LL << 60;

int main() {
    ll N;
    cin >> N;
    vector<ll> T(5);
    ll minpp = INF;
    for (int i = 0; i < 5; i++) {
        cin >> T[i];
        chmin(minpp, T[i]);
    }

    ll time = 5;
    ll delay = ceil((double)N / minpp) - 1;
    time += delay;
    cout << time << endl;

    return 0;
}

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

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

Measured memory_bytes: 256