akhauriyash/Code-Regression huggingface dataset:
#import math
#import bisect
#import numpy as np
#import itertools
#import copy
import sys

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    k, x = list(map(int,ipti().split()))
    minlim = x - (k-1)
    maxlim = x + (k-1)

    ans = [_ for _ in range(minlim, maxlim + 1)]
    print(*ans)

if __name__ == '__main__':
    main()

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

int main(){
  int N;
  cin  >> N;
  
  if(N == 1){
    cout << 0 << endl;
  }
  else{
    long ans;
    for(int i=0;i<N;i++){
      ans = ans + i;
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define mii         map<ll int,ll int>
#define msi         map<string,ll int>
#define mis         map<ll int, string>
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define mpi         map<pair<ll int,ll int>,ll int>
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define vii         vector<pair<ll int, ll int>>
#define vs          vector<string>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
//#define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
using namespace std;
#define N  1000000007 
#define MAXN   200005
int main()
{
ios_base::sync_with_stdio(false);
 cin.tie(0);
 cout.tie(0);
ll int n;
cin>>n;
vi a(n);
rep(i,0,n)
cin>>a[i];
ll int dp[n+1];
rep(i,0,n+1)
dp[i]=0;
dp[0]=0;
dp[1]=0;
dp[2]=abs(a[1]-a[0]);
rep(i,3,n+1)
{
dp[i]=min(dp[i-1]+abs(a[i-1]-a[i-2]),dp[i-2]+abs(a[i-1]-a[i-3]));
}
cout<<dp[n];
}


Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
#include<set>
#include<cstring>
using namespace std;

int main() {
  string s; cin >> s;
  int n = s.size();
  int z = 0;
  for(int i=0; i<n; i++){
    if(s[i] == '0') z++;
  }
  cout << n - (max(n-z, z)-min(n-z, z)) << endl;
  return 0;
}






//EOF


Measured memory_bytes: 512
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/
const int MOD = 1000000007;

const int MAX = 10000000;
int least_prime_factor[MAX + 1];
void osa_k_init(int num = MAX) {
  memset(least_prime_factor, -1, sizeof(least_prime_factor));
  vector<bool> is_prime(num + 1, true);
  least_prime_factor[0] = 0;
  least_prime_factor[1] = 1;
  is_prime[0] = false;
  is_prime[1] = false;
  FOR(i, 2, num + 1) if (is_prime[i]) {
    least_prime_factor[i] = i;
    for (int j = i * i; j <= num; j += i) {
      is_prime[j] = false;
      if (least_prime_factor[j] == -1) least_prime_factor[j] = i;
    }
  }
}

vector<pair<int, int> > osa_k(int num) {
  vector<pair<int, int> > res;
  while (num > 1) {
    int prime = least_prime_factor[num], exponent = 0;
    while (least_prime_factor[num] == prime) {
      ++exponent;
      num /= prime;
    }
    res.emplace_back(prime, exponent);
  }
  return res;
}

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n; cin >> n;
  osa_k_init(n);
  map<int, int> mp;
  FOR(i, 2, n + 1) {
    auto tmp = osa_k(i);
    for (auto a : tmp) mp[a.first] += a.second;
  }
  long long ans = 1;
  FOR(i, 2, n + 1) if (mp[i] > 0) (ans *= (mp[i] + 1)) %= MOD;
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 39424
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>



#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  string a,b,c;
  cin>>a>>b>>c;
  if(*a.rbegin()==*b.begin()&&*b.rbegin()==*c.begin())cout<<"YES"<<endl;
  else cout<<"NO"<<endl;

  return 0;

}


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

using namespace std;

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

int main(int argc, char const *argv[])
{
	int n;
	int nn,d;

	int maxx,maxy,minx,miny;

	while(1){
		cin>>n;
		if(n==0) break;

		vector<pair<int,int> > v;

		v.push_back(make_pair(0,0));

		for(int i1=1;i1<n;i1++){
			cin>>nn>>d;
			v.push_back(make_pair(v[nn].first+dx[d],v[nn].second+dy[d]));
		}

		maxx=-300;
		minx=300;
		maxy=-300;
		miny=300;
		for(int i1=0;i1<n;i1++){
			if(maxx<v[i1].first) maxx=v[i1].first;
			if(minx>v[i1].first) minx=v[i1].first;
			if(maxy<v[i1].second) maxy=v[i1].second;
			if(miny>v[i1].second) miny=v[i1].second;
		}
		cout<<maxx-minx+1<<" "<<maxy-miny+1<<endl;
	}
	return 0;
}

Measured memory_bytes: 1200
#include"bits/stdc++.h"
using namespace std;

#define REP(i,n) for(int i=0;i<(n);i++)
#define REPR(i,n) for(int i=(n)-1;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<(n);i++)
#define ALL(x) x.begin(),x.end()
#define ll long long
typedef pair<int,int> pii;

int W,H;
char A[22][22];
int dist[404][404];

const int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
void solve(){
	cin>>W>>H;
	if(W==0)exit(0);
	int sx=0,sy=0;
	vector<int>ps;
	REP(i,H){
		REP(j,W){
			cin>>A[i][j];
			if(A[i][j]=='o'){
				sx=i,sy=j;
			}
			if(A[i][j]=='*'){
				ps.push_back(i*W+j);
			}
		}
	}
	REP(i,H)REP(j,W){
		REP(x,H)REP(y,W){
			dist[i*W+j][x*W+y]=1e9;
		}
	}
	REP(i,H)REP(j,W){
		dist[i*W+j][i*W+j]=0;
	}
	REP(i,H){
		REP(j,W){
			if(A[i][j]=='x')continue;
			REP(k,4){
				int x=i+dx[k];
				int y=j+dy[k];
				if(x>=0&&x<H&&y>=0&&y<W&&A[x][y]!='x'){
					dist[i*W+j][x*W+y]=1;
				}
			}
		}
	}
	REP(k,H*W){
		REP(i,H*W){
			REP(j,H*W){
				dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
			}
		}
	}
	int M=ps.size();
	int perm[10];
	REP(i,M)perm[i]=i;
	ll ans = 1e9;
	REP(i,M){
		if(dist[sx*W+sy][ps[i]]>=1e9){
			cout<<-1<<endl;
			return;
		}
	}
	do{
		ll res = 0;
		res+=dist[sx*W+sy][ps[perm[0]]];
		REP(i,M-1){
			res+=dist[ps[perm[i]]][ps[perm[i+1]]];
			if(res>=ans)break;
		} 
		ans=min(ans,res);
	}while(next_permutation(perm,perm+M));
	if(ans<1e9){
		cout<<ans<<endl;
	}
	else{
		cout<<-1<<endl;
	}
}

signed main() {
	//test();
	while(true)solve();
}


Measured memory_bytes: 3688
import * as readline from "readline";

/* ここに処理を書く */
const op = (a: number, b: number, opId: number): number => {
  let res: number;
  switch (opId) {
    case 0:
      return a + b;
    case 1:
      return a - b;
    default:
      return -1;
  }
};
const printOp = (id: number): string => {
  return id === 0 ? "+" : "-";
};
const main = (args: any[]) => {
  const N = args[0];
  const A = Math.floor(N / 1000) % 10,
    B = Math.floor(N / 100) % 10,
    C = Math.floor(N / 10) % 10,
    D = Math.floor(N) % 10;
  // console.log(A, B, C, D);
  for (let op1 = 0; op1 < 2; op1++) {
    for (let op2 = 0; op2 < 2; op2++) {
      for (let op3 = 0; op3 < 2; op3++) {
        if (op(op(op(A, B, op1), C, op2), D, op3) === 7) {
          console.log(
            A + printOp(op1) + B + printOp(op2) + C + printOp(op3) + D + "=7"
          );
          return;
        }
      }
    }
  }
};

/* 標準入力処理 */
const stdin = (main: Function) => {
  const args: any[] = [];
  const reader = readline.createInterface({
    input: process.stdin,
    output: process.stdout
  });
  reader.on("close", function() {
    main(args);
  });
  reader.on("line", function(line: any) {
    if (line === "") {
      reader.close();
    }
    line.split(" ").forEach((arg: any) => {
      args.push(isNaN(arg) ? arg : Number(arg));
    });
  });
};
/* 実行 */
stdin(main);


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

int main(){

  while(1){
     int a, b;
     string op;
     cin>>a>>op>>b;
     if(op == "?") break;

     int ans;
     if(op == "+") ans = a + b;
     if(op == "-") ans = a - b;
     if(op == "*") ans = a * b;
     if(op == "/") ans = a / b;

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



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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  int bound = 0;
  vector<int> last(20);
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    for (int j = 0; j < 20; j++) {
      if ((x >> j) & 1) {
        bound = max(bound, last[j]);
        last[j] = i + 1;
      }
    }
    ans += i - bound + 1;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,c) for(int i=0;i<c;++i)
#define PI 3.14159265358979323846264338327950L
typedef unsigned long long uint64;
using namespace std;
using ll = long long;
int main(){
  int n;
  cin >> n;
  vector<int>a(n);
  rep(i,n){
    cin >> a[i];
  }
  for(int i= 0;i<n;i++){
    if((a[i]%2==0)&&(a[i]%3!=0&&a[i]%5!=0)){
      cout << "DENIED" << endl;
      return 0;
    }
  }
  cout << "APPROVED" << endl;
}


Measured memory_bytes: 3592
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int main(){
	long long a,b,c,d;
	while(scanf("%lld%lld%lld%lld",&a,&b,&c,&d)!=EOF){
		long long ans1 = a*b;
		long long ans2 = c*d;
		printf("%lld\n",max(ans1,ans2));
	}
		
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define UPD(x,y) (((x)+=(y))>=mo?(x)-=mo:233)
#define CLR(a,v) memset(a,v,sizeof(a))
using namespace std;
const int mo=1000000007;
int power(int x,int y){
	int s=1;
	for (;y;y/=2,x=1ll*x*x%mo)
		if (y&1) s=1ll*s*x%mo;
	return s;
}
const int N=105;
int a[N],mn[N][N];
int fxor[N][N];
int pre[N][N];
int suf[N][N];
int mx[N],g[N],n;
int main(){
	scanf("%d",&n); n++;
	For(i,2,n) scanf("%d",&a[i]);
	a[0]=a[1]=a[n+1]=a[n+2]=1;
	For(i,0,n+2) mn[i][i]=i;
	For(l,0,n+2) For(r,l+1,n+2)
		mn[l][r]=(a[r]<a[mn[l][r-1]]?r:mn[l][r-1]);
	For(i,1,n+2) fxor[i][i-1]=1;
	Rep(l,n+1,1) For(r,l,n+1){
		int dn=max(a[l-1],a[r+1]),md=mn[l][r];
		if (a[md]>=dn) fxor[l][r]=1ll*power(2,a[md]-dn)*fxor[l][md-1]%mo*fxor[md+1][r]%mo;
	}
	For(l,0,n+2){
		CLR(mx,0); mx[l]=a[l];
		For(i,l+1,n+2) mx[i]=min(a[i],mx[i-1]);
		int tmp=pre[l][l]=1,las=l;
		For(r,l+1,n+2){
			pre[l][r]=1ll*tmp*fxor[las+1][r-1]%mo;
			if (mx[r]>=a[r]) tmp=1ll*tmp*fxor[las+1][r-1]%mo,las=r;
		}
	}
	For(r,0,n+2){
		CLR(mx,0); mx[r]=a[r];
		Rep(i,r-1,0) mx[i]=min(a[i],mx[i+1]);
		int tmp=suf[r][r]=1,las=r;
		Rep(l,r-1,0){
			suf[l][r]=1ll*tmp*fxor[l+1][las-1]%mo;
			if (mx[l]>=a[l]) tmp=1ll*tmp*fxor[l+1][las-1]%mo,las=l;
		}
	}
	g[1]=1;
	For(i,2,n+2) For(j,1,i-1){
		int md=mn[j-1][i];
		UPD(g[i],1ll*g[j]*pre[j-1][md]%mo*suf[md][i]%mo);
	}
	printf("%d\n",1ll*g[n+2]*500000004ll%mo);
}

Measured memory_bytes: 384
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

typedef long long ll;
constexpr double PI = 3.141592653589793;

using namespace std;
//    cout << setprecision(20) << ans << "\n";

int main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        if (a % 2 == 0)
        {
            if (a % 3 != 0 && a % 5 != 0)
            {
                cout << "DENIED"
                     << "\n";
                return 0;
            }
        }
    }
    cout << "APPROVED"
         << "\n";

    return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
di = {}
for i in a:
    if i in di:
        di[i] += 1
    else:
        di[i] = 1
k = list(di.keys())
v = list(di.values())
if n%3!=0 and len(di)>1:
    print('No')
elif len(di)==3 and v[0]==v[1]==v[2] and k[0]^k[1]^k[2]==0:
    print('Yes')
elif len(di)==2 and ((v[0]<v[1] and v[0]==n//3 and k[0]==0) or (v[0]>v[1] and v[1]==n//3 and k[1]==0)):
    print('Yes')
elif len(di)==1 and k[0]==0:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 14212
#include <stdio.h>
#include <math.h>
#include <string.h>
int max(int a,int b)
{
    if (a>b) {
        return a;
    }
    else return b;
}
int main()
{
    int a,b,c,d;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    printf("%d",max(a*b, c*d));
    return 0;
}

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

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

void Main(){
  int N; cin >> N;
  vector<int> B(N-1);
  rep(i, 0, N-1) cin >> B[i];
  int res = 0;
  rep(i, 0, N){
    int A = 100000000;
    if(i < N - 1)A = min(A, B[i]);
    if(i > 0) A = min(A, B[i - 1]);
    res += A;
  }
  cout << res << endl;
}

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

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  //cout << std::fixed << std::setprecision(15);

  Main();
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
# c-abc114.py
import itertools
# input
a = input()
N = int(a)
e = len(a)
c = 0
for i in range(3, e):
    o = itertools.product(['3', '5', '7'], repeat=i)
    for j in o:
        if all(j.count(k) > 0 for k in '357') == True:
            c += 1
l = itertools.product(['3', '5', '7'], repeat=e)
for m in l:
    if all(m.count(k) > 0 for k in '357') == True and int(''.join(m)) <= N:
        c += 1
print(c)


Measured memory_bytes: 3064
H,W = map(int,input().split())
S = []
for i in range(H):
    s = input().split()
    S.append(s)
for i in range(H):
    for j in range(W):
        if S[i][j]=="snuke":
            a=[chr(65+j),i+1]
            print(*a,sep="")


Measured memory_bytes: 3060
{-# OPTIONS_GHC -fno-warn-type-defaults #-}
module Main where

import Data.List

main :: IO ()
main = readLn >>= print . (*1000) . yamikin 100 1.05

yamikin :: Int -- ^ ?????¬?????????????????????
        -> Double -- ^ ??????
        -> Int -- ^ ??±
        -> Int -- ^ ???????????????????????????
yamikin c r n = foldl' f c [1..n]
  where
    f b _
        | d > 0     = m + 1
        | otherwise = m
      where
        (m,d) = properFraction $ fromIntegral b * r

Measured memory_bytes: 3800
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define mod 1000000007
#define N 1000005
using namespace std;

typedef long long ll;

int n, m, kac, bas[N], son[N], fen[N];
vector < int > g[N];

void up(int x, int y){
	for(; x < N; x += x&-x)
		fen[x] += y;
}

int qu(int x){
	int ans = 0;
	for(; x > 0; x -= x&-x)
		ans += fen[x];
	return ans;
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d %d",&n ,&m);
	for(int i = 1; i <= n; i++){
		scanf("%d %d",bas + i, son + i);
		g[son[i] - bas[i] + 1].pb(i);
	}
	kac = n;
	for(int i = 1; i <= m; i++){
		int ans = kac;
		for(int j = i; j <= m; j += i)
			ans += qu(j);
		printf("%d\n", ans);
		for(int j = 0; j < g[i].size(); j++){
			int k = g[i][j];
			up(bas[k], 1);
			up(son[k] + 1, -1);
			kac--;
		}
	}
	return 0;
}

Measured memory_bytes: 34688
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const int64_t INF = 1LL << 60;

long long a[100010][3];
long long dp[100010][3];

int main() {
    int N; cin >> N;
    for (int i = 0; i < N; ++i) for (int j = 0; j < 3; ++j) cin >> a[i][j];

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                if (j == k) continue;
                chmax(dp[i + 1][k], dp[i][j] + a[i][k]);
            }
        }
    }

    long long res = 0;
    for (int j = 0; j < 3; ++j) chmax(res, dp[N][j]);
    cout << res << endl;
}

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

int main(){
  int a,b,c,k,ans=0;cin>>a>>b>>c>>k;
  if(k<=a) ans=k;
  else if(k<=a+b) ans=a;
  else ans=a-(k-a-b);

  cout<<ans;
}

Measured memory_bytes: 3624
#include<iostream>
#include<cstring>
#include<cstdio>
#define lint long long
#define LOG 17
#define maxK 10
#define V 1<<LOG
#define N 42
#define mod 1000000007
using namespace std;
inline int updv(int x,int p) { return x|(1<<(p-1)); }
int dp[N][V],can[V];
int fast_pow(int x,int k)
{
    int ans=1;
    while(k)
    {
        if(k&1) ans=(lint)ans*x%mod;
        x=(lint)x*x%mod,k>>=1;
    }
    return ans;
}
int show(int x)
{
    for(int i=1;i<=LOG;i++)
        printf("%d",(x&(1<<(i-1)))>>(i-1));
    cout<<endl;
    return 0;
}
int main()
{
    int n,x,y,z;scanf("%d%d%d%d",&n,&x,&y,&z);
    int all=(1<<LOG)-1,v=0,ans=0;dp[0][0]=1;
    v=updv(v,x+y+z),v=updv(v,y+z),v=updv(v,z);
    for(int i=0;i<=all;i++) can[i]=((i&v)!=v);
    for(int i=0,x;i<n;i++)
        for(int j=0;j<=all;j++)
            if(can[j]&&(x=dp[i][j]))
                for(int k=1;k<=maxK;k++)
                    (dp[i+1][all&updv(j<<k,k)]+=x)%=mod;
    for(int i=1;i<=all;i++)
        if(can[i]) (ans+=dp[n][i])%=mod;
    printf("%d\n",(fast_pow(10,n)-ans+mod)%mod);
    return 0;
}

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



int main() {
    int n;
    cin >> n;
    
    vector<double> v(n);
    rep(i,n) {
        cin >> v[i];
    }
    
    sort(v.begin(),v.end());
    
    double ans = v[0];
    for(int i = 1; i < n; i++) {
        ans = (ans + v[i]) / 2;
    }
    
    cout << ans << endl;
    
    
    return 0;
}


Measured memory_bytes: 3836
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _0025
{
    class Program
    {
        static void Main(string[] args)
        {
            Game game = new Game();
            string str;
            while ((str = Console.ReadLine()) != null)
            {
                string[] a = str.Split();
                string[] b = Console.ReadLine().Split();
                //game.a = str.Split().Select(int.Parse).ToArray();
                //game.b = Console.ReadLine().Split().Select(int.Parse).ToArray();
                int hitPoint = 0;
                int blowPoint = 0;
                for (int i = 0; i < 4; ++i)
                {
                    if (a[i]==b[i])
                    {
                        hitPoint++;
                    }
                }
                for(int i = 0; i < 4; ++i)
                {
                    if (b.Contains(a[i]))
                    {
                        blowPoint++;
                    }
                }
                Console.WriteLine("{0} {1}", hitPoint, blowPoint-hitPoint);
            }
        }
    }
    class Game
    {
        internal int[] a = new int[4];
        internal int[] b = new int[4];
        List<int> hitList = new List<int>();
        internal bool Hit(int i)
        {
            if (a[i] == b[i])
            {
                hitList.Add(a[i]);
                return true;
            }
            else
            {
                return false;
            }
        }
        internal bool Blow(int i)
        {
            if (b.Contains(a[i])&&!(hitList.Contains(a[i])))
            {
                return true;
            }
            else
            {
                return false;
            }
        }

    }
}



Measured memory_bytes: 13912
import sys
sys.setrecursionlimit(2147483647)

n,m = map(int,input().split())
a = n - 1
b = m - 1
ans = 0

if m <= 1:
    ans = n*a/2
else:
    ans = n*a/2 + m*b/2

print(str(int(ans)))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define pi 3.141592653589793238
#define int long long
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// mt19937 gen_rand_int(chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 gen_rand_ll(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

long long power(long long a, long long b,long long m) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a %m;
        a = a * a %m;
        b >>= 1;
    }
    return res;
}


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

#ifndef ONLINE_JUDGE
    if(fopen("INPUT.txt","r"))
    {
    freopen ("INPUT.txt" , "r" , stdin);
    freopen ("OUTPUT.txt" , "w" , stdout);
    }
#endif  


    int n;
    cin>>n;
    pair<int,int>p[n+1];
    for(int i=1;i<=n;i++)
        cin>>p[i].first>>p[i].second;
    int mm[n+1]={0};
    vector<pair<int,int> >v;
    for(int i=1;i<=n;i++)
    {
        v.push_back({p[i].first,i});
        v.push_back({p[i].second,i});
    }
    sort(v.begin(),v.end());
    int tot=0;
    bool flag=false;
    for(int i=0;i<n;i++)
    {
        mm[v[i].second]++;
        tot+=v[i].first;
        if(mm[v[i].second]>1)
            flag=true;
    }
    if(flag)
    {
        cout<<tot;
    }
    else
    {
        int x=0;
        int mn=1e17;
        for(int i=1;i<=n;i++)
            x+=p[i].first;
        mn=min(mn,x);
        x=0;
        for(int i=1;i<=n;i++)
            x+=p[i].second;
        mn=min(mn,x);
        for(int i=1;i<=n;i++)
        {
            tot+=max(p[i].first,p[i].second);
            if(v[n-1].second==i)
            {
                tot-=v[n-2].first;
                mn=min(mn,tot);
                tot+=v[n-2].first;
                tot-=max(p[i].first,p[i].second);
                continue;
            }
            tot-=v[n-1].first;
            mn=min(mn,tot);
            tot+=v[n-1].first;
            tot-=max(p[i].first,p[i].second);
        }
        cout<<mn;
    }
    


} 
    

Measured memory_bytes: 9760
// Union Find 版
package main

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

func find(parent []int, i int) int {
	if parent[i] == -1 {
		return i
	}
	parent[i] = find(parent, parent[i])
	return parent[i]
}

func unite(parent []int, i, j int) {
	i = find(parent, i)
	j = find(parent, j)
	if i == j {
		return
	}
	parent[i] = j
}

func main() {
	n := readInt()
	k := readInt()
	l := readInt()

	roads := make([]int, n)
	rails := make([]int, n)
	for i := 0; i < n; i++ {
		roads[i] = -1
		rails[i] = -1
	}

	for i := 0; i < k; i++ {
		p := readInt()
		q := readInt()
		unite(roads, p-1, q-1)
	}

	for i := 0; i < l; i++ {
		p := readInt()
		q := readInt()
		unite(rails, p-1, q-1)
	}

	d := map[int]int{}
	for i := 0; i < n; i++ {
		d[2000001*find(roads, i)+find(rails, i)]++
	}

	result := make([]int, n)
	for i := 0; i < n; i++ {
		result[i] = d[2000001*find(roads, i)+find(rails, i)]
	}
	printIntln(result...)
}

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
}

func printIntln(v ...int) {
	b := make([]byte, 0, 4096)
	for i := 0; i < len(v)-1; i++ {
		b = append(b, strconv.Itoa(v[i])...)
		b = append(b, " "...)
	}
	b = append(b, strconv.Itoa(v[len(v)-1])...)
	fmt.Println(string(b))
}


Measured memory_bytes: 20224
L = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(L[int(input())-1])

Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define r(i,n) for(int i=0;i<n;i++)
set<string> a;
int main(){
	int n;
	cin>>n;
	string s[n],t;
	r(i,n)cin>>s[i];
	r(i,6)r(j,n)r(k,s[j].size())
		if(k+i<=s[j].size())a.insert(s[j].substr(k,i));
	r(i,27)r(j,27)r(k,27)r(l,26){
		t="";
		if(i)t+='a'-1+i;
		if(j)t+='a'-1+j;
		if(k)t+='a'-1+k;
		t+='a'+l;
		if(!a.count(t))cout<<t<<endl,exit(0);
	}
}

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

int main(){
vector<int> num(102,0);
for(int i = 0;i <=101;i++) num[i] = i;

int x, n, t;
cin >> n >> x ;

    if(x != 0){
for(int i = 0; i < x; i++){
  cin >> t;
  num[t] = 1000;
}
  bool judge = true;
    int dn = n - 1;
    int da = n + 1;
    while(judge){
            if(num[n] != 1000){
            dn = n;
            da = 1000;
            judge = false;     
        }
    else if(num[dn] != 1000 || num[da] != 1000){
            dn = num[dn];
            da = num[da];
            judge = false;        
        }
      else{
            dn--;
            da++;
                }
}
        cout << min(dn,da);
        }
        else cout << n;
}


Measured memory_bytes: 3576
s=gets.chomp.split("").map{|s| s.to_i}
a,b=0,0

for i in 0..s.size-1
  if (s[i]==0 && i%2==0) || (s[i]==1 && i%2==1)
    a+=1
  end

  if (s[i]==0 && i%2==1) || (s[i]==1 && i%2==0)
    b+=1
  end
end

if a<b
  puts a
else
  puts b
end

Measured memory_bytes: 7676
# include <bits/stdc++.h>
# define int      long long
# define all(vc)   vc.begin(),vc.end()
# define all2(vc)  vc.rbegin(),vc.rend()
# define pb        push_back
# define vec       vector
# define fi        first 
# pragma GCC optimize "-O3"
# define se        second
# define speed     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
# define time      cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"

using namespace std; 
map <int, int> mp;
void solve(){
    int n = 0, m;
    cin >> n;
    vec <int> used(1000, 0);
    for (int i = -500; i < 500; ++i)
    {
        int A = i * i * i * i * i;
        for (int j = -500; j < 500; ++j)
        {
            int B = j * j * j * j * j;
            if( A - B == n){
                cout << i << ' ' << j;
                return;
            }
        }
    }

}
int32_t main(){
    speed;
    int T = 1;
    //cin >> T;
    while( T-- ){
         solve();
         cout<<'\n';
    }
    time;
}
 

Measured memory_bytes: 3856
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
#include<iterator>
#include<list>

using namespace std;

typedef  long long int lint;

#define rep(i, n) for (lint i = 0; i < n; i++)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)
#define mp make_pair
#define IP pair<int,int>
#define enld endl

#define SIZE 1000

lint power(lint a, lint b) {
	lint ans = a * a * a * a * a;
	return ans;
}

bool isOK(lint A, lint B,lint X) {
	if (power(A,5)-power(B,5)<=X) return true;
	else return false;
}

// 汎用的な二分探索のテンプレ
lint binary_search(lint A,lint X) {
	lint left = -1*SIZE; //「index = 0」が条件を満たすこともあるので、初期値は -1
	lint right = SIZE; // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

	/* どんな二分探索でもここの書き方を変えずにできる！ */
	while (right - left > 1) {
		lint mid = left + (right - left) / 2;

		if (isOK(A,mid, X)) right = mid;
		else left = mid;
	}

	/* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
	return right;
}

int main() {
	lint X;
	cin >> X;
	for (lint A = -1*SIZE; A <= SIZE; A++) {
		//cout << A << '!';
		if (power(A, 5) - power(binary_search(A, X), 5) == X) {
			cout << A << ' ' << binary_search(A, X) << endl;
			return 0;
		}
	}
 }

Measured memory_bytes: 3636
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
#include <atcoder/mincostflow>
using namespace std;
#define INF ((1<<30)-1)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()




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

	int n, m;
	cin >> n >> m;
	atcoder::mcf_graph<int, long long> g(n * m + 2);

	string f[50];
	rep(i, n)cin >> f[i];

	int s = n * m;
	int t = s + 1;

	int init = 0;
	rep(i, n)rep(j,m) {
		int u = i * m + j;
		if (f[i][j] == 'o') {
			g.add_edge(s, u, 1, 0);
			init += n + m - i - j;;
		}
		g.add_edge(u, t, 1, n + m - i - j);

		if (i + 1 < n && f[i][j] != '#' && f[i + 1][j] != '#') {
			g.add_edge(u, (i + 1) * m + j, INF, 0);
		}
		if (j + 1 < m && f[i][j] != '#' && f[i][j + 1] != '#') {
			g.add_edge(u, (i)*m + j + 1, INF, 0);
		}
	}

	int cost = g.flow(s, t).second;
	cout << init - cost << endl;



	return 0;
}


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

int main (){
  	ll N;
      cin>>N;
    vector<ll> A(N), B(N);
    ll Sum=0;
    for(int i=0; i<N; i++){
        cin>>A.at(i);
        if(i==0){
            B.at(i)=A.at(i);
        }
        else{
            B.at(i)=B.at(i-1)+A.at(i);
        }
        Sum += A.at(i);
    }
    ll Half=Sum / 2;
    ll HalfNum;
    for(int i=0; i<N; i++){
        if(B.at(i)>=Half){
            HalfNum=i;
            break;
        }
    }
    //if(Sum%2==0){
    cout<<min(Sum-2*B.at(HalfNum-1),2*B.at(HalfNum)-Sum)<<endl;
    //}
    //else{

   // }


}

Measured memory_bytes: 3328
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Linq;
using System.Diagnostics;
using System.Globalization;
using static System.Console;
using static System.Math;


namespace templete
{
    class abc100_a
    {
        static void Main(string[] args)
        {
            int[] input = ReadLine().Split().Select(int.Parse).ToArray();
            if(input[0] <= 8 && input[1] <= 8){
                WriteLine("Yay!");
            }else{
                WriteLine(":(");
            }
        }

        static void Swap<T>(ref T lhs, ref T rhs)
        {
            T temp;
            temp = lhs;
            lhs = rhs;
            rhs = temp;
        }
    }
}

Measured memory_bytes: 13268
import scala.io.StdIn.readLine


object Main extends App {
def solve(): Unit = {
  val s = readLine.split(" ").map(x => x.toInt)
  var a = s(0)
  val b = s(1)
  var c = s(2)
  val d = s(3)
  while (true) {
    c -= b
    if (c <= 0) {
      println("Yes")
      return
    }
    a -= d
    if (a <= 0) {
      println("No")
      return
    }
  }
}
  solve()
}


Measured memory_bytes: 54600
#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>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
	int n, m; cin>>n>>m;
	int h[100010];
	for(int i=0; i<n; i++) cin>>h[i];
	vector<int> g[100010];
	for(int i=0; i<m; i++){
		int a, b; cin>>a>>b;
		a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	int ans=0;
	for(int i=0; i<n; i++){
		int mx=0;
		for(auto j:g[i]){
			mx=max(mx, h[j]);
		}
		if(h[i]>mx) ans++;
	}
	cout<<ans<<endl;
	return 0;
}


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

int main()
{
	int count = 0;
	string S;
	
	cin >> S;
	
	for (int i = 1; i < S.length(); i++) {
		if (S[i] == S[i - 1]) {
			if (S[i] == '0') {
				S[i] = '1';
			}
			else {
				S[i] = '0';
			}
			
			count++;
		}
	}
	
	cout << count << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> pii;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i))
#define mat(type, c, m, n) vector<vector<type>> c(m, vector<type>(n));for(auto& r:c)for(auto& i:r)cin>>i;
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a), i##_len=(n); i>i##_len; --i)
#define each(x,y) for(auto &(x):(y))
#define var(type, ...)type __VA_ARGS__;Scan(__VA_ARGS__);
template<typename T> void Scan(T& t) { cin >> t; }
template<typename First, typename...Rest>void Scan(First& first, Rest&...rest) { cin >> first; Scan(rest...); }
#define vec(type, c, n) vector<type> c(n);for(auto& i:c) cin>>i;
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
#define em emplace
#define pb pop_back
#define fi first
#define se second
#define get(a, i) get<i>(a)
#define bit_count __builtin_popcount
#define mt make_tuple
inline string zero(int a,string s,char c='0'){return string(a-len(s),c)+s;}
inline string zero(int a,int t,char c='0'){return zero(a, to_string(t), c);}
inline string zero(int a,ll t,char c='0'){return zero(a, to_string(t), c);}
#define mini min_element
#define maxi max_element
#define sum accumulate
#define chmax(a,b) if(a<b)a=b
#define chmin(a,b) if(a>b)a=b
template <class T> inline void print(T t){cout << t << '\n';}
template <class H, class... T> inline void print(H h, T... t){cout << h << " ";print(t...);}
#define MAX int(110)
ll V[int(1e6)];
void solve() {
	var(int, n, W);
	fill(V, V + W, -1);
	V[0] = 0;
	ll w, v;
	rep(i, 0, n) {
		cin >> w >> v;
		rrep(j, W - 1, -1) {
			if (V[j] != -1) {
				chmax(V[j + w], V[j] + v);
			}
		}
	}
	print(*maxi(V, V + W + 1));
}
int main() {
	solve();
	return 0;
}


Measured memory_bytes: 1792
a = 'abcdefghijklmnopqrstuvwxyz'
n = int(input())
r = 26
d = 1
while n-r > 0:
    n -= r
    r *= 26
    d += 1
n -= 1
name = ''
for i in range(d):
    if n >= 26:
        name = a[n % 26]+name
        n //= 26
    elif n > 0:
        name = a[n]+name
        n = 0
    else:
        name = a[n]+name
print(name)

Measured memory_bytes: 9032
#include <iostream>
using namespace std;
int n,l,a,b,ans;
int main(void){
    cin>>n>>l;
    a=l,b=n+l-1;
    for(int i=a;i<=b;i++){
        ans+=i;
    }
    if(a>0&&b>0)ans-=a;
    if(a<0&&b<0)ans-=b;
    cout<<ans<<endl;
}


Measured memory_bytes: 256
N = int(input())
j = 0
start = 0
ans = 0
number_list = list(map(int,input().split()))
after_l = []
B = []
for i in range(N):
    for i in range(N):
        if number_list[i] == 0:
            if B != []:
                after_l.append(B)
                B=[]
            after_l.append([0])
        else:
            B.append(number_list[i])
    if B != []:
        after_l.append(B)
    for i in range(len(after_l)):
        C = after_l[i]
        C = min(C)
        ans += C
        after_l[i] = list(map(lambda x:x-C,after_l[i]))
    number_list = sum(after_l,[])
    after_l = []
    B = []
print(ans)

Measured memory_bytes: 3064
import numpy as np
N = int(input())
l = list(map(int, input().split()))


L = [l]
cnt = 0
while L:

    l = L.pop()
    if len(l) == 0:
        pass
    elif len(l) == 1:
        cnt += l[0]
    else:
        min_l = min(l)
        l = [s for s in map(lambda x: x-min_l, l)]
        cnt += min_l
        len_l = len(l)
        i = 0
        temp = []
        while i != len_l:

            if l[i] != 0:
                temp.append(l[i])
            else:
                L.append(temp)
                temp = []
            i += 1
        if len(temp) != 0:
            L.append(temp)

print(cnt)


Measured memory_bytes: 12672
/*
  Author - KISHAN TIWARI
  Dream bigger. Do bigger.
  Wake up with determination. Go to bed with satisfaction.
*/
//Sometimes later becomes never. Do it now.
#include<bits/stdc++.h>
using namespace std;
#define ll           long long
#define f(i,a,b)     for(ll i=a;i<b;i++)
#define mod          1000000007
#define fi           first
#define se           second
#define pa           pair <ll,ll>
#define mp           make_pair
#define pb           push_back
#define ve           vector<ll>
#define vep          vector< pa >
#define all(a)       a.begin(), a.end()
#define sz(x)        (ll)x.size()
#define c(t)         cout<<t<<"\n"
using namespace std;
vector<ll> adj[200005];
bool vis[200005];
static ll  co=0;
void dfs(ll s)
{
    vis[s]=1;
    for(ll i=0;i<adj[s].size();i++)
    {
        if(!vis[adj[s][i]])
        {
           dfs(adj[s][i]);
           co++;
        }
    }
}
void solve()
{
ll n,m;
cin>>n>>m;
f(i,0,m)
{
    ll u,v;
    cin>>u>>v;
    adj[u].pb(v);
    adj[v].pb(u);
}
memset(vis,0,sizeof(vis));
ll ma=-mod;
f(i,1,n+1)
{
    if(!vis[i])
    {   dfs(i);
        ma=max(ma,co);
        co=0;
    }
}
c(ma+1);
}
int main()
{
    ios::sync_with_stdio(true);
    /*#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif*/
    cin.tie(0);
    cout.tie(0);
    ll t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
return 0;
}


Measured memory_bytes: 20952
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll  long long
#define pb push_back
#define po pop_back
#define mp make_pair
#define ff first
#define ss second
int m(int x)
{
  if(x==1)
  {
    return 1;
  }
  else if(x>1)
  {
    return 2*m(x/2) +1 ;
  }
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  int h,n=0;
  cin>>h;
  n=m(h);
  cout<<n;
  return 0;
}
    
    

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
const int N=2e4+5;
int n,idx[N<<1],pos[N<<1],val[N<<1],org[N<<1];

inline int nxi(FILE *fd=stdin){
	int x=0;
	char c;
	while((c=fgetc(fd))>'9'||c<'0');
	while(x=x*10-48+c,(c=fgetc(fd))>='0'&&c<='9');
	return x;
}

inline bool cmp_org(const int a,const int b){
	return org[a]<org[b];
}

template <class T> inline void abs(const T x){
	return x<0?-x:x;
}

template <class T> inline void apn(T &x,const T y){
	x>y?x=y:0;
}

namespace G{
	int cnd,cscc,cnt,fir[N*6],bel[N*6],dfn[N*6],low[N*6];
	struct edge{
		int to,nx;
	}eg[N*36];

	void clear(){
		cnt=cscc=cnd=0;
		memset(fir,0,(n+1)*6*sizeof(int));
		memset(bel,0,(n+1)*6*sizeof(int));
		memset(dfn,0,(n+1)*6*sizeof(int));
	}

	inline void add(const int a,const int b){
		//printf("add: %d -> %d\n",a,b);
		eg[++cnt]=(edge){b,fir[a]};
		fir[a]=cnt;
	}

	void tarjan(const int x){
		static int top,stk[N*6];
		dfn[x]=low[x]=++cnd;
		stk[++top]=x;
		for(int i=fir[x]; i; i=eg[i].nx){
			const int y=eg[i].to;
			if(!dfn[y]) tarjan(y);
			if(!bel[y]) apn(low[x],low[y]);
		}
		if(dfn[x]!=low[x]) return;
		++cscc;
		for(int i=stk[top--]; ; i=stk[top--]){
			bel[i]=cscc;
			if(i==x) break;
		}
	}
}

namespace T{
	int x,y,v;
	inline int idx(const int l,const int r){
		return (l+r)|(l!=r);
	}

	void build(const int l,const int r){
		if(l==r) return;
		const int k=idx(l,r),mid=(l+r)>>1;
		G::add(k+(n<<1),idx(l,mid)+(n<<1));
		G::add(k+(n<<1),idx(mid+1,r)+(n<<1));
		build(l,mid);
		build(mid+1,r);
	}

	void lnk_t(const int l,const int r){
		if(l>=x&&r<=y){
			G::add(v,idx(l,r)+(n<<1));
			return;
		}
		const int mid=(l+r)>>1;
		if(x<=mid) lnk_t(l,mid);
		if(y>mid) lnk_t(mid+1,r);
	}

	inline void lnk(const int x,const int l,const int r){
		T::x=l,T::y=r,T::v=x;
		lnk_t(1,(n<<1));
	}
}

bool jdg(const int tgt){
	G::clear();
	T::build(1,n<<1);
	for(int i=1; i<n<<1; i+=2){
		const int p1=pos[i],p2=pos[i+1];
		G::add(T::idx(p1,p1)+(n<<1),p2);
		G::add(T::idx(p2,p2)+(n<<1),p1);
	}
	for(int i=1; i<=n<<1; ++i){
		const int l=std::lower_bound(val+1,val+i+1,val[i]-tgt+1)-val;
		if(l<i) T::lnk(i,l,i-1);
		const int r=std::upper_bound(val+i,val+(n<<1)+1,val[i]+tgt-1)-val-1;
		if(r>i) T::lnk(i,i+1,r);
	}
	for(int i=1; i<=n<<1; ++i){
		if(!G::bel[i]) G::tarjan(i);
	}
	for(int i=1; i<n<<1; i+=2){
		if(G::bel[pos[i]]==G::bel[pos[i+1]]) return 0;
	}
	return 1;
}

int solve(){
	int l=0,r=1e9,mid;
	while(l!=r){
		mid=(l+r+1)>>1;
		if(jdg(mid)) l=mid;
		else r=mid-1;
	}
	return l;
}

int main(){
	n=nxi();
	for(int i=1; i<=n; ++i){
		org[(i<<1)-1]=nxi(),org[i<<1]=nxi();
	}
	for(int i=1; i<=n<<1; ++i){
		idx[i]=i;
	}
	std::sort(idx+1,idx+(n<<1)+1,cmp_org);
	for(int i=1; i<=n<<1; ++i){
		pos[idx[i]]=i;
		val[i]=org[idx[i]];
	}
	printf("%d\n",solve());
	return 0;
}


Measured memory_bytes: 10880
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    n, m, l = LI()
    dist = [[inf] * n for i in range(n)]

    for _ in range(m):
        a, b, c = LI_()
        c += 1
        if c > l:
            continue
        dist[a][b] = c
        dist[b][a] = c

    supply = [[n] * n for i in range(n)]
    for k in range(n):
        distk = dist[k]
        for i in range(n):
            if i == k:
                continue
            disti = dist[i]
            distik = dist[i][k]
            for j in range(i + 1, n):
                if distik + distk[j] < disti[j]:
                    disti[j] = distik + distk[j]
                    dist[j][i] = disti[j]

    lis = [[] for i in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if dist[i][j] <= l:
                supply[i][j] = 0
                supply[j][i] = 0
                lis[i].append(j)
                lis[j].append(i)

    for i in range(n):
        q = []
        for k in lis[i]:
            heappush(q, (0, k))
        supplyi = supply[i]

        while q:
            time, p = heappop(q)
            for k in lis[p]:
                if supplyi[k] > time + 1:
                    supplyi[k] = time + 1
                    heappush(q, (time + 1, k))

    q = II()
    for _ in range(q):
        s, t = LI_()
        if dist[s][t] == inf:
            print(-1)
            continue
        else:
            print(supply[s][t])
    return


#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    E()


Measured memory_bytes: 82140
#include<bits/stdc++.h>
using namespace std;
const int N=100000;
int a[N+1],b[N+1],c[N+1];
int dp1[N+1],dp2[N+1],dp3[N+1];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>c[i];
	for(int i=1;i<=n;i++)
		dp1[i]=max(dp2[i-1],dp3[i-1])+a[i],
		dp2[i]=max(dp1[i-1],dp3[i-1])+b[i],
		dp3[i]=max(dp1[i-1],dp2[i-1])+c[i];
	cout<<max(max(dp1[n],dp2[n]),dp3[n]);
	return 0;
}
/*1
3
10 40 70
20 50 80
30 60 90
*/
/*2
1
100 10 1
*/
/*3
7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1
*/

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

#define fo(i, n) for(ll i = 0; i < n; i++)
#define endl "\n"
#define of(i, n) for(ll i = n - 1; i >= 0; i--)
#define ll long long
#define vec vector<ll>
#define fio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define tr(container, it) \
for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)


ll mod= 1e9+7;

#define umap unordered_map

string t;

ll sub(string s)
{
    ll l=0,h=s.length();
    ll j=0;
    for (int i=0; i<s.length()&&j<t.length(); i++)
       if (t[j] == s[i])
         j++;

    return (j==t.length());
}

ll check(ll n, string s)
{
    ll l,h;
    l=0;h=n-1;
    while(h<s.length()){
        if(sub(s.substr(l,h))) return 1;
        l++;h++;
    }
    return 0;
}

ll ab(ll x)
{
    if(x<0) x*=-1;
    return x;
}

int main()
{
    fio;
    ll n,w;
    cin>>n>>w;
    ll dp[n+1][w+1];
    int wt[n],v[n];
    fo(i,n) cin>>wt[i]>>v[i];

    fo(i,n+1)
    {
        fo(j,w+1)
        {
            if(i==0 || j==0) dp[i][j]=0;
            else if(wt[i-1]<=j)
            {
                dp[i][j] = max(v[i-1] + dp[i-1][j-wt[i-1]], dp[i-1][j]);
            }
            else dp[i][j]  = dp[i-1][j];

        }
    }
    cout<<dp[n][w]<<endl;
}






Measured memory_bytes: 79232
import Foundation
let line = readLine()!.components(separatedBy: " ").map { Int($0)! }
let N = line[0]
let K = line[1]
let p = readLine()!.components(separatedBy: " ").map { Int($0)! }.sorted()

var minTotal = 0
for i in 0..<K {
    minTotal += p[i]
}
print(minTotal)


Measured memory_bytes: 14304
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>	// upper_bound(A, A+N, num), lower_bound(A, A+N, num)
#include <functional>
#include <string>
#include <sstream>
#include <complex>
#include <vector>		// V[i],  push_back(x), pop_back(), insert(index, x), erase(index), sort(v.begin(), v.end(), greater<int>())
#include <list>			// push_front(x), push_back(x), pop_front(), pop_back(), insert(index, x)
#include <queue>		// push(x), front(), pop()
#include <deque>
#include <stack>		// push(x), top(), pop()
#include <map>			// M[key],  insert(key, val), erase(key), find(key), 
#include <set>			// insert(key), erase(key), find(key)

using namespace std;
typedef long long ll;
// typedef pair<int, int> P;

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

int H, W;
int dx[5] = { -1,0,0,1 };
int dy[5] = { 0,1,-1,0 };
bool flag = false;

void solve() {
	cin >> H >> W;
	string s[51];
	for (int i = 0; i < H; i++) cin >> s[i];

	for (int y = 0; y < H; y++) {//y
		for (int x = 0; x < W; x++) {//x
			if (s[y][x] == '#') {
				flag = false;
				for (int k = 0; k < 4; k++) {
					if (x + dx[k] < 0 || x + dx[k] >= W || y + dy[k] < 0 || y + dy[k] >= H) continue;
					if (s[y + dy[k]][x + dx[k]] == '#')flag = true;
				}
				if (!flag) {
					cout << "No" << endl;
					return;
				}
			}
		}
	}
	cout << "Yes" << endl;
}

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

Measured memory_bytes: 256